人工智能經(jīng)典試題及答案

1、PAGE 268PAGE 88 知識表示方法部分參考答案 2.8 設(shè)有如如下語句，請請用相應(yīng)的謂謂詞公式分別別把他們表示示出來：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) 新型計計算機(jī)

2、速度又又快，存儲容容量又大。解：定義謂詞NC(x)：xx是新型計算算機(jī)F(x)：x速速度快 B(x)：x容容量大將知識用謂詞表表示為：(x) (NCC(x)F(x)B(x)(4) 不是每每個計算機(jī)系系的學(xué)生都喜喜歡在計算機(jī)機(jī)上編程序。解：定義謂詞S(x)：x是是計算機(jī)系學(xué)學(xué)生L(x, prragrammming)：x喜歡編編程序U(x,commputerr)：x使用用計算機(jī)將知識用謂詞表表示為： (x) (S(x)L(x, pragrramminng)U(x,ccomputter)(5) 凡是喜喜歡編程序的的人都喜歡計計算機(jī)。解：定義謂詞P(x)：x是是人L(x, y)：x喜歡yy將知識用謂詞

3、表表示為：(x) (P(x)L(x,ppragraammingg)L(x, compuuter)2.9 用謂詞詞表示法求解解機(jī)器人摞積積木問題。設(shè)設(shè)機(jī)器人有一一只機(jī)械手，要要處理的世界界有一張桌子子，桌上可堆堆放若干相同同的方積木塊塊。機(jī)械手有有4個操作積積木的典型動動作：從桌上上揀起一塊積積木；將手中中的積木放到到桌之上；在在積木上再摞摞上一塊積木木；從積木上上面揀起一塊塊積木。積木木世界的布局局如下圖所示示。AABCCACABB圖 機(jī)器人摞摞積木問題解：(1) 先先定義描述狀狀態(tài)的謂詞 CLEEAR(x)：積木x上面是空的的。 ON(x, y)：積木x在積木y的上面。 ONTTABLE(x

4、)：積木木x在桌子上。 HOLLDING(x)：機(jī)械械手抓住x。HANDEMPPTY：機(jī)械械手是空的。其中，x和y的的個體域都是是A, BB, C。問題的初始狀態(tài)態(tài)是：ONTABLEE(A)ONTABLEE(B)ON(C, AA) CLEEAR(B) CLEEAR(C) HANNDEMPTTY 問題的的目標(biāo)狀態(tài)是是： ONTTABLE(C) ON(B, C) ON(A, B)CLEAR(AA) HANDEMPPTY(2) 再定義義描述操作的的謂詞在本問題中，機(jī)機(jī)械手的操作作需要定義以以下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 用謂謂詞表示法求求解農(nóng)夫、狼狼、山羊、白白菜問題。農(nóng)農(nóng)夫、狼、山山羊、白菜全全部放在一條條河的左岸，現(xiàn)現(xiàn)在要把他們們?nèi)克偷胶雍拥挠野度?，農(nóng)農(nóng)夫有一條船船，過河時，除除農(nóng)夫外船上上至多能載狼狼、山羊、白白菜中的一種種。狼要吃山山羊，山羊要要吃白菜，除除非農(nóng)夫在那那里。似規(guī)劃劃出一個確保保全部安全過過河的計劃。請

9、請寫出所用謂謂詞的定義，并并給出每個謂謂詞的功能及及變量的個體體域。解：(1) 先先定義描述狀狀態(tài)的謂詞要描述這個問題題，需要能夠夠說明農(nóng)夫、狼狼、羊、白菜菜和船在什么么位置，為簡簡化問題表示示，取消船在在河中行駛的的狀態(tài)，只描描述左岸和右右岸的狀態(tài)。并并且，由于左左岸和右岸的的狀態(tài)互補(bǔ)，因因此可僅對左左岸或右岸的的狀態(tài)做直接接描述。本題題選擇對左岸岸進(jìn)行直接描描述的方法，即即定義謂詞如如下：AL(x)：xx在左岸其中，x的個體體域是農(nóng)夫夫，船，狼，羊羊，白菜。對對應(yīng)地，AL(x)表示x在右右岸。 問題的的初始狀態(tài)：AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(白菜) 問題的的目標(biāo)狀態(tài)：AL

10、(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(白菜) (2) 再定定義描述操作作的謂詞本題需要以下44個描述操作作的謂詞：L-R：農(nóng)夫自自己劃船從左左岸到右岸L-R(x)：農(nóng)夫帶著xx劃船從左岸岸到右岸R-L：農(nóng)夫自自己劃船從右右岸到左岸R-L(x) ：農(nóng)夫帶著著x劃船從右右岸到左岸其中，x的個體體域是狼，羊羊，白菜。對上述每個操作作，都包括條條件和動作兩兩部分。它們們對應(yīng)的條件件和動作如下下：L-R：農(nóng)夫劃劃船從左岸到到右岸 條件：AL(船)，AL(農(nóng)農(nóng)夫)，AL(狼)AL(羊羊)，AL(羊)AL(白白菜) 動作：刪除表：AAL(船)，AAL(農(nóng)夫) 添加加表：AL(船)，AL(農(nóng)夫夫)L-R

11、(狼)：農(nóng)夫帶著狼狼劃船從左岸岸到右岸 條件：AL(船)，AL(農(nóng)農(nóng)夫)，ALL(狼)，AL(羊) 動作：刪除表：AAL(船)，AAL(農(nóng)夫)，AL(狼狼) 添加加表：AL(船)，AL(農(nóng)夫夫)，AL(狼)L-R(羊)：農(nóng)夫帶著羊羊劃船從左岸岸到右岸 條件：AL(船)，AL(農(nóng)農(nóng)夫)，ALL(羊)， AL(狼)，AL(白白菜) 或：AAL(船)，AAL(農(nóng)夫)，AL(羊羊)，AL(狼)，AL(白菜菜) 動作：刪除表：AAL(船)，AAL(農(nóng)夫)，AL(羊羊) 添加加表：AL(船)，AL(農(nóng)夫夫)，AL(羊)L-R(白菜)：農(nóng)夫帶著著白菜劃船從從左岸到右岸岸 條件：AL(船)，AL(農(nóng)農(nóng)夫)，A

12、LL(白菜)，AL(狼) 動作：刪除表：AAL(船)，AAL(農(nóng)夫)，AL(白白菜) 添加加表：AL(船)，AL(農(nóng)夫夫)，AL(白菜菜)R-L：農(nóng)夫劃劃船從右岸到到左岸 條件：AL(船)，AL(農(nóng)夫夫)，AL(狼)AL(羊)，AL(羊羊)AL(白菜菜) 或：AL(船)，AL(農(nóng)夫夫) ，AL(狼)，AL(白菜菜)，AL(羊) 動作：刪除表：AL(船)，AL(農(nóng)夫夫) 添加加表：AL(船)，ALL(農(nóng)夫)R-L(羊) ：農(nóng)夫帶著著羊劃船從右右岸到左岸 條件：AL(船)，AL(農(nóng)夫夫)，AL(羊) ，AL(狼)，AL(羊)，AL(白白菜) 動作：刪除表：AL(船)，AL(農(nóng)夫夫)，AL(羊) 添

13、加加表：AL(船)，ALL(農(nóng)夫)，AAL(羊)(3) 問題求求解過程AL(白菜)AL(農(nóng)夫)AL(白菜)AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(農(nóng)夫)AL(船)AL(狼)AL(白菜)AL(羊)AL(狼)AL(白菜)AL(農(nóng)夫)AL(船)AL(羊)R-L R-L(羊) L-R(狼)L-R(羊)AL(船)R-L R-L(羊) L-R(狼)L-R(羊)AL(狼)AL(羊)AL(白菜)AL(農(nóng)夫)AL(船)AL(羊)AL(農(nóng)夫)AL(船)AL(羊)AL(白菜)AL(狼)AL(農(nóng)夫)AL(船)AL(羊)AL(白菜)AL(狼)AL(羊)AL(農(nóng)夫)AL(船)AL(白菜)AL(狼)L-R(羊)AL

14、(農(nóng)夫)L-R(羊)AL(農(nóng)夫)AL(船)AL(羊)AL(白菜)AL(狼)R-L L-R(白菜)2.11 用謂謂詞表示法求求解修道士和和野人問題。在在河的北岸有有三個修道士士、三個野人人和一條船，修修道士們想用用這條船將所所有的人都運運過河去，但但要受到以下下條件限制：(1) 修道士士和野人都會會劃船，但船船一次只能裝裝運兩個人。(2) 在任何何岸邊，野人人數(shù)不能超過過修道士，否否則修道士會會被野人吃掉掉。假定野人愿意服服從任何一種種過河安排，請請規(guī)劃出一種種確保修道士士安全的過河河方案。要求求寫出所用謂謂詞的定義、功功能及變量的的個體域。解：（1）定義義謂詞先定義修道士和和野人人數(shù)關(guān)關(guān)系的謂

15、詞：G(x,y,SS)： 在狀狀態(tài)S下x大大于yGE(x,y,S)：在狀狀態(tài)S下x大大于或等于yy其中，x,y分分別代表修道道士人數(shù)和野野人數(shù)，他們們的個體域均均為0,11,2,3。再定義船所在岸岸的謂詞和修修道士不在該該岸上的謂詞詞：Boat(z,S)：狀態(tài)態(tài)S下船在zz岸EZ(x,S)： 狀態(tài)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的含義同同上。該謂詞詞的含義是：狀態(tài)S下，在在z岸，保證證修道士安全全，當(dāng)且僅

16、當(dāng)當(dāng)修道士不在在該岸上，或或者修道士在在該岸上，但但人數(shù)超過野野人數(shù)。該謂謂詞同時也描描述了相應(yīng)的的狀態(tài)。再定義描述過河河方案的謂詞詞：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 請對對下列命題分分別寫出它們們的語義網(wǎng)絡(luò)絡(luò)：(1) 每個學(xué)學(xué)生都有一臺臺計算機(jī)。gGSgGSGS解：gGSgGSGS占有權(quán)計算機(jī)學(xué)生占有權(quán)計算機(jī)學(xué)生AKOISAISAFAKOISAISAFOwnsOwnerOwnsOwnercosgcosg(2) 高老師師從3月到77月給計算機(jī)機(jī)系學(xué)生講計計算機(jī)網(wǎng)絡(luò)課課。 解：7月8月7月8月StartEndStartEnd老師ISAObje

21、ctSubject高老師計算機(jī)系學(xué)生講課事件老師ISAObjectSubject高老師計算機(jī)系學(xué)生講課事件ActionCaurseActionCaurse計算機(jī)網(wǎng)絡(luò)講課計算機(jī)網(wǎng)絡(luò)講課(3) 學(xué)習(xí)班班的學(xué)員有男男、有女、有有研究生、有有本科生。 解：參參例2.144(4) 創(chuàng)新公公司在科海大大街56號，劉劉洋是該公司司的經(jīng)理，他他32歲、碩碩士學(xué)位。 解：參參例2.100(5) 紅隊與與藍(lán)隊進(jìn)行足足球比賽，最最后以3：22的比分結(jié)束束。 解：比賽比賽AKOAKOParticipants1Outcome3:22Participants1Outcome3:22足球賽紅隊紅隊Participants

22、2Participants 2藍(lán)隊藍(lán)隊2.19 請把把下列命題用用一個語義網(wǎng)網(wǎng)絡(luò)表示出來來：(1) 樹和草草都是植物；植物解：植物AKOAKOAKOAKO草樹草樹(2) 樹和草草都有葉和根根；根葉 解：根葉HaveHaveHaveHave植物植物是一種是一種是一種是一種草樹草樹(3) 水草是是草，且生長長在水中； 解：LiveAKOAKO水草LiveAKOAKO水草水中植物草水中植物草(4) 果樹是是樹，且會結(jié)結(jié)果； 解：CanAKOAKO果樹CanAKOAKO果樹結(jié)果植物樹結(jié)果植物樹(5) 梨樹是是果樹中的一一種，它會結(jié)結(jié)梨。 解：CanAKOAKO梨樹CanAKOAKO梨樹樹果樹結(jié)梨樹果樹

23、結(jié)梨2.25 假設(shè)設(shè)有以下一段段天氣預(yù)報：“北京地區(qū)今今天白天晴，偏偏北風(fēng)3級，最最高氣溫122，最低氣溫溫-2，降水概率率15%?！闭堄每蚣鼙肀硎具@一知識識。解：Frame 地域：北京 時段：今天白天 天氣：晴 風(fēng)向：偏北 風(fēng)力：3級 氣溫：最高：122度 最低低：-2度 降水概概率：15%2.26 按“師生框架”、“教師框架”、“學(xué)生框架”的形式寫出出一個框架系系統(tǒng)的描述。解：師生框架Frame Namme：Uniit（Lasst-namme，F(xiàn)irrst-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 學(xué)生框架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)已經(jīng)經(jīng)是Skollem標(biāo)準(zhǔn)型型，且P(xx, y)Q

27、(x, y)已經(jīng)是是合取范式，所所以可直接消消去全稱量詞詞、合取詞，得得 P(x, y), Q(x, y) 再進(jìn)行行變元換名得得子句集： 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標(biāo)標(biāo)準(zhǔn)型。 再消去去全稱量詞得得子句集： 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函函數(shù)f(x)替換y得：(x)(P(xx, f(xx)Q(x, f(x)R(x, f(x)此公式已為Skkolem標(biāo)標(biāo)準(zhǔn)型。 最后消消去全稱量詞詞得子句集： 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函函數(shù)f(x)替換y得：(x) (y) (P(x, y)Q(x, y)R(x, f(x,yy)此公式已為Skkolem標(biāo)標(biāo)準(zhǔn)型。 最后消消去全

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) 不可可滿足，其歸歸結(jié)過程為：PQQPPNIL(2) 不可滿滿足，其歸結(jié)結(jié)過程為：PPQPQQPQPQQNIL(3) 不

30、是不不可滿足的，原原因是不能由由它導(dǎo)出空子子句。(4) 不可滿滿足，其歸結(jié)結(jié)過程略(5) 不是不不可滿足的，原原因是不能由由它導(dǎo)出空子子句。(6) 不可滿滿足，其歸結(jié)結(jié)過程略 3.114 對下列各各題分別證明明G是否為F1,F2,Fn的邏輯結(jié)論論：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進(jìn)行歸結(jié)：PP(x,b)P(a,b)NIL a/xxNIL 所以，G是F的邏輯結(jié)論(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)因此，擴(kuò)充的子子句集為：S= P(xx)，(Q(a)Q(b)， P(x) Q(x) 再對SS進(jìn)行歸結(jié)：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的邏輯結(jié)論 同理可可求得(3)、(4)和和(5)，其其求解過程略略。 3.15 設(shè)設(shè)已知：如果x是y的父父親，y是z的父親，則則x是z的祖父；每個人都有一個個父親。使用歸結(jié)演繹推推理證明：對對于某人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) 求證結(jié)結(jié)論G：(u) (v)( P(uu)GF(v,uu) 然后再再將F1，F(xiàn)F2和G化成子句句集： F(x,yy)F(y,zz)GF(x,zz) P(r)F(s,rr) P(u) GF(vv,u) 對上述述擴(kuò)充的子句句集，其歸結(jié)結(jié)推理過程如如下：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 由于導(dǎo)導(dǎo)出了空子句句，故結(jié)論得得證。3

34、.16 假假設(shè)張被盜，公公安局派出55個人去調(diào)查查。案情分析析時，貞察員員A說：“趙與錢中至至少有一個人人作案”，貞察員B說：“錢與孫中至至少有一個人人作案”，貞察員C說：“孫與李中至至少有一個人人作案”，貞察員D說：“趙與孫中至至少有一個人人與此案無關(guān)關(guān)”，貞察員E說：“錢與李中至至少有一個人人與此案無關(guān)關(guān)”。如果這55個偵察員的的話都是可信信的，使用歸歸結(jié)演繹推理理求出誰是盜盜竊犯。解：(1) 先先定義謂詞和和常量設(shè)C(x)表示示x作案，ZZ表示趙，QQ表示錢，SS表示孫，LL表示李(2) 將已知知事實用謂詞詞公式表示出出來趙與錢中至少有有一個人作案案：C(Z)C(Q)錢與孫中至少有有一個

35、人作案案：C(Q)C(S)孫與李中至少有有一個人作案案：C(S)C(L)趙與孫中至少有有一個人與此此案無關(guān)： (C (ZZ)C(S)，即 C (Z) C(S)錢與李中至少有有一個人與此此案無關(guān)： (C (QQ)C(L)，即 C (Q) C(L)(3) 將所要要求的問題用用謂詞公式表表示出來，并并與其否定取取析取。設(shè)作案者為u，則則要求的結(jié)論論是C(u)。將其與其其否)取析取取，得： C(u) C(u)(4) 對上述述擴(kuò)充的子句句集，按歸結(jié)結(jié)原理進(jìn)行歸歸結(jié)，其修改改的證明樹如如下：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、因此，錢錢是盜竊犯。實實際上，本案案的盜竊犯不不止一人。根根據(jù)歸結(jié)原理理還可以得出出：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 設(shè)設(shè)有子句集： P(x)Q(a, b), PP(a)Q(a, b), QQ(a, ff(a), P(x)Q(x, b)分別用各種歸結(jié)結(jié)策略求出其其歸結(jié)式。解：支持集策略略不可用，原原因是沒有指指明哪個子句句是由目標(biāo)公公式的否定

37、化化簡來的。刪除策略不可用用，原因是子子句集中沒有有沒有重言式式和具有包孕孕關(guān)系的子句句。單文字子句策略略的歸結(jié)過程程如下：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)用線性輸入策略略（同時滿足足祖先過濾策策略）的歸結(jié)結(jié)過程如下：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 設(shè)設(shè)已知：能閱讀的人是識識字的；海豚不識字；有些海豚是很聰聰明的。請用歸結(jié)演繹推推理證明：有有些很聰明的的人并不識字字。解：第一步，先先定義謂詞， 設(shè)R(x)表示示x是能閱讀讀的；K(y)表示yy是識字的；W(z) 表示示z是很聰明明的；第二步，將已知知事實和目標(biāo)標(biāo)用謂詞公式式表示出來能閱讀的人是識識字的：(xx)(R(xx)K(x)海豚不識字：(y)(K (y)有些海豚是很聰聰明的：(zz) W(zz)有些很聰明的人人并不識字：(x)( W(z)K(x) 第三步步，將上述已已知事實和目目標(biāo)的否定化化成子句集： R(x)K(x)K (y)W(z)W(z)KK(x) 第四步，用用歸

39、結(jié)演繹推推理進(jìn)行證明明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 的不可滿足性。原原因是按線性性輸入策略，不不存在從該子子句集到空子子句地歸結(jié)過過程。3.21 對對線性輸入策策略和單文字字子句策略分分別給出一個個反例，以說說明它們是不不完備的。3.22 分分別說明正向向、逆向、雙雙向與/或形形演繹推理的的基本思想。3.23 設(shè)設(shè)已知事實為為 (PQ)R)

40、 (S(TU) F規(guī)則則為 S(XY)Z試用正向演繹推推理推出所有有可能的子目目標(biāo)。解：先給出已知知事實的與/或樹，再利利用F規(guī)則進(jìn)進(jìn)行推理，其其規(guī)則演繹系系統(tǒng)如下圖所所示。由該圖可以直接接寫出所有可可能的目標(biāo)子子句如下： PQQPQPQYYRTU RXZRYZ 所有子目標(biāo)UTZYXRQP所有目標(biāo)UTZYXRQPYXZXYSUTTUS所有目標(biāo)UTZYXRQP所有目標(biāo)YZU所有子目標(biāo)UTZYXRQP所有目標(biāo)UTZYXRQPYXZXYSUTTUS所有目標(biāo)UTZYXRQP所有目標(biāo)YZUTXPRQYXXYYXXYF規(guī)則F規(guī)則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 設(shè)設(shè)有如下一段段知識：“張、王和李都都屬于高山協(xié)協(xié)會。該協(xié)會會的每個成員員不是滑雪運運動員，就是是登山運動員員，其中不喜喜歡雨的運動動員是登山運運動員，不喜喜歡雪的運動動員不是滑雪雪運動員。王王不喜歡張所所喜歡的一切切東西，而喜喜歡張所不喜喜歡的一切東東西。張喜歡歡雨和雪。”試用謂詞公式集集合表示這段段知識，這些些謂詞公式要要適合一個逆逆向的基于規(guī)規(guī)則的演繹系系統(tǒng)。試說明明這樣一個系系統(tǒng)怎樣才能能回答問

42、題：“高山俱樂部中中有沒有一個個成員，他是是一個登山運運動員，但不不是一個滑雪雪運動員？”解：(1) 先先定義謂詞A(x) 表示示x是高山協(xié)協(xié)會會員S(x) 表示示x是滑雪運運動員C(x) 表示示x是登山運運動員L(x,y) 表示x 喜喜歡y (2) 將問題題用謂詞表示示出來“張、王和李都都屬于高山協(xié)協(xié)會A(Zhangg)A(Wanng)A(Li)高山協(xié)會的每個個成員不是滑滑雪運動員，就就是登山運動動員(x)(A(xx)S(x)C(x)高山協(xié)會中不喜喜歡雨的運動動員是登山運運動員(x)(L(x, Raain)C(x)高山協(xié)會中不喜喜歡雪的運動動員不是滑雪雪運動員(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) 為了進(jìn)行行推理，把問問題劃分為已已知事實和規(guī)規(guī)則兩大部分分。假設(shè)，劃劃分如下：已知事實：A(Zhangg)A(Wanng)A(Li)L(Zhangg , Raa

44、in)L(Zhaang , Snow)規(guī)則：(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) 把已知事事實、規(guī)則和和目標(biāo)化成推推理所需要的的形式事實已經(jīng)是文字字的合取形式式：f1: A(ZZhang)A(Wanng)A(Li)f2: L (Zhangg , Raain)L(Zhaang , Snow)將規(guī)則轉(zhuǎn)化為后后件為單文字字的形式：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) 將目標(biāo)標(biāo)公式轉(zhuǎn)換為為與/或形式式 A(x)(C(x) S(x) (6) 進(jìn)行逆向向推理逆向推理的關(guān)鍵鍵是要能夠推推出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 有一農(nóng)農(nóng)夫帶一條狼狼，一只羊和和一框青菜與與從河的左岸岸乘船倒右岸岸，但受到下下列條件的限限制：(1) 船太小小，農(nóng)夫每次次只能帶一樣樣?xùn)|西過河；如果沒有農(nóng)夫看看管，則狼要要吃羊，羊要要吃菜。請設(shè)計一個過河河方案，使得得農(nóng)夫、浪、羊羊都能不受損損失的過河，畫畫出相應(yīng)的狀狀態(tài)空間

47、圖。題示：(1) 用四元組（農(nóng)農(nóng)夫，狼，羊羊，菜）表示示狀態(tài)，其中中每個元素都都為0或1，用用0表示在左左岸，用1表表示在右岸。(2) 把每次次過河的一種種安排作為一一種操作，每每次過河都必必須有農(nóng)夫，因因為只有他可可以劃船。解：第一步，定定義問題的描描述形式用四元組S=（ff，w，s，vv）表示問題題狀態(tài)，其中中，f，w，ss和v分別表表示農(nóng)夫，狼狼，羊和青菜菜是否在左岸岸，它們都可可以取1或00，取1表示示在左岸，取取0表示在右右岸。第二步，用所定定義的問題狀狀態(tài)表示方式式，把所有可可能的問題狀狀態(tài)表示出來來，包括問題題的初始狀態(tài)態(tài)和目標(biāo)狀態(tài)態(tài)。由于狀態(tài)變量有有4個，每個個狀態(tài)變量都都有2

48、種取值值，因此有以以下16種可可能的狀態(tài)：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)其中，狀態(tài)S33，S6，S7，S8，S9，S12是不合法法狀態(tài)，S00和S15分別是初初始狀態(tài)和目

49、目標(biāo)狀態(tài)。第三步，定義操操作，即用于于狀態(tài)變換的的算符組F由于每次過河船船上都必須有有農(nóng)夫，且除除農(nóng)夫外船上上只能載狼，羊羊和菜中的一一種，故算符符定義如下：L(i)表示農(nóng)農(nóng)夫從左岸將將第i樣?xùn)|西西送到右岸（ii=1表示狼狼，i=2表表示羊，i=3表示菜，ii=0表示船船上除農(nóng)夫外外不載任何東東西）。由于于農(nóng)夫必須在在船上，故對對農(nóng)夫的表示示省略。R (i)表示示農(nóng)夫從右岸岸將第i樣?xùn)|東西帶到左岸岸（i=1表表示狼，i=2表示羊，ii=3表示菜菜，i=0表表示船上除農(nóng)農(nóng)夫外不載任任何東西）。同同樣，對農(nóng)夫夫的表示省略略。這樣，所定義的的算符組F可可以有以下88種算符：L (0)，LL (1)，

50、LL (2)，LL (3) R(0)，R(1)，R (2)，RR (3)第四步，根據(jù)上上述定義的狀狀態(tài)和操作進(jìn)進(jìn)行求解。該問題求解過程程的狀態(tài)空間間圖如下：(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 圓盤問問題。設(shè)有大大小不等的三三個圓盤A、B、C套在一根軸軸上，每個盤盤上都標(biāo)有數(shù)數(shù)字1、2、33、4，并且且每個圓盤都都可以獨立的的繞軸做逆時時針轉(zhuǎn)動，每每次轉(zhuǎn)動900，其初始狀狀態(tài)S0和目標(biāo)狀態(tài)態(tài)Sg如圖4-331所示，請請用廣度優(yōu)先先搜索和深度度優(yōu)先搜索，求求出從S0到Sg的路徑。CC12222222 CC12222222BAAB42 BAAB42234131231331412341312313314144444343 初始始狀態(tài)S0 目標(biāo)狀態(tài)態(tài)Sg 圖 431 圓盤問題解：設(shè)用qA，qqB和qC分別表示

52、把把A盤，B盤盤和C盤繞軸軸逆時針轉(zhuǎn)動動90，這些操作作（算符）的的排列順序是是qA，qB，qC。應(yīng)用廣度優(yōu)先搜搜索，可得到到如下搜索樹樹。在該搜索索樹中，重復(fù)復(fù)出現(xiàn)的狀態(tài)態(tài)不再劃出，節(jié)節(jié)點旁邊的標(biāo)標(biāo)識Si，i=0,1,2,，為按節(jié)點點被擴(kuò)展的順順序給出的該該節(jié)點的狀態(tài)態(tài)標(biāo)識。由該圖可以看出出，從初始狀狀態(tài)S0到目標(biāo)狀態(tài)態(tài)Sg的路徑是S02513(Sg)323221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC41341233233412333131312442241

53、2344123412313324112244qC334213112244qA314241231234qB132314242413qC4.7題的廣度優(yōu)先搜索樹S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索索略。4.8 圖4-32是5個個城市的交通通圖，城市之之間的連線旁旁邊的數(shù)字是是城市之間路路程的費用。要要求從A城出發(fā)，經(jīng)經(jīng)過其它各城城市一次且僅僅一次，最后后回到A城，請找出出一條最優(yōu)線線路。 A 10 BB 2 8 9 CC 111 66 3 12 8 D 9 EE432 交通通費用圖解：這個問題又又稱為旅行商商問題（trravellling ssalesmm

54、an prroblemm, TSPP）或貨郎擔(dān)擔(dān)問題，是一一個較有普遍遍性的實際應(yīng)應(yīng)用問題。根根據(jù)數(shù)學(xué)理論論，對n個城城市的旅行商商問題，其封封閉路徑的排排列總數(shù)為： (nn!)/n=(n-1)!其計算量相當(dāng)大大。例如，當(dāng)當(dāng)n=20時時，要窮舉其其所有路徑，即即使用一個每每秒一億次的的計算機(jī)來算算也需要3550年的時間間。因此，對對這類問題只只能用搜索的的方法來解決決。下圖是對圖4-32按最小小代價搜索所所得到的搜索索樹，樹中的的節(jié)點為城市市名稱，節(jié)點點邊上的數(shù)字字為該節(jié)點的的代價g。其其計算公式為為 g(nni+1)=gg(ni)+c(nni, ni+11)其中，c(nii,ni+1)為節(jié)節(jié)

55、點ni到ni+1節(jié)點的的邊代價。0A0A119210119210102119BDCE102119BDCE9869312838612898693128386128201917CDB181221ECB10105EDB16E2218DC201917CDB181221ECB10105EDB16E2218DC331288933128892312386886896912612988323123868868969126129883C32B222925DC2020EBB16D191622DE31E25CC32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426

56、CB2720C1417BE2524DC2621DE9838E12912BD272426CB2720C1417BE2524DC2621DE68126666812666E3133E9328D31B926B26E831B28DD273E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B30282023E35ED27D32C34B302820E28CBE28CB21021030A30A30A30A圖4.32的最小代價搜索樹圖4.32的最小代價搜索樹可以看出，其最最短路經(jīng)是 A-CC-D-E-B-A或 A-BB-E-D-C-A其實，它們是同同一條路經(jīng)。4.11

57、 設(shè)有有如下結(jié)構(gòu)的的移動將牌游游戲：BBWWE其中，B表示黑黑色將牌，WW表是白色將將牌，E表示空格。游游戲的規(guī)定走走法是：(1) 任意一一個將牌可移移入相鄰的空空格，規(guī)定其其代價為1；(2) 任何一一個將牌可相相隔1個其它的將將牌跳入空格格，其代價為為跳過將牌的的數(shù)目加1。游戲要達(dá)到的目目標(biāo)什是把所所有W都移到B的左邊。對對這個問題，請請定義一個啟啟發(fā)函數(shù)h(n)，并給給出用這個啟啟發(fā)函數(shù)產(chǎn)生生的搜索樹。你你能否判別這這個啟發(fā)函數(shù)數(shù)是否滿足下下解要求？再再求出的搜索索樹中，對所所有節(jié)點是否否滿足單調(diào)限限制？解：設(shè)h(x)=每個W左左邊的B的個個數(shù)，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 設(shè)有有如圖4-334的

59、與/或或/樹，請分分別按和代價價法及最大代代價法求解樹樹的代價。AABCDt2t3t4t1圖4.34 習(xí)題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 設(shè)有如如圖4-355所示的博弈弈樹，其中最最下面的數(shù)字字是假設(shè)的估估值，請對該該博弈樹作如如下工作：(1) 計

60、算各各節(jié)點的倒推推值；利用-剪枝枝技術(shù)剪去不不必要的分枝枝。圖4.35 習(xí)題4.15的博弈樹圖4.35 習(xí)題4.15的博弈樹305-336-2354-3068-3369S0ABCDEFGHIJKLNM 解：各各節(jié)點的倒推推值和剪枝情情況如下圖所所示：習(xí)題4.15的倒推值和剪枝情況習(xí)題4.15的倒推值和剪枝情況305-336-2354-3068-336000-39334444-366S0ABCDEFGHIJKMNL第5章 計算算智能部分參參考答案5.15 對對遺傳法的選選擇操作：設(shè)設(shè)種群規(guī)模為為4，個體采采用二進(jìn)制編碼，適應(yīng)度度函數(shù)為 f(x)=x2，初始種群情況況如下表所示示：編號個體串x適應(yīng)