1、第第2章章 一阶谓词逻辑一阶谓词逻辑(4)栾新成栾新成 四川大学四川大学软件学院件学院85997822 138080240811/24谓词演算综合推理方法谓词演算综合推理方法一、基本推理方法一、基本推理方法 1、直接、直接证实方法方法 2、间接接证实方法（反方法（反证法）法）3、利用、利用CP规则二、推理中需注意几个二、推理中需注意几个问题1）为了在推了在推导过程中消去量程中消去量词，能，能够引用引用规则US和和规则ES来消去量来消去量词。2）当所要求当所要求结论可能被定量可能被定量时，此，此时可引用可引用规则UG和和规则EG将其量将其量词加入。加入。3）在推在推导过程中，程中，对消去量消去量
2、词公式或公式中没含量公式或公式中没含量词子公子公式，完全能式，完全能够引用命引用命题演算中基本等价公式和基本演算中基本等价公式和基本蕴涵公涵公式。式。2/242024年年11月月29日日2谓词演算综合推理方法谓词演算综合推理方法4)在推在推导过程中，程中，对含有量含有量词公式能公式能够引用引用谓词中基本等价中基本等价公式和基本公式和基本蕴涵公式。涵公式。5)在推在推导过程中，如既要使用程中，如既要使用规则US又要使用又要使用规则ES消去公消去公式中量式中量词(要先使用要先使用规则ES，再使用，再使用规则US)。然后再使用。然后再使用命命题演算中推理演算中推理规则，最，最终使用使用规则UG或或规
3、则EG引入量引入量词，得到所要，得到所要结论。6)如一个如一个变量是用量是用规则ES消去量消去量词,对该变量在添加量量在添加量词时,则只能使用只能使用规则EG,而不能使用而不能使用规则UG;如使用如使用规则US消消去量去量词,对该变量在添加量量在添加量词时,则可使用可使用规则EG和和规则UG。7)有两个含有存在量有两个含有存在量词公式，当用公式，当用规则ES消去量消去量词时，不能，不能选取一取一样一个常量符号来取代两个公式中一个常量符号来取代两个公式中变元，而元，而应用不用不一一样常量符号来取代它常量符号来取代它们。3/242024年年11月月29日日3谓词演算综合推理方法谓词演算综合推理方法
4、8）在用）在用规则US和和规则ES消去量消去量词时，此量，此量词必必须位于整个位于整个公式最前端，而且它公式最前端，而且它辖域域为其后整个公式。其后整个公式。9）在添加量）在添加量词(x)、(x)时，所，所选取取x不能在公式不能在公式G(c)或或G(y)中以任何中以任何约束出束出现。10）在使用）在使用EG规则引入存在量引入存在量词(x)，此，此x不得不得为G(c)或或G(y)中函数中函数变元。在使用元。在使用UG规则引入全称量引入全称量词(x)时，此此x不得不得为G(y)中函数中函数变元元(因因该函数函数变元不得作元不得作为自由自由变元元)。4/242024年年11月月29日日4直接证实方法
5、直接证实方法例例5.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(x)M(x)US,(1)(3)H(s)P (4)M(s)T,(2),(3)，I(2)错了！了！5/242024年年11月月29日日5直接证实方法直接证实方法证实：(1)(x)(H(x)M(x)P (2)H(s)M(s)US,(1)(3)H(s)P (4)M(s)T,(2),(3
6、)，I6/242024年年11月月29日日6直接证实方法直接证实方法例例5.2证实：(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)(x)P(x)EG,3)5)Q(c)T,2),I 6)(x)Q(x)EG,5)7)(x)P(x)(x)Q(x)T,3),6),I 7/242024年年11月月29日日7直接证实方法直接证实方法对上述推上述推导作深入分析，考作深入分析，考虑其逆推其逆推导以下以下1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)
7、T,1),I5)Q(c)ES,4)6)(P(c)Q(c)T,3),4),I7)(x)(P(x)Q(x)EG,6)这是是错误结论推推导错了！了！选取了一取了一样一个一个常量符号来取常量符号来取代两个公式中代两个公式中变元元.8/242024年年11月月29日日8直接证实方法直接证实方法v正确推正确推导以下：以下：v1)(x)P(x)(x)Q(x)Pv2)(x)P(x)T,1),Iv3)P(c)ES,2)v4)(x)Q(x)T,1),Iv5)Q(b)ES,4)v6)(P(c)Q(b)T,3),4),Iv7)(x)(y)(P(x)Q(y)EG,6)v即即(x)P(x)(x)Q(x)(x)(y)(P(
8、x)Q(y)9/242024年年11月月29日日9直接证实方法直接证实方法例例 证实下述下述论断正确性：全部哺乳断正确性：全部哺乳动物都是脊椎物都是脊椎动物；并非物；并非全部哺乳全部哺乳动物都是胎生物都是胎生动物；故有些脊椎物；故有些脊椎动物不是胎生。物不是胎生。证实设谓词以下：以下：P(x)：x是哺乳是哺乳动物；物；Q(x)：x是脊椎是脊椎动物；物；R(x)：x是胎生是胎生动物。物。则有：有：(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x)10/242024年年11月月29日日10直接证实方法直接证实方法证实(x)(P(x)Q(x),(x)(P(x)R(x)(x)(
9、Q(x)R(x)1.1.(x)(P(x)R(x)P2.2.(P(x)R(x)US,1)3.3.(P(x)R(x)T,2)，E4.(P(x)R(x)T,3),E5.P(x)T,4),I 6.6.R(x)T,4),I7.(x)(P(x)Q(x)P8.P(x)Q(x)US,7)9.Q(x)T,(5),(8),I 10.Q(x)R(x)T,6),9),I11.(x)(Q(x)R(x)EG,10)或者有：或者有：(x)(Q(x)R(x)UG,10)2）错了！在用了！在用规则US和和规则ES消去量消去量词时，此量此量词必必须位于整个公位于整个公式最前端，而且它式最前端，而且它辖域域为其后整个公式。其后整个
10、公式。正确正确为：11/242024年年11月月29日日11直接证实方法直接证实方法证实：(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x)(x)(P(x)R(x)P(x)(P(x)R(x)T,1),E(P(c)R(c)ES,2)(P(c)R(c)T,3),EP(c)T,4),I R(c)T,4),I(x)(P(x)Q(x)PP(c)Q(c)US,7)Q(c)T,5),8),I Q(c)R(c)T,6),9),Ik(x)(Q(x)R(x)EG,10)12/242024年年11月月29日日12直接证实方法直接证实方法证实下述下述论断正确性：断正确性：每个每个报考考硕士大学
11、士大学毕业生要么参加生要么参加硕士入学考士入学考试，要么被推荐，要么被推荐为免免试生；生；每个每个报考考硕士大学士大学毕业生当且生当且仅当学当学习成成绩优异才被推荐异才被推荐为免免试生；生；有些有些报考考硕士大学士大学毕业生学生学习成成绩优异，但并非全部异，但并非全部报考考硕士大学士大学毕业生学生学习成成绩都都优异。异。所以，有些所以，有些报考考硕士大学士大学毕业生要参加生要参加硕士入学考士入学考试。设P(x)：x是是报考考硕士大学士大学毕业生；生；Q(x)：x参加参加硕士入学考士入学考试；R(x)：x被推荐被推荐为免免试生；生；S(x)：x学学习成成绩优异。异。符号化符号化为：(x)(P(x
12、)(Q(x)R(x)，(x)(P(x)(R(x)S(x)，(x)(P(x)S(x),(x)(P(x)S(x)(x)(P(x)Q(x)13/242024年年11月月29日日13直接证实方法直接证实方法证实：(x)(P(x)(Q(x)R(x)，(x)(P(x)(R(x)S(x)，(x)(P(x)S(x),(x)(P(x)S(x)(x)(P(x)Q(x)(1)(x)(P(x)S(x)P(2)(x)(P(x)S(x)T,(1),E(3)P(c)S(c)ES,(2)(4)P(c)T,(3),I(5)(x)(P(x)(Q(x)R(x)P(6)P(c)（Q(c)R(c)）US,(5)(7)Q(c)R(c)T
13、,(4),(6),I(8)(x)(P(x)(R(x)S(x)P(9)P(c)(R(c)S(c)US，（，（8）(10)R(c)S(c)T,(4),(9),I14/242024年年11月月29日日14直接证实方法直接证实方法(11)(R(c)S(c)(S(c)R(c)T,(10),E(12)R(c)S(c)T,(12),I(13)S(c)T,(3),I(14)R(c)T,(12),(13),I(15)Q(c)T,(7),(14),I(16)P(c)Q(c)T,(4),(15),I(17)(x)(P(x)Q(x)ES,(16)15/242024年年11月月29日日15反证法反证法例例证实：(x)(
14、P(x)Q(x)(x)P(x)(x)Q(x)1)(x)(P(x)Q(x)P (附加前提）附加前提）2)(x)(P(x)(x)Q(x)T 3)(x)(P(x)I 4)(x)Q(x)I 5)P(c)ES 3)6)Q(c)ES 4)7)(x)(P(x)Q(x)P 8)P(c)Q(c)US 7)9)Q(c)T,5),8),I 10)I,6),9)16/242024年年11月月29日日16利用利用CP规则规则例例证实：(x)(P(x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x)(x)P(x)(x)Q(x)1)(x)P(x)P(附加前提）附加前提）2)(x)(P(x)I 3)P(c)ES
15、4)(x)(P(x)Q(x)P 5)P(c)Q(c)US 6)Q(c)T,(3),(5),I 7)(x)Q(x)EG,(6)8)(x)P(x)(x)Q(x)CP(1),(7)17/242024年年11月月29日日17消解消解(归结归结)法法v消解消解证实过程：程：v为了了证实 G1,G2,Gn Hv(1)依据反依据反证法法，即需，即需证实 G=G1,G2,Gn,H R Rv(2)建立子句集建立子句集v 先将先将G化成等化成等值前束范式前束范式v 将前束范式化成将前束范式化成Skolem范式范式(消去存在量消去存在量词),得到得到仅含全称量含全称量词公式公式G*,从而从而对G不可不可满足性足性,
16、可由可由G*不不可可满足性得到。足性得到。18/242024年年11月月29日日18消解消解(归结归结)法法v 将将G*全称量全称量词省略。省略。v G*母式母式(已合取化已合取化)合取合取词 以以，表示表示,得得G子子句集句集S。v(3)对S作作归结(消解消解)v 归结：设C1,C2是两个无共同是两个无共同变元子句元子句,L1,L2分分别是是C1,C2中句中句节。假如。假如L1和和L2有合一置有合一置换(一致化一致化)(L1,L2中中变元元x用用 代入代入),v (C1-L1)U(C2-L2)称作子句称作子句C1,C2归结式。式。19/242024年年11月月29日日19消解消解(归结归结)
17、法法v（比如（比如 C1=P(x)Q(x)C2=P(a)R(y)v P(x)与与P(a)合一置合一置换a/x,即将即将变元元x换成成a,便便为互互补对,可作可作归结了了,有有归结式式v R(C1,C2)=Q(a)R(y)）v 对子句集子句集S任意两个子句作任意两个子句作归结(假如可作假如可作归结)并将并将归结式仍放入式仍放入S,重复重复这一一过程。程。v(4)直到直到归结出空子句出空子句,证实结束束。20/242024年年11月月29日日20消解消解(归结归结)法法v消解消解(归结)法法证实举例例v例例4.6 证实 x(P(x)Q(x)x(Q(x)R(x)x(P(x)R(x)v解：解：(1)写
18、出公式写出公式G=x(P(x)Q(x)x(Q(x)R(x)（x(P(x)R(x)）v为求子句集求子句集S,可分可分别对G三个合取范式分量三个合取范式分量结构子句集构子句集,然然后作并集得后作并集得G子句集。子句集。v x(P(x)Q(x)子句集子句集为:v P(x)Q(x)v x(Q(x)R(x)子句集子句集为:v Q(x)R(x)21/242024年年11月月29日日21消解消解(归结归结)法法v x(P(x)R(x)v x(P(x)R(x)v x(P(x)R(x)v其子句集其子句集为:P(a),R(a)v于是于是G子句集子句集vS=P(x)Q(x),Q(x)R(x),P(a),R(a)22/242024年年11月月29日日22消解消解(归结归结)法法v归结过程程:P(x)Q(x),Q(x)R(x),P(a),R(a)v1)P(x)Q(x)v2)Q(x)R(x)v3)P(a)v4)R(a)v5)Q(a)1),3)归结v6)R(a)2),5)归结v7)4),6)归结23/242024年年11月月29日日23作业作业v习题二二 16、17、1824/242024年年11月月29日日24
