解：设E1，E2两个谓词公式，其最一般合一置换算法： （1） 令W=｛E1，E2｝。
（2） 令k=0，Wk=W，?k=?；?是空置换，它表示不作置换。
（3） 如果Wk只有一个表达式，则算法停止，?k就是所要求的mgu。 （4） 找出Wk的不一致集Dk。
（5） 若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk 中出现，则置： ?k+1=?k?{ tk/xk} Wk+1=Wk?{ tk/xk} k=k+1 然后转（3）。 （6） 算法终止，W的mgu不存在。
11. 判断以下公式对是否可合一；若可合一，则求出最一般的合一。
（1）P(a,b)， P(x,y) 解：依据算法：
(1) 令W={P(a,b)，P(x,y)}。 (2) 令?0=?，W0=W。 (3) W0未合一。
(4) 从左到右找不一致集，得D0={a，x}。 (5) 取x0=x，t0=a，则
?1=?0?{ t0/ x0}=?0?{a/ x}={a/ x} W1= W0?1={P(a,b)，P(a,y)}
(3’) W1未合一。
(4’) 从左到右找不一致集，得D1={b，y}。
(5’) 取x1=y，t1=b，则
?2=?1?{ t1/ x1}=?1?{b/ y}={a/ x}?{b/ y}={a/x，b/y} W2= W1?2={P(a,b)，P(a,b)}
(3’’) W2已合一，因为其中包含相同的表达式，这时?2={a/x，b/y}即为所求的mgu。
（2）P(f(z)),b)， P(y,x) 解：依据算法：
(1) 令W={P(f(z),b)，P(y,x)}。 (2) 令?0=?，W0=W。 (3) W0未合一。
(4) 从左到右找不一致集，得D0={f(z)，y}。 (5) 取x0=y，t0=f(z)，则
?1=?0?{ t0/ x0}=?0?{f(z)/ y}={f(z)/y} W1= W0?1={P(f(z),b)，P(f(z),x)}
(3’) W1未合一。
(4’) 从左到右找不一致集，得D1={b，x}。
(5’) 取x1=x，t1=b，则
?2=?1?{ t1/ x1}=?1?{b/ x}={ f(z)/ y}?{ b/ x}={f(z)/y，b/x} W2= W1?2={P(f(z),b)，P(f(z),b)}
(3’’) W2已合一，因为其中包含相同的表达式，这时?2={f(z)/y，b/x}即为所求的mgu。
（3）P(f(x),y)， P(y,f(a)) 解：依据算法：
(1) 令W={P(f(x),y)，P(y,f(a))}。 (2) 令?0=?，W0=W。 (3) W0未合一。
(4) 从左到右找不一致集，得D0={f(x)，y}。
9
(5) 取x0=y，t0=f(x)，则
?1=?0?{ t0/ x0}=?0?{f(x)/ y}={f(x)/y} W1= W0?1={P(f(x),f(x))，P(f(x),f(a))}
(3’) W1未合一。
(4’) 从左到右找不一致集，得D1={y，f(a)}。
(5’) 取x1=y，t1=f(a)，则
?2=?1?{ t1/ x1}=?1?{f(a)/ y}={ f(x)/ y}?{ f(a)/ y}={f(x)/y} W2= W1?2={P(f(x),f(x))，P(f(x),f(a))}
(6) 算法终止，W的mgu不存在。 （4）P(f(y),y,x)， P(x,f(a),f(b)) 解：依据算法：
(1) 令W={P(f(y),y,x)，P(x,f(a),f(b))}。 (2) 令?0=?，W0=W。 (3) W0未合一。
(4) 从左到右找不一致集，得D0={f(y)，x}。 (5) 取x0=x，t0=f(y)，则
?1=?0?{ t0/ x0}=?0?{f(y)/ x}={f(y)/x} W1= W0?1={P(f(y),y,f(y))，P(f(y),f(a),f(b))}
(3’) W1未合一。
(4’) 从左到右找不一致集，得D1={y，f(a)}。
(5’) 取x1=y，t1=f(a)，则
?2=?1?{ t1/ x1}=?1?{f(a)/ y}={ f(y)/ x}?{ f(a)/ y}={f(f(a))/x,f(a)/y} W2= W1?2={P(f(f(a)),f(a),f(f(a)))，P(f(f(a)),f(a),f(b))}
(6) 算法终止，W的mgu不存在。 （5）P(x,y)， P(y,x) 解：依据算法：
(1) 令W={P(x,y)，P(y,x)}。 (2) 令?0=?，W0=W。 (3) W0未合一。
(4) 从左到右找不一致集，得D0={x，y}。 (5) 取x0=x，t0=y，则
?1=?0?{ t0/ x0}=?0?{y/ x}={y/ x} W1= W0?1={P(y,y)，P(y,y)}
(3’) W2已合一，因为其中包含相同的表达式，这时?1={y/x}即为所求的mgu。 12. 什么是范式？请写出前束范式与SKOLEM范式的形式。
定义：量词按照一定的规则出现的谓词公式。
前束范式形式：(?x) (?y)(?z)(P(x)?F(y,z)?Q(y,z)) SKOLEM范式形式：(?x1) (?x2)? (?xn)M(x1，x2，?，xn） 13. 什么是子句？什么是子句集？请写出谓词公式子句集的步骤。
解：子句就是由一些文字组成的析取式。由子句构成的集合称为子句集。
步骤：（1）消去谓词公式中的蕴涵和双条件符号，以?A?B代替A?B，以(A?B)?(?A??B)替换A?B。 （2）减少不定符号的辖域，使不定符号最多只作用到一个谓词上。
（3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。 （4）消去存在量词。
（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。
10
（6）母式化为合取范式，建立起与其对应的子句集。 14. 谓词公式与它的子句集等值吗？在什么情况下它们才会等价？
解：不等值。在不可满足的意义下是等价的。 15. 把下列谓词公式分别化为相应的子句集：
（1）(?z)(?y)(P(z,y)?Q(z,y)) 解：所求子句集为S={P(z,y)，(z,y)} （2）(?x)(?y)(P(x,y)?Q(x,y)) 解：原式?(?x)(?y)(?P(x,y)?Q(x,y)) 所求子句集为S={?P(x,y)?Q(x,y)} （3）(?x)(?y)(P(x,y)?(Q(x,y)?R(x,y))) 解：原式?(?x)(?y)(P(x,y)?(?Q(x,y)?R(x,y))) ?(?x)(P(x,f(x))?(?Q(x,f(x))?R(x,f(x)))) 所求子句集为S={ P(x,f(x))?(?Q(x,f(x))?R(x,f(x)))} （4）(?x) (?y) (?z)(P(x,y)?Q(x,y)?R(x,z)) 解：原式?(?x) (?y) (?z)(?P(x,y)?Q(x,y)?R(x,z)) ?(?x) (?y) (?P(x,y)?Q(x,y)?R(x,f(x,y))) 所求子句集为S={?P(x,y)?Q(x,y)?R(x,f(x,y))}
（5）(?x) (?y) (?z) (?u) (?v) (?w)(P(x,y,z,u,v,w)?(Q(x,y,z,u,v,w)??R(x,z,w)))
解：原式?(?x) (?y) (?z) (?u) (?v) (P(x,y,z,u,v,f(z,v))?(Q(x,y,z,u,v,f(z,v))??R(x,z,f(z,v)))) ?(?x) (?y) (?z)(?v) (P(x,y,z,f(z),v,f(z,v))?(Q(x,y,z,f(z),v,f(z,v))??R(x,z,f(z,v)))) ?(?z)(?v) (P(a,b,z,f(z),v,f(z,v))?(Q(a,b,z,f(z),v,f(z,v))??R(a,b,f(z,v)))) 所求子句集为S={ P(a,b,z,f(z),v,f(z,v))，Q(a,b,z,f(z),v,f(z,v))??R(a,b,f(z,v))} 16. 判断下列子句集中哪些是不可满足的：
（1）S={?P?Q, ?Q,P, ?P } 解：使用归结推理：
(1) ?P?Q (2) ?Q (3)P (4) ?P (3)与(4)归结得到NIL，因此S是不可满足的。 （2）S={P?Q, ?P?Q,P??Q, ?P??Q } 解：使用归结推理：
(1) P?Q (2) ?P?Q (3) P??Q (4) ?P??Q (1)与(2)归结得 (5)Q (3)与(5)归结得 (6)P (4)与(6)归结得 (7) ?Q
(5)与(7)归结得NIL，因此S是不可满足的。 （3）S={P(y)?Q(y), ?P(f(x)) ?R(a) } 解：使用归结推理：
设C1= P(y)?Q(y)，C2=?P(f(x)) ?R(a)，选L1= P(y)，L2=?P(f(x))，则
L1与L2的mgu是?={f(x)/y}，C1 与C2的二元归结式C12=Q(f(x))?R(a)，因此S是可满足的。 （4）S={?P(x)?Q(x), ?P(y)?R(y),P(a), S(a), ?S(z)??R(z) } 解：使用归结推理：
(1) ?P(x)?Q(x) (2) ?P(y)?R(y) (3) P(a) (4) S(a) (5) ?S(z)??R(z) (2)与(3)归结得到 (6)R(a) (4)与(5)归结得到 (7) ?R(a)
(6)与(7)归结得到NIL，因此S是不可满足的。
（5）S={?P(x)? ?Q(y) ? ?L(x,y), P(a), ?R(z) ? L(a,z) ,R(b),Q(b) }
11
解：使用归结推理：
(1) ?P(x)? ?Q(y) ? ?L(x,y) (2) P(a) (3) ?R(z) ? L(a,z) (4) R(b) (5) Q(b) (1)与(2)归结得到 (6) ?Q(y) ? ?L(a,y) (5)与(6)归结得到 (7) ?L(a,b) (3)与(4)归结得到 (8) L(a,b)
(7)与(8)归结得到NIL，因此S是不可满足的。
（6）S={?P(x)?Q(f(x),a), ?P(h(y))?Q(f(h(y)),a) ??P(z) } 解：使用归结推理：
令C1= ?P(x)?Q(f(x),a)，C2= ?P(h(y))?Q(f(h(y)),a) ??P(z) 则 C2内部的mgu是?={h(y)/z}，合一后C2’=?P(h(y))?Q(f(h(y)),a) 选L1=?P(x)，L2=?P(h(y)) 则 L1与L2的mgu是?={h(y)/x}，
C1 与C2’的二元归结式C12=?P(h(y))?Q(f(h(y)),a)，因此S是可满足的。 （7）S={P(x)? Q(x) ? R(x), ?P(y) ? R(y) , ?Q(a), ?R(b) } 解：使用归结推理：
(1) P(x)? Q(x) ? R(x) (2) ?P(y) ? R(y) (3) ?Q(a) (4) ?R(b) (1)与(3)归结得到 (5) P(a) ? R(a) (2)与(4)归结得到 (6) ?P(b) (5)与(6)归结得到 (7) R(b)
(4)与(7)归结得到NIL，因此S是不可满足的。 （8）S={P(x)?Q(x), ?Q(y)?R(y), ?P(z)?Q(z) , ?R(u)} 解：使用归结推理：
(1) P(x)?Q(x) (2) ?Q(y)?R(y) (3) ?P(z)?Q(z) (4) ?R(u) (2)与(4)归结得到 (5) ?Q(u) (1)与(5)归结得到 (6) P(u) (3)与(6)归结得到 (7)Q(u)
(5)与(7)归结得到NIL，因此S是不可满足的。
21. 引入Robinson的归结原理有何意义？什么是归结推理？什么是归结式？请写出它的推理规则。
解：Robinson归结原理是一种证明子句集不可满足性，从而实现定理证明的方法，是对自动推理的重大突破，使机器定理
证明变为现实。
设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，则从C1和C2中可以分别消去L1
和L2，并将二子句中余下的部分做析取构成一个新的子句C12，这一过程称为归结，所得到的子句C12称为C1和C2的归结式。
推理规则：消去互补对。
22. 请写出应用归结原理进行定理证明的步骤。
解：设要被证明的定理可用谓词公式表示如下的形式： A1? A2? ?? An?B
（1）首先否定结论B，并将否定后的公式?B与前提公式集组成如下形式的谓词公式： G=A1? A2? ?? An??B （2）求谓词公式G的子句集S。
（3）应用归结原理，证明子句集S的不可满足性，从而证明谓词公式G的不可满足
性。这就说明对结论B的否定是错误的，推断出定理的成立。 23. 对下列各题分别证明G是否为F1，F2，?，Fn的逻辑结论。
（1）F1：(?x)(?y)P(x,y) G：(?y)(?x)P(x,y) 解：首先将F1和?G化为子句集：
12
