推理与证明技术.ppt

电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院28 28 十一月十一月 2022 2022电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2第第5 5章章 推理与证明技术推理与证明技术 数学归纳法的使用数学归纳法的使用 3CPCP规则相关证明规则相关证明4命题逻辑的推理理论命题逻辑的推理理论 1谓词逻辑的推理理论谓词逻辑的推理理论 2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程35.1 5.1 本章学习要求本章学习要求1掌握各种不同掌握各种不同类型的规则和类型的规则和公理，特别是公理，特别是命题逻辑和谓命题逻辑和谓词逻辑的推理词逻辑的推理规则和公理规则和公理 3理解谓词逻辑理解谓词逻辑的精髓，将其的精髓，将其思想贯穿于所思想贯穿于所有的证明之中有的证明之中 2熟练掌握不同熟练掌握不同证明方法的证证明方法的证明原理、不同明原理、不同的应用场景的应用场景 重点掌握重点掌握一般掌握一般掌握了解了解电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程45.2 5.2 命题逻辑的推理理论命题逻辑的推理理论 概念概念描述问题描述问题的句子；的句子；Add Your Text判断判断对概念的肯对概念的肯定与否定的定与否定的判断；判断；推理推理从一个或多从一个或多个前提推出个前提推出结论的思维结论的思维过程。过程。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程5推理的有效性和结论的真实性推理的有效性和结论的真实性有效的推理不一定产生真实的结论有效的推理不一定产生真实的结论；而而产生真实结论的推理过程未必是有效的产生真实结论的推理过程未必是有效的。有效的推理有效的推理中可能包含为中可能包含为“假假”的前提的前提，而而无效的推理无效的推理却可能得到为却可能得到为“真真”的结论的结论。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程6推理的有效性和结论的真实性推理的有效性和结论的真实性所谓所谓推理有效推理有效，指的是指的是它的结论是它的前提的合乎逻辑的结果它的结论是它的前提的合乎逻辑的结果。即，如果它的即，如果它的前提都为真，那么所得的结论也前提都为真，那么所得的结论也必然为真必然为真，而并不是要求前提或结论一定为真或为，而并不是要求前提或结论一定为真或为假；假；如果推理是有效的话，那么不可能它的前提都为如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。真时，而它的结论为假。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程75.2.1 5.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 conclusion)(logic 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,G,Gn n称为一组前提称为一组前提(Premise)(Premise)，有时用集合，有时用集合来来表示，记表示，记=G=G1 1,G,G2 2,G,Gn n。H H称为称为结论结论(conclusion)(conclusion)。又称又称H H是前提集合的逻辑结果。记为是前提集合的逻辑结果。记为 H H。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8判定定理判定定理定理定理 公式公式H H是前提集合是前提集合=G=G1 1,G,G2 2,G,Gn n 的逻的逻辑结果辑结果当且仅当当且仅当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 G1 1GG2 2GGn nHH是永真公式。是永真公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程9判定定理（续）判定定理（续）“”若若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 n H H为假，这为假，这 就与就与G G1 1GG2 2GGn nHH是永真式相矛盾，是永真式相矛盾，所以所以G G1 1,G,G2 2,G,Gn n 是有效的推理形式。是有效的推理形式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程10“”与与“”“”的不同的不同1.1.“”“”仅是一般的仅是一般的蕴涵联结词蕴涵联结词，GHGH的结果仍是一个公的结果仍是一个公式，式，而而“”却描述了两个公式却描述了两个公式G G，H H之间的一种逻辑蕴涵之间的一种逻辑蕴涵关系，关系，G G H H的的“结果结果”，是非命题公式；，是非命题公式；2.2.用计算机来判断用计算机来判断G G H H是办不到的。是办不到的。然而计算机却可然而计算机却可“计算计算”公式公式GHGH是否为永真是否为永真公式。公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程115.2.2 5.2.2 判断有效结论的常用方法判断有效结论的常用方法 要求要求=G G1 1,G,G2 2,G,Gn n H H也就是也就是G G1 1GG2 2GGn n为永真公式为永真公式因而因而真值表技术、演绎法和真值表技术、演绎法和间接证明方法间接证明方法电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程121 1、真值表技术、真值表技术 设设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 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的逻辑结果的逻辑结果.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程13例例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：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 01 11 10 00 01 11 11 11 11 10 00 00 00 01 11 10 01 11 1(3)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程142 2 推理定律推理定律设设G G，H H，I I，J J是任意的命题公式，则有：是任意的命题公式，则有：1)1)I I1 1：GH GH G G(简化规则简化规则)I I2 2：GH GH H H2)2)I I3 3：G G GHGH(添加规则添加规则)I I4 4：H H GHGH3)3)I I5 5：G G GHGHI I6 6：H H GHGH4)4)I I7 7：(GH)(GH)G GI I8 8：(GH)(GH)HH5)5)I I9 9：G,H G,H GHGH电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程152 2 推理定律推理定律(续续)6）I10：G,G H H (选言选言/析取析取三段论三段论)I11：G,G H H7）I12：G,GH H(分离规则分离规则)8）I13：H,GH G (否定后件式否定后件式)9）I14：GH,HI GI (假言三段论假言三段论)10）I15：G H,GI,HI I (二难推论二难推论)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程16例子例子1)1)、前提：、前提：1.1.如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。PQPQ2 2明天的确天晴。明天的确天晴。P P结论：我们外出旅游。结论：我们外出旅游。Q Q可描述为：可描述为：PQPQ，P P Q Q(分离规则分离规则)2)2)、前提：、前提：1.1.如果一个人是单身汉，则他不幸福。如果一个人是单身汉，则他不幸福。PPQ Q2.2.如果一个人不幸福，则他死得早。如果一个人不幸福，则他死得早。QRQR结论：单身汉死得早。结论：单身汉死得早。PRPR可描述为：可描述为：PPQ Q，QRQR PRPR(假言三段论假言三段论)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程17例子例子(续续1)1)3)3)、某、某人人在某日晚归家途中被杀害，据多方调查确在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得王某在工厂值夜班，没有外出，根据上述案情可得：前提：前提：1.1.凶手为王某或陈某凶手为王某或陈某。PQPQ 2.2.如果王某是凶手，则他在作案当晚必外如果王某是凶手，则他在作案当晚必外出出 PRPR3.3.王某案发之晚并未外出。王某案发之晚并未外出。RR结论：陈某是凶手。结论：陈某是凶手。Q Q则则可描述为可描述为：PR,RPR,R PP(否定后件式否定后件式)PQPQ，PP Q Q(选言三段论选言三段论)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程18例子例子(续续2)2)4)4)、前提：、前提：1.1.如果某同学为省二级以上运动员，则他如果某同学为省二级以上运动员，则他将被大学录取。将被大学录取。PRPR2.2.如果某同学高考总分在如果某同学高考总分在560560分以上，则分以上，则将被大学录取。将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省分以上或者是省二级运动员。二级运动员。PQPQ结论：该同学被大学录取。结论：该同学被大学录取。R R则上述例子可描述为：则上述例子可描述为：PQPQ，PRPR，QRQR R R(二难推论二难推论)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程193 3 演绎法演绎法 演绎法演绎法是从前提是从前提(假设假设)出发，依据公认的推理出发，依据公认的推理规则和推理定律，推导出一个结论来。规则和推理定律，推导出一个结论来。YN触发规则触发规则新事实新事实事实事实=结论结论？事实库事实库规则匹配规则匹配公理库公理库将事实加入到事实库中将事实加入到事实库中结束结束引入事实引入事实电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程20引入推理规则引入推理规则在数理逻辑中，主要的推理规则有：在数理逻辑中，主要的推理规则有：P P规则（称为前提引用规则）：规则（称为前提引用规则）：在推导的过程中，在推导的过程中，可可随时引入前提集合中的任意一个前提随时引入前提集合中的任意一个前提；规则（逻辑结果引用规则）：规则（逻辑结果引用规则）：在推导的过程在推导的过程中，可以中，可以随时引入公式随时引入公式S S，该公式，该公式S S是由其前的一个是由其前的一个或多个公式推导出来的逻辑结果或多个公式推导出来的逻辑结果。规则（附加前提规则）：规则（附加前提规则）：如果能从给定的如果能从给定的前提集合前提集合与公式与公式P P推导出推导出S S，则能从此，则能从此前提集合前提集合推导出推导出PSPS。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程21演绎的定义演绎的定义定义定义 从前提集合从前提集合推出结论推出结论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）使用使用USUS规则消去规则消去量量词，词，“y y”在公式中必在公式中必须是须是自由的自由的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程50推理规则的正确使用（推理规则的正确使用（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）使用使用ESES规则消规则消去去量词，量词，若还若还有其它有其它自由变自由变元元，则必须用则必须用关于自由变元关于自由变元的的函数符号函数符号来来取代常量符号取代常量符号.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程51推理规则的正确使用（推理规则的正确使用（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规则规则来来添加添加量词时，量词时，所使用的变元符所使用的变元符号号不能与不能与辖域内的变元符号辖域内的变元符号相同相同.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程52推理规则的正确使用（推理规则的正确使用（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规则规则来来添加添加量词时，量词时，所使用的变元符所使用的变元符号号不能与不能与辖域内的变元符号辖域内的变元符号相同相同.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程535.3.2 5.3.2 谓词演算的综合推理方法谓词演算的综合推理方法（1）推导过程中可以引用命题演算中的）推导过程中可以引用命题演算中的规则规则P 和和规则规则T。（2）如果）如果结论是以条件的形式结论是以条件的形式(或析取形式或析取形式)给出，给出，我们还可以我们还可以使用规则使用规则CP。（3）若需）若需消去量词消去量词，可以，可以引用规则引用规则US和规则和规则ES。（4）当所要求的结论可能被）当所要求的结论可能被定量定量时，此时可时，此时可引用引用规则规则UG和规则和规则EG将其量词加入将其量词加入。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程54谓词演算的综合推理方法（续）谓词演算的综合推理方法（续）（5）证明时可采用如）证明时可采用如命题演算命题演算中的中的直接证明方法直接证明方法和间接证明方法和间接证明方法。（6）在推导过程中，）在推导过程中，对消去量词的公式或公式中对消去量词的公式或公式中不含量词的子公式不含量词的子公式，完全可以，完全可以引用命题演算中的基引用命题演算中的基本等价公式和基本蕴涵公式本等价公式和基本蕴涵公式。（7）在推导过程中，对）在推导过程中，对含有量词的公式含有量词的公式可以可以引用引用谓词中的基本等价公式和基本蕴涵公式谓词中的基本等价公式和基本蕴涵公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程55例例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)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”证明：证明：(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)(4)M(s)M(s)T,(2),(3)T,(2),(3)，I I(4)(4)错了！错了！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程56例例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)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”正确正确证明：证明：(1)1)(x)(H(x)x)(H(x)M(x)M(x)P P (2)(2)H(H(s s)M(M(s 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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程57例例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)(P(x)(2)(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),I T,(2),(4),I (6)(6)(x)x)Q(x)Q(x)EG,(5)EG,(5)(4)(4)中的中的“c”c”未必能保证未必能保证令令(2)(2)为真，为真，推导错误！推导错误！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程58例（例（)推导可修改为（正确与否？）推导可修改为（正确与否？）：(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(P(c)(2)(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)Q(c)(5)Q(c)T,(2),(4),IT,(2),(4),I(6)(6)(x)x)Q(x)Q(x)EG,(5)EG,(5)证明：证明：(x)(P(x)x)(P(x)Q(x)Q(x)，(x)x)P(x)P(x)(x)x)Q(x)Q(x)(2)(2)中的中的“c”c”未必能保证未必能保证令令(4)(4)为真，为真，推导错误！推导错误！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程59例例()正确推导正确推导如下：如下：(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)(P(c)(4)(P(c)Q(c)Q(c)US,(3)US,(3)(5)Q(c)(5)Q(c)T,(2),(4),IT,(2),(4),I(6)(6)(x)x)Q(x)Q(x)EG,(5)EG,(5)证明：证明：(x)(P(x)x)(P(x)Q(x)Q(x)，(x)x)P(x)P(x)(x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程60例例证明证明：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)7)7)(x x)P(x)P(x)(x x)Q(x)Q(x)T,5),6),I T,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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程61例例(续续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)P(c)3)P(c)ES,2)ES,2)4)4)(x x)Q(x)Q(x)T,1),IT,1),I5)Q(c)5)Q(c)ES,4)ES,4)6)(P(c)6)(P(c)Q(c)Q(c)T,3),4),I T,3),4),I7)7)(x x)(P(x)(P(x)Q(x)Q(x)EG,6)EG,6)请看上述推论的逆推导请看上述推论的逆推导（正确与否？）（正确与否？）：证明：证明：(x x)(P(x)(P(x)Q(x)Q(x)(x)x)P(x)P(x)(x)x)Q(x)Q(x)“c”c”未必能保证同时令未必能保证同时令(2)(2)和和(4)(4)为真，为真，推导错误！推导错误！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程62例例(续续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,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)(x x)(P(x)(P(x)Q(x)Q(x)(x)x)P(x)P(x)(x)x)Q(x)Q(x)的逆推导：的逆推导：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程63例例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)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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程64例例5.3.4 5.3.4 证明（续）证明（续）6)6)P(c)P(c)ES,5)ES,5)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)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)证明证明(x)(P(x)x)(P(x)Q(x)Q(x)(x)P(x)x)P(x)(x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程655.3.3 5.3.3 谓词逻辑推理的难点谓词逻辑推理的难点（1 1）在推导过程中，如在推导过程中，如既要使用规则既要使用规则US又要使用规又要使用规则则ES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，而且选用的个体是同一个符号，则必须符号，则必须先使用规则先使用规则ES，再使用规则，再使用规则US。然后再使用命题演算中的推理规则，最后使用然后再使用命题演算中的推理规则，最后使用规则规则UGUG或规则或规则EGEG引入量词，得到所要的结论。引入量词，得到所要的结论。（2 2）如一个变量是用如一个变量是用规则规则ES消去量词消去量词，对该变量再，对该变量再添加量词时，则添加量词时，则只能使用规则只能使用规则EG，而不能使用规则，而不能使用规则UGUG；如使用；如使用规则规则US消去量词消去量词，对该变量在添加量词，对该变量在添加量词时，则时，则可使用规则可使用规则EG和规则和规则UG。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程66谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（3 3）如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消消去量词去量词时，时，不能选用同样的一个常量符号不能选用同样的一个常量符号来取代两来取代两个公式中的变元，而应用不同的常量符号来取代它个公式中的变元，而应用不同的常量符号来取代它们。们。（4）在用规则在用规则US和规则和规则ES消去量词消去量词时，此量词必时，此量词必须位于须位于整个公式的最前端整个公式的最前端。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（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)中的函数变元中的函数变元(因该函数变元不得作为自由变元因该函数变元不得作为自由变元)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程685.3.4 5.3.4 谓词逻辑推理的应用谓词逻辑推理的应用例例 每个喜欢步行的人都不喜欢坐汽车；每个人或每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。自行车。因而有的人不喜欢步行。证明证明 设设H(x)H(x)：x x是人；是人；P(x)P(x)：x 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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程69例例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)(2)(4)(4)Q(c)TQ(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上述语句可符号化为：上述语句可符号化为：(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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程70例例5.3.5 5.3.5 证明（续）证明（续）(3)H(c)T(3)H(c)T，(2)(2)(8)P(c)T(8)P(c)T，(4)(4)，(7)(7)，I I(9)(9)(x)(H(x)R(x)x)(H(x)R(x)P(x)PP(x)P(10)H(c)R(c)(10)H(c)R(c)P(c)USP(c)US，(9)(9)(11)(11)(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)上述语句可符号化为：上述语句可符号化为：(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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程71例例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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程72请看下面推导：请看下面推导：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)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)(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)错误推导错误推导电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程73例例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