人工智能经典试题及答案

1、PAGE 268PAGE 88 知识表示方法部分参考答案 2.8 设有如如下语句，请请用相应的谓谓词公式分别别把他们表示示出来：s(1) 有的人人喜欢梅花，有有的人喜欢菊菊花，有的人人既喜欢梅花花又喜欢菊花花 。解：定义谓词ddP(x)：x是是人L(x,y)：x喜欢y其中，y的个体体域是梅花花，菊花。将知识用谓词表表示为：(x )(P(x)L(x, 梅花)L(x, 菊花)L(x, 梅花)L(x, 菊花)(2) 有人每每天下午都去去打篮球。解：定义谓词P(x)：x是是人B(x)：x打打篮球A(y)：y是是下午将知识用谓词表表示为：a(x )(y) (A(yy)B(x)P(x)(3) 新型计计算机

2、速度又又快，存储容容量又大。解：定义谓词NC(x)：xx是新型计算算机F(x)：x速速度快 B(x)：x容容量大将知识用谓词表表示为：(x) (NCC(x)F(x)B(x)(4) 不是每每个计算机系系的学生都喜喜欢在计算机机上编程序。解：定义谓词S(x)：x是是计算机系学学生L(x, prragrammming)：x喜欢编编程序U(x,commputerr)：x使用用计算机将知识用谓词表表示为： (x) (S(x)L(x, pragrramminng)U(x,ccomputter)(5) 凡是喜喜欢编程序的的人都喜欢计计算机。解：定义谓词P(x)：x是是人L(x, y)：x喜欢yy将知识用谓词

3、表表示为：(x) (P(x)L(x,ppragraammingg)L(x, compuuter)2.9 用谓词词表示法求解解机器人摞积积木问题。设设机器人有一一只机械手，要要处理的世界界有一张桌子子，桌上可堆堆放若干相同同的方积木块块。机械手有有4个操作积积木的典型动动作：从桌上上拣起一块积积木；将手中中的积木放到到桌之上；在在积木上再摞摞上一块积木木；从积木上上面拣起一块块积木。积木木世界的布局局如下图所示示。AABCCACABB图 机器人摞摞积木问题解：(1) 先先定义描述状状态的谓词 CLEEAR(x)：积木x上面是空的的。 ON(x, y)：积木x在积木y的上面。 ONTTABLE(x

4、)：积木木x在桌子上。 HOLLDING(x)：机械械手抓住x。HANDEMPPTY：机械械手是空的。其中，x和y的的个体域都是是A, BB, C。问题的初始状态态是：ONTABLEE(A)ONTABLEE(B)ON(C, AA) CLEEAR(B) CLEEAR(C) HANNDEMPTTY 问题的的目标状态是是： ONTTABLE(C) ON(B, C) ON(A, B)CLEAR(AA) HANDEMPPTY(2) 再定义义描述操作的的谓词在本问题中，机机械手的操作作需要定义以以下4个谓词词： Pickup(x)：从桌桌面上拣起一一块积木x。 Putdownn(x)：将将手中的积木木放到

5、桌面上上。Stack(xx, y)：在积木x上面再摞上上一块积木yy。Upstackk(x, yy)：从积木木x上面拣起一一块积木y。其中，每一个操操作都可分为为条件和动作作两部分，具具体描述如下下： Pickup(x) 条件件：ONTAABLE(xx)，HANDEEMPTY，CLEARR(x) 动作作：删除表：ONTABBLE(x)，HANDEEMPTY 添添加表：HAANDEMPPTY(x)Putdownn(x) 条件件：HANDDEMPTYY(x) 动作作：删除表：HANDEEMPTY(x) 添添加表：ONNTABLEE(x)，CLEARR(x) ，HANDEEMPTYStack(xx,

6、 y) 条件件：HANDDEMPTYY(x)，CLEARR(y) 动作作：删除表：HANDEEMPTY(x)，CLEARR(y) 添添加表：HAANDEMPPTY，ON(x, y) ，CLEAAR(x)Upstackk(x, yy) 条件件：HANDDEMPTYY，CLEARR(y) ，ON(yy,x) 动作作：删除表：HANDEEMPTY，ON(y, x) 添添加表：HOLDINNG(y)，CLEARR(x) (3) 问题求解解过程利用上述谓词和和操作，其求求解过程为：ONTABLE(A)ONTABLE(B)ONTABLE(ONTABLE(A)ONTABLE(B)ONTABLE(C)CLEA

7、R(A)CLEAR(B)CLEAR(C)HANDEMPTYONTABLE(A) ONTABLE(B)ON(C, A)CLEAR(B)CLEAR(C) HANDEMPTYONTABLE(A)ONTABLE(B) HOLDING(C)CLEAR(A)CLEAR(B)CLEAR(C)Upstack(AUpstack(A,C)Putdown(C)Pickup(Pickup(B)ONTABLE(A)ONTABLE(ONTABLE(A)ONTABLE(C)ON(B,C)CLEAR(A)CLEAR(B)HANDEMPTYONTABLE(A)ONTABLE(C)HOLDING(B)CLEAR(A)CLEAR(

8、B)CLEAR(C)ONTABLE(CONTABLE(C)ON(B,C)ON(A,B)CLEAR(A)HANDEMPTONTABLE(C)ON(B,C)CLEAR(A)CLEAR(B)HOLDING(A)Stack(B,Stack(B,A)Stack(C,B)Pickup(A)2.10 用谓谓词表示法求求解农夫、狼狼、山羊、白白菜问题。农农夫、狼、山山羊、白菜全全部放在一条条河的左岸，现现在要把他们们全部送到河河的右岸去，农农夫有一条船船，过河时，除除农夫外船上上至多能载狼狼、山羊、白白菜中的一种种。狼要吃山山羊，山羊要要吃白菜，除除非农夫在那那里。似规划划出一个确保保全部安全过过河的计划。请

9、请写出所用谓谓词的定义，并并给出每个谓谓词的功能及及变量的个体体域。解：(1) 先先定义描述状状态的谓词要描述这个问题题，需要能够够说明农夫、狼狼、羊、白菜菜和船在什么么位置，为简简化问题表示示，取消船在在河中行驶的的状态，只描描述左岸和右右岸的状态。并并且，由于左左岸和右岸的的状态互补，因因此可仅对左左岸或右岸的的状态做直接接描述。本题题选择对左岸岸进行直接描描述的方法，即即定义谓词如如下：AL(x)：xx在左岸其中，x的个体体域是农夫夫，船，狼，羊羊，白菜。对对应地，AL(x)表示x在右右岸。 问题的的初始状态：AL(农夫)AL(船)AL(狼)AL(羊)AL(白菜) 问题的的目标状态：AL

10、(农夫)AL(船)AL(狼)AL(羊)AL(白菜) (2) 再定定义描述操作作的谓词本题需要以下44个描述操作作的谓词：L-R：农夫自自己划船从左左岸到右岸L-R(x)：农夫带着xx划船从左岸岸到右岸R-L：农夫自自己划船从右右岸到左岸R-L(x) ：农夫带着着x划船从右右岸到左岸其中，x的个体体域是狼，羊羊，白菜。对上述每个操作作，都包括条条件和动作两两部分。它们们对应的条件件和动作如下下：L-R：农夫划划船从左岸到到右岸 条件：AL(船)，AL(农农夫)，AL(狼)AL(羊羊)，AL(羊)AL(白白菜) 动作：删除表：AAL(船)，AAL(农夫) 添加加表：AL(船)，AL(农夫夫)L-R

11、(狼)：农夫带着狼狼划船从左岸岸到右岸 条件：AL(船)，AL(农农夫)，ALL(狼)，AL(羊) 动作：删除表：AAL(船)，AAL(农夫)，AL(狼狼) 添加加表：AL(船)，AL(农夫夫)，AL(狼)L-R(羊)：农夫带着羊羊划船从左岸岸到右岸 条件：AL(船)，AL(农农夫)，ALL(羊)， AL(狼)，AL(白白菜) 或：AAL(船)，AAL(农夫)，AL(羊羊)，AL(狼)，AL(白菜菜) 动作：删除表：AAL(船)，AAL(农夫)，AL(羊羊) 添加加表：AL(船)，AL(农夫夫)，AL(羊)L-R(白菜)：农夫带着着白菜划船从从左岸到右岸岸 条件：AL(船)，AL(农农夫)，A

12、LL(白菜)，AL(狼) 动作：删除表：AAL(船)，AAL(农夫)，AL(白白菜) 添加加表：AL(船)，AL(农夫夫)，AL(白菜菜)R-L：农夫划划船从右岸到到左岸 条件：AL(船)，AL(农夫夫)，AL(狼)AL(羊)，AL(羊羊)AL(白菜菜) 或：AL(船)，AL(农夫夫) ，AL(狼)，AL(白菜菜)，AL(羊) 动作：删除表：AL(船)，AL(农夫夫) 添加加表：AL(船)，ALL(农夫)R-L(羊) ：农夫带着着羊划船从右右岸到左岸 条件：AL(船)，AL(农夫夫)，AL(羊) ，AL(狼)，AL(羊)，AL(白白菜) 动作：删除表：AL(船)，AL(农夫夫)，AL(羊) 添

13、加加表：AL(船)，ALL(农夫)，AAL(羊)(3) 问题求求解过程AL(白菜)AL(农夫)AL(白菜)AL(农夫)AL(船)AL(狼)AL(羊)AL(农夫)AL(船)AL(狼)AL(白菜)AL(羊)AL(狼)AL(白菜)AL(农夫)AL(船)AL(羊)R-L R-L(羊) L-R(狼)L-R(羊)AL(船)R-L R-L(羊) L-R(狼)L-R(羊)AL(狼)AL(羊)AL(白菜)AL(农夫)AL(船)AL(羊)AL(农夫)AL(船)AL(羊)AL(白菜)AL(狼)AL(农夫)AL(船)AL(羊)AL(白菜)AL(狼)AL(羊)AL(农夫)AL(船)AL(白菜)AL(狼)L-R(羊)AL

14、(农夫)L-R(羊)AL(农夫)AL(船)AL(羊)AL(白菜)AL(狼)R-L L-R(白菜)2.11 用谓谓词表示法求求解修道士和和野人问题。在在河的北岸有有三个修道士士、三个野人人和一条船，修修道士们想用用这条船将所所有的人都运运过河去，但但要受到以下下条件限制：(1) 修道士士和野人都会会划船，但船船一次只能装装运两个人。(2) 在任何何岸边，野人人数不能超过过修道士，否否则修道士会会被野人吃掉掉。假定野人愿意服服从任何一种种过河安排，请请规划出一种种确保修道士士安全的过河河方案。要求求写出所用谓谓词的定义、功功能及变量的的个体域。解：（1）定义义谓词先定义修道士和和野人人数关关系的谓

15、词：G(x,y,SS)： 在状状态S下x大大于yGE(x,y,S)：在状状态S下x大大于或等于yy其中，x,y分分别代表修道道士人数和野野人数，他们们的个体域均均为0,11,2,3。再定义船所在岸岸的谓词和修修道士不在该该岸上的谓词词：Boat(z,S)：状态态S下船在zz岸EZ(x,S)： 状态SS下x等于00，即修道士士不在该岸上上其中，z的个体体域是L,R，L表表示左岸，RR表示右岸。 再定义义安全性谓词词： Saffety(zz,x,y,S)(G(x,0,S)GE(x,y,S)(EZ(x,S)其中，z,x,y的含义同同上。该谓词词的含义是：状态S下，在在z岸，保证证修道士安全全，当且仅

16、当当修道士不在在该岸上，或或者修道士在在该岸上，但但人数超过野野人数。该谓谓词同时也描描述了相应的的状态。再定义描述过河河方案的谓词词：L-R(x, x1, yy, y1,S)：x11个修道士和和y1个野人人渡船从河的的左岸到河的的右岸条件：Safeety(L,x-x1,y-y1,S)Safetty(R,33-x+x11,3-y+y1,S)Boat(L,S)动作：Safeety(L,x-x1,y-y1,S)Safetty(R,33-x+x11,3-y+y1,S)Boat(R,S)R-L (x, x1, y, y11,S)：xx2个修道士士和y2个野野人渡船从河河的左岸到河河的右岸条件：Safe

17、ety(R,3-x-xx2,3-yy-y2,SS)Safetty(L,xx+x2,yy+y2,SS)Boat(R,S)动作：Safeety(R,3-x-xx2,3-yy-y2,SS)Safetty(L,xx+x2,yy+y2,SS)Boat(L,S) (2) 过河方案案 Safeety(L,3,3,SS0)Safetty(R,00,0,S00)Boat(L,S0) L-R(33, 1, 3, 1,S0) LL-R(3, 0, 33, 2,SS0)Safety(L,2,22,S1)Safetty(R,11,1,S11)Boat(R,S1)Safety(L,3,11,S1)Safetty(R,00

18、,2,S11)Boat(R,S1)R-L (2, 1, 22, 0,SS1) R-L (3,0, 1, 1,S11)Safety(L,3,22,S2)Safetty(R,00,1,S22)Boat(L,S2)L-R(3, 0, 2, 2,S22)Safety(L,3,00,S3)Safetty(R,00,3,S33)Boat(R,S3)R-L (3, 0, 00, 1,SS3)Safety(L,3,11,S4)Safetty(R,00,2,S11)Boat(L,S4)L-R(3, 2, 1, 0,S44)Safety(L,1,11,S5)Safetty(R,22,2,S55)Boat(R,S5

19、)R-L (1, 1, 11, 1,SS5)Safety(L,2,22,S6)Safetty(R,11,1,S66)Boat(L,S6)L-R(2, 2, 2, 0,S66)Safety(L,0,22,S7)Safetty(R,33,1,S77)Boat(R,S7)R-L (0, 0, 22, 1,SS7)Safety(L,0,33,S8)Safetty(R,33,0,S88)Boat(L,S8)L-R(0, 0, 3, 2,S88)Safety(L,0,11,S9)Safetty(R,33,2,S99)Boat(R,S9)R-L (0, 1, 11, 0,SS9)Safety(L,1,11,

20、S10)Safetty(R,22,2,S110)Boat(L,S100)L-R(1, 1, 1, 1,S110)Safety(L,0,00,S11)Safetty(R,33,3,S111)Boat(R,S111)2.18 请对对下列命题分分别写出它们们的语义网络络：(1) 每个学学生都有一台台计算机。gGSgGSGS解：gGSgGSGS占有权计算机学生占有权计算机学生AKOISAISAFAKOISAISAFOwnsOwnerOwnsOwnercosgcosg(2) 高老师师从3月到77月给计算机机系学生讲计计算机网络课课。 解：7月8月7月8月StartEndStartEnd老师ISAObje

21、ctSubject高老师计算机系学生讲课事件老师ISAObjectSubject高老师计算机系学生讲课事件ActionCaurseActionCaurse计算机网络讲课计算机网络讲课(3) 学习班班的学员有男男、有女、有有研究生、有有本科生。 解：参参例2.144(4) 创新公公司在科海大大街56号，刘刘洋是该公司司的经理，他他32岁、硕硕士学位。 解：参参例2.100(5) 红队与与蓝队进行足足球比赛，最最后以3：22的比分结束束。 解：比赛比赛AKOAKOParticipants1Outcome3:22Participants1Outcome3:22足球赛红队红队Participants

22、2Participants 2蓝队蓝队2.19 请把把下列命题用用一个语义网网络表示出来来：(1) 树和草草都是植物；植物解：植物AKOAKOAKOAKO草树草树(2) 树和草草都有叶和根根；根叶 解：根叶HaveHaveHaveHave植物植物是一种是一种是一种是一种草树草树(3) 水草是是草，且生长长在水中； 解：LiveAKOAKO水草LiveAKOAKO水草水中植物草水中植物草(4) 果树是是树，且会结结果； 解：CanAKOAKO果树CanAKOAKO果树结果植物树结果植物树(5) 梨树是是果树中的一一种，它会结结梨。 解：CanAKOAKO梨树CanAKOAKO梨树树果树结梨树果树

23、结梨2.25 假设设有以下一段段天气预报：“北京地区今今天白天晴，偏偏北风3级，最最高气温122，最低气温温-2，降水概率率15%。”请用框架表表示这一知识识。解：Frame 地域：北京 时段：今天白天 天气：晴 风向：偏北 风力：3级 气温：最高：122度 最低低：-2度 降水概概率：15%2.26 按“师生框架”、“教师框架”、“学生框架”的形式写出出一个框架系系统的描述。解：师生框架Frame Namme：Uniit（Lasst-namme，Firrst-naame） Sexx：Areaa（malee，femaale） Deffault：male Agee：Unitt（Yearrs）Te

24、lephoone：Hoome UUnit（NNumberr）Mobile Unitt（Numbber） 教师框架Frame AKOO Majjor：Unnit（Maajor-NName） Leccturess：Unitt（Courrse-Naame） Fieeld：Unnit（Fiield-NName） Prooject ：Areaa（Natiional，PProvinncial，OOther） Defauult：Prrovinccial Papper：Arrea（SCCI，EI，CCore，GGeneraal） DDefaullt：Corre 学生框架Frame AKOO Majjor：Un

25、nit（Maajor-NName） Claasses：Unit（CClassees-Namme） Deggree：AArea（ddoctorr，masttor, bbachellor） DDefaullt：bacchelorr 确定性推理部分分参考答案3.8 判断下下列公式是否否为可合一，若若可合一，则则求出其最一一般合一。(1) P(a, b), P(xx, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, xx), P(x, f(a), ff(b) (5) P(xx, y), P(y, x)解：(1) 可合一，

26、其其最一般和一一为：=a/x, b/y。(2) 可合合一，其最一一般和一为：=y/f(x), b/z。(3) 可合合一，其最一一般和一为：= f(b)/y, b/xx。(4) 不可可合一。(5) 可合合一，其最一一般和一为：= y/x。3.11 把下下列谓词公式式化成子句集集：(x)(y)(P(x, y)Q(x, y)(x)(y)(P(x, y)Q(x, y)(x)(y)(P(x, y)(Q(x, y)R(x, y)(x) (y) (z)(P(x, y)Q(x, y)R(x, z) 解：(1) 由于于(x)(y)(P(x, y)Q(x, y)已经经是Skollem标准型型，且P(xx, y)Q

27、(x, y)已经是是合取范式，所所以可直接消消去全称量词词、合取词，得得 P(x, y), Q(x, y) 再进行行变元换名得得子句集： S= P(x, y), Q(u, v) (2) 对谓词公公式(x)(y)(P(x, y)Q(x, y)，先先消去连接词词“”得：(x)(y)(P(x, y)Q(x, y)此公式已为Skkolem标标准型。 再消去去全称量词得得子句集： S=P(x, y)Q(x, y) (3) 对谓词公公式(x)(y)(P(x, y)(Q(x, y)R(x, y)，先先消去连接词词“”得：(x)(y)(P(x, y)(Q(x, y)R(x, y)此公式已为前束束范式。再消去存

28、在量词词，即用Skkolem函函数f(x)替换y得：(x)(P(xx, f(xx)Q(x, f(x)R(x, f(x)此公式已为Skkolem标标准型。 最后消消去全称量词词得子句集： S=PP(x, ff(x)Q(x, f(x)R(x, f(x) (4) 对谓词(x) (y) (z)(P(x, y)Q(x, y)R(x, z)，先先消去连接词词“”得：(x) (y) (z)(P(x, y)Q(x, y)R(x, z)再消去存在量词词，即用Skkolem函函数f(x)替换y得：(x) (y) (P(x, y)Q(x, y)R(x, f(x,yy)此公式已为Skkolem标标准型。 最后消消去全

29、称量词词得子句集：S=P(xx, y)Q(x, y)R(x, f(x,yy)3-13 判判断下列子句句集中哪些是是不可满足的的：PQ, Q, PP, P PQ , PQ, PPQ, PQ P(y)Q(y) , P(f(xx)R(a)P(x)Q(x) , P(y)R(y), P(a), S(a), S(z)R(z)P(x)Q(f(xx),a) , P(h(yy)Q(f(hh(y), a)P(z)P(x)QQ(x)R(x) , P(y)R(y), Q(a), R(b) 解：(1) 不可可满足，其归归结过程为：PQQPPNIL(2) 不可满满足，其归结结过程为：PPQPQQPQPQQNIL(3) 不

30、是不不可满足的，原原因是不能由由它导出空子子句。(4) 不可满满足，其归结结过程略(5) 不是不不可满足的，原原因是不能由由它导出空子子句。(6) 不可满满足，其归结结过程略 3.114 对下列各各题分别证明明G是否为F1,F2,Fn的逻辑结论论：F: (x)(y)(P(x, y)G: (y)(x)(P(x, y)F: (x)(P(x)(Q(a)Q(b)G: (x) (P(x)Q(x)F: (x)(y)(P(f(x)(Q(f(y)G: P(f(a)P(y)Q(y)F1: (x)(P(x)(y)(Q(y)L(x.yy)F2: (x) (P(xx)(y)(R(y)L(x.yy)G: (x)(R(x

31、)Q(x)F1: (x)(P(x)(Q(x)R(x)F2: (x) (P(xx)S(x)G: (x) (S(x)R(x) 解：(1) 先将将F和G化成子句句集： S=PP(a,b), P(x,bb) 再对SS进行归结：PP(x,b)P(a,b)NIL a/xxNIL 所以，G是F的逻辑结论(2) 先将FF和G化成子句句集由F得：S1=P(x)，(Q(a)Q(b)由于G为： (x) (PP(x)Q(x)，即 (x) ( P(x) Q(x)，可得： S2= P(x) Q(x)因此，扩充的子子句集为：S= P(xx)，(Q(a)Q(b)， P(x) Q(x) 再对SS进行归结：Q(a)Q(a)Q(b

32、)Q(a) P(x) Q(x) P(a)P(x)NILQ(a)Q(b) a/bb P(x) P(x) Q(x)Q(a)a/x P( P(a)P(x) a/xNILNIL 所以，G是F的逻辑结论 同理可可求得(3)、(4)和和(5)，其其求解过程略略。 3.15 设设已知：如果x是y的父父亲，y是z的父亲，则则x是z的祖父；每个人都有一个个父亲。使用归结演绎推推理证明：对对于某人u，一定存在在一个人v，v是u的祖父。 解：先先定义谓词 F(xx,y)：xx是y的父亲 GF(x,z)：x是z的祖父 P(xx)：x是一个人 再用谓谓词把问题描描述出来： 已知FF1：(x) (y) (z)( F(x,

33、y)F(y,zz)GF(x,zz) F2：(y)(P(x)F(x,yy) 求证结结论G：(u) (v)( P(uu)GF(v,uu) 然后再再将F1，FF2和G化成子句句集： F(x,yy)F(y,zz)GF(x,zz) P(r)F(s,rr) P(u) GF(vv,u) 对上述述扩充的子句句集，其归结结推理过程如如下：F(x,y)F(y,z)GF(x,z)GF(v,u)F(x,y)F(y,z)P(r)F(s,r)F(y,z)P(y)P(r)F(s,r)P(y)P(z)P(y)P(u)NIL x/v,z/uux/s,y/ry/s,z/r yy/z y/u 由于导导出了空子句句，故结论得得证。3

34、.16 假假设张被盗，公公安局派出55个人去调查查。案情分析析时，贞察员员A说：“赵与钱中至至少有一个人人作案”，贞察员B说：“钱与孙中至至少有一个人人作案”，贞察员C说：“孙与李中至至少有一个人人作案”，贞察员D说：“赵与孙中至至少有一个人人与此案无关关”，贞察员E说：“钱与李中至至少有一个人人与此案无关关”。如果这55个侦察员的的话都是可信信的，使用归归结演绎推理理求出谁是盗盗窃犯。解：(1) 先先定义谓词和和常量设C(x)表示示x作案，ZZ表示赵，QQ表示钱，SS表示孙，LL表示李(2) 将已知知事实用谓词词公式表示出出来赵与钱中至少有有一个人作案案：C(Z)C(Q)钱与孙中至少有有一个

35、人作案案：C(Q)C(S)孙与李中至少有有一个人作案案：C(S)C(L)赵与孙中至少有有一个人与此此案无关： (C (ZZ)C(S)，即 C (Z) C(S)钱与李中至少有有一个人与此此案无关： (C (QQ)C(L)，即 C (Q) C(L)(3) 将所要要求的问题用用谓词公式表表示出来，并并与其否定取取析取。设作案者为u，则则要求的结论论是C(u)。将其与其其否)取析取取，得： C(u) C(u)(4) 对上述述扩充的子句句集，按归结结原理进行归归结，其修改改的证明树如如下：C(C(Z)C(Q)C (Z) C(S)C(Q)C(S)C(Q)C(S)C(Q)C(u)C(u)C(Q) Q/uu

36、因此，钱钱是盗窃犯。实实际上，本案案的盗窃犯不不止一人。根根据归结原理理还可以得出出：C(S)C(L)C(S)C(L)C (Q) C(L)C(S)C(Q)C(Q)C(S)C(S)C(u)C(u)C(S)C (Q) C(L)C(S)C(L)C(Q)C(Q)C(S)C(S)C(Q)C(u)C(u)C(S)C(S) S/uu C(S)C(S) 因此，孙孙也是盗窃犯犯。3.18 设设有子句集： P(x)Q(a, b), PP(a)Q(a, b), QQ(a, ff(a), P(x)Q(x, b)分别用各种归结结策略求出其其归结式。解：支持集策略略不可用，原原因是没有指指明哪个子句句是由目标公公式的否定

37、化化简来的。删除策略不可用用，原因是子子句集中没有有没有重言式式和具有包孕孕关系的子句句。单文字子句策略略的归结过程程如下：Q(a, f(a)P(x)Q(a, f(a)P(x)Q(a, b) bb/f(a)P(x)P(x)Q(x, b)P(a)Q(a, f(a)Q(a, b) Q(a, f(a)Q(a, b) b/f(aa)Q(Q(a, b)用线性输入策略略（同时满足足祖先过滤策策略）的归结结过程如下：P(a)P(a)Q(a, b)P(x)Q(a, b)P(x)Q(x, b)P(a) P(x)Q(x, b)P(a)a/xQ(a, f(a)QQ(a, f(a)Q(a,b) b/f(a)NIL N

38、IL3.19 设设已知：能阅读的人是识识字的；海豚不识字；有些海豚是很聪聪明的。请用归结演绎推推理证明：有有些很聪明的的人并不识字字。解：第一步，先先定义谓词， 设R(x)表示示x是能阅读读的；K(y)表示yy是识字的；W(z) 表示示z是很聪明明的；第二步，将已知知事实和目标标用谓词公式式表示出来能阅读的人是识识字的：(xx)(R(xx)K(x)海豚不识字：(y)(K (y)有些海豚是很聪聪明的：(zz) W(zz)有些很聪明的人人并不识字：(x)( W(z)K(x) 第三步步，将上述已已知事实和目目标的否定化化成子句集： R(x)K(x)K (y)W(z)W(z)KK(x) 第四步，用用归

39、结演绎推推理进行证明明W(z)W(z)W(z)K(x)W(z)K(z)W(z)K(z)NILNIL3.20 对对子句集： PQ, QR, RW, RP, WQ, QR 用线性输入策略略是否可证明明该子句集的的不可满足性性？ 解：用用线性输入策策略不能证明明子句集PQ, QQR, RW, RP, WQ, QR 的不可满足性。原原因是按线性性输入策略，不不存在从该子子句集到空子子句地归结过过程。3.21 对对线性输入策策略和单文字字子句策略分分别给出一个个反例，以说说明它们是不不完备的。3.22 分分别说明正向向、逆向、双双向与/或形形演绎推理的的基本思想。3.23 设设已知事实为为 (PQ)R)

40、 (S(TU) F规则则为 S(XY)Z试用正向演绎推推理推出所有有可能的子目目标。解：先给出已知知事实的与/或树，再利利用F规则进进行推理，其其规则演绎系系统如下图所所示。由该图可以直接接写出所有可可能的目标子子句如下： PQQPQPQYYRTU RXZRYZ 所有子目标UTZYXRQP所有目标UTZYXRQPYXZXYSUTTUS所有目标UTZYXRQP所有目标YZU所有子目标UTZYXRQP所有目标UTZYXRQPYXZXYSUTTUS所有目标UTZYXRQP所有目标YZUTXPRQYXXYYXXYF规则F规则ZXYZXYXYZSSSSUTQPTUQPUTQPTUQP已知事实已知事实已知

41、事实已知事实TUSR(PQ)TTUSR(PQ)TURS(PQ) (S(T (S(TU)(PQ)R) (S(TU)(PQ)R)(PQ)(PQ)R) (S(TU)(PQ)R) (S(TU)3.24 设设有如下一段段知识：“张、王和李都都属于高山协协会。该协会会的每个成员员不是滑雪运运动员，就是是登山运动员员，其中不喜喜欢雨的运动动员是登山运运动员，不喜喜欢雪的运动动员不是滑雪雪运动员。王王不喜欢张所所喜欢的一切切东西，而喜喜欢张所不喜喜欢的一切东东西。张喜欢欢雨和雪。”试用谓词公式集集合表示这段段知识，这些些谓词公式要要适合一个逆逆向的基于规规则的演绎系系统。试说明明这样一个系系统怎样才能能回答问

42、题：“高山俱乐部中中有没有一个个成员，他是是一个登山运运动员，但不不是一个滑雪雪运动员？”解：(1) 先先定义谓词A(x) 表示示x是高山协协会会员S(x) 表示示x是滑雪运运动员C(x) 表示示x是登山运运动员L(x,y) 表示x 喜喜欢y (2) 将问题题用谓词表示示出来“张、王和李都都属于高山协协会A(Zhangg)A(Wanng)A(Li)高山协会的每个个成员不是滑滑雪运动员，就就是登山运动动员(x)(A(xx)S(x)C(x)高山协会中不喜喜欢雨的运动动员是登山运运动员(x)(L(x, Raain)C(x)高山协会中不喜喜欢雪的运动动员不是滑雪雪运动员(x)(L(x, Snnow)

43、S(x)王不喜欢张所喜喜欢的一切东东西(y)( L(Zhangg, y) L(WWang ,y) 王喜欢欢张所不喜欢欢的一切东西西(y)( LL(Zhanng, y)L(Wanng, y)张喜欢雨和雪L(Zhangg , Raain)L(Zhaang , Snow)(3) 将问题题要求的答案案用谓词表示示出来高山俱乐部中有有没有一个成成员，他是一一个登山运动动员，但不是是一个滑雪运运动员？ (x)( A(x)C(x) S(x) (4) 为了进行行推理，把问问题划分为已已知事实和规规则两大部分分。假设，划划分如下：已知事实：A(Zhangg)A(Wanng)A(Li)L(Zhangg , Raa

44、in)L(Zhaang , Snow)规则：(x)(A(xx)S(x)C(x)(x)(L(x, Raain)C(x)(x)(L(x, Snnow) S(x)(y)( L(Zhangg, y) L(WWang ,y)(y)( LL(Zhanng, y)L(Wanng, y) (5) 把已知事事实、规则和和目标化成推推理所需要的的形式事实已经是文字字的合取形式式：f1: A(ZZhang)A(Wanng)A(Li)f2: L (Zhangg , Raain)L(Zhaang , Snow)将规则转化为后后件为单文字字的形式：r1: A(xx)S(x)C(x)r2: L(x, Raain)C(x)r

45、3: L(x, Snnow) S(x)r4: L(ZZhang, y) L(Waang ,yy)r5: LL(Zhanng, y)L(Wanng , yy) 将目标标公式转换为为与/或形式式 A(x)(C(x) S(x) (6) 进行逆向向推理逆向推理的关键键是要能够推推出L(Zhhang , Rainn)L(Zhaang , Snow)，其逆向演绎过程程如下图所示示。 A(x)(C(x) S(x)C(x)C(x) S(x) A(x)C(x)C(x) S(x)r2r2r34LL(x, Rain)L(x, Snow)Wang/x, y/RainWang /x, y/SnowWang/x, y/R

46、ainWang /x, y/SnowLL(Wang, y)L(Wang, y)r4r4r4r4L(Zhang, y)L(Zhang, y)L(Zhang, y)Rain/ySnow/yRain/ySnow/yL(Zhang, Snow)L(Zhang, Snow)L(Zhang, Rain)搜索策略部分参参考答案4.5 有一农农夫带一条狼狼，一只羊和和一框青菜与与从河的左岸岸乘船倒右岸岸，但受到下下列条件的限限制：(1) 船太小小，农夫每次次只能带一样样东西过河；如果没有农夫看看管，则狼要要吃羊，羊要要吃菜。请设计一个过河河方案，使得得农夫、浪、羊羊都能不受损损失的过河，画画出相应的状状态空间

47、图。题示：(1) 用四元组（农农夫，狼，羊羊，菜）表示示状态，其中中每个元素都都为0或1，用用0表示在左左岸，用1表表示在右岸。(2) 把每次次过河的一种种安排作为一一种操作，每每次过河都必必须有农夫，因因为只有他可可以划船。解：第一步，定定义问题的描描述形式用四元组S=（ff，w，s，vv）表示问题题状态，其中中，f，w，ss和v分别表表示农夫，狼狼，羊和青菜菜是否在左岸岸，它们都可可以取1或00，取1表示示在左岸，取取0表示在右右岸。第二步，用所定定义的问题状状态表示方式式，把所有可可能的问题状状态表示出来来，包括问题题的初始状态态和目标状态态。由于状态变量有有4个，每个个状态变量都都有2

48、种取值值，因此有以以下16种可可能的状态：S0=(1,11,1,1)，S1=(1,11,1,0)，S2=(1,11,0,1)，S3=(1,11,0,0)S4=(1,00,1,1)，S5=(1,00,1,0)，S6=(1,00,0,1)，S7=(1,00,0,0) S8=(0,11,1,1)，S9=(0,11,1,0)，S10=(0,1,0,11)，S111=(0,11,0,0)S12=(0,0,1,11)，S133=(0,00,1,0)，S14=(0,0,0,11)，S155=(0,00,0,0)其中，状态S33，S6，S7，S8，S9，S12是不合法法状态，S00和S15分别是初初始状态和目

49、目标状态。第三步，定义操操作，即用于于状态变换的的算符组F由于每次过河船船上都必须有有农夫，且除除农夫外船上上只能载狼，羊羊和菜中的一一种，故算符符定义如下：L(i)表示农农夫从左岸将将第i样东西西送到右岸（ii=1表示狼狼，i=2表表示羊，i=3表示菜，ii=0表示船船上除农夫外外不载任何东东西）。由于于农夫必须在在船上，故对对农夫的表示示省略。R (i)表示示农夫从右岸岸将第i样东东西带到左岸岸（i=1表表示狼，i=2表示羊，ii=3表示菜菜，i=0表表示船上除农农夫外不载任任何东西）。同同样，对农夫夫的表示省略略。这样，所定义的的算符组F可可以有以下88种算符：L (0)，LL (1)，

50、LL (2)，LL (3) R(0)，R(1)，R (2)，RR (3)第四步，根据上上述定义的状状态和操作进进行求解。该问题求解过程程的状态空间间图如下：(1,1,l,1)(1,1,l,1)L(2)L(2)(0,1,0,1)(0,1,0,1)R(0)R(0)(1,1,0,1)(1,1,0,1)L(3)L(1)L(3)L(1)(0,1,0,0)(0,0,0,1)(0,1,0,0)(0,0,0,1)R(2)R(2)R(2)R(2)(1,1,1,0)(1,0,1,1)(1,1,1,0)(1,0,1,1)L(2)L(2)L(3)L(3)(0,0,1,0)(0,0,1,0)R(0)R(0)(1,0,1

51、,0)(1,0,1,0)L(2)L(2)(0,0,0,0)(0,0,0,0)4.7 圆盘问问题。设有大大小不等的三三个圆盘A、B、C套在一根轴轴上，每个盘盘上都标有数数字1、2、33、4，并且且每个圆盘都都可以独立的的绕轴做逆时时针转动，每每次转动900，其初始状状态S0和目标状态态Sg如图4-331所示，请请用广度优先先搜索和深度度优先搜索，求求出从S0到Sg的路径。CC12222222 CC12222222BAAB42 BAAB42234131231331412341312313314144444343 初始始状态S0 目标状态态Sg 图 431 圆盘问题解：设用qA，qqB和qC分别表示

52、把把A盘，B盘盘和C盘绕轴轴逆时针转动动90，这些操作作（算符）的的排列顺序是是qA，qB，qC。应用广度优先搜搜索，可得到到如下搜索树树。在该搜索索树中，重复复出现的状态态不再划出，节节点旁边的标标识Si，i=0,1,2,，为按节点点被扩展的顺顺序给出的该该节点的状态态标识。由该图可以看出出，从初始状状态S0到目标状态态Sg的路径是S02513(Sg)323221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC41341233233412333131312442241

53、2344123412313324112244qC334213112244qA314241231234qB132314242413qC4.7题的广度优先搜索树S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度优先搜索索略。4.8 图4-32是5个个城市的交通通图，城市之之间的连线旁旁边的数字是是城市之间路路程的费用。要要求从A城出发，经经过其它各城城市一次且仅仅一次，最后后回到A城，请找出出一条最优线线路。 A 10 BB 2 8 9 CC 111 66 3 12 8 D 9 EE432 交通通费用图解：这个问题又又称为旅行商商问题（trravellling ssalesmm

54、an prroblemm, TSPP）或货郎担担问题，是一一个较有普遍遍性的实际应应用问题。根根据数学理论论，对n个城城市的旅行商商问题，其封封闭路径的排排列总数为： (nn!)/n=(n-1)!其计算量相当大大。例如，当当n=20时时，要穷举其其所有路径，即即使用一个每每秒一亿次的的计算机来算算也需要3550年的时间间。因此，对对这类问题只只能用搜索的的方法来解决决。下图是对图4-32按最小小代价搜索所所得到的搜索索树，树中的的节点为城市市名称，节点点边上的数字字为该节点的的代价g。其其计算公式为为 g(nni+1)=gg(ni)+c(nni, ni+11)其中，c(nii,ni+1)为节节

55、点ni到ni+1节点的的边代价。0A0A119210119210102119BDCE102119BDCE9869312838612898693128386128201917CDB181221ECB10105EDB16E2218DC201917CDB181221ECB10105EDB16E2218DC331288933128892312386886896912612988323123868868969126129883C32B222925DC2020EBB16D191622DE31E25CC32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426

56、CB2720C1417BE2524DC2621DE9838E12912BD272426CB2720C1417BE2524DC2621DE68126666812666E3133E9328D31B926B26E831B28DD273E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B30282023E35ED27D32C34B302820E28CBE28CB21021030A30A30A30A图4.32的最小代价搜索树图4.32的最小代价搜索树可以看出，其最最短路经是 A-CC-D-E-B-A或 A-BB-E-D-C-A其实，它们是同同一条路经。4.11

57、 设有有如下结构的的移动将牌游游戏：BBWWE其中，B表示黑黑色将牌，WW表是白色将将牌，E表示空格。游游戏的规定走走法是：(1) 任意一一个将牌可移移入相邻的空空格，规定其其代价为1；(2) 任何一一个将牌可相相隔1个其它的将将牌跳入空格格，其代价为为跳过将牌的的数目加1。游戏要达到的目目标什是把所所有W都移到B的左边。对对这个问题，请请定义一个启启发函数h(n)，并给给出用这个启启发函数产生生的搜索树。你你能否判别这这个启发函数数是否满足下下解要求？再再求出的搜索索树中，对所所有节点是否否满足单调限限制？解：设h(x)=每个W左左边的B的个个数，f(xx)=d(xx)+3*hh(x)，其其

58、搜索树如下下：f(x)=0+12=12f(x)=0+12=12BBWWEf(x)=1+12=13f(x)=1+12=13BBE WWf(x)=1+12=13f(x)=1+12=13BBWE Wf(x)=2+12=14f(x)=2+12=14f(x)=2+9=11f(x)=2+9=11BBEWWBEWBWf(x)=3+9=12f(x)=3+9=12EBWBWf(x)=4+6=10f(x)=4+6=10WBE BWf(x)=5+3=8f(x)=5+3=8WBWBEf(x)=6+3=9f(x)=6+3=9WBWE Bf(x)=7+0=7f(x)=7+0=7WBWE B4.14 设有有如图4-334的

59、与/或或/树，请分分别按和代价价法及最大代代价法求解树树的代价。AABCDt2t3t4t1图4.34 习题4.14的与/或树56217223E解：若按和代价价法，则该解解树的代价为为： h(A)=2+3+2+55+2+1+6=21若按最大代价法法，则该解树树的代价为： h(A)=maaxh(BB)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6 = max(max(22, 3)+2)+5, max(2, 1)+6=max(55+5, 22+6)=110 4.115 设有如如图4-355所示的博弈弈树，其中最最下面的数字字是假设的估估值，请对该该博弈树作如如下工作：(1) 计

60、算各各节点的倒推推值；利用-剪枝枝技术剪去不不必要的分枝枝。图4.35 习题4.15的博弈树图4.35 习题4.15的博弈树305-336-2354-3068-3369S0ABCDEFGHIJKLNM 解：各各节点的倒推推值和剪枝情情况如下图所所示：习题4.15的倒推值和剪枝情况习题4.15的倒推值和剪枝情况305-336-2354-3068-336000-39334444-366S0ABCDEFGHIJKMNL第5章 计算算智能部分参参考答案5.15 对对遗传法的选选择操作：设设种群规模为为4，个体采采用二进制编码，适应度度函数为 f(x)=x2，初始种群情况况如下表所示示：编号个体串x适应