离散数学课程组国家级课程课件.ppt

1、离 散 数 学电子科技大学计算机科学与工程学院示范性软件学院20222022年年11 11月月3030日星期三日星期三第第5 5章章 推理与证明技术推理与证明技术 数学归纳法的使用数学归纳法的使用 3CPCP规则相关证明规则相关证明4命题逻辑的推理理论命题逻辑的推理理论 1谓词逻辑的推理理论谓词逻辑的推理理论 25.1 5.1 本章学习要求本章学习要求1掌握各种不同掌握各种不同类型的规则和类型的规则和公理，特别是公理，特别是命题逻辑和谓命题逻辑和谓词逻辑的推理词逻辑的推理规则和公理规则和公理 3理解谓词逻辑理解谓词逻辑的精髓，将其的精髓，将其思想贯穿于所思想贯穿于所有的证明之中有的证明之中 2

2、熟练掌握不同熟练掌握不同证明方法的证证明方法的证明原理、不同明原理、不同的应用场景的应用场景 重点掌握重点掌握一般掌握一般掌握了解了解5.2 5.2 命题逻辑的推理理论命题逻辑的推理理论 概念概念描述问题描述问题的句子；的句子；Add Your Text判断判断对概念的肯对概念的肯定定与否定的与否定的判断判断；推理推理从一个或多从一个或多个前提推出个前提推出结论的结论的思维思维过程过程。推理的有效性和结论的真实性推理的有效性和结论的真实性有效的推理不一定产生真实的结论有效的推理不一定产生真实的结论；而而产生真实结论的推理过程未必是有效的产生真实结论的推理过程未必是有效的。有效的推理有效的推理中

3、可能包含为中可能包含为“假假”的前提的前提，而而无效的推理无效的推理却可能得到为却可能得到为“真真”的结论的结论。推理的有效性和结论的真实性推理的有效性和结论的真实性所谓所谓推理有效推理有效，指的是指的是它的结论是它前提的合乎逻辑的结果它的结论是它前提的合乎逻辑的结果。即，如果它的即，如果它的前提都为真，那么所得的结论也前提都为真，那么所得的结论也必然为真必然为真，而并不是要求前提或结论一定为真或为，而并不是要求前提或结论一定为真或为假；假；如果推理是有效的话，那么不可能它的前提都如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。为真时，而它的结论为假。5.2.1 5.2.1 推

4、理的基本概念和推理形式推理的基本概念和推理形式 定义定义5.2.15.2.1 设设G G1 1,G,G2 2,G,Gn n,是公式，称是公式，称H H是是G G1 1,G G2 2,G,Gn n的逻辑结果的逻辑结果(G(G1 1,G,G2 2,G,Gn n共同蕴涵共同蕴涵H)H)，当且仅当当且仅当H H 是是G G1 1GG2 2GGn n的逻辑结果的逻辑结果(logic(logic conclusion)conclusion)。记为。记为G G1 1,G,G2 2,G,Gn n ，此时称，此时称G G1 1,G G2 2,G,Gn n 为为有效的有效的(efficacious)(effica

5、cious)，否则称为，否则称为无效的无效的（inefficaciousinefficacious）。）。G G1 1,G,G2 2,G,Gn n称为一称为一组前提组前提(Premise)(Premise)，有时用集合，有时用集合来表示，记来表示，记=GG1 1,G,G2 2,G,Gn n。H H称为称为结论结论(conclusion)(conclusion)。又称。又称H H是前提集合的逻辑结果。记为是前提集合的逻辑结果。记为 H H。判定定理判定定理定理定理5.2.15.2.1 公式公式H H是前提集合是前提集合=G=G1 1,G,G2 2,G,Gn n 的逻辑结果当且仅当的逻辑结果当且仅

6、当G G1 1GG2 2GGn n为永真公为永真公式。式。证明：证明：“”若若G G1 1,G,G2 2,G,Gn n ，但，但G G1 1GG2 2GGn nHH不是永真式。于是，必存在不是永真式。于是，必存在G G1 1,G G2 2,G,Gn n，H H的一个解释的一个解释I I，使得，使得G G1 1GG2 2GGn n为真，为真，而而H H为假，因此对于该解释为假，因此对于该解释I I，有，有G G1 1,G,G2 2,G,Gn n都为真，都为真，而而H H为假，这就与推理形式为假，这就与推理形式G G1 1,G,G2 2,G,Gn n 是有效是有效的相矛盾，故：的相矛盾，故：G G

7、1 1GG2 2GGn nHH是永真公式。是永真公式。判定定理（续）判定定理（续）“”若若G G1 1GG2 2GGn nHH是永真式，但是永真式，但G G1 1,G G2 2,G,Gn n 不是有效的推理形式，故存在不是有效的推理形式，故存在G G1 1,G G2 2,G,Gn n,H,H的一个解释的一个解释I I，使得，使得G G1 1,G,G2 2,G,Gn n都都为真，而为真，而H H为假，故为假，故G G1 1GG2 2GGn n为真，而为真，而H H为假，为假，即是说即是说G G1 1GG2 2GGn nHH为假，这就与为假，这就与G G1 1GG2 2GGn nHH是永真式相矛盾

8、，所以是永真式相矛盾，所以G G1 1,G G2 2,G,Gn n 是有效的推理形式。是有效的推理形式。“”与与“”“”的不同的不同1.1.“”“”仅是一般的仅是一般的蕴涵联结词蕴涵联结词，GHGH的结果仍是的结果仍是一个公式，而一个公式，而“”却描述了两个公式却描述了两个公式G G，H H之间的之间的一种逻辑蕴涵关系，一种逻辑蕴涵关系，G G H H的的“结果结果”，是非命题，是非命题公式；公式；2.2.用计算机来判断用计算机来判断G G H H是办不到的。然而计算是办不到的。然而计算机却可机却可“计算计算”公式公式GHGH是否为永真公式。是否为永真公式。1 1、真值表技术、真值表技术 设设

9、P P1 1,P,P2 2,P,Pn n是出现在前提是出现在前提G G1 1,G,G2 2,G,Gn n和结和结论论H H中的一切命题变元，如果将中的一切命题变元，如果将P P1 1,P,P2 2,P,Pn n中所有中所有可能的解释及可能的解释及G G1 1,G,G2 2,G,Gn n，H H的对应真值结果都列的对应真值结果都列在一个表中，在一个表中，根据根据“”的定义，的定义，则有判断方法则有判断方法如下：如下：1.1.对所有对所有G G1 1,G,G2 2,G,Gn n都具有真值都具有真值T T的行的行(表示前提为真的表示前提为真的行行)，如果在每一个这样的行中，如果在每一个这样的行中，H

10、 H也具有真值也具有真值T T，则则H H是是G G1 1,G,G2 2,G,Gn n的逻辑结果。的逻辑结果。2.2.对所有对所有H H具有真值为具有真值为F F的行的行(表示结论为假的行表示结论为假的行),),如果在如果在每一个这样的行中，每一个这样的行中，G G1 1,G,G2 2,G,Gn n中至少有一个公式的中至少有一个公式的真值为真值为F(F(前提也为假前提也为假)，则，则H H是是G G1 1,G,G2 2,G,Gn n的逻辑结果的逻辑结果.例例5.2.1 5.2.1 判断下列判断下列H H是否是前提是否是前提G G1 1,G,G2 2的逻辑结果的逻辑结果(1)(1)H H：Q Q

11、；G G1 1：P P；G G2 2：PQPQ；(2)(2)H H：P P；G G1 1：PQPQ；G G2 2：Q Q；(3)(3)H H：Q Q；G G1 1：P P；G G2 2：PQPQ。解解P P Q QG G1 1G G2 2H H0 0 0 00 01 10 00 0 1 10 01 11 11 1 0 01 10 00 01 1 1 11 11 11 1(1)P PQ QG G1 1G G2 2H H0 00 01 11 11 10 01 11 10 01 11 10 00 01 10 01 11 11 10 00 0(2)P PQ QG G1 1G G2 2H H0 00 0

12、1 11 10 00 01 11 11 11 11 10 00 00 00 01 11 10 01 11 1(3)5.2.2 5.2.2 判断有效结论的常用方法判断有效结论的常用方法 =G G1 1,G,G2 2,G,Gn n H HG G1 1GG2 2GGn n为永真公式为永真公式真值表技术、演绎法和真值表技术、演绎法和间接证明方法间接证明方法设设G，H，S是任何的公式，则：是任何的公式，则：基本等价公式基本等价公式1)1)1 1：G(HS)G(HS)(GH)S(GH)S(结合律结合律)2 2:G(HS)G(HS)(GH)S(GH)S2)2)3 3：GHGHHG HG (交换律交换律)4

13、4：GHGHHGHG3)3)5 5：GGGGG G (幂等律幂等律)6 6：GGGGG G4)4)7 7：G(GH)G(GH)G G (吸收律吸收律)8 8：G(GH)G(GH)G G5)9：G(HS)(GH)(GS)(分配律）分配律）10：G(HS)(GH)(GS)6)11：GG(同一律同一律)12：GG 7)13：G(零律零律)14：G8)15：GG(排中律排中律)9)16：GG(矛盾律矛盾律)基本等价公式（续）基本等价公式（续）基本等价公式（续）基本等价公式（续）10)17：(G)G(双重否定律双重否定律)11)18：(GH)GH(De MoRGan定律定律)19：(GH)GH12)20

14、:(GH)(GH)(HG)(等价等价式式)13)21：(GH)(GH)(蕴涵蕴涵式式)14)14)E E2222：G G(假言易位假言易位)15)15)E E2323：G G(等价否定等式等价否定等式)16)16)E E2424：(G)(G)G(归谬论归谬论)5.2.2 5.2.2 判断有效结论的常用方法判断有效结论的常用方法 =G G1 1,G,G2 2,G,Gn n H HG G1 1GG2 2GGn n为永真公式为永真公式真值表技术、演绎法和真值表技术、演绎法和间接证明方法间接证明方法真值表技术真值表技术G G1 1G G2 2G G3 3G Gn nH H0 0 1 10 01 10

15、00 0 1 10 01 11 11 1 0 01 10 00 01 1 1 11 11 11 1真值表技术真值表技术2 2 推理定律推理定律设设G G，H H，I I，J J是任意的命题公式，则有：是任意的命题公式，则有：1)1)I I1 1：GHGHG G(简化规则简化规则)I I2 2：GHGHH H2)2)I I3 3：G GGHGH(添加规则添加规则)I I4 4：H HGHGH3)3)I I5 5：G GGHGHI I6 6：H HGHGH4)4)I I7 7：(GH)(GH)G GI I8 8：(GH)(GH)HH5)5)I I9 9：G,HG,HGHGH2 2 推理定律推理定律

16、(续续)6 6）I I1010：G,GHG,GHH H (选言三段论选言三段论)I I1111：G,G HG,G HH H7 7）I I1212：G,GHG,GHH H(分离规则分离规则)8 8）I I1313：H,GHH,GHGG(否定后件式否定后件式)9 9）I I1414：GH,HIGH,HIGIGI(假言三段论假言三段论)1010）I I1515：GH,GI,HGH,GI,HI II I (二难推论二难推论)例子例子1)1)、前提：、前提：1.1.如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。PQPQ2 2明天的确天晴。明天的确天晴。P P结论：我们外出旅游。结论：我

17、们外出旅游。Q Q可描述为：可描述为：PQPQ，P PQ Q(分离规则分离规则)2)2)、前提：、前提：1.1.如果一个人是单身汉，则他不幸福。如果一个人是单身汉，则他不幸福。PQPQ2.2.如果一个人不幸福，则他死得早。如果一个人不幸福，则他死得早。QRQR结论：单身汉死得早。结论：单身汉死得早。PRPR可描述为：可描述为：PQPQ，QRQRPRPR(假言三段论假言三段论)例子例子(续续1)1)3)3)、某女子在某日晚归家途中被杀害，据多方调查确、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜

18、班，没有外出，根据上述案情可得某在工厂值夜班，没有外出，根据上述案情可得前提：前提：1.1.凶手为王某或陈某凶手为王某或陈某。PQPQ 2.2.如果王某是凶手，则他在作案当晚必外出如果王某是凶手，则他在作案当晚必外出PRPR 3.3.王某案发之晚并未外出。王某案发之晚并未外出。RR结论：陈某是凶手。结论：陈某是凶手。Q Q则则可描述为可描述为：PR,RPR,RPP(否定后件式否定后件式)PQPQ，PPQ Q(选言三段论选言三段论)例子例子(续续2)2)4)4)、前提：、前提：1.1.如果某同学为省二级以上运动员，则他如果某同学为省二级以上运动员，则他将被大学录取。将被大学录取。PRPR2.2.

19、如果某同学高考总分在如果某同学高考总分在560560分以上，则分以上，则将被大学录取。将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省分以上或者是省二级运动员。二级运动员。PQPQ 结论：该同学被大学录取。结论：该同学被大学录取。R R 则上述例子可描述为：则上述例子可描述为：PQPQ，PRPR，QRQRR R(二难推论二难推论)3 3 演绎法演绎法 演绎法演绎法是从前提是从前提(假设假设)出发，依据公认的推理出发，依据公认的推理规则和推理定律，推导出一个结论来。规则和推理定律，推导出一个结论来。YN触发规则触发规则新事实新事实事实事实=结论？结论？事实

20、库事实库规则匹配规则匹配公理库公理库将事实加入到事实库中将事实加入到事实库中结束结束引入事实引入事实引入推理规则引入推理规则在数理逻辑中，主要的推理规则有：在数理逻辑中，主要的推理规则有：P P规则（称为前提引用规则）：规则（称为前提引用规则）：在推导的过程中，在推导的过程中，可可随时引入前提集合中的任意一个前提随时引入前提集合中的任意一个前提；规则（逻辑结果引用规则）：规则（逻辑结果引用规则）：在推导的过程在推导的过程中，可以中，可以随时引入公式随时引入公式S S，该公式，该公式S S是由其前的一个是由其前的一个或多个公式推导出来的逻辑结果或多个公式推导出来的逻辑结果。规则（附加前提规则）：

21、规则（附加前提规则）：如果能从给定的如果能从给定的前提集合前提集合与公式与公式P P推导出推导出S S，则能从此，则能从此前提集合前提集合推导出推导出PSPS。演绎的定义演绎的定义定义定义5.2.25.2.2 从前提集合从前提集合推出结论推出结论H H的一个演绎是构造的一个演绎是构造命题公式的一个有限序列：命题公式的一个有限序列：H H1 1，H H2 2，H Hn n 其中，其中，H Hi i或者是或者是中的某个前提，或者是前中的某个前提，或者是前面的某些面的某些H Hj j（jijx。推导推导1：（1）(x)(y)G(x,y)P （2）(y)G(y,y)US，（，（1）分析分析：推导：推导

22、1是错误的。是错误的。正确的推导如下：正确的推导如下：（1）(x)(y)G(x,y)P （2）(y)G(z,y)US，（，（1）注意：注意：使用使用USUS规则规则来来消去消去量词时，所选用取代量词时，所选用取代x x的变的变元元y y在公式中必须是在公式中必须是自由的自由的。推理规则的正确使用（推理规则的正确使用（2 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）

23、G(z,f(z)ES，（，（2）注意：注意：使用使用ESES规则规则来来消去消去量词时，量词时，若还有其它若还有其它自自由变由变元元时，时，则必须用关于自由变元的则必须用关于自由变元的函数符号函数符号来取来取代常量符号代常量符号.推理规则的正确使用（推理规则的正确使用（3 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）注意：注意：使用使用UGUG规则规则来来添加添加量词时，量词时，所使用的变元符所使用的变

24、元符号不能与辖域内的变元符号相同号不能与辖域内的变元符号相同.推理规则的正确使用（推理规则的正确使用（4 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）注意：注意：使用使用EGEG规则规则来来添加添加量词时，量词时，所使用的变元符所使用的变元符号不能与辖域内的变元符号相同号不能与辖域内的变元符号相同.5.3.2 5.3.2 谓词演算的综合推理方法谓词演算的综合推理方法（1）推导过程中可以引用命题演算中的）推导过程中可以引用命题演

25、算中的规则规则P 和和规则规则T。（2）如果）如果结论是以条件的形式结论是以条件的形式(或析取形式或析取形式)给出，给出，我们还可以我们还可以使用规则使用规则CP。（3）若需）若需消去量词消去量词，可以，可以引用规则引用规则US和规则和规则ES。（4）当所要求的结论可能被）当所要求的结论可能被定量定量时，此时可时，此时可引用引用规则规则UG和规则和规则EG将其量词加入将其量词加入。谓词演算的综合推理方法（续）谓词演算的综合推理方法（续）（5）证明时可采用如）证明时可采用如命题演算命题演算中的中的直接证明方法直接证明方法和间接证明方法和间接证明方法。（6）在推导过程中，）在推导过程中，对消去量词

26、的公式或公式中对消去量词的公式或公式中不含量词的子公式不含量词的子公式，完全可以，完全可以引用命题演算中的基引用命题演算中的基本等价公式和基本蕴涵公式本等价公式和基本蕴涵公式。（7）在推导过程中，对）在推导过程中，对含有量词的公式含有量词的公式可以可以引用引用谓词中的基本等价公式和基本蕴涵公式谓词中的基本等价公式和基本蕴涵公式。例例5.3.1 5.3.1 解解 设设H(x)H(x)：x x是人；是人；M(x)M(x)：x x是要死的；是要死的；s s：苏格：苏格拉底。则符号化为：拉底。则符号化为：(x)(H(x)x)(H(x)M(x)M(x)，H(s)H(s)M(s)M(s)证明证明苏格拉底三

27、段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”证明：证明：(1)(1)(x)(H(x)x)(H(x)M(x)M(x)P P(2)H(x)(2)H(x)M(x)M(x)US,(1)US,(1)(3)H(s)(3)H(s)P P(4)M(s)(4)M(s)T,(2),(3)T,(2),(3)，I I证明：证明：(1)(1)(x)(H(x)x)(H(x)M(x)M(x)P P(2)(2)H(s)H(s)M(s)M(s)US,(1)US,(1)(3)(3)H(s)H(s)P P(4)(4)M(s)M(s)T,(2

28、),(3)T,(2),(3)，I I(4)(4)错了！错了！正确的为正确的为例例5.3.2 5.3.2 证明：证明：(x)(P(x)x)(P(x)Q(x)Q(x)，(x)x)P(x)P(x)(x)x)Q(x)Q(x)有下面的推导有下面的推导：(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P (2)(2)P(x)P(x)Q(x)Q(x)US,(1)US,(1)(3)(3)(x)x)P(x)P(x)P P (4)(4)P(c)P(c)ES,(3)ES,(3)(5)(5)Q(c)Q(c)T,(2),(4),IT,(2),(4),I (6)(6)(x)x)Q(x)Q(x)EG,(5)E

29、G,(5)错错!例例5.3.25.3.2（)推导可修改为推导可修改为：(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(2)(P(c)(P(c)Q(c)Q(c)US,(1)US,(1)(3)(3)(x)x)P(x)P(x)P P(4)(4)P(c)P(c)ES,(3)ES,(3)(5)(5)Q(c)Q(c)T,(2),(4),IT,(2),(4),I(6)(6)(x)x)Q(x)Q(x)EG,(5)EG,(5)还错还错!c=c=5 5c=3c=3例例5.3.25.3.2()正确地推导正确地推导如下：如下：(1)(1)(x)x)P(x)P(x)P P(2)(2)P(c)P(

30、c)ESES，(1)(1)(3)(3)(x)(P(x)x)(P(x)Q(x)Q(x)P P(4)(4)(P(c)(P(c)Q(c)Q(c)US,(3)US,(3)(5)(5)Q(c)Q(c)T,(2),(4),IT,(2),(4),I(6)(6)(x)x)Q(x)Q(x)EG,(5)EG,(5)例例5.3.3 5.3.3 证明证明：1)(1)(x x)(P(x)(P(x)Q(x)Q(x)P P 2)(P(c)2)(P(c)Q(c)Q(c)ES,1)ES,1)3)P(c)3)P(c)T,2),IT,2),I 4)Q(c)4)Q(c)T,2),IT,2),I 5)5)(x x)P(x)P(x)EG

31、,3)EG,3)6)6)(x x)Q(x)Q(x)EG,4)EG,4)7)7)(x x)P(x)P(x)(x x)Q(x)Q(x)T,5),6),IT,5),6),I证明：证明：(x x)(P(x)(P(x)Q(x)Q(x)(x)x)P(x)P(x)(x)x)Q(x)Q(x)例例5.3.35.3.3(续续1)1)1)1)(x x)P(x)P(x)(x x)Q(x)Q(x)P P2)2)(x x)P(x)P(x)T,1),IT,1),I3)3)P(c)P(c)ES,2)ES,2)4)4)(x x)Q(x)Q(x)T,1),IT,1),I5)5)Q(c)Q(c)ES,4)ES,4)6)6)(P(c

32、)(P(c)Q(c)Q(c)T,3),4),IT,3),4),I7)7)(x x)(P(x)(P(x)Q(x)Q(x)EG,6)EG,6)请看上述推论的逆推导请看上述推论的逆推导：错错!P(x):xP(x):x喜欢踢足喜欢踢足球；球；Q(x)Q(x)：x x喜欢喜欢跳舞跳舞例例5.3.35.3.3(续续2)2)正确地推导正确地推导：1)(1)(x x)P(x)P(x)(x x)Q(x)Q(x)P P2)2)(x x)P(x)P(x)T,1),IT,1),I3)P(c)3)P(c)ES,2)ES,2)4)4)(x x)Q(x)Q(x)T,1),IT,1),I5)Q(b)5)Q(b)ES,4)ES

33、,4)6)(P(c)6)(P(c)Q(b)Q(b)T,3),4),IT,3),4),I7)7)(x x)()(y y)(P(x)(P(x)Q(y)Q(y)EG,6)EG,6)例例5.3.4 5.3.4 证明证明(采用反证法，采用反证法，CPCP规则的方法由学生完成规则的方法由学生完成)：1 1)(x)P(x)x)P(x)(x)x)Q(x)Q(x)P(P(附加前提附加前提)2 2)(x)P(x)x)P(x)(x)x)Q(x)Q(x)T,1),ET,1),E3)3)(x)P(x)x)P(x)T,2),IT,2),I4)4)(x)x)Q(x)Q(x)T,2),IT,2),I5)5)(x)x)P(x)

34、P(x)T,3),ET,3),E6)6)P(c)P(c)ES,5)ES,5)证明证明(x)(P(x)x)(P(x)Q(x)Q(x)(x)P(x)x)P(x)(x)x)Q(x)Q(x)例例5.3.4 5.3.4 证明（续）证明（续）7)(7)(x)x)Q(x)Q(x)T,4),ET,4),E8)8)Q(c)Q(c)US,7)US,7)9)9)P(c)P(c)Q(c)Q(c)T,6),8),I T,6),8),I10)10)(P(c)(P(c)Q(c)Q(c)T,9),E T,9),E11)(11)(x)(P(x)x)(P(x)Q(x)Q(x)P P12)(P(c)12)(P(c)Q(c)Q(c)

35、US,11)US,11)13)13)(P(c)(P(c)Q(c)Q(c)(P(c)(P(c)Q(c)Q(c)T,10),12)T,10),12)5.3.3 5.3.3 谓词逻辑推理的难点谓词逻辑推理的难点（1 1）在推导过程中，如在推导过程中，如既要使用规则既要使用规则USUS又要使用规又要使用规则则ESES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，而且选用的个体是同一个符号，则必须符号，则必须先先使用规则先先使用规则ESES，再使用规则，再使用规则USUS。然。然后再使用命题演算中的推理规则，最后使用规则后再使用命题演算中的推理规则，最后使用规则UGUG或规则或规则EGEG引

36、入量词，得到所要的结论。引入量词，得到所要的结论。（2 2）如一个变量是用如一个变量是用规则规则ESES消去量词消去量词，对该变量在，对该变量在添加量词时，则添加量词时，则只能使用规则只能使用规则EGEG，而不能使用规则，而不能使用规则UGUG；如使用；如使用规则规则USUS消去量词消去量词，对该变量在添加量词，对该变量在添加量词时，则时，则可使用规则可使用规则EGEG和规则和规则UGUG。谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（3 3）如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消消去量词去量词时，时，不能选用同样的一个常量符号不能选用同样的一个

37、常量符号来取代两来取代两个公式中的变元，而应用不同的常量符号来取代它个公式中的变元，而应用不同的常量符号来取代它们。们。（4）在用规则在用规则US和规则和规则ES消去量词消去量词时，此量词必时，此量词必须位于须位于整个公式的最前端整个公式的最前端。谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（5 5）在在添加量词添加量词(x)x)、(x)x)时，所选用的时，所选用的x x不能不能在公式在公式G(c)G(c)或或G(y)G(y)中中以任何约束出现以任何约束出现。（6 6）在使用在使用EGEG规则规则引入存在量词引入存在量词(x)x)，此此x x不得不得仅为仅为G(c)G(c)或或G(y)G(

38、y)中的函数变元中的函数变元。在使用。在使用UGUG规则规则引入引入全称量词全称量词(x)x)时，时，此此x x不得为不得为G(y)G(y)中的函数变元中的函数变元(因该函数变元不得作为自由变元因该函数变元不得作为自由变元)。5.3.4 5.3.4 谓词逻辑推理的应用谓词逻辑推理的应用例例5.3.5 每个喜欢步行的人都不喜欢坐汽车；每个每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。欢骑自行车。因而有的人不喜欢步行。证明证明 设设H(x)H(x)：x x是人；是人；P(x)P(x)：x

39、 x喜欢坐汽车；喜欢坐汽车；Q(x)Q(x)：x x喜欢骑自行车；喜欢骑自行车；R(x)R(x)：x x喜欢步行喜欢步行。则上述语句可符号化为：则上述语句可符号化为：(x)(H(x)R(x)x)(H(x)R(x)P(x)P(x)，(x)(H(x)P(x)Q(x)x)(H(x)P(x)Q(x)，(x)(H(x)x)(H(x)Q(x)Q(x)(x)(H(x)x)(H(x)R(x)R(x)例例5.3.5 5.3.5 证明（续）证明（续）(1)(1)(x)(H(x)x)(H(x)Q(x)PQ(x)P(2)H(c)(2)H(c)Q(c)ESQ(c)ES，(1)(1)(3)H(c)T(3)H(c)T，(2

40、)(2)(4)(4)Q(c)T Q(c)T，(2)(2)(5)(5)(x)(H(x)P(x)Q(x)Px)(H(x)P(x)Q(x)P (6)H(c)P(c)Q(c)US(6)H(c)P(c)Q(c)US，(5)(5)(7)P(c)Q(c)T(7)P(c)Q(c)T，(3)(3)，(6)(6)，I I (8)P(c)T(8)P(c)T，(4)(4)，(7)(7)，I I例例5.3.5 5.3.5 证明（续）证明（续）(9)(9)(x)(H(x)R(x)x)(H(x)R(x)P(x)P P(x)P(10)H(c)R(c)(10)H(c)R(c)P(c)US P(c)US，(9)(9)(11)(1

41、1)(H(c)R(c)T(H(c)R(c)T，(8)(8)，(10)(10)，I I(12)(12)H(c)H(c)R(c)TR(c)T，(11)(11)，E E(13)(13)R(c)TR(c)T，(3)(3)，(12)(12)，I I(14)H(c)(14)H(c)R(c)TR(c)T，(3)(3)，(13)(13)，I I(15)(15)(x)(H(x)x)(H(x)R(x)EGR(x)EG，(14)(14)例例5.3.6 5.3.6 证明下述论断的正确性：证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些

42、脊椎动物不是胎生的。物都是胎生动物；故有些脊椎动物不是胎生的。证明证明 设设谓词如下：谓词如下：P(x)P(x)：x x是哺乳动物；是哺乳动物；Q(x)Q(x)：x x是脊椎动物；是脊椎动物；R(x)R(x)：x x是胎生动物。是胎生动物。则有则有：(x)(P(x)x)(P(x)Q(x),Q(x),(x)(P(x)x)(P(x)R(x)R(x)(x)x)(Q(x)(Q(x)R(x)R(x)请看下面推导：请看下面推导：1 1)(x)(P(x)x)(P(x)R(x)R(x)P P2)2)(P(x)(P(x)R(x)R(x)US,1)US,1)3)3)(P(x)P(x)R(x)T,2)R(x)T,2

43、)，E E4)(P(x)4)(P(x)R(x)R(x)T,3),ET,3),E5)P(x)5)P(x)T,4),IT,4),I6)6)R(x)R(x)T,4),IT,4),I7)(7)(x)(P(x)x)(P(x)Q(x)PQ(x)P8)P(x)8)P(x)Q(x)Q(x)US,7)US,7)9)Q(x)9)Q(x)T,(5),(8),IT,(5),(8),I10)Q(x)10)Q(x)R(x)R(x)T,6),9),IT,6),9),I11)11)(x)x)(Q(x)(Q(x)R(x)R(x)EG,10)EG,10)12)(12)(x)(Q(x)x)(Q(x)R(x)R(x)UG,10)UG

44、,10)错错!(x)x)没有位于整没有位于整个公式的最前端！个公式的最前端！例例5.3.6 5.3.6 证明（续）证明（续）1 1)(x)(P(x)x)(P(x)R(x)R(x)P P2)2)(x)x)(P(x)P(x)R(x)R(x)T,1),ET,1),E3)3)(P(c)P(c)R(c)R(c)ES,2)ES,2)4)(P(c)4)(P(c)R(c)R(c)T,3),ET,3),E5)P(c)5)P(c)T,4),IT,4),I6)6)R(c)R(c)T,4),IT,4),I7)(7)(x)(P(x)x)(P(x)Q(x)Q(x)P P8)P(c)8)P(c)Q(c)Q(c)US,7)U

45、S,7)9)Q(c)9)Q(c)T,5),8),IT,5),8),I10)Q(c)10)Q(c)R(c)R(c)T,6),9),IT,6),9),I11)11)(x)x)(Q(x)(Q(x)R(x)R(x)EG,10)EG,10)例例5.3.7 5.3.7 证明下列论断的正确性：证明下列论断的正确性：有些学生相信所有的教师；任何一个学生都不相信骗有些学生相信所有的教师；任何一个学生都不相信骗子子；所以，教师都不是骗子。所以，教师都不是骗子。证明证明 设谓词如下：设谓词如下：S(x)S(x)：x x是学生是学生T(x)T(x)：x x是教师是教师P(x)P(x)：x x是骗子是骗子L(x,y)L

46、(x,y)：x x相信相信y y则可符号化为：则可符号化为：(x)x)(S(x)(S(x)(y)(T(y)y)(T(y)L(x,y)L(x,y)，(x)x)(y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y)(x)(T(x)x)(T(x)P(x)P(x)例例5.3.7 5.3.7 证明（续）证明（续）1)(1)(x)x)(S(x)(S(x)(y)(T(y)y)(T(y)L(x,y)PL(x,y)P2)S(c)2)S(c)(y)(T(y)y)(T(y)L(c,y)ES,1)L(c,y)ES,1)3)S(c)3)S(c)T,2),I T,2),I4)(4)(y)(T(y)y)(T

47、(y)L(c,y)L(c,y)T,2),I T,2),I5)T(x)5)T(x)L(c,x)L(c,x)US,4)US,4)6)(6)(x)x)(y)(S(x)y)(S(x)P(y)P(y)L(x,y)PL(x,y)P7)(7)(y)(S(c)y)(S(c)P(y)P(y)L(c,y)US,6)L(c,y)US,6)8 8)(S(c)S(c)P(x)P(x)L(c,x)US,7)L(c,x)US,7)例例5.3.7 5.3.7 证明（续）证明（续）9)S(c)9)S(c)(P(x)P(x)L(c,x)T,8),EL(c,x)T,8),E10)P(x)10)P(x)L(c,x)L(c,x)T,3

48、),8),E T,3),8),E11)L(c,x)11)L(c,x)P(x)P(x)T,10),E T,10),E12)T(12)T(x)x)P(x)P(x)T,5),11),ET,5),11),E13)(13)(x)(x)(T(T(x)x)P(x)US,12)P(x)US,12)5.4 5.4 数学归纳法数学归纳法 5.4.1 数学归纳法原理数学归纳法原理假设要证明的命题能写成形式假设要证明的命题能写成形式:nn0，有，有P(n)其中其中n0是某个固定的整数，是某个固定的整数，即：希望证明对所有的整数即：希望证明对所有的整数nn0都有都有P(n)为真为真 数学归纳法原理数学归纳法原理假设假设

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

50、设假定 对于对于n=k(k1)，有，有P(k)为真，为真，即有即有 1+2+3+k=；2111)(21)k(k 例例5.4.15.4.1归纳结论证明归纳结论证明 对于对于nk1，有，有P(k+1)为真为真 1+2+3+k+(k+1)=+(k+1)=由数学归纳法原理得到，由数学归纳法原理得到，P(n)对所有对所有n1为真。为真。21)k(k 2111221121)(k(k)(k(k)k)(k5.5 5.5 按定义证明方法按定义证明方法 在离散数学中，我们大量的定义描述都是用在离散数学中，我们大量的定义描述都是用蕴涵型蕴涵型“PQ”的方式来描述的。的方式来描述的。如集合中子集的包含关系的定义描述为