（人工智能）人工智能經典習題集及各章總結(期末考試必備)

人工智能各章小結及習題解答第一部分緒論習題解答：1．什么是人工智能？發(fā)展過程中經歷了哪些階段？解：人工智能是計算機科學的一個重要分支，也是一門正在發(fā)展中的綜合性前沿學科，它是由計算機科學、控制論、信息論、神經生理學、哲學、語言學等多種學科相互滲透而發(fā)展起來的，目前正處于發(fā)展階段尚未形成完整體系。發(fā)展過程中經歷的階段有：第一階段（40年代中～50年代末）神經元網絡時代第二階段（50年代中～60年代中）通用方法時代第三階段（60年代中～80年代初）知識工程時代第四階段（80年代中～90年代初）新的神經元網絡時代第五階段（90年代初～現在）海量信息處理與網絡時代2．人工智能研究的基本內容是什么？解：基本內容是：搜索技術、知識表示、規(guī)劃方法、機器學習、認知科學、自然語言理解與機器翻譯、專家系統與知識工程、定理證明、博弈、機器人、數據挖掘與知識發(fā)現、多Agent系統、復雜系統、足球機器人、人機交互技術等。3．人工智能主要有哪幾大研究學派？解：（１）符號主義學派：由心理學途徑產生，符號主義認為人工智能起源于數理邏輯，人類認識（智能）的基本元素是符號，而智能行為則是符號運算的結果。（２）連接主義學派：由生理學途徑產生，連接主義又稱為仿生學派，認為人工智能的基本元素是神經元，智能產生于大量神經元的并行分布式聯結之中，而智能行為則是聯結計算的結果。（３）行為主義學派：由生物演化途徑產生，行為主義認為人工智能起源于控制論，提出智能取決于感知和行為，取決于對外界復雜環(huán)境的適應，而不是表示和推理。４．人工智能有哪些主要的研究領域？解：（１）問題求解（２）邏輯推理與定理證明（３）自然語言理解（４）自動程序設計（５）專家系統（６）機器學習（７）神經網絡（８）機器人學（９）模式識別（１０）機器視覺（１１）智能控制（１２）智能檢索（１３）智能調度與指揮（１４）分布式人工智能與Ａｇｅｎｔ（１５）計算智能與進化計算（１６）數據挖掘與知識發(fā)現（１７）人工生命（１８）系統與語言工具第2部分知識與知識表示本章小結：知識表示謂詞表示法知識表示謂詞表示法產生式表示法框架表示法語義網絡表示法框架通常由指定事物各個方面的槽組成，每個槽擁有若干個側面，而每個側面又可擁有若干個值。語義網絡由節(jié)點和弧線或鏈線組成，節(jié)點用于表示物體、概念和狀態(tài)，弧線用于表示節(jié)點間的關系。產生式系統由3個基本部分組成：規(guī)則庫、綜合數據庫、控制系統。首先定義謂詞，指出每個謂詞的確切含義，然后再用連接詞把有關的謂詞連接起來，形成一個謂詞公式表達一個完整的意義。習題解答：1設有如下問題：（1）有五個相互可直達且距離已知的城市A、B、C、D、E，如圖所示；（2）某人從A地出發(fā)，去其它四個城市各參觀一次后回到A;（3）找一條最短的旅行路線請用產生式規(guī)則表示旅行過程。解：=1\*GB3①綜合數據庫（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)為走過的城市數，GOTO(x)為走向城市x=5\*GB3⑤路線如下圖所示:最短旅行路線為：A->C->D->E->B->A總距離為5+6+8+10+7=362神州大學和東方大學兩?；@球隊在東方大學進行一場比賽，結局的比分是85：89，用語義網絡表示。第3部分推理本章小結：習題解答：1張某被盜，公安局派出五個偵察員去調查。研究案情時，偵察員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城市是出發(fā)地，E城市是目的地，兩城市間的交通費用（代價）如圖中數字所示。求從A到E的最小費用交通路線。解：先將交通圖轉換為代價樹，如圖4-2所示。若用g(x)表示從初始節(jié)點s0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)方法一：代價樹的廣度優(yōu)先搜索（擴展節(jié)點ｎ，將其子節(jié)點放入open表中，計算各子節(jié)點的代價，并按各節(jié)點的代價對open表中全部節(jié)點按從小到大的順序進行排序（隊列））步驟如下：圖4-3-4圖4-3-4所以，最優(yōu)路徑為A->C->D->E方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）（擴展節(jié)點ｎ，將其子節(jié)點按代價從小到大的順序放到open表的首部（棧））步驟如下：4435AC1B1D18圖4-4-3934E2B2E為目標節(jié)點，E2->D1->C1->A所以路徑為A->Ｃ->Ｄ->Ｅ注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結果相同，但這只是巧合。一般情況下，這兩種方法得到的結果不一定相同。另外，由于代價樹的深度優(yōu)先搜索有可能進入無窮分支的路徑，因此它是不完備的。２如下圖４-5所示，分別用代價樹的廣度優(yōu)先搜索策略和代價樹的深度優(yōu)先搜索策略，求A到E的最短費用路徑。圖４－５圖４－５ＡＣＢＤＥ６５６７８７解：先將其化成代價樹,如圖4-6：(1)代價樹的廣度優(yōu)先搜索,步驟如下：AAB1C167圖4-7-2圖4-7-2B1B1C16D1A11D2E17781415E為目標節(jié)點，路徑為A->C->E，代價為15。（2）代價樹的深度優(yōu)先搜索,步驟如下：B1B1C167D1A511圖4-8-2圖4-8-2雖然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下圖是五城市間的交通費用圖，若從西安出發(fā)，要求把每個城市都訪問一遍，最后到達廣州，請找一條最優(yōu)路線。邊上的數字是兩城市間的交通費用。解：先畫出代價樹：AAB1C1D1E1C2D2E2B2D3E3B3C3E4D4E5C4E6D5E7B4E8C5E9B5E10E11E12E13E14E15E16809512015017075160130709017013090751307013090751607570圖4-10按代價樹的廣度優(yōu)先搜索即可得出最優(yōu)路線，步驟如下：C1C1圖4-11-2AB1D12D2E2250155240C1C1圖4-11-4AB1D12D2E2250155240B2D3E3265225185故由此得出最優(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可解。所以求得解樹為：（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談談你對于人工智能的認識。人工智能就是人造智能，目前指用計算機模擬或實現的智能，因此人工智能又稱機器智能。人工智能在我看來，應該是像人一樣思考的系統、像人一樣行動的系統、理性地思考的系統、理性地行動的系統，是像人一樣具有感知的系統，是可以獨立思考、獨立判斷的系統人工智能有哪些研究途徑和方法？它們的關系如何？心理模擬,符號推演;生理模擬,神經計算;行為模擬,控制進化;群體模擬,仿生計算;博采廣鑒,自然計算;原理分析,數學建模;它們各有所長,也都有一定的局限性，因此這些研究途徑和方法并不能互相取代,而是并存和互補的關系。人工智能有哪些研究內容？搜索與求解、學習與發(fā)現、知識與推理、發(fā)明與創(chuàng)造、感知與交流、記憶與聯想、系統與建造、應用與工程等八個方面。人工智能有哪些分支領域和研究方向？從模擬的智能層次和所用的方法看，可分為符號智能和計算智能兩大領域；從模擬的腦智能或腦功能看，可分為機器學習、機器感知、機器聯想、機器推理、機器行為等分支領域；從應用角度看，可分為難題求解、自動規(guī)劃、調度與配置、機器定理證明、自動程序設計、機器翻譯、智能控制、智能管理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人機接口、模式識別、數據挖掘與數據庫中的知識發(fā)現、計算機輔助創(chuàng)新、計算機文藝創(chuàng)作、機器博弈、智能機器人；從系統角度看，可分為智能計算機系統和智能應用系統；從基礎理論看，可分為數理邏輯和多種非標準邏輯、圖論、人工神經網絡、模糊集、粗糙集、概率統計和貝葉斯網絡、統計學習理論與支持向量機、形式語言與自動機等領域；人工智能有哪些應用領域或課題？試舉例說明難題求解、自動規(guī)劃、調度與配置、機器定理證明、自動程序設計、機器翻譯、智能控制、智能管理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人機接口、模式識別、數據挖掘與數據庫中的知識發(fā)現、計算機輔助創(chuàng)新、計算機文藝創(chuàng)作、機器博弈、智能機器人。就機器博弈方面，在1997年IBM的“深藍”計算機以2勝3平1負的戰(zhàn)績擊敗了蟬聯12年之久的直接國際象棋冠軍加里卡斯帕羅夫，比如先如今中的五子棋對弈，能實現人與電腦之間的下棋，電腦自動搜索棋步，還可根據人們所選的電腦難度來決定電腦的難易程度。簡述人工智能的發(fā)展狀況人工智能的現狀和發(fā)展呈現如下特點：多種途徑齊頭并進，多種方法寫作互補；新思想、新技術不斷涌現，新領域、新方向不斷開括;理論研究更加深入，應用研究更加廣泛;研究隊伍日益壯大，社會影響越來越大;以上特點展現了人工智能學科的繁榮景象和光明前景。它表明，雖然在通向其最終目標的道路上，還有不少困難、問題和挑戰(zhàn)，但前進和發(fā)展畢竟是大勢所趨。7、試編寫一個描述親屬關系的PROLOG程序，然后再給出一些事實數據，建立一個小型演繹數據庫。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)對不同的時間做出反應的。與或圖是一種系統地將問題分解為互相獨立的小問題，然后分而解決的方法。與或圖中有兩種代表性的節(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)為“關、開、關”,問連按三次后是否會出現“開、開、開”或“關、關、關”的狀態(tài)？要求每次必須按下一個開關,而且只能按一個開關。請畫出狀態(tài)空間圖。解：用（K1,K2,K3）表示三個開關的狀態(tài)，取值為0時表示閉合，為1時表示打開。則初始狀態(tài)為（0，1，0）。根據題設要求，一個狀態(tài)I的下一個狀態(tài)和I只能有一位取值不同（此即狀態(tài)轉換規(guī)則），據此可以畫出狀態(tài)空間圖。（0，0，0）（0，0，0）（1，1，0）（1，1，0） 從此狀態(tài)圖不難看出：經過連續(xù)三步有狀態(tài)（0，1，0）只能到達狀態(tài)（0，0，0）而不能到達狀態(tài)（1，1，1），即會出現狀態(tài)“關，關，關”，但不會出現“開，開，開”。13.有一農夫帶一只狼、一只羊和一筐菜欲從河的左岸乘船到右岸,但受下列條件限制：(1)船太小,農夫每次只能帶一樣東西過河。(2)如果沒有農夫看管,則狼要吃羊,羊要吃菜。請設計一個過河方案,使得農夫、狼、羊、菜都能不受損失地過河。畫出相應的狀態(tài)空間圖。提示：(1)用四元組(農夫、狼、羊、菜)表示狀態(tài),其中每個元素都可為0或1,用0表示在左岸,用1表示在右岸。(2)把每次過河的一種安排作為一個算符,每次過河都必須有農夫,因為只有他可以劃船。解：初始S=(0，0，0，0)，目標G=(1，1，1，1)定義操作符L(i)表示農夫帶東西到右岸：定義操作符R(i)表示農夫帶東西到左岸：

i=0農夫自己到右岸；

i=0農夫自己到左岸；i=1農夫帶狼到右岸；i=1農夫帶狼到左岸；i=2農夫帶羊到右岸；i=2農夫帶羊到左岸；i=3農夫帶菜到右岸；i=3農夫帶菜到左岸；約束狀態(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)是否出現在這些子節(jié)點中。若出現，則搜索成功，找到了問題的解；若沒出現，則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現在子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進行“擴展”是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。OPEN表用于存放剛生成的節(jié)點，對于不同的搜索策略，節(jié)點在OPEN表中的排序是不同的。CLOSED表用于存放將要擴展或者已擴展的節(jié)點。15.廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點？答：廣度優(yōu)先搜索就是始終先在同一級節(jié)點中考查,只有當同一級節(jié)點考查完之后,才考查下一級節(jié)點?；蛘哒f,是以初始節(jié)點為根節(jié)點，向下逐級擴展搜索樹。所以,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴展一個子節(jié)點,不斷地向縱深前進,直到不能再前進（到達葉子節(jié)點或受到深度限制）時，才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝(即深度無限)，則不可能找到目標節(jié)點。所以，深度優(yōu)先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解(最短路徑)。廣度優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。16.是五大城市間的交通示意圖,邊上的數字是兩城市間的距離。用圖搜索技術編寫程序,求解以下問題：解：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.何謂估價函數？在估價函數中,g(x)和h(x)各起什么作用？答：估價函數用來估計節(jié)點重要性的函數。估價函數f(x)被定義為從初始節(jié)點S0出發(fā)，約束經過節(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ā)函數值大小以升序排序，再將它們依次放入OPEN表的首部。故算法從略。19.傳教士和野人問題。有三個傳教士和三個野人一起來到河邊準備渡河,河邊有一條空船,且傳教士和野人都會劃船,但每次最多可供兩人乘渡。河的任何一岸以及船上一旦出現野人人數超過傳教士人數,野人就會把傳教士吃掉。為安全地渡河,傳教士應如何規(guī)劃渡河方案？試給出該問題的狀態(tài)圖表示,并用PROLOG語言編程求解之。若傳教士和野人的數目均為五人,渡船至多可乘三人,請定義一個啟發(fā)函數,并給出相應的搜索樹。解：首先選取描述問題狀態(tài)的方法。在這個問題中，需要考慮兩岸的修道士人數和野人數，還需要考慮船在左岸還是在右岸。從而可用一個三元組來表示狀態(tài)：S=(m,c,b)其中，m表示左岸的修道士人數，c表示左岸的野人數，b表示左岸的船數。右岸的狀態(tài)可由下式確定：右岸修道士數：m'=3-m；右岸野人數：c'=3-c；右岸船數：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的減少數目應該等于到達岸邊的m和c的增加數目；二是每次操作船上人數不得超過2個；三是操作應保證不產生非法狀態(tài)。因此，操作應由條件部分和動作部分：條件：只有當其條件具備時才能使用動作：刻劃了應用此操作所產生的結果。操作的表示：用符號Pij表示從左岸到右岸的運人操作用符號Qij表示從右岸到左岸的操作其中：i表示船上的修道士人數j表示船上的野人數操作集本問題有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)可表示為八元組的一組值。專家系統：所謂專家系統，就是基于人類專家知識的程序系統。專家系統的特點是擁有大量的專家知識（包括領域知識和經驗知識），能模擬專家的思維方式，面對領域中復雜的實際問題，能作出專家水平級的決策，像專家一樣解決實際問題。

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

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

專門負責向用戶解釋專家系統的行為和結果。

6知識庫管理系統：是知識庫的支撐軟件。其功能包括知識庫的建立、刪除、重組；知識的獲取、知識的檢查等。

專家系統的應用和發(fā)展情況：醫(yī)學診斷/地質勘探/物質結構分析/生物遺傳研究/市場決策/生產管理。20世紀90年代模糊技術、神經網絡和面向對象等新技術迅速崛起，為專家系統注入了新的活力。

知識獲?。褐R獲取是建造專家系統的關鍵一步，也是較為困難的一步，被稱為建造專家系統的“瓶頸”。知識獲取大體有三種途徑。1人工獲?。杭从嬎銠C人員與領域專家合作，對有關領域知識和專家知識，進行挖掘、搜集、分析、綜合、整理、歸納，然后以某種表示形式存入知識庫。2半自動獲取，即利用某種專門的知識獲取系統，采取提示、指導或問答的方式，幫助專家提取、歸納有關知識，并自動記入知識庫。3

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

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,puter)：x使用計算機將知識用謂詞表示為：?(x)(S(x)→L(x,pragramming)∧U(x,puter))(5)凡是喜歡編程序的人都喜歡計算機。解：定義謂詞P(x)：x是人L(x,y)：x喜歡y將知識用謂詞表示為：(x)(P(x)∧L(x,pragramming)→L(x,puter))2.9用謂詞表示法求解機器人摞積木問題。設機器人有一只機械手，要處理的世界有一張桌子，桌上可堆放若干相同的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如下圖所示。BB圖機器人摞積木問題解：(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(A)ONTABLE(B)ONTABLE(C)CLEAR(A)CLEAR(B)CLEAR(C)HANDEMPTYONTABLE(A)ONTABLE(B)HOLDING(C)CLEAR(A)CLEAR(B)CLEAR(C)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)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(白菜)2.11用謂詞表示法求解修道士和野人問題。在河的北岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但要受到以下條件限制：(1)修道士和野人都會劃船，但船一次只能裝運兩個人。(2)在任何岸邊，野人數不能超過修道士，否則修道士會被野人吃掉。假定野人愿意服從任何一種過河安排，請規(guī)劃出一種確保修道士安全的過河方案。要求寫出所用謂詞的定義、功能及變量的個體域。解：（1）定義謂詞先定義修道士和野人人數關系的謂詞：G(x,y,S)：在狀態(tài)S下x大于yGE(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)每個學生都有一臺計算機。gGS解：gGS計算機計算機AKOAKOOwnsOwnsoo(2)高老師從3月到7月給計算機系學生講《計算機網絡》課。解：8月8月EndEnd老師老師(3)學習班的學員有男、有女、有研究生、有本科生。解：參例2.14(4)創(chuàng)新公司在科海大街56號，劉洋是該公司的經理，他32歲、碩士學位。解：參例2.10(5)紅隊與藍隊進行足球比賽，最后以3：2的比分結束。解：比賽比賽紅隊紅隊2.19請把下列命題用一個語義網絡表示出來：(1)樹和草都是植物；解：樹樹(2)樹和草都有葉和根；葉解：葉樹樹(3)水草是草，且生長在水中；解：水草水草(4)果樹是樹，且會結果；解：結果結果(5)梨樹是果樹中的一種，它會結梨。解：結梨結梨2.25假設有以下一段天氣預報：“北京地區(qū)今天白天晴，偏北風3級，最高氣溫12o，最低氣溫-2o，降水概率15%?！闭堄每蚣鼙硎具@一知識。解：Frame<天氣預報>地域：北京時段：今天白天天氣：晴風向：偏北風力：3級氣溫：最高：12度最低：-2度降水概率：15%2.26按“師生框架”、“教師框架”、“學生框架”的形式寫出一個框架系統的描述。解：師生框架Frame<Teachers-Students>Name：Unit（Last-name，First-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函數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判斷下列子句集中哪些是不可滿足的：{?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)不可滿足，其歸結過程為：(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(x,b){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(a)∨Q(b)Q(a)?P(x)∨?Q(x)?P(a)P(x)NIL{a/b}{a/x}{a/x}所以，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，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)對上述擴充的子句集，按歸結原理進行歸結，其修改的證明樹如下：{Q/u}因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據歸結原理還可以得出：??C(Q)∨?C(L)??C(u)∨C(u){S/u}因此，孫也是盜竊犯。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))Q(a,f(a)){b/f(a)}{a/x}{b/f(a)}用線性輸入策略（同時滿足祖先過濾策略）的歸結過程如下：{a/x}{a/x}QQ(a,b){b/f(a)}3.19設已知：能閱讀的人是識字的；海豚不識字；有些海豚是很聰明的。請用歸結演繹推理證明：有些很聰明的人并不識字。解：第一步，先定義謂詞，設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)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ī)則演繹系統如下圖所示。由該圖可以直接寫出所有可能的目標子句如下：P∨Q∨Ｔ∨ＵP∨Q∨Ｘ∨ＺP∨Q∨Y∨ＺR∨T∨UR∨X∨ZR∨Y∨ZUXZQZTUXUXZQZTUXXYXYF規(guī)則F規(guī)則XX∧YUQUQ已知事實已知事實(P∨Q)(P∨Q)T∨U3.24設有如下一段知識：“張、王和李都屬于高山協會。該協會的每個成員不是滑雪運動員，就是登山運動員，其中不喜歡雨的運動員是登山運動員，不喜歡雪的運動員不是滑雪運動員。王不喜歡張所喜歡的一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪?！痹囉弥^詞公式集合表示這段知識，這些謂詞公式要適合一個逆向的基于規(guī)則的演繹系統。試說明這樣一個系統怎樣才能回答問題：“高山俱樂部中有沒有一個成員，他是一個登山運動員，但不是一個滑雪運動員？”解：(1)先定義謂詞A(x)表示x是高山協會會員S(x)表示x是滑雪運動員C(x)表示x是登山運動員L(x,y)表示x喜歡y(2)將問題用謂詞表示出來“張、王和李都屬于高山協會A(Zhang)∧A(Wang)∧A(Li)高山協會的每個成員不是滑雪運動員，就是登山運動員(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))張喜歡雨和雪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)，其逆向演繹過程如下圖所示。C(x)C(x)∧?S(x)??S(x)rr34{Rain/y}{Snow/y}{Rain/y}{Snow/y}搜索策略部分參考答案4.5有一農夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：(1)船太小，農夫每次只能帶一樣東西過河；如果沒有農夫看管，則狼要吃羊，羊要吃菜。請設計一個過河方案，使得農夫、浪、羊都能不受損失的過河，畫出相應的狀態(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種可能的