人工智能原理及其應(yīng)用第2版》王萬森編著電子工業(yè)出版社課后習(xí)題答案37.doc

第2章 知識表示方法部分參考答案2.8 設(shè)有如下語句，請用相應(yīng)的謂詞公式分別把他們表示出來：(1) 有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花 。解：定義謂詞P(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是下午將知識用謂詞表示為：(x )(y) (A(y)B(x)P(x)(3) 新型計算機速度又快，存儲容量又大。解：定義謂詞NC(x)：x是新型計算機F(x)：x速度快B(x)：x容量大將知識用謂詞表示為：(x) (NC(x)F(x)B(x)(4) 不是每個計算機系的學(xué)生都喜歡在計算機上編程序。解：定義謂詞S(x)：x是計算機系學(xué)生L(x, pragramming)：x喜歡編程序U(x,computer)：x使用計算機將知識用謂詞表示為： (x) (S(x)L(x, pragramming)U(x,computer)(5) 凡是喜歡編程序的人都喜歡計算機。解：定義謂詞P(x)：x是人L(x, y)：x喜歡y將知識用謂詞表示為：(x) (P(x)L(x,pragramming)L(x, computer)2.9 用謂詞表示法求解機器人摞積木問題。設(shè)機器人有一只機械手，要處理的世界有一張桌子，桌上可堆放若干相同的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如下圖所示。ABCCAB圖 機器人摞積木問題解：(1) 先定義描述狀態(tài)的謂詞 CLEAR(x)：積木x上面是空的。 ON(x, y)：積木x在積木y的上面。 ONTABLE(x)：積木x在桌子上。 HOLDING(x)：機械手抓住x。HANDEMPTY：機械手是空的。其中，x和y的個體域都是A, B, C。問題的初始狀態(tài)是：ONTABLE(A)ONTABLE(B)ON(C, A) CLEAR(B) CLEAR(C) HANDEMPTY 問題的目標(biāo)狀態(tài)是： ONTABLE(C) ON(B, C) ON(A, B)CLEAR(A) HANDEMPTY(2) 再定義描述操作的謂詞在本問題中，機械手的操作需要定義以下4個謂詞： Pickup(x)：從桌面上揀起一塊積木x。 Putdown(x)：將手中的積木放到桌面上。Stack(x, y)：在積木x上面再摞上一塊積木y。Upstack(x, y)：從積木x上面揀起一塊積木y。其中，每一個操作都可分為條件和動作兩部分，具體描述如下： Pickup(x) 條件：ONTABLE(x)，HANDEMPTY，CLEAR(x) 動作：刪除表：ONTABLE(x)，HANDEMPTY 添加表：HANDEMPTY(x)Putdown(x) 條件：HANDEMPTY(x) 動作：刪除表：HANDEMPTY(x) 添加表：ONTABLE(x)，CLEAR(x) ，HANDEMPTYStack(x, y) 條件：HANDEMPTY(x)，CLEAR(y) 動作：刪除表：HANDEMPTY(x)，CLEAR(y) 添加表：HANDEMPTY，ON(x, y) ，CLEAR(x)Upstack(x, y) 條件：HANDEMPTY，CLEAR(y) ，ON(y,x) 動作：刪除表：HANDEMPTY，ON(y, x) 添加表：HOLDING(y)，CLEAR(x) (3) 問題求解過程利用上述謂詞和操作，其求解過程為：ONTABLE(A)ONTABLE(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)ONTABLE(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 用謂詞表示法求解農(nóng)夫、狼、山羊、白菜問題。農(nóng)夫、狼、山羊、白菜全部放在一條河的左岸，現(xiàn)在要把他們?nèi)克偷胶拥挠野度?，農(nóng)夫有一條船，過河時，除農(nóng)夫外船上至多能載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農(nóng)夫在那里。似規(guī)劃出一個確保全部安全過河的計劃。請寫出所用謂詞的定義，并給出每個謂詞的功能及變量的個體域。解：(1) 先定義描述狀態(tài)的謂詞要描述這個問題，需要能夠說明農(nóng)夫、狼、羊、白菜和船在什么位置，為簡化問題表示，取消船在河中行駛的狀態(tài)，只描述左岸和右岸的狀態(tài)。并且，由于左岸和右岸的狀態(tài)互補，因此可僅對左岸或右岸的狀態(tài)做直接描述。本題選擇對左岸進行直接描述的方法，即定義謂詞如下：AL(x)：x在左岸其中，x的個體域是農(nóng)夫，船，狼，羊，白菜。對應(yīng)地，AL(x)表示x在右岸。 問題的初始狀態(tài)：AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(白菜) 問題的目標(biāo)狀態(tài)：AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(白菜) (2) 再定義描述操作的謂詞本題需要以下4個描述操作的謂詞：L-R：農(nóng)夫自己劃船從左岸到右岸L-R(x)：農(nóng)夫帶著x劃船從左岸到右岸R-L：農(nóng)夫自己劃船從右岸到左岸R-L(x) ：農(nóng)夫帶著x劃船從右岸到左岸其中，x的個體域是狼，羊，白菜。對上述每個操作，都包括條件和動作兩部分。它們對應(yīng)的條件和動作如下：L-R：農(nóng)夫劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(狼)AL(羊)，AL(羊)AL(白菜) 動作：刪除表：AL(船)，AL(農(nóng)夫) 添加表：AL(船)，AL(農(nóng)夫)L-R(狼)：農(nóng)夫帶著狼劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(狼)，AL(羊) 動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(狼) 添加表：AL(船)，AL(農(nóng)夫)，AL(狼)L-R(羊)：農(nóng)夫帶著羊劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(羊)， AL(狼)，AL(白菜) 或：AL(船)，AL(農(nóng)夫)，AL(羊)，AL(狼)，AL(白菜) 動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(羊) 添加表：AL(船)，AL(農(nóng)夫)，AL(羊)L-R(白菜)：農(nóng)夫帶著白菜劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(白菜)，AL(狼) 動作：刪除表：AL(船)，AL(農(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(船)，AL(農(nóng)夫)R-L(羊) ：農(nóng)夫帶著羊劃船從右岸到左岸 條件：AL(船)，AL(農(nóng)夫)，AL(羊) ，AL(狼)，AL(羊)，AL(白菜) 動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(羊) 添加表：AL(船)，AL(農(nóng)夫)，AL(羊)(3) 問題求解過程AL(白菜)AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(農(nóng)夫)AL(船)AL(狼)AL(白菜)AL(羊)AL(狼)AL(白菜)AL(農(nóng)夫)AL(船)AL(羊)AL(農(nóng)夫)R-L R-L(羊) L-R(狼)L-R(羊)AL(船)AL(狼)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(農(nóng)夫)AL(船)AL(羊)AL(白菜)AL(狼)R-L L-R(白菜)2.11 用謂詞表示法求解修道士和野人問題。在河的北岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但要受到以下條件限制：(1) 修道士和野人都會劃船，但船一次只能裝運兩個人。(2) 在任何岸邊，野人數(shù)不能超過修道士，否則修道士會被野人吃掉。假定野人愿意服從任何一種過河安排，請規(guī)劃出一種確保修道士安全的過河方案。要求寫出所用謂詞的定義、功能及變量的個體域。解：（1）定義謂詞先定義修道士和野人人數(shù)關(guān)系的謂詞：G(x,y,S)： 在狀態(tài)S下x大于yGE(x,y,S)：在狀態(tài)S下x大于或等于y其中，x,y分別代表修道士人數(shù)和野人數(shù)，他們的個體域均為0,1,2,3。再定義船所在岸的謂詞和修道士不在該岸上的謂詞：Boat(z,S)：狀態(tài)S下船在z岸EZ(x,S)： 狀態(tài)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的含義同上。該謂詞的含義是：狀態(tài)S下，在z岸，保證修道士安全，當(dāng)且僅當(dāng)修道士不在該岸上，或者修道士在該岸上，但人數(shù)超過野人數(shù)。該謂詞同時也描述了相應(yīng)的狀態(tài)。再定義描述過河方案的謂詞：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.18 請對下列命題分別寫出它們的語義網(wǎng)絡(luò)：(1) 每個學(xué)生都有一臺計算機。gGSgGSGS解：占有權(quán)計算機學(xué)生AKOISAISAFOwnsOwnercosg(2) 高老師從3月到7月給計算機系學(xué)生講計算機網(wǎng)絡(luò)課。 解：7月8月StartEnd老師ISAObjectSubject高老師計算機系學(xué)生講課事件ActionCaurse計算機網(wǎng)絡(luò)講課(3) 學(xué)習(xí)班的學(xué)員有男、有女、有研究生、有本科生。 解：參例2.14(4) 創(chuàng)新公司在科海大街56號，劉洋是該公司的經(jīng)理，他32歲、碩士學(xué)位。 解：參例2.10(5) 紅隊與藍隊進行足球比賽，最后以3：2的比分結(jié)束。 解：比賽AKOParticipants1Outcome3:22足球賽紅隊Participants 2藍隊2.19 請把下列命題用一個語義網(wǎng)絡(luò)表示出來：(1) 樹和草都是植物；植物解：AKOAKO草樹(2) 樹和草都有葉和根；根葉 解：HaveHave植物是一種是一種草樹(3) 水草是草，且生長在水中； 解：LiveAKOAKO水草水中植物草(4) 果樹是樹，且會結(jié)果； 解：CanAKOAKO果樹結(jié)果植物樹(5) 梨樹是果樹中的一種，它會結(jié)梨。 解：CanAKOAKO梨樹樹果樹結(jié)梨2.25 假設(shè)有以下一段天氣預(yù)報：“北京地區(qū)今天白天晴，偏北風(fēng)3級，最高氣溫12，最低氣溫-2，降水概率15%。”請用框架表示這一知識。解：Frame<天氣預(yù)報> 地域：北京 時段：今天白天 天氣：晴 風(fēng)向：偏北 風(fēng)力：3級 氣溫：最高：12度 最低：-2度 降水概率：15%2.26 按“師生框架”、“教師框架”、“學(xué)生框架”的形式寫出一個框架系統(tǒng)的描述。解：師生框架Frame <Teachers-Students> Name：Unit（Last-name，F(xiàn)irst-name） Sex：Area（male，female） Default：male Age：Unit（Years）Telephone：Home Unit（Number）Mobile Unit（Number） 教師框架Frame <Teachers > AKO<Teachers-Students > Major：Unit（Major-Name） Lectures：Unit（Course-Name） Field：Unit（Field-Name） Project ：Area（National，Provincial，Other） Default：Provincial Paper：Area（SCI，EI，Core，General） Default：Core 學(xué)生框架Frame <Students> AKO< Teachers-Students > Major：Unit（Major-Name） Classes：Unit（Classes-Name） Degree：Area（doctor，mastor, bachelor） Default：bachelor 第3章 確定性推理部分參考答案3.8 判斷下列公式是否為可合一，若可合一，則求出其最一般合一。(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, x), P(x, f(a), f(b) (5) P(x, y), P(y, x)解：(1) 可合一，其最一般和一為：=a/x, b/y。(2) 可合一，其最一般和一為：=y/f(x), b/z。(3) 可合一，其最一般和一為：= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一為：= y/x。3.11 把下列謂詞公式化成子句集：(1) (x)(y)(P(x, y)Q(x, y)(2) (x)(y)(P(x, y)Q(x, y)(3) (x)(y)(P(x, y)(Q(x, y)R(x, y)(4) (x) (y) (z)(P(x, y)Q(x, y)R(x, z) 解：(1) 由于(x)(y)(P(x, y)Q(x, y)已經(jīng)是Skolem標(biāo)準(zhǔn)型，且P(x, y)Q(x, y)已經(jīng)是合取范式，所以可直接消去全稱量詞、合取詞，得 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)此公式已為Skolem標(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)此公式已為前束范式。再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x)(P(x, f(x)Q(x, f(x)R(x, f(x)此公式已為Skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得子句集： S=P(x, f(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)再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x) (y) (P(x, y)Q(x, y)R(x, f(x,y)此公式已為Skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得子句集：S=P(x, y)Q(x, y)R(x, f(x,y)3-13 判斷下列子句集中哪些是不可滿足的：(1) PQ, Q, P, P(2) PQ , PQ, PQ, PQ (3) P(y)Q(y) , P(f(x)R(a)(4) P(x)Q(x) , P(y)R(y), P(a), S(a), S(z)R(z)(5) P(x)Q(f(x),a) , P(h(y)Q(f(h(y), a)P(z)(6) P(x)Q(x)R(x) , P(y)R(y), Q(a), R(b) 解：(1) 不可滿足，其歸結(jié)過程為：PQQPPNIL(2) 不可滿足，其歸結(jié)過程為：PQPQQPQPQQNIL(3) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4) 不可滿足，其歸結(jié)過程略(5) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6) 不可滿足，其歸結(jié)過程略 3.14 對下列各題分別證明G是否為F1,F2,Fn的邏輯結(jié)論：(1) F: (x)(y)(P(x, y)G: (y)(x)(P(x, y)(2) F: (x)(P(x)(Q(a)Q(b)G: (x) (P(x)Q(x)(3) F: (x)(y)(P(f(x)(Q(f(y)G: P(f(a)P(y)Q(y)(4) F1: (x)(P(x)(y)(Q(y)L(x.y)F2: (x) (P(x)(y)(R(y)L(x.y)G: (x)(R(x)Q(x)(5) F1: (x)(P(x)(Q(x)R(x)F2: (x) (P(x)S(x)G: (x) (S(x)R(x) 解：(1) 先將F和G化成子句集： S=P(a,b), P(x,b) 再對S進行歸結(jié)：P(x,b)P(a,b)NIL a/x 所以，G是F的邏輯結(jié)論(2) 先將F和G化成子句集由F得：S1=P(x)，(Q(a)Q(b)由于G為： (x) (P(x)Q(x)，即 (x) ( P(x) Q(x)，可得： S2= P(x) Q(x)因此，擴充的子句集為：S= P(x)，(Q(a)Q(b)， P(x) Q(x) 再對S進行歸結(jié)：Q(a)Q(b)Q(a) P(x) Q(x) P(a)P(x)NILQ(a)Q(b) a/b P(x) Q(x)Q(a)a/x P(a)P(x) a/xNIL 所以，G是F的邏輯結(jié)論 同理可求得(3)、(4)和(5)，其求解過程略。 3.15 設(shè)已知：(1) 如果x是y的父親，y是z的父親，則x是z的祖父；(2) 每個人都有一個父親。使用歸結(jié)演繹推理證明：對于某人u，一定存在一個人v，v是u的祖父。 解：先定義謂詞 F(x,y)：x是y的父親 GF(x,z)：x是z的祖父 P(x)：x是一個人 再用謂詞把問題描述出來： 已知F1：(x) (y) (z)( F(x,y)F(y,z)GF(x,z) F2：(y)(P(x)F(x,y) 求證結(jié)論G：(u) (v)( P(u)GF(v,u) 然后再將F1，F(xiàn)2和G化成子句集： F(x,y)F(y,z)GF(x,z) P(r)F(s,r) P(u) GF(v,u) 對上述擴充的子句集，其歸結(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/ux/s,y/ry/s,z/r y/z y/u 由于導(dǎo)出了空子句，故結(jié)論得證。3.16 假設(shè)張被盜，公安局派出5個人去調(diào)查。案情分析時，貞察員A說：“趙與錢中至少有一個人作案”，貞察員B說：“錢與孫中至少有一個人作案”，貞察員C說：“孫與李中至少有一個人作案”，貞察員D說：“趙與孫中至少有一個人與此案無關(guān)”，貞察員E說：“錢與李中至少有一個人與此案無關(guān)”。如果這5個偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰是盜竊犯。解：(1) 先定義謂詞和常量設(shè)C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李(2) 將已知事實用謂詞公式表示出來趙與錢中至少有一個人作案：C(Z)C(Q)錢與孫中至少有一個人作案：C(Q)C(S)孫與李中至少有一個人作案：C(S)C(L)趙與孫中至少有一個人與此案無關(guān)： (C (Z)C(S)，即 C (Z) C(S)錢與李中至少有一個人與此案無關(guān)： (C (Q)C(L)，即 C (Q) C(L)(3) 將所要求的問題用謂詞公式表示出來，并與其否定取析取。設(shè)作案者為u，則要求的結(jié)論是C(u)。將其與其否)取析取，得： C(u) C(u)(4) 對上述擴充的子句集，按歸結(jié)原理進行歸結(jié)，其修改的證明樹如下：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 因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出：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 設(shè)有子句集： P(x)Q(a, b), P(a)Q(a, b), Q(a, f(a), P(x)Q(x, b)分別用各種歸結(jié)策略求出其歸結(jié)式。解：支持集策略不可用，原因是沒有指明哪個子句是由目標(biāo)公式的否定化簡來的。刪除策略不可用，原因是子句集中沒有沒有重言式和具有包孕關(guān)系的子句。單文字子句策略的歸結(jié)過程如下：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)用線性輸入策略（同時滿足祖先過濾策略）的歸結(jié)過程如下：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 設(shè)已知：(1) 能閱讀的人是識字的；(2) 海豚不識字；(3) 有些海豚是很聰明的。請用歸結(jié)演繹推理證明：有些很聰明的人并不識字。解：第一步，先定義謂詞， 設(shè)R(x)表示x是能閱讀的；K(y)表示y是識字的；W(z) 表示z是很聰明的；第二步，將已知事實和目標(biāo)用謂詞公式表示出來能閱讀的人是識字的：(x)(R(x)K(x)海豚不識字：(y)(K (y)有些海豚是很聰明的：(z) W(z)有些很聰明的人并不識字：(x)( W(z)K(x) 第三步，將上述已知事實和目標(biāo)的否定化成子句集： R(x)K(x)K (y)W(z)W(z)K(x) 第四步，用歸結(jié)演繹推理進行證明W(z)W(z)K(x)W(z)K(z)NIL3.20 對子句集： PQ, QR, RW, RP, WQ, QR 用線性輸入策略是否可證明該子句集的不可滿足性？ 解：用線性輸入策略不能證明子句集PQ, QR, RW, RP, WQ, QR 的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過程。3.21 對線性輸入策略和單文字子句策略分別給出一個反例，以說明它們是不完備的。3.22 分別說明正向、逆向、雙向與/或形演繹推理的基本思想。3.23 設(shè)已知事實為 (PQ)R) (S(TU) F規(guī)則為 S(XY)Z試用正向演繹推理推出所有可能的子目標(biāo)。解：先給出已知事實的與/或樹，再利用F規(guī)則進行推理，其規(guī)則演繹系統(tǒng)如下圖所示。由該圖可以直接寫出所有可能的目標(biāo)子句如下： PQPQPQYRTU RXZRYZ 所有子目標(biāo)UTZYXRQP所有目標(biāo)UTZYXRQPYXZXYSUTTUS所有目標(biāo)UTZYXRQP所有目標(biāo)YZUTXPRQYXXYF規(guī)則ZXYXYZSSUTQPTUQP已知事實已知事實TUSR(PQ)TURS(PQ) (S(TU)(PQ)R) (S(TU)(PQ)R)(PQ)R) (S(TU)(PQ)R) (S(TU)3.24 設(shè)有如下一段知識：“張、王和李都屬于高山協(xié)會。該協(xié)會的每個成員不是滑雪運動員，就是登山運動員，其中不喜歡雨的運動員是登山運動員，不喜歡雪的運動員不是滑雪運動員。王不喜歡張所喜歡的一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪。”試用謂詞公式集合表示這段知識，這些謂詞公式要適合一個逆向的基于規(guī)則的演繹系統(tǒng)。試說明這樣一個系統(tǒng)怎樣才能回答問題：“高山俱樂部中有沒有一個成員，他是一個登山運動員，但不是一個滑雪運動員？”解：(1) 先定義謂詞A(x) 表示x是高山協(xié)會會員S(x) 表示x是滑雪運動員C(x) 表示x是登山運動員L(x,y) 表示x 喜歡y (2) 將問題用謂詞表示出來“張、王和李都屬于高山協(xié)會A(Zhang)A(Wang)A(Li)高山協(xié)會的每個成員不是滑雪運動員，就是登山運動員(x)(A(x)S(x)C(x)高山協(xié)會中不喜歡雨的運動員是登山運動員(x)(L(x, Rain)C(x)高山協(xié)會中不喜歡雪的運動員不是滑雪運動員(x)(L(x, Snow) S(x)王不喜歡張所喜歡的一切東西(y)( L(Zhang, y) L(Wang ,y) 王喜歡張所不喜歡的一切東西(y)( L(Zhang, y)L(Wang, y)張喜歡雨和雪L(Zhang , Rain)L(Zhang , Snow)(3) 將問題要求的答案用謂詞表示出來高山俱樂部中有沒有一個成員，他是一個登山運動員，但不是一個滑雪運動員？ (x)( A(x)C(x) S(x) (4) 為了進行推理，把問題劃分為已知事實和規(guī)則兩大部分。假設(shè)，劃分如下：已知事實：A(Zhang)A(Wang)A(Li)L(Zhang , Rain)L(Zhang , Snow)規(guī)則：(x)(A(x)S(x)C(x)(x)(L(x, Rain)C(x)(x)(L(x, Snow) S(x)(y)( L(Zhang, y) L(Wang ,y)(y)( L(Zhang, y)L(Wang, y) (5) 把已知事實、規(guī)則和目標(biāo)化成推理所需要的形式事實已經(jīng)是文字的合取形式：f1: A(Zhang)A(Wang)A(Li)f2: L (Zhang , Rain)L(Zhang , Snow)將規(guī)則轉(zhuǎn)化為后件為單文字的形式：r1: A(x)S(x)C(x)r2: L(x, Rain)C(x)r3: L(x, Snow) S(x)r4: L(Zhang, y) L(Wang ,y)r5: L(Zhang, y)L(Wang , y) 將目標(biāo)公式轉(zhuǎn)換為與/或形式 A(x)(C(x) S(x) (6) 進行逆向推理逆向推理的關(guān)鍵是要能夠推出L(Zhang , Rain)L(Zhang , Snow)，其逆向演繹過程如下圖所示。 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)第4章 搜索策略部分參考答案4.5 有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：(1) 船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；(2) 如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。請設(shè)計一個過河方案，使得農(nóng)夫、浪、羊都能不受損失的過河，畫出相應(yīng)的狀態(tài)空間圖。題示：(1) 用四元組（農(nóng)夫，狼，羊，菜）表示狀態(tài)，其中每個元素都為0或1，用0表示在左岸，用1表示在右岸。(2) 把每次過河的一種安排作為一種操作，每次過河都必須有農(nóng)夫，因為只有他可以劃船。解：第一步，定義問題的描述形式用四元組S=（f，w，s，v）表示問題狀態(tài)，其中，f，w，s和v分別表示農(nóng)夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定義的問題狀態(tài)表示方式，把所有可能的問題狀態(tài)表示出來，包括問題的初始狀態(tài)和目標(biāo)狀態(tài)。由于狀態(tài)變量有4個，每個狀態(tài)變量都有2種取值，因此有以下16種可能的狀態(tài)：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，狀態(tài)S3，S6，S7，S8，S9，S12是不合法狀態(tài)，S0和S15分別是初始狀態(tài)和目標(biāo)狀態(tài)。第三步，定義操作，即用于狀態(tài)變換的算符組F由于每次過河船上都必須有農(nóng)夫，且除農(nóng)夫外船上只能載狼，羊和菜中的一種，故算符定義如下：L(i)表示農(nóng)夫從左岸將第i樣?xùn)|西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西）。由于農(nóng)夫必須在船上，故對農(nóng)夫的表示省略。R (i)表示農(nóng)夫從右岸將第i樣?xùn)|西帶到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西）。同樣，對農(nóng)夫的表示省略。這樣，所定義的算符組F可以有以下8種算符：L (0)，L (1)，L (2)，L (3)R(0)，R(1)，R (2)，R (3)第四步，根據(jù)上述定義的狀態(tài)和操作進行求解。該問題求解過程的狀態(tài)空間圖如下：(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,0,1,0)R(0)(1,0,1,0)L(2)(0,0,0,0)4.7 圓盤問題。設(shè)有大小不等的三個圓盤A、B、C套在一根軸上，每個盤上都標(biāo)有數(shù)字1、2、3、4，并且每個圓盤都可以獨立的繞軸做逆時針轉(zhuǎn)動，每次轉(zhuǎn)動90，其初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如圖4-31所示，請用廣度優(yōu)先搜索和深度優(yōu)先搜索，求出從S0到Sg的路徑。CC12222222 BAAB42 234131231331414443 初始狀態(tài)S0 目標(biāo)狀態(tài)Sg 圖 431 圓盤問題解：設(shè)用qA，qB和qC分別表示把A盤，B盤和C盤繞軸逆時針轉(zhuǎn)動90，這些操作（算符）的排列順序是qA，qB，qC。應(yīng)用廣度優(yōu)先搜索，可得到如下搜索樹。在該搜索樹中，重復(fù)出現(xiàn)的狀態(tài)不再劃出，節(jié)點旁邊的標(biāo)識Si，i=0,1,2,，為按節(jié)點被擴展的順序給出的該節(jié)點的狀態(tài)標(biāo)識。由該圖可以看出，從初始狀態(tài)S0到目標(biāo)狀態(tài)Sg的路徑是S02513(Sg)3221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334213112244qA314241231234qB132314242413qC4.7題的廣度優(yōu)先搜索樹S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索略。4.8 圖4-32是5個城市的交通圖，城市之間的連線旁邊的數(shù)字是城市之間路程的費用。要求從A城出發(fā)，經(jīng)過其它各城市一次且僅一次，最后回到A城，請找出一條最優(yōu)線路。 A 10 B 2 8 9 C 11 6 3 12 8 D 9 E432 交通費用圖解：這個問題又稱為旅行商問題（travelling salesman problem, TSP）或貨郎擔(dān)問題，是一個較有普遍性的實際應(yīng)用問題。根據(jù)數(shù)學(xué)理論，對n個城市的旅行商問題，其封閉路徑的排列總數(shù)為： (n!)/n=(n-1)!其計算量相當(dāng)大。例如，當(dāng)n=20時，要窮舉其所有路徑，即使用一個每秒一億次的計算機來算也需要350年的時間。因此，對這類問題只能用搜索的方法來解決。下圖是對圖4-32按最小代價搜索所得到的搜索樹，樹中的節(jié)點為城市名稱，節(jié)點邊上的數(shù)字為該節(jié)點的代價g。其計算公式為 g(ni+1)=g(ni)+c(ni, ni+1)其中，c(ni,ni+1)為節(jié)點ni到ni+1節(jié)點的邊代價。0A119210102119BDCE98693128386128201917CDB181221ECB10105EDB16E2218DC331288923123868868969126129883C32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426CB2720C1417BE2524DC2621DE6812666E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B302820E28CB21030A30A圖4.32的最小代價搜索樹可以看出，其最短路經(jīng)是 A-C-D-E-B-A或 A-B-E-D-C-A其實，它們是同一條路經(jīng)。4.11 設(shè)有如下結(jié)構(gòu)的移動將牌游戲：BBWWE其中，B表示黑色將牌，W表是白色將牌，E表示空格。游戲的規(guī)定走法是：(1) 任意一個將牌可移入相鄰的空格，規(guī)定其代價為1；(2) 任何一個將牌可相隔1個其它的將牌跳入空格，其代價為跳過將牌的數(shù)目加1。游戲要達到的目標(biāo)什是把所有W都移到B的左邊。對這個問題，請定義一個啟發(fā)函數(shù)h(n)，并給出用這個啟發(fā)函數(shù)產(chǎn)生的搜索樹。你能否判別這個啟發(fā)函數(shù)是否滿足下解要求？再求出的搜索樹中，對所有節(jié)點是否滿足單調(diào)限制？解：設(shè)h(x)=每個W左邊的B的個數(shù)，f(x)=d(x)+3*h(x)，其搜索樹如下：f(x)=0+12=12BBWWEf(x)=1+12=13BBE WWf(x)=1+12=13