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

《《推理与证明方法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3数学推理MathematicalReasoning3.1推理与证明方法ReasoningandMethodsofProof3.2数学归纳方法3.3递推方法7/15/20211定理/Theorem:一个真值为T的命题语句。证明/Proof：用论证方式形成的一个命题语句序列说明一个定理为T。证明的构造/形式：由两个部分组成1、公理、假定或前提/axiom、postulate、hypotheses2、推理规则/ruleofinference其它：引理/lemma、推论/corollary、猜想/conjecture一些基本概念7/15/20212Definit

2、ion1蕴涵演算/logicalimplyingoperation对于任意的公式P和Q，如果P→Q为T，则称P蕴涵Q，记为PQ或P/Q蕴涵演算的推广表示：P1、P2、…、PnQ前提组/hypotheses结论/conclusion证明的基本工具：等值演算，真值表，范式，引用已知简单结论下表是一些常用的简单结论7/15/20213Table1RuleofInferenceNamePP∨QAddition/析取附加式P∧QPSimplification/合取化简式P、QP∧QConjunction/并发式P、P→QQModusponens/分离式

3、¬Q、P→Q¬PModustollens/拒取式¬p、P∨QQDisjunctivesyllogism/析取三段式P→Q、Q→RP→RHypotheticalsyllogism/假言三段式7/15/20214EXAMPLE6Hypotheses:(1)Itisnotsunnythisafternoonanditiscolderthanyesterday.(2)Wewillgoswimmingonlyifitissunny.(3)Ifwedon’tgoswimming,thenwewilltakeacanoetrip.(4)Ifwetakeacanoe

4、trip,thenwewillbehomebysunset.Conclusion:Wewillbehomebysunset.P:Itissunnythisafternoon.Q:Itiscolderthanyesterday.R:Wewillgoswimming.S:Wewilltakeacanoetrip.T:Wewillbehomebysunset.7/15/20215Thehypothesesbecome¬P∧Q,R→P,¬R→S,andS→T,TheconclusionisT¬P∧Q(h)7.S→T(h)¬P(s)8.TR→P(h)¬R(m)¬R→

5、S(h)S(m)7/15/20216Table2.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:Generalization7/15/20217EXAMPLE3苏格拉底论证：人固有一死，苏格拉底是人，因此苏格拉底固有一死。P(x):x是人，D(x):x是要死的

6、，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)7/15/20218EXAMPLE4Hypotheses:任何人如果他喜欢步行，则他就不喜欢乘汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜欢骑自行车，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))7/15/20219x(¬K(

7、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)7/15/202110Indirectproof,negatetheconclusionHypotheses: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

8、.P∨Q(h)Q→S(h)8.¬P(6,7)12.F(11,12)