推理与证明技术.ppt

《推理与证明技术.ppt》由会员分享，可在线阅读，更多相关《推理与证明技术.ppt（103页珍藏版）》请在三一办公上搜索。

1、离 散 数 学,电子科技大学,计算机科学与工程学院示 范 性 软 件 学 院,2023年6月20日星期二,第5章 推理与证明技术,5.1 本章学习要求,5.2 命题逻辑的推理理论,推理的有效性和结论的真实性,有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论。,推理的有效性和结论的真实性,所谓推理有效，指的是它的结论是它的前提的合乎逻辑的结果。即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假；如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。,5.2.

2、1 推理的基本概念和推理形式,定义 设G1,G2,Gn,是公式，称H是G1,G2,Gn的逻辑结果(G1,G2,Gn共同蕴涵H)，当且仅当H 是G1G2Gn的逻辑结果(logic conclusion)。记G1,G2,Gn，此时称G1,G2,Gn 为有效的(efficacious)，否则称为无效的（inefficacious）。G1,G2,Gn称为一组前提(Premise)，有时用集合来表示，记=G1,G2,Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为 H。,判定定理,定理 公式H是前提集合=G1,G2,Gn的逻辑结果当且仅当G1G2Gn为永真公式。,证明：“”若G

3、1,G2,Gn，但G1G2GnH不是永真式。于是，必存在G1,G2,Gn，H的一个解释I，使得G1G2Gn为真，而H为假，因此对于该解释I，有G1,G2,Gn都为真，而H为假，这就与推理形式G1,G2,Gn 是有效的相矛盾.故：G1G2GnH是永真公式。,判定定理（续）,“”若G1G2GnH是永真式，但G1,G2,Gn 不是有效的推理形式，故存在G1,G2,Gn,H的一个解释I，使得G1,G2,Gn都为真，而H为假，故G1G2Gn为真，而H为假，即是说G1G2Gn H为假，这 就与G1G2GnH是永真式相矛盾，所以G1,G2,Gn 是有效的推理形式。,“”与“”的不同,1.“”仅是一般的蕴涵联

4、结词，GH的结果仍是一个公式，而“”却描述了两个公式G，H之间的一种逻辑蕴涵关系，G H的“结果”，是非命题公式；,2.用计算机来判断G H是办不到的。然而计算机却可“计算”公式GH是否为永真公式。,5.2.2 判断有效结论的常用方法,1、真值表技术,设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元，如果将P1,P2,Pn中所有可能的解释及G1,G2,Gn，H的对应真值结果都列在一个表中，根据“”的定义，则有判断方法如下：,对所有G1,G2,Gn都具有真值T的行(表示前提为真的行)，如果在每一个这样的行中，H也具有真值T，则H是G1,G2,Gn的逻辑结果。对所有H具有真值

5、为F的行(表示结论为假的行),如果在每一个这样的行中，G1,G2,Gn中至少有一个公式的真值为F(前提也为假)，则H是G1,G2,Gn的逻辑结果.,例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。,解,2 推理定律,设G，H，I，J是任意的命题公式，则有：,I1：GH G(简化规则)I2：GH HI3：G GH(添加规则)I4：H GHI5：G GHI6：H GHI7：(GH)GI8：(GH)HI9：G,H GH,2 推理定律(续),6）I10：G,GH H(选言/析取三段论)I1

6、1：G,G H H7）I12：G,GH H(分离规则)8）I13：H,GH G(否定后件式)9）I14：GH,HI GI(假言三段论)10）I15：GH,GI,HI I(二难推论),例子,1)、前提：1.如果明天天晴，我们准备外出旅游。PQ2明天的确天晴。P结论：我们外出旅游。Q可描述为：PQ，P Q(分离规则)2)、前提：1.如果一个人是单身汉，则他不幸福。PQ2.如果一个人不幸福，则他死得早。QR结论：单身汉死得早。PR可描述为：PQ，QR PR(假言三段论),例子(续1),3)、某人在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出

7、，根据上述案情可得：前提：1.凶手为王某或陈某。PQ 2.如果王某是凶手，则他在作案当晚必外出 PR3.王某案发之晚并未外出。R结论：陈某是凶手。Q则可描述为：PR,R P(否定后件式)PQ，P Q(选言三段论),例子(续2),4)、前提：1.如果某同学为省二级以上运动员，则他将被大学录取。PR2.如果某同学高考总分在560分以上，则将被大学录取。QR3.某同学高考总分在560分以上或者是省二级运动员。PQ结论：该同学被大学录取。R则上述例子可描述为：PQ，PR，QR R(二难推论),3 演绎法,演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。,引入事实,引入推理规

8、则,在数理逻辑中，主要的推理规则有：P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提；规则（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。规则（附加前提规则）：如果能从给定的前提集合与公式P推导出S，则能从此前提集合推导出PS。,演绎的定义,定义 从前提集合推出结论H的一个演绎是指构造命题公式的一个有限序列：H1，H2，Hn 其中，Hi或者是中的某个前提，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H为该演绎的有效结论，或者称从前提能够演绎出结论H来。,例5.2.2,证明1 PQP

9、PQT(1)QSP PST SPT PRP(PR)(RP)PR SR T SRT(9),设前提=PQ,PR,QS,G=SR。证明G。,设前提=PQ,PR,QS,G=SR。证明G。,证明2SP(附加前提)QSP QT,I PQP PT,I PR P(PR)(RP),E PR,I R T,I SR CP,SR T,E,例,证 RP(附加前提)RPPPT,IP(QS)PQST,IQPST,IRSCP,设=P(QS),RP,Q,G=RS。证明：G。,4 间接证明法（反证法）,前面使用过的一些证明方法都是正向推理。但在数学领域中，经常会遇到一些问题，当采用正向推理时很难从前提为真推出结论为真。,PQ等价

10、于QP，因此，为了间接地证明PQ，可以假设Q为假(Q)，然后证明P为假(P)。,例,设n是一个整数，证明：如果n2是奇数，那么n是奇数。,证明 设n是偶数，则n2k，这里k是一个整数。于是有：n2(2k)2=4k2=2(2k2)所以n2是偶数。因而证明了若n是偶数，则n2是偶数，它是已知命题的逆否式。因此，证明了所给的命题。,定义,假设G1,G2,Gn是一组命题公式，P1,P2,Pn是出现在中的一切命题变元，I是它的任意解释，若有解释I使G1G2Gn取值为“真”，则称公式G1,G2,Gn是一致的，或者说是相容的。如对任意的解释I，都有G1G2Gn取值为“假”,则称公式G1,G2,Gn是不一致的

11、。或者说G1G2Gn是一个矛盾式。,定义,G1G2Gn是矛盾式当且仅当 G1G2Gn,其中，R可为任意公式，RR为一矛盾式。,间接证明方法,将结论的否定加入到前提集合中，构成一组新的前提，然后证明这组新的前提集合是不相容的，即蕴涵一个矛盾式。G1,G2,Gn,H RR,定理5.2.2 设命题公式集合G1,G2,Gn是一致的，于是从前提集合出发可以逻辑地推出公式H的充要条件是从前提集合G1,G2,Gn，H出发，可以逻辑地推出一个矛盾（永假）式来。,例,证明不存在有理数p/q其平方为2，即，证明 是无理数。,证明 对某两个整数p和q，假设(p/q)2=2成立，并且p和q没有公因子。如果原来选择的p

12、/q不是最小项，则可以用它等价的最小项形式来取代它。于是p2=2q2，所以p2是偶数，这就推出p是偶数，因为一个奇数的平方是奇数。,例5.2.5 证明（续）,因此存在某个整数n使得p2n成立。因此2q2p2(2n)2=4n2，即有q2=2n2，所以q2是偶数，从而q是偶数，于是得到p和q都是偶数，故它们有一个公因子2，这与假设相矛盾。因此假设一定为假。,例,用反证法证明二难推论 PQ，PR，QR R,证明 R P(附加前提)PR P P T,I QR P Q T,(1),I PQ P,I PP,I,三种证明方法之间的关系,G1,G2,Gn,G1,G2,Gn()G1,G2,Gn()G1,G2,G

13、n,反证法CP规则证明法直接证明法,5.2.3 命题逻辑推理的难点,1、弄清楚蕴涵式PQ的逻辑关系及其真值，这里Q是P的必要条件。无论蕴涵关系如何表述，都要仔细地区分出蕴涵式的前件和后件。2、推理过程中推理规则、基本等值式和逻辑蕴涵式的引用要适当，逻辑思维要清晰。,5.2.3 命题逻辑推理的难点,3、弄清楚几种推理方法的区别与联系，对于命题逻辑推理而言，任何一个问题的推理，都可以采取三种推理方法中的任何一种来证明，针对不同的问题选用不同的推理方法。一般而言，对于结论是蕴涵式或析取式的，大多可以采取带CP规则的直接证明方法。,5.2.4 命题逻辑推理的应用,例 符号化下面的语句，并用演绎法证明结

14、论是否有效。或者明天下午是天晴，或者是下雨；如果明天下午是天晴，则我将去看电影；如果我去看电影，我就不看书。如果我看书，则天在下雨。,设P：明天下午天晴；Q：明天下午下雨；R：明天下午去看电影；S：明天下午看书。则上述命题可符号化为：P Q，PR，RS SQ。,例 证明,P Q，PR，RS SQ。（1）S P(附加前提)（2）RS P（3）R（1）（2）（4）PR P（5）P（3）（4）（6）P Q（7）Q（5）（6）,例,一个公安人员审查一件盗窃案，已知的事实如下：A或B盗窃了x；若A盗窃了x，则作案时间不能发生在午夜前；若B证词正确，则在午夜时屋里灯光未灭；若B证词不正确，则作案时间发生在

15、午夜前；午夜时屋里灯光灭了。B盗窃了x。,例5.2.8 证明,设 P：A盗窃了x；Q：B盗窃了x；R：作案时间发生在午夜前；S：B证词正确；T：在午夜时屋里灯光未灭。则上述命题可符号化为：PQ，PR，ST，SR，T Q,例5.2.8 证明（续）,证明1 采用直接证明方法（反证法请自行完成）（1）T（2）ST（3）S，（1），（2），I（4）SR（5）R，（3），（4），I（6）PR P（7）P，（5），（6），I（8）PQ（9）Q，（7），（8），I,证明 令P：马会飞；Q：羊吃草；R：母鸡是飞鸟；S：烤熟的鸭子还会跑。符号化上述语句为：=PQR,RS,S,G=Q。证明G。,如果马会飞或羊吃草

16、，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。,例5.2.8,例5.2.8 证明（续）,S PRS PR T,IPQR P(PQ)T,IPQ T,EQ T,I,5.3 谓词逻辑的推理理论,5.3.1 谓词演算的演绎与推理,定义5.3.1 设G1,G2,Gn,是公式，称H是G1,G2,Gn的逻辑结果(G1,G2,Gn共同蕴涵H)，当且仅当H是G1G2Gn的逻辑结果(logic conclusion)。记为G1,G2,Gn，此时称G1,G2,Gn 为有效的，否则称为无效的。G1,G2,Gn称为一组前提(Premise)，有时用集合来表示，记=G1,G2,

17、Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为 H。,定理5.3.1,定理 公式H是前提集合=G1,G2,Gn的逻辑结果当且仅当 G1G2Gn为有效公式。,一 推理定律(对比第4章PPT，第83页),教材P129 130（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),推理定律（续）,（4）I21：(x)(y)G(x,y)

18、(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,y)(x)(y)G(x,y)；I25：(x)(y)G(x,y)(y)(x)G(x,y)；I26：(y)(x)G(x,y)(x)(y)G(x,y)；,二 推理规则,1、US（全称特指规则，Universal Specify）：(x)G(x)G(y)，其中G(x)对y是自由的 推广：(x)G(x)G(c)，其中c为任意个体常量,2、ES（存在特指规则，Existential Specify）：(x)G(x)G(c)，其中c为特定个

19、体常量,推理规则（续）,3、UG（全称推广规则，Universal Generalize）：G(y)(x)G(x)，其中G(y)对x是自由的,4、EG（存在推广规则，Existential Generalize）：G(c)(x)G(x)，其中c为特定个体常量 推广：G(y)(x)G(x)，其中G(y)对x是自由的,推理规则的正确使用(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

20、）(y)G(z,y)US，（1）,使用US规则消去量词，“y”在公式中必须是自由的。,推理规则的正确使用（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)P（2）(y)G(z,y)US，（1）（3）G(z,f(z)ES，（2）,使用ES规则消去量词，若还有其它自由变元，则必须用关于自由变元的函数符号来取代常量符号.,推理规则的正确使用（3）,推导3：（1）(y)G(z,y)P（2）(y)(y)G(y,y)UG，（1）,分析：推导3是错误的。正确的推导如下：（1）

21、(y)G(z,y)P（2）(z)(y)G(z,y)UG，（1）,注意：使用UG规则来添加量词时，所使用的变元符号不能与辖域内的变元符号相同.,推理规则的正确使用（4）,推导4：（1）G(x,c)P（2）(x)G(x,x)EG，（2）,分析：推导4是错误的。正确的推导如下：（1）G(x,c)P（2）(y)G(x,y)EG，（2）,注意：使用EG规则来添加量词时，所使用的变元符号不能与辖域内的变元符号相同.,5.3.2 谓词演算的综合推理方法,（1）推导过程中可以引用命题演算中的规则P 和规则T。（2）如果结论是以条件的形式(或析取形式)给出，我们还可以使用规则CP。（3）若需消去量词，可以引用规

22、则US和规则ES。（4）当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入。,谓词演算的综合推理方法（续）,（5）证明时可采用如命题演算中的直接证明方法和间接证明方法。（6）在推导过程中，对消去量词的公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。（7）在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。,例5.3.1,解 设H(x)：x是人；M(x)：x是要死的；s：苏格拉底。则符号化为：(x)(H(x)M(x)，H(s)M(s),证明苏格拉底三段论：“所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。”,证明：

23、(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)错了！,例5.3.1,解 设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(s)M(s)US,(1)(3)H(s)P(4)M(s)T,(2),(3)，I,例5.3.2,证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x),有下面的推导（正确与否？）：(1)(x)(P(x

24、)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),(4)中的“c”未必能保证令(2)为真，推导错误！,例（),推导可修改为（正确与否？）：(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),证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x),(2)中的“c”未必能保证令(4)为真，推导错误！,例(),正确推导如下：(1)(x)P(x)P(

25、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),证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x),例,证明：1)(x)(P(x)Q(x)P 2)(P(c)Q(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),例(续1),1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P

26、(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),请看上述推论的逆推导（正确与否？）：,证明：(x)(P(x)Q(x)(x)P(x)(x)Q(x),“c”未必能保证同时令(2)和(4)为真，推导错误！,例(续2),正确推导：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(b)ES,4)6)(P(c)Q(b)T,3),4),I7)(x)(y)(P(x)Q(y)EG,6),(x)(P(x)Q(x)(x)P(x)(x)Q(x)的

27、逆推导：,例5.3.4,证明(采用反证法，CP规则的方法自己完成)：1)(x)P(x)(x)Q(x)P(附加前提)2)(x)P(x)(x)Q(x)T,1),E3)(x)P(x)T,2),I4)(x)Q(x)T,2),I5)(x)P(x)T,3),E6)P(c)ES,5),证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),例5.3.4 证明（续）,6)P(c)ES,5)7)(x)Q(x)T,4),E8)Q(c)US,7)9)P(c)Q(c)T,6),8),I10)(P(c)Q(c)T,9),E11)(x)(P(x)Q(x)P12)(P(c)Q(c)US,11)13)(P(c)Q(c)(P

28、(c)Q(c)T,10),12),证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),5.3.3 谓词逻辑推理的难点,（1）在推导过程中，如既要使用规则US又要使用规则ES消去公式中的量词，而且选用的个体是同一个符号，则必须先使用规则ES，再使用规则US。然后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所要的结论。（2）如一个变量是用规则ES消去量词，对该变量再添加量词时，则只能使用规则EG，而不能使用规则UG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。,谓词逻辑推理的难点（续）,（3）如有两个含有存在量词的公式，当用规则ES消去量

29、词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。（4）在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端。,谓词逻辑推理的难点（续）,（5）在添加量词(x)、(x)时，所选用的x不能在公式G(c)或G(y)中以任何约束出现。（6）在使用EG规则引入存在量词(x)，此x不得仅为G(c)或G(y)中的函数变元。在使用UG规则引入全称量词(x)时，此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。,5.3.4 谓词逻辑推理的应用,例 每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的

30、人不喜欢步行。,证明 设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),例5.3.5 证明（续）,证：(1)(x)(H(x)Q(x)P(2)H(c)Q(c)ES，(1)(3)H(c)T，(2)(4)Q(c)T，(2)(5)(x)(H(x)P(x)Q(x)P(6)H(c)P(c)Q(c)US，(5)(7)P(c)Q(c)T，(3)，(6)，I(8)P(c)T，(4)，(7)，I,上述语句可符号化为：(x)(H(x)R

31、(x)P(x),(x)(H(x)P(x)Q(x),(x)(H(x)Q(x)(x)(H(x)R(x),例5.3.5 证明（续）,(3)H(c)T，(2)(8)P(c)T，(4)，(7)，I(9)(x)(H(x)R(x)P(x)P(10)H(c)R(c)P(c)US，(9)(11)(H(c)R(c)T，(8)，(10)，I(12)H(c)R(c)T，(11)，E(13)R(c)T，(3)，(12)，I(14)H(c)R(c)T，(3)，(13)，I(15)(x)(H(x)R(x)EG，(14),上述语句可符号化为：(x)(H(x)R(x)P(x),(x)(H(x)P(x)Q(x),(x)(H(x)

32、Q(x)(x)(H(x)R(x),例5.3.6,证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。证明 设谓词如下：P(x)：x是哺乳动物；Q(x)：x是脊椎动物；R(x)：x是胎生动物。则有：(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),请看下面推导：,1)(x)(P(x)R(x)P2)(P(x)R(x)US,1)3)(P(x)R(x)T,2)，E4)(P(x)R(x)T,3),E5)P(x)T,4),I6)R(x)T,4),I7)(x)(P(x)Q(x)P8)P(x)Q(x)US,7)9)Q(x)T,(

33、5),(8),I10)Q(x)R(x)T,6),9),I11)(x)(Q(x)R(x)EG,10)12)(x)(Q(x)R(x)UG,10),(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),错误推导,例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),I11)(x)(Q(x)R(x)E

34、G,10),(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),正确推导,例5.3.7,证明下列论断的正确性：有些信徒相信所有的神父；任何一个信徒都不相信骗子；所以，神父都不是骗子。证明 设谓词如下：S(x)：x是信徒T(x)：x是神父P(x)：x是骗子L(x,y)：x相信y则可符号化为：(x)(S(x)(y)(T(y)L(x,y)，(x)(y)(S(x)P(y)L(x,y)(x)(T(x)P(x),例5.3.7 证明（续）,1)(x)(S(x)(y)(T(y)L(x,y)P2)S(c)(y)(T(y)L(c,y)ES,1)3)S(c)T,2),I4)(y)(T(y)L

35、(c,y)T,2),I5)T(x)L(c,x)US,4)6)(x)(y)(S(x)P(y)L(x,y)P7)(y)(S(c)P(y)L(c,y)US,6)8)(S(c)P(x)L(c,x)US,7),(x)(S(x)(y)(T(y)L(x,y)，(x)(y)(S(x)P(y)L(x,y)(x)(T(x)P(x),例5.3.7 证明（续）,3)S(c)T,2),I8)(S(c)P(x)L(c,x)US,7)9)S(c)(P(x)L(c,x)T,8),E10)P(x)L(c,x)T,3),8),E11)L(c,x)P(x)T,10),E12)T(x)P(x)T,5),11),E13)(x)(T(x

36、)P(x)US,12),(x)(S(x)(y)(T(y)L(x,y)，(x)(y)(S(x)P(y)L(x,y)(x)(T(x)P(x),例,现有一智力测验题目(水容器问题)：设有两个分别能盛7升与5升的水容器，开始时两个容器均空，允许对容器做三种操作：（1）容器倒满水，（2）将容器中的水倒光，（3）从一个容器倒水至另一容器，使一个容器倒光而另一容器倒满。最后要求能使大容器(能盛7升的容器)中有4升水，并求其操作过程。,例的解决方案,例5.3.8 证明,（1）S(0,0)P（2）(x)(y)(S(x,y)S(7,y)P（3）(y)(S(0,y)S(7,y)US,(2)（4）S(0,0)S(7,

37、0)US,(3)（5）S(7,0)T,(1),(4).I（6）(x)(y)(z)(S(x,y)S(z,5)P（7）(y)(z)(S(7,y)S(z,5)US，（6）（8）(z)(S(7,0)S(z,5)US，（7）（9）S(7,0)S(2,5)ES，（8）,例5.3.8 证明（续）,（10）S(2,5)T,(5),(9),I（11）(x)(y)(S(x,y)S(x,0)P（12）(y)(S(2,y)S(2,0)US，（11）（13）S(2,5)S(2,0)US，（12）（14）S(2,0)T,(10),(13),I（15）(x)(y)(z)(S(x,y)S(0,z)P（16）(y)(z)(S(

38、2,y)S(0,z)US，（15）（17）(z)(S(2,0)S(0,z)US，（16）,例5.3.8 证明（续）,（18）(S(2,0)S(0,2)ES，（17）（19）S(0,2)T,(14),(18),I（20）(x)(y)(S(x,y)S(7,y)P（21）(y)(S(0,y)S(7,y)US，（20）（22）(S(0,2)S(7,2)US，（21）（23）S(7,2)T,(19),(22),I（24）(x)(y)(z)(S(x,y)S(z,5)P（25）(y)(z)(S(7,y)S(z,5)US，（24）（26）(z)(S(7,2)S(z,5)US，（25）,例5.3.8 证明（续）

39、,（27）S(7,2)S(4,5)ES，（26）（28）S(4,5)T,(23),(27),I（29）(x)(y)(S(x,y)S(x,0)P（30）(y)(S(4,y)S(4,0)US，（29）（31）S(4,5)S(4,0)US，（30）（32）S(4,0)T,(30),(33),I,5.4 数学归纳法,5.4.1 数学归纳法原理,假设要证明的命题能写成形式:nn0，有P(n)其中n0是某个固定的整数，即：希望证明对所有的整数nn0都有P(n)为真,数学归纳法原理,假设 1）验证nn0，有P(n0)为真；(归纳基础)2）假设对于nk(kn0)，有P(k)为真；(归纳假设)3）证明nk1，有

40、P(k+1)为真。(归纳结论)结论 对所有的整数nn0，都有P(n)为真。,谓词表示：(n0)(P(n0)(n)(nk)P(k)P(k+1)1,强形式数学归纳法原理,假设 1）验证nn0、n0+1，有P(n0)、P(n0+1)为真；(归纳基础)2）假设对于n k(kn0)，有P(n)为真；(归纳假设)3）证明nk1，有P(k+1)为真。(归纳结论)结论 对所有的整数nn0，都有P(n)为真。,谓词表示：(n0)(P(n0)P(n0+1)(n)(nk)P(n)P(k+1)1,例,用数学归纳法证明：对所有n1，有1+2+3+n=,证明 归纳基础验证 1=显然P(1)真值为1；归纳假设假定 对于n=

41、k(k1)，有P(k)为真，即有 1+2+3+k=；,例,归纳结论证明 对于nk1，有P(k+1)为真 1+2+3+k+(k+1)=+(k+1)=由数学归纳法原理得到，P(n)对所有n1为真。,例,对每个正整数n1，能惟一地写成，其中pi是素数且满足p1p2ps。,分析 设P(n)：n；由于素数一定是大于等于2的正整数，因此，n02。,例,证明 归纳基础验证 因为2=21，3=31，所以P(2)、P(3)为真；归纳假设假定 对nk的所有正整数，都有P(n)为真，即 n,例5.4.2 证明(续),归纳结论证明 对nk1，需分两种情况讨论：（1）如果n本身就是一个素数，则 k1(k+1)1，即P(

42、k+1)为真；（2）如果n不是一个素数，则k1lm，其中2lk，2mk，此时由归纳假设有 l，m其中，p1,p2,ps是素数，且是包含l、m中全部分解因子，bi、ci0的自然数，,例5.4.2 证明(续),为此有 k1lm 由于p1,p2,ps是素数，所以k+1能分解成素数的积，又因为l和m的因子分解是惟一的，所以k1的因子分解也是惟一的，所以P(k+1)是真的。由数学归纳法原理得到，P(n)对所有n1为真。,5.4.2 数学归纳法应用,例 用数学归纳法证明下列伪码程序的计算结果时两个正整数的最大公因子。其中伪码程序为 FUNCTION GCD(X,Y)1.WHILE(XY)a.IF(XY)T

43、HEN 1.XX-Y b.ELSE 1.YY-X 2.RETURN(X)END OF FUNCTION GCD,例5.4.3 证明,归纳基础验证 因为在循环开始之前存在变量值X0X，Y0Y，因此，P(0)是命题GCD(X0,Y0)=GCD(X,Y)，显然命题为真；归纳假设假定 设P(k)是命题GCD(Xk,Yk)=GCD(X,Y)为真；,例5.4.3 证明（续）,归纳结论证明 首先考虑P(k1)的左边，即GCD(Xk1,Yk1)。在通过k1次循环后，或者Xk1Xk和Yk1YkXk；或者Xk1XkYk和Yk1Yk；则由整数的基本性质知，P(k1)GCD(Xk1,Yk1)GCD(Xk,Yk)GCD

44、(X,Y)。根据数学归纳法知：对所有n0，有P(n)为真。为此，该伪码程序输出的结果必是两个正整数的最大公因子。,铺瓦问题,例 一个直角三正方形，是一个由三个正方形组成的对象，如图1所示。如果我们从nn(n为2的幂)正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图2。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称为铺瓦问题。,铺瓦问题,铺瓦问题 证明（续）,（归纳结论证明部分）对于2k12k1的缺方板问题，我们可以将其分成四个2k2k的板，如图所示。旋转此板，使缺少的正方形在左上

45、的四分之一中。由归纳假设，此左上的2k2k缺方板可由直角三正方形铺成，把一个直角三正方形T放在中间，则另外三个四分之一都是2k2k的缺方板。由归纳假设，它们的铺瓦问题都是可以解决的。于是2k12k1的缺方板可由直角三正方形铺成。由数学归纳法知，对任何的n，nn正方形的铺瓦问题都是可以铺成的。,5.5 按定义证明方法,在离散数学中，我们大量的定义描述都是用蕴涵型“PQ”的方式来描述的。,如集合中子集的包含关系的定义描述为：集合A B(a)(aAaB),5.5.1 按定义证明方法原理,5.5.2 按定义证明方法应用,例 设A、B是两个任意集合，证明 A B P(A)P(B),证明（1）必要性“”：对任意的xP(A)，则x A，由于A B，所以x B，即有xP(B)。由CP规则知：P(A)P(B)。即 A B P(A)P(B),例 证明（续）,（2）充分性“”：对任意的xA，则xP(A)，由于P(A)P(B)，所以xP(B)，即有xB。由CP规则知：A B。即 P(A)P(B)A B。原式得证。,例5.5.2,如果A B，则ABB且ABA,证明两个集合相等，即是证明两个集合相互包含，请学生自证。,作业,1.（2）2.（1）（6）3.（3）（5）57.(8)(9),