数理逻辑 课 程 V

第5章 谓词逻辑的等值和推理演算 谓词逻辑研究的对象是重要的逻辑规律，普遍有效式是最重要的逻辑规律，而等值式、推理式都是普遍有效的谓词公式，因此等值和推理演算就成了谓词逻辑的基本内容，同命题逻辑相比，由于量词谓词的引入，使谓词演算有着广泛的应用．特别是计算机科学、人工智能等领域，是把谓词逻辑当作表示知识、实现推理的有力工具来看待的． 这章的讨论，主要是以语义的观点进行的非形式的描述，而严格的形式化的讨论见第6章所建立的公理系统．

5．1 否定型等值式 若给定了两个谓词公式A，B，说A和B是等值的，如果在公式A，B的任一解释下，A和B都有相同的真值． 5．1 否定型等值式 若给定了两个谓词公式A，B，说A和B是等值的，如果在公式A，B的任一解释下，A和B都有相同的真值． 等价的说法是A，B等值当且仅当A↔B是普遍有效的公式,A和B等值．就记作A＝B或AB，

5．1．1 由命题公式移植来的等值式 若将命题公式的等值式，直接以谓词公式代入命题变项便可得谓词等值式．由 5．1．1 由命题公式移植来的等值式 若将命题公式的等值式，直接以谓词公式代入命题变项便可得谓词等值式．由 ﹁﹁p＝p,p→q=﹁p∨q, (p∧q)∨r=(p∨r)∧(q∨r) 可得 ﹁﹁P(x)＝P(x) ﹁﹁(x)P(x)＝(x)P(x) P(x)→Q(x)＝﹁P(x)∨Q(x) (x)P(x)→(x)Q(x)＝﹁ (x)P(x)∨(x)Q(x) (P(x)∧Q(x))∨R(x)=(P(x)∨R(x))∧(Q(x)∨R(x)) ((x)P(x)∧Q(y))∨(z)R(z)=((x)P(x)∨(z)R(z))∧(Q(y)∨(z)R(z))

5．1．2 否定型等值式 ﹁(x)P(x)=(x)﹁P(x) ﹁(x)P(x)=(x)﹁P(x) 5．1．2 否定型等值式 ﹁(x)P(x)=(x)﹁P(x) ﹁(x)P(x)=(x)﹁P(x) 形式上看这对公式，是说否定词”﹁”可越过量词深入到量词的辖域内，但要把所越过的量词转换为，转换为

(1)从语义上说明 ﹁(x)P(x)语义上表示的是，并非所有的x都具有性质P．这相当于，有一个x不具有性质P，这正是 (x)﹁P(x)的含义．从而由语义分析知﹁(x)P(x) 与(x)﹁P(x)表示的是同一命题，自然有 ﹁(x)P(x)=(x)﹁P(x) (x)P(x)=﹁ (x)﹁P(x) 类似的有﹁(x)P(x)=(x)﹁P(x) (x)P(x)=﹁(x)﹁P(x)

而﹁(x)P(x)与(x)﹁P(x)不等值，如P(x)表示x是有理数，前者的语义是并非所有的x都是有理数．而后者的语义是说所有的x都不是有理数．这两句话是不同的。

(2)在{l，2}域上分析 ﹁(x)P(x)=﹁(P(1)^P(2))=﹁P(1)v﹁P(2)=(x) ﹁P(x) ﹁(x)P(x)=﹁(P(1)vP(2))=﹁P(1)^﹁P(2)=(x)﹁P(x) 这样看来，否定词越过量词的内移规律，就是摩根律的推广．

(3)语义上的证明 依等值式定义，A=B如果在任一解释I下A真B就真，而且B真A就真． 若证明﹁(x)P(x)=(x)﹁P(x) 设任—解释I下有﹁(x)P(x)=T 从而(x)P(x)=F，即有一个xoD,使P(Xo)=F 于是﹁P(xo)=T 故在I下(x)﹁P(x)=T 反过来，设任—解释I下有 (x) ﹁P(x)=T 即有一个xoD,使﹁P(Xo)=T 从而P(Xo)=F 于是(x) P(x)=F 即﹁ (x)P(x)=T

(4)举例 例1 “并非所有的动物都是猫”的表示 设 A(x)：x是动物 B(x)：x是描 原语句可表示成﹁(x)(A(x)B(x)) 例1 “并非所有的动物都是猫”的表示 设 A(x)：x是动物 B(x)：x是描 原语句可表示成﹁(x)(A(x)B(x)) 依否定型公式得

例2 “天下乌鸦—般黑”的表示 设 F(x)：x是乌鸦 G(x，y)：x与y是一般黑 原语句可表示成 (x)(y)(F(x)^F(y) →G(x,y)) 不难知道与之等值的公式是 ﹁(x)(y)(F(x)^F(y)^﹁G(x,y)) 即不存在x,y是乌鸦但不一般黑．这两句话含义是相同的．经计算有

5．2 量词分配等值式 5．2．1 量词对V、^的分配律 这是一组量词对V、^的分配律，其中q是命题变项，与个体变元x无关，这是很重要的条件． 我们仅对第一个等式给出证明，其余三个同样可证．

设在一解释I下，(x)(P(x)vq)=T，从而对任一x D ，有P(x)vq=T 又设q＝T，则(x)P(x)vq=T 若q＝F，从而对任一x D ，有P(x) =T ，即有(x)P(x)=T，故仍有，(x)P(x)vq=T 反过来，设在一解释I下，(x)P(x)vq=T，又设q=T，则(x)(P(x)vq)=T 若q=F，必有(x)P(x)=T，从而对任一xD有P(x) =T，于是对任一x D有P(x)vq=T故(x)(P(x)vq)=T．

5．2．2 量词对→的分配律 这是一组量词对→的分配律，其中p，q是命题变项，与个体变元x无关，这是很重要的条件．

先证明其中的第一个等式． 依5．2．1的等值式 依5．l．2的等值式

再证明其中的第三个等式 依5．2．l的等值式 其余两个等值式同样可证．

5．2．3 量词对^、量词对V的分配律 这是当P(x)，Q(x)都含有个体变元x时，量词对^，量词对V所遵从的分配律．然而对V，对^的分配律一般并不成立．

(1)先证明对^的分配律 设在一解释I下，(x)(P(x)^Q(x))=T于是对任一x D P(x)^Q(x)=T 即P(x)=Q(x)=T 从而有(x)P(x)=(x)Q(x)=T 故有(x)P(x)^(x)Q(x)=T 反推回去，易知在一解释I下，只要 (x)P(x)^(x)Q(x)=T 必有(x)(P(x)^Q(x))=T

再证明对v的分配律 设在一解释I下，(x)(P(x)vQ(x))=T.于是有x0D 使 P(x0)vQ(x0)=T 从而有P(x0)=T或Q(x0)=T也即 (x)P(x)或(x)Q(x)为T 故有(x)P(x)v(x)Q(x)=T 反推回去，易知在一解释I下，只要(x)P(x)v(x)Q(x)=T 必有(x)(P(x)vQ(x))=T

(2)分析一下，对V，对^分配律不成立的原因． 先从{1，2}域上看．有 (x)(P(x)vQ(x))=(P(1)vQ(1))^(P(2)vQ(2)) =(P(1)^P(2))v(Q(1)^Q(2))v(P(1)^Q(2))v(Q(1)^P(2)) 而 (x)P(x)v(x)Q(x)=(P(1)^P(2))v(Q(1)^Q(2)) 于是有 (x)(P(x)vQ(x))=(x)P(x)v(x)Q(x)v(P(1)^Q(2))v(Q(1)^P(2)) 然而 (x)(P(x)^Q(x))=(P(1)^Q(1))^(P(2)^Q(2)) =(P(1)^P(2))^(Q(1)^Q(2))=(x)P(x)^(x)Q(x)

可看出对^的分配律，只涉及到^和交换律，这是没有问题的，对V的分配律，涉及到^和V，这是对V分配律不成立的原因．从{1，2}域上的观察，可知 (x)P(x)v(x)Q(x)=>(x)(P(x)vQ(x)) 是成立的．将会看到在任意论域D上也是成立．再看

同样可看出对V的分配律，只涉及到V和交换律，仍然是没问题的．对^的分配律，涉及到V和^，这是对^分配律不成立的原因．从{1，2}域上的观察，可知 (x)(P(x)^Q(x))=>(x)P(x)^(x)Q(x) 是成立的．将会看到在任意论域D上也是成立的． 还可解释性的说明． 由(x)(P(x)vQ(x))=T,导不出(x)P(x)v(x)Q(x)=T如下规定解释I: x1时,P(x1)=T而Q(x1)=F. x2时,P(x2)=F而Q(x2)=T. 对其他x属于D，只要求P(x)，Q(x)中只有一为T．在这个I下，显然有(x)(P(x)vQ(x))=T 而没有(x)P(x)v(x)Q(x)=T 同样在这个I下,有(x)P(x)^(x)Q(x)=T,而没有(x)(P(x)^Q(x))=T

5．2．4 变元易名后的分配律 这两个等值式，说明了通过变元的易名，仍可实现对V，对^的分配律． 证明是容易的．首先有变元易名等值式 5．2．4 变元易名后的分配律 这两个等值式，说明了通过变元的易名，仍可实现对V，对^的分配律． 证明是容易的．首先有变元易名等值式 (x)P(x)= (y)P(y) (x)P(x)= (y)P(y) 于是(x)P(x)v(x)Q(x)=(x)P(x)v(y)Q(y)

对x而言(y)Q(y)相当于命题变项，与x无关，可推得 (x)P(x)v(y)Q(y)=(x)(P(x)v(y)Q(y)) 对y而言，P(x)相当于命题变项与y无关，又可推得 (x)(P(x)v(y)Q(y))=(x)(y)(P(x)vQ(y)) 同理(x)(y)(P(x)^Q(y))=(x)P(x)^(x)Q(x) 然而(x)(y)(P(x)vQ(y))与(x)(P(x)vQ(x)) 是不等值的(x)(y)(P(x)^Q(y))与(x)(P(x)^Q(x)) 也是不等值的

5．3 范 式 在命题逻辑里．每一公式都有与之等值的范式，范式是一种统一的表达形式、当研究一 5．3 范 式 在命题逻辑里．每一公式都有与之等值的范式，范式是一种统一的表达形式、当研究一 个公式的特点(如永真、永假)时，范式起着重要的作用．对谓词逻辑的公式来说也有范式，其中前束范式与原公式是等值的，而其他范式与原公式只有较弱的关系，

5．3．1 前束范式 定义5．3．1 说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边(不含否定词)且这些量词的辖域都延伸到公式的末端，前束范式A的一般形式为 (Q1x1)…(Qnxn)M(xl，…，xn) 其中Q，为量词或(i＝l，…，n)，M称作公式A的母式(基式)，M中不再有量词．

定理5．3．1 谓词逻辑的任一公式都可化为与之等值的前束范式．但其前束范式并不唯一． 我们并不一般性地证明这个定理(只是为了避免叙述上的不便)，而是通过例子给出化前来范式的过程．

经过这几步，便可求得任一公式的前束范式．由于每一步变换都保持着等值性，所以，所得到的前束形与原公式是等值的． 这里的S(a，b，x，y，z)便是原公式的母式． 由于前束中量词的次序排列，以及对母式都没有明确的限制，自然前束范式不是唯一的，如例1的前束范式也可以是 (x)(z)(y)(S(a,b,x,y,z)^P) 其中P可以是任一不含量词的普遍有效的公式。

5．3．2 Skolem标准形 前束范式对前束量词没有次序要求，也没有其他要求．如果对前束范式进而要求所有存 在量词都在全称量词之左，或是只保留全称量词而消去存在量词，便得Skolem标准．不 难想像，仍保持与原公式的等值性就不可能了，只能保持在某种意义下的等值关系．

(1)前束范式 一个公式的前束范式或说Skolem标准形为 (x1)…(xi)(xi+1)…(xn )M(x1，…，xn) 即存在量词都在全称量词的左边，且可保持至少有一个存在量词(i≥1)，其中M(x1，…，xn)中不再含有量词也无自由个体变项

定理5．3 ． 2 谓词逻辑的任一公式A，都可化成相应的前束范式，并且A是普遍有效的当且仅当其前束范式是普遍有效的。

例2 求( x)( y)( u)P(x，y，u)的前束范式(P中无量词)． 将一公式化成前束形，首先要求出前束形，再做前束，这个例子已是前束形了，便可直接求前束形．

首先将全称量词( y)改写成存在量词( y)，其次是引入谓词S和一个变元z，得S(x，z)，建立公式 ( x)((y)(u)(P(x，y，u)^﹁S(x，y))V(z)S(x，z)) 其中﹁S(x，y)的变元，是(y)的变元y和(y)左边存在量词( x)的变元x附加的(z)S(x，z)中的变元z是新引入的未在原公式中出现过的个体，S也是不曾在M中出现过的谓词． 进而将(z)左移(等值演算)，便得前束范式 ( x)(y)(u)(z)((P(x，y，u)^﹁S(x，y))VS(x，z))． 当原公式中，有多个全称量词在存在量词的左边，可按这办法将全称量词逐一地右移． 前束范式仅在普遍有效的意义下与原公式等值． 前束形对谓词逻辑完备性的证明是重要的．

(2)Skolem标准形 另一种Skolem标准形是仅保留全称量词的前束形． 定理5．3．3 谓词逻辑的任一公式A，都可化成相应的Skolem标准形(只保留全称量词的前束形)，并且A是不可满足的当且仅当其Skolem标准形是不可满足的． 这定理是说对不可满足的公式，它与其Skolem标准形是等值的，而一般的公式与其Skolem标准形并不是等值的．自然仅当A是不可满足的方使用Skolem标准形.

例3 求公式(x)(y)(z)(u)(v)(w)P(x，y，z，u，v，w)的Skolem标准形． 将一公式化成Skolem标准形，首先也要求出前束形．这个例子已是前束形了，便可直接求Skolem标准形了．

首先将最左边的(x)消去，而将谓词P中出现的所有变元x均以论域中的某个常项a(未在P中出现过)代入．进而消去从左边数第二个存在量词(u)，因(u)的左边有全称量词(y)(z)，需将谓词P中出现的所有变元w均以y，z的某个二元函数f(y，z)(未在P中出现过)代人．最后按同样的方法消去存在量词(w)，因(w)的左边有全称量词(y)(z)和(v)，需将谓词P中出现的所有变元w均以y，z，v的某个三元函数g(y，z，v)(未在P中出现过也不同于f(y，z))代人．这样便得消去全部存在量词的Skolem标准形 (y)(z)(v)P(a，y，z，f(y，z)，v，g(y，z，v))．

消存在量词是将相应变元以函数代入，可这样来理解，如(x)(y)P(x，y)的Skolem标准形是(y)P(x，f(x))．因为(x)(y)P(x，y)的意思是对任一x，都有一个y使P(x，y)成立，那么这个y通常是依赖于x的，可视作x的某个函数f(x)．从而有Skolem标准形(x)P(x，f(x))，然而所能找到的y不必然是x的函数f，于是(x)(y)P(x,y)与(x)P(x，f(x))并不等值．

在{1，2}域上 (x)(y)P(x，y)=(P(1，1)VP(1，2))^(P(2，1)VP(2，2)) (x)P(x，f(x))=P(1，f(1))^P(2，f(2)) 两者明显的不等值，但在不可满足的意义下两者是一致的，这种标准形，对使用归结法的定理证明来说是重要的． 还可讨论前束形(在所有的的左边)，而且一个公式与它的前束形在可满足意义下是一致的．

5．4 基本的推理公式 命题逻辑中有关推理形式、重言蕴涵以及基本的推理公式的讨论和所用的术语，都可引 入到谓词逻辑中．并可把命题逻辑的推理作为谓词逻辑推理的一个部分来看待． 这里所介绍的是谓词逻辑所特有的，在命题逻辑里不能讨论的推理形式和基本的推理公式、

5．4 ． 1 推理形式举例 例1 所有的整数都是有理数，所有的有理数都是实数，所以所有的整数都是实数． 5．4 ． 1 推理形式举例 例1 所有的整数都是有理数，所有的有理数都是实数，所以所有的整数都是实数． 引入谓词将这三句话形式化，可得如下推理形式: (x)(P(x)→Q(x))^(x)(Q(x)→R(x))→(x)(P(x)→R(x))

例2 所有的人都是要死的，孔子是人，所以孔子是要死的，引入谓词将这三句话形式化，可得如下推理形式： (x)(A(x)→B(x))^A(孔子)→B(孔子)．

例3 有一个又高又胖的人，必有一个高个子而且有—个胖子。 引入谓词将这两句话形式化，可得如下推理形式： (x)(C(x)^D(x))→(x)C(x)^(x)D(x)．

例4 若某一个体a具有性质E，那么所有的个体x都具有性质E． 这两句话形式化，可得如下推理形式： E(a)→(Vx)E(x) 不难看出，由例1，2，3所建立的推理形式是正确的，而例4的推理形式是不正确的，

从而有 (x)(P(x)→Q(x))^(x)(Q(x)→R(x))=>(x)(P(x)→R(x)) (x)(A(x)→B(x))^A(孔于)=>B(孔子) (x)(C(x)^D(x))=>(x)C(x)^(x)D(x) 这样的推理形式是命题逻辑所不能处理的，或说这些推理关系，仅使用命题逻辑的工具是无法描述的．需使用谓词逻辑的工具．如例1所讨论的推理，在命题逻辑里只能形式化成 三个独立命p，q，r间的推理形式 p^q→r 这显然不是正确的推理形式，

5 ． 4．2 基本的推理公式 (1) (x)P(x)V(x)Q(x)=>(x)(P(x)VQ(x)) 5 ． 4．2 基本的推理公式 (1) (x)P(x)V(x)Q(x)=>(x)(P(x)VQ(x)) (2) (x)(P(x)^Q(x))=>(x)P(x)^(x)Q(x) (3) (x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x) (4) (x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x) (5) (x)(P(x)←→Q(x) )=>(x)P(x)←→(x)Q(x) (6) (x)(P(x)←→Q(x))=>(x)P(x)←→(x)Q(x) (7) (x)(P(x)→Q(x)) ^ (x)(Q(x)→R(x))=>(x)(P(x)→R(x)) (8) (x)(P(x)→Q(x)) ^ P(a)=>Q(a) (9) (x)(y)P(x,y)=>(x)(y)P(x,y) (x)(y)P(x,y)=>(y)(x)P(x,y) 这些推理公式或称椎理定理的逆一般是不成立的，所以正确地理解这些定理的前提与结论的不同是重要的。

5．4 ． 3 基本推理公式的说明 对这些基本推理公式的直观说明以及解释性的证明仅就其中的2，3和10来讨论 5．4 ． 3 基本推理公式的说明 对这些基本推理公式的直观说明以及解释性的证明仅就其中的2，3和10来讨论 (1)(x)(P(x)^Q(x))=>(x)P(x)^(x)Q(x) 这定理在{1．2}域上是成立的，已在5．2．3节作了说明,再从语义上讨论． 如果个体域是某班学生，P(x)表x是高材生．Q(x)表x是运动健将,那么(x)(P(x)^Q(x))表这个班上有一个学生既是高材生又是运动健将．而(x)P(x)^(x)Q(x)只是说这个班上有—个高材生而且有一个运动健将，但不要求高材生和运动健将是同一个学生．

显然推理式是成立的．其结论比前提明显地要求弱了．从而这推理式的逆是不成立的． 不难给出解释性的证明． 设解释I下有(x)(P(x)^Q(x))＝T。即有xoD使P(xo)^Q(xo)=T从而有P(xo)=T，Q(xo)=T。 也即(x)P(x)＝T，(x)Q(x)＝T从而有 (x)P(x)^(x)Q(x)＝T

(2)(x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x) 从语义上讨论．论域仍是某班的学生，为使(x)(P(x)→Q(x))=T.论域内学生分布只有两种可能，一是班上所有学生都是高材生又都是运动健将。一是班上有的学生不是高材生，但凡高材生必是运动健将．这两种情况下都有(x)P(x)→(x)Q(x)=T 然而这推理式的逆是不成立的，仅当班上有的高材生不是运动健将，而且又有的学生不是高材生时，有(x)P(x)→(x)Q(x)＝T．而(x)(P(x)→Q(x))＝F 解释性的证明．

设在一解释I下，有 (x)(P(x)→Q(x))＝T．从而对任一x D, P(x)→Q(x)=T.必能保证(x)p(x)＝T时有(x)Q(x)＝T．从而有 (x)P(x)→(x)Q(x)=T

(3)(x)(y)P(x，y)=>(y)(x)P(x，y) 这定理在{1，2}域上是成立的，已在4.5. 2节作了说明从语义上讨论，如论域为实数域上的区间[-1，1]，而P(x,y)表x·y=0.这时(x) (y)P(x，y)＝T．因为取x＝0，对所有的y都有x·y＝0．自然有(y)(x)P(x,y)=T,因对所有的y，均取x=0便有x·y=0成立。 这定理的逆也是不成立的，如取P(x，y)表x+y＝0，这时(y)(x)P(x，y)＝T，而 (x)(y)P(x，y)=F．

解释性的证明． 设一解释I下，有(x)(y)P(x，y)＝T，于是有x0D，使对一切的yD都有 P(x0，y)=T．从而对一切的yD，都有一个x(均选为x0)使P(x，y)=T，即(y)(x) P(x，y)＝T．

5.5 推理演算 命题逻辑中引入推理规则的推理演算，可推广到谓词逻辑，有关的推理规则(代入规则需补充说明)都可直接移入到谓词逻辑，除此之外还需介绍4条有关量词的消去和引入规则． 5．5．1 推理规则

(1)全称量词消去规则 (x)P(x)=>P(y)其中y是论域中一个体． 意指如果所有的xD都具有性质P，那么D中任一个体y必具有性质P．当P(x)中不再含有量词和其他变项时，这条规则明显成立． 而当允许P(x)中可出现量词和变项时，需限制y不在P(x)中约束出现，以避免发生错误． 如(x)P(x)＝(x)((z)(x<z))在实数上成立，P(y)＝(z)(y<z)但当y取为z，便有(z)(z<z)，这是矛盾式，这时，在P(x)中是约束出现了．

(2)全称量词引入规则 P(y)，(x)P(x)其中y是论域中任—个体． 意指如果任一个体y(自由变项)都具有性质P，那么所有个体x都具有性质P，仍需限制x不在P(y)中约束出现．如P(y)＝(z)(z>y)在实数域上成立， (x)P(x)＝(x)((z)(z>x))但当z取为x，这时x在P(y)中约束出现，(x)(x)(x>x)是不成立的，

(3)存在量词消去规则 (x)P(x)=>P(c)其中c是论域中的一个个体常项． 意指如果论域中存在有个体具有性质P，那么必有某个个体c具有性质P． 需限制(x)P(x)中没有自由个体出现．如实数域上(x)P(x)＝(x)(x>y)是成立的，y是自由个体，这时不能推导出c>y,还需限制P(x)中不含有c．如在实数域上(x)P(x)=(x)(c<x)是成立的，但c<c不能成立．

(4)存在量词引入规则 P(c)=>(x)P(x)其中c是论域中一个个体常项． 意指如果有个体常项c具有性质P，那么( x)P(x)必真． 需限制x不出现在P(c)中．如实数域上，P(0)＝( x)(x>0)成立，但( x)( x)(x> x)是不成立的．

这4条推理规则是基本的，对多个量词下的量词消去与引入规则的使用也已谈到．再明确说明一下． (x)(y)P(x，y)=>(y)P(x，y) 的右端，不允许写成(y)P(y，y)， 而(x)P(x，c)=>(y)(x)P(x，y) 的右端不允许写成(x)(x)P(x，x)。

(x)(y)P(x，y)=>(y)P(x，y)=>P(x，a) 但不允许再推演出(x)P(x，a)和(y)(x)P(x，y)．原因是(x)(y)P(x，y)成立时，所找到的y是依赖于x的，从而P(x，y)的成立是有条件的，不是对所有的x对同一个y都有P(x，y)成立，于是不能再推演出(x)P(x,y)．

5．5．2 使用推理规则的推理演算举例 和命题逻辑相比，在谓词逻辑里使用推理规则进行推理演算同样是方便的，然而在谓词逻辑里，真值表法不能使用，又不存在判明A→B是普遍有效的一般方法，从而使用推理规则的推理方法已是谓词逻辑的基本推理演算方法． 推理演算过程．首先是将以自然语句表示的推理问题引入谓词形式化，若不能直接使用基本的推理公式便消去量词，在无量词下使用规则和公式推理，最后再引入量词以求得结论．

例1 前提 (x)(P(x)→Q(x))，(x)(Q(x)→R(x)) 结论 (x)(P(x)→R(x)) 证明 (1)(x)(P(x)→Q(x)) 前提 (2)P(x)→Q(x) 全称量词消去 (3)(x)(Q(x)→R(x)) 前提 (4)Q(x)→R(x) 全称量词消去 (5)P(x)→R(x) (2)，(4)三段论 (6)(x)(P(x)→R(x)) 全称量词引入

例2 所有的人都是要死的，苏格拉底是人，所 以苏格拉底是要死的． 首先引入谓词形式化，令P(x)表x是人，Q(x)表x是要死的，于是问题可描述为 (x)(P(x)→Q(x))^P(苏格拉底)→Q(苏格拉底) 证明 (1)(x)(P(x)→Q(x)) 前提 (2)P(苏格拉底)→Q(苏格拉底) 全称量词消去 (3)P(苏格拉底) 前提 (4)Q(苏格拉底) (2)，(3)分离

例3 前提(x)P(x)→(x)((P(x)VQ(x))→R(x))，(x)P(x) 结论(x)(y)(R(x)^R(y)) 证明 (1)(x)P(x)→(x)((P(x)VQ(x))→R(x)) 前提 (2)(x)P(x) 前提 (3)(x)((P(x)VQ(x))→R(x)) (1)，(2)分离 (4)P(c) (2)存在量词消去 (5)P(c)VQ(c)→R(c) (3)全称量词消去 (6)P(c)VQ(c) (4) (7)R(c) (5)，(6)分离 (8)(x)R(x) (7)存在量词引入 (9)(y)R(y) (7)存在量词引入 (10)(x)R(x)^(y)R(y) (8)，(9) (11)(x)(y)(R(x)^R(y)) (10)置换

例4 分析下述推理的正确性 (1)(x)(y)(x>y) 前提 (2)(y)(z>y) 全称量词消去 (3)z>b 存在量词消去 (4)(z)(z>b) 全称量词引入 (5)b>b 全称量词消去 (6)(x)(x>x) 全称量词引入 推理(1)到(2)，应明确指出y是依赖于x的，即(2)中y和z有关．(2)到(3)，其中的b是依赖于z的．从而(3)到(4)是不成立的．又由于b是常项，(5)到(6)也是不允许的，因个体常项不能用全称量词量化．

例5 有的病人喜欢所有的医生，没有一个病人喜欢某一庸医， 所以没有医生是庸医． 先形式化．令P(x)表x是病人，Q(x)表x是庸医．D(x)表x是医生，L(x，y)表x喜欢y， 第一句话可描述为 (x)(P(x)^(y)(D(y)→L(x，y))) 第二句话可描述为 (x)(P(x)→(y)(Q(y)→﹁L(x，y))) 或写成 ﹁ (x)(P(x)^(y)(Q(y)^L(x，y))) 结论可描述为 (x)(D(x)→﹁Q(x)) ﹁ (x)(D(x)^Q(x))

证明 (1)(x)(P(x)^(y)(D(y)→L(x，y))) 前提 (2)P(c)^(y)(D(y)→L(c，y)) 存在量词消去 (3)(x)(P(x)→(y)(Q(y)→﹁L(x，y))) 前提 (4)P(c)→(y)(Q(y)→﹁L(c，y)) 全称量词消去 (5)P(c) (2) (6)(y)(D(y)→L(c，y)) (2) (7)D(y)→L(c,y) 全称量词消去 (8)(y)(Q(y)→﹁L(c,y)) (4)，(5)分离 (9)Q(y)→﹁L(c，y) 全称量词消去 (10)L(c，y)→﹁Q(y) (9)置换 (11)D(y)→ ﹁Q(y) (7)，(10)三段论 (12)(y)(D(y)→﹁Q(y)) 全称量词引入 (13)(x)(D(x)→﹁ Q(x)) (12)置换

5．6 谓词逻辑的归结推理法 归结方法可推广到谓词逻辑，困难在于出现了量词，变元．证明过程同命题逻辑，只不过每一步骤都要考虑到有变元，从而带来复杂性． 使用推理规则的推理演算过于灵活，技巧性强，而归结法较为机械，容易使用计算机来 实现。

5．6．1 归结证明过程 (1)为证明A→B是定理(A，B为谓词公式)，等价的是证明A^，B=G是矛盾式，这是归结法的出发点． 5．6．1 归结证明过程 (1)为证明A→B是定理(A，B为谓词公式)，等价的是证明A^，B=G是矛盾式，这是归结法的出发点． (2)建立子句集S， 如何消去G中的量词，特别是存在量词，是建立子句集S的关键． 办法是先将G化成等值的前束范式，进而将这前束形化成Skolem标准形(消去存在量词)，得仅含全称量词的公式G*，曾指出G与G*在不可满足的意义下是一致的，从而对G的不可满足性．可由G*的不可满足性来求得． 再将G*中的全称量词省略，G*母式(已合取范式化)中的合取词^以“，”表示，便得G的子句集S.而S与G是同时不可满足的，S中的变元视作有全称量词作用着．

(3)对S作归结， 设C1，C2是两个无共同变元的子句，L1，L2分别是C1，C2中的文字，如果L1和L2有合一置换，则 (C1 -{L1})U(C2-{L2}) 称作子句C1，C2的归结式． 如 C1=P(x)VQ(x) C2=﹁P(a)VR(y) P(x)与﹁P(a)，在合一置换{x／a}下将变元x换成a，便为互补对可作归结了，有归结式 R(C1，C2)=Q(a)VR(y) 对于句集S的任两子句作归结(如果可作归结)．并将归结式仍放入S中．重复这过程． (4)直至归结出空子句口，证明结束．

5．6．2 归结法证明举例 例1 (x)(P(x)→Q(x))^(x)(Q(x)→R(x))=>(x)(P(x)→R(x)) 5．6．2 归结法证明举例 例1 (x)(P(x)→Q(x))^(x)(Q(x)→R(x))=>(x)(P(x)→R(x)) 首先写出公式G G＝(x)(P(x)→Q(x))^(x)(Q(x)→R(x))^﹁ (x)(P(x)→R(x)) 为求G的子句集S，可分别对(x)(P(x)→Q(x))，(x)(Q(x)→R(x))，﹁ (x)(P(x)→R(x))作子句集，然后求并集来作为G的“子句集”(这个“子句集”不一定是S，但与S同时是不可满足的，而且较占来得简单，于是为方便可将这个“子句集”视作S)． (x)(P(x)→Q(x))的子句集为{﹁P(x)VQ(x)) (x)(Q(x)→R(x))的子句集为{﹁Q(x)VR(x)} ﹁ (Vx)(P(x)→R(x))＝(x) ﹁(﹁P(x)VR(x))＝(x)(P(x)^﹁R(x)) Skolem化，得子句集{P(a)，﹁R(a)} 于是G的子句集S＝{﹁P(x)VQ(x)，﹁Q(x)VR(x)，P(a)，﹁R(a)}

证明S是不可满足的，有归结过程： (1) ﹁P(x)VQ(x) (2) ﹁Q(x)VR(x) (3) P(a) (4) ﹁R(a) (5) Q(a) (1)(3)归结 (6) R(a) (2)(5)归结 (7) 口 (4)(6)归结

例2 A1＝(x)(P(x)^(y)(D(y)→L(x,y))) A2＝(x)(P(x)→(y)(Q(y)→﹁L(x，y))) B＝(x)(D(x)→﹁Q(x)) 求证A1^A2=>B． 证明 不难建立A1的子句集为{P(a)，﹁D(y)VL(a，y)}，A2的子句集为{﹁P(x)V﹁Q(y)V﹁L(x，y)}, ﹁B的子句集为{D(b)，Q(b)}，求并集得子句集S，进而建立归结过程：

(1) P(a) (2) ﹁D(y)VL(a，y) (3) ﹁P(x)V﹁Q(y)V﹁L(x，y) (4) D(b) (5) Q(b) (6) L(a，b) (2)(4)归结 (7) ﹁Q(y)V﹁L(a，y) (1)(3)归结 (8) ﹁L(a，b) (5)(7)归结 (9) 口 (6)(8)归结