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

《人工智能原理及其應(yīng)用第2版》王萬(wàn)森編著電子工業(yè)出版社課后習(xí)題答案37.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能原理及其應(yīng)用第2版》王萬(wàn)森編著電子工業(yè)出版社課后習(xí)題答案37.doc（38頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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