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

第章 附加题1. 请写出用一阶谓词逻辑表示法表示知识的步骤。步骤：（1）定义谓词及个体，确定每个谓词及个体的确切含义；（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。1. 什么是子句？什么是子句集？请写出谓词公式子句集的步骤。解：子句就是由一些文字组成的析取式。由子句构成的集合称为子句集。步骤：（1）消去谓词公式中的蕴涵和双条件符号，以AB代替AB，以(AB)(AB)替换AB。（2）减少不定符号的辖域，使不定符号最多只作用到一个谓词上。（3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。（4）消去存在量词。（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。（6）母式化为合取范式，建立起与其对应的子句集。2-2 用谓词表示法求解修道士和野人问题。在河的北岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但要受到以下条件限制：(1) 修道士和野人都会划船，但船一次只能装运两个人。(2) 在任何岸边，野人数不能超过修道士，否则修道士会被野人吃掉。假定野人愿意服从任何一种过河安排，请规划出一种确保修道士安全的过河方案。要求写出所用谓词的定义、功能及变量的个体域。解：（1）定义谓词先定义修道士和野人人数关系的谓词：G(x,y,S)： 在状态S下x大于yGE(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,S1)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)C-D-E-B-A总距离为5+6+8+10+7=362-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/yANSWER(sun) (6)与(14)归结, =sun/y所以，本题的盗窃犯是两个人：钱和孙。2 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？解：第一步：将已知条件用谓词公式表示出来，并化成子句集。那么，要先定义谓词。定义谓词：设Father(x,y)表示x是y的父亲。设Brother(x,y)表示x和y是兄弟。将已知事实用谓词公式表示出来：F1: 任何兄弟都有同一个父亲。( x)( y)( z)( Brother(x,y)Father(z,x)Father(z,y)F2: John和Peter是兄弟。Brother(John, Peter)F3: John的父亲是David。Father(David, J