人工智能原理及其应用王万森编著习题解答37

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

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

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

4、的上面。 OONTABBLE(xx)：积木木x在桌子上上。 HHOLDIING(xx)：机械械手抓住xx。HANDEEMPTYY：机械手手是空的。其中，x和和y的个体域域都是AA, B, C。问题的初始始状态是：ONTABBLE(AA)ONTABBLE(BB)ON(C, A) CCLEARR(B) CCLEARR(C) HHANDEEMPTYY 问问题的目标标状态是： OONTABBLE(CC) OON(B, C) OON(A, B)CLEARR(A) HANDEEMPTYY(2) 再再定义描述述操作的谓谓词在本问题中中，机械手手的操作需需要定义以以下4个谓谓词： Pickuup(x)：从桌面

5、面上拣起一一块积木xx。 Putdoown(xx)：将手手中的积木木放到桌面面上。Stackk(x, y)：在在积木x上面再摞上一一块积木yy。Upstaack(xx, y)：从积木x上面拣起起一块积木木y。其中，每一一个操作都都可分为条条件和动作作两部分，具具体描述如如下： Pickuup(x) 条件：ONNTABLLE(x)，HANDDEMPTTY，CLEAAR(x) 动作：删删除表：OONTABBLE(xx)，HANDDEMPTTY 添加加表：HANDEEMPTYY(x)Putdoown(xx) 条件：HAANDEMMPTY(x) 动作：删删除表：HHANDEEMPTYY(x) 添加加表

6、：ONNTABLLE(x)，CLEAAR(x) ，HANDDEMPTTYStackk(x, y) 条件：HAANDEMMPTY(x)，CLEAAR(y) 动作：删删除表：HHANDEEMPTYY(x)，CLEAAR(y) 添加加表：HAANDEMMPTY，ON(xx, y) ，CLEEAR(xx)Upstaack(xx, y) 条件：HAANDEMMPTY，CLEAAR(y) ，ON(y,x) 动作：删删除表：HHANDEEMPTYY，ON(y, x) 添加加表：HOLDIING(y)，CLEAAR(x) (3) 问问题求解过过程利用上述谓谓词和操作作，其求解过程为为：ONTABLE(A)ON

7、TABLE(B)ONTABLE(C)CLEAR(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(A,C)Putdown(C)Pickup(B)ONTABLE(A)ONTABLE(C)ON(B,C)CLEAR(A)CLEAR(B)HANDEMPTYONTABLE(A)ONTABLE(C)HOLDING(B)CLEAR(A)CLEAR(B)CLEAR(C)ON

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

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

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

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

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

13、 ，AL(狼狼)，AL(羊羊)，ALL(白菜) 动动作：删除除表：AL(船船)，AL(农农夫)，AL(羊羊) 添加表表：AL(船)，AAL(农夫夫)，ALL(羊)(3) 问问题求解过过程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(船)AL(狼)AL(羊)AL(白菜菜)AL(农夫)AL(船)AL(羊)AL(白菜)AL(狼)AL(农夫)AL(船)AL(羊)AL(白菜)AL(狼)AL(羊)AL(农夫)AL(船)AL(白

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

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

16、下，在z岸，保证证修道士安安全，当且且仅当修道道士不在该该岸上，或者者修道士在在该岸上，但人人数超过野野人数。该该谓词同时时也描述了了相应的状状态。再定义描述述过河方案的谓谓词：L-R(xx, x11, y, y1,S)：x1个修修道士和yy1个野人人渡船从河河的左岸到到河的右岸岸条件：Saafetyy(L,xx-x1,y-y11,S)Safeety(RR,3-xx+x1,3-y+y1,SS)Boatt(L,SS)动作：Saafetyy(L,xx-x1,y-y11,S)Safeety(RR,3-xx+x1,3-y+y1,SS)Boatt(R,SS)R-L (x, xx1, yy, y11,S)

17、：x2个修修道士和yy2个野人人渡船从河河的左岸到到河的右岸岸条件：Saafetyy(R,33-x-xx2,3-y-y2,S)Safeety(LL,x+x2,yy+y2,SS)Boatt(R,SS)动作：Saafetyy(R,33-x-xx2,3-y-y22,S)Safeety(LL,x+xx2,y+y2,SS)Boatt(L,SS) (2) 过过河方案 SSafetty(L,3,3,S0)Safeety(RR,0,00,S0)Boatt(L,SS0) L-R(3, 1, 3, 1,S0) L-RR(3, 0, 33, 2,S0)Safetty(L,2,2,S1)Safeety(RR,1,11

18、,S1)Boatt(R,SS1)Safetty(L,3,1,S1)Safeety(RR,0,22,S1)Boatt(R,SS1)R-L (2, 1, 2, 0,S1) R-L (3,00, 1, 1,SS1)Safetty(L,3,22,S2)Safeety(RR,0,11,S2)Boatt(L,SS2)L-R(33, 0, 2, 2,S22)Safetty(L,3,0,S3)Safeety(RR,0,33,S3)Boatt(R,S3)R-L (3, 00, 0, 1,SS3)Safetty(L,3,1,S4)Safeety(RR,0,22,S1)Boatt(L,SS4)L-R(33, 2,

19、1, 0,S4)Safetty(L,1,1,S5)Safeety(RR,2,22,S5)Boatt(R,SS5)R-L (1, 11, 1, 1,SS5)Safetty(L,2,2,S6)Safeety(RR,1,11,S6)Boatt(L,SS6)L-R(22, 2, 2, 0,S66)Safetty(L,0,2,S7)Safeety(RR,3,11,S7)Boatt(R,SS7)R-L (0, 00, 2, 1,SS7)Safetty(L,0,3,S8)Safeety(RR,3,00,S8)Boatt(L,SS8)L-R(00, 0, 3, 2,S88)Safetty(L,0,1,S9)S

20、afeety(RR,3,22,S9)Boatt(R,SS9)R-L (0, 11, 1, 0,SS9)Safetty(L,1,1,S10)Safeety(RR,2,22,S100)Boatt(L,SS10)L-R(11, 1, 1, 1,S110)Safetty(L,0,0,S11)Safeety(RR,3,33,S111)Boatt(R,SS11)2.18 请对下列命命题分别写写出它们的的语义网络络：(1) 每每个学生都都有一台计计算机。gGSgGSGS解：占有权计算机学生AKOISAISAFOwnsOwnercosg(2) 高高老师从33月到7月月给计算机机系学生讲讲计算机机网络课课。 解

21、解：7月8月StartEnd老师ISAObjectSubject高老师计算机系学生讲课事件ActionCaurse计算机网络讲课(3) 学学习班的学学员有男、有女、有有研究生、有本科生生。 解解：参例22.14(4) 创创新公司在在科海大街街56号，刘刘洋是该公公司的经理理，他322岁、硕士士学位。 解解：参例22.10(5) 红红队与蓝队队进行足球球比赛，最最后以3：2的比分分结束。 解解：比赛AKOParticipants1Outcome3:22足球赛红队Participants 2蓝队2.19 请把下列列命题用一一个语义网网络表示出出来：(1) 树树和草都是是植物；植物解：AKOAKO草

22、树(2) 树树和草都有有叶和根；根叶 解解：HaveHave植物是一种是一种草树(3) 水水草是草，且且生长在水水中； 解解：LiveAKOAKO水草水中植物草(4) 果果树是树，且且会结果； 解解：CanAKOAKO果树结果植物树(5) 梨梨树是果树树中的一种种，它会结结梨。 解解：CanAKOAKO梨树树果树结梨2.25 假设有以以下一段天天气预报：“北京地区区今天白天天晴，偏北北风3级，最最高气温112，最低气气温-2，降水概概率15%。”请用框架架表示这一一知识。解：Framee 地地域：北京京 时时段：今天天白天 天天气：晴 风风向：偏北北 风风力：3级级 气气温：最高高：12度度

23、最低：-2度 降降水概率：15%2.26 按“师生框架架”、“教师框架架”、“学生框架架”的形式写写出一个框框架系统的的描述。解：师生框框架Framee NName：Unitt（Lasst-naame，FFirstt-namme） SSex：AArea（mmale，ffemalle） Defaault：malee AAge：UUnit（YYearss）Telepphonee：Homme UUnit（NNumbeer）Mobille UUnit（NNumbeer） 教师框架Framee AAKO MMajorr：Uniit（Maajor-Namee） LLectuures：Unitt（Couur

24、se-Namee） FFieldd：Uniit（Fiield-Namee） PProjeect ：Areaa（Nattionaal，Prrovinnciall，Othher） DDefauult：PProviinciaal PPaperr：Areea（SCCI，EII，Corre，Geeneraal） Deefaullt：Coore 学生框架Framee AAKO MMajorr：Uniit（Maajor-Namee） CClassses：UUnit（CClassses-NName） DDegreee：Arrea（ddoctoor，maastorr, baachellor） Deefaullt

25、：baachellor 确定性推理理部分参考考答案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(bb)(4) P(f(y), y, xx), PP(x, f(a), f(b) (5) P(x, y), P(yy, x)解：(1) 可合一，其其最一般和和一为：=a/x, b/y。(2) 可合一，其其最一般和和一为：=y/f(x), b/z。(3) 可合一，其其最一般和和一为：= f(b)/y, bb/x。(4) 不可合一一。(5)

26、可合一，其其最一般和和一为：= y/x。3.11 把下列谓谓词公式化化成子句集集：(x)(yy)(P(x, y)Q(x, y)(x)(yy)(P(x, y)Q(x, y)(x)(yy)(P(x, yy)(Q(x, y)R(x, y)(x) (y) (z)(PP(x, y)Q(x, y)R(x, z) 解解：(1) 由于(x)(y)(P(x, y)Q(x, y)已经是SSkoleem标准型型，且P(x, yy)Q(x, y)已已经是合取取范式，所所以可直接接消去全称称量词、合合取词，得得 P(x, y), Q(xx, y) 再再进行变元元换名得子子句集： SS= P(x, y), Q(u, v)

27、 (2) 对对谓词公式式(x)(y)(P(x, y)Q(x, y)，先消去去连接词“”得：(x)(yy)(P(x, y)Q(x, y)此公式已为为Skollem标准准型。 再再消去全称称量词得子子句集： SS=P(x, y)Q(x, y) (3) 对对谓词公式式(x)(y)(P(xx, y)(Q(x, y)R(x, y)，先消消去连接词词“”得：(x)(yy)(P(x, yy)(Q(x, y)R(x, y)此公式已为为前束范式式。再消去存在在量词，即即用Skoolem函函数f(xx)替换yy得：(x)(PP(x, f(x)Q(x, f(xx)R(x, f(xx)此公式已为为Skollem标准准

28、型。 最最后消去全全称量词得得子句集： SS=P(x, ff(x)Q(x, f(x)R(x, f(xx) (4) 对对谓词(x) (y) (z)(PP(x, y)Q(x, y)R(x, z)，先消去去连接词“”得：(x) (y) (z)(P(x, y)Q(x, y)R(x, z)再消去存在在量词，即即用Skoolem函函数f(xx)替换yy得：(x) (y) (P(x, y)Q(x, y)R(x, f(xx,y)此公式已为为Skollem标准准型。 最最后消去全全称量词得得子句集：S=PP(x, y)Q(x, y)R(x, f(xx,y)3-13 判断下下列子句集集中哪些是是不可满足足的：PQ

29、Q, Q, P, P PQQ , PQ, PQ, PQ P(yy)Q(y) , P(f(x)R(a)P(xx)Q(x) , P(y)R(y), P(aa), SS(a), S(z)R(z)P(xx)Q(f(x),aa) , P(hh(y)Q(f(h(y), aa)P(z)P(x)Q(x)R(x) , P(y)R(y), Q(a), R(b) 解解：(1) 不可满满足，其归归结过程为为：PQQPPNIL(2) 不不可满足，其其归结过程程为：PQPQQPQPQQNIL(3) 不不是不可满满足的，原原因是不能能由它导出出空子句。(4) 不不可满足，其其归结过程程略(5) 不不是不可满满足的，原原因是

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

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

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

33、y) 求求证结论GG：(u) (v)( P(u)GF(v,u) 然然后再将FF1，F22和G化成子子句集： F(x,y)F(y,z)GF(x,z) P(r)F(s,r) P(uu) GFF(v,uu) 对对上述扩充充的子句集集，其归结结推理过程程如下：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/ux/s,y/ry/s,z/r y/z y/u 由由于导出了了空子句，故故结论得证证。3.16 假设张张被盗，公公安局派出出5个人去去调查。案案情分析时时，贞察

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

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

36、窃窃犯不止一一人。根据据归结原理理还可以得得出：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(S)C(S)C(Q)C(u)C(u)C(S) S/u C(S) 因因此，孙也也是盗窃犯犯。3.18 设有子子句集： P(x)Q(a, b), P(aa)Q(a, b), Q(aa, f(a), P(xx)Q(x, b)分别用各种种归结策略略求出其归归结式。解：支持集集策略不可可用，原因因是没有指指明哪个子子句是由目目标公式的的否定化简简来的。删除策略不不可用，原原因是子句句集中没有有没有重言言式和具有

37、有包孕关系系的子句。单文字子句句策略的归归结过程如如下：Q(a, f(a)P(x)Q(a, b) b/f(a)P(x)Q(x, b)P(a)Q(a, f(a)Q(a, b) a/x b/f(a)Q(a, b)用线性输入入策略（同同时满足祖祖先过滤策策略）的归归结过程如如下：P(a)Q(a, b)P(x)Q(a, b)P(x)Q(x, b)P(a) a/xa/xQ(a, f(a)Q(a,b) b/f(a)NIL 3.19 设已知知：能阅读的人人是识字的的；海豚不识字字；有些海豚是是很聪明的的。请用归结演演绎推理证证明：有些些很聪明的的人并不识识字。解：第一步步，先定义义谓词， 设R(x)表示x是

38、是能阅读的的；K(y)表表示y是识识字的；W(z) 表示z是是很聪明的的；第二步，将将已知事实实和目标用用谓词公式式表示出来来能阅读的人人是识字的的：(x)(R(xx)K(x)海豚不识字字：(y)(K (y)有些海豚是是很聪明的的：(z) W(z)有些很聪明明的人并不不识字：(x)( W(z)K(xx) 第第三步，将将上述已知知事实和目目标的否定定化成子句句集： R(x)K(x)K (yy)W(z)W(z)K(x) 第四四步，用归归结演绎推推理进行证证明W(z)W(z)K(x)W(z)K(z)NIL3.20 对子句集集： PQ, QQR, RRW, RP, WQ, QR 用线性输入入策略是否否

39、可证明该该子句集的的不可满足足性？ 解解：用线性性输入策略略不能证明明子句集PQ, QR, RRW, RP, WQ, QR 的不可满足足性。原因因是按线性性输入策略略，不存在在从该子句句集到空子子句地归结结过程。3.21 对线性输输入策略和和单文字子子句策略分分别给出一一个反例，以以说明它们们是不完备备的。3.22 分别说说明正向、逆向、双双向与/或或形演绎推推理的基本本思想。3.23 设已知知事实为 (PQ)R) (S(TU) FF规则为 SS(XY)Z试用正向演演绎推理推推出所有可可能的子目目标。解：先给出出已知事实实的与/或或树，再利利用F规则则进行推理理，其规则则演绎系统统如下图所所示

40、。由该图可以以直接写出出所有可能能的目标子子句如下： PPQPQQPQQYRTUU RXZZRYZZ 所有子目标UTZYXRQP所有目标UTZYXRQPYXZXYSUTTUS所有目标UTZYXRQP所有目标YZUTXPRQYXXYF规则ZXYXYZSSUTQPTUQP已知事实已知事实TUSR(PQ)TURS(PQ) (S(TU)(PQ)R) (S(TU)(PQ)R)(PQ)R) (S(TU)(PQ)R) (S(TU)3.24 设有如如下一段知知识：“张、王和和李都属于于高山协会会。该协会会的每个成成员不是滑滑雪运动员员，就是登登山运动员员，其中不不喜欢雨的的运动员是是登山运动动员，不喜喜欢雪的

41、运运动员不是是滑雪运动动员。王不不喜欢张所所喜欢的一一切东西，而而喜欢张所所不喜欢的的一切东西西。张喜欢欢雨和雪。”试用谓词公公式集合表表示这段知知识，这些些谓词公式式要适合一一个逆向的的基于规则则的演绎系系统。试说说明这样一一个系统怎怎样才能回回答问题：“高山俱乐乐部中有没没有一个成成员，他是是一个登山山运动员，但但不是一个个滑雪运动动员？”解：(1) 先定义义谓词A(x) 表示x是是高山协会会会员S(x) 表示x是是滑雪运动动员C(x) 表示x是是登山运动动员L(x,yy) 表示示x 喜欢y (2) 将将问题用谓谓词表示出出来“张、王和和李都属于于高山协会会A(Zhaang)A(Wang)

42、A(Li)高山协会的的每个成员员不是滑雪雪运动员，就就是登山运运动员(x)(AA(x)S(xx)C(x)高山协会中中不喜欢雨雨的运动员员是登山运运动员(x)(L(x, Raiin)C(x)高山协会中中不喜欢雪雪的运动员员不是滑雪雪运动员(x)(L(x, Snoow) S(x)王不喜欢张张所喜欢的的一切东西西(y)( L(Zhhang, y) L(Wangg ,y) 王王喜欢张所所不喜欢的的一切东西西(y)( L(Zhhang, y)L(Waang, y)张喜欢雨和和雪L(Zhaang , Raiin)L(Zhaang , Snoow)(3) 将将问题要求求的答案用用谓词表示示出来高山俱乐部部中

43、有没有有一个成员员，他是一一个登山运运动员，但但不是一个个滑雪运动动员？ (x)( A(x)C(x) S(x) (4) 为为了进行推推理，把问问题划分为为已知事实实和规则两两大部分。假设，划划分如下：已知事实：A(Zhaang)A(Waang)A(Lii)L(Zhaang , Raiin)L(Zhhang , Snnow)规则：(x)(AA(x)S(xx)C(x)(x)(L(x, Raiin)C(x)(x)(L(x, Snoow) S(x)(y)( L(Zhhang, y) L(Wangg ,y)(y)( L(Zhhang, y)L(Waang, y) (5) 把把已知事实实、规则和和目标化成

44、成推理所需需要的形式式事实已经是是文字的合合取形式：f1: AA(Zhaang)A(Waang)A(Lii)f2: LL (Zhhang , Raain)L(Zhhang , Snnow)将规则转化化为后件为为单文字的的形式：r1: AA(x)S(xx)C(x)r2: L(x, Raiin)C(x)r3: L(x, Snoow) S(xx)r4: LL(Zhaang, y) L(WWang ,y)r5: L(Zhhang, y)L(Waang , y) 将将目标公式式转换为与与/或形式式 A(xx)(C(x) S(x) (6) 进进行逆向推推理逆向推理的的关键是要要能够推出出L(Zhhang

45、, Raain)L(Zhhang , Snnow)，其逆向演绎过程如下图所示。 A(x)(C(x) S(x)C(x) S(x) A(x)C(x) S(x)r2r34L(x, Rain)L(x, Snow)Wang/x, y/RainWang /x, y/SnowL(Wang, y)L(Wang, y)r4r4L(Zhang, y)L(Zhang, y)Rain/ySnow/yL(Zhang, Snow)L(Zhang, Rain)PAGE 268PAGE 14搜索策略部部分参考答答案4.5 有有一农夫带带一条狼，一一只羊和一一框青菜与与从河的左左岸乘船倒倒右岸，但但受到下列列条件的限限制：(1

46、) 船船太小，农农夫每次只只能带一样样东西过河河；如果没有农农夫看管，则则狼要吃羊羊，羊要吃吃菜。请设计一个个过河方案案，使得农农夫、浪、羊都能不不受损失的的过河，画画出相应的的状态空间间图。题示：(11) 用四元元组（农夫夫，狼，羊羊，菜）表表示状态，其其中每个元元素都为00或1，用用0表示在在左岸，用用1表示在在右岸。(2) 把把每次过河河的一种安安排作为一一种操作，每每次过河都都必须有农农夫，因为为只有他可可以划船。解：第一步步，定义问问题的描述述形式用四元组SS=（f，ww，s，vv）表示问问题状态，其其中，f，ww，s和vv分别表示示农夫，狼狼，羊和青青菜是否在在左岸，它它们都可以以

47、取1或00，取1表表示在左岸岸，取0表表示在右岸岸。第二步，用用所定义的的问题状态态表示方式式，把所有有可能的问问题状态表表示出来，包包括问题的的初始状态态和目标状状态。由于状态变变量有4个个，每个状状态变量都都有2种取取值，因此此有以下116种可能能的状态：S0=(11,1,11,1)，SS1=(1,1,1,0)，SS2=(1,1,0,1)，SS3=(1,1,0,0)S4=(11,0,11,1)，SS5=(1,0,1,0)，SS6=(1,0,0,1)，SS7=(1,0,0,0)S8=(00,1,11,1)，SS9=(0,1,1,0)，SS10=(00,1,00,1)，SS11=(00,1,0

48、0,0)S12=(0,0,1,1)，S133=(0,0,1,0)，SS14=(00,0,00,1)，SS15=(00,0,00,0)其中，状态态S3，S6，S7，S8，S9，S12是不合合法状态，SS0和S15分别是是初始状态态和目标状状态。第三步，定定义操作，即即用于状态态变换的算算符组F由于每次过过河船上都都必须有农农夫，且除除农夫外船船上只能载载狼，羊和和菜中的一一种，故算算符定义如如下：L(i)表表示农夫从从左岸将第第i样东西西送到右岸岸（i=11表示狼，ii=2表示示羊，i=3表示菜菜，i=00表示船上上除农夫外外不载任何何东西）。由于农夫夫必须在船船上，故对对农夫的表表示省略。R

49、(i)表示农夫夫从右岸将将第i样东东西带到左左岸（i=1表示狼狼，i=22表示羊，ii=3表示示菜，i=0表示船船上除农夫夫外不载任任何东西）。同样，对对农夫的表表示省略。这样，所定定义的算符符组F可以以有以下88种算符：L (0)，L (1)，LL (2)，L (3)R(0)，RR(1)，RR (2)，R (3)第四步，根根据上述定定义的状态态和操作进进行求解。该问题求解解过程的状状态空间图图如下：(1,1,l,1)L(2)(0,1,0,1)R(0)(1,1,0,1)L(3)L(1)(0,1,0,0)(0,0,0,1)R(2)R(2)(1,1,1,0)(1,0,1,1)L(2)L(3)(0,

50、0,1,0)R(0)(1,0,1,0)L(2)(0,0,0,0)4.7 圆圆盘问题。设有大小小不等的三三个圆盘AA、B、C套在一根根轴上，每每个盘上都都标有数字字1、2、3、4，并并且每个圆圆盘都可以以独立的绕绕轴做逆时时针转动，每每次转动990，其初始始状态S0和目标状状态Sg如图4-31所示示，请用广广度优先搜搜索和深度度优先搜索索，求出从从S0到Sg的路径。CC12222222 BAAB42 234131231331414443 初始状态态S0 目标状状态Sg 图 4331 圆盘问题题解：设用qqA，qB和qC分别表示示把A盘，BB盘和C盘盘绕轴逆时时针转动990，这些操操作（算符符）的

51、排列列顺序是qqA，qB，qC。应用广度优优先搜索，可可得到如下下搜索树。在该搜索索树中，重重复出现的的状态不再再划出，节节点旁边的的标识Sii，i=00,1,22,，为按节节点被扩展展的顺序给给出的该节节点的状态态标识。由该图可以以看出，从从初始状态态S0到目标状状态Sg的路径是是S02513(SSg)3221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334

52、213112244qA314241231234qB132314242413qC4.7题的广度优先搜索树S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度优先先搜索略。4.8 图图4-322是5个城城市的交通通图，城市市之间的连连线旁边的的数字是城城市之间路路程的费用用。要求从从A城出发，经经过其它各各城市一次次且仅一次次，最后回回到A城，请找找出一条最最优线路。 A 10 B 22 8 9 C 111 6 3 112 8 D 9 E432 交通费用用图解：这个问问题又称为为旅行商问问题（trravelllingg sallesmaan prrobleem, TTSP）或或货

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

54、价。0A119210102119BDCE98693128386128201917CDB181221ECB10105EDB16E2218DC331288923123868868969126129883C32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426CB2720C1417BE2524DC2621DE6812666E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B302820E28CB21030A30A图4.32的最小代价搜索树可以看出，其其最短路经经是 AA-C-DD-E-BB-A或 AA-B

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

56、x)=每每个W左边边的B的个个数，f(x)=d(xx)+3*h(x)，其搜索索树如下：f(x)=0+12=12BBWWEf(x)=1+12=13BBE WWf(x)=1+12=13BBWE Wf(x)=2+12=14f(x)=2+9=11BBEWWBEWBWf(x)=3+9=12EBWBWf(x)=4+6=10WBE BWf(x)=5+3=8WBWBEf(x)=6+3=9WBWE Bf(x)=7+0=7WBWE B4.14 设有如图图4-344的与/或或/树，请请分别按和和代价法及及最大代价价法求解树树的代价。ABCDt2t3t4t1图4.34 习题4.14的与/或树56217223E解：若按

57、和和代价法，则则该解树的的代价为： h(A)=2+33+2+55+2+11+6=221若按最大代代价法，则则该解树的的代价为： h(A)=maxxh(BB)+5, h(CC)+6 = max(h(EE)+2)+5, h(C)+6 = max(maxx(2, 3)+22)+5, maxx(2, 1)+66=max(5+55, 2+6)=110 44.15 设有如图图4-355所示的博博弈树，其其中最下面面的数字是是假设的估估值，请对对该博弈树树作如下工工作：(1) 计计算各节点点的倒推值值；利用-剪枝技术术剪去不必必要的分枝枝。图4.35 习题4.15的博弈树305-336-2354-3068-

58、3369S0ABCDEFGHIJKLNM 解解：各节点点的倒推值值和剪枝情情况如下图图所示：习题4.15的倒推值和剪枝情况305-336-2354-3068-336000-39334444-366S0ABCDEFGHIJKMNL第5章 计算智能能部分参考考答案5.15 对遗传法法的选择操操作：设种种群规模为为4，个体体采用二进进制编码，适应应度函数为为 f(x)=x2，初始种群群情况如下下表所示：编号个体串x适应值百分比累计百分比比选中次数S01101010S0201004S03110012S0401117若规定选择择概率为1100%,选择算法法为轮盘赌赌算法，且且依次生成成的4个随随机数为0

59、0.42, 0.116, 00.89, 0.771，请填填写上表中中的全部内内容，并求求出经本次次选择操作作后所得到到的新的种种群。解：表格的的完整内容容为：编号个体串x适应值百分比累计百分比比选中次数S0110101010032.36632.3661S0201004165.1837.5440S0311001214444.60084.1442S04011174915.8661001本次选择后后所得到的的新的种群群为： SS01=11100 SS02=10010 SS03=01111 SS04=111005.18 设某小小组有5个个同学，分分别为S1,S2,S3,S4,S5。若对每每个同学的的“

60、学习好”程度打分分： SS1:95 S22:85 S33:80 S44:70 S55:90这样就确定定了一个模模糊集F，它表示示该小组同同学对“学习好”这一模糊糊概念的隶隶属程度，请请写出该模模糊集。 解解：对模糊糊集为F，可可表示为： FF=95/ S1+85/S2+80/ S3+70/S4+90/S5或 FF=955/ S1, 855/S2, 800/ S3, 700/S4, 900/S5 55.19 设有论论域 UU=u11, u2, u3, u4, u5并设F、GG是U上的两个个模糊集，且且有 FF=0.99/u1+0.77/u2+0.55/u3+0.33/u4 GG=0.66/u3+