离散数学ppt电子教案第05章推理与证明技术课件

《离散数学ppt电子教案第05章推理与证明技术课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学02九月2021第5章推理与证明技术数学归纳法的使用3按定义证明方法4命题逻辑的推理理论1谓词逻辑的推理理论25.1本章学习要求1掌握各种不同类型的规则和公理，特别是命题逻辑和谓词逻辑的推理规则和公理3理解谓词逻辑的精髓，将其思想贯穿于所有的证明之中2熟练掌握不同证明方法的证明原理、不同的应用场景重点掌握一般掌握了解5.2命题逻辑的推理理论概念描述问题的句子；AddYourText判断对概念的肯定与否定的判断；推理从一个或多个前提推出结论的思维过程。推理的有效性和结论的真实性有效的推理不一定产生真实的结论；而产生

2、真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论。推理的有效性和结论的真实性所谓推理有效，指的是它的结论是它前提合乎逻辑的结果。此时,如果它的前提都为真，那么所得的结论也必然为真;如果它的前提为假,那么所得的结论可以为假.如果推理是有效的，那么不可能它的前提都为真时，而它的结论为假。5.2.1推理的基本概念和推理形式定义5.2.1设G1,G2,…,Gn,Ｈ是公式，称H是G1,G2,…,Gn的逻辑结果(G1,G2,…,Gn共同蕴涵H),当且仅当H是G1∧G2∧…∧Gn

3、的逻辑结果。记为G1,G2,…,GnＨ,此时,称G1,G2,…,GnＨ为有效的。G1,G2,…,Gn称为一组前提，有时用集合Г来表示,记Г={G1,G2,…,Gn};H称为结论,它是前提集合的逻辑结果。记为ГH。判定定理定理5.2.1G1,G2,…,GnＨ当且仅当G1∧G2∧…∧Gn→Ｈ为永真公式。注意:“→”是蕴涵联结词，G→H仍是一个公式;“”描述了两个公式G,H之间的一种逻辑蕴涵关系,GH不是公式；练习:P1461(1)1.用基本等价公式的转换方法验证下述论断是否有效.(1)PQ,RS,QPS

4、证明(PQ)(RS)Q(PS)=(PQ)RSQ(PS)=PRSQ(PS)=PRSQ(PS)=PRSQ这说明(PQ)(RS)Q(PS)不是永真式,因此PQ,RS,Q⇏PS5.2.2判断有效结论的常用方法要求Г=｛G1,G2,…,Gn｝ГH也就是G1∧G2∧…∧Gn→Ｈ为永真公式因而真值表技术、演绎法和间接证明方法1、真值表技术设P1,P2,…,Pn是出现在前提G1,G2,…,Gn和结论H中的一切命题变元，如果将P1,P2,…,Pn中

5、所有可能的解释及G1,G2,…,Gn,H对应的真值结果都列在一个表中，根据“→”的定义，则有判断方法如下：(1)如果在所有G1,G2,…,Gn都具有真值1的行中,H的真值为1,则H是G1,G2,…,Gn的逻辑结果。(2)如果在所有H具有真值0的行中,G1,G2,…,Gn中至少有一个公式的真值为0，则H是G1,G2,…,Gn的逻辑结果。例5.2.1判断下列H是否是前提G1,G2的逻辑结果(1)H：Q；G1：P；G2：P→Q；(2)H：┐P；G1：P→Q；G2：┐Q；(3)H：Q；G1：┐P；G2：P→Q。解PQG1G2H0

6、0010010111010011111(1)PQG1G2H00111011011001011100(2)PQG1G2H00110011111000011011(3)2推理定律I1-I15设G，H，I，J是任意的命题公式，则有：I1：G∧HG;I2：G∧HH;(简化规则)I3：GG∨H;I4：HG∨H;(添加规则)I5：GG→H;I6：HG→H;I7：(G→H)G;I8：(G→H)H;I9：G,HG∧H;2推理定律(续)6)I10：G,G∨HH(选言三段论)I11：G,GHH7)I12：G

7、,G→HH(分离规则)8)I13：H,G→HG(否定后件式)9)I14：G→H,H→IG→I(假言三段论)10)I15：G∨H,G→I,H→II(二难推论)例子1)、前提：1.如果明天天晴，我们准备外出旅游。P→Q2．明天的确天晴。P结论：我们外出旅游。Q可描述为：P→Q,PQ(分离规则)2)、前提：1.　如果一个人是单身汉，则他不幸福。P→Q2.　如果一个人不幸福，则他死得早。Q→R结论：单身汉死得早。P→R可描述为：P→Q,Q→RP→R(假言三段论)例子(续)3)、某女子在某日晚归家途中被杀害，据多方

8、调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提:1.凶手为王某或陈某;。P∨Q2.如果王某是凶手,则他在作案当晚必外出;P→R3.王某案发之晚并未外出。┐R结论：陈某是凶手。Q则可描述为：P→R,┐R┐P(否定后件式)P∨Q,┐PQ(选言三段论)3演绎法演绎法是