1 判断下列公式是否为可合一，若可合一，则求出其最一般合一。
(1) P(a, b), P(x, y) (2) P(f(x), b), P(y, z) (3) P(f(x), y), P(y, f(b)) (4) P(f(y), y, x), P(x, f(a), f(b))
解：(1) 可合一，其最一般和一为：σ={a/x, b/y}。(2) 可合一，其最一般和一为：σ={y/f(x), b/z}。 (3) 可合一，其最一般和一为：σ={ f(b)/y, b/x}。(4) 不可合一。 2 把下列谓词公式化成子句集：
(1) (2) (3) (4)
(?x)(?y)(P(x, y)∧Q(x, y)) (?x)(?y)(P(x, y)→Q(x, y))
(?x)(?y)(P(x, y)∨(Q(x, y)→R(x, y))) (?x) (?y) (?z)(P(x, y)→Q(x, y)∨R(x, z))
解：(1) 由于(?x)(?y)(P(x, y)∧Q(x, y))已经是Skolem标准型，且P(x, y)∧Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 { P(x, y), Q(x, y)} 再进行变元换名得子句集： S={ P(x, y), Q(u, v)}
(2) 对谓词公式(?x)(?y)(P(x, y)→Q(x, y))，先消去连接词“→”得：
(?x)(?y)(?P(x, y)∨Q(x, y))
此公式已为Skolem标准型。 再消去全称量词得子句集： 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)))此公式已为前束范式。
再消去存在量词，即用Skolem函数f(x)替换y得：(?x)(P(x, f(x))∨?Q(x, f(x))∨R(x, f(x))) 此公式已为Skolem标准型。最后消去全称量词得子句集： 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)) 再消去存在量词，即用Skolem函数f(x)替换y得：
(?x) (?y) (?P(x, y)∨Q(x, y)∨R(x, f(x,y)))
此公式已为Skolem标准型。 最后消去全称量词得子句集：S={?P(x, y)∨Q(x, y)∨R(x, f(x,y))} 3 对下列各题分别证明G是否为F1,F2,…,Fn的逻辑结论：
(1) F: (?x)(?y)(P(x, y) G: (?y)(?x)(P(x, y) (2) F: (?x)(P(x)∧(Q(a)∨Q(b))) G: (?x) (P(x)∧Q(x)) (3) F: (?x)(?y)(P(f(x))∧(Q(f(y))) G: P(f(a))∧P(y)∧Q(y)
(4) F1: (?x)(P(x)→(?y)(Q(y)→?L(x.y))) F2: (?x) (P(x)∧(?y)(R(y)→L(x.y)))
G: (?x)(R(x)→?Q(x))
(5) F1: (?x)(P(x)→(Q(x)∧R(x))) F2: (?x) (P(x)∧S(x)) G: (?x) (S(x)∧R(x))
解：(1) 先将F和?G化成子句集： S={P(a,b), ?P(x,b)} 再对S进行归结
{a/x}
所以，G是F的逻辑结论
(2) 先将F和?G化成子句集
P(a,b) ?P(x,b) NIL 由F得：S1={P(x)，(Q(a)∨Q(b))} 由于?G为：? (?x) (P(x)∧Q(x))，即
(?x) (? P(x)∨? Q(x))，
可得： S2={? P(x)∨? Q(x)}
因此，扩充的子句集为：
S={ P(x)，(Q(a)∨Q(b))，? P(x)∨? Q(x)} 再对S进行归结：
所以，G是F的逻辑结论 同理可求得(3)、(4)和(5)，其求解过程略。 5如果x是y的父亲，y是z的父亲，则x是z的祖父； 2每个人都有一个父亲。 使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。 解：先定义谓词
F(x,y)：x是y的父亲 GF(x,z)：x是z的祖父 P(x)：x是一个人 再用谓词把问题描述出来：
已知F1：(?x) (?y) (?z)( F(x,y)∧F(y,z))→GF(x,z)) F2：(?y)(P(x)→F(x,y)) 求证结论G：(?u) (?v)( P(u)→GF(v,u)) 然后再将F1，F2和?G化成子句集： ① ?F(x,y)∨?F(y,z)∨GF(x,z)
② ?P(r)∨F(s,r) ③ P(u) ④ ?GF(v,u))
对上述扩充的子句集，其归结推理过程如下：
{x/v,z/u}
{x/s,y/r}
{y/s,z/r}
{y/z} {y/u} Q(a)∨Q(b) {a/b} Q(a) {a/x} ? P(x)∨? ? P(a) P(x) {a/x} NIL ?F(x,y)∨?F(y,z)∨GF(x,z) ?GF(v,u) ?F(x,y)∨?F(y,z) ?P(r)∨F(s,r) ?F(y,z)∨?P(y) ?P(r)∨F(s,r) ?P(y)∨?P(z?P(y) P(u) NIL 由于导出了空子句，故结论得证。
6 假设张被盗，公安局派出5个人去调查。案情分析时，贞察员A说：“赵与钱中至少有一个人作案”，贞察员B说：“钱与孙中至少有一个人作案”，贞察员C说：“孙与李中至少有一个人作案”，贞察员D说：“赵与孙中至少有一个人与此案无关”，贞察员E说：“钱与李中至少有一个人与此案无关”。如果这5个侦察员的话都是可信的，使用归结演绎推理求出谁是盗窃犯。
解：(1) 先定义谓词和常量
设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李 (2) 将已知事实用谓词公式表示出来 赵与钱中至少有一个人作案：C(Z)∨C(Q) 钱与孙中至少有一个人作案：C(Q)∨C(S) 孙与李中至少有一个人作案：C(S)∨C(L)
赵与孙中至少有一个人与此案无关：? (C (Z)∧C(S))，即 ?C (Z) ∨?C(S) 钱与李中至少有一个人与此案无关：? (C (Q)∧C(L))，即 ?C (Q) ∨?C(L) (3) 将所要求的问题用谓词公式表示出来，并与其否定取析取。 设作案者为u，则要求的结论是C(u)。将其与其否)取析取，得：
? C(u) ∨C(u)
(4) 对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：
{Q/u}
{S/u}
因此，孙也是盗窃犯。 7 设有子句集：
{P(x)∨Q(a, b), P(a)∨?Q(a, b),
C(Z)∨C(Q) ?C (Z) ∨?C(S) C(Q)∨?C(S) C(Q)∨C(S) C(Q) ?C(u)∨C(uC(Q) 因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：
C(S)∨C(L) ?C (Q) ∨?C(L) C(S)∨?C(Q) C(Q)∨C(S) C(S) ?C(u)∨C(uC(S) ?Q(a, f(a)), ?P(x)∨Q(x, b)}
分别用各种归结策略求出其归结式。
解：支持集策略不可用，原因是没有指明哪个子句是由目标公式的否定化简来的。 删除策略不可用，原因是子句集中没有没有重言式和具有包孕关系的子句。 单文字子句策略的归结过程如下：
{b/f(a)}
用线性输入策略（同时满足祖先过滤策略）的归结过程如下：
{a/x}
{a/x}
8 设已知： P(x)∨Q(a, b) ?Q(a, f(a)) {b/f(a)} P(a) ?P(x)∨Q(x, b) Q(a, b) {a/x} ?Q(a, f(a)) Q(a, b) P(x)∨Q(a, b) P(a)∨?Q(a, b) P(a) ?P(x)∨Q(x, b) Q(a,b) ?Q(a, f(a)) {b/f(a)} NIL (1) 能阅读的人是识字的；2海豚不识字；3有些海豚是很聪明的。
请用归结演绎推理证明：有些很聪明的人并不识字。
解：第一步，先定义谓词， 设R(x)表示x是能阅读的； K(y)表示y是识字的； W(z) 表示z是很聪明的；
第二步，将已知事实和目标用谓词公式表示出来
能阅读的人是识字的：(?x)(R(x))→K(x)) 海豚不识字：(?y)(?K (y)) 有些海豚是很聪明的：(?z) W(z)
有些很聪明的人并不识字：(?x)( W(z)∧?K(x))
第三步，将上述已知事实和目标的否定化成子句集： ?R(x))∨K(x) ?K (y) W(z) ?W(z)∨K(x)) 第四步，用归结演绎推理进行证明
9 对子句集：
{P∨Q, Q∨R, R∨W,
?W(z)∨K(x)) W(z) K(z) W(z) NIL ?R∨?P, ?W∨?Q, ?Q∨?R }
?R∨?P, ?W∨?Q, ?Q∨?R }
用线性输入策略是否可证明该子句集的不可满足性？
解：用线性输入策略不能证明子句集 {P∨Q, Q∨R, R∨W,
10 设有如下一段知识：
“张、王和李都属于高山协会。该协会的每个成员不是滑雪运动员，就是登山运动员，其中不喜欢雨的运动员是登山运动员，不喜欢雪的运动员不是滑雪运动员。王不喜欢张所喜欢的一切东西，而喜欢张所不喜欢的一切东西。张喜欢雨和雪。”试用谓词公式集合表示这段知识，这些谓词公式要适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题：“高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？”
解：(1) 先定义谓词
A(x) 表示x是高山协会会员 S(x) 表示x是滑雪运动员 C(x) 表示x是登山运动员 L(x,y) 表示x 喜欢y (2) 将问题用谓词表示出来
“张、王和李都属于高山协会 A(Zhang)∧A(Wang)∧A(Li)
高山协会的每个成员不是滑雪运动员，就是登山运动员 (?x)(A(x)∧?S(x)→C(x)) 高山协会中不喜欢雨的运动员是登山运动员 (?x)(?L(x, Rain)→C(x)) 高山协会中不喜欢雪的运动员不是滑雪运动员 (?x)(?L(x, Snow)→? S(x)) 王不喜欢张所喜欢的一切东西 (?y)( L(Zhang, y)→? L(Wang ,y)) 王喜欢张所不喜欢的一切东西 (?y)(? L(Zhang, y)→L(Wang, y))
张喜欢雨和雪 L(Zhang , Rain)∧L(Zhang , Snow) (3) 将问题要求的答案用谓词表示出来
高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？ (?x)( A(x)→C(x)∧? S(x))
(4) 为了进行推理，把问题划分为已知事实和规则两大部分。假设，划分如下：
已知事实：
A(Zhang)∧A(Wang)∧A(Li) L(Zhang , Rain)∧L(Zhang , Snow) 规则：
(?x)(A(x)∧?S(x)→C(x)) (?x)(?L(x, Rain)→C(x)) (?x)(?L(x, Snow)→? S(x)) (?y)( L(Zhang, y)→? L(Wang ,y))
的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。