?K (y) W(z) ?W(z)∨K(x))
第四步，用归结演绎推理进行证明
3.20 对子句集：
{P∨Q, Q∨R, R∨W, ?R∨?P, ?W∨?Q, ?Q∨?R } 用线性输入策略是否可证明该子句集的不可满足性？ 解：用线性输入策略不能证明子句集
{P∨Q, Q∨R, R∨W, ?R∨?P, ?W∨?Q, ?Q∨?R }
的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。
3.21 对线性输入策略和单文字子句策略分别给出一个反例，以说明它们是不完备的。
3.22 分别说明正向、逆向、双向与/或形演绎推理的基本思想。
3.23 设已知事实为
((P∨Q)∧R) ∨(S∧(T∨U)) F规则为
S→(X∧Y)∨Z
试用正向演绎推理推出所有可能的子目标。
解：先给出已知事实的与/或树，再利用F规则进行推理，其规则演绎系统如下图所示。 由该图可以直接写出所有可能的目标子句如下： P∨Q∨Ｔ∨Ｕ P∨Q∨Ｘ∨Ｚ P∨Q∨Y∨Ｚ
R∨T∨U R∨X∨Z R∨Y∨Z 所有子所有 目标 目标
?W(z)∨K(x)) W(z) K(z) W(z) NIL P Q R X Y Z T U 16 X Y X Y X∧Y S Z F 规 则 P Q R T S U 已 知 事 实
(P∨Q) T∨U (S∧(T∨U)) ((P∨Q)∧R) ((P∨Q)∧R) ∨(S∧(T∨U)) 3.24 设有如下一段知识：
“张、王和李都属于高山协会。该协会的每个成员不是滑雪运动员，就是登山运动员，其中不喜欢雨的运动员是登山运动员，不喜欢雪的运动员不是滑雪运动员。王不喜欢张所喜欢的一切东西，而喜欢张所不喜欢的一切东西。张喜欢雨和雪。”
试用谓词公式集合表示这段知识，这些谓词公式要适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题：
“高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？” 解：(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))
高山协会中不喜欢雪的运动员不是滑雪运动员
17
(?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)) (?y)(? L(Zhang, y)→L(Wang, y))
(5) 把已知事实、规则和目标化成推理所需要的形式
事实已经是文字的合取形式：
f1: A(Zhang)∧A(Wang)∧A(Li)
f2: L (Zhang , Rain)∧L(Zhang , Snow) 将规则转化为后件为单文字的形式：
r1: A(x)∧?S(x)→C(x)) r2: ?L(x, Rain)→C(x) r3: ?L(x, Snow)→? S(x) r4: L(Zhang, y)→? L(Wang ,y) r5: ? L(Zhang, y)→L(Wang , y)
将目标公式转换为与/或形式
? A(x)∨(C(x)∧? S(x))
(6) 进行逆向推理
逆向推理的关键是要能够推出L(Zhang , Rain)∧L(Zhang , Snow)，其逆向演绎过程如下图所示。
? A(x)∨(C(x)∧? S(x)) ? A(x) C(x) C(x)∧? S(x) 18 ? S(x)
第4章
4.5 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制： (1) 船太小，农夫每次只能带一样东西过河； (2) 如果没有农夫看管，则狼要吃羊，羊要吃菜。
请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。
题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。
(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。 解：第一步，定义问题的描述形式
用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。
第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。
由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态： S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0) S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0) S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0) S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)
其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。
第三步，定义操作，即用于状态变换的算符组F
由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下： L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。由于农夫必须在船上，故对农夫的表示省略。
R (i)表示农夫从右岸将第i样东西带到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。同样，对农夫的表示省略。
这样，所定义的算符组F可以有以下8种算符：
19
搜索策略部分参考答案
r2 ?L(x, Rain) {Wang/x, y/Rain} ?L(Wang, y) r4 L(Zhang, y) {Rain/y} L(Zhang, Rain) {Snow/y} r4 r3?L(x, Snow) {Wang /x, y/Snow} ?L(Wang, y) L(Zhang, y) L(Zhang, Snow) L (0)，L (1)，L (2)，L (3) R(0)，R(1)，R (2)，R (3)
第四步，根据上述定义的状态和操作进行求解。 该问题求解过程的状态空间图如下：
4.7 圆盘问题。设有大小不等的三个圆盘A、B、C套在一根轴上，每个盘上都标有数字1、2、3、4，并且每个圆盘都可以独立的绕轴做逆时针转动，每次转动90°，其初始状态S0和目标状态Sg如图4-31所示，请用广度优先搜索和深度优先搜索，求出从S0到Sg的路径。
(1,1,l,1) L(2) (0,1,0,1) R(0) (1,1,0,1) L(1) (0,0,0,1) R(2) (1,0,1,1) L(3)
(0,0,1,0) R(0)
(1,0,1,0) L(2) (0,0,0,0)
L(3) (0,1,0,0)
R(2) (1,1,1,0) L(2)
20