张仰森 - 人工智能原理及其应用（第二版）习题答案(3)

(2) 不可满足，其归结过程为：

(3) 不是不可满足的，原因是不能由它导出空子句。 (4) 不可满足，其归结过程略 (5) 不是不可满足的，原因是不能由它导出空子句。 (6) 不可满足，其归结过程略 (1) (2) (3) (4)

F: (?x)(?y)(P(x, y) G: (?y)(?x)(P(x, y) F: (?x)(P(x)∧(Q(a)∨Q(b))) G: (?x) (P(x)∧Q(x))

F: (?x)(?y)(P(f(x))∧(Q(f(y))) G: P(f(a))∧P(y)∧Q(y)

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化成子句集 由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进行归结：

P∨Q Q ?P∨Q P∨?Q ?Q ?P∨?Q NIL 3.14 对下列各题分别证明G是否为F1,F2,…,Fn的逻辑结论：

P(a,b) ?P(x,b) NIL Q(a)∨Q(b) {a/b} Q(a) ? P(x)∨? Q(x) 11

{a/x}

所以，G是F的逻辑结论 同理可求得(3)、(4)和(5)，其求解过程略。 3.15 设已知：

(1) 如果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}

? P(a) P(x) {a/x} NIL ?F(x,y)∨?F(y,z)∨GF(x,?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(?P(y12 P(u) NI {y/u}

由于导出了空子句，故结论得证。

3.16 假设张被盗，公安局派出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}

13 C(Z)∨C(Q) ?C (Z) ∨?C(S) C(Q)∨?C(S) C(Q)∨C(S) C(Q) ?C(u)∨C(u) C(Q) 因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：

C(S)∨C(L) ?C (Q) ∨?C(L) C(S)∨?C(Q) C(Q)∨C(S) C(S) ?C(u)∨C(u) C(S) {S/u}

因此，孙也是盗窃犯。

3.18 设有子句集：

{P(x)∨Q(a, b), P(a)∨?Q(a, b), 分别用各种归结策略求出其归结式。

解：支持集策略不可用，原因是没有指明哪个子句是由目标公式的否定化简来的。 删除策略不可用，原因是子句集中没有没有重言式和具有包孕关系的子句。 单文字子句策略的归结过程如下：

{a/x}

{b/f(a)}

{a/x}

{a/x}

{b/f(a)} 3.19 设已知： (1) 能阅读的人是识字的； (2) 海豚不识字； (3) 有些海豚是很聪明的。

请用归结演绎推理证明：有些很聪明的人并不识字。

解：第一步，先定义谓词， 设R(x)表示x是能阅读的；

14

C(S) ?Q(a, f(a)), ?P(x)∨Q(x, b)}

P(x)∨Q(a, b) ?Q(a, f(a)) {b/f(a)} P(a) ?P(x)∨Q(x, b) Q(a, b) ?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)) NIL 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))

第四步，用归结演绎推理进行证明

3.20 对子句集：

{P∨Q, Q∨R, R∨W,

?W(z)∨K(x)) W(z) K(z) W(z) NIL ?R∨?P, ?W∨?Q, ?Q∨?R }

用线性输入策略是否可证明该子句集的不可满足性？ 解：用线性输入策略不能证明子句集

{P∨Q, Q∨R, R∨W,

3.21 对线性输入策略和单文字子句策略分别给出一个反例，以说明它们是不完备的。

3.22 分别说明正向、逆向、双向与/或形演绎推理的基本思想。

3.23 设已知事实为

((P∨Q)∧R) ∨(S∧(T∨U)) F规则为

S→(X∧Y)∨Z

试用正向演绎推理推出所有可能的子目标。

解：先给出已知事实的与/或树，再利用F规则进行推理，其规则演绎系统如下图所示。 由该图可以直接写出所有可能的目标子句如下： P∨Q∨Ｔ∨Ｕ

15

?R∨?P, ?W∨?Q, ?Q∨?R }

的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。