人工智能第4版部分课后答案

第２章 附加题

1. 请写出用一阶谓词逻辑表示法表示知识的步骤。

步骤：（1）定义谓词及个体，确定每个谓词及个体的确切含义；（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。

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

解：子句就是由一些文字组成的析取式。由子句构成的集合称为子句集。

步骤：（1）消去谓词公式中的蕴涵和双条件符号，以?A?B代替A?B，以(A?B)?(?A??B)替换A?B。 （2）减少不定符号的辖域，使不定符号最多只作用到一个谓词上。

（3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。 （4）消去存在量词。

（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。 （6）母式化为合取范式，建立起与其对应的子句集。

2-2 用谓词表示法求解修道士和野人问题。在河的北岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但要受到以下条件限制：

(1) 修道士和野人都会划船，但船一次只能装运两个人。

(2) 在任何岸边，野人数不能超过修道士，否则修道士会被野人吃掉。 假定野人愿意服从任何一种过河安排，请规划出一种确保修道士安全的过河方案。要求写出所用谓词的定义、功能及变量的个体域。

解：（1）定义谓词

先定义修道士和野人人数关系的谓词： G(x,y,S)： 在状态S下x大于y

GE(x,y,S)：在状态S下x大于或等于y

其中，x,y分别代表修道士人数和野人数，他们的个体域均为{0,1,2,3}。

再定义船所在岸的谓词和修道士不在该岸上的谓词： Boat(z,S)：状态S下船在z岸

EZ(x,S)： 状态S下x等于0，即修道士不在该岸上 其中，z的个体域是{L,R}，L表示左岸，R表示右岸。 再定义安全性谓词：

Safety(z,x,y,S)≡(G(x,0,S)∧GE(x,y,S))∨(EZ(x,S))

其中，z,x,y的含义同上。该谓词的含义是：状态S下，在z岸，保证修道士安全，当且仅当修道士不在该岸上，或者修道士在该岸上，但人数超过野人数。该谓词同时也描述了相应的状态。

再定义描述过河方案的谓词：

L-R(x, x1, y, y1,S)：x1个修道士和y1个野人渡船从河的左岸到河的右岸

条件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S) 动作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’) R-L (x, x1, y, y1,S)：x2个修道士和y2个野人渡船从河的左岸到河的右岸

条件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S) 动作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’)

(2) 过河方案

Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0)

L-R(3, 1, 3, 1,S0) L-R(3, 0, 3, 2,S0)

Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1)

Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S

1’)

R-L (2, 1, 2, 0,S1) R-L (3,0, 1, 1,S1’)

Safety(L,3,2,S2)∧Safety(R,0,1,S2)∧Boat(L,S2)

L-R(3, 0, 2, 2,S2)

Safety(L,3,0,S3)∧Safety(R,0,3,S3)∧Boat(R,S3)

R-L (3, 0, 0, 1,S3)

Safety(L,3,1,S4)∧Safety(R,0,2,S1)∧Boat(L,S4)

L-R(3, 2, 1, 0,S4)

Safety(L,1,1,S5)∧Safety(R,2,2,S5)∧Boat(R,S5)

R-L (1, 1, 1, 1,S5)

Safety(L,2,2,S6)∧Safety(R,1,1,S6)∧Boat(L,S6)

L-R(2, 2, 2, 0,S6)

Safety(L,0,2,S7)∧Safety(R,3,1,S7)∧Boat(R,S7)

R-L (0, 0, 2, 1,S7)

Safety(L,0,3,S8)∧Safety(R,3,0,S8)∧Boat(L,S8)

L-R(0, 0, 3, 2,S8)

Safety(L,0,1,S9)∧Safety(R,3,2,S9)∧Boat(R,S9)

R-L (0, 1, 1, 0,S9)

Safety(L,1,1,S10)∧Safety(R,2,2,S10)∧Boat(L,S10)

L-R(1, 1, 1, 1,S10)

Safety(L,0,0,S11)∧Safety(R,3,3,S11)∧Boat(R,S11)

习题解答：

2-3设有如下问题：

（1）有五个相互可直达且距离已知的城市A、B、C、D、E，如图所示； （2）某人从A地出发，去其它四个城市各参观一次后回到A; （3）找一条最短的旅行路线 请用产生式规则表示旅行过程。 解：①综合数据库（x）

(x)中x可以是一个字母，也可以是一个字符串。 ②初始状态（A）

③目标状态（Ax1x2x3x4A） ④规则集：

r1: IF L(S)=5 THEN GOTO(A) r2: IF L(S)<5 THEN GOTO(B) r3: IF L(S)<5 THEN GOTO(C) r4: IF L(S)<5 THEN GOTO(D) r5: IF L(S)<5 THEN GOTO(E)

其中L(S)为走过的城市数，GOTO(x)为走向城市x

⑤路线如下图所示:

起始 7

( AB ) 7

( A CB) 5 ( AC ) 6 ( A CD) 10

( A CDB)

8

( ACDE ) 10 ( ACDEB ) 7

9

( ACE ) ( A ) 10

( AD )

10

( AE ) ( ACDEBA)

目标

最短旅行路线为：A->C->D->E->B->A 总距离为5+6+8+10+7=36 2-6 把下列句子变换成子句形式： (1) (x)｛P(x)→P(x)｝

(2) xy(On(x,y)→Above(x,y))

(3) xyz(Above(x,y)∧Above(y,z)→Above(x,z)) (4) ～｛(x)｛P(x)→｛（y）［p(y)→p(f(x,y))］∧(y)［Q(x,y)→P(y)］｝｝｝ (ANY x) { P(x)?P(x) } (ANY x) {~P(x) OR P(x)} ~P(x) OR P(x) 最后子句为 ~P(x) OR P(x)

(2) (ANY x) (ANY y) { On(x,y)?Above(x,y) } (ANY x) (ANY y) { ~On(x,y) OR Above(x,y) } ~On(x,y) OR Above(x,y) 最后子句为

~On(x,y) OR Above(x,y)

(3) (ANY x) (ANY y) (ANY z) { Above(x,y) AND Above(y,z) ? Above(x,z) } (命题联结词之优先级如下:否定→合取→析取→蕴涵→等价)

(ANY x) (ANY y) (ANY z) { ~ [ Above(x,y) AND Above(y,z) ] OR Above (x,z) } ~ [ Above(x,y) AND Above(y,z) ] OR Above (x,z) 最后子句为

~[Above(x,y), Above(y,z)] OR Above(x,z)

(4) ~{ (ANY x) { P(x)? { (ANY y) [ p(y)?p(f(x,y)) ] AND (ANY y) [ Q(x,y) ? P(y) ] } } } ~ { (ANY x) { ~P(x) OR { (ANY y) [ ~p(y) OR p(f(x,y)) ] AND (ANY y) [ ~Q(x,y) OR P(y) ] } } }

(EXT x) { P(x) AND { (EXT x) [ p(y) AND ~p(f(x,y)) ] OR (EXT y) [ Q(x,y) AND ~P(y) ] } } (EXT x) { P(x) AND { (EXT w) [ p(y) AND ~p(f(w,y)) ] OR (EXT v) [ Q(x,v) AND ~P(v) ] } } P(A) AND { [ p(y) AND ~p(f(B,y)) ] OR [ Q(A,C) AND ~P(C) ] }

P(A) AND { [ p(y) AND ~p(f(B,y)) OR Q(A,C) ] AND [ p(y) AND ~p(f(B,y)) OR ~P(C) ] } P(A) AND { { p(y), ~p(f(B,y)) } OR Q(A,C) } AND { { p(y), ~p(f(B,y)) } OR ~P(C) } 最后子句为 P(A)

{ p(x), ~p(f(B,x)) } OR Q(A,C) { p(y), ~p(f(B,y)) } OR ~P(C)

2 － 7 用谓词演算公式表示下列英文句子 ( 多用而不是省用不同谓词和项。例如不要用单一的谓词字母来表示每个句子 ) 。

A computer system is intelligent if it can perform a task which,if performed by a human, requires intelligence.

2 －7 答：定义如下谓词： P(x,y) ： x performs y task （ x 完成 y 任务）； Q(y) ： y requires intelligence(y 需要智能 ) C(x) ： x is a computer system(x 是一个计算机系统 ) I(x) ： x is intelligent(x 是智能的 )

2 － 7答：定义如下谓词： P(x,y) ： x performs y task （ x 完成 y 任务）； Q(y) ： y requires intelligence(y 需要智能 ) C(x) ： x is a computer system(x 是一个计算机系统 ) I(x) ： x is intelligent(x 是智能的 )

2 － 8 把下列语句表示成语义网络描述： (1) All man are mortal.

(2) Every cloud has a silver liming.

(3) All branch managers of DEC participate in a profit-sharing plan. 2 － 8 答： （１）

（２）

（３）

2-9 以办公室框架为例： 办公室

名称：教务办 电话： 1234567

工作人员：工作人员 _1 、工作人员 _2 设备：电脑 2 台、复印机 3 台 工作人员 _1 姓名：张三

出生年月： 1965 年 9 月 岗位：办公室主任 职称：副教授 工作人员 _2 姓名：李四

出生年月： 1984 年 9 月 岗位：普通办公员 职称：助教

3-14 下列语句是一些几何定理，把这些语句表示为基于规则的几何证明系统的产生式规则： (1) 两个全等三角形的各对应角相等。 (2) 两个全等三角形的各对应边相等。 (3) 各对应边相等的三角形是全等三角形。 (4) 等腰三角形的两底角相等。 规则(1): IF 两个三角形全等 THEN 各对应角相等 规则(2): IF 两个三角形全等 THEN 各对应边相等

规则(3): IF 两个三角形各对应边相等 THEN 两三角形全等

规则(4): IF 它是等腰三角形 THEN 它的两底角相等 补充：

1 张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A说“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。 解：第一步：将5位侦察员的话表示成谓词公式，为此先定义谓词。 设谓词P(x)表示是作案者，所以根据题意： A: P(zhao) ∨ P(qian) B: P(qian) ∨ P(sun)

C: P(sun) ∨ P(li) D: ﹁P(zhao) ∨ ﹁P(sun) E: ﹁P(qian) ∨ ﹁P(li)

以上每个侦察员的话都是一个子句。

第二步：将待求解的问题表示成谓词。设y是盗窃犯，则问题的谓词公式为P(y)，将其否定并与ANSWER(y)做析取： ﹁P(y) ∨ ANSWER(y)

第三步：求前提条件及﹁P(y) ∨ ANSWER(y)的子句集，并将各子句列表如下： P(zhao) ∨ P(qian) P(qian) ∨ P(sun) P(sun) ∨ P(li)

﹁P(zhao) ∨ ﹁P(sun) ﹁P(qian) ∨ ﹁P(li) ﹁P(y) ∨ ANSWER(y)

第四步：应用归结原理进行推理。

P(qian) ∨ ﹁P(sun) (1)与(4)归结 P(zhao) ∨ ﹁P(li) (1)与(5)归结 P(qian) ∨ ﹁P(zhao) (2)与(4)归结 P(sun) ∨﹁P(li) (2)与(5)归结 ﹁P(zhao) ∨ P(li) (3)与(4)归结 P(sun) ∨﹁P(qian) (3)与(5)归结 P(qian) (2)与(7)归结 P(sun) (2)与(12)归结 ANSWER(qian) (6)与(13)归结，σ={qian/y} ANSWER(sun) (6)与(14)归结, σ={sun/y} 所以，本题的盗窃犯是两个人：钱和孙。

2 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？

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

设Father(x,y)表示x是y的父亲。 设Brother(x,y)表示x和y是兄弟。 将已知事实用谓词公式表示出来：

F1: 任何兄弟都有同一个父亲。

???∧Father(z,x)→Father(z,y)) ( x)( y)( z)( Brother(x,y)

F2: John和Peter是兄弟。 Brother(John, Peter)

F3: John的父亲是David。 Father(David, John) 将它们化成子句集，得

S1={﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y), Brother(John, Peter), Father(David, John)} 第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER做析取。 设Peter的父亲是u，则有：Father(u, Peter) 将其否定与ANSWER做析取，得 G: ﹁Father(u, Peter) ∨ ANSWER(u)

第三步：将上述公式G化为子句集S2，并将S1和S2合并到S。 S2={﹁Father(u, Peter) ∨ ANSWER(u)} S=S1∪S2

将S中各子句列出如下：

（1）﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y) （2）Brother(John, Peter) （3）Father(David, John)

（4）﹁Father(u, Peter) ∨ ANSWER(u) 第四步：应用归结原理进行归结。

（5）﹁Brother(John,y) ∨ Father(David,y) （1）与（3）归结，σ={ David/z, John/x}

（6）﹁Brother(John, Peter) ∨ ANSWER(David) （4）与（5）归结，σ={ David/u, Peter/y} （7）ANSWER(David) （2）与（6）归结

第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David,即Peter的父亲是David。

本文来源：https://www.bwwdw.com/article/b6kf.html