《推理与证明方法课件.ppt》由会员分享，可在线阅读，更多相关《推理与证明方法课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、推理与证明方法推理与证明方法推理与证明方法推理与证明方法10/5/20221第1页，此课件共38页哦定理定理/Theorem:一个真值为一个真值为T的命题语句。的命题语句。证明证明/Proof：用论证方式形成的一个命题语句序列说明：用论证方式形成的一个命题语句序列说明一个定理为一个定理为T。证明的构造证明的构造/形式：由两个部分组成形式：由两个部分组成1、公理、假定或前提公理、假定或前提/axiom、postulate、hypotheses2、推理规则推理规则/ruleofinference其它：其它：引理引理/lemma、推论推论/corollary、猜想猜想/conjecture一些基本概
2、念一些基本概念一些基本概念一些基本概念10/5/20222第2页，此课件共38页哦Definition 1 Definition 1 蕴涵演算蕴涵演算/logicalimplyingoperation对对于于任任意意的的公公式式P和和Q，如如果果PQ为为T，则则称称P蕴蕴涵涵Q，记记为为PQ或或P/Q蕴涵演算的推广表示：蕴涵演算的推广表示：P1、P2、PnQ前提组前提组/hypotheses结论结论/conclusion证明的基本工具：等值演算，真值表，范式，引用已知简单结论证明的基本工具：等值演算，真值表，范式，引用已知简单结论下表是一些常用的简单结论下表是一些常用的简单结论10/5/202
3、23第3页，此课件共38页哦Table 1 Table 1 Rule of Inference NameP P QAddition/析取附加式P Q P Simplification/合取化简式P、Q P Q Conjunction/并发式P、P Q QModus ponens/分离式 Q、P Q PModus tollens/拒取式 p、P Q QDisjunctive syllogism/析取三段式P Q、Q R P R Hypothetical syllogism/假言三段式10/5/20224第4页，此课件共38页哦EXAMPLE 6 EXAMPLE 6 Hypotheses:(1)I
4、t is not sunny this afternoon and it is colder thanyesterday.(2)We will go swimming only if it is sunny.(3)If we dont goswimming,thenwewilltakeacanoetrip.(4)Ifwetakeacanoetrip,thenwewillbehomebysunset.Conclusion:Wewillbehomebysunset.P:Itissunnythisafternoon.Q:Itiscolderthanyesterday.R:Wewillgoswimmi
5、ng.S:Wewilltakeacanoetrip.T:Wewillbehomebysunset.10/5/20225第5页，此课件共38页哦Thehypothesesbecome PQ,RP,RS,andST,TheconclusionisT1.PQ(h)7.ST(h)2.P(s)8.T3.RP(h)4.R (m)5.RS(h)6.S(m)10/5/20226第6页，此课件共38页哦Table 2.Table 2.Rule of InferenceName x P(x)P(c)if cUUI/全称举例P(c)for an arbitrary cU x P(x)UG/全称推广x P(x)P(c
6、)for some cUEI/存在举例P(c)for some cU x P(x)EG/存在推广U:UniversalI:InstantiationE:ExistentialG:Generalization10/5/20227第7页，此课件共38页哦EXAMPLE 3 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
7、)4.D(S)10/5/20228第8页，此课件共38页哦EXAMPLE 4 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)10/5/20229第9页，
8、此课件共38页哦1.x(K(x)(h)7.W(c)B(c)(UI)2.K(c)(EI)8.W(c)3.x(B(x)K(x)(h)9.x(W(x)(EG)4.B(c)K(c)(UI)5.B(c)6.x(W(x)B(x)(h)10/5/202210第10页，此课件共38页哦Indirect proof,negate the conclusionIndirect proof,negate the conclusionHypotheses:PQ,PR,QSConclusion:SRProof:PQ,PR,QSSR(1)(SR)（否定结论否定结论）5.Q(3,4)9.P Q(5,8)(2)SR（DM）6
9、.R(2)10.(PQ)(9)(3)S（化简）化简）7.PR(h)11.PQ(h)(4)QS(h)8.P(6,7)12.F(11,12)10/5/202211第11页，此课件共38页哦定理证明方法：定理证明方法：1、直接证明、直接证明/directproof:pQ2、间接证明、间接证明/indirectproof:pQ Q P3、空证明、空证明/vacuousproof:pQ其中其中P为为F4、平凡证明、平凡证明/trivialproof：pQ其中其中Q为为T10/5/202212第12页，此课件共38页哦5、反证明、反证明/proofofcontradiction：P PS S6、分例证明、
10、分例证明/proofofcases：P1P2PnQ（P1Q）（P2Q）（PnQ）定理证明方法：定理证明方法：定理证明方法：定理证明方法：10/5/202213第13页，此课件共38页哦7、存在证明、存在证明/existenceproof：xP(x)constructive,nonconstructive8、归纳证明、归纳证明/inductionproof：xP(x)定理证明方法：（含有量词）定理证明方法：（含有量词）定理证明方法：（含有量词）定理证明方法：（含有量词）10/5/202214第14页，此课件共38页哦进一步的思考进一步的思考1、从等值演算到蕴涵演算、从等值演算到蕴涵演算2、从命题
11、公式的推理到谓词公式的推理、从命题公式的推理到谓词公式的推理3、停机问题、停机问题/HaltingProblem10/5/202215第15页，此课件共38页哦练练习习pp.1834、16、43、6810/5/202216第16页，此课件共38页哦3数学推理数学推理MathematicalReasoning3.1推理与证明方法推理与证明方法3.2数学归纳方法数学归纳方法MathematicalInduction3.3递推方法递推方法10/5/202217第17页，此课件共38页哦The well-ordering propertyThe well-ordering propertyThewel
12、l-orderingproperty(良序定理良序定理）Everynonemptysetofnonnegativeintegershasaleastelement(非空的非负整数集合必有最小元）非空的非负整数集合必有最小元）10/5/202218第18页，此课件共38页哦数学归纳法数学归纳法用来证明与用来证明与整数有关整数有关的命题。的命题。数学归纳法的公式表示：数学归纳法的公式表示：P(1)m(m 1P(m)P(m+1)nP(n)1、归纳基础：、归纳基础：P(1)2、归纳步骤：、归纳步骤：m(m 1P(m)P(m+1)数学归纳的理论基础是数学归纳的理论基础是整数公理整数公理，如下所示：，如下
13、所示：Definition 1Definition 110/5/202219第19页，此课件共38页哦皮亚诺公理皮亚诺公理皮亚诺公理皮亚诺公理（1）0N；（2）对每一个）对每一个nN，唯一定义了一个自然数，唯一定义了一个自然数n，n称为称为n的后邻；的后邻；（3）不同的自然数，其后邻也不同；）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是）没有一个自然数的后邻是0；（5）如果有一个子集）如果有一个子集M N满足：满足：0M；nM时必时必nM,则则M=N自然数全体自然数全体N通过皮亚诺公理的五条公理组成。通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（这些公理缺一不可，其中性
14、质（5）称为归纳公理，并指出了自然数是满足公理）称为归纳公理，并指出了自然数是满足公理（1）（4）的最小集合。）的最小集合。10/5/202220第20页，此课件共38页哦数学归纳法的一般公式表示：数学归纳法的一般公式表示：P(k)m(m kP(m)P(m+1)nP(n)1、归纳基础：、归纳基础：P(k)2、归纳步骤：、归纳步骤：m(m kP(m)P(m+1)Definition 2Definition 210/5/202221第21页，此课件共38页哦EXAMPLE 1 EXAMPLE 1 pp.191example51+2+22+2n=2n+1-1数数学学归归纳纳法法的的正正确确性性可可以
15、以用用皮皮亚亚诺诺公公理理与与良良序序定定理理来来证证明。明。10/5/202222第22页，此课件共38页哦第二数学归纳法：第二数学归纳法：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)Definition 3Definition 310/5/202223第23页，此课件共38页哦EXAMPLE 2 EXAMPLE 2 证证明明：任任意意一一个个大大于于1的的自自然然数数或或为为质质数数，或或能能表表示示为若干个质数的乘积。为若干个质数的乘积。10/
16、5/202224第24页，此课件共38页哦有限数学归纳法：对于有限数学归纳法：对于n0 n nk的的P(n)有限数学归纳法的前推公式表示：有限数学归纳法的前推公式表示：P(n0)n(n0 n nk-1P(n)P(n+1)n(n0 n nkP(n)1、归纳基础：、归纳基础：P(n0)2、归纳步骤：、归纳步骤：n(n0 n nk-1P(n)P(n+1)Definition 4Definition 410/5/202225第25页，此课件共38页哦EXAMPLE 3 EXAMPLE 3 pp.195Example11，12，1410/5/202226第26页，此课件共38页哦3.3递归方法递归方法R
17、ecursiveDefinition10/5/202227第27页，此课件共38页哦DEFINITION 1DEFINITION 1定义定义1如如果果一一个个对对象象部部分分地地由由自自己己所所组组成成，或或者者按按它它自自己己定义，则称为是定义，则称为是递归递归的（的（Recursion）。）。递归定义的函数递归定义的函数递归定义的函数递归定义的函数f f：f的定义域：非负整数集的定义域：非负整数集1、递归基础：、递归基础：f(0)2、递归步骤：、递归步骤：f(n)=g(f(k),k0Example 1Example 110/5/202229第29页，此课件共38页哦菲波那契数菲波那契数/F
18、ibonacciF(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 2Example 210/5/202230第30页，此课件共38页哦Example6（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(归纳证明）归纳证明）10/
19、5/202231第31页，此课件共38页哦利用利用Fibonacci数列研究数列研究Euclid算法的计算复杂性。算法的计算复杂性。a=r0,b=r1ri=ri+1qi+1+ri+2(0ri+2ri+1,0In-2)rn-1=rnqnrn1=f2,rn-12rn2f2=f3,假设假设ri+1fn+1-i，ri+2fn-iriri+1+ri+2fn+1-i+fn-i=fn+2-i(0i n-1,10b(n-1)10(n-1)/5hence,n510b+110/5/202232第32页，此课件共38页哦递归定义的集合：递归定义的集合：1、3 S2、X SY SX+Y SS是能够被是能够被3整除的正
20、整数集合。整除的正整数集合。Example 4Example 410/5/202233第33页，此课件共38页哦Well-formedformulae1、命题公式的定义、命题公式的定义2、谓词公式的定义、谓词公式的定义3、数集上的、数集上的+，-，*，/，数学表达式的定义数学表达式的定义Example 5Example 510/5/202234第34页，此课件共38页哦递归算法和迭代算法递归算法和迭代算法递归算法和迭代算法递归算法和迭代算法建立在递归函数上的算法称为递归算法，即要求解一建立在递归函数上的算法称为递归算法，即要求解一个有参数个有参数n的函数可以调用含有更小参数的同样的函数。的函数
21、可以调用含有更小参数的同样的函数。任何一个递归算法都有一个迭代算法与之对应。递归任何一个递归算法都有一个迭代算法与之对应。递归算法要保存和计算一系列中间过步骤，而迭代算法只须算法要保存和计算一系列中间过步骤，而迭代算法只须保存最新结果，因此其计算量与存贮量都比递归算法好，保存最新结果，因此其计算量与存贮量都比递归算法好，但是从逻辑结构上讲，递归算法更加紧凑简洁。但是从逻辑结构上讲，递归算法更加紧凑简洁。10/5/202235第35页，此课件共38页哦小小结结1、数学归纳方法、数学归纳方法基础，步骤基础，步骤一般一般/强，无限强，无限/有限有限2、递归方法、递归方法基础，步骤基础，步骤10/5/202236第36页，此课件共38页哦进一步的思考进一步的思考1、以可数集为对象的应用、以可数集为对象的应用2、与算法的关系、与算法的关系递归算法（递归算法（recursive)与迭代算法与迭代算法(iterative)10/5/202237第37页，此课件共38页哦练练习习pp.1995、48、57pp.2092(b),(d)、8、2510/5/202238第38页，此课件共38页哦