《离散数学PPT电子教案第05章推理与证明技术.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT电子教案第05章推理与证明技术.ppt（69页珍藏版）》请在三一办公上搜索。
1、离 散 数 学,2023年3月7日星期二,2023/3/7,第5章 推理与证明技术,2023/3/7,5.1 本章学习要求,2023/3/7,5.2 命题逻辑的推理理论,2023/3/7,推理的有效性和结论的真实性,有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论。,2023/3/7,推理的有效性和结论的真实性,所谓推理有效，指的是它的结论是它前提合乎逻辑的结果。此时,如果它的前提都为真，那么所得的结论也必然为真;如果它的前提为假,那么所得的结论可以为假.如果推理是有效的，那么不可能它的前提都为真时，
2、而它的结论为假。,2023/3/7,5.2.1 推理的基本概念和推理形式,定义5.2.1 设G1,G2,Gn,是公式，称H是G1,G2,Gn的逻辑结果(G1,G2,Gn共同蕴涵H),当且仅当 H 是 G1G2Gn 的逻辑结果。记为G1,G2,Gn,此时,称 G1,G2,Gn 为有效的。G1,G2,Gn 称为一组前提，有时用集合来表示,记=G1,G2,Gn;H称为结论,它是前提集合的逻辑结果。记为 H。,2023/3/7,判定定理,定理5.2.1 G1,G2,Gn 当且仅当 G1G2Gn 为永真公式。,注意:“”是蕴涵联结词，GH 仍是一个公式;“”描述了两个公式G,H之间的一种逻辑蕴涵关 系,
3、G H 不是公式；,2023/3/7,练习:P146 1(1),1.用基本等价公式的转换方法验证下述论断是否有效.(1)PQ,RS,Q PS 证明(PQ)(RS)Q(PS)=(PQ)RSQ(PS)=PRSQ(PS)=PRSQ(PS)=PRSQ 这说明(PQ)(RS)Q(PS)不是永真式,因此 PQ,RS,Q PS,2023/3/7,5.2.2 判断有效结论的常用方法,2023/3/7,1、真值表技术,设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元，如果将P1,P2,Pn中所有可能的解释及G1,G2,Gn,H对应的真值结果都列在一个表中，根据“”的定义，则有判断方法如下：
4、,(1)如果在所有G1,G2,Gn都具有真值1的行中,H的真值为1,则 H 是 G1,G2,Gn 的逻辑结果。(2)如果在所有H具有真值0的行中,G1,G2,Gn中至少有一个公式的真值为0，则 H 是 G1,G2,Gn 的逻辑结果。,2023/3/7,例5.2.1,判断下列H是否是前提G1,G2的逻辑结果(1)H：Q；G1：P；G2：PQ；(2)H：P；G1：PQ；G2：Q；(3)H：Q；G1：P；G2：PQ。,解,2023/3/7,2 推理定律 I1-I15,设G，H，I，J是任意的命题公式，则有：,I1：GH G;I2：GH H;(简化规则)I3：G GH;I4：H GH;(添加规则)I5
5、：G GH;I6：H GH;I7：(GH)G;I8：(GH)H;I9：G,H GH;,2023/3/7,2 推理定律(续),6)I10：G,GH H(选言三段论)I11：G,G H H7)I12：G,GH H(分离规则)8)I13：H,GH G(否定后件式)9)I14：GH,HI GI(假言三段论)10)I15：GH,GI,HI I(二难推论),2023/3/7,例子,1)、前提：1.如果明天天晴，我们准备外出旅游。PQ2明天的确天晴。P结论：我们外出旅游。Q可描述为：PQ,P Q(分离规则)2)、前提：1.如果一个人是单身汉，则他不幸福。PQ2.如果一个人不幸福，则他死得早。QR结论：单身汉
6、死得早。PR可描述为：PQ,QR PR(假言三段论),2023/3/7,例子(续),3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提:1.凶手为王某或陈某;。PQ 2.如果王某是凶手,则他在作案当晚必外出;PR 3.王某案发之晚并未外出。R结论：陈某是凶手。Q则可描述为：PR,R P(否定后件式)PQ,P Q(选言三段论),2023/3/7,3 演绎法,演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。,引入事实,2023/3/7,推理规则,在数理逻辑中，主要的推理规则有：P
7、规则(称为前提引用规则)：在推导的过程中，可随时引入前提集合中的任意一个前提；规则 T(逻辑结果引用规则)：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。规则 CP(附加前提规则)：如果能从给定的前提集合与公式P推导出S，则能从此前提集合推导出 PS。,2023/3/7,演绎的定义,定义5.2.2 从前提集合推出结论H的一个演绎是构造命题公式的一个有限序列：H1，H2，Hn 其中，Hi 或者是中的某个前提，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H为该演绎的有效结论，或者称从前提能够演绎出结论H来。,2023/3/7,例5.2.
8、2,证明1 PQ P PQ T,(1),E QS P PS T,I SP T,E PR P(PR)(RP),E PR,I SR T,I SR T,(9),E,设前提=PQ,PR,QS,G=SR.证明G.,2023/3/7,例5.2.2(续),证明2 SP(附加前提)QSP QT,I PQP PT,I PR P(PR)(RP),E PR,I R T,I SR CP,SR T,E,2023/3/7,例5.2.3,证 RP(附加前提)RPPPT,IP(QS)PQST,IQPST,IRSCP,设=P(QS),RP,Q,G=RS。证明：G。,2023/3/7,练习:P146 2(1)(3),2.用演绎法
9、证明下述论断的正确性.(1)CD,(CD)P,P(AB),(AB)(RS)RS(3)P,P(Q(RS)QS,2023/3/7,4 间接证明法（反证法）,前面使用过的一些证明方法都是正向推理。但在数学领域中，经常会遇到一些问题，当采用正向推理时很难从前提为真推出结论为真。,PQ等价于QP，因此，为了间接地证明PQ，可以假设Q为假(Q)，然后证明P为假(P)。,2023/3/7,定义5.2.3,假设G1,G2,Gn是一组命题公式，P1,P2,Pn是出现在中的一切命题变元，I是它的任意解释，若有解释I使G1G2Gn取值为“真”，则称公式G1,G2,Gn是一致的，或者说是相容的。如果对任意的解释I，都
10、有G1G2Gn取值为“假”,则称公式G1,G2,Gn是不一致的。或者说G1G2Gn是一个矛盾式。,2023/3/7,间接证明方法(反证法),将结论的否定加入到前提集合中构成一组新的前提，然后证明这组新的前提集合是不相容的，即蕴涵一个矛盾式,G1,G2,Gn,H RR,定理5.2.2 设命题公式集合G1,G2,Gn是一致的,于是从前提集合出发可以逻辑地推出公式H的充要条件是从前提集合 G1,G2,Gn,H 出发，可以逻辑地推出一个矛盾（永假）式来。,2023/3/7,例5.2.6,用反证法证明二难推论 PQ，PR，QRR,证明 PR P R(附加前提)P T,I QR P Q T,I PQ P,
11、I PP,I,2023/3/7,三种证明方法之间的关系,G1,G2,Gn,G1,G2,Gn()G1,G2,Gn()G1,G2,Gn,反证法CP规则证明法直接证明法,2023/3/7,5.2.3 命题逻辑推理的难点,1、弄清楚 蕴涵式PQ 的逻辑关系及其真值,这里Q是P的必要条件.要仔细区分出蕴涵式的前件和后件.2、推理过程中推理规则、基本等值式和逻辑蕴涵式的引用要适当，逻辑思维要清晰。3、弄清楚几种推理方法的区别与联系.一般而言,对于结论是蕴涵式或析取式的,大多可以采取带CP规则的直接证明方法。,2023/3/7,5.2.4 命题逻辑推理的应用,例5.2.7 符号化下面的语句，并用演绎法证明结
12、论是否有效。或者明天下午是天晴，或者是下雨；如果明天下午是天晴，则我将去看电影；如果我去看电影，我就不看书。如果我看书，则天在下雨。,设P：明天下午天晴；Q：明天下午下雨；R：明天下午去看电影；S：明天下午看书。则上述命题可符号化为：P Q，PR，RS SQ。,2023/3/7,例5.2.7 证明,P Q，PR，RS SQ。（1）S P(附加前提)（2）RS P（3）R T,(1),(2),I（4）PR P（5）P T,(3),(4),I（6）P Q（7）Q T,(4),(7),I,2023/3/7,例5.2.8,一个公安人员审查一件盗窃案，已知的事实如下：A或B盗窃了x；若A盗窃了x，则作案
13、时间不能发生在午夜前；若B证词正确，则在午夜时屋里灯光未灭；若B证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。B盗窃了x。,2023/3/7,例5.2.8 证明,设 P：A盗窃了x；Q：B盗窃了x；R：作案时间发生在午夜前；S：B证词正确；T：在午夜时屋里灯光未灭。则上述命题可符号化为：PQ，PR，ST，SR，T Q,2023/3/7,PQ,PR,ST,SR,T Q,证明1 采用直接证明方法（反证法略）（1）T（2）ST（3）S T,(1),(2),I（4）SR（5）R T,(3),(4),I（6）PR P（7）P T,(5),(6),I（8）PQ（9）Q T,(7),(8),I,2
14、023/3/7,作业,第146-147页 2(2),3(3)(6)预习:5.3 谓词逻辑的推理理论,2023/3/7,5.3 谓词逻辑的推理理论,5.3.1 谓词演算的演绎与推理,定义5.3.1 设G1,G2,Gn,是公式,称H是G1,G2,Gn的逻辑结果(G1,G2,Gn共同蕴涵H),当且仅当 H 是G1G2Gn的逻辑结果。记为G1,G2,Gn,此时称G1,G2,Gn 为有效的。G1,G2,Gn称为一组前提，有时用集合来表示，记=G1,G2,Gn。H称为结论。又称H是前提集合的逻辑结果。记为 H。,2023/3/7,判定定理,定理5.3.1 公式H是前提集合=G1,G2,Gn的逻辑结果当且仅
15、当G1G2Gn为有效公式。,2023/3/7,一 推理规律,（1）I16：(x)G(x)(x)G(x)；（2）I17：(x)G(x)(x)H(x)(x)(G(x)H(x)I18：(x)(G(x)H(x)(x)G(x)(x)H(x)（3）I19：(x)(G(x)H(x)(x)G(x)(x)H(x)I20：(x)(G(x)H(x)(x)G(x)(x)H(x),2023/3/7,推理规律（续）,（4）I21：(x)(y)G(x,y)(y)(x)G(x,y)；I22：(x)(y)G(x,y)(y)(x)G(x,y)；I23：(y)(x)G(x,y)(x)(y)G(x,y)；I24：(y)(x)G(x,
16、y)(x)(y)G(x,y)；I25：(x)(y)G(x,y)(y)(x)G(x,y)；,2023/3/7,二 推理规则,1、US（全称特指规则）：(x)G(x)G(y)，其中G(x)对y是自由的 推广：(x)G(x)G(c)，其中c为任意个体常量,2、ES（存在特指规则）：(x)G(x)G(c)，其中c为特定个体常量,2023/3/7,推理规则（续）,3、UG（全称推广规则）：G(y)(x)G(x)，其中G(y)对x是自由的,4、EG（存在推广规则）：G(c)(x)G(x)，其中c为特定个体常量 推广：G(y)(x)G(x)，其中G(y)对x是自由的,2023/3/7,推理规则的正确使用(1
17、),例5.3.1 设实数集中，语句“不存在最大的实数”可符号化为：(x)(y)G(x,y)。其中：G(x,y)：yx。,推导1：（1）(x)(y)G(x,y)P（2）(y)G(y,y)US，（1）,分析：推导1是错误的。正确的推导如下：（1）(x)(y)G(x,y)P（2）(y)G(z,y)US，（1）,注意：使用US规则来消去量词时，所选用取代x的变元y在公式中必须是自由的。,2023/3/7,推理规则的正确使用（2）,推导2：（1）(x)(y)G(x,y)P（2）(y)G(z,y)US，（1）（3）G(z,c)ES，（2）,分析：推导2是错误的。正确的推导如下：（1）(x)(y)G(x,y
18、)P（2）(y)G(z,y)US，（1）（3）G(z,f(z)ES，（2）,注意：使用ES规则来消去量词时，若还有其它自由变元时，则必须用关于自由变元的函数符号来取代常量符号.,2023/3/7,推理规则的正确使用（3）,推导3：（1）(y)G(z,y)P（2）(y)(y)G(y,y)UG，（1）,分析：推导3是错误的。正确的推导如下：（1）(y)G(z,y)P（2）(z)(y)G(z,y)UG，（1）,注意：使用UG规则来添加量词时，所使用的变元符号不能与辖域内的变元符号相同.,2023/3/7,推理规则的正确使用（4）,推导4：（1）G(x,c)P（2）(x)G(x,x)EG，（2）,分析
19、：推导4是错误的。正确的推导如下：（1）G(x,c)P（2）(y)G(x,y)EG，（2）,注意：使用EG规则来添加量词时，所使用的变元符号不能与辖域内的变元符号相同.,2023/3/7,5.3.2 谓词演算的综合推理方法,（1）推导过程中可以引用命题演算中的规则P 和规则T。（2）如果结论是蕴涵式或析取式，我们还可以使用规则CP。（3）若需消去量词，可以引用规则US和规则ES。（4）当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入。,2023/3/7,谓词演算的综合推理方法（续）,（5）证明时可采用如命题演算中的直接证明方法和间接证明方法。（6）在推导过程中，对消去量词的
20、公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。（7）在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。,2023/3/7,例5.3.2,解 设H(x)：x是人；M(x)：x是要死的；s：苏格拉底。则符号化为：(x)(H(x)M(x)，H(s)M(s),证明苏格拉底三段论：“所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。”,证明：(1)(x)(H(x)M(x)P(2)H(x)M(x)US,(1)(3)H(s)P(4)M(s)T,(2),(3)，I,(4)错了！正确的为,证明：(1)(x)(H(x)M(x)P(2)H(s)M(s
21、)US,(1)(3)H(s)P(4)M(s)T,(2),(3)，I,2023/3/7,练习:P147 5(1),5.构造下列推理的证明.(1)(x)(P(x)Q(x),(x)Q(x)(x)P(x),2023/3/7,例5.3.3,证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x),有下面的推导：(1)(x)(P(x)Q(x)P(2)(P(x)Q(x)US,(1)(3)(x)P(x)P(4)P(c)ES,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),(5)错了！,2023/3/7,例5.3.3(),证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x
22、)修改后的推导：(1)(x)(P(x)Q(x)P(2)(P(c)Q(c)US,(1)(3)(x)P(x)P(4)P(c)ES,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),(4)错了！,2023/3/7,例5.3.3(),证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x)正确地推导如下：(1)(x)P(x)P(2)P(c)ES，(1)(3)(x)(P(x)Q(x)P(4)(P(c)Q(c)US,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),2023/3/7,例5.3.4,证明：1)(x)(P(x)Q(x)P 2)(P(c)Q
23、(c)ES,1)3)P(c)T,2),I 4)Q(c)T,2),I 5)(x)P(x)EG,3)6)(x)Q(x)EG,4)7)(x)P(x)(x)Q(x)T,5),6),I,证明：(x)(P(x)Q(x)(x)P(x)(x)Q(x),2023/3/7,例5.3.4(续1),1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)T,1),I5)Q(c)ES,4)6)(P(c)Q(c)T,3),4),I7)(x)(P(x)Q(x)EG,6),请看上述推论的逆推导：,(5)错了！,2023/3/7,例5.3.4(续2),正确地推导：1)(x)P(x
24、)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)T,1),I5)Q(b)ES,4)6)(P(c)Q(b)T,3),4),I7)(x)(y)(P(x)Q(y)EG,6),2023/3/7,例5.3.5 证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),证明：1)(x)P(x)P(附加前提)2)(x)P(x)T,1),E 3)P(c)ES,2)4)(x)(P(x)Q(x)P 5)(P(c)Q(c)US,4)6)Q(c)T,3),5),I 7)(x)Q(x)EG,6)8)(x)P(x)(x)Q(x)CP,1),7)9)(x)P(x)(x)Q(x)T,8
25、),E,2023/3/7,5.3.4 谓词逻辑推理的应用,例5.3.6 每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。,证明 设 H(x)：x是人；P(x)：x喜欢坐汽车；Q(x)：x喜欢骑自行车；R(x)：x喜欢步行。则上述语句可符号化为：(x)(H(x)R(x)P(x)，(x)(H(x)P(x)Q(x)，(x)(H(x)Q(x)(x)(H(x)R(x),2023/3/7,例5.3.7,证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。证明 设谓词如下：P(x)：x是
26、哺乳动物；Q(x)：x是脊椎动物；R(x)：x是胎生动物。则有：(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),2023/3/7,请看下面推导：,1)(x)(P(x)R(x)P2)(P(x)R(x)US,1),错了！,2023/3/7,例5.3.6 证明（续）,1)(x)(P(x)R(x)P2)(x)(P(x)R(x)T,1),E3)(P(c)R(c)ES,2)4)(P(c)R(c)T,3),E5)P(c)T,4),I6)R(c)T,4),I7)(x)(P(x)Q(x)P8)P(c)Q(c)US,7)9)Q(c)T,5),8),I10)Q(c)R(c)T,6),9)
27、,I11)(x)(Q(x)R(x)EG,10),对了！,2023/3/7,练习:P148 7(1),7.将下列命题符号化,并用演绎法证明其论证是否正确.(1)每一个大学生,不是文科学生,就是理工科学生;有的大学生是优等生;小张不是文科生,但他是优等生.因此,如果小张是大学生,他就是理工科学生.,2023/3/7,作业,第147-148页 5(4),7(4)(7)复习:第4章和第5章,2023/3/7,6 指出下列推导中的错误,并改正.,1)(1)(x)P(x)Q(x)P,错了！,(2)P(y)Q(y)US,(1),(2)P(y)Q(x)US,(1),2)(1)P(a)Q(b)P,(2)(x)(
28、P(x)Q(x)EG,(1),(2)(x)(y)(P(x)Q(y)EG,(1),错了！,2023/3/7,6 指出下列推导中的错误,并改正.,3)(1)P(x)Q(c)P,错了！,(2)(x)(P(x)Q(x)EG,(1),(2)(y)(P(x)Q(y)EG,(1),4)(1)(x)(P(x)Q(x)P,(2)P(a)Q(b)US,(1),(2)P(a)Q(a)US,(1),错了！,2023/3/7,6 指出下列推导中的错误,并改正.,5)(1)(x)P(x)P(2)P(c)ES,(1)(3)(x)Q(x)P,错了！,(4)Q(c)ES,(3),(4)Q(b)ES,(3),6)(1)(x)(y
29、)(xy)P(2)(y)(zy)US,(1),(3)(zc)ES,(2)(4)(x)(xc)UG,(3)(5)cc US,(4),错了！,(3)(zf(z)ES,(2),2023/3/7,6 指出下列推导中的错误,并改正.,7)(1)(x)(y)(xy)P(2)(y)(zy)US,(1)(3)(zcz)ES,(2),(4)(x)(xx)UG,(3),错了！,(4)(x)(xcx)UG,(3),2023/3/7,5.构造下列推理的证明.,4)(x)(P(x)(Q(x)R(x)，(x)P(x)(x)(P(x)R(x),证明:(1)(x)P(x)P(2)P(c)ES,(1)(3)(x)(P(x)(Q
30、(x)R(x)P(4)P(c)(Q(c)R(c)US,(3)(5)Q(c)R(c)T,(2),(4),I(6)R(c)T,(5),I(7)P(c)R(c)T,(2),(6),I(8)(x)(P(x)R(x)EG,(7),2023/3/7,7.将下列命题符号化,并证明论证是否正确.,4)没有不守信用的人是可以信赖的;有些可以信赖的人是受过教育的.因此,有些受过教育的人是守信用的.解 设 H(x):x是人;T(x):x守信;R(x):x可信赖;E(x):x受过教育.前提:(x)(H(x)T(x)R(x),(x)(H(x)R(x)E(x).结论:(x)(H(x)E(x)T(x).,2023/3/7,7.将下列命题符号化,并证明论证是否正确.,7)所有的舞蹈者都很有风度;王英是个学生并且是个舞蹈者.因此,有些学生很有风度.解 设 D(x):x是舞蹈者;T(x):x有风度;S(x):x是学生;a:王英.前提:(x)(D(x)T(x),S(a)D(a).结论:(x)(S(x)T(x).,
