《推理与证明方法》PPT课件

5/16/20202:29PM,1,3数学推理MathematicalReasoning3.1推理与证明方法ReasoningandMethodsofProof3.2数学归纳方法3.3递推方法,5/16/20202:29PM,2,定理/Theorem:一个真值为T的命题语句。证明/Proof：用论证方式形成的一个命题语句序列说明一个定理为T。证明的构造/形式：由两个部分组成1、公理、假定或前提/axiom、postulate、hypotheses2、推理规则/ruleofinference其它：引理/lemma、推论/corollary、猜想/conjecture,一些基本概念,5/16/20202:29PM,3,Definition1,蕴涵演算/logicalimplyingoperation对于任意的公式P和Q，如果PQ为T，则称P蕴涵Q，记为PQ或P/Q蕴涵演算的推广表示：P1、P2、PnQ前提组/hypotheses结论/conclusion证明的基本工具：等值演算，真值表，范式，引用已知简单结论下表是一些常用的简单结论,5/16/20202:29PM,4,Table1,5/16/20202:29PM,5,EXAMPLE6,Hypotheses:(1)Itisnotsunnythisafternoonanditiscolderthanyesterday.(2)Wewillgoswimmingonlyifitissunny.(3)Ifwedontgoswimming,thenwewilltakeacanoetrip.(4)Ifwetakeacanoetrip,thenwewillbehomebysunset.Conclusion:Wewillbehomebysunset.P:Itissunnythisafternoon.Q:Itiscolderthanyesterday.R:Wewillgoswimming.S:Wewilltakeacanoetrip.T:Wewillbehomebysunset.,5/16/20202:29PM,6,ThehypothesesbecomePQ,RP,RS,andST,TheconclusionisTPQ(h)7.ST(h)P(s)8.TRP(h)R(m)RS(h)S(m),5/16/20202:29PM,7,Table2.,U:UniversalI:InstantiationE:ExistentialG:Generalization,5/16/20202:29PM,8,EXAMPLE3,苏格拉底论证：人固有一死，苏格拉底是人，因此苏格拉底固有一死。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),5/16/20202:29PM,9,EXAMPLE4,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),5/16/20202:29PM,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),5/16/20202:29PM,11,Indirectproof,negatetheconclusion,Hypotheses:PQ,PR,QSConclusion:SRProof:PQ,PR,QSSR(SR)（否定结论）5.Q(3,4)9.PQ(5,8)SR（DM）6.R(2)10.(PQ)(9)S（化简）7.PR(h)11.PQ(h)QS(h)8.P(6,7)12.F(11,12),5/16/20202:29PM,12,定理证明方法：1、直接证明/directproof:pQ2、间接证明/indirectproof:pQQP3、空证明/vacuousproof:pQ其中P为F4、平凡证明/trivialproof：pQ其中Q为T,5/16/20202:29PM,13,5、反证明/proofofcontradiction：PPSS6、分例证明/proofofcases：P1P2PnQ（P1Q）（P2Q）（PnQ）,定理证明方法：,5/16/20202:29PM,14,7、存在证明/existenceproof：xP(x)constructive,nonconstructive8、归纳证明/inductionproof：xP(x),定理证明方法：（含有量词）,5/16/20202:29PM,15,进一步的思考,1、从等值演算到蕴涵演算2、从命题公式的推理到谓词公式的推理3、停机问题/HaltingProblem,5/16/20202:29PM,16,练习,pp.1834、16、43、68,5/16/20202:29PM,17,3数学推理MathematicalReasoning3.1推理与证明方法3.2数学归纳方法MathematicalInduction3.3递推方法,5/16/20202:29PM,18,Thewell-orderingproperty,Thewell-orderingproperty(良序定理）Everynonemptysetofnonnegativeintegershasaleastelement(非空的非负整数集合必有最小元）,5/16/20202:29PM,19,数学归纳法用来证明与整数有关的命题。数学归纳法的公式表示：P(1)m(m1P(m)P(m+1)nP(n)1、归纳基础：P(1)2、归纳步骤：m(m1P(m)P(m+1)数学归纳的理论基础是整数公理，如下所示：,Definition1,5/16/20202:29PM,20,皮亚诺公理,（1）0N；（2）对每一个nN，唯一定义了一个自然数n，n称为n的后邻；（3）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是0；（5）如果有一个子集MN满足：0M；nM时必nM,则M=N自然数全体N通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数是满足公理（1）（4）的最小集合。,5/16/20202:29PM,21,数学归纳法的一般公式表示：P(k)m(mkP(m)P(m+1)nP(n)1、归纳基础：P(k)2、归纳步骤：m(mkP(m)P(m+1),Definition2,5/16/20202:29PM,22,EXAMPLE1,pp.191example51+2+22+2n=2n+1-1数学归纳法的正确性可以用皮亚诺公理与良序定理来证明。,5/16/20202:29PM,23,第二数学归纳法：P(n0)k(kn0P(n0)P(n0+1)P(k)P(k+1)nP(n)1、归纳基础：P(n0)2、归纳步骤：k(kn0P(n0)P(n0+1)P(k)P(k+1),Definition3,5/16/20202:29PM,24,EXAMPLE2,证明：任意一个大于1的自然数或为质数，或能表示为若干个质数的乘积。,5/16/20202:29PM,25,有限数学归纳法：对于n0nnk的P(n)有限数学归纳法的前推公式表示：P(n0)n(n0nnk-1P(n)P(n+1)n(n0nnkP(n)1、归纳基础：P(n0)2、归纳步骤：n(n0nnk-1P(n)P(n+1),Definition4,5/16/20202:29PM,26,EXAMPLE3,pp.195Example11，12，14,5/16/20202:29PM,27,3.3递归方法RecursiveDefinition,5/16/20202:29PM,28,DEFINITION1,定义1如果一个对象部分地由自己所组成，或者按它自己定义，则称为是递归的（Recursion）。递归定义的函数f：f的定义域：非负整数集1、递归基础：f(0)2、递归步骤：f(n)=g(f(k),k0,Example1,5/16/20202:29PM,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，利用菲波那契数可以推算出兔子繁衍规律。,Example2,5/16/20202:29PM,31,Example6（PP.205），f3=2,f4=32,(归纳基础）fn-1n-3,fnn-2(n3)(归纳假设）fn+1=fn-1+fnn-2+n-3=n-3(1+)=n-32=n-1(归纳证明）,5/16/20202:29PM,32,利用Fibonacci数列研究Euclid算法的计算复杂性。a=r0,b=r1ri=ri+1qi+1+ri+2(0ri+2n-1,10b(n-1)10(n-1)/5hence,n510b+1,5/16/20202:29PM,33,递归定义的集合：1、3S2、XSYSX+YSS是能够被3整除的正整数集合。,Example4,5/16/20202:29PM,34,Well-formedformulae1、命题公式的定义2、谓词公式的定义3、数集上的+，-，*，/，数学表达式的定义,Example5,5/16/20202:29PM,35,递归算法和迭代算法,建立在递归函数上的算法称为递归算法，即要求解一个有参数n的函数可以调用含有更小参数的同样的函数。任何一个递归算法都有一个迭代算法与之对应。递归算法要保存和计算一系列中间过步骤，而迭代算法只须保存最新结果，因此其计算量与存贮量都比