人工智能教程习题及答案第3章习题参考解答

第三章 确定性推理方法 习题参考解答

3.1 练习题

3.1 什么是命题？请写出 3个真值为 T 及真值为 F 的命题。

3.2 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？ 3.3 谓词逻辑和命题逻辑的关系如何？有何异同？

3.4 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。

3.5 什么是谓词公式？什么是谓词公式的解释？设 D= {1,2} ，试给出谓词公式 （ x）（（P（x,y） Q（x,y）） 的所有解释，并且对每一种解释指出该谓词公式的真值。

3.6 对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的

辖域。 （1） ( x)(P(x, y) ( y)(Q(x, y) R(x, y))) （2） ( z)( y)(P(z, y) Q(z, x)) R(u, v)

（3）

( x)(~ P( x, f (x )) ( z)(Q(x,z) ~ R(x,z)))

（4） ( z)(( y)(( t)(P(z, t) Q(y, t)) R(z, y))

（5） ( z)( y)(P(z, y) ( z)(( y)(P(z, y) Q(z, y) ( z)Q(z, y))))

3.7 什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含？ 3.8 什么是置换？什么是合一？什么是最一般的合一？

3.9

判断以下公式对是否可合一；若可合一，则求出最一般的合一：

（1） P(a,b) ， P(x, y) （2） P(f(z),b) ， P(y, x) （3） P(f(x), y) ， P(y, f(a)) （4） P(f(y), y,x) ， P(x, f(a), f(b)) （5） P(x, y) ，

P(y, x)

3.10 什么是范式？请写出前束型范式与 SKOLEM 范式的形式。 3.11

什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。

3.12 谓词公式与它的子句集等值吗？在什么情况下它们才会等价？

54

y）

3.13 把下列谓词公式分别化为相应的子句集：

(1) ( z)( y)(P(z, y) Q(z, y)) (2) ( x)( y)(P(x, y) Q(x, y)) (3) ( x)( y)(P(x, y) (Q(x, y) R(x, y))) (4) ( x)( y)( z)(P(x, y) Q(x, y) R(x, z))

(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)))

3.14 判断下列子句集中哪些是不可满足的：

(1) S {~ P Q,~ Q,P,~ P} (2) S {P Q,~ P Q,P ~ Q,~ P ~ Q} (3) S {P(y) Q(y), ~ P(f(x)) R(a)}

(4) S {~ P(x) Q(x), ~ P(y) R(y), P(a),S(a),~ S(z) ~ R(z)} (5) S {~ P(x) ~ Q(y) ~ L(x, y), P(a), ~ R(z) L(a, z), R(b), Q(b)} (6) S {~ P(x) Q(f(x), a), ~ P(h(y)) Q(f(h(y)), a) ~ P(z)}

(7)

S {P(x) Q(x) R(x),~ P(y) R(y),~Q(a),~ R(b)}

(8)

S {P(x) Q(x),~ Q(y) R(y), ~ P(z) Q(z),~ R(u)}

3.15 为什么要引入 Herbrand 理论？什么是 H 域？如何求子句集的 H 域？ 3.16 什么是原子集？如何求子句集的原子集？

3.17 什么是 H 域解释？如何用域 D 上的一个解释 I 构造 H 域上的解释 I *呢？ 3.18 假设子句集 S＝ {P(z) ∨Q(z),R(f(t))} ，S 中不出现个体常量符号。 设个体域 D＝{1,2}

原子集的定义：

H＝ {a,f(a),f(f(a)),

⋯}

A＝ {P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),

⋯}

如果设 I 是 D 上的解释，并作如下的设定

I ： f(1)

f(2) P(1) P(2) Q(1) Q(2) R(1) R(2) 2

2

T

F

F

T

F

T

请构造 H 域上的一个解释 I*与 I 相对应，且使 S|I* =T。

55

H 域和由

3.19 引入 Robinson 的归结原理有何意义？其基本思想是什么？

56

3.20 请写出应用归结原理进行定理证明的步骤。

3.21 对下列各题分别证明 G 是否为 F1，F2，⋯，Fn 的逻辑结论。 (1) F1:( x)( y)P(x, y)

G:( y)( x)P(x, y)

(Q(a) Q(b))) Q(x))

(2) F1 :( x)(P(x)

G :( x)(P(x)

(3) F1 :( x)( y)(P(f(x)) Q(f(b)))

G : P(f(a)) P(y) Q(y)

(4) F1:( x)(P(x)

( y)(Q(y) ~ L(x,y))) ( y)(R(y) L(x,y))) ~ Q(x))

(Q(x) R(x))) S(x)) R(x))

~ B(z) ( y)(D(z, y) C(y))) A(z) ( y)(D(z, y) E(y))) ~ B(z)) C(z))

F2:( x)(P(x) G:( x)(R(x)

(5) F1:( x)(P(x)

F2:( x)(P(x) G : ( x)(S(x) (6) Fl:( z)(A(z)

F2:( z)(E(z) F3:( z)(E(x) G:( z)(E(z)

3.22 证明：

( y)(Q(y)

(B(y) C(y))) ( y)(Q(y) D(y))

( y)(D (y) C(y))

3.23

某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下想法：

1) 如果录取张三而不录取李四，则一定录取王五。 2) 如果录取李四，则一定录取王五。 3) 三人中至少要录取一人。

求证：王五一定会被单位录取。

3.24 每个储蓄钱的人就是为了获得利息。求证：对某个人来说，如果不能获得利息，则他就不会储 蓄

钱。

3.25 请写出利用归结原理求解问题答案的步骤。 3.26 应用归结原理求解下列问题：

设张三、 李四和王五三人中有人从不说真话， 也有人从不说假话。 某人向这三人分别提出同一个问题： 谁是说假话者？张三答： “李四和王五都是说假话者” ；李四答：“张三和王五都是说假话者” ；王五答：“张 三和李四中至少有一个说假话者” 。求谁是说假话者，谁是说真话者？

57

3.27 已知樊臻的老师是张先生，樊臻与李伟是同班同学。如果 x与 y是同班同学，则 x的老师也是 y 的

老师。请问李伟的老师是谁？

3.28 什么是完备的归结控制策略？有哪些归结控制策略是完备的？

3.29 设已知：

（1）能阅读的人是识字的。 （2）海豚不识字。 （3）有些海豚是很聪明的。

用输入归结策略证明：有些很聪明的人并不识字。

3.30 用输入归结策略是否可证明下列子句集的不可满足性？

S={P ∨Q,Q∨ R,R∨ W,～ R∨～ P,～ W∨～ Q,～Q∨～ R}

3.2 习题参考解答

3.1 答

（略： 答 ）（略3.2 ： ）

答（略3.3 ： ）

答（略3.4 ： ）

3.5

解:

在谓词公式 （ x）（ y）（P（x,y） Q（x,y）） 中没有包括个体常量和函数，所以， 可以直接为谓

词指派真值。设：

P(1,1)=T， Q(1,1) =T,

P(1,2)=F， Q(1,2) =F,

P(2,1)=T， Q(2,1)=T ，

P(2,2)=F Q(2,2)=F

在这种解释下，对某一个 x（x=1 或 x=2）对所有的 y（即 y=1 或 y=2）都不能使 P（x,y） 的真值 为 T，所以，在此解释下， P（x,y）的真值为 F。同理， Q（x,y） 的真值也为 F。根据谓词逻辑真 值表可知：在该解释下，上述谓词公式的真值为 T。

上述谓词公式在 D={1,2} 上共有 256 种解释，这里不再一一列出，读者可自己列出其中的几

58

个，并求出其真值。

3.6 解：

(1) P(x,y)，Q(x,y)和 R(x,y)中的 x 以及 Q(x,y) ， R(x,y)中的 y 是约束变元。 P(x,y)中的 y 是 自由变

元。量词 x 的辖域使整个公式，量词 y 的辖域是( Q(x,y) R(x,y) )。

(2) z 和 y 是约束变元。 x, u, v 是自由变元。 z 和 y 辖域都是 P(z,y) Q(z,x) 。

(3) x和 z均是约束变元。 没有自由变元。 x 的辖域是整个公式， z的辖域是 Q(x,z) ~R(x,z) 。 (4) z 、y 和 t 均是约束变元。没有自由变元。 z 和 y 的辖域是整个公式， t 的辖域是 P(z,t)

Q(y,t)。

(5) 本小题比较复杂，表面上只涉及两个变元 z 和 y，实际上公式中后面的两个 z 和一个 y 都

可看成是另外的变量，因此，可作变元替换将公式变换为：

( z)( y)(P(z, y) ( z')(( y')(P(z' , y' ) Q(z',y') ( z'')Q(z'',y'))))

公式中的变元就成为 z、y、z'、y'、z'五'个变元。 z 和 y 的辖域是整个公式， z'和 y'的辖 域是

P(z', y' ) Q(z' , y' ) ( z' ' )Q(z' ' , y' ) ，而 z'为'Q(z'',。y ')

3.7 答：(略) 3.8 答：(略) 3.9 解：

(1) (2) (3) (4) (5)

P(a,b)与 P(x,y) 是可合一的。σ ={a/x,b/y} P(f(z),b) 与 P(x,y) 是可合一的。σ ={f(z)/x,b/y}

P(f(x),y) 与 P(y,f(a)) 是可合一的。根据最一般合一求取算法，可得σ P(f(y),y,x) 与 P(x,f(a),f(b)) 是不可合一的。 P(x,y) 与 P(y,x) 是可合一的。σ ={y/x} 或σ ={x/y}

={f(a)/y,a/x}

3.10 答：

范式就是标准型。谓词演算中， 一般有两种范式， 一种叫 前束形范式 ，另一种叫 斯克林

59

(Skolem)范式 。一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且 它的辖域一直延伸到公式之末，同时公式中不出现连接词→及 ， 这种形式的公式称作前 束形范式。它的一般形式是

(Q1x1)(Q 2x2) ⋯ (Qnxn)M(x 1,x2, ⋯ ,xn)

其中， Qi(i=1,2, ⋯ n)是存在量词或全称量词，而母式 M(x 1,x2, ⋯ ,xn)不再含有量词。

从前束形范式中消去全部存在量词所得到的公式称为 Skolem 标准型，它的一般形式是

( x1)( x2) ⋯( xn)M(x 1,x2, ⋯ ,xn)

3.11 答：

子句就是由一些文字组成的析取式。而所谓文字是指原子或原子的否定。不含有任何 连接词的谓词公式叫做原子或原子公式。由子句构成的集合称为子句集。

求谓词公式 G 的子句集的步骤如下：

(a)

消去谓词公式 G中的蕴涵(→)和双条件符号(

)，以～ A ∨B 代替 A→B，以

(A∧B)∨(～A∧～ B)替换 A B。

(b) (c) (d)

减少否定符号(～)的辖域，使否定符号“～”最多只作用到一个谓词上。

重新命名变元名， 使所有的变元的名字均不同， 并且自由变元及约束变元亦不同。 消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域 内，

此时， 只要用一个新的个体常量替换该存在量词约束的变元， 就可以消去存在量词；另 一种情况是，存在量词位于一个或多个全称量词的辖域内，例如，

( x1)( x2)⋯( xn)( y)P(x1,x2, ⋯ ,xn,y)

此时，变元 y 实际受前面的变元 x1，x2，⋯，xn的约束， 需要用 Skolem 函数 f(x1,x2, ⋯ ,xn) 替换 y 即可将存在量词 y 消去，得到：

( x1)( x2)⋯( xn)P(x1,x2, ⋯,xn, f(x1,x2, ⋯ ,xn))

(e) 把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整 个部

分。

60

(f) 母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的 有限

集组成的合取。

(g) 消去全称量词。

(h) 对变元进行更名，是不同子句中的变元不同名。 (i)

消去合取符号∧，将各子句写成子居积合的形式。

3.12 答：(略) 3.13 解：

61

1) 因为 ( z)( y)(P(z,y) Q(z,y))已经是一个 Skolem 标准型， P(z,y) Q(z,y)已是合取范 式，以逗号代

替 ，得子句集： S＝{ P(z,y) ，Q(z,y) }

2)

首先将谓词公式 ( x)( y)(P(x, y) Q(x, y))化为 Skolem标准型：

( x)( y)(~ P(x, y) Q(x, y))

消去全称量词，并将母式化为子句集

S＝{～ P(x,y)

Q(x,y) }

(Q(x, y)

R(x, y))) 化为 Skolem 标准型：

3)首先将谓词公式 ( x)( y)(P(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)))

第三步：消去全称量词，并将母式化为子句集

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))化为 Skolem 标准型： 第一步：消去 号

( x)( y)( z)(~ P(x,y) Q(x, y) R(x, z)) 第二步：消去存在量词，用 Skolem 函数 f(x,y) 代替 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)))

化为 Skolem 标准型：

第一步：消去存在量词 x,y，以常量 a,b 分别代之

( z)( u)( v)( w)(P(a, b, z,u,v, w) (Q(a,b,z,u,v,w) ~ R(a,z,w)))

第二步：消去存在量词 u，由于 u 在全称量词 z 的辖域内，令 Skolem 函数 u=f(z)

( z)( v)( w)(P(a,b,z,f(z),v,w) (Q(a,b,z,f(z),v,w) ~ R(a,z,w)))

再消去存在量词 w ，由于 w 在全称量词 z 和 v 的辖域内，令 Skolem 函数 w=g(z,v)

( z)( v)(P(a,b,z,f(z), v,g(z, v)) (Q(a,b,z,f(z),v,g(z,v)) ~ R(a,z,g(z,v))))

第三步：消去全称量词，并将母式化为合取范式，再化为子句集

62

S＝{ P(a,b,z,f(z),v,g(z,v))， Q(a,b,z,f(z),v,g(z,v)) ~ R(a,z,g(z,v)) } 3.14 解

(1) 依照归结推理过程，对子句集 S {~P Q,~Q,P,~P} 进行归结推理

1) 2) 3)

～ P Q ～Q

P

4) ~P

5) NIL 3),4) 归结

所以，该子句集是不可满足的。同理，可以推知第( 也是不可满足的，因为它们都可以归结出空子句。

3.15 答：

2)、( 4)、( 5)、( 8)小题的子句集

引入 Herbrand 理论的目的是为了简化对谓词公式不可满足性的证明。对于一个谓词公 式来说，要证明它的不可满足性是困难的，故考虑它的子句集的不可满足性。然而，对子句 集的不可满足性的判定仍然是困难的， 因为要判断子句集的不可满足性就要对子句集中的每 一个子句逐个进行判定。由于个体变元域 D 的任意性以及解释个数的无限性，这实际上是 一项难以完成的工作。 能否针对某一个具体的谓词公式， 找到一个比较简单的特殊域， 只要 使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢？ Herbrand 理论就构造了这样的一个域， 称为 Herbrand 域( H 域)。只要对 H 域上的所有解释 进行判定，即可得知谓词公式是否是不可满足的。

H 域的定义中就包含了子句集 H 域的求取方法：设谓词公式 G 的子句集为 S ，则按下 述方

法构造的个体变元域 H 称为公式 G 或子句集 S 的 Herbrand 域，简称 H 域。

(a) 令 H0是 S中所出现的常量的集合。 若 S中没有常量出现， 就任取一个常量 a D， 规定 H

0={a}

。

(b) 令 Hi+1=Hi∪{S 中所有的形如 f(t 1, ⋯ ,nt)的元素 }

63

其中 f(t 1, ⋯ ,nt)是出现于 G中的任一函数符号， 而t1，⋯，tn是Hi中的元素。 i=0 ，1，2，

⋯ 。

3.16 答：

下列集合称为子句集 S 的原子集：

A＝｛所有形如 P(t1, t2, ⋯ ,nt)的元素｝ 其中， P(t1, t2, ⋯ ,nt)是出现在 S中的任一谓词符

号，而 t1，t2，⋯，tn则是 S的 H 域上的任意 元素。该定义就给出了子句集的原子集的求法。

3.17 答：

如果子句集 S的原子集为 A，则对 A 中各元素的真假值的一个具体设定都是 解释。

用域 D 上的一个解释 I 构造 H 域上的解释 I* 的方法如下：

(1) 求子句集 S的 H 域和原子集 A

S的一个 H

(2) 根据 D 域上的解释 I，对 H 域中的每个元素设定相应的值。 如果 H 域中有常量符号，

可按 D 中的元素给 a 设定某一值。

(3) 依据 H 中各元素的值与解释 I 的规定，确定原子集 A 中各元素的取值。

这样，原子集 A 中的各个元素都得到了一个取值，它就是与 D 上的解释 I 相对应的 H 域上的解释 I* 。

3.18 解 :

已知个体域 D＝｛ 1,2｝，I 是 D 上的解释，并作如下的设定

f(1) 2

f(2) 2

P(1) T

P(2) F

Q(1) F

Q(2) T

R(1) F

R(2) T

将以上各值代入 S，有 S|I=T。现在要构造 H 域上的一个解释 I*与 I 相对应，且使 S|I* =T。 依据 D 域上的解释 I 之规定，对 H 域中的每个元素设定相应的值。在 H 中的常量符号 有

a，f(a)，f(f(a)) ， ⋯.。这时，由于 a在解释 I 中并未给出规定，所以我们要按 D 中的元素 给 a设

定值， a可以设定为 1，也可以设定为 2(因为 1，2 都是 D 的元素)。

若 a 设定成 1，则依照解释 I， H 中的其他元素的值即确定如下：

f(a) → f(1) → 2 f(f(a)) → f(2) → 2

f(f(f(a))) → f(2) → 2

再依据 H 中各元素的值与解释 I 的规定，确定原子集 A 中各元素的取值：

P(a) → P(1) → T Q(a) → Q(1) → F R(a) → R(1) → F P(f(a)) →P(2) → F Q(f(a)) → Q(2) → T R(f(a)) → R(2) → T

于是，便得到与 D 域上解释 I 相对应的 H 域上的解释 I*1 ：

I1={P(a), ～ Q(a), ～ R(a), ～ P(f(a)),Q(f(a)),R(f(a)), ⋯}

*

同理，若将 H 中的元素 a设成 2，我们可以得到与 I 相对应的另一个 H解释 I*2 ：

I2={ ～ P(a),Q(a),R(a), ～ P(f(a)),Q(f(a)),R(f(a)), ⋯}

*

可以验证 S| I 1=T， S| I 2=T 。解释 I*1 、 I *2便是所求的与 D 域上解释 I 相对应的 H 域之解释。

*

*

3.19 答：(略) 3.20 答：

设要被证明的定理可用谓词公式表示为形式 行定理证明的步骤如下：

A 1∧A2∧⋯∧An→B，则应用归结原理进

(1) 首先否定结论 B，并将否定后的公式～ B 与前提公式集组成如下形式的谓词公式：

G= A1∧A2∧⋯

∧An∧～ B

(2) 求谓词公式 G 的子句集 S。

(3) 应用归结原理，证明子句集 S的不可满足性，从而证明谓词公式

G 的不可满足性。

这就说明对结论 B 的否定是错误的，推断出定理的成立。

3.21 解：

65

(1) F:( x)( y)P(x, y)

1

G:( y)( x)P(x, y)

首先将 F1 和～G 化为子句集

1) P(a,b)

2) ~P(x,b) 然后利用归结原理进行归结 3)

NIL 1)与 2)归结， σ ={a/x}

所以 G 是 F1 的逻辑结论。

(2) 首先将 F1和～G 化为子句集

F1:( x)(P(x) (Q(a) Q(b))) ,由于 F1本身就是 Skelom 标准型，所以有 S1＝{ P(x),Q(a) Q(b) } ～G＝

( x)(~ P(x) ~ Q(x)) 所以， S2＝{ ~P(x) ~Q(x) }

下面进行归结

1) P(x)

2) 3) 4) 5) 6)

Q(a) Q(b)

~ P(x) ~ Q(x)

~Q(x) Q(b) NIL

1)，3)归结 2)，4)归结 4)，5)归结

σ ={a/x} σ ={b/x}

所以 G 是 F1 的逻辑结论。 其余各题的证明留给读者自己练习。

3.22 证明： 第一步：先对结论否定并与前提合并得谓词公式 G

G=( y)(Q(y)→(B(y)∧C(y)))∧( y)(Q(y) ∧D(y)) ∧～ ( y)(D(y) ∧C(y)) 第二步：将公式 G 化

为子句集，可将 G 看作三项的合取，对每一项分别求子句集 G1：( y)(Q(y) →(B(y) ∧C(y)))

=( y)(～Q(y)∨(B(y) ∧C(y)))

= ( y)(( ～ Q(y) ∨ B(y)) ∧(～Q(y)∨C(y))) 所以， S1={( ～Q(y)∨B(y)), ～ Q(y)

∨C(y)} 。

G2：( y)(Q(y) ∧D(y))

66

所以， S2={Q(a),D(a)} 。

～B：～( y)(D(y) ∧C(y))

=( y)(～D(y) ∨～ C(y))

所以， S～B={ ～D(y) ∨～ C(y)} 。 从而得公式 G 的子句集：

S= S1∪S2∪S～B={(～Q(y)∨B(y)),～Q(y)∨C(y),Q(a),D(a), ～ D(y) ∨～ C(y)} 第三步：使用归

结原理，对子句集 S 进行归结。

(1) ～ Q(y) ∨B(y) (2) ～ Q(y) ∨C(y) (3) Q(a) (4) D(a)

(5) ～D(y) ∨～ C(y) (6) C(a) (7) ～ C(a) (8) NIL

(2)与(3)归结 σ ={a/y} (4)与(5)归结 σ ={a/y} (6)与(7)归结

由此得出子句集 S 是不可满足的，因而公式 G 也是不可满足的，从而命题得证。

3.23 证明：

第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。 (1)定义谓词和常量：

谓词 Matr(x) 表示 x 被录取。

Z 表示张三， L 表示李四， W 表示王五。 (2)

将前提及要证的问题表示成谓词公式：

a) Matr(Z) ∧~ Matr(L) → Matr(W) b) Matr(L) → Matr(W)

c) Matr(Z) ∨Matr(L) ∨ Matr(W) 把要求证的问题否定，并用谓词公式表示出来：

d) ～

Matr(W)

67

第二步：将上述公式化成子句集。

1)

～ Matr(Z) ∨ Matr(L) ∨ Matr(W) ～ Matr(L) ∨ Matr(W)

Matr(Z) ∨ Matr(L) ∨ Matr(W)

～

2)

3) 4)

Matr(W)

第三步：利用归结原理对上面的子句集中的子句进行归结。

5) Matr(L) ∨ Matr(W) 6) Matr(W) 7) NIL

1)与 3)归结 2)与 5)归结

4)与 6)归结

所以，王五一定会被录取。

3.24 证法一： 第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出

来。 定义谓词：

设： Save(x)：表示 x 储蓄钱；

Interest(x) ：表示 x 获得利息。

将前提表示成谓词公式：

( x )( Save( x ) Interest( x )) 把要求证

的问题用谓词公式表示出来：

( y)(~ Interest(y) ~ Save(y)) 第二步：将前提和要求证的问题之否定化成子句集。

求前提子句集：

( x )( Save(x ) Interest(x )) ( x)(~ Save( x ) Interest(x))

前提的子句集： S1＝{ ~ Save(x ) Interest(x) } 求结论之否定子句集：

68

~ ( y)(~ Interest ( y) ~ Save(y)) ~ ( y)(Interest(y) ~ Save( y )) ( y)(~ Interest ( y) Save( y ))

结论之否定子句集： S2＝{～ Interest(y) ， Save(y)}

第三步：利用归结原理对上面的子句集中的子句进行归结

(1) ~ Save( x ) Interest ( x ) (2) ~ Interest(y ) (3) Save(y) (4) ～ Save(y) (5) NIL

(1)，(2)归结 σ＝{ x/y }

(3) ，(4)归结

证毕。

证法二：

第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。 定义谓词：

设： Save(x,y)：表示 x 储蓄 y；

Money(y) ：表示 y 是钱； Interest(y) ：表示 y 是利息； Obtain(x,y) ：表示 x 获得 y 。

将前提表示成谓词公式：

( x)(( y)( Money ( y) Save( x , y)) ( u)( Interest( u) Obtain (x, u))) 把要求证的问题用

谓词公式表示出来：

( x)(~ ( u)(Interest(u) Obtain ( x, u)) ~ ( y)(Money(y) Save(x,y))) 第二步：将前提和要

求证的问题之否定化成子句集。

求前提子句集：

69

( x)(( y)(Money(y) Save( x, y)) ( u)(Interest(u) Obtain(x,u))) ( x)(~ ( y)(Money (y) Save(x,y)) ( u )(Interest( u ) Obtain ( x , u))) ( x)(( y)(~ Money (y) ~ Save(x,y)) ( u)(Interest(u) Obtain(x,u)))

设 skolem 函数为 u=f(x) ，则：

70

前提的子句集： S1＝{ ~ Money (y) ~ Save(x,y) Interest(f(x)) ，

~ Money (y) ~ Save(x, y) Obtain (x ,f (x)) }

求结论之否定子句集：

~ ( x)(~ ( u)(Interest(u) Obtain ( x , u)) ~ ( y )( Money ( y) Save(x,y))) 成析取式。谓词

ANSWER 是一个专为求解问题而设置的谓词，其变量必须与问

题公式的变 量完全一致。

~ ( x)(( u)(Interest(u) ( x)(( u)(~ Interest(u)

Obtain (x, u)) ~ ( y)(Money(y) ~ Obtain ( x, u)) ( y)( Money ( y )

Save( x , y ))) Save(x,y)))

设 skolem 函数为 y=g（x） ，则上式变为：

( x)( u)((~ Interest (u ) ~ Obtain(x,u)) (Money(g(x))

结论之否定子句集：

Save(x,g(x))))

S2＝{ ~ Interest(u) ~ Obtain(x,u),Money(g(x)),Save(x,g(x))}

第三步：利用归结原理对上面的子句集中的子句进行归结

(1) (2) (3) (4) (5) (6) (7)

~ Money (y ) ~ Save(x, y) Interest(f (x))

~ Money (y ) ~ Save(x, y) Obtain(x,f (x))

~ Interest (u ) ~ Obtain ( x , u )

Money ( g(x ))

Save(x,g(x))

~ Money (y) ~ Save(x, y) ~ Obtain (x ,f (x)) ~ Money (y ) ~ Save(x , y)

（1），（3）归

σ＝{ f(x)/u } 结

（2），（6）归结

（5），（ 7）归

σ＝{ g(x)/y } 结

（4），（8）

(8) ~ Money (g(x)) (9) NIL

归结

证毕。

3.25 答：

利用归结原理求取问题答案的步骤如下：

（1） 把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为 S1。

（2） 把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词 ANSWER 构

71

(3) 把问题公式与谓词 ANSWER 构成的析取式化为子句集，并把该子句集与 S1 合并构

成子句集 S。

(4) 对子句集 S 应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变 ANSWER 中的变元。

(5) 如果得到归结式 ANSWER ，则问题的答案即在 ANSWER 谓词中。

3.26 解： 第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。

(1) 定义谓词和常量：

设 P(x) 表示 x 说真话。 Z 表示张三， L 表示李四， W 表示王五。

(2) 将已知事实用谓词公式表示出来。

若张三说的是真话，则有 P(Z)→ ～ P(L) ∧ ～P(W) 若张三说的是假话，则有 ～P(Z)→ P(L)

∨P(W) 对李四和王五说的话做同样的处理，可得：

P(L)→ ～P(Z)∧～P(W) ～ P(L)→ P(Z)∨ P(W) P(W)→ ～P(Z)∨～P(L)

～ P(W)→ P(Z) ∧P(L)

(3) 将它们化成子句集得 S： 1) ～P(Z) ∨ ～ P(L) 2) ～ P(Z)∨ ～ P(W) 3) P(Z)∨P(L) ∨P(W) 4) ～ P(L)∨ ～ P(W) 5) ～P(W)∨～P(Z) ∨～P(L)

6) P(W) ∨P(Z)

7) P(W) ∨P(L)

第二步：把问题用谓词公式表示出来，并将其否定与谓词 ANSWER 作析取。 设 u 是说真话者，则有： P(u) 。将其否定与 ANSWER 作析取，得：

G：～ P(u)∨ ANSWER(u)

72

将上述公式 G 化为如下的子句，并将其合并到 S。

8)

～ P(u)∨ANSWER(u)}

第三步：应用归结原理对上述子句集进行归结

9)

～ P(Z)∨P(W)

P(W)

1)与 7) 归结

10) 11)

6)与 9) 归结

ANSWER(W) 8)与 10) 归结 σ ={W/u}

第四步：得到的归结式 ANSWER(W) ，答案即在其中， u=W ，所以，求得王五是说真 话者。

除此之外， 无论对上述子句集如何进行归结， 都推不出 ANSWER(Z) 和 ANSWER(L) 来， 说明张三和李四不是说真话者。 其实可以证明张三和李四是说假话者。 证明的方法是设张三 或李四是说假话者，则有： ～P(Z)或～P(L) 作为要证明的结论，将它的否定之子句并入前面 的子句集 1)－ 7)，并进行归结推理，推出空子句，从而证明假设的正确性，即张三和李四 是说假话者。

3.27 解：

第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。 ( 1) 定义谓词和常量：

Teacher(x,y) 表示 x 是 y 的老师。 Classmate(x,y) 表示 x 和 y 同班同学

Fz 表示樊臻， Lw 表示李伟， Zm 表示张先生。

( 2) 将已知事实用谓词公式表示出来。

樊臻的老师是张先生： Teacher(Zm, Fz) 樊臻与李伟是同班同学： Classmate(Fz,Lw)

如果 x 与 y 是同班同学，则 x 的老师也是 y 的老师：

( x)( y)( z)(Classmate(x, y) Teacher(z,x) Teacher(z,y))

73

3) 1) 2) 3)

将它们化成子句集得 S：

Teacher(Zm, Fz) Classmate(Fz, Lw)

～

Classmate(x,y)

∨～ Teacher(z, x)∨ Teacher(z, y) 第二步：把问题用谓词公式表示出

来，并将其否定与谓词 ANSWER 作析取。 设李伟的老师是 u，则有： Teacher(u, Lw) 。将其否定与 ANSWER 作析取，并求子句且 把所得子句并入上述子句集：

4) 5) 6) 7)

～Teacher(u, Lw)∨ANSWER(u) 第三步：应用归结原理对上述子句集进行归结 ～ Classmate(Fz, y)∨ Teacher(Zm, y)

～

1)与 3) 归结 σ ={Fz/x,Zm/z} 4)与 5) 归结 σ ={Lw/y,Zm/u} 2)与 6) 归结

Classmate(Fz,Lw)

∨ ANSWER(Zm)

ANSWER(Zm)

第四步： 得到的归结式 ANSWER(W) ，答案即在其中， u=Zm，即李伟的老师是张先生。

3.28 答：(略)

3.29 证明 第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。

( 1) 定义谓词和常量：

Read(x) 表示 x 是能阅读的； Know(y) 表示 y 是识字的； Wise(z) 表示 z 是很聪明的；

用 r 表示人类，用 h 表示海豚 .

( 2) 将已知事实用谓词公式表示出来。 能阅读的人是识字的： ( r)(Read(r) Know (r)) 海豚不识字： ( h)(~ Know (h)) 有些海豚是很聪明的： ( h)(Wise(h)) ( 3) 将要证明的目标转化为谓词 第二步：将它们化成子句集

1) ～ Read(r)∨Know(r) 2) ~Know(h) 3) Wise(a)

有些很聪明的人并不识字：

( r)(Wise(r) ~ Know(r))

4) ~Wise(r) ∨ Know(r)

74

第三步：对以上子句集进行归结

5) 6) NIL

Know(a) 3)与 4) 归结 σ ={a/r} 2)与 5) 归结 σ ={a/h}

从而命题得证。

3.30 解

利用输入归结策略不能证明子句集

S={P∨Q,Q∨R,R∨W,～R∨～ P,～W∨～Q,～Q∨～R}

的不可满足性。 因为按照输入归结策略的要求， 每次参加归结推理的两个子句中， 必须至少 有一个子句是初始子句集中的子句。 另外，要特别注意的是， 在进行归结时，不能同时消去 两个互补文字对，因为消去两个互补文字对所得到的结果，不是两个亲本子句的逻辑推论。 例如，在本题中，子句 Q∨R 和～ Q∨～ R 不能进行归结，因为它们归结时将消去两个文字 对。所以，根据这些要求，将不能从该子句集中归结出空子句，也就是说，不能证明该子句 集的不可满足性。

75