人工智能課后題答案

1、精品資料推薦第一章課后習(xí)題答案第1題答：1,綜合數(shù)據(jù)庫定義三元組：(m,c,b)其中：。乜舊名5,表示傳教士在河左岸的人數(shù)。表示野人在河左岸的認輸。啟專b=1,表示船在左岸，b=0,表示船在右岸。2,規(guī)則集規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法：按每次渡河的人數(shù)分別寫出每一個規(guī)則，共(30)、(03)、(21)、(11)、(10)、(01)、(20)、(02)八種渡河的可能(其中(xy)表示x個傳教士和y個野人上船渡河)，因此共有16個規(guī)則(從左岸到右岸、右岸到左岸各八個)。注意：這里沒有(12),因為該組合在船上的傳教士人數(shù)少于野人人數(shù)。規(guī)則集如下：r1：IF(m,c,1)THE

2、N(m-3,c,0)r2：IF(m,c,1)THEN(m,c-3,0)r3：IF(m,c,1)THEN(m-2,c-1,0)r4：IF(m,c,1)THEN(m-1,c-1,0) TOC o 1-5 h z r5：IF(m,c,1)THEN(m-1,c,0)r6：IF(m,c,1)THEN(m,c-1,0)r7:IF(m,c,1)THEN(m-2,c,0)r8：IF(m,c,1)THEN(m,c-2,0)r9:IF(m,c,0)THEN(m+3,c,1)r10:IF(m,c,0)THEN(m,c+3,1)r11:IF(m,c,0)THEN(m+2,c+1,1)r12：IF(m,c,0)THEN

3、(m+1,c+1,1)r13：IF(m,c,0)THEN(m+1,c,1)r14：IF(m,c,0)THEN(m,c+1,1)r15：IF(m,c,0)THEN(m+2,c,1)r16：IF(m,c,0)THEN(m,c+2,1)第二種方法：將規(guī)則集綜合在一起，簡化表示。規(guī)則集如下：r1：IF(m,c,1)and0i+j=jori=0)THEN(m-i,c-j,0)r2：IF(m,c,0)and0i+j=jori=0)THEN(m+i,c+j,1)3,初始狀態(tài)：(5,5,1)4,結(jié)束狀態(tài)：(0,0,0)第2題答：1,綜合數(shù)據(jù)庫定義兩元組：(L5,L2)其中：0=L5=5,表示容量為5升的壺的當(dāng)

4、前水量。0=L2=2,表示容量為2升的壺的當(dāng)前水量。將L5灌滿水*/將L2灌滿水*/將L5水到光*/將L2水到光*/2,規(guī)則集ri:IF(L5,L2)THEN(5,L2)/*r2:IF(L5,L2)THEN(L5,2)/*r3:IF(L5,L2)THEN(0,L2)/*r4:IF(L5,L2)THEN(L5,0)/* TOC o 1-5 h z r5:IF(L5,L2)andL5+L25THEN(5,L5+L2-5)/*L2至U入L5中*/r7:IF(L5,L2)andL5+L25THEN(L5+L2-2,2)/*L5至U入L2中*/3,初始狀態(tài)：(5,0)4,結(jié)束條件：(x,1),其中x表示

5、不定。當(dāng)然結(jié)束條件也可以寫成：(0,1)第3題答：1,綜合數(shù)據(jù)庫定義三元組：(A,B,C)其中A,B,C分別表示三根立柱，均為表，表的元素為1N之間的整數(shù)，表示N個不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個元素表示立柱最上面的柱子，其余類推。2,規(guī)則集為了方便表示規(guī)則集，引入以下幾個函數(shù)：first(L)：取表的第一個元素，對于空表，first得到一個很大的大于N的數(shù)值。tail(L):取表除了第一個元素以外，其余元素組成的表。cons(x,L)：將x加入到表L的最前面。規(guī)則集：r1:IF(A,B,C)and(first(A)first(B)THEN(tail(A)

6、,cons(first(A),B),C)r2:IF(A,B,C)and(first(A)first(C)THEN(tail(A),B,cons(first(A),C)r3:IF(A,B,C)and(first(B)first(C)THEN(A,tail(B),cons(first(B),C)r4:IF(A,B,C)and(first(B)first(A)THEN(cons(first(B),A),tail(B),C)r5:IF(A,B,C)and(first(C)first(A)THEN(cons(first(C),A),B,tail(C)r6:IF(A,B,C)and(first(C)fir

7、st(B)THEN(A,cons(first(C),B),tail(C)3,初始狀態(tài)：(1,2,.,N),(),()4,結(jié)束狀態(tài)：()，()，(1,2,，N)問題的狀態(tài)規(guī)模：每一個盤子都有三中選擇：在A上、或者在B上、或者在C上，共N個盤子，所以共有3*種可能。即問題的狀態(tài)規(guī)模為3”。第4題答：1,綜合數(shù)據(jù)庫定義5元組：(M,B,Box,On,H)其中：M:猴子的位置B:香蕉的位置Box:箱子的位置On=0:猴子在地板上On=1:猴子在箱子上H=0:猴子沒有抓到香蕉H=1:猴子抓到了香蕉2,規(guī)則集猴子從x處走到w處如果猴子和箱子在一起，猴子將箱子推到z處如果猴子和箱子在一起，猴子爬到箱子上如果

8、猴子在箱子上，猴子從箱子上下來如果箱子在香蕉處，猴子在箱子上，猴子摘到香蕉 TOC o 1-5 h z 1IF(x,y,z,0,0)THEN(w,y,z,0,0)r2:IF(x,y,x,0,0)THEN(z,y,z,0,0)r3:IF(x,y,x,0,0)THEN(x,y,x,1,0)r4:IF(x,y,x,1,0)THEN(x,y,x,0,0)r5:IF(x,x,x,1,0)THEN(x,x,x,1,1)其中x,y,z,w為變量3,初始狀態(tài)(c,a,b,0,0)4,結(jié)束狀態(tài)(x1,x2,x3,x4,1)其中x1x4為變量。第5題答：1,綜合數(shù)據(jù)庫定義四元組：(x,y,z,n)其中x,y,xG

9、0,1,1表示錢幣為正面，0表示錢幣為方面。n=0,1,2,3,表示當(dāng)前狀態(tài)是經(jīng)過n次翻錢幣得到的2,規(guī)則庫r1:IF(x,y,z,n)THEN(x,y,z,n+1)r2:IF(x,y,z,n)THEN(x,y,z,n+1)r3:IF(x,y,z,n)THEN(x,y,z,n+1)其中x表示對x取反。3,初始狀態(tài)(1,1,0,0)4,結(jié)束狀態(tài)(1,1,1,3)或者(0,0,0,3)第6題提示：將十進制數(shù)分為整數(shù)部分和小數(shù)部分兩部分。用四元組(a,b,c,d)表示綜合數(shù)據(jù)庫，其中a,b表示到目前為止還沒有轉(zhuǎn)換的十進制數(shù)的整數(shù)部分和小數(shù)部分，c,d表示已經(jīng)轉(zhuǎn)換得到的二進制數(shù)的整數(shù)部分和小數(shù)部分。然

10、后根據(jù)十進制數(shù)轉(zhuǎn)換二進制數(shù)的原理，分別定義整數(shù)的轉(zhuǎn)換規(guī)則和小數(shù)的轉(zhuǎn)換規(guī)則，一次規(guī)則的執(zhí)行，轉(zhuǎn)換得到二進制數(shù)的一位。第7題答：設(shè)規(guī)則R的逆用R表示。由題意有R應(yīng)用于D后，得到數(shù)據(jù)庫D,由可交換系統(tǒng)的性質(zhì)，有：rule(D)二rule(D)其中rule(D)表示可應(yīng)用于D的規(guī)則集合。由于R是R的逆，所以R應(yīng)用于D后，得到數(shù)據(jù)庫Do同樣由可交換系統(tǒng)的性質(zhì)，有:rule(D)=rule(D)綜合上述兩個式子，有rule(D)=rule(D)。第8題答：說明一個產(chǎn)生式系統(tǒng)是可交換的，就是要證明該產(chǎn)生式系統(tǒng)滿足可交換產(chǎn)生式系統(tǒng)的三條性質(zhì)。(1)該產(chǎn)生式系統(tǒng)以整數(shù)的集合為綜合數(shù)據(jù)庫，其規(guī)則是將集合中的兩個整

11、數(shù)相乘后加入到數(shù)據(jù)庫中。由于原來數(shù)據(jù)庫是新數(shù)據(jù)庫的子集，所以原來的規(guī)則在新數(shù)據(jù)庫中均可以使用。所以滿足可交換產(chǎn)生式系統(tǒng)的第一條性質(zhì)。(2)該產(chǎn)生式系統(tǒng)以某個整數(shù)的子集的出現(xiàn)為目標條件，由于規(guī)則執(zhí)行的結(jié)果只是向數(shù)據(jù)庫中添加數(shù)據(jù)，如果原數(shù)據(jù)庫中已經(jīng)滿足目標了，即出現(xiàn)了所需要的整數(shù)子集，規(guī)則的執(zhí)行結(jié)果不會破壞該整數(shù)子集的出現(xiàn)，因此新的數(shù)據(jù)庫仍然會滿足目標條件。滿足可交換產(chǎn)生式系統(tǒng)的第二個性質(zhì)。(3)設(shè)D是該產(chǎn)生式系統(tǒng)的一個綜合數(shù)據(jù)庫。對D施以一個規(guī)則序列后，得到一個新的數(shù)據(jù)庫D。該規(guī)則序列中的有些規(guī)則有些是可以應(yīng)用于D的，這些規(guī)則用R1表示。有些規(guī)則是不能應(yīng)用于D的，這些規(guī)則用R2表示。由于R1中的

12、規(guī)則可以直接應(yīng)用與D,所以R1中規(guī)則的應(yīng)用與R2中規(guī)則的執(zhí)行結(jié)果無關(guān)，也與R1中其他的規(guī)則的執(zhí)行無關(guān)。所以可以認為，先將R1中所有的規(guī)則對D應(yīng)用，然后再按照原來的次序應(yīng)用R2中的規(guī)則。因此對于本題的情況，這樣得到的綜合數(shù)據(jù)庫與D是相同的。而由于R1中一條規(guī)則的執(zhí)行與其他的規(guī)則無關(guān)，所以R1中規(guī)則的執(zhí)行順序不會影響到最終的結(jié)果。因此滿足可交換產(chǎn)生式系統(tǒng)的第三個條件。因此這樣一個產(chǎn)生式系統(tǒng)是一個可交換的產(chǎn)生式系統(tǒng)。第二章課后習(xí)題答：為了方便起見，我們用(AB)()()這樣的表表示一個狀態(tài)。這樣得到搜索圖如下:第2題提示：可定義h為：h=B右邊的W的數(shù)目設(shè)j節(jié)點是i節(jié)點的子節(jié)點，則根據(jù)走法不同，h(

13、i)-h(j)的值和C(i,j)分為如下幾種情況：B或W走到了相鄰的一個空格位置，此時：h(i)-h(j)=0,C(i,j)=1;W跳過了1或2個W,此時h(i)-h(j)=0,C(i,j)=1或2;W向右跳過了一個B(可能同時包含一個W),此時：h(i)-h(j)=-1,C(i,j)=1或2;W向右跳過了兩個B,此時:h(i)-h(j)=-2,C(i,j)=2;W向左跳過了一個B(可能同時包含一個W),此時：h(i)-h(j)=1,C(i,j)=1或2;W向左跳過了兩個B,此時：h(i)-h(j)=2,C(i,j)=2;精品資料推薦B跳過了1或2個B,止匕時h(i)-h(j)=0,C(i,j

14、)=1或2;B向右跳過了一個W(可能同時包含一個B),此時：h(i)-h(j)=1,C(i,j)=1或2;B向右跳過了兩個W,此時:h(i)-h(j)=2,C(i,j)=2;B向左跳過了一個W(可能同時包含一個B),此時：h(i)-h(j)=-1,C(i,j)=1或2;B向左跳過了兩個W,此時:h(i)-h(j)=-2,C(i,j)=2;縱上所述，無論是哪一種情況，具有：h(i)-h(j)C(i,j)且容易驗證h(t)=0,所以該h是單調(diào)的。由于h滿足單調(diào)條件，所以也一定有h(n)h*(n)即滿足A*條件第3題n答：定義h1=n*k,其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小值。

15、h2=f=l,其中n是還未走過的城市數(shù)，ki是還未走過的城市間距離中n個最小的距離。顯然這兩個h函數(shù)均滿足A*條件。第4題提示：對于四皇后問題，如果放一個皇后的耗散值為1的話，則任何一個解的耗散值都是4。因此如果h是對該耗散值的估計，是沒有意義的。對于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對找到解的可能性的評價。比如像課上講到的，利用一個位置放皇后后，消去的對角線的長度來進行評價。第5題答：定義h1=M+C-2B,其中M,C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。B=1表示船在左岸，B=0表示船在右岸。也可以定義h2=M+C。h1是滿足A*條件的，而h2不滿足。要說明h(n)=M+C不滿足A*條件

16、是很容易的，只需要給出一個反例就可以了。比如狀態(tài)(1,1,1),h(n)=M+C=1+1=2,而實際上只要一次擺渡就可以達到目標狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。下面我們來證明h(n)=M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運到右岸，然后再有一個人將船送回來。這樣，船一個來回可以運過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們?nèi)繌淖蟀哆\到右岸。所以,x2+1在不考慮限制條件的情況下，也至少需要擺渡I2次。其中分子上的3表示剩下三個留待最后一次運過去。除以2是因為一個來回可以

17、運過去2人，需要2個來回，而來回數(shù)不能是小數(shù)，需要向上取整，這個用符號表示。而乘以2是因為一個來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的十1,則表示將剩下的3個運過去，需要一次擺渡化簡有：x2+l=M+C-3+l=M+C-2再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運到左岸。因此對于狀態(tài)(M,C,0)來說，其所需要的最少擺渡數(shù)，相當(dāng)于船在左岸時狀態(tài)(M+1,C,1)或(M,C+1,1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因此所需要的最少擺渡數(shù)為：(M+C+1)-2+1o其中(M+C+1)的十1表示送船回到左岸的那個人，而最后邊的十1,表示送船

18、到左岸時的一次擺渡?；営校?M+C+1)-2+1=M+C。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個式子表示為：M+C-2B。其中B=1表示船在左岸，B=0表示船在右岸。由于該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制條件時，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。精品資料推薦第6題答：題目的另一個說法是：當(dāng)A*結(jié)束時，OPEN表中任何一個具有f(n)f*(s)的節(jié)點都被擴展了。用反證法證明。假設(shè)在A*結(jié)束的時候，OPEN表中有一個節(jié)點n沒有被擴展，且f(n)f*(s)。A*算法每次從OPEN表中取出f值最小的節(jié)

19、點擴展，當(dāng)該節(jié)點是目標節(jié)點時，算法結(jié)束。并且由可采納性定理，知道這時A*找到了從初始節(jié)點到目標節(jié)點的最佳路徑，即f(t)=f*(s)。如果這時OPEN中存在f(n)f*(s)的節(jié)點n,由于f(n)f(t),則這時A*算法應(yīng)選擇n擴展，而不是目標t,與A*已經(jīng)結(jié)束矛盾。第7題答：因為A*選作擴展的任彳61一個節(jié)點n,均有f(n)f*(s)的節(jié)點，不會被A*所擴展。所以如果從OPEN表中去掉f(n)f*(s)的節(jié)點，不會影響A*的可采納性。而F是f*(s)的上界范圍，因此去掉f(n)F的節(jié)點也同樣不會影響A*的可采納性。第8題提示：對于8數(shù)碼問題，逆向搜索和正向搜索是完全一樣的，只是把目標狀態(tài)和初

20、始狀態(tài)對調(diào)就可以了。第9題提示：在搜索期間改善h函數(shù)，是一種動態(tài)改變h函數(shù)的方法。像改進的A*算法中，對NEST中的節(jié)點按g值的大小選擇待擴展的節(jié)點，相當(dāng)于令這些節(jié)點的h=0,就是動態(tài)修改h函數(shù)的一種方法。由定理6,當(dāng)h滿足單調(diào)條件時，A*所擴展的節(jié)點序列，其f是非遞減的。對于任何節(jié)點i,j,如果j是i的子節(jié)點，則有f(i)&f(j)利用該性質(zhì)，我們可以提出另一種動態(tài)修改h函數(shù)的方法：f(j)=max(f(i),f(j)以f(j)作為節(jié)點j的f值。f值的改變，隱含了h值的改變。當(dāng)h不滿足單調(diào)條件時，經(jīng)過這樣修正后的h具有一定的單調(diào)性質(zhì)，可以減少重復(fù)節(jié)點的可能性。第10題提示：很多知識對求解問題

21、有好處，這些知識并不一定要寫成啟發(fā)函數(shù)的形式，很多情況下，也不一定能清晰的寫成一個函數(shù)的形式。為了敘述方便，我們將兩個相對的扇區(qū)稱為相對扇區(qū)，圖中陰影部分的扇區(qū)稱為陰影扇區(qū)，非陰影部分的扇區(qū)稱為非陰影扇區(qū)。由題意，在目標狀態(tài)下，一個扇區(qū)的數(shù)字之和等于12,一個相對扇區(qū)的數(shù)字之和等于24,而一個陰影扇區(qū)或者非陰影扇區(qū)的數(shù)字之和為48為此，我們可以將目標進行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48(這時非陰影部分的數(shù)字和也一定為48)。為了這個目標我們可以通過每次車動圓盤45。實現(xiàn)。在第一個目標被滿足的情況下，我們再考慮第二個目標：每一個相對扇區(qū)的數(shù)字和為24。在實現(xiàn)這個目標的過程中，我們希望不破壞

22、第一個目標。為此我們采用轉(zhuǎn)動90。的方式實現(xiàn)，這樣即可以調(diào)整相對扇區(qū)的數(shù)字和，又不破壞第一個目標。在第二個目標實現(xiàn)之后，我們就可以實現(xiàn)最終目標：扇區(qū)內(nèi)的數(shù)字和為12。同樣我們希望在實現(xiàn)這個目標的時候，不破壞前兩個目標。為此我們采用轉(zhuǎn)動180。的方式實現(xiàn)。這樣同樣是即可以保證前兩個目標不被破壞，又可以實現(xiàn)第三個目標。經(jīng)過這樣的分析以后，我們發(fā)現(xiàn)該問題就清晰多了。當(dāng)然，是否每一個第一、第二個目標的實現(xiàn)，都能夠?qū)崿F(xiàn)第三個目標呢？有可能不一定。在這種情況下，就需要在發(fā)現(xiàn)第三個目標不能實現(xiàn)時，重新試探其他的第一、第二個目標。第三章課后習(xí)題答案第1題答：此題要求按照課中例題的方式，給出算法，以下是每個循環(huán)

23、結(jié)束時的搜索圖。上面這種做法比較簡單，也可以如下做:第2題從該搜索圖可以看出，無論先走者選擇哪個走步，后走者都可以走到標記為A的節(jié)點，該節(jié)點只剩下一枚錢幣，所以先走者必輸。于一般的具有n個錢幣的情況，當(dāng)n=4xm+1時，后走者存在取勝策略。因為后走者可以根據(jù)先走者的走法，選擇自己的走法，使得雙方拿走的錢幣數(shù)為4,這樣經(jīng)過m個輪回后，共拿走了4Xm個錢幣，只剩下了一枚錢幣，而此時輪到先走者走棋。所以在這種情況下，后4 xm走者存在取勝的策略。對于錢幣數(shù)不等于4xm+1的情況，先走者可以根據(jù)實際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為+1個，此時先走者相當(dāng)于4xm+1個錢幣時的后走者了。因此在

24、這種情況下，先走者存在獲勝的策略。第3題答：點擊看大圖第四章課后習(xí)題答案第1題答：(1)(Vx)P(x)-P(x)(Vx)-P(x)VP(x)P(x)VP(x)(Vx)P(x)一x)P(x)(Vx)P(x)V(x)P(x)(1-x)P(x)V(口y)P(y)(x)(匚y)P(x)VP(y)P(x)VP(f(a)(Vx)P(x)一(忖y)P(y)-P(f(x,y)A(Vy)Q(x,y)-P(y)精品資料推薦(|Vk)P(x)一(Wy)P(y)vp(f(x,y)八(Vy)Q(x,y)vP(y)(|Vx)P(x)-CVy)P(y)VP(f(x,y)A(wy)Q(x,y)AP(y)(|Vx)P(x)(

25、Vy)-P(y)VP(f(x,y)A(z)Q(x,z)AP(z)(|Vx)P(x)V(Yy)-P(y)VP(f(x,y)Afez)Q(x,z)AP(z)(mx)P(x)A(my)P(y)A-P(f(x,y)V(Vz)-Q(x,z)VP(z)(Bx)(By)(Vz)P(x)AP(y)AP(f(x,y)VQ(x,z)VP(z)(mx)(my)(Ez)P(x)AP(y)VQ(x,z)VP(z)AP(f(x,y)VQ(x,z)VP(z)P(a)AP(b)VQ(a,z)VP(z)AP(f(a,b)VQ(a,z)VP(z)P(a),P(b)VQ(a,z1)VP(z1),P(f(a,b)VQ(a,z2)VP

26、(z2)(Vx)(wy)P(x,y)-Q(y,x)AQ(y,x)-S(x,y)-tox)(甘y)P(x,y)-S(x,y)(Vx)(Ry)P(x,y)-Q(y,x)AQ(y,x)-S(x,y)-Ex)(Vy)P(x,y)-S(x,y)(Vx)(rny)P(x,y)VQ(y,x)AQ(y,x)VS(x,y)一5u)(Uv)P(u,v)VS(u,v)(Vx)(roy)P(x,y)VQ(y,x)AQ(y,x)VS(x,y)V(rou)(Vv)P(u,v)VS(u,v)(mx)(Vy)P(x,y)八Q(y,x)VQ(y,x)八S(x,y)V(mu)(Vv)P(u,v)VS(u,v)(rox)(Vy)(

27、au)(Vv)P(x,y)AQ(y,x)VQ(y,x)AS(x,y)VP(u,v)VS(u,v)(rox)(Vy)(au)(Vv)P(x,y)VQ(y,x)AP(x,y)VS(x,y)AQ(y,x)VS(x,y)VP(u,v)VS(u,v)(rox)(Vy)(au)(Vv)P(x,y)VQ(y,x)VP(u,v)VS(u,v)AP(x,y)VS(x,y)VP(u,v)VS(u,v)AQ(y,x)VS(x,y)VP(u,v)VS(u,v)P(a,y)VQ(y,a)VP(f(y),v)VS(f(y),v)AP(a,y)VS(a,y)VP(f(y),v)VS(f(y),v)AQ(y,a)VS(a,y

28、)VP(f(y),v)VS(f(y),v)P(a,y1)VQ(y1,a)VP(f(y1),v)VS(f(y1),v),P(a,y2)VS(a,y2)VP(f(y2),v2)VS(f(y2),v2),Q(y3,a)VS(a,y3)VP(f(y3),v3)VS(f(y3),v3)第2題答：設(shè)有兩個置換s1=a/x和s2=x/y,合適公式P(x,y)。則：P(x,y)s1s2=P(a,x)P(x,y)s2s1=P(a,a)二者不相等。所以說，置換的合成是不可交換的。第3題答：A/x,A./y,A/z,A/w,A/u第4題答：(1)P(f(x,x),A),P(f(y,f(y,A),A)在合一時，f(x

29、,x)要與f(y,f(y,a)進行合一，x置換成y后，y要與f(y,a)進行合一，出現(xiàn)了嵌套的情況，所以不能進行合一。P(A),P(x)一個是謂詞P,一個是P的反，不能合一。P(f(A),x),P(x,A)在合一的過程中，x置換為f(A),而f(A)與A不能合一。第6題答：(1)(叫)P(x)-P(A)AP(x)-P(B)目標取反化子句集：(mx)P(x)-P(A)AP(x)-P(B)(wP(x)VP(A)AP(x)VP(B)(Vx)P(x)AP(A)VP(x)AP(B)(Vx)P(x)AP(A)VP(x)AP(x)AP(A)VP(B)(Vx)P(x)AP(A)VP(x)AP(x)VP(B)A

30、P(A)VP(B)P(x)AP(A)VP(x)AP(x)VP(B)A-P(A)VP(B)得子句集：P(x1)P(A)VPx2P(x3)VP(B)P(A)VP(B)(Vz)Q(z)-P(z)一(x)Q(x)-P(A)AQ(x)-P(B)目標取反化子句集：(Vz)Q(z)-P(z)一x)Q(x)-P(A)AQ(x)-P(B)(Vz)Q(z)VP(z)-(5x)Q(x)VP(A)AQ(x)VP(B)(Vz)Q(z)VP(z)V(x)Q(x)VP(A)AQ(x)VP(B)(Vz)(Vx)Q(z)VP(z)AQ(x)AP(A)VQ(x)AP(B)(Vz)(Vx)Q(z)VP(z)AQ(x)AQ(x)VP

31、(B)AP(A)VQ(x)AP(A)VP(B)Q(z)VP(z)AQ(x)AQ(x)VP(B)AP(A)VQ(x)AP(A)VP(B)得子句集：Q(z)VP(z)Q(x2)Q(x3)VP(B)P(A)VQ(x4)P(A)VP(B)精品資料推薦(rax)(my)P(f(x)AQ(f(B)一P(f(A)AP(y)AQ(y)目標取反化子句集：(旬x)(y)P(f(x)AQ(f(B)一P(f(A)AP(y)AQ(y)(5x)(y)P(f(x)AQ(f(B)VP(f(A)AP(y)AQ(y)(x)(y)P(f(x)AQ(f(B)AP(f(A)V-P(y)VQ(y)P(f(x)AQ(f(B)AP(f(A)

32、V-P(y)VQ(y)得子句集：P(f(x1)Q(f(B)P(f(A)VP(y3)VQ(y3)(rax)(Vy)P(x,y)一(Hy)(Rx)P(x,y)目標取反化子句集：(Bx)(Vy)P(x,y)一(Vy)(Bx)P(x,y)(日x)(Vy)P(x,y)V(Vy)(ffix)P(x,y)(nix)(Vy)P(x,y)V(Vv)(OTu)P(u,v)(x)(Vy)P(x,y)A(Wv)(|Vu)P(u,v)(Wx)(Vy)(Wv)(Vu)P(x,y)AP(u,v)P(a,y)AP(u,f(y)得子句集：P(a,y1)2,P(u,f(y2)(Vx)P(x)AQ(A)VQ(B)一(rx)P(x)

33、AQ(x)目標取反化子句集：(Vx)P(x)AQ(A)VQ(B)(Wx)P(x)AQ(x)(3x)P(x)AQ(A)VQ(B)V(x)P(x)AQ(x)(|Vx)P(x)AQ(A)VQ(B)A(Vx)P(x)VQ(x)(Vx)P(x)AQ(A)VQ(B)A(Vy)P(y)VQ(y)(Vx)(Vy)P(x)AQ(A)VQ(B)AP(y)VQ(y)P(x)AQ(A)VQ(B)AP(y)VQ(y)得子句集：P(x)Q(A)VQ(B)P(y)VQ(y)第7題答：(1)將(Wx)P(x)取反化為子句：(Ex)P(x)=(x)P(x)與條件P(A1)VP(A2)合在一起得子句集:P(x),P(A1)VP(

34、A2)精品資料推薦所以，公式(x)P(x)是P(A1)VP(A2)的邏輯推論。(2)對于(mx)P(x)的Skolem形，即P(A),取反后為P(A),與條件P(A1)VP(A2)合在一起得子句集：P(A),P(A1)VP(A2)該子句集不能進行歸結(jié)，故P(A)不是P(A1)VP(A2)的邏輯推論。第8題答：該問題用謂詞公式描述如下：已知：(Vx)Food(x)-Like(John,x)Food(Apple)(Vx)(|Vy)Eat(y,x)八Kill(x,y)一Food(x)Eat(Bill,Peanut)AKill(Penut,Bill)(Vx)Eat(Bill,x)-Eat(Sue,x)

35、目標1：Like(John,Peanut)目標2：(Wx)Food(x)AEat(Sue,x)已知條件化子句集：(Vx)Food(x)-Like(John,x)=(Wx)Food(x)VLike(John,x)=Food(x)VLike(John,x)Food(Apple)(Vx)(|y)Eat(y,x)八Kill(x,y)一Food(x)=(Vx)(Wy)Eat(y,x)AKill(x,y)VFood(x)=(Wx)(y)Eat(y,x)VKill(x,y)VFood(x)=Eat(y,x)VKill(x,y)VFood(x)Eat(Bill,Peanut)AKill(Penut,Bill)

36、=Eat(Bill,Peanut),Kill(Penut,Bill)(Vx)Eat(Bill,x)-Eat(Sue,x)=(5/x)Eat(Bill,x)VEat(Sue,x)=Eat(Bill,x)VEat(Sue,x)目標1取反化子句集：Like(John,Peanut)目標2取反化子句集：(0 x)Food(x)AEat(Sue,x)=(Vx)Food(x)VEat(Sue,x)=Food(x)VEat(Sue,x)對于目標1,經(jīng)變量換名后，得子句集：V Eat(Sue,Food(x1)VLike(John,x1),Food(Apple),Eat(y2,x2)VKill(x2,y2)VF

37、ood(x2),Eat(Bill,Peanut),Kill(Penut,Bill),Eat(Bill,x3)x3),Like(John,Peanut)歸結(jié)樹如下:對于目標2,經(jīng)變量換名后，得子句集：V Eat(Sue,Food(x1)VLike(John,x1),Food(Apple),Eat(y2,x2)VKill(x2,y2)VFood(x2),Eat(Bill,Peanut),Kill(Penut,Bill),Eat(Bill,x3)x3),Food(x)VEat(Sue,x)歸結(jié)樹如下：修改證明樹如下:A、B兩個子句的歸結(jié)，兩個子句中的y應(yīng)該B中的y用y1代替，則歸結(jié)結(jié)果如下：得到解答

38、為：Food(Peanut)AEat(Sue,Peanut)第9題答：該歸結(jié)過程存在錯誤。其原因是由于不同的子句用了相同的變量名引起的。如上圖中是不同的變量，在歸結(jié)時，如果用不同的變量分別表示，就不會出現(xiàn)這樣的問題了。比如第10題答：化子句集：(Vu)LAST(cons(u,NIL),u)=LAST(cons(u,NIL),u)(Vx)(Vy)(Wz)(LAST(y,z)-LAST(cons(x,y),z)=(VX)(Vy)(Vz)(LAST(y,z)VLAST(cons(x,y),z)=LAST(y,z)VLAST(cons(x,y),z)KL)C&TlSCOIiE目標取反:=(Vv) LA

39、ST (cons (2, cons (1, NIL ) ) , v)經(jīng)變量換名后，得子句集:LAST (cons (u, NIL ) , u) , -LAST (y, z) V LAST (cons (x, y) , z) , -LAST (cons (2, cons (1, NIL) ) , v) 歸結(jié)樹如下:LAST (com (2 j cons (1 皿)j 1)(Ev) LAST (cons (2, cons (1, NIL ),修改證明樹:得到解答：LAST(cons(2 , cons(1 , NIL) , 1),表 cons(2, cons(1 , NIL)的最后一個元素為 1通過

40、以上歸結(jié)過程，我們可以看出，該方法求解長表的最后一個元素的方法是，每次將長表去掉第一個元素，直到最后得到了只有一個元素的表，該元素就是長表的最后一個元素第12題= -LAST (cons (2, cons (1, NIL ),LAST,LAST (con (jt y) j 上LAST (coils a ML) j r)VLAST (cons (2cons (1 . HIIJ) j 力XAST (sns ，q qg Cl i ) v) YLAST (c arts 2 j cons C HTL) 中)Iflns C2 j cons (1 j NIDJj v)LAST (兩二僅 * jr) J z)

41、 J“AST (c(mS (1 HTL) j z)LAST Cc mu (ii j NIL uLAST Goni(-u j NIL) , T精品資料推薦答：我們用Skier(x)表示x是滑雪運動員，Alpinist(x)表示x是登山運動員，Alpine(x)表示x是Alpine俱樂部的成員。問題用謂詞公式表示如下：已知：Alpine(Tony)Alpine(Mike)Alpine(John)(x)Alpine(x)SkierA)pinist(x)(x)Alpinist(x)fLike(x,Rain)(x)Like(x,Snow)fSkier(x)(x)Like(Tony,x)fLike(Mike,x)(x)Like(Tony,x)-Like(Mike,x)Like(Tony,Snow)Like(Tony,Rain)目標：(vx)Alpine(x)AAlpinist(x)ASkier(x)化子句集：Alpine(Tony)Alpine(Mike)Alpine(John)(x)Alpine(x)Skier(Alpinist(x)=(x)Alpine(x)VSkier(x)VAlpinist(x)=Alpine(x)VSk