3-1 NEW 数学推理--Sec 1 证明的方法.ppt

* 似乎没法证明这些是重言式，但是，它们不证自明。 很多书上的推理规则是用“竖式”表示的，竖式中含有一个“therefore”和一个horizontal bar。。 * * * 汉语里，论证和证明还没有发现有什么区别。一样。 可能不一样，论证强调的是形式，而且每当。证明则不是这样。See：/wiki/Argument_form ，/wiki/Argument#Deductive_arguments 。 有效指合乎逻辑， * * (p?q)?q ? p，当p假 q真时，为假。 (p?q)??p ? ?q，当p假 q真时，为假。 上面两个例子，在 你学过离散数学，且你没有做书中的每一道习题时，为假。 fallacy ( 1. 错误推理，2. 似是而非。) * 许多定理都是逻辑蕴涵式,也有的不是,如根号下2是无理数，费尔马大定理，当然这里面也隐含着蕴含关系. 3.和4.可得结论 对于自然数n（指≥0的整数n）成立：若n1则n2n。 若a, b为正整数， a? b，则 an ? bn 对一切自然数都成立。可由数学归纳法证明。n=0时的证明为一个平凡证明。 * 欲证明P为真，证明 ?P ? F (其逆否命题说明P为真)，只要证明：? P ? S ∧ ? S (矛盾式F)， §1.2讲该式子过（后面部分）。 （简单证明方法的创造性地、巧妙地应用，研究中也如此）。当然需要对所研究问题的长期的、反复的思考，然后灵感才能冒出来（功到自然成）。 * * 判断“给定一个程序及其一个输入，执行时是否停机的算法或者程序是不存在的。停机问题是一个不可解问题（ unsolvable ）。 * wiki百科中的康托尔定理条目中有此证明。 * * 任何一个整数都可以分解成一系列素数因子的乘积，这是“算术基本定理”，下节（数学归纳法）给与证明。 * x：算法 （再形式一些：U是所有算法的集合，x ? U。） P(x)：x能够对每一个程序及该程序的所有输入都判断出是否停机。 ?x P(x) ?x（P(x)为假），或者， ?x ?P(x) （每个x，P(x)都为假） * 8、若存在两个逆元q, r,证明q=r；或者若q?r，推出矛盾；或者若q?r，证明r不具有逆元的性质。 9、记号? ，p ? q：若当命题p为真，必有命题q为真。即p ? q表示p ? q为重言式或永真式。 * * * 以后可以把递归的基本概念和方法讲一下，也是个基础，也许在看文献时会用到。递归算法确实用处不大，但至少有这么一个算法，而且在问题的规模小时还是有效的。 第3章 数学推理 证明的方法： 什么样的证明过程是正确的？推理规则。 有哪些方法可用来构造证明？ 这便于我们：阅读（理解、评判）已有的数学证明; 构建证明。 数学归纳法：证明关于整数n定理(良序集也成立*) 程序正确性：证明方法的应用 （自学） 名词与基本概念 定理/Theorem: 一个真值为真的命题。 证明/Proof：说明一个定理为真的过程。 是从定理的前提假设(hypotheses)出发，应用推理规则(rule of inference)，把证明的各个步骤联系起来，直到得出定理的结论(conclusion)。 推理规则/rule of inference 从某些断言得出结论的方法； 它把证明的各个步骤联系起来. §1 证明的方法 其他几个相关名词 公理/axiom：不证自明、公认正确。 引理/lemma：使复杂的证明过程层次分明。 如费尔马大定理(曾叫费马猜想)的证明包括引理。 推论/corollary：根据定理可直接得出的结论。 引理和推论都是定理。 猜想/conjecture：到目前为止真值未知的命题。 例如：哥德巴赫猜想，费马猜想，P≠NP。 tautology(重言式) Name p ? [ p ?q ] addition/析取附加式 [ p ?q ] ? p simplification/合取化简式 [ (p) ? (q) ] ? [ p?q ] conjunction/合取式 [ p ? (p?q) ] ? q ] modus ponens/分离式、假言推理 [ ?q ? (p ? q) ] ? ? p modus tollens/取拒式、否认结论式 [ ?p ? (p?q) ] ? q disjunctive syllogism/析取三段式 [ (p ? q) ? (q ? r) ] ? [ p ? r ] hypothetical syllogism/假言三段式 推理规则(Rule of Inference) 可择其一进行证明 当左边为真，右边也为真。