人工智能經(jīng)典習題集及各章匯報

人工智能各章小結及習題解答第一部分緒論習題解答：1．什么是人工智能？進展過程中經(jīng)歷了哪些時期？解：人工智能是計算機科學的一個重要分支，也是一門正在進展中的綜合性前沿學科，它是由計算機科學、操縱論、信息論、神經(jīng)生理學、哲學、語言學等多種學科相互滲透而進展起來的，目前正處于進展時期尚未形成完整體系。進展過程中經(jīng)歷的時期有：第一時期（40年代中～50年代末）神經(jīng)元網(wǎng)絡時代第二時期（50年代中～60年代中）通用方法時代第三時期（60年代中～80年代初）知識工程時代第四時期（80年代中～90年代初）新的神經(jīng)元網(wǎng)絡時代第五時期（90年代初～現(xiàn)在）海量信息處理與網(wǎng)絡時代2．人工智能研究的差不多內(nèi)容是什么？解：差不多內(nèi)容是：搜索技術、知識表示、規(guī)劃方法、機器學習、認知科學、自然語言理解與機器翻譯、專家系統(tǒng)與知識工程、定理證明、博弈、機器人、數(shù)據(jù)挖掘與知識發(fā)覺、多Agent系統(tǒng)、復雜系統(tǒng)、足球機器人、人機交互技術等。3．人工智能要緊有哪幾大研究學派？解：（１）符號主義學派：由心理學途徑產(chǎn)生，符號主義認為人工智能起源于數(shù)理邏輯，人類認識（智能）的差不多元素是符號，而智能行為則是符號運算的結果。（２）連接主義學派：由生理學途徑產(chǎn)生，連接主義又稱為仿生學派，認為人工智能的差不多元素是神經(jīng)元，智能產(chǎn)生于大量神經(jīng)元的并行分布式聯(lián)結之中，而智能行為則是聯(lián)結計算的結果。（３）行為主義學派：由生物演化途徑產(chǎn)生，行為主義認為人工智能起源于操縱論，提出智能取決于感知和行為，取決于對外界復雜環(huán)境的適應，而不是表示和推理。４．人工智能有哪些要緊的研究領域？解：（１）問題求解（２）邏輯推理與定理證明（３）自然語言理解（４）自動程序設計（５）專家系統(tǒng)（６）機器學習（７）神經(jīng)網(wǎng)絡（８）機器人學（９）模式識不（１０）機器視覺（１１）智能操縱（１２）智能檢索（１３）智能調(diào)度與指揮（１４）分布式人工智能與Ａｇｅｎｔ（１５）計算智能與進化計算（１６）數(shù)據(jù)挖掘與知識發(fā)覺（１７）人工生命（１８）系統(tǒng)與語言工具第2部分知識與知識表示本章小結：知識表示謂詞表示法知識表示謂詞表示法產(chǎn)生式表示法框架表示法語義網(wǎng)絡表示法框架通常由指定事物各個方面的槽組成，每個槽擁有若干個側(cè)面，而每個側(cè)面又可擁有若干個值。語義網(wǎng)絡由節(jié)點和弧線或鏈線組成，節(jié)點用于表示物體、概念和狀態(tài)，弧線用于表示節(jié)點間的關系。產(chǎn)生式系統(tǒng)由3個差不多部分組成：規(guī)則庫、綜合數(shù)據(jù)庫、操縱系統(tǒng)。首先定義謂詞，指出每個謂詞的確切含義，然后再用連接詞把有關的謂詞連接起來，形成一個謂詞公式表達一個完整的意義。習題解答：1設有如下問題：（1）有五個相互可直達且距離已知的都市A、B、C、D、E，如圖所示；（2）某人從A地動身，去其它四個都市各參觀一次后回到A;（3）找一條最短的旅行路線請用產(chǎn)生式規(guī)則表示旅行過程。解：=1\*GB3①綜合數(shù)據(jù)庫（x）(x)中x能夠是一個字母，也能夠是一個字符串。=2\*GB3②初始狀態(tài)（A）=3\*GB3③目標狀態(tài)（Ax1x2x3x4A）=4\*GB3④規(guī)則集：r1:IFL(S)=5THENGOTO(A)r2:IFL(S)<5THENGOTO(B)r3:IFL(S)<5THENGOTO(C)r4:IFL(S)<5THENGOTO(D)r5:IFL(S)<5THENGOTO(E)其中L(S)為走過的都市數(shù)，GOTO(x)為走向都市x=5\*GB3⑤路線如下圖所示:(A)(A)(AB)(AC)(AD)(AE)(ACB)(ACD)(ACE)(ACDB)(ACDE)(ACDEB)(ACDEBA)751010769108107起始目標最短旅行路線為：A->C->D->E->B->A總距離為5+6+8+10+7=362神州大學和東方大學兩?；@球隊在東方大學進行一場競賽，結局的比分是85：89，用語義網(wǎng)絡表示。第3部分推理本章小結：自然演繹推理推理自然演繹推理推理經(jīng)典邏輯推理不確定與非單調(diào)推理歸結演繹推理與/或形演繹推理習題解答：1張某被盜，公安局派出五個偵察員去調(diào)查。研究案情時，偵察員A講“趙與鈔票中至少有一人作案”；偵察員B講“鈔票與孫中至少有一人作案”；偵察員C講“孫與李中至少有一人作案”；偵察員D講“趙與孫中至少有一人與此案無關”；偵察員E講“鈔票與李中至少有一人與此案無關”。假如這五個偵察員的話差不多上可信的，試用歸結演繹推理求出誰是盜竊犯。解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞。 設謂詞P(x)表示是作案者，因此依照題意：A:P(zhao)∨P(qian)B:P(qian)∨P(sun)C:P(sun)∨P(li)D:﹁P(zhao)∨﹁P(sun)E:﹁P(qian)∨﹁P(li)以上每個偵察員的話差不多上一個子句。第二步：將待求解的問題表示成謂詞。設y是盜竊犯，則問題的謂詞公式為P(y)，將其否定并與ANSWER(y)做析?。害鑀(y)∨ANSWER(y)第三步：求前提條件及﹁P(y)∨ANSWER(y)的子句集，并將各子句列表如下：P(zhao)∨P(qian)P(qian)∨P(sun)P(sun)∨P(li)﹁P(zhao)∨﹁P(sun)﹁P(qian)∨﹁P(li)﹁P(y)∨ANSWER(y)第四步：應用歸結原理進行推理。P(qian)∨﹁P(sun)(1)與(4)歸結P(zhao)∨﹁P(li)(1)與(5)歸結P(qian)∨﹁P(zhao)(2)與(4)歸結P(sun)∨﹁P(li)(2)與(5)歸結﹁P(zhao)∨P(li)(3)與(4)歸結P(sun)∨﹁P(qian)(3)與(5)歸結P(qian)(2)與(7)歸結P(sun)(2)與(12)歸結ANSWER(qian)(6)與(13)歸結，σ={qian/y}ANSWER(sun)(6)與(14)歸結,σ={sun/y}因此，本題的盜竊犯是兩個人：鈔票和孫。2任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？解：第一步：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。定義謂詞：設Father(x,y)表示x是y的父親。設Brother(x,y)表示x和y是兄弟。將已知事有用謂詞公式表示出來：F1:任何兄弟都有同一個父親。(x)(y)(z)(Brother(x,y)∧Father(z,x)→Father(z,y))F2:John和Peter是兄弟。Brother(John,Peter)F3:John的父親是David。Father(David,John)將它們化成子句集，得S1={﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y),Brother(John,Peter),Father(David,John)}第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER做析取。設Peter的父親是u，則有：Father(u,Peter)將其否定與ANSWER做析取，得 G:﹁Father(u,Peter)∨ANSWER(u)第三步：將上述公式G化為子句集S2，并將S1和S2合并到S。S2={﹁Father(u,Peter)∨ANSWER(u)}S=S1∪S2將S中各子句列出如下：（1）﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y)（2）Brother(John,Peter)（3）Father(David,John)（4）﹁Father(u,Peter)∨ANSWER(u)第四步：應用歸結原理進行歸結。（5）﹁Brother(John,y)∨Father(David,y)（1）與（3）歸結，σ={David/z,John/x}（6）﹁Brother(John,Peter)∨ANSWER(David) （4）與（5）歸結，σ={David/u,Peter/y}（7）ANSWER(David)（2）與（6）歸結第五步：得到了歸結式ANSWER(David)，答案即在其中，因此u=David,即Peter的父親是David。第4部分搜索策略本章小結：狀態(tài)空間搜索策略狀態(tài)空間搜索策略搜索策略盲目搜索啟發(fā)式搜索廣度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的深度優(yōu)先搜索局部擇優(yōu)搜索全局擇優(yōu)搜索A*算法與/或樹搜索策略盲目搜索廣度優(yōu)先搜索深度及有界深度優(yōu)先搜索有序搜索專門情況博弈問題提高搜索效率的方法α-β剪枝技術博弈問題：博弈問題：極大微小分析法：計算出端節(jié)點的估值，再推算出父節(jié)點的得分。推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父節(jié)點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點，選其子節(jié)點中一個最小的得分作為父節(jié)點的得分，這是為了立足于最壞的情況。如此計算出的父節(jié)點的得分稱為倒推值。α-β剪枝技術：關于一個“與”節(jié)點來講，它取當前子節(jié)點中的最小倒推值作為它倒推值的上界，稱此值為β值。關于一個“或”節(jié)點來講，它取當前子節(jié)點中的最大倒推值作為它倒推值的下界，稱此值為α值。其一般規(guī)律為:（1）任何“或”節(jié)點x的α值假如不能降低其父節(jié)點的β值，則對節(jié)點x以下的分枝可停止搜索，并使x的倒推值為α。這種剪枝成為β剪枝。（2）任何“與”節(jié)點x的β值假如不能升高其父節(jié)點的α值，則對節(jié)點x以下的分枝可停止搜索，并使x的倒推值為β。這種剪枝成為α剪枝。習題解答:1圖4-1是五都市間的交通路線圖，A都市是動身地，E都市是目的地，兩都市間的交通費用（代價）如圖中數(shù)字所示。求從A到E的最小費用交通路線。圖4-1圖4-1解：先將交通圖轉(zhuǎn)換為代價樹，如圖4-2所示。若用g(x)表示從初始節(jié)點s0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)AAC1B1D11D2E1E2B2E4C2E33423454523圖4-2方法一：代價樹的廣度優(yōu)先搜索（擴展節(jié)點ｎ，將其子節(jié)點放入open表中，計算各子節(jié)點的代價，并按各節(jié)點的代價對open表中全部節(jié)點按從小到大的順序進行排序（隊列））步驟如下：圖4-3-1圖4-3-1圖4-3-2圖4-3-2圖4-3-3圖4-3-3圖4-3-4圖4-3-4圖4-3-5圖4-3-5因此，最優(yōu)路徑為A->C->D->E方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）（擴展節(jié)點ｎ，將其子節(jié)點按代價從小到大的順序放到open表的首部（棧））步驟如下：AAC1B143圖4-4-1盡管D1的代價大于B1的代價，但按照代價樹的深度優(yōu)先搜索策略，要對D1進行擴展，放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴展B1）4盡管D1的代價大于B1的代價，但按照代價樹的深度優(yōu)先搜索策略，要對D1進行擴展，放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴展B1）435AC1B1D12圖4-4-24435AC1B1D18圖4-4-3934E2B2E為目標節(jié)點，E2->D1->C1->A因此路徑為A->Ｃ->Ｄ->Ｅ注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結果相同，但這只是巧合。一般情況下，這兩種方法得到的結果不一定相同。另外，由于代價樹的深度優(yōu)先搜索有可能進入無窮分支的路徑，因此它是不完備的。２如下圖４-5所示，分不用代價樹的廣度優(yōu)先搜索策略和代價樹的深度優(yōu)先搜索策略，求A到E的最短費用路徑。圖４－５圖４－５ＡＣＢＤＥ６５６７８７解：先將其化成代價樹,如圖4-6：D1D165ＡＢ1C1D2E1C2E2B2E3E466577788圖4-6(1)代價樹的廣度優(yōu)先搜索,步驟如下：AAB1C167圖4-7-1圖4-7-1B1B1C167D1A511圖4-7-2圖4-7-25B15B1C16D1A11D2E17781415圖4-7-3圖4-7-3E為目標節(jié)點，路徑為A->C->E，代價為15。（2）代價樹的深度優(yōu)先搜索,步驟如下：B1C1B1C167D1A511C2E2761817B1C167D1A511圖4-8-2圖4-8-1圖4-8-2圖4-8-1盡管C1代價低于D1，但按照代價樹的深度優(yōu)先搜索策略，對D1進行擴展，放入closed表中，因為B1擴展的節(jié)點為D1，而C1是A節(jié)點擴展得到的。E出棧，為目標節(jié)點，結束。故解路徑為A->B->D->E,代價為17，不是最優(yōu)解。注：深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解。得到的解也不一定是最優(yōu)解（因為是局部優(yōu)先搜索）。3下圖是五都市間的交通費用圖，若從西安動身，要求把每個都市都訪問一遍，最后到達廣州，請找一條最優(yōu)路線。邊上的數(shù)字是兩都市間的交通費用。北京B北京B上海DA西安S0昆明C廣州ESg7570809590120150170160130圖4-9解：先畫出代價樹：AAB1C1D1E1C2D2E2B2D3E3B3C3E4D4E5C4E6D5E7B4E8C5E9B5E10E11E12E13E14E15E16809512015017075160130709017013090751307013090751607570圖4-10按代價樹的廣度優(yōu)先搜索即可得出最優(yōu)路線，步驟如下：C1C1圖4-11-1AB1D11C1圖4-11-2AB1D12D2E2250155240C1C1圖4-11-3AB1D12D2E2250155240B2D3E3265225185C1圖4-11-4C1圖4-11-4AB1D12D2E2250155240B2D3E3265225185B3C3E4195250190B4B4E8B3C3E4195250190C1圖4-11-5AB1D12D2E2250155240B2D3E3265225185C4E6285225C5E9365355300295E10B5E5D4380340420340E7D5340425E12375故由此得出最優(yōu)路線為A->B1->D2->C4->E12即A->B->D->C->E，交通費用為375。4設有如圖所示的一棵與/或樹，請分不用與/或樹的廣度優(yōu)先搜索及與/或樹的深度優(yōu)先搜索求出解樹。BBCt1t2t3t4t5AD解：（1）與/或樹的廣度優(yōu)先搜索先擴展節(jié)點A,得到節(jié)點B和C，再擴展節(jié)點B,得節(jié)點t1、t2，因為t1、t2為可解節(jié)點，故節(jié)點B可解，從而可節(jié)點A可解。Bt1Bt1t2A（2）與/或樹的深度優(yōu)先搜索先擴展節(jié)點A,得到節(jié)點B和C,再擴展節(jié)點C,得節(jié)點D和t5,t5為可解節(jié)點，再擴展節(jié)D，得節(jié)點t3、t4，因為t3、t4為可解節(jié)點，故節(jié)點D可解，因為節(jié)點D和t5可解，故節(jié)點C可解，從而可節(jié)點A可解。因此求得解樹為：CCt3t4t5AD5設有如圖所示的與/或樹，請分不按和代價法及最大代價法求解樹代價。BBCDt2t1t4At357223621按和代價法：h(B)=7,h(C)=3,h(A)=7+3+5+6=21按最大代價法：h(B)=5,h(C)=2,h(A)=5+5=10談談你關于人工智能的認識。人工智能確實是人造智能，目前指用計算機模擬或?qū)崿F(xiàn)的智能，因此人工智能又稱機器智能。人工智能在我看來，應該是像人一樣考慮的系統(tǒng)、像人一樣行動的系統(tǒng)、理性地考慮的系統(tǒng)、理性地行動的系統(tǒng)，是像人一樣具有感知的系統(tǒng)，是能夠獨立考慮、獨立推斷的系統(tǒng)人工智能有哪些研究途徑和方法？它們的關系如何？心理模擬,符號推演;生理模擬,神經(jīng)計算;行為模擬,操縱進化;群體模擬,仿生計算;博采廣鑒,自然計算;原理分析,數(shù)學建模;它們各有所長,也都有一定的局限性，因此這些研究途徑和方法并不能互相取代,而是并存和互補的關系。人工智能有哪些研究內(nèi)容？搜索與求解、學習與發(fā)覺、知識與推理、發(fā)明與制造、感知與交流、經(jīng)歷與聯(lián)想、系統(tǒng)與建筑、應用與工程等八個方面。人工智能有哪些分支領域和研究方向？從模擬的智能層次和所用的方法看，可分為符號智能和計算智能兩大領域；從模擬的腦智能或腦功能看，可分為機器學習、機器感知、機器聯(lián)想、機器推理、機器行為等分支領域；從應用角度看，可分為難題求解、自動規(guī)劃、調(diào)度與配置、機器定理證明、自動程序設計、機器翻譯、智能操縱、智能治理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人機接口、模式識不、數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)覺、計算機輔助創(chuàng)新、計算機文藝創(chuàng)作、機器博弈、智能機器人；從系統(tǒng)角度看，可分為智能計算機系統(tǒng)和智能應用系統(tǒng)；從基礎理論看，可分為數(shù)理邏輯和多種非標準邏輯、圖論、人工神經(jīng)網(wǎng)絡、模糊集、粗糙集、概率統(tǒng)計和貝葉斯網(wǎng)絡、統(tǒng)計學習理論與支持向量機、形式語言與自動機等領域；人工智能有哪些應用領域或課題？試舉例講明難題求解、自動規(guī)劃、調(diào)度與配置、機器定理證明、自動程序設計、機器翻譯、智能操縱、智能治理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人機接口、模式識不、數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)覺、計算機輔助創(chuàng)新、計算機文藝創(chuàng)作、機器博弈、智能機器人。就機器博弈方面，在1997年IBM的“深藍”計算機以2勝3平1負的戰(zhàn)績擊敗了蟬聯(lián)12年之久的直接國際象棋冠軍加里卡斯帕羅夫，比如先現(xiàn)在中的五子棋對弈，能實現(xiàn)人與電腦之間的下棋，電腦自動搜索棋步，還可依照人們所選的電腦難度來決定電腦的難易程度。簡述人工智能的進展狀況人工智能的現(xiàn)狀和進展呈現(xiàn)如下特點：多種途徑齊頭并進，多種方法寫作互補；新思想、新技術不斷涌現(xiàn)，新領域、新方向不斷開括;理論研究更加深入，應用研究更加廣泛;研究隊伍日益壯大，社會阻礙越來越大;以上特點展現(xiàn)了人工智能學科的繁榮景象和光明前景。它表明，盡管在通向其最終目標的道路上，還有許多困難、問題和挑戰(zhàn)，但前進和進展怎么講是大勢所趨。7、試編寫一個描述親屬關系的PROLOG程序，然后再給出一些事實數(shù)據(jù)，建立一個小型演繹數(shù)據(jù)庫。domainsname=symbol.sex=symbol.age=integer.predicatesperson(name,sex,age)mother(name,name)father(name,name)brother(name,name)sister(name,name)grandfather(name,name)grandmother(name,name)goalbrother(Name1,Name2),write(Name1,"is",Name2,"'sbrother!\n"),sister(Name3,Name4),write(Name3,"is",Name4,"'ssister!\n"),grandfather(Name5,Name6),write(Name5,"is",Name6,"'sgrandfather!\n"),grandmother(Name7,Name8),write(Name7,"is",Name8,"'sgrandmother!\n").clausesperson(alan,m,21).person(john,m,22).person(marry,w,23).person(ann,w,24).mother(alice,alan).mother(alice,john).mother(alice,marry).mother(alice,ann).mother(marry,jane).father(alan,tom).father(tom,ben).brother(Name1,Name2):-person(Name1,m,Age1),person(Name2,m,Age2),mother(Z,Name1),mother(Z,Name2),Age1>Age2.sister(Name3,Name4):-person(Name3,w,Age3),person(Name4,w,Age4),mother(Z,Name3),mother(Z,Name4),Age3>Age4.grandfather(Name1,Name2):-father(Name1,Y),father(Y,Name2).grandmother(Name7,Name8):-mother(Name7,X),mother(X,Name8).8．何為狀態(tài)圖和與或圖？圖搜索與問題求解有什么關系？狀態(tài)圖是描述查找目標或路徑問題的有向圖，即描述一個實體基于事件反應的動態(tài)行為，顯示了該實體如何依照當前所處的狀態(tài)對不同的時刻做出反應的。與或圖是一種系統(tǒng)地將問題分解為互相獨立的小問題，然后分而解決的方法。與或圖中有兩種代表性的節(jié)點：“與節(jié)點”和“或節(jié)點”，“與節(jié)點”指所有的后續(xù)節(jié)點都有解時它才有解；“或節(jié)點”指各個后續(xù)節(jié)點均完全獨立，只要其中有一個有解它就有解。關系：問題求解確實是在一個圖中查找一個從初始節(jié)點到目標節(jié)點的路徑問題，圖搜索模擬的實際是人腦分析問題，解決問題的過程，它基于領域知識的問題求解過程。9.綜述圖搜索的方式和策略。答：圖搜索方式可分為樹式搜索和線式搜索。圖搜索策略可分為盲目搜索和啟發(fā)式搜索。10.什么是問題的解?什么是最優(yōu)解？答：能夠解決問題的方法或具體做法。其中最好的解決方法即代價最小的解稱為最優(yōu)解。11.什么是與或樹？什么是可解節(jié)點？什么是解樹？答：一棵樹中的弧線表示所連樹枝為“與”關系,不帶弧線的樹枝為或關系。這棵樹中既有與關系又有或關系，因此被稱為與或樹。滿足下列條件的節(jié)點為可解節(jié)點。①終止節(jié)點是可解節(jié)點；②一個與節(jié)點可解，當且僅當其子節(jié)點全都可解；③一個或節(jié)點可解，只要其子節(jié)點至少有一個可解。解樹實際上是由可解節(jié)點形成的一棵子樹,這棵子樹的根為初始節(jié)點，葉為終止節(jié)點，且這棵子樹一定是與樹。12.設有三只琴鍵開關一字排開,初始狀態(tài)為“關、開、關”,問連按三次后是否會出現(xiàn)“開、開、開”或“關、關、關”的狀態(tài)？要求每次必須按下一個開關,而且只能按一個開關。請畫出狀態(tài)空間圖。解：用（K1,K2,K3）表示三個開關的狀態(tài)，取值為0時表示閉合，為1時表示打開。則初始狀態(tài)為（0，1，0）。依照題設要求，一個狀態(tài)I的下一個狀態(tài)和I只能有一位取值不同（此即狀態(tài)轉(zhuǎn)換規(guī)則），據(jù)此能夠畫出狀態(tài)空間圖。（0，0，0）（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）（1，1，1） 從此狀態(tài)圖不難看出：通過連續(xù)三步有狀態(tài)（0，1，0）只能到達狀態(tài)（0，0，0）而不能到達狀態(tài)（1，1，1），即會出現(xiàn)狀態(tài)“關，關，關”，但可不能出現(xiàn)“開，開，開”。13.有一農(nóng)夫帶一只狼、一只羊和一筐菜欲從河的左岸乘船到右岸,但受下列條件限制：(1)船太小,農(nóng)夫每次只能帶一樣東西過河。(2)假如沒有農(nóng)夫看管,則狼要吃羊,羊要吃菜。請設計一個過河方案,使得農(nóng)夫、狼、羊、菜都能不受損失地過河。畫出相應的狀態(tài)空間圖。提示：(1)用四元組(農(nóng)夫、狼、羊、菜)表示狀態(tài),其中每個元素都可為0或1,用0表示在左岸,用1表示在右岸。(2)把每次過河的一種安排作為一個算符,每次過河都必須有農(nóng)夫,因為只有他能夠劃船。解：初始S=(0，0，0，0)，目標G=(1，1，1，1)定義操作符L(i)表示農(nóng)夫帶東西到右岸：定義操作符R(i)表示農(nóng)夫帶東西到左岸：

i=0農(nóng)夫自己到右岸；

i=0農(nóng)夫自己到左岸；i=1農(nóng)夫帶狼到右岸；i=1農(nóng)夫帶狼到左岸；i=2農(nóng)夫帶羊到右岸；i=2農(nóng)夫帶羊到左岸；i=3農(nóng)夫帶菜到右岸；i=3農(nóng)夫帶菜到左岸；約束狀態(tài)如下：(1，0，0，X)狼、羊在左岸；(1，X，0，0)羊、菜在左岸；(0，1，1，X)狼、羊在右岸；(0，X，1，1)羊、菜在右岸；

14.請闡述狀態(tài)空間的一般搜索過程。OPEN表與CLOSED表的作用是什么？答：先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進行“擴展”是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。OPEN表用于存放剛生成的節(jié)點，關于不同的搜索策略，節(jié)點在OPEN表中的排序是不同的。CLOSED表用于存放將要擴展或者已擴展的節(jié)點。15.廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點？答：廣度優(yōu)先搜索確實是始終先在同一級節(jié)點中考查,只有當同一級節(jié)點考查完之后,才考查下一級節(jié)點?；蛘咧v,是以初始節(jié)點為根節(jié)點，向下逐級擴展搜索樹。因此,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索確實是在搜索樹的每一層始終先只擴展一個子節(jié)點,不斷地向縱深前進,直到不能再前進（到達葉子節(jié)點或受到深度限制）時，才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又接著前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索假如誤入無窮分枝(即深度無限)，則不可能找到目標節(jié)點。因此，深度優(yōu)先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解(最短路徑)。廣度優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。16.是五大都市間的交通示意圖,邊上的數(shù)字是兩都市間的距離。用圖搜索技術編寫程序,求解以下問題：解：domainsp=string

d=integerpp=p*

predicatesroad(p,p,d)path(p,p,pp,d)member(p,pp)

clausespath(X,Y,L,D):-road(X,Y,D),L=[X|[Y]].path(X,Y,L,D):-road(X,Z,D1),%從當前點向前走到下一點Znot(member(Z,L)),

path(Z,Y,［Z|L］,D2),D=D1+D2.%再找Z到出口Y的路徑member(X,［X|_］).member(X,［_|T］)ifmember(X,T).road(A,B,D):-road(B,A,D).%因為沒向圖/*交通圖*/road(“西安”,”北京”,1165).road(“西安”,”上?！?1511).road(“西安”,“廣州”,2129).road(“西安”,”昆明”,1942).road(“昆明”,”北京”,3179).road(“昆明”,”上?！?2677).road(“昆明”,“廣州”,2216).road(“北京”,”廣州”,2510).road(“上?！?”北京”,1462).road(“廣州”,“上?！?1511).（1）path(“西安”,”北京”,L,D),write(L,D).（2）path(“西安”,”北京”,L,D),member(“上?！?L),write(L,D).

（3）path(“西安”,”北京”,L,D),member(“上?！?L),not(member(“昆明”,L)),write(L,D).17.何謂估價函數(shù)？在估價函數(shù)中,g(x)和h(x)各起什么作用？答：估價函數(shù)用來可能節(jié)點重要性的函數(shù)。估價函數(shù)f(x)被定義為從初始節(jié)點S0動身，約束通過節(jié)點x到達目標節(jié)點Sg的所有路徑中最小路徑代價的可能值。它的一般形式為：f(x)=g(x)+h(x)其中，g(x)是從初始節(jié)點S0到節(jié)點x的實際代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的可能代價。18.局部擇優(yōu)搜索與全局擇優(yōu)搜索的相同處與區(qū)不各是什么？答：局部擇優(yōu)搜索與全局擇優(yōu)搜索的區(qū)不是，擴展節(jié)點N后僅對N的子節(jié)點按啟發(fā)函數(shù)值大小以升序排序，再將它們依次放入OPEN表的首部。故算法從略。19.傳教士和野人問題。有三個傳教士和三個野人一起來到河邊預備渡河,河邊有一條空船,且傳教士和野人都會劃船,但每次最多可供兩人乘渡。河的任何一岸以及船上一旦出現(xiàn)野人人數(shù)超過傳教士人數(shù),野人就會把傳教士吃掉。為安全地渡河,傳教士應如何規(guī)劃渡河方案？試給出該問題的狀態(tài)圖表示,并用PROLOG語言編程求解之。若傳教士和野人的數(shù)目均為五人,渡船至多可乘三人,請定義一個啟發(fā)函數(shù),并給出相應的搜索樹。解：首先選取描述問題狀態(tài)的方法。在那個問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸依舊在右岸。從而可用一個三元組來表示狀態(tài)：S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。右岸的狀態(tài)可由下式確定：右岸修道士數(shù)：m'=3-m；右岸野人數(shù)：c'=3-c；右岸船數(shù)：b'=1-b在這種表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32種狀態(tài)。這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了這些狀態(tài)，還需要考慮可進行的操作。操作是指用船把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。每個操作都應當滿足如下條件：一是船至少有一個人（m或c）操作，離開岸邊的m和c的減少數(shù)目應該等于到達岸邊的m和c的增加數(shù)目；二是每次操作船上人數(shù)不得超過2個；三是操作應保證不產(chǎn)生非法狀態(tài)。因此，操作應由條件部分和動作部分：條件：只有當其條件具備時才能使用動作：刻劃了應用此操作所產(chǎn)生的結果。操作的表示：用符號Pij表示從左岸到右岸的運人操作用符號Qij表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的野人數(shù)操作集本問題有10種操作可供選擇：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01為例來講明這些操作的條件和動作。操作符號條件動作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=0,m=0或3，c≤2b=1,c=c+1

20.設（1）凡事清潔的東西就有人喜愛（2）人們都不喜愛蒼蠅用歸結原理證明蒼蠅是不清潔的21.八皇后問題：答案：用八元組(X0,X1,X2,X3,X4,X5,X6,X7)表示第1~8行的棋子，值(x0,x1,x2,x3,x4,x5,x6,x7)表示其在列上的位置。狀態(tài)可表示為八元組的一組值。專家系統(tǒng)：所謂專家系統(tǒng)，確實是基于人類專家知識的程序系統(tǒng)。專家系統(tǒng)的特點是擁有大量的專家知識（包括領域知識和經(jīng)驗知識），能模擬專家的思維方式，面對領域中復雜的實際問題，能作出專家水平級的決策，像專家一樣解決實際問題。

專家系統(tǒng)的特征：1)處理問題的性質(zhì)：善于解決不確定、非結構化、沒有算法解或雖有算法解但在現(xiàn)有機器上無法實施的困難問題。2)處理問題方法：靠知識和推理來解決問題3系統(tǒng)結構：強調(diào)知識與推理的分離，系統(tǒng)具有專門好的靈活性和可擴充性。4具有解釋功能：在運行中能回答用戶提出的問題，同時還能對輸出（結論）或處理問題的過程作出解釋。5具有“自學習”能力：即不斷對已有知識進行擴充、完善和提煉。6專家系統(tǒng)它始終如一地以專家級水平求解問題。

各部分功能：1知識庫：以某種表示形式存儲于計算機中的知識集合。知識庫中的知識一般包括專家知識、領域知識和元知識。2推理機：推理機確實是實現(xiàn)機器推理的程序，包括通常的邏輯推理和基于產(chǎn)生式的操作。3動態(tài)數(shù)據(jù)庫：是存放初始證據(jù)事實、推理結果和操縱信息的場所。4。人機界面：最終用戶與專家系統(tǒng)的交互界面5解釋模塊：

專門負責向用戶解釋專家系統(tǒng)的行為和結果。

6知識庫治理系統(tǒng)：是知識庫的支撐軟件。其功能包括知識庫的建立、刪除、重組；知識的獵取、知識的檢查等。

專家系統(tǒng)的應用和進展情況：醫(yī)學診斷/地質(zhì)勘探/物質(zhì)結構分析/生物遺傳研究/市場決策/生產(chǎn)治理。20世紀90年代模糊技術、神經(jīng)網(wǎng)絡和面向?qū)ο蟮刃录夹g迅速崛起，為專家系統(tǒng)注入了新的活力。

知識獵取：知識獵取是建筑專家系統(tǒng)的關鍵一步，也是較為困難的一步，被稱為建筑專家系統(tǒng)的“瓶頸”。知識獵取大體有三種途徑。1人工獵取：即計算機人員與領域?qū)＜液献?，對有關領域知識和專家知識，進行挖掘、搜集、分析、綜合、整理、歸納，然后以某種表示形式存入知識庫。2半自動獵取，即利用某種專門的知識獵取系統(tǒng)，采取提示、指導或問答的方式，關心專家提取、歸納有關知識，并自動記入知識庫。3

自動獵取又可分為兩種形式：一種是系統(tǒng)本身具有一種機制，使得系統(tǒng)在運行過程中能不斷地總結經(jīng)驗，并修改和擴充自己的知識庫；另一種是開發(fā)專門的機器學習系統(tǒng)，讓機器自動從實際問題中獵取知識，并填充知識庫。

22.有兩個最優(yōu)解樹左解樹：為最優(yōu)解右解樹按和代價法，代價為：g(S0)=12,g(A)=7,g(D)=4.按最大代價法，代價為：g(S0)=10,g(A)=5,g(D)=2.知識表示方法部分參考答案2.8設有如下語句，請用相應的謂詞公式分不把他們表示出來：s(1)有的人喜愛梅花，有的人喜愛菊花，有的人既喜愛梅花又喜愛菊花。解：定義謂詞dP(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是下午將知識用謂詞表示為：a(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個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如下圖所示。AABCCACABB圖機器人摞積木問題解：(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)，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(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)夫、狼、山羊、白菜問題。農(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)夫，船，狼，羊，白菜}。對應地，?AL(x)表示x在右岸。問題的初始狀態(tài)：AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(白菜)問題的目標狀態(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的個體域是{狼，羊，白菜}。對上述每個操作，都包括條件和動作兩部分。它們對應的條件和動作如下：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(農(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用謂詞表示法求解修道士和野人問題。在河的北岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但要受到以下條件限制：(1)修道士和野人都會劃船，但船一次只能裝運兩個人。(2)在任何岸邊，野人數(shù)不能超過修道士，否則修道士會被野人吃掉。假定野人情愿服從任何一種過河安排，請規(guī)劃出一種確保修道士安全的過河方案。要求寫出所用謂詞的定義、功能及變量的個體域。解：（1）定義謂詞先定義修道士和野人人數(shù)關系的謂詞：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岸，保證修道士安全，當且僅當修道士不在該岸上，或者修道士在該岸上，但人數(shù)超過野人數(shù)。該謂詞同時也描述了相應的狀態(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)絡：(1)每個學生都有一臺計算機。gGSgGSGS解：gGSgGSGS占有權計算機學生占有權計算機學生AKOISAISAFAKOISAISAFOwnsOwnerOwnsOwnercosgcosg(2)高老師從3月到7月給計算機系學生講《計算機網(wǎng)絡》課。解：7月8月7月8月StartEndStartEnd老師ISAObjectSubject高老師計算機系學生講課事件老師ISAObjectSubject高老師計算機系學生講課事件ActionCaurseActionCaurse計算機網(wǎng)絡講課計算機網(wǎng)絡講課(3)學習班的學員有男、有女、有研究生、有本科生。解：參例2.14(4)創(chuàng)新公司在科海大街56號，劉洋是該公司的經(jīng)理，他32歲、碩士學位。解：參例2.10(5)紅隊與藍隊進行足球競賽，最后以3：2的比分結束。解：競賽競賽AKOAKOParticipants1Outcome3:22Participants1Outcome3:22足球賽紅隊紅隊Participants2Participants2藍隊藍隊2.19請把下列命題用一個語義網(wǎng)絡表示出來：(1)樹和草差不多上植物；植物解：植物AKOAKOAKOAKO草樹草樹(2)樹和草都有葉和根；根葉解：根葉HaveHaveHaveHave植物植物是一種是一種是一種是一種草樹草樹(3)水草是草，且生長在水中；解：LiveAKOAKO水草LiveAKOAKO水草水中植物草水中植物草(4)果樹是樹，且會結果；解：CanAKOAKO果樹CanAKOAKO果樹結果植物樹結果植物樹(5)梨樹是果樹中的一種，它會結梨。解：CanAKOAKO梨樹CanAKOAKO梨樹樹果樹結梨樹果樹結梨2.25假設有以下一段天氣預報：“北京地區(qū)今天白天晴，偏北風3級，最高氣溫12o，最低氣溫-2o，降水概率15%?！闭堄每蚣鼙硎具@一知識。解：Frame<天氣預報>地域：北京時段：今天白天天氣：晴風向：偏北風力：3級氣溫：最高：12度最低：-2度降水概率：15%2.26按“師生框架”、“教師框架”、“學生框架”的形式寫出一個框架系統(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學生框架Frame<Students>AKO<Teachers-Students>Major：Unit（Major-Name）Classes：Unit（Classes-Name）Degree：Area（doctor，mastor,bachelor）Default：bachelor確定性推理部分參考答案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))差不多是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函數(shù)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函數(shù)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推斷下列子句集中哪些是不可滿足的：{?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)不可滿足，其歸結過程為：??P∨Q?Q?PPNIL(2)不可滿足，其歸結過程為：PP∨Q?P∨QQP∨?Q?P∨?Q?QNIL(3)不是不可滿足的，緣故是不能由它導出空子句。(4)不可滿足，其歸結過程略(5)不是不可滿足的，緣故是不能由它導出空子句。(6)不可滿足，其歸結過程略3.14對下列各題分不證明G是否為F1,F2,…,Fn的邏輯結論：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進行歸結：?P?P(x,b)P(a,b)NIL{a/x}NIL因此，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(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的邏輯結論同理可求得(3)、(4)和(5)，其求解過程略。3.15設已知：假如x是y的父親，y是z的父親，則x是z的祖父；每個人都有一個父親。使用歸結演繹推理證明：關于某人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，F(xiàn)2和?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個人去調(diào)查。案情分析時，貞察員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(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(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設有子句集：{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,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)用線性輸入策略（同時滿足祖先過濾策略）的歸結過程如下：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設已知：能閱讀的人是識字的；海豚不識字；有些海豚是專門聰慧的。請用歸結演繹推理證明：有些專門聰慧的人并不識字。解：第一步，先定義謂詞，設R(x)表示x是能閱讀的；K(y)表示y是識字的；W(z)表示z是專門聰慧的；第二步，將已知事實和目標用謂詞公式表示出來能閱讀的人是識字的：(x)(R(x))→K(x))海豚不識字：(y)(?K(y))有些海豚是專門聰慧的：(z)W(z)有些專門聰慧的人