第五章推理与证明技术

1、离离 散散 数数 学学20222022年年6 6月月1616日星期四日星期四22022-6-162022-6-16第第5 5章章 推理与证明技术推理与证明技术 命题逻辑的推理理论命题逻辑的推理理论 1谓词逻辑的推理理论谓词逻辑的推理理论 232022-6-162022-6-165.1 5.1 本章学习要求本章学习要求1掌握各种不同掌握各种不同类型的规则和类型的规则和公理，特别是公理，特别是命题逻辑和谓命题逻辑和谓词逻辑的推理词逻辑的推理规则和公理规则和公理 3理解谓词逻辑理解谓词逻辑的精髓，将其的精髓，将其思想贯穿于所思想贯穿于所有的证明之中有的证明之中 2熟练掌握不同熟练掌握不同证明方法的证

2、证明方法的证明原理、不同明原理、不同的应用场景的应用场景 重点掌握重点掌握一般掌握一般掌握了解了解42022-6-162022-6-165.2 5.2 命题逻辑的推理理论命题逻辑的推理理论 概念概念描述问题描述问题的句子；的句子；Add Your Text判判断断对概念的肯对概念的肯定与否定的定与否定的判断；判断；推理推理从一个或多从一个或多个前提推出个前提推出结论的思维结论的思维过程。过程。命题演算的一个主要任务在于提供一种正确的思命题演算的一个主要任务在于提供一种正确的思维规律，即维规律，即推理规则推理规则，应用此规则从一些前提中推导，应用此规则从一些前提中推导出一个结论来，这种推导过程称

3、为出一个结论来，这种推导过程称为演绎演绎或或形式证明形式证明。52022-6-162022-6-16推理的有效性和结论的真实性推理的有效性和结论的真实性有效的推理不一定产生真实的结论有效的推理不一定产生真实的结论；而而产生真实结论的推理过程未必是有效的产生真实结论的推理过程未必是有效的。有效的推理有效的推理中可能包含为中可能包含为“假假”的前提的前提，而而无效的推理无效的推理却可能得到为却可能得到为“真真”的结论的结论 。62022-6-162022-6-16推理的有效性和结论的真实性推理的有效性和结论的真实性所谓所谓推理有效推理有效， 指的是指的是它的结论是它前提的合乎逻辑的结果它的结论是它

4、前提的合乎逻辑的结果。 即，如果它的即，如果它的前提都为真，那么所得的结论也前提都为真，那么所得的结论也必然为真必然为真，而并不是要求前提或结论一定为真或为，而并不是要求前提或结论一定为真或为假；假； 如果推理是有效的话，那么不可能它的前提都如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。为真时，而它的结论为假。72022-6-162022-6-165.2.1 5.2.1 推理的基本概念和推理形式推理的基本概念和推理形式 定义定义5.2.15.2.1 设设G G1 1, G, G2 2, , ,G,Gn n, ,是公式，称是公式，称H H是是G G1 1, , G G2 2,

5、, ,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)(efficacious)，否则称为，否则称为无效的无效的（inefficaciousinefficacious）。）。G G1 1, G, G2 2

6、, , ,G,Gn n称为一称为一组前提组前提(Premise)(Premise)，有时用集合，有时用集合来表示，记来表示，记 = = GG1 1, G, G2 2, , ,G,Gn n 。H H称为称为结论结论(conclusion)(conclusion)。又称。又称H H是前提集合的逻辑结果。记为是前提集合的逻辑结果。记为 H H。 82022-6-162022-6-16判定定理判定定理定理定理5.2.15.2.1 公式公式H H是前提集合是前提集合=G=G1 1, G, G2 2, , , G, Gn n 的逻辑结果当且仅当的逻辑结果当且仅当G G1 1GG2 2GGn n为永真公为永

7、真公式。式。 证明：证明：“”若若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 是有效是有效的相矛盾，故：的相矛盾，故：

8、G G1 1GG2 2GGn nHH是永真公式。是永真公式。92022-6-162022-6-16判定定理（续）判定定理（续） “”若若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

9、2GGn n H H为假，这就与为假，这就与G G1 1GG2 2GGn nHH是永真式相矛盾，所以是永真式相矛盾，所以G G1 1, , G G2 2, , ,G,Gn n 是有效的推理形式。是有效的推理形式。 102022-6-162022-6-16“”与与“”的不同的不同1.1.“”“”仅是一般的仅是一般的蕴涵联结词蕴涵联结词，GHGH的结果仍是的结果仍是一个公式，而一个公式，而“”却描述了两个公式却描述了两个公式G G，H H之间的之间的一种逻辑蕴涵一种逻辑蕴涵关系关系，G G H H的的“结果结果”，是非命题，是非命题公式；公式；2.2. 用计算机来判断用计算机来判断G G H H是

10、办不到的。然而计算是办不到的。然而计算机却可机却可“计算计算”公式公式GHGH是否为永真公式。是否为永真公式。 112022-6-162022-6-165.2.2 5.2.2 判断有效结论的常用方法判断有效结论的常用方法 =G G1 1, G, G2 2, , ,G,Gn n H HG G1 1GG2 2GGn n为永真公式为永真公式真值表技术、演绎法和真值表技术、演绎法和间接证明方法间接证明方法122022-6-162022-6-161 1、真值表技术、真值表技术 设设P P1 1,P,P2 2,P,Pn n是出现在前提是出现在前提G G1 1,G,G2 2,G,Gn n和结和结论论H H中

11、的一切命题变元，如果将中的一切命题变元，如果将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 H也具有真值也具有真值T T，则则H H是是G G1 1,G,G2 2, ,G,Gn n的逻辑结果。的逻辑结

12、果。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的逻辑结果的逻辑结果. .132022-6-162022-6-16例例5.2.1 5.2.1 判断下列判断下列H H是否是前提是否是前提G G1 1,G,G2 2的逻辑结果的逻辑结果(1)(1)H H：Q Q；G G1 1：P P；G G2 2：PQP

13、Q；(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 01 11 10 00 01 11 11 1

14、1 11 10 00 00 00 01 11 10 01 11 1(3)142022-6-162022-6-162 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,HGHGH15

15、2022-6-162022-6-162 2 推理定律推理定律( (续续) )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,HIGH,GI,HII I ( (二难推论二难推论) )162022-6-162022-6-16例子例子1)1)、前提：、前提：

16、1.1.如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。PQPQ2 2明天的确天晴。明天的确天晴。P P结论：我们外出旅游。结论：我们外出旅游。Q Q可描述为：可描述为：PQPQ，P PQ Q( (分离规则分离规则) )2)2)、前提：、前提：1.1.如果一个人是单身汉，则他不幸福。如果一个人是单身汉，则他不幸福。PQPQ2.2.如果一个人不幸福，则他死得早。如果一个人不幸福，则他死得早。QRQR结论：单身汉死得早。结论：单身汉死得早。 PRPR可描述为：可描述为：PQPQ，QRQRPRPR( (假言三段论假言三段论) )172022-6-162022-6-16例子例子( (续

17、续1)1)3)3)、某女子在某日晚归家途中被杀害，据多方调查、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可晚王某在工厂值夜班，没有外出，根据上述案情可得前提：得前提：1.1.凶手为王某或陈某凶手为王某或陈某。PQPQ 2.2.如果王某是凶手，则他在作案当晚必外如果王某是凶手，则他在作案当晚必外出出 PRPR3.3.王某案发之晚并未外出。王某案发之晚并未外出。 RR结论：陈某是凶手。结论：陈某是凶手。Q Q则则可描述为可描述为：PR,RPR,RPP ( (否定后件式否定

18、后件式) ) PQPQ，PPQ Q ( (选言三段论选言三段论) )182022-6-162022-6-16例子例子( (续续2)2)4)4)、前提：、前提：1.1.如果某同学为省二级以上运动员，则他如果某同学为省二级以上运动员，则他将被大学录取。将被大学录取。PRPR2.2.如果某同学高考总分在如果某同学高考总分在560560分以上，则分以上，则将被大学录取。将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省分以上或者是省二级运动员。二级运动员。PQPQ结论：该同学被大学录取。结论：该同学被大学录取。R R则上述例子可描述为：则上述例子可描述为： PQP

19、Q，PRPR，QRQRR R( (二难推论二难推论) )192022-6-162022-6-163 3 演绎法演绎法 演绎法演绎法是从前提是从前提(假设假设)出发，依据公认的推理出发，依据公认的推理规则和推理定律，推导出一个结论来。规则和推理定律，推导出一个结论来。 YN触发规则触发规则新事实新事实事实事实=结结论？论？事实库事实库规则匹配规则匹配公理库公理库将事实加入到事实库中将事实加入到事实库中结束结束引入事实引入事实202022-6-162022-6-16引入推理规则引入推理规则在数理逻辑中，主要的推理规则有：在数理逻辑中，主要的推理规则有： P P规则（称为前提引用规则）：规则（称为前

20、提引用规则）：在推导的过程中，在推导的过程中，可可随时引入前提集合中的任意一个前提随时引入前提集合中的任意一个前提； 规则（逻辑结果引用规则）：规则（逻辑结果引用规则）：在推导的过程在推导的过程中，可以中，可以随时引入公式随时引入公式S S，该公式，该公式S S是由其前的一个是由其前的一个或多个公式推导出来的逻辑结果或多个公式推导出来的逻辑结果。 规则（附加前提规则）：规则（附加前提规则）：如果能从给定的如果能从给定的前提集合前提集合与公式与公式P P推导出推导出S S，则能从此，则能从此前提集合前提集合推导出推导出PSPS。 212022-6-162022-6-16演绎的定义演绎的定义定义定

21、义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） 分析分析：推导：推导1是错误的。是错误的。正确的推导如下：正确的推导如下： （1）( x)( y)G(x, y) P （2）( y)G(z, y) US，（，（1）注意：注意：使用使用

22、USUS规则规则来来消去消去量词时，所选用取代量词时，所选用取代x x的变的变元元y y在公式中必须是在公式中必须是自由的自由的。492022-6-162022-6-16推理规则的正确使用（推理规则的正确使用（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）G(z, f(z) ES，（，（2） 注意：注意：使用使用ESE

23、S规则规则来来消去消去量词时，量词时， 若还有其它若还有其它自自由变由变元元时，时，则必须用关于自由变元的则必须用关于自由变元的函数符号函数符号来取来取代常量符号代常量符号. .502022-6-162022-6-16推理规则的正确使用（推理规则的正确使用（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、使用的变元符所使用的变元符号不能与辖域内的变元符号相同号不能与辖域内的变元符号相同. .512022-6-162022-6-16推理规则的正确使用（推理规则的正确使用（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规则规则来来添加添加量词时，量词时， 所使用的变元符所使用的变元符号不能与辖域内的变元符号相同号不能与辖域内的变元符号相同. .522022-6-162022-6

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

26、综合推理方法（续）（5）证明时可采用如）证明时可采用如命题演算命题演算中的中的直接证明方法直接证明方法和间接证明方法和间接证明方法。（6）在推导过程中，）在推导过程中，对消去量词的公式或公式中对消去量词的公式或公式中不含量词的子公式不含量词的子公式，完全可以，完全可以引用命题演算中的基引用命题演算中的基本等价公式和基本蕴涵公式本等价公式和基本蕴涵公式。（7）在推导过程中，对）在推导过程中，对含有量词的公式含有量词的公式可以可以引用引用谓词中的基本等价公式和基本蕴涵公式谓词中的基本等价公式和基本蕴涵公式。 542022-6-162022-6-16例例5.3.1 5.3.1 解解 设设H(x)H(

27、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)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”证明：证明：(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,(

28、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),(3)T,(2),(3)，I I(4)(4)错了！错了！正确的为正确的为552022-6-162022-6-16例例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

29、)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) EG,(5)562022-6-162022-6-16例例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)U

30、S,(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)572022-6-162022-6-16例例5.3.25.3.2( () )正确地推导正确地推导如下：如下：(1)(1)( ( x)x)P(x)P(x)P P(2)(2)P(c)P(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

31、)(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)582022-6-162022-6-16例例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,3)EG,3) 6) 6)( ( x x) )Q(x)Q(x)EG,4)EG,4)

32、 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)592022-6-162022-6-16例例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),I

33、5)5)Q(c)Q(c)ES,4)ES,4)6)6)(P(c)(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)请看上述推论的逆推导请看上述推论的逆推导：602022-6-162022-6-16例例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

34、),IT,1),I5)Q(b)5)Q(b)ES,4)ES,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)612022-6-162022-6-16例例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)

35、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)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)622022-6-162022-6-16例例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

36、,7)US,7)9) 9) P(c)P(c) Q(c)Q(c) T,6),8),IT,6),8),I10)10) (P(c)(P(c)Q(c)Q(c) T,9),ET,9),E11)(11)( x)(P(x)x)(P(x)Q(x)Q(x) P P12)(P(c)12)(P(c)Q(c)Q(c) US,11)US,11)13) 13) (P(c)(P(c)Q(c)Q(c)(P(c)(P(c)Q(c) Q(c) T,10)T,10),12),12)632022-6-162022-6-165.3.3 5.3.3 谓词逻辑推理的难点谓词逻辑推理的难点（1 1）在推导过程中，如在推导过程中，如既要使用规

37、则既要使用规则USUS又要使用规又要使用规则则ESES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，而且选用的个体是同一个符号，则必须符号，则必须先先使用规则先先使用规则ESES，再使用规则，再使用规则USUS。然。然后再使用命题演算中的推理规则，最后使用规则后再使用命题演算中的推理规则，最后使用规则UGUG或规则或规则EGEG引入量词，得到所要的结论。引入量词，得到所要的结论。（2 2）如一个变量是用如一个变量是用规则规则ESES消去量词消去量词，对该变量在，对该变量在添加量词时，则添加量词时，则只能使用规则只能使用规则EGEG，而不能使用规则，而不能使用规则UGUG；如使用；如

38、使用规则规则USUS消去量词消去量词，对该变量在添加量词，对该变量在添加量词时，则时，则可使用规则可使用规则EGEG和规则和规则UGUG。642022-6-162022-6-16谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（3 3）如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消消去量词去量词时，时，不能选用同样的一个常量符号不能选用同样的一个常量符号来取代两来取代两个公式中的变元，而应用不同的常量符号来取代它个公式中的变元，而应用不同的常量符号来取代它们。们。（4）在用规则在用规则US和规则和规则ES消去量词消去量词时，此量词必时，此量词必须位于须位于整

39、个公式的最前端整个公式的最前端。652022-6-162022-6-16谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（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(y)中的函数变元中的函数变元。在使用。在使用UGUG规则规则引入引入全称量词全称量词( ( x)x)时，时，此此x x不得为不得为G(y)G(y)中的函数变元

40、中的函数变元( (因该函数变元不得作为自由变元因该函数变元不得作为自由变元) )。662022-6-162022-6-165.3.4 5.3.4 谓词逻辑推理的应用谓词逻辑推理的应用例例5.3.5 每个喜欢步行的人都不喜欢坐汽车；每个每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。欢骑自行车。因而有的人不喜欢步行。 证明证明 设设H(x)H(x)：x x是人；是人； P(x)P(x)：x x喜欢坐汽车；喜欢坐汽车； Q(x) Q(x)：x x喜欢骑自行车；喜欢骑自行车；R(x)R(x)

41、：x x喜欢步行喜欢步行。则上述语句可符号化为：则上述语句可符号化为： ( ( x)(H(x)R(x)P(x)x)(H(x)R(x)P(x)， ( ( x)(H(x)P(x)Q(x)x)(H(x)P(x)Q(x)， ( ( x)(H(x)Q(x) x)(H(x)Q(x) ( ( x)(H(x)R(x) x)(H(x)R(x) 672022-6-162022-6-16例例5.3.5 5.3.5 证明（续）证明（续） (1)(1)( x)(H(x)Q(x) Px)(H(x)Q(x) P (2)H(c)Q(c) ES (2)H(c)Q(c) ES，(1)(1) (3)H(c) T(3)H(c) T，

42、(2)(2) (4)Q(c) T(4)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 I682022-6-162022-6-16例例5.3.5 5.3.5 证明（续）证明（续） (9)(9) ( ( x)(H(x)R(x)P(x) Px)(H(x)R(x)P(x) P(10) H(

43、c)R(c)P(c) US(10) H(c)R(c)P(c) US，(9)(9)(11)(11) (H(c)R(c) T(H(c)R(c) T，(8)(8)，(10)(10)，I I(12) H(c)R(c) T(12) H(c)R(c) T，(11)(11)，E E(13) R(c) T(13) R(c) T，(3)(3)，(12)(12)，I I(14) H(c)R(c) T(14) H(c)R(c) T，(3)(3)，(13)(13)，I I(15)(15) ( ( x)(H(x)R(x) EGx)(H(x)R(x) EG，(14) (14) 692022-6-162022-6-16例例

44、5.3.6 5.3.6 证明下述论断的正确性：证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。物都是胎生动物；故有些脊椎动物不是胎生的。证明证明 设设谓词如下：谓词如下：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)702

45、022-6-162022-6-16请看下面推导：请看下面推导：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)，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

46、) 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,10)712022-6-162022-6-16例例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) (

47、( 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)US,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,

48、10)722022-6-162022-6-16例例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(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)( (

49、 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)732022-6-162022-6-16例例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(y)L(c,y)L(c,y) T,2),I T,2),I5)

50、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)742022-6-162022-6-16例例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

51、) P(x)L(c,x)L(c,x) T,3),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),E T,5),11),E13) (13) ( x)(x)(T(T(x)x)P(x) US,12)P(x) US,12)752022-6-162022-6-16例例5.3.85.3.8 现有一智力测验题目现有一智力测验题目(水容器问题水容器问题)：设有两个：设有两个分别能盛分别能盛7升与升与5升的水容器，开始时两个容器均升的水容器，开始时两个容器均空，允许对容器做三种

52、操作：空，允许对容器做三种操作： （1）容器倒满水，）容器倒满水， （2）将容器中的水倒光，）将容器中的水倒光， （3）从一个容器倒水至另一容器，使一个容）从一个容器倒水至另一容器，使一个容器倒光而另一容器倒满。器倒光而另一容器倒满。 最后要求能使大容器最后要求能使大容器(能盛能盛7升的容器升的容器)中有中有4升升水，并求其操作过程。水，并求其操作过程。 762022-6-162022-6-16例例5.3.85.3.8的的解决方案解决方案S(0,0)S(7,0)S(2,5) S(2,0) S(0,2)S(7,2)S(4,5)S(4,0)大容器注满大容器注满大容器注满大容器注满小容器倒空小容器倒空小容器注满小容器注满小容器倒空小容器倒空倒倒入入小小容容器器容容器器注注满满小容器注满小容器注满772022-6-162022-6-16例例5.3.8 5.3.8 证明证明（1 1）S(0, 0) PS(0, 0) P（2 2）( ( x)(x)( y)(S(x, y)y)(S(x, y)S(7, y)