人工智能原理和應(yīng)用(第二版)習(xí)題答案及解析

...wd......wd......wd...知識(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ī)械手，要處理的世界有一張桌子，桌上可堆放假設(shè)干一樣的方積木塊。機(jī)械手有4個(gè)操作積木的典型動(dòng)作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如以以以下圖所示。AABCCACABB圖機(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)，HANDEMPTYStack(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(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(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(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)夫、狼、山羊、白菜問(wèn)題。農(nóng)夫、狼、山羊、白菜全部放在一條河的左岸，現(xiàn)在要把他們?nèi)克偷胶拥挠野度?，農(nóng)夫有一條船，過(guò)河時(shí)，除農(nóng)夫外船上至多能載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農(nóng)夫在那里。似規(guī)劃出一個(gè)確保全部安全過(guò)河的方案。請(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(農(nóng)夫)?AL(船)?AL(狼)?AL(羊)AL(農(nóng)夫)AL(船)AL(狼)AL(白菜)?AL(羊)AL(狼)AL(白菜)?AL(農(nóng)夫)?AL(船)?AL(羊)R-LR-L(羊)L-R(狼)L-R(羊)AL(船)R-LR-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(農(nóng)夫)?L-R(羊)?AL(農(nóng)夫)?AL(船)?AL(羊)?AL(白菜)?AL(狼)R-LL-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大于yGE(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ī)。gGSgGSGS解：gGSgGSGS占有權(quán)計(jì)算機(jī)學(xué)生占有權(quán)計(jì)算機(jī)學(xué)生AKOISAISAFAKOISAISAFOwnsOwnerOwnsOwnercosgcosg(2)高教師從3月到7月給計(jì)算機(jī)系學(xué)生講《計(jì)算機(jī)網(wǎng)絡(luò)》課。解：7月8月7月8月StartEndStartEnd教師ISAObjectSubject高教師計(jì)算機(jī)系學(xué)生講課事件教師ISAObjectSubject高教師計(jì)算機(jī)系學(xué)生講課事件ActionCaurseActionCaurse計(jì)算機(jī)網(wǎng)絡(luò)講課計(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的比分完畢。解：比賽比賽AKOAKOParticipants1Outcome3:22Participants1Outcome3:22足球賽紅隊(duì)紅隊(duì)Participants2Participants2藍(lán)隊(duì)藍(lán)隊(duì)2.19請(qǐng)把以下命題用一個(gè)語(yǔ)義網(wǎng)絡(luò)表示出來(lái)：(1)樹(shù)和草都是植物；植物解：植物AKOAKOAKOAKO草樹(shù)草樹(shù)(2)樹(shù)和草都有葉和根；根葉解：根葉HaveHaveHaveHave植物植物是一種是一種是一種是一種草樹(shù)草樹(shù)(3)水草是草，且生長(zhǎng)在水中；解：LiveAKOAKO水草LiveAKOAKO水草水中植物草水中植物草(4)果樹(shù)是樹(shù)，且會(huì)結(jié)果；解：CanAKOAKO果樹(shù)CanAKOAKO果樹(shù)結(jié)果植物樹(shù)結(jié)果植物樹(shù)(5)梨樹(shù)是果樹(shù)中的一種，它會(huì)結(jié)梨。解：CanAKOAKO梨樹(shù)CanAKOAKO梨樹(shù)樹(shù)果樹(shù)結(jié)梨樹(shù)果樹(shù)結(jié)梨2.25假設(shè)有以下一段天氣預(yù)報(bào)：“北京地區(qū)今天白天晴，偏北風(fēng)3級(jí)，最高氣溫12o，最低氣溫-2o，降水概率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<Teachers-Students>Name：Unit〔Last-name，F(xiàn)irst-name〕Sex：Area〔male，female〕Default：maleAge：Unit〔Years〕Telephone：HomeUnit〔Number〕MobileUnit〔Number〕教師框架Frame<Teachers>AKO<Teachers-Students>Major：Unit〔Major-Name〕Lectures：Unit〔Course-Name〕Field：Unit〔Field-Name〕Project：Area〔National，Provincial，Other〕Default：ProvincialPaper：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.8判斷以下公式是否為可合一，假設(shè)可合一，則求出其最一般合一。(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把以下謂詞公式化成子句集：(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)是Skolem標(biāo)準(zhǔn)型，且P(x,y)∧Q(x,y)已經(jī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)型。再消去全稱量詞得子句集：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)型。最后消去全稱量詞得子句集：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)型。最后消去全稱量詞得子句集：S={?P(x,y)∨Q(x,y)∨R(x,f(x,y))}3-13判斷以下子句集中哪些是不可滿足的：{?P∨Q,?Q,P,?P}{P∨Q,?P∨Q,P∨?Q,?P∨?Q}{P(y)∨Q(y),?P(f(x))∨R(a)}{?P(x)∨Q(x),?P(y)∨R(y),P(a),S(a),?S(z)∨?R(z)}{?P(x)∨Q(f(x),a),?P(h(y))∨Q(f(h(y)),a)∨?P(z)}{P(x)∨Q(x)∨R(x),?P(y)∨R(y),?Q(a),?R(b)}解：(1)不可滿足，其歸結(jié)過(guò)程為：??P∨Q?Q?PPNILP∨P∨Q?P∨QQP∨?Q?P∨?Q?QNIL(3)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4)不可滿足，其歸結(jié)過(guò)程略(5)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6)不可滿足，其歸結(jié)過(guò)程略3.14對(duì)以下各題分別證明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.y)))F2:(x)(P(x)∧(y)(R(y)→L(x.y)))G:(x)(R(x)→Q(x))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?P(x,b)P(a,b)NIL{a/x}NIL所以，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(a)∨Q(b){a/b}?P(x)?P(x)∨?Q(x)Q(a){a/x}?P(?P(a)P(x){a/x}NILNIL所以，G是F的邏輯結(jié)論同理可求得(3)、(4)和(5)，其求解過(guò)程略。3.15設(shè)：如果x是y的父親，y是z的父親，則x是z的祖父；每個(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ō)：“趙與人民幣中至少有一個(gè)人作案〞，貞察員B說(shuō)：“人民幣與孫中至少有一個(gè)人作案〞，貞察員C說(shuō)：“孫與李中至少有一個(gè)人作案〞，貞察員D說(shuō)：“趙與孫中至少有一個(gè)人與此案無(wú)關(guān)〞，貞察員E說(shuō)：“人民幣與李中至少有一個(gè)人與此案無(wú)關(guān)〞。如果這5個(gè)偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰(shuí)是盜竊犯。解：(1)先定義謂詞和常量設(shè)C(x)表示x作案，Z表示趙，Q表示人民幣，S表示孫，L表示李(2)將事實(shí)用謂詞公式表示出來(lái)趙與人民幣中至少有一個(gè)人作案：C(Z)∨C(Q)人民幣與孫中至少有一個(gè)人作案：C(Q)∨C(S)孫與李中至少有一個(gè)人作案：C(S)∨C(L)趙與孫中至少有一個(gè)人與此案無(wú)關(guān)：?(C(Z)∧C(S))，即?C(Z)∨?C(S)人民幣與李中至少有一個(gè)人與此案無(wú)關(guān)：?(C(Q)∧C(L))，即?C(Q)∨?C(L)(3)將所要求的問(wèn)題用謂詞公式表示出來(lái)，并與其否認(rèn)取析取。設(shè)作案者為u，則要求的結(jié)論是C(u)。將其與其否)取析取，得：?C(u)∨C(u)(4)對(duì)上述擴(kuò)大的子句集，按歸結(jié)原理進(jìn)展歸結(jié)，其修改的證明樹(shù)如下：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/u}因此，人民幣是盜竊犯。實(shí)際上，本案的盜竊犯不止一人。根據(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/u}C(S)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)公式的否認(rèn)化簡(jiǎn)來(lái)的。刪除策略不可用，原因是子句集中沒(méi)有沒(méi)有重言式和具有包孕關(guān)系的子句。單文字子句策略的歸結(jié)過(guò)程如下：Q(a,f(a))P(x)Q(a,f(a))P(x)∨Q(a,b){b/f(a)}P(x)∨P(x)∨Q(x,b)P(a)Q(a,f(a))Q(aQ(a,f(a))Q(a,b){b/f(a)}Q(Q(a,b)用線性輸入策略〔同時(shí)滿足祖先過(guò)濾策略〕的歸結(jié)過(guò)程如下：P(a)∨P(a)∨Q(a,b)P(x)∨Q(a,b)P(x)∨Q(x,P(x)∨Q(x,b)P(a){a/x}Q(a,f(a))QQ(a,f(a))Q(a,b){b/f(a)}NILNIL3.19設(shè)：能閱讀的人是識(shí)字的；海豚不識(shí)字；有些海豚是很聰明的。請(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èn)化成子句集：?R(x))∨K(x)?K(y)W(z)?W(z)∨K(x))第四步，用歸結(jié)演繹推理進(jìn)展證明W(z)?W(z)?W(z)∨K(x))W(z)K(z)W(z)K(z)NILNIL3.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∨UR∨X∨ZR∨Y∨Z所有子目標(biāo)UTZYXRQP所有目標(biāo)UTZYXRQPYXZX∧YSUTT∨US所有目標(biāo)UTZYXRQP所有目標(biāo)YZU所有子目標(biāo)UTZYXRQP所有目標(biāo)UTZYXRQPYXZX∧YSUTT∨US所有目標(biāo)UTZYXRQP所有目標(biāo)YZUTXPRQYXXYYXXYF規(guī)則F規(guī)則ZX∧YZX∧YX∧YZSSSSUTQPTUQPUTQPTUQP事實(shí)事實(shí)事實(shí)事實(shí)T∨USR(P∨Q)T∨T∨USR(P∨Q)T∨URS(P∨Q)(S∧(T∨(S∧(T∨U))((P∨Q)∧R)(S∧(T∨U))((P∨Q)∧R)((P∨Q)((P∨Q)∧R)∨(S∧(T∨U))((P∨Q)∧R)∨(S∧(T∨U))3.24設(shè)有如下一段知識(shí)：“張、王和李都屬于高山協(xié)會(huì)。該協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)發(fā)動(dòng)，就是登山運(yùn)發(fā)動(dòng)，其中不喜歡雨的運(yùn)發(fā)動(dòng)是登山運(yùn)發(fā)動(dòng)，不喜歡雪的運(yùn)發(fā)動(dòng)不是滑雪運(yùn)發(fā)動(dòng)。王不喜歡張所喜歡的一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪。〞試用謂詞公式集合表示這段知識(shí)，這些謂詞公式要適合一個(gè)逆向的基于規(guī)則的演繹系統(tǒng)。試說(shuō)明這樣一個(gè)系統(tǒng)若何才能答復(fù)以下問(wèn)題：“高山俱樂(lè)部中有沒(méi)有一個(gè)成員，他是一個(gè)登山運(yùn)發(fā)動(dòng)，但不是一個(gè)滑雪運(yùn)發(fā)動(dòng)〞解：(1)先定義謂詞A(x)表示x是高山協(xié)會(huì)會(huì)員S(x)表示x是滑雪運(yùn)發(fā)動(dòng)C(x)表示x是登山運(yùn)發(fā)動(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)發(fā)動(dòng)，就是登山運(yùn)發(fā)動(dòng)(x)(A(x)∧?S(x)→C(x))高山協(xié)會(huì)中不喜歡雨的運(yùn)發(fā)動(dòng)是登山運(yùn)發(fā)動(dòng)(x)(?L(x,Rain)→C(x))高山協(xié)會(huì)中不喜歡雪的運(yùn)發(fā)動(dòng)不是滑雪運(yùn)發(fā)動(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)發(fā)動(dòng)，但不是一個(gè)滑雪運(yùn)發(fā)動(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)∧?C(x)∧?S(x)?A(x)C(x)?C(x)?S(x)r2r2r34?L?L(x,Rain)?L(x,Snow){Wang/x,y/Rain}{Wang/x,y/Snow}{Wang/x,y/Rain}{Wang/x,y/Snow}?L?L(Wang,y)?L(Wang,y)r4r4r4r4L(Zhang,y)L(Zhang,y)L(Zhang,y){Rain/y}{Snow/y}{Rain/y}{Snow/y}L(Zhang,L(Zhang,Snow)L(Zhang,Rain)搜索策略局部參考答案4.5有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到以下條件的限制：(1)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河；如果沒(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)(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,0)(1,0,1,0)L(2)L(2)(0,0,0,0)(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的路徑。CC12222222CC12222222BAAB42BAAB42234131231331412341312313314144444343初始狀態(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)90o，這些操作〔算符〕的排列順序是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)323221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334213112244qA314241231234qB132314242413qC4.7題的廣度優(yōu)先搜索樹(shù)S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索略。4.8圖4-32是5個(gè)城市的交通圖，城市之間的連線旁邊的數(shù)字是城市之間路程的費(fèi)用。要求從A城出發(fā)，經(jīng)過(guò)其它各城市一次且僅一次，最后回到A城，請(qǐng)找出一條最優(yōu)線路。A10B289C1163128D9E432交通費(fèi)用圖解：這個(gè)問(wèn)題又稱為旅行商問(wèn)題〔travellingsalesmanproblem,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ì)這類問(wèn)題只能用搜索的方法來(lái)解決。以以以下圖是對(duì)圖4-32按最小代價(jià)搜索所得到的搜索樹(shù)，樹(shù)中的節(jié)點(diǎn)為城市名稱，節(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à)。0A0A119210119210102119BDCE102119BDCE9869312838612898693128386128201917CDB181221ECB10105EDB1201917CDB181221ECB10105EDB16E2218DC331288933128892312386886896912612923123868868969126129883C32B222925DC2020EBB16D191622DE31C32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426CB2720C1417BE2524DC2621DE9838E12912BD272426CB2720C1417BE2524DC2621DE68126666812666E3133E9328D31B926B26E831B28DD273E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B30282023E35ED27D32C34B302820E28CBE28CB21021030A30A30A30A圖4.32的最小代價(jià)搜索樹(shù)圖4.32的最小代價(jià)搜索樹(shù)可以看出，其最短路經(jīng)是A-C-D-E-B-A或A-B-E-D-C-A其實(shí)，它們是同一條路經(jīng)。4.11設(shè)有如下構(gòu)造的移動(dòng)將牌游戲：BBWWE其中，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=12f(x)=0+12=12BBWWEf(x)=1+12=13f(x)=1+12=13BBEWWf(x)=1+12=13f(x)=1+12=13BBWEWf(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=10WBEBWf(x)=5+3=8f(x)=5+3=8WBWBEf(x)=6+3=9f(x)=6+3=9WBWEBf(x)=7+0=7f(x)=7+0=7WBWEB4.14設(shè)有如圖4-34的與/或/樹(shù)，請(qǐng)分別按和代價(jià)法及最大代價(jià)法求解樹(shù)的代價(jià)。AABCDt2t3t4t1圖4.34習(xí)題4.14的與/或樹(shù)56217223E解：假設(shè)按和代價(jià)法，則該解樹(shù)的代價(jià)為：h(A)=2+3+2+5+2+1+6=21假設(shè)按最大代價(jià)法，則該解樹(shù)的代價(jià)為：h(A)=max{h(B)+5,h(C)+6}=max{(h(E)+2)+5,h(C)+6}=max{(max(2,3)+2)+5,max(2,1)+6}=max((5+5,2+6)=104.15設(shè)有如圖4-35所示的博弈樹(shù)，其中最下面的數(shù)字是假設(shè)的估值，請(qǐng)對(duì)該博弈樹(shù)作如下工作：(1)計(jì)算各節(jié)點(diǎn)的倒推值；利用α-β剪枝技術(shù)剪去不必要的分枝。圖4.35習(xí)題4.15的博弈樹(shù)圖4.35習(xí)題4.15的博弈樹(shù)305-336-2354-3068-3369S0ABCDEFGHIJKLNM解：各節(jié)點(diǎn)的倒推值和剪枝情況如以以以下圖所示：習(xí)題4.15的倒推值和剪枝情況習(xí)題4.15的倒推值和剪枝情況305-336-2354-3068-336≤0≥0≤0≤-39≤3≥3≤4≥4≤4≥4≤-3≤6≥6S0ABCDEFGHIJKMNL第5章計(jì)算智能局部參考答案5.15對(duì)遺傳法的選擇操作：設(shè)種群規(guī)模為4，個(gè)體采用二進(jìn)制編碼，適應(yīng)度函數(shù)為f(x)=x2，初始種群情況如下表所示：編號(hào)個(gè)體串x適應(yīng)值百分比累計(jì)百分比選中次數(shù)S01101010S0201004S03110012S0401117假設(shè)規(guī)定選擇概率為100%,選擇算法為輪盤(pán)賭算法，且依次生成的4個(gè)隨機(jī)數(shù)為0.42,0.16,0.89,0.71，請(qǐng)?zhí)顚?xiě)上表中的全部?jī)?nèi)容，并求出經(jīng)本次選擇操作后所得到的新的種群。解：表格的完整內(nèi)容為：編號(hào)個(gè)體串x適應(yīng)值百分比累計(jì)百分比選中次數(shù)S0110101010032.3632.361S0201004165.1837.540S0311001214444.6084.142S04011174915.861001本次選擇后所得到的新的種群為：S01=1100S02=1010S03=0111S04=11005.18設(shè)某小組有5個(gè)同學(xué)，分別為S1,S2,S3,S4,S5。假設(shè)對(duì)每個(gè)同學(xué)的“學(xué)習(xí)好〞程度打分：S1:95S2:85S3:80S4:70S5:90這樣就確定了一個(gè)模糊集F，它表示該小組同學(xué)對(duì)“學(xué)習(xí)好〞這一模糊概念的隸屬程度，請(qǐng)寫(xiě)出該模糊集。解：對(duì)模糊集為F，可表示為：F=95/S1+85/S2+80/S3+70/S4+90/S5或F={95/S1,85/S2,80/S3,70/S4,90/S5}5.19設(shè)有論域U={u1,u2,u3,u4,u5}并設(shè)F、G是U上的兩個(gè)模糊集，且有F=0.9/u1+0.7/u2+0.5/u3+0.3/u4G=0.6/u3+0.8/u4+1/u5請(qǐng)分別計(jì)算F∩G，F(xiàn)∪G，﹁F。解：F∩G=(0.9∧0)/u1+(0.7∧0)/u2+(0.5∧0.6)/u3+(0.3∧0.8)/u4+(0∧1)/u5=0/u1+0/u2+0.5/u3+0.3/u4+0/u5=0.5/u3+0.3/u4F∪G=(0.9∨0)/u1+(0.7∨0)/u2+(0.5∨0.6)/u3+(0.3∨0.8)/u4+(0∨1)/u5=0.9/u1+0.7/u2+0.6/u3+0.8/u4+1/u5﹁F=(1-0.9)/u1+(1-0.7)/u2+(1-0.5)/u3+(1-0.3)/u4+(1-0)/u5=0.1/u1+0.3/u2+0.5/u3+0.7/u4+1/u55.21設(shè)有如下兩個(gè)模糊關(guān)系：請(qǐng)寫(xiě)出R1與R2的合成R1οR2。解：R(1,1)=(0.3∧0.2)∨(0.7∧0.6)∨(0.2∧0.9)=0.2∨0.6∨0.2=0.6R(1,2)=(0.3∧0.8)∨(0.7∧0.4)∨(0.2∧0.1)=0.3∨0.4∨0.1=0.4R(2,1)=(1∧0.2)∨(0∧0.6)∨(0.4∧0.9)=0.2∨0∨0.4=0.4R(2,2)=(1∧0.8)∨(0∧0.4)∨(0.4∧0.1)=0.8∨0∨0.1=0.8R(3,1)=(0∧0.2)∨(0.5∧0.6)∨(1∧0.9)=0.2∨0.6∨0.9=0.9R(3,2)=(0∧0.8)∨(0.5∧0.4)∨(1∧0.1)=0∨0.4∨0.1=0.4因此有5.22設(shè)F是論域U上的模糊集，R是U×V上的模糊關(guān)系，F(xiàn)和R分別為：求模糊變換FοR。解：={0.1∨0.4∨0.6,0.3∨0.6∨0.3,0.4∨0.6∨0}={0.6,0.6,0.6}不確定性推理局部參考答案6.8設(shè)有如下一組推理規(guī)則:r1:IFE1THENE2(0.6)r2:IFE2ANDE3THENE4(0.7)r3:IFE4THENH(0.8)r4:IFE5THENH(0.9)且CF(E1)=0.5,CF(E3)=0.6,CF(E5)=0.7。求CF(H)=?解：(1)先由r1求CF(E2)CF(E2)=0.6×max{0,CF(E1)}=0.6×max{0,0.5}=0.3(2)再由r2求CF(E4)CF(E4)=0.7×max{0,min{CF(E2),CF(E3)}}=0.7×max{0,min{0.3,0.6}}=0.21(3)再由r3求CF1(H)CF1(H)=0.8×max{0,CF(E4)}=0.8×max{0,0.21)}=0.168(4)再由r4求CF2(H)CF2(H)=0.9×max{0,CF(E5)}=0.9×max{0,0.7)}=0.63(5)最后對(duì)CF1(H)和CF2(H)進(jìn)展合成，求出CF(H)CF(H)=CF1(H)+CF2(H)+CF1(H)×CF2(H)=0.6926.10設(shè)有如下推理規(guī)則r1:IFE1THEN(2,0.00001)H1r2:IFE2THEN(100,0.0001)H1r3:IFE3THEN(200,0.001)H2r4:IFH1THEN(50,0.1)H2且P(E1)=P(E2)=P(H3)=0.6,P(H1)=0.091,P(H2)=0.01,又由用戶告知：P(E1|S1)=0.84,P(E2|S2)=0.68,P(E3|S3)=0.36請(qǐng)用主觀Bayes方法求P(H2|S1,S2,S3)=?解：(1)由r1計(jì)算O(H1|S1)先把H1的先驗(yàn)概率更新為在E1下的后驗(yàn)概率P(H1|E1)P(H1|E1)=(LS1×P(H1))/((LS1-1)×P(H1)+1)=(2×0.091)/((2-1)×0.091+1)=0.16682由于P(E1|S1)=0.84>P(E1)，使用P(H|S)公式的后半局部，得到在當(dāng)前觀察S1下的后驗(yàn)概率P(H1|S1)和后驗(yàn)幾率O(H1|S1)P(H1|S1)=P(H1)+((P(H1|E1)–P(H1))/(1-P(E1)))×(P(E1|S1)–P(E1))=0.091+(0.16682–0.091)/(1–0.6))×(0.84–0.6)=0.091+0.18955×0.24=0.136492O(H1|S1)=P(H1|S1)/(1-P(H1|S1))=0.15807(2)由r2計(jì)算O(H1|S2)先把H1的先驗(yàn)概率更新為在E2下的后驗(yàn)概率P(H1|E2)P(H1|E2)=(LS2×P(H1))/((LS2-1)×P(H1)+1)=(100×0.091)/((100-1)×0.091+1)=0.90918由于P(E2|S2)=0.68>P(E2)，使用P(H|S)公式的后半局部，得到在當(dāng)前觀察S2下的后驗(yàn)概率P(H1|S2)和后驗(yàn)幾率O(H1|S2)P(H1|S2)=P(H1)+((P(H1|E2)–P(H1))/(1-P(E2)))×(P(E2|S2)–P(E2))=0.091+(0.90918–0.091)/(1–0.6))×(0.68–0.6)=0.25464O(H1|S2)=P(H1|S2)/(1-P(H1|S2))=0.34163(3)計(jì)算O(H1|S1,S2)和P(H1|S1,S2)先將H1的先驗(yàn)概率轉(zhuǎn)換為先驗(yàn)幾率O(H1)=P(H1)/(1-P(H1))=0.091/(1-0.091)=0.10011再根據(jù)合成公式計(jì)算H1的后驗(yàn)幾率O(H1|S1,S2)=(O(H1|S1)/O(H1))×(O(H1|S2)/O(H1))×O(H1)=(0.15807/0.10011)×(0.34163)/0.10011)×0.10011=0.53942再將該后驗(yàn)幾率轉(zhuǎn)換為后驗(yàn)概率P(H1|S1,S2)=O(H1|S1,S2)/(1+O(H1|S1,S2))=0.35040(4)由r3計(jì)算O(H2|S3)先把H2的先驗(yàn)概率更新為在E3下的后驗(yàn)概率P(H2|E3)P(H2|E3)=(LS3×P(H2))/((LS3-1)×P(H2)+1)=(200×0.01)/((200-1)×0.01+1)=0.09569由于P(E3|S3)=0.36<P(E3)，使用P(H|S)公式的前半局部，得到在當(dāng)前觀察S3下的后驗(yàn)概率P(H2|S3)和后驗(yàn)幾率O(H2|S3)P(H2|S3)=P(H2|?E3)+(P(H2)–P(H2|?E3))/P(E3))×P(E3|S3)由當(dāng)E3肯定不存在時(shí)有P(H2|?E3)=LN3×P(H2)/((LN3-1)×P(H2)+1)=0.001×0.01/((0.001-1)×0.01+1)=0.00001因此有P(H2|S3)=P(H2|?E3)+(P(H2)–P(H2|?E3))/P(E3))×P(E3|S3)=0.00001+((0.01-0.00001)/0.6)×0.36=0.00600O(H2|S3)=P(H2|S3)/(1-P(H2|S3))=0.00604(5)由r4計(jì)算O(H2|H1)先把H2的先驗(yàn)概率更新為在H1下的后驗(yàn)概率P(H2|H1)P(H2|H1)=(LS4×P(H2))/((LS4-1)×P(H2)+1)=(50×0.01)/((50-1)×0.01+1)=0.33557由于P(H1|S1,S2)=0.35040>P(H1)，使用P(H|S)公式的后半局部，得到在當(dāng)前觀察S1,S2下H2的后驗(yàn)概率P(H2|S1,S2)和后驗(yàn)幾率O(H2|S1,S2)P(H2|S1,S2)=P(H2)+((P(H2|H1)–P(H2))/(1-P(H1)))×(P(H1|S1,S2)–P(H1))=0.01+(0.33557–0.01)/(1–0.091))×(0.35040–0.091)=0.10291O(H2|S1,S2)=P(H2|S1,S2)/(1-P(H2|S1,S2))=0.10291/(1-0.10291)=0.11472(6)計(jì)算O(H2|S1,S2,S3)和P(H2|S1,S2,S3)先將H2的先驗(yàn)概率轉(zhuǎn)換為先驗(yàn)幾率O(H2)=P(H2)/(1-P(H2))=0.01/(1-0.01)=0.01010再根據(jù)合成公式計(jì)算H1的后驗(yàn)幾率O(H2|S1,S2,S3)=(O(H2|S1,S2)/O(H2))×(O(H2|S3)/O(H2))×O(H2)=(0.11472/0.01010)×(0.00604)/0.01010)×0.01010=0.06832再將該后驗(yàn)幾率轉(zhuǎn)換為后驗(yàn)概率P(H2|S1,S2,S3)=O(H1|S1,S2,S3)/(1+O(H1|S1,S2,S3))=0.06832/(1+0.06832)=0.06395可見(jiàn)，H2原來(lái)的概率是0.01，經(jīng)過(guò)上述推理后得到的后驗(yàn)概率是0.06395，它相當(dāng)于先驗(yàn)概率的6倍多。6.11設(shè)有如下推理規(guī)則r1:IFE1THEN(100,0.1)H1r2:IFE2THEN(50,0.5)H2r3:IFE3THEN(5,0.05)H3且P(H1)=0.02,P(H2)=0.2,P(H3)=0.4，請(qǐng)計(jì)算當(dāng)證據(jù)E1，E2，E3存在或不存在時(shí)P(Hi|Ei)或P(Hi|﹁Ei)的值各是多少(i=1,2,3)解：(1)當(dāng)E1、E2、E3肯定存在時(shí)，根據(jù)r1、r2、r3有P(H1|E1)=(LS1×P(H1))/((LS1-1)×P(H1)+1)=(100×0.02)/((100-1)×0.02+1)=0.671P(H2|E2)=(LS2×P(H2))/((LS2-1)×P(H2)+1)=(50×0.2)/((50-1)×0.2+1)=0.9921P(H3|E3)=(LS3×P(H3))/((LS3-1)×P(H3)+1)=(5×0.4)/((5-1)×0.4+1)=0.769(2)當(dāng)E1、E2、E3肯定存在時(shí)，根據(jù)r1、r2、r3有P(H1|?E1)=(LN1×P(H1))/((LN1-1)×P(H1)+1)=(0.1×0.02)/((0.1-1)×0.02+1)=0.002P(H2|?E2)=(LN2×P(H2))/((LN2-1)×P(H2)+1)=(0.5×0.2)/((0.5-1)×0.2+1)=0.111P(H3|?E3)=(LN3×P(H3))/((LN3-1)×P(H3)+1)=(0.05×0.4)/((0.05-1)×0.4+1)=0.0326.13設(shè)有如下一組推理規(guī)則:r1:IFE1ANDE2THENA={a}(CF={0.9})r2:IFE2AND(E3ORE4)THENB={b1,b2}(CF={0.8,0.7})r3:IFATHENH={h1,h2,h3}(CF={0.6,0.5,0.4})r4:IFBTHENH={h1,h2,h3}(CF={0.3,0.2,0.1})且初始證據(jù)確實(shí)定性分別為：CER(E1)=0.6,CER(E2)=0.7,CER(E3)=0.8,CER(E4)=0.9。假設(shè)|Ω|=10，求CER(H)。解：其推理過(guò)程參考例6.9具體過(guò)程略6.15設(shè)U=V={1，2，3，4}且有如下推理規(guī)則：IFxis少THENyis多其中，“少〞與“多〞分別是U與V上的模糊集，設(shè)少=0.9/1+0.7/2+0.4/3多=0.3/2+0.7/3+0.9/4事實(shí)為xis較少“較少〞的模糊集為較少=0.8/1+0.5/2+0.2/3請(qǐng)用模糊關(guān)系Rm求出模糊結(jié)論。解：先用模糊關(guān)系Rm求出規(guī)則IFxis少THENyis多所包含的模糊關(guān)系RmRm(1,1)=(0.9∧0)∨(1-0.9)=0.1Rm(1,2)=(0.9∧0.3)∨(1-0.9)=0.3Rm(1,3)=(0.9∧0.7)∨(1-0.9)=0.7Rm(1,4)=(0.9∧0.9)∨(1-0.9)=0.7Rm(2,1)=(0.7∧0)∨(1-0.7)=0.3Rm(2,2)=(0.7∧0.3)∨(1-0.7)=0.3Rm(2,3)=(0.7∧0.7)∨(1-0.7)=0.7Rm(2,4)=(0.7∧0.9)∨(1-0.7)=0.7Rm(3,1)=(0.4∧0)∨(1-0.4)=0.6Rm(3,2)=(0.4∧0.3)∨(1-0.4)=0.6Rm(3,3)=(0.4∧0.7)∨(1-0.4)=0.6Rm(3,4)=(0.4∧0.9)∨(1-0.4)=0.6Rm(4,1)=(0∧0)∨(1-0)=1Rm(4,2)=(0∧0.3)∨(1-0)=1Rm(4,3)=(0∧0.7)∨(1-0)=1Rm(3,4)=(0∧0.9)∨(1-0)=1即：因此有即，模糊結(jié)論為Y’={0.3,0.3,0.7,0.8}6.16設(shè)U=V=W={1,2,3,4}且設(shè)有如下規(guī)則：r1：IFxisFTHENyisGr2：IFyisGTHENzisHr3：IFxisFTHENzisH其中，F(xiàn)、G、H的模糊集分別為：F=1/1+0.8/2+0.5/3+0.4/4G=0.1/2+0.2/3+0.4/4H=0.2/2+0.5/3+0.8/4請(qǐng)分別對(duì)各種模糊關(guān)系驗(yàn)證滿足模糊三段論的情況。解：此題的解題思路是：由模糊集F和G求出r1所表示的模糊關(guān)系R1m,R1c,R1g再由模糊集G和H求出r2所表示的模糊關(guān)系R2m,R2c,R2g再由模糊集F和H求出r3所表示的模糊關(guān)系R3m,R3c,R3g然后再將R1m,R1c,R1g分別與R2m,R2c,R2g合成得R12m,R12c,R12g最后將R12m,R12c,R12g分別與R3m,R3c,R3g對(duì)比機(jī)器學(xué)習(xí)參考答案7-6設(shè)訓(xùn)練例子集如下表所示：序號(hào)屬性分類x1x21TT+2TT+3TF-4FF+5FT_6FT_請(qǐng)用ID3算法完成其學(xué)習(xí)過(guò)程。解：設(shè)根節(jié)點(diǎn)為S，盡管它包含了所有的訓(xùn)練例子，但卻沒(méi)有包含任何分類信息，因此具有最大的信息熵。即：H(S)=-(P(+)log2P(+)+P(-)log2P(-))式中P(+)=3/6，P(-)=3/6分別是決策方案為“+〞或“-〞時(shí)的概率。因此有H(S)=-((3/6)log2(3/6)+(3/6)log2(3/6))=1按照ID3算法，需要選擇一個(gè)能使S的期望熵為最小的一個(gè)屬性對(duì)根節(jié)點(diǎn)進(jìn)展擴(kuò)展，因此我們需要先計(jì)算S關(guān)于每個(gè)屬性的條件熵：H(S|xi)=(|ST|/|S|)*H(ST)+(|SF|/|S|)*H(SF)其中，T和F為屬性xi的屬性值，ST和SF分別為xi=T或xi=F時(shí)的例子集，|S|、|ST|和|SF|分別為例子集S、ST和SF