人工智能原理及其應(yīng)用考試復(fù)習(xí)題

知識表示方法部分參考答案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.18請對下列命題分別寫出它們的語義網(wǎng)絡(luò)：(1)每個學(xué)生都有一臺計算機。gGSgGSGS解：gGSgGSGS占有權(quán)計算機學(xué)生占有權(quán)計算機學(xué)生AKOISAISAFAKOISAISAFOwnsOwnerOwnsOwnercosgcosg(2)高老師從3月到7月給計算機系學(xué)生講《計算機網(wǎng)絡(luò)》課。解：7月8月7月8月StartEndStartEnd老師ISAObjectSubject高老師計算機系學(xué)生老師ISAObjectSubject高老師計算機系學(xué)生講課事件ActionCaurseActionCaurse計算機網(wǎng)絡(luò)講課計算機網(wǎng)絡(luò)講課(3)學(xué)習(xí)班的學(xué)員有男、有女、有研究生、有本科生。解：參例2.14(4)創(chuàng)新公司在科海大街56號，劉洋是該公司的經(jīng)理，他32歲、碩士學(xué)位。解：參例2.10(5)紅隊與藍(lán)隊進行足球比賽，最后以3：2的比分結(jié)束。解：比賽比賽AKOAKOParticipants1Outcome3:22Participants1Outcome3:22足球賽紅隊紅隊Participants2Participants2藍(lán)隊藍(lán)隊2.19請把下列命題用一個語義網(wǎng)絡(luò)表示出來：(1)樹和草都是植物；植物解：植物AKOAKOAKOAKO草樹草樹(2)樹和草都有葉和根；根葉解：根葉HaveHaveHaveHave植物植物是一種是一種是一種是一種草樹草樹(3)水草是草，且生長在水中；解：LiveAKOAKO水草LiveAKOAKO水草水中植物草水中植物草(4)果樹是樹，且會結(jié)果；解：CanAKOAKO果樹CanAKOAKO果樹結(jié)果植物樹結(jié)果植物樹(5)梨樹是果樹中的一種，它會結(jié)梨。解：CanAKOAKO梨樹CanAKOAKO梨樹樹果樹結(jié)梨樹果樹結(jié)梨5.18設(shè)某小組有5個同學(xué)，分別為S1,S2,S3,S4,S5。若對每個同學(xué)的“學(xué)習(xí)好”程度打分：S1:95S2:85S3:80S4:70S5:90這樣就確定了一個模糊集F，它表示該小組同學(xué)對“學(xué)習(xí)好”這一模糊概念的隸屬程度，請寫出該模糊集。解：對模糊集為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上的兩個模糊集，且有F=0.9/u1+0.7/u2+0.5/u3+0.3/u4G=0.6/u3+0.8/u4+1/u5請分別計算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è)有如下兩個模糊關(guān)系：請寫出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}確定性推理部分參考答案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把下列謂詞公式化成子句集：(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)}再進行變元換名得子句集：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判斷下列子句集中哪些是不可滿足的：{?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é)過程為：??P∨Q?Q?PPNIL(2)不可滿足，其歸結(jié)過程為：PP∨Q?P∨QQP∨?Q?P∨?Q?QNIL(3)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4)不可滿足，其歸結(jié)過程略(5)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6)不可滿足，其歸結(jié)過程略3.14對下列各題分別證明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)}再對S進行歸結(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)}因此，擴充的子句集為：S={P(x)，(Q(a)∨Q(b))，?P(x)∨?Q(x)}再對S進行歸結(jié)：Q(a)∨Q(a)∨Q(b)Q(a)?P(x)∨?Q(x)?P(a)P(x)NILQ(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)，其求解過程略。3.15設(shè)已知：如果x是y的父親，y是z的父親，則x是z的祖父；每個人都有一個父親。使用歸結(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/u}{x/s,y/r}{y/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)對上述擴充的子句集，按歸結(jié)原理進行歸結(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/u}因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據(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é)式。解：支持集策略不可用，原因是沒有指明哪個子句是由目標(biāo)公式的否定化簡來的。刪除策略不可用，原因是子句集中沒有沒有重言式和具有包孕關(guān)系的子句。單文字子句策略的歸結(jié)過程如下：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)用線性輸入策略（同時滿足祖先過濾策略）的歸結(jié)過程如下：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è)已知：能閱讀的人是識字的；海豚不識字；有些海豚是很聰明的。請用歸結(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)?W(z)∨K(x))W(z)K(z)W(z)K(z)NILNIL3.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}的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過程。3.21對線性輸入策略和單文字子句策略分別給出一個反例，以說明它們是不完備的。3.22分別說明正向、逆向、雙向與/或形演繹推理的基本思想。搜索策略部分參考答案4.5有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：(1)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；如果沒有農(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)(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圓盤問題。設(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的路徑。CC12222222CC12222222BAAB42BAAB42234131231331412341312313314144444343初始狀態(tài)S0目標(biāo)狀態(tài)Sg圖431圓盤問題解：設(shè)用qA，qB和qC分別表示把A盤，B盤和C盤繞軸逆時針轉(zhuǎn)動90o，這些操作（算符）的排列順序是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的路徑是S0→2→5→13(Sg)323221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334213112244qA314241231234qB132314242413qC4.7題的廣度優(yōu)先搜索樹S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索略。4.11設(shè)有如下結(jié)構(gòu)的移動將牌游戲：BBWWE其中，B表示