人工智能经典习题集

再用谓词把问题描述出来：

已知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))

对上述扩充的子句集，其归结推理过程如下：

?F(x,y)∨?F(y,z)∨GF(x,z) ?GF(v,u)

{x/v,z/u}

?F(x,y)∨?F(y,z) ?P(r)∨F(s,r)

{x/s,y/r} ?F(y,z)∨?P(y) ?P(r)∨F(s,r)

{y/s,z/r} ?P(y)∨?P(z

{y/z} P(u) ?P(y)

{y/u} NIL

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

3.19 设已知：

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

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

W(z) ?W(z)∨K(x))

K(z) W(z) NIL

第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种算符： L (0)，L (1)，L (2)，L (3) R(0)，R(1)，R (2)，R (3)

第四步，根据上述定义的状态和操作进行求解。 该问题求解过程的状态空间图如下：

(1,1,l,1)

L(2)

4.15 设有如图4-35所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：

(1) 计算各节点的倒推值；

(2) 利用α-β剪枝技术剪去不必要的分枝。

S0

A B

C D E F H I J G K L M N

0 5 -3 3 3 6 6 -2 3 5 4 -3 0 (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)

6 8 9 -3 图4.35 习题4.15的博弈树

解：各节点的倒推值和剪枝情况如下图所示：

≥4 ≤0 A ≤4 B S0

≥0 ≤0 G C ≤-3 H ≤3 ≥3 I D J ≤4 ≥4 E L ≤6 ≥6 M F K ≤-3 N 0 5 -3 3 3 3 6 6 -2 3 5 4 -3 0 6 8 9 -3 习题4.15的倒推值和剪枝情况

5.19 设有论域

U={u1, u2, u3, u4, u5}

并设F、G是U上的两个模糊集，且有 F=0.9/u1+0.7/u2+0.5/u3+0.3/u4 G=0.6/u3+0.8/u4+1/u5 请分别计算 F∩G，F∪G，﹁F。

解：F∩G=(0.9∧0)/ u1+(0.7∧0)/ u2+(0.5∧0.6)/u3+(0.3∧0.8)/u4+(0∧1)/u5 =0/ u1+0/ u2+0.5/u3+0.3/u4+0/u5 =0.5/u3+0.3/u4

F∪G=(0.9∨0)/ u1+(0.7∨0)/ u2+(0.5∨0.6)/u3+(0.3∨0.8)/u4+(0∨1)/u5

=0.9/ u1+0.7/ u2+0.6/u3+0.8/u4+1/u5

﹁F=(1-0.9)/ u1+(1-0.7)/ u2+(1-0.5)/u3+(1-0.3)/u4+(1-0)/u5

=0.1/ u1+0.3/ u2+0.5/u3+0.7/u4+1/u5

5.21设有如下两个模糊关系：

?0.30.70.2?R1??100.4?????00.51???0.20.8?R2??0.60.4?????0.90.1??请写出R1与R2的合成R1οR2。

解：R(1,1)=(0.3∧0.2)∨(0.7∧0.6)∨(0.2∧0.9)= 0.2∨0.6∨0.2=0.6