3.1 证明方法

推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.13数学推理MathematicalReasoning3.1推理与证明方法ReasoningandMethodsofProof3.2数学归纳方法3.3递推方法推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.2定理/Theorem:一个真值为T的命题语句。证明/Proof：用论证方式形成的一个命题语句序列说明一个定理为T。证明的构造/形式：由两个部分组成1、公理、假定或前提/axiom、postulate、hypotheses2、推理规则/ruleofinference其它：引理/lemma、推论/corollary、猜想/conjecture一些基本概念推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.3Definition1蕴涵演算/logicalimplyingoperation对于任意的公式P和Q，如果P→Q为T，则称P蕴涵Q，记为PQ或P/Q蕴涵演算的推广表示：P1、P2、…、PnQ前提组/hypotheses结论/conclusion推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.4Table1RuleofInferenceNamePP∨QAddition/析取附加式P∧QPSimplification/合取化简式P、QP∧QConjunction/并发式P、P→QQModusponens/分离式¬Q、P→Q¬PModustollens/拒取式¬p、P∨QQDisjunctivesyllogism/析取三段式P→Q、Q→RP→RHypotheticalsyllogism/假言三段式推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.5EXAMPLE1Hypotheses:P∨Q,P→R,Q→SConclusion:S∨RProof:P∨Q,P→R,Q→SS∨R推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.6EXAMPLE2Hypotheses:(1)Itisnotsunnythisafternoonanditiscolderthanyesterday.(2)Wewillgoswimmingonlyifitissunny.(3)Ifwedon’tgoswimming,thenwewilltakeacanoetrip.(4)Ifwetakeacanoetrip,thenwewillbehomebysunset.Conclusion:Wewillbehomebysunset.P:Itissunnythisafternoon.Q:Itiscolderthanyesterday.R:Wewillgoswimming.S:Wewilltakeacanoetrip.T:Wewillbehomebysunset.推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.7Table2.RuleofInferenceNamexP(x)P(c)ifcUUI/全称举例P(c)foranarbitrarycUxP(x)UG/全称推广xP(x)P(c)forsomecUEI/存在举例P(c)forsomecUxP(x)EG/存在推广U:UniversalI:InstantiationE:ExistentialG:Generalization推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.8EXAMPLE3苏格拉底论证：人固有一死，苏格拉底是人，因此苏格拉底固有一死。推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.9EXAMPLE4Hypotheses:任何人如果他喜欢步行，则他就不喜欢乘汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜欢骑自行车，Conclusion:因此有的人不喜欢步行。推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.10定理证明方法：1、直接证明/directproof:p→Q2、间接证明/indirectproof:p→Q¬Q→¬P3、空证明/vacuousproof:p→Q其中P为F4、平凡证明/trivialproof：p→Q其中Q为T推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.11定理证明方法：5、反证明/proofofcontradiction：P¬PS∧¬S6、分例证明/proofofcases：P1∨P2…∨Pn→Q（P1→Q）∧（P2→Q）…∧（Pn→Q）推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.12定理证明方法：7、存在证明/existenceproof：xP(x)constructive,nonconstructive8、归纳证明/inductionproof：xP(x)推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.13小结1、推理应用中的六个规则2、证明的八种不同方法推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.14进一步的思考1、从等值演算到蕴涵演算2、从命题公式的推理到谓词公式的推理3、停机问题/HaltingProblem推理与证明方法1/21/20202:26PMDerenChen,ZhejiangUniv.15练习pp.1834、16、43、68