推理与证明方法.ppt
6/20/2023,1,3 数学推理 Mathematical Reasoning 3.1 推理与证明方法 Reasoning and Methods of Proof 3.2 数学归纳方法 3.3 递推方法,6/20/2023,2,定理/Theorem:一个真值为T的命题语句。证明/Proof：用论证方式形成的一个命题语句序列说明一个定理为T。证明的构造/形式：由两个部分组成 1、公理、假定或前提/axiom、postulate、hypotheses 2、推理规则/rule of inference其它：引理/lemma、推论/corollary、猜想/conjecture,一些基本概念,6/20/2023,3,Definition 1,蕴涵演算/logical implying operation 对于任意的公式P和Q，如果P Q 为T，则称P蕴涵Q，记为P Q 或P/Q蕴涵演算的推广表示：P1、P2、Pn Q 前提组/hypotheses 结论/conclusion证明的基本工具：等值演算，真值表，范式，引用已知简单结论下表是一些常用的简单结论,6/20/2023,4,Table 1,6/20/2023,5,EXAMPLE 6,Hypotheses:(1)It is not sunny this afternoon and it is colder than yesterday.(2)We will go swimming only if it is sunny.(3)If we dont go swimming,then we will take a canoe trip.(4)If we take a canoe trip,then we will be home by sunset.Conclusion:We will be home by sunset.P:It is sunny this afternoon.Q:It is colder than yesterday.R:We will go swimming.S:We will take a canoe trip.T:We will be home by sunset.,6/20/2023,6,The hypotheses become P Q,R P,R S,and S T,The conclusion is T P Q(h)7.S T(h)P(s)8.T R P(h)R(m)R S(h)S(m),6/20/2023,7,Table 2.,U:Universal I:InstantiationE:Existential G:Generalization,6/20/2023,8,EXAMPLE 3,苏格拉底论证：人固有一死，苏格拉底是人，因此苏格拉底固有一死。P(x):x是人，D(x):x是要死的，S:苏格拉底。x(P(x)D(x),P(S)D(S)1.x(P(x)D(x)(h)3.P(S)2.P(s)D(s)(UG)4.D(S),6/20/2023,9,EXAMPLE 4,Hypotheses:任何人如果他喜欢步行，则他就不喜欢乘汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜欢骑自行车，Conclusion:因此有的人不喜欢步行。W(x):喜欢步行，B(x):x喜欢乘汽车，K(x)：x喜欢骑自行车；前提：x(W(x)B(x)，x(B(x)K(x),x(K(x),结论：x(W(x),6/20/2023,10,x(K(x)(h)7.W(c)B(c)(UI)K(c)(EI)8.W(c)x(B(x)K(x)(h)9.x(W(x)(EG)B(c)K(c)(UI)B(c)x(W(x)B(x)(h),6/20/2023,11,Indirect proof,negate the conclusion,Hypotheses:P Q,P R,Q SConclusion:S RProof:P Q,P R,Q S S R(S R)（否定结论）5.Q(3,4)9.P Q(5,8)S R（DM）6.R(2)10.(P Q)(9)S（化简）7.P R(h)11.P Q(h)Q S(h)8.P(6,7)12.F(11,12),6/20/2023,12,定理证明方法：1、直接证明/direct proof:p Q 2、间接证明/indirect proof:p Q Q P3、空证明/vacuous proof:p Q 其中 P为 F4、平凡证明/trivial proof：p Q 其中 Q 为T,6/20/2023,13,5、反证明/proof of contradiction：P P S S6、分例证明/proof of cases：P1 P2 Pn Q（P1 Q）（P2 Q）（Pn Q）,定理证明方法：,6/20/2023,14,7、存在证明/existence proof：x P(x)constructive,nonconstructive8、归纳证明/induction proof：x P(x),定理证明方法：（含有量词）,6/20/2023,15,进一步的思考,1、从等值演算到蕴涵演算 2、从命题公式的推理到谓词公式的推理 3、停机问题/Halting Problem,6/20/2023,16,练 习,pp.183 4、16、43、68,6/20/2023,17,3 数学推理 Mathematical Reasoning 3.1 推理与证明方法 3.2 数学归纳方法 Mathematical Induction 3.3 递推方法,6/20/2023,18,The well-ordering property,The well-ordering property(良序定理）Every nonempty set of nonnegative integers has a least element(非空的非负整数集合必有最小元）,6/20/2023,19,数学归纳法用来证明与整数有关的命题。数学归纳法的公式表示：P(1)m(m 1 P(m)P(m+1)n P(n)1、归纳基础：P(1)2、归纳步骤：m(m 1 P(m)P(m+1)数学归纳的理论基础是整数公理，如下所示：,Definition 1,6/20/2023,20,皮亚诺公理,（1）0N；（2）对每一个nN，唯一定义了一个自然数n，n 称为n的后邻；（3）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是0；（5）如果有一个子集MN满足：0M；nM时必n M,则M=N自然数全体N通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数是满足公理（1）（4）的最小集合。,6/20/2023,21,数学归纳法的一般公式表示：P(k)m(m k P(m)P(m+1)n P(n)1、归纳基础：P(k)2、归纳步骤：m(m k P(m)P(m+1),Definition 2,6/20/2023,22,EXAMPLE 1,pp.191 example 5 1+2+22+2n=2n+1-1 数学归纳法的正确性可以用皮亚诺公理与良序定理来证明。,6/20/2023,23,第二数学归纳法：P(n0)k(k n0 P(n0)P(n0+1)P(k)P(k+1)n P(n)1、归纳基础：P(n0)2、归纳步骤：k(k n0 P(n0)P(n0+1)P(k)P(k+1),Definition 3,6/20/2023,24,EXAMPLE 2,证明：任意一个大于1 的自然数或为质数，或能表示为若干个质数的乘积。,6/20/2023,25,有限数学归纳法：对于 n0 n nk 的 P(n)有限数学归纳法的前推公式表示：P(n0)n(n0 n nk-1 P(n)P(n+1)n(n0 n nk P(n)1、归纳基础：P(n0)2、归纳步骤：n(n0 n nk-1 P(n)P(n+1),Definition 4,6/20/2023,26,EXAMPLE 3,pp.195 Example 11，12，14,6/20/2023,27,3.3 递归方法 Recursive Definition,6/20/2023,28,DEFINITION 1,定义1如果一个对象部分地由自己所组成，或者按它自己定义，则称为是递归的（Recursion）。递归定义的函数f：f的定义域：非负整数集 1、递归基础：f(0)2、递归步骤：f(n)=g(f(k),kn,n0,6/20/2023,29,自然数阶乘n!就是采用递归方法计算出来的。令f(n)=n!，则f(n)可以表示为：f(0)=1f(n)=nf(n1)n0,Example 1,6/20/2023,30,菲波那契数/FibonacciF(0)=0，F(1)=1F(n)=F(n1)+F(n2)n1由上述公式，我们得到：F(2)=1，F(3)=2，F(4)=3，F(5)=5，F(6)=8，利用菲波那契数可以推算出兔子繁衍规律。,Example 2,6/20/2023,31,Example 6（PP.205），f3=2,f4=3 2,(归纳基础）fn-1 n-3,fn n-2(n3)(归纳假设）fn+1=fn-1+fn n-2+n-3=n-3(1+)=n-3 2=n-1(归纳证明）,6/20/2023,32,利用 Fibonacci数列研究Euclid算法的计算复杂性。a=r0,b=r1 ri=ri+1qi+1+ri+2(0 ri+2 n-1,10b(n-1)10(n-1)/5 hence,n5 10b+1,6/20/2023,33,递归定义的集合：1、3 S2、X S Y S X+Y SS是能够被3 整除的正整数集合。,Example 4,6/20/2023,34,Well-formed formulae 1、命题公式的定义 2、谓词公式的定义 3、数集上的+，-，*，/，数学表达式的定义,Example 5,6/20/2023,35,递归算法和迭代算法,建立在递归函数上的算法称为递归算法，即要求解一个有参数n的函数可以调用含有更小参数的同样的函数。任何一个递归算法都有一个迭代算法与之对应。递归算法要保存和计算一系列中间过步骤，而迭代算法只须保存最新结果，因此其计算量与存贮量都比递归算法好，但是从逻辑结构上讲，递归算法更加紧凑简洁。,6/20/2023,36,小 结,1、数学归纳方法 基础，步骤 一般/强，无限/有限2、递归方法 基础，步骤,6/20/2023,37,进一步的思考1、以可数集为对象的应用 2、与算法的关系 递归算法（recursive)与迭代算法(iterative),6/20/2023,38,练 习,pp.199 5、48、57pp.209 2(b),(d)、8、25,
