《人工智能原理及其應用第2版》王萬森編著電子工業(yè)出版社課后習題答案37.doc》由會員分享，可在線閱讀，更多相關《人工智能原理及其應用第2版》王萬森編著電子工業(yè)出版社課后習題答案37.doc（38頁珍藏版）》請在裝配圖網上搜索。

第2章 知識表示方法部分參考答案 2.8 設有如下語句，請用相應的謂詞公式分別把他們表示出來： (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) 不是每個計算機系的學生都喜歡在計算機上編程序。 解：定義謂詞 S(x)：x是計算機系學生 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 用謂詞表示法求解機器人摞積木問題。設機器人有一只機械手，要處理的世界有一張桌子，桌上可堆放若干相同的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如下圖所示。 A B C CA B 圖 機器人摞積木問題 解：(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 問題的目標狀態(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) ，HANDEMPTY Stack(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) HANDEMPTY ONTABLE(A) ONTABLE(B) ON(C, A) CLEAR(B) CLEAR(C) HANDEMPTY ONTABLE(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) HANDEMPTY ONTABLE(A) ONTABLE(C) HOLDING(B) CLEAR(A) CLEAR(B) CLEAR(C) ONTABLE(C) ON(B,C) ON(A,B) CLEAR(A) HANDEMPT ONTABLE(C) ON(B,C) CLEAR(A) CLEAR(B) HOLDING(A) Stack(B,A) Stack(C,B) Pickup(A) 2.10 用謂詞表示法求解農夫、狼、山羊、白菜問題。農夫、狼、山羊、白菜全部放在一條河的左岸，現在要把他們全部送到河的右岸去，農夫有一條船，過河時，除農夫外船上至多能載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農夫在那里。似規(guī)劃出一個確保全部安全過河的計劃。請寫出所用謂詞的定義，并給出每個謂詞的功能及變量的個體域。 解：(1) 先定義描述狀態(tài)的謂詞 要描述這個問題，需要能夠說明農夫、狼、羊、白菜和船在什么位置，為簡化問題表示，取消船在河中行駛的狀態(tài)，只描述左岸和右岸的狀態(tài)。并且，由于左岸和右岸的狀態(tài)互補，因此可僅對左岸或右岸的狀態(tài)做直接描述。本題選擇對左岸進行直接描述的方法，即定義謂詞如下： AL(x)：x在左岸 其中，x的個體域是{農夫，船，狼，羊，白菜}。對應地，AL(x)表示x在右岸。 問題的初始狀態(tài)： AL(農夫) AL(船) AL(狼) AL(羊) AL(白菜) 問題的目標狀態(tài)： AL(農夫) AL(船) AL(狼) AL(羊) AL(白菜) (2) 再定義描述操作的謂詞 本題需要以下4個描述操作的謂詞： L-R：農夫自己劃船從左岸到右岸 L-R(x)：農夫帶著x劃船從左岸到右岸 R-L：農夫自己劃船從右岸到左岸 R-L(x) ：農夫帶著x劃船從右岸到左岸 其中，x的個體域是{狼，羊，白菜}。 對上述每個操作，都包括條件和動作兩部分。它們對應的條件和動作如下： L-R：農夫劃船從左岸到右岸 條件：AL(船)，AL(農夫)，AL(狼)∨AL(羊)，AL(羊)∨AL(白菜) 動作：刪除表：AL(船)，AL(農夫) 添加表：AL(船)，AL(農夫) L-R(狼)：農夫帶著狼劃船從左岸到右岸 條件：AL(船)，AL(農夫)，AL(狼)，AL(羊) 動作：刪除表：AL(船)，AL(農夫)，AL(狼) 添加表：AL(船)，AL(農夫)，AL(狼) L-R(羊)：農夫帶著羊劃船從左岸到右岸 條件：AL(船)，AL(農夫)，AL(羊)， AL(狼)，AL(白菜) 或：AL(船)，AL(農夫)，AL(羊)，AL(狼)，AL(白菜) 動作：刪除表：AL(船)，AL(農夫)，AL(羊) 添加表：AL(船)，AL(農夫)，AL(羊) L-R(白菜)：農夫帶著白菜劃船從左岸到右岸 條件：AL(船)，AL(農夫)，AL(白菜)，AL(狼) 動作：刪除表：AL(船)，AL(農夫)，AL(白菜) 添加表：AL(船)，AL(農夫)，AL(白菜) R-L：農夫劃船從右岸到左岸 條件：AL(船)，AL(農夫)，AL(狼)∨AL(羊)，AL(羊)∨AL(白菜) 或：AL(船)，AL(農夫) ，AL(狼)，AL(白菜)，AL(羊) 動作：刪除表：AL(船)，AL(農夫) 添加表：AL(船)，AL(農夫) R-L(羊) ：農夫帶著羊劃船從右岸到左岸 條件：AL(船)，AL(農夫)，AL(羊) ，AL(狼)，AL(羊)，AL(白菜) 動作：刪除表：AL(船)，AL(農夫)，AL(羊) 添加表：AL(船)，AL(農夫)，AL(羊) (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(白菜) AL(狼) L-R(羊) AL(農夫) AL(船) AL(羊) AL(白菜) AL(狼) R-L L-R(白菜) 2.11 用謂詞表示法求解修道士和野人問題。在河的北岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但要受到以下條件限制： (1) 修道士和野人都會劃船，但船一次只能裝運兩個人。 (2) 在任何岸邊，野人數不能超過修道士，否則修道士會被野人吃掉。 假定野人愿意服從任何一種過河安排，請規(guī)劃出一種確保修道士安全的過河方案。要求寫出所用謂詞的定義、功能及變量的個體域。 解：（1）定義謂詞 先定義修道士和野人人數關系的謂詞： G(x,y,S)： 在狀態(tài)S下x大于y GE(x,y,S)：在狀態(tài)S下x大于或等于y 其中，x,y分別代表修道士人數和野人數，他們的個體域均為{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岸，保證修道士安全，當且僅當修道士不在該岸上，或者修道士在該岸上，但人數超過野人數。該謂詞同時也描述了相應的狀態(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 請對下列命題分別寫出它們的語義網絡： (1) 每個學生都有一臺計算機。 g GS g GS GS 解： 占有權 計算機 學生 AKO ISA ISA F Owns Owner c o s g (2) 高老師從3月到7月給計算機系學生講《計算機網絡》課。 解： 7月 8月 Start End 老師 ISA Object Subject 高老師 計算機系學生 講課事件 Action Caurse 計算機網絡 講課 (3) 學習班的學員有男、有女、有研究生、有本科生。 解：參例2.14 (4) 創(chuàng)新公司在科海大街56號，劉洋是該公司的經理，他32歲、碩士學位。 解：參例2.10 (5) 紅隊與藍隊進行足球比賽，最后以3：2的比分結束。 解： 比賽 AKO Participants1 Outcome 3:2 2 足球賽 紅隊 Participants 2 藍隊 2.19 請把下列命題用一個語義網絡表示出來： (1) 樹和草都是植物； 植物 解： AKO AKO 草 樹 (2) 樹和草都有葉和根； 根 葉 解： Have Have 植物 是一種 是一種 草 樹 (3) 水草是草，且生長在水中； 解： Live AKO AKO 水草 水中 植物 草 (4) 果樹是樹，且會結果； 解： Can AKO AKO 果樹 結果 植物 樹 (5) 梨樹是果樹中的一種，它會結梨。 解： Can AKO AKO 梨樹 樹 果樹 結梨 2.25 假設有以下一段天氣預報：“北京地區(qū)今天白天晴，偏北風3級，最高氣溫12，最低氣溫-2，降水概率15%?！闭堄每蚣鼙硎具@一知識。 解： Frame<天氣預報> 地域：北京 時段：今天白天 天氣：晴 風向：偏北 風力：3級 氣溫：最高：12度 最低：-2度 降水概率：15% 2.26 按“師生框架”、“教師框架”、“學生框架”的形式寫出一個框架系統(tǒng)的描述。 解：師生框架 Frame Name：Unit（Last-name，First-name） Sex：Area（male，female） Default：male Age：Unit（Years） Telephone：Home Unit（Number） Mobile Unit（Number） 教師框架 Frame AKO 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 學生框架 Frame 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))已經是Skolem標準型，且P(x, y)∧Q(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)) 此公式已為Skolem標準型。 再消去全稱量詞得子句集： 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函數f(x)替換y得： (x)(P(x, f(x))∨Q(x, f(x))∨R(x, f(x))) 此公式已為Skolem標準型。 最后消去全稱量詞得子句集： 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函數f(x)替換y得： (x) (y) (P(x, y)∨Q(x, y)∨R(x, f(x,y))) 此公式已為Skolem標準型。 最后消去全稱量詞得子句集： S={P(x, y)∨Q(x, y)∨R(x, f(x,y))} 3-13 判斷下列子句集中哪些是不可滿足的： (1) {P∨Q, Q, P, P} (2) { P∨Q , P∨Q, P∨Q, P∨Q } (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) 不可滿足，其歸結過程為： P∨Q Q P P NIL (2) 不可滿足，其歸結過程為： P∨Q P∨Q Q P∨Q P∨Q Q NIL (3) 不是不可滿足的，原因是不能由它導出空子句。 (4) 不可滿足，其歸結過程略 (5) 不是不可滿足的，原因是不能由它導出空子句。 (6) 不可滿足，其歸結過程略 3.14 對下列各題分別證明G是否為F1,F2,…,Fn的邏輯結論： (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進行歸結： P(x,b) P(a,b) NIL {a/x} 所以，G是F的邏輯結論 (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進行歸結： Q(a)∨Q(b) Q(a) P(x)∨ Q(x) P(a) P(x) NIL Q(a)∨Q(b) {a/b} P(x)∨ Q(x) Q(a) {a/x} P(a) P(x) {a/x} NIL 所以，G是F的邏輯結論 同理可求得(3)、(4)和(5)，其求解過程略。 3.15 設已知： (1) 如果x是y的父親，y是z的父親，則x是z的祖父； (2) 每個人都有一個父親。 使用歸結演繹推理證明：對于某人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)) 求證結論G：(u) (v)( P(u)→GF(v,u)) 然后再將F1，F2和G化成子句集： ① F(x,y)∨F(y,z)∨GF(x,z) ② P(r)∨F(s,r) ③ P(u) ④ GF(v,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/u} {x/s,y/r} {y/s,z/r} {y/z} {y/u} 由于導出了空子句，故結論得證。 3.16 假設張被盜，公安局派出5個人去調查。案情分析時，貞察員A說：“趙與錢中至少有一個人作案”，貞察員B說：“錢與孫中至少有一個人作案”，貞察員C說：“孫與李中至少有一個人作案”，貞察員D說：“趙與孫中至少有一個人與此案無關”，貞察員E說：“錢與李中至少有一個人與此案無關”。如果這5個偵察員的話都是可信的，使用歸結演繹推理求出誰是盜竊犯。 解：(1) 先定義謂詞和常量 設C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李 (2) 將已知事實用謂詞公式表示出來 趙與錢中至少有一個人作案：C(Z)∨C(Q) 錢與孫中至少有一個人作案：C(Q)∨C(S) 孫與李中至少有一個人作案：C(S)∨C(L) 趙與孫中至少有一個人與此案無關： (C (Z)∧C(S))，即 C (Z) ∨C(S) 錢與李中至少有一個人與此案無關： (C (Q)∧C(L))，即 C (Q) ∨C(L) (3) 將所要求的問題用謂詞公式表示出來，并與其否定取析取。 設作案者為u，則要求的結論是C(u)。將其與其否)取析取，得： C(u) ∨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} 因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據歸結原理還可以得出： 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(a)∨Q(a, b), Q(a, f(a)), P(x)∨Q(x, b)} 分別用各種歸結策略求出其歸結式。 解：支持集策略不可用，原因是沒有指明哪個子句是由目標公式的否定化簡來的。 刪除策略不可用，原因是子句集中沒有沒有重言式和具有包孕關系的子句。 單文字子句策略的歸結過程如下： 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/x} {a/x} Q(a, f(a)) Q(a,b) {b/f(a)} NIL 3.19 設已知： (1) 能閱讀的人是識字的； (2) 海豚不識字； (3) 有些海豚是很聰明的。 請用歸結演繹推理證明：有些很聰明的人并不識字。 解：第一步，先定義謂詞， 設R(x)表示x是能閱讀的； K(y)表示y是識字的； W(z) 表示z是很聰明的； 第二步，將已知事實和目標用謂詞公式表示出來 能閱讀的人是識字的：(x)(R(x))→K(x)) 海豚不識字：(y)(K (y)) 有些海豚是很聰明的：(z) W(z) 有些很聰明的人并不識字：(x)( W(z)∧K(x)) 第三步，將上述已知事實和目標的否定化成子句集： R(x))∨K(x) K (y) W(z) W(z)∨K(x)) 第四步，用歸結演繹推理進行證明 W(z) W(z)∨K(x)) W(z) K(z) NIL 3.20 對子句集： {P∨Q, Q∨R, R∨W, R∨P, W∨Q, Q∨R } 用線性輸入策略是否可證明該子句集的不可滿足性？ 解：用線性輸入策略不能證明子句集 {P∨Q, Q∨R, R∨W, R∨P, W∨Q, Q∨R } 的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結過程。 3.21 對線性輸入策略和單文字子句策略分別給出一個反例，以說明它們是不完備的。 3.22 分別說明正向、逆向、雙向與/或形演繹推理的基本思想。 3.23 設已知事實為 ((P∨Q)∧R) ∨(S∧(T∨U)) F規(guī)則為 S→(X∧Y)∨Z 試用正向演繹推理推出所有可能的子目標。 解：先給出已知事實的與/或樹，再利用F規(guī)則進行推理，其規(guī)則演繹系統(tǒng)如下圖所示。 由該圖可以直接寫出所有可能的目標子句如下： P∨Q∨Ｔ∨Ｕ 　　P∨Q∨Ｘ∨Ｚ 　　P∨Q∨Y∨Ｚ R∨T∨U R∨X∨Z R∨Y∨Z 所有子 目標 U T Z Y X R Q P 所有 目標 U T Z Y X R Q P Y X Z X∧Y S U T T∨U S 所有 目標 U T Z Y X R Q P 所有 目標 Y Z U T X P R Q Y X X Y F 規(guī)則 Z X∧Y X∧Y Z S S U T Q P T U Q P 已知事實 已知事實 T∨U S R (P∨Q) T∨U R S (P∨Q) (S∧(T∨U)) ((P∨Q)∧R) (S∧(T∨U)) ((P∨Q)∧R) ((P∨Q)∧R) ∨(S∧(T∨U)) ((P∨Q)∧R) ∨(S∧(T∨U)) 3.24 設有如下一段知識： “張、王和李都屬于高山協(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ī)則兩大部分。假設，劃分如下： 已知事實： 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ī)則和目標化成推理所需要的形式 事實已經是文字的合取形式： f1: A(Zhang)∧A(Wang)∧A(Li) f2: L (Zhang , Rain)∧L(Zhang , Snow) 將規(guī)則轉化為后件為單文字的形式： 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) 將目標公式轉換為與/或形式 A(x)∨(C(x)∧ S(x)) (6) 進行逆向推理 逆向推理的關鍵是要能夠推出L(Zhang , Rain)∧L(Zhang , Snow)，其逆向演繹過程如下圖所示。 A(x)∨(C(x)∧ S(x)) C(x)∧ S(x) A(x) C(x) S(x) r2 r34 L(x, Rain) L(x, Snow) {Wang/x, y/Rain} {Wang /x, y/Snow} L(Wang, y) L(Wang, y) r4 r4 L(Zhang, y) L(Zhang, y) {Rain/y} {Snow/y} L(Zhang, Snow) L(Zhang, Rain) 第4章 搜索策略部分參考答案 4.5 有一農夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制： (1) 船太小，農夫每次只能帶一樣東西過河； (2) 如果沒有農夫看管，則狼要吃羊，羊要吃菜。 請設計一個過河方案，使得農夫、浪、羊都能不受損失的過河，畫出相應的狀態(tài)空間圖。 題示：(1) 用四元組（農夫，狼，羊，菜）表示狀態(tài)，其中每個元素都為0或1，用0表示在左岸，用1表示在右岸。 (2) 把每次過河的一種安排作為一種操作，每次過河都必須有農夫，因為只有他可以劃船。 解：第一步，定義問題的描述形式 用四元組S=（f，w，s，v）表示問題狀態(tài)，其中，f，w，s和v分別表示農夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。 第二步，用所定義的問題狀態(tài)表示方式，把所有可能的問題狀態(tài)表示出來，包括問題的初始狀態(tài)和目標狀態(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)和目標狀態(tài)。 第三步，定義操作，即用于狀態(tài)變換的算符組F 由于每次過河船上都必須有農夫，且除農夫外船上只能載狼，羊和菜中的一種，故算符定義如下： L(i)表示農夫從左岸將第i樣東西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農夫外不載任何東西）。由于農夫必須在船上，故對農夫的表示省略。 R (i)表示農夫從右岸將第i樣東西帶到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農夫外不載任何東西）。同樣，對農夫的表示省略。 這樣，所定義的算符組F可以有以下8種算符： L (0)，L (1)，L (2)，L (3) R(0)，R(1)，R (2)，R (3) 第四步，根據上述定義的狀態(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 圓盤問題。設有大小不等的三個圓盤A、B、C套在一根軸上，每個盤上都標有數字1、2、3、4，并且每個圓盤都可以獨立的繞軸做逆時針轉動，每次轉動90，其初始狀態(tài)S0和目標狀態(tài)Sg如圖4-31所示，請用廣度優(yōu)先搜索和深度優(yōu)先搜索，求出從S0到Sg的路徑。 C C 1 2 2 2 2 2 2 2 B A A B 4 2 2 3 4 1 3 1 2 3 1 3 3 1 4 1 4 4 4 3 初始狀態(tài)S0 目標狀態(tài)Sg 圖 431 圓盤問題 解：設用qA，qB和qC分別表示把A盤，B盤和C盤繞軸逆時針轉動90，這些操作（算符）的排列順序是qA，qB，qC。 應用廣度優(yōu)先搜索，可得到如下搜索樹。在該搜索樹中，重復出現的狀態(tài)不再劃出，節(jié)點旁邊的標識Si，i=0,1,2,…，為按節(jié)點被擴展的順序給出的該節(jié)點的狀態(tài)標識。 由該圖可以看出，從初始狀態(tài)S0到目標狀態(tài)Sg的路徑是 S0→2→5→13(Sg) 3 2 2 1 1 1 3 3 3 4 4 4 4 2 3 3 13 23 1 4 1 2 2 3 4 4 3 2 3 1 4 1 2 1 2 4 3 4 2 3 3 1 1 4 2 4 2 4 1 3 A B C qA qB qC 3 3 1 3 1 1 2 2 4 2 4 4 qA 3 2 2 4 4 1 3 1 1 3 2 4 qB qC 4 13 4 1 23 3 23 3 4 1 23 3 3 1 3 1 3 1 2 4 4 2 2 4 1 2 3 4 4 1 2 3 4 1 2 3 1 3 3 2 4 1 1 2 2 4 4 qC 3 3 4 2 1 3 1 1 2 2 4 4 qA 3 1 4 2 4 1 2 3 1 2 3 4 qB 1 3 2 3 1 4 2 4 2 4 1 3 qC 4.7題的廣度優(yōu)先搜索樹 S0 S1 S2 S4 S5 S6 S7 S8 S9 S10 S11 S12即Sg S3 其深度優(yōu)先搜索略。 4.8 圖4-32是5個城市的交通圖，城市之間的連線旁邊的數字是城市之間路程的費用。要求從A城出發(fā)，經過其它各城市一次且僅一次，最后回到A城，請找出一條最優(yōu)線路。 A 10 B 2 8 9 C 11 6 3 12 8 D 9 E 432 交通費用圖 解：這個問題又稱為旅行商問題（travelling salesman problem, TSP）或貨郎擔問題，是一個較有普遍性的實際應用問題。根據數學理論，對n個城市的旅行商問題，其封閉路徑的排列總數為： (n!)/n=(n-1)! 其計算量相當大。例如，當n=20時，要窮舉其所有路徑，即使用一個每秒一億次的計算機來算也需要350年的時間。因此，對這類問題只能用搜索的方法來解決。 下圖是對圖4-32按最小代價搜索所得到的搜索樹，樹中的節(jié)點為城市名稱，節(jié)點邊上的數字為該節(jié)點的代價g。其計算公式為 g(ni+1)=g(ni)+c(ni, ni+1) 其中，c(ni,ni+1)為節(jié)點ni到ni+1節(jié)點的邊代價。 0 A 11 9 2 10 10 2 11 9 B D C E 9 8 6 9 3 12 8 3 8 6 12 8 20 19 17 C D B 18 12 21 E C B 10 10 5 E D B 16 E 22 18 D C 3 3 12 8 8 9 23 12 3 8 6 8 8 6 8 9 6 9 12 6 12 9 8 8 3 C 32 B 22 29 25 D C 20 20 E B B 16 D 19 16 22 D E 31 E 25 C 9 8 3 8 E 12 9 12 B D 27 24 26 C B 27 20 C 14 17 B E 25 24 D C 26 21 D E 6 8 12 6 6 6 E 31 33 E 9 3 28 D 31 B 9 26 B 26 E 8 31 B 28 D D 27 3 23 E 35 E D 27 D 32 C 34 B 30 28 20 E 28 C B 2 10 30 A 30 A 圖4.32的最小代價搜索樹 可以看出，其最短路經是 A-C-D-E-B-A 或 A-B-E-D-C-A 其實，它們是同一條路經。 4.11 設有如下結構的移動將牌游戲： B B W W E 其中，B表示黑色將牌，W表是白色將牌，E表示空格。游戲的規(guī)定走法是： (1) 任意一個將牌可移入相鄰的空格，規(guī)定其代價為1； (2) 任何一個將牌可相隔1個其它的將牌跳入空格，其代價為跳過將牌的數目加1。 游戲要達到的目標什是把所有W都移到B的左邊。對這個問題，請定義一個啟發(fā)函數h(n)，并給出用這個啟發(fā)函數產生的搜索樹。你能否判別這個啟發(fā)函數是否滿足下解要求？再求出的搜索樹中，對所有節(jié)點是否滿足單調限制？ 解：設h(x)=每個W左邊的B的個數，f(x)=d(x)+3*h(x)，其搜索樹如下： f(x)=0+12=12 B B W W E f(x)=1+12=13 B B E W W f(x)=1+12=13