人工智能課后題答案20

人工智能課后題答案20

第I題

答：1,綜合數(shù)據(jù)庫

定義三元組：(m,c,b)

其中：那M5,表示傳教士在河左岸的人數(shù)。

0<5,表示野人在河左岸的認(rèn)輸。

be{01},b=i,表示船在左岸，b=o,表示船在右岸。

2,規(guī)則集

規(guī)則集能夠用兩種方式表示，兩種方法均可。

第一種方法：按每次渡河的人數(shù)分別寫出每一個規(guī)則，共(30)、(03)、(21)、(11)、(10)、(01)、(20)、(02)八種渡河的可能(其

中(xy)表示x個傳教士與y個野人上船渡河)，因此共有16個規(guī)則(從左岸到右岸、右岸到左岸各八個)。注意：這里沒有(12),

由于該組合在船上的傳教士人數(shù)少于野人人數(shù)。

規(guī)則集如下：

rl：lF(m,c,1)THEN(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-l,c-l,0)

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)

rlO：IF(m,c,0)THEN(m,c+3,1)

rll：IF(m,c,0)THEN(m+2,c+1J)

r12：IF(m,c,0)THEN(m+1,c+1,1)

rl3：IF(m,c,0)THEN(m+l,c,1)

rJ4：IF(m,c,0)THEN(m,c+l,1)

r15：IF(m,c,0)THEN(m+2,c,1)

rl6：IF(m,c,0)THEN(m,c+2,1)

第二種方法：將規(guī)則集綜合在一起，簡化表示。規(guī)則集如下：

rl：IF(m,c,1)and0<i+j(=3and(i>=jori=0)THEN(m-i,c-j,0)

r2：IF(m,c,0)and0<i+j(=3and(i>=jori=0)THEN(m+i,c+j,I)

3,初始狀態(tài)：(5,5,1)

4,結(jié)束狀態(tài)：(0,0,0)

第2題

答：1,綜合數(shù)據(jù)庫

定義兩元組：(L5,L2)

其中：0yL5<=5,表示容量為5升的壺的當(dāng)前水量。

(X=L2<=2,表示容量為2升的壺的當(dāng)前水量。

2,規(guī)則集

rl：IF(L5,L2)THEN(5,L2)/*將L5灌滿水*/

r2：IF(L5,L2)THEN(L5,2)/*將L2灌滿水*/

r3：IF(L5,L2)THEN(0,L2)/*將L5水到光*/

r4：IF(L5,L2)THEN(L5,0)/*將L2水到光*/

r5：IF(L5,L2)andL5+L2<=5THEN(L5+L2,0)/*L2至入L5中*/

r6：IF(L5,L2)andL5+L2>5THEN(5,L5+L2-5)/*L2到入L5中*/

r7：IF(L5,L2)andL5+L2<=2THEN(0,L5+L2)/*L5到入L2中*/

r8：IF(L5,L2)andL5+L2>5THEN(L5+L2-2,2)/*L5至lj入L2中*/

3,初始狀態(tài)：(5,0)

4,結(jié)束條件：(x,1),其中x表示不定。當(dāng)然結(jié)束條件也能夠?qū)懗桑?0,1)

第3題

答：1,綜合數(shù)據(jù)庫

定義三元組：(A,B,C)

其中A,B,C分別表示三根立柱，均為表，表的元素為1?N之間的整數(shù)，表示N個不一致大小的盤子，數(shù)值小的數(shù)表示小盤子，

數(shù)值大的數(shù)表示大盤子。表的第一個元素表示立柱最上面的柱子，其余類推。

2,規(guī)則集

為了方便表示規(guī)則集，引入下列幾個函數(shù)：

first(L)：取表的第一個元素，關(guān)于空表，first得到一個很大的大于N的數(shù)值。

tail(L)：取表除了第一個元素以外，其余元素構(gòu)成的表。

cons(x,L)：將x加入到表L的最前面。

規(guī)則集：

rl:IF(A,B,C)and(first(A)<first(B))THEN(tail(A),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)<first(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=l：猴子在箱子上

H=0：猴子沒有抓到香蕉

H=l：猴子抓到了香蕉

2,規(guī)則集

rl:IF(x,y,z,0,0)THEN(w,y,z,0,0)猴子從x處走到w處

r2:IF(x,y,x,0,0)THEN(z,y,z,0,0)假如猴子與箱子在一起,猴子將箱子推到z處

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,I)假如箱子在香蕉處，猴子在箱子上,猴子摘到香蕉

其中x,y,z,w為變量

3,初始狀態(tài)(c,a,b,0,0)

4,結(jié)束狀態(tài)(xl,x2,x3,x4,1)其中xl?x4為變量。

第5題

答：1,綜合數(shù)據(jù)庫

定義四元組：(x,y,z,n)

其中x,y,x￡[0H，1表示錢幣為正面，0表示錢幣為方面。戶0,123,表示當(dāng)前狀態(tài)是通過n次翻錢幣得到的。

2,規(guī)則庫

rl:IF(x,y,z,n)THEN(~x,y,z,n+1)

r2:IF(x,y,z,n)THEN(x,~y,z,n+l)

r3:IF(x,y,z,n)THEN(x,y,~z,n+l)

其中?x表示對x取反。

3,初始狀態(tài)(1,1,0,0)

4,結(jié)束狀態(tài)(1,1,1,3)或者者(0,0,0,3)

第6題

提示：將十進(jìn)制數(shù)分為整數(shù)部分與小數(shù)部分兩部分。用四元組(a,b.c,d)表示綜合數(shù)據(jù)庫，其中a,b表示到目前為止還沒有轉(zhuǎn)換的十

進(jìn)制數(shù)的整數(shù)部分與小數(shù)部分，c,d表示已經(jīng)轉(zhuǎn)換得到的二進(jìn)制數(shù)的整數(shù)部分與小數(shù)部分。然后根據(jù)十進(jìn)制數(shù)轉(zhuǎn)換二進(jìn)制數(shù)的原理，

分別定義整數(shù)的轉(zhuǎn)換規(guī)則與小數(shù)的轉(zhuǎn)換規(guī)則，一次規(guī)則的執(zhí)行，轉(zhuǎn)換得到二進(jìn)制數(shù)的一位。

第7題

答：設(shè)規(guī)則R的逆用R，表示。由題意有R應(yīng)用于D后，得到數(shù)據(jù)庫D：由可交換系統(tǒng)的性質(zhì)，

有:rule(D)CZrule(D')

其中rule(D)表示可應(yīng)用于D的規(guī)則集合。

由于R，是R，的逆，因此R，應(yīng)用于D，后，得到數(shù)據(jù)庫D。同樣由可交換系統(tǒng)的性質(zhì)，

有：rule(D')Crule(D)

綜合上述兩個式子，有rule(D')=rule(D)o

第8題

答：說明一個產(chǎn)生式系統(tǒng)是可交換的，就是要證明該產(chǎn)生式系統(tǒng)滿足可交換產(chǎn)生式系統(tǒng)的三條性質(zhì)。

(1)該產(chǎn)生式系統(tǒng)以整數(shù)的集合為綜合數(shù)據(jù)庫，其規(guī)則是將集合中的兩個整數(shù)相乘后加入到數(shù)據(jù)庫中。由于原先數(shù)據(jù)庫是新數(shù)據(jù)

庫的子集，因此原先的規(guī)則在新數(shù)據(jù)庫中均能夠使用。因此滿足可交換產(chǎn)生式系統(tǒng)的第一條性質(zhì)。

(2)該產(chǎn)生式系統(tǒng)以某個整數(shù)的子集的出現(xiàn)為目標(biāo)條件，由于規(guī)則執(zhí)行的結(jié)果只是向數(shù)據(jù)庫中添加數(shù)據(jù)，假如原數(shù)據(jù)庫中已經(jīng)滿

足口標(biāo)了，即出現(xiàn)了所需要的整數(shù)子集，規(guī)則的執(zhí)行結(jié)果不可能破壞該整數(shù)子集的出現(xiàn)，因此新的數(shù)據(jù)庫仍然會滿足目標(biāo)條件。滿

足可交換產(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中的規(guī)則能夠直接應(yīng)用與D,

因此R1中規(guī)則的應(yīng)用與R2中規(guī)則的執(zhí)行結(jié)果無關(guān)，也與R1中其他的規(guī)則的執(zhí)行無關(guān)。因此能夠認(rèn)為，先將R1中所有的規(guī)則對

D應(yīng)用，然后再按照原先的次序應(yīng)用R2中的規(guī)則。因此關(guān)于本題的情況，這樣得到的綜合數(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í)題

第1題

答：為了方便起見，我們用((AB)()())這樣的表表示一個狀態(tài)。這樣得到搜索圖如下：

((AB)00)

第2題

提示：可定義h為：

h=B右邊的W的數(shù)目

設(shè)j節(jié)點是i節(jié)點的子節(jié)點，則根據(jù)走法不一致，h⑴-h(j)的值與C(i,j)分為如下幾種情況：

(1)B或者W走到了相鄰的一個空格位置，如今：h(i)-h(j)=0,C(i,j)=l：

(2)W跳過了1或者2個W,如今h(i)-h(j)=0,C(i,j)=l或者2；

(3)W向右跳過了一個B(可能同時包含一個W),如今：h(i)-h(j)=-l,C(i,j尸1或者2；

(4)W向右跳過了兩個B,如今：h(i)-h(j)=-2,C(i,j)=2；

(5)W向左跳過了一個B(可能同時包含一個W),如今：h(i)-h(j)=l,C(i,j)=l或者2；

(6)W向左跳過了兩個B,如今：h(i)-h(j)=2,C(ij)=2；

(7)B跳過了1或者2個B,如今h(i)-h(j)=0,C(ij)=l或者2；

(8)B向右跳過了一個W(可能同時包含一個B),如今：h(i)-h(j)=l,C(i,j)=l或者2；

(9)B向右跳過了兩個W,如今：h(i)-h(j)=2,C(ij)=2：

(10)B向左跳過了一個W(可能同時包含一個B),如今：h(i)-h(j)=-l,C(i,j)=l或者2；

(11)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)Wh*(n),即滿足A*條件。

第3題

n

N島

答：定義hl=n*k,其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小值。h2=3=l,其中n是還未走過的城市數(shù)，

ki是還未走過的城市間距離中n個最小的距離。顯然這兩個h函數(shù)均滿足A*條件。

第4題

提示：關(guān)于四皇后問題，假如放一個皇后的耗散值為1的話，則任何一個解的耗散值都是4。因此假如h是對該耗散值的估計，是沒

有意義的。關(guān)于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對找到解的可能性的評價。比如像課上講到的，利用一個位置放皇后后，消去的對

角線的長度來進(jìn)行評價。

第5題

答：定義hl=M+C-2B,其中M,C分別是在河的左岸的傳教士人數(shù)與野人人數(shù)。B=1表示船在左岸，B=0表示船在右岸。

也能夠定義h2=M+C。

hl是滿足A*條件的，而h2不滿足。

要說明h(n)=M+C不滿足A*條件是很容易的，只需要給出一個反例就能夠了。比如狀態(tài)(1,1,1),h(n)=M+C=1+1=2,而實際上只要一次

擺渡就能夠達(dá)到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散值為1。因此不滿足A*的條件。

下面我們來證明h(n)=M+C-2B是滿足A*條件的。

我們分兩種情況考慮。先考慮船在左岸的情況。假如不考慮限制條件，也就是說，船一次能夠?qū)⑷藦淖蟀哆\到右岸，然后再有一個人將

船送【可來。這樣，船?個來回能夠運過河2人，而船仍然在左岸。而最后剩下的三個人，則能夠一次將他們?nèi)繌淖蟀哆\到右岸。因此，

M+C-3

x2+l

在不考慮限制條件的情況下，也至少需要擺渡次。其中分子上的3”表示剩下三個留待最后一次運過去。除以“2"

A+C-3

是由于一個來回能夠運過去2人，需要2個來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個用符號-1表示。而乘以“2”是

由于一個來回相當(dāng)于兩次擺渡，因此要乘以2。而坡后的“+1”，則表示將剩下的3個運過去，需要一次擺渡。

化簡有：

M+C—3-,、M+C—3c.,,?c,..

-------------x2+l>---------------x2+l=M+C-3+l=M+C-2

22

再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運到左岸。因此關(guān)于狀態(tài)(M,C,0)來說，其所需要的最少擺

渡數(shù)，相當(dāng)于船在左岸時狀態(tài)(M+l,C,1)或者(M,C+l,1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因

此所需要的最少擺渡數(shù)為：(M+C+l)-2+l。其中(M+C+1)的”+1”表示送船回到左岸的那個人，而最后邊的“+1”，表示送船到左岸時的一

次擺渡。

化簡有：(M+C+l)-2+l=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é)點都被擴(kuò)展了。

用反證法證明。

假設(shè)在A*結(jié)束的時候，OPEN表中有一個節(jié)點n沒有被擴(kuò)展，且f(n)<f*(s)。A*算法每次從OPEN表中取出f值最小的節(jié)點擴(kuò)展，當(dāng)該節(jié)

點是目標(biāo)節(jié)點時，算法結(jié)束。同時由可采納性定理，明白這時A*找到了從初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，即f(t)=f*(s)。假如這時OPEN

中存在f(n)(伴(s)的節(jié)點n,由于f(n)<f(t),則這時A*算法應(yīng)選擇n擴(kuò)展，而不是目標(biāo)I,與A*已經(jīng)結(jié)束矛盾。

笫7題

答：由于A*選作擴(kuò)展的任何一個節(jié)點n,均有f(n)Sf*(s),因此f(n)>f*⑸的節(jié)點，不可能被A*所擴(kuò)展。因此假如從OPEN表中去掉

f(n)>件(s)的節(jié)點，不可能影響A*的可采納性。而F是件(s)的上界范圍，因此去掉f(n)>F的節(jié)點也同樣不可能影響A*的可采納性。

第8題

提示：關(guān)于8數(shù)碼問題，逆向搜索與正向搜索是完全一樣的，只是把目標(biāo)狀態(tài)與初始狀態(tài)對調(diào)就能夠了。

第9題

提示：在搜索期間改善h函數(shù)，是一種動態(tài)改變h函數(shù)的方法。像改進(jìn)的A*算法中，對NEST中的節(jié)點按g值的大小選擇待擴(kuò)展的

節(jié)點，相當(dāng)于令這些節(jié)點的h=0,就是動態(tài)修改h函數(shù)的一種方法。

由定理6,當(dāng)h滿足單調(diào)條件時，A*所擴(kuò)展的節(jié)點序列，其f是非遞減的。關(guān)于任何節(jié)點i,j,假如j是i的子節(jié)點，則有也好埒)。利用

該性質(zhì)，我們能夠提出另一種動態(tài)修改h函數(shù)的方法：

f(j)=max(f(i),f(j))

以f(j)作為節(jié)點j的f值。f值的改變，隱含了h值的改變。

當(dāng)h不滿足單調(diào)條件時，通過這樣修正后的h具有一定的單調(diào)性質(zhì)，能夠減少重復(fù)節(jié)點的可能性。

第10題

提示：很多知識對求解問題有好處，這些知識并不一定要寫成啟發(fā)函數(shù)的形式，很多情況下，也不一定能清晰的寫成一個函數(shù)的形式。

為了敘述方便，我們將兩個相對的扇區(qū)稱之相對扇區(qū)，圖中陰影部分的扇區(qū)稱之陰影扇區(qū)，非陰影部分的扇區(qū)稱之非陰影扇區(qū)。由

題意，在目標(biāo)狀態(tài)下，一個扇區(qū)的數(shù)字之與等于12,一個相對扇區(qū)的數(shù)字之與等于24,而一個陰影扇區(qū)或者者非陰影扇區(qū)的數(shù)字之與為

48。為此，我們能夠?qū)⒛繕?biāo)進(jìn)行分解，首先滿足陰影扇區(qū)的數(shù)字之與為48（這時非陰影部分的數(shù)字與也一定為48）。為了這個目標(biāo)我們

能夠通過每次轉(zhuǎn)動圓盤45。實現(xiàn)。在第一個目標(biāo)被滿足的情況下，我們再考慮第二個目標(biāo)：每一個相對扇區(qū)的數(shù)字與為24。在實現(xiàn)這個目

標(biāo)的過程中，我們希望不破壞第一個目標(biāo)。為此我們使用轉(zhuǎn)動90。的方式實現(xiàn)，這樣即能夠調(diào)整相對扇區(qū)的數(shù)字與，又不破壞第一個目標(biāo)。

在第二個目標(biāo)實現(xiàn)之后，我們就能夠?qū)崿F(xiàn)最終目標(biāo)：扇區(qū)內(nèi)的數(shù)字與為12。同樣我們希望在實現(xiàn)這個目標(biāo)的時候，不破壞前兩個目標(biāo)。為

此我們使用轉(zhuǎn)動183的方式實現(xiàn)。這樣同樣是即能夠保證前兩個目標(biāo)不被破壞，又能夠?qū)崿F(xiàn)第三個目標(biāo)。通過這樣的分析以后，我們發(fā)

現(xiàn)該問題就清晰多了.當(dāng)然，是否每一個第一、第二個目標(biāo)的實現(xiàn)，都能夠?qū)崿F(xiàn)第三個目標(biāo)呢？有可能不一定。在這種情況下，就需要在

發(fā)現(xiàn)第三個目標(biāo)不能實現(xiàn)時，重新試探其他的第一、第二個目標(biāo)。

第三章課后習(xí)題答案

第1題

答：此題要求按照課中例題的方式，給出算法，下列是每個循環(huán)結(jié)束時的搜索圖。

上面這種做法比較簡單，也能夠如下做:

8

866

(4)0@

6

?

(5)?@

第七步

4(3)

2

(6)

第2題

從該搜索圖能夠看出，不管先走者選擇哪個走步，后走者都能夠走到標(biāo)記為A的節(jié)點，該節(jié)點只剩下一枚錢幣，因此先走者必輸。關(guān)

于通常的具有n個錢幣的情況，當(dāng)n=4xm+l時，后走者存在取勝策略。由于后走者能夠根據(jù)先走者的走法，選擇自己的走法，使得雙方

拿走的錢幣數(shù)為4,這樣通過m個輪回后，共拿走了4xm個錢幣，只剩下了一枚錢幣，而如今輪到先走者走棋。因此在這種情況下，后

走者存在取勝的策略。關(guān)于錢幣數(shù)不等于4xm+l的情況，先走者能夠根據(jù)實際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為4xm

+1個，如今先走者相當(dāng)于4xm+l個錢幣時的后走者了。因此在這種情況下，先走者存在獲勝的策略。

第3題

答：

點擊看大圖

第四章課后習(xí)題答案

第1題

答：(1)(Vx)[P(x)-P(x)]

(Vx)[~P(x)VP(x)]

卜P(x)VP(x)}

(2){~{(Vx)P(x)}}一(tDx)[~P(x)]

{(Vx)P(x))V(rax)[~P(x)]

{(Vx)P(x))V(Wy)[~P(y)]

(Vx)(tDy)[P(x)V~P(y)]

{P(x)V~P(f(a))}

(3)~(Vx){P(x)->{(Vy)[P(y)->P(f(x,y))]A~(Vy)[Q(x,yHP(y)])}

~(Vx){P(x)^{(Vy)[~P(y)VP(f(x,y))]A~(Vy)[~Q(x,y)VP(y)])}

~(Ux){P(x)—{(Vy)[~P(y)VP(f(x,y))]A(ffiy)[Q(x,y)A-P(y)]))

~(Vx){P(x)->{(Vy)[~P(y)VP(f(x>y))]A(tOz)[Q(x,z)A~P(z)]})

~(Vx){~P(x)V{(Vy)[-P(y)VP(f(x,y))]A(Wz)[Q(x,z)A~P(z)]))

(Wx){P(x)A{(?y)[P(y)A-P(f(x,y))]V(Vz)[-Q(x,z)VP(z)])|

(Wx)(Wy)(Vz)(P(x)A{[P(y)A-P(f(x,y))]V[~Q(x,z)VP(z)])}

(tDx)(Wy)(Vz){P(x)A[P(y)V-Q(x,z)VP(z)]A[-P(f(x,y))V~Q(x,z)VP(z)])

{P(a)A[P(b)V-Q(a,z)VP(z)]A[-P(f(a,b))V~Q(a,z)VP(z)]}

(P(a),P(b)V-Q(a,zl)VP(zl),-P(f(a,b))V-Q(a,z2)VP(z2)}

(4)(Vx)(tDy){[P(x,y)->Q(y,x)]A[Q(y,x)—S(x,y)])-*(Wx)(Vy)[P(x,y)-S(x,y)]

(Vx)(tDy){[P(x,y)-Q(y,x)]A[Q(y,x)-S(x,y)])->(Wx)(Vy)[P(x,y)->S(x,y)]

(Vx)(tDy){[-P(x,y)VQ(y,x)]A[-Q(y,x)VS(x,y)]}—?(?0)(Vv)[~P(u,v)VS(u?v)]

~{(Vx)(?y){[-P(x,y)VQ(y,x)]A[-Q(y,x)VS(x,y)]}}V(?u)(Vv)[-P(u,v)VS(u,v)|

(tDx)(Vy){[P(x?y)A~Q(y,x)]V[Q(y,x)A~S(x,y)]}V(Wu)(Vv)[-P(u>v)VS(u,v)]

(GJx)(Vy)(tDu)(Vv){[P(x,y)/\~Q(y,x)]V[Q(y,x)A~S(x,y)]}V[-P(u,v)VS(u,v)]

(Wx)(Vy)(Wu)(Vv){[P(x,y)VQ(y,x)]A[P(x,y)V-S(x?y)]A[-Q(y>x)V~S(x,y)]}V[-P(u,v)VS(u,v)]

(tDx)(Vy)(?u)(Vv)[P(x,y)VQ(y,x)V~P(u,v)VS(u,v)]A[P(x,y)V~S(x,y)V~P(u>v)VS(u,v)]A[~Q(y?x)V~S(x,y)V-P(u>

v)VS(u,v)]

[P(a,y)VQ(y,a)V~P(f(y),v)VS(f(y),v)]A[P(a,y)V~S(a,y)V?P(f(y),v)VS(f(y),v)]A[-Q(y,a)V-S(a,y)V~P(f(y),v)

VS(f(y),v)]

{P(a,yl)VQ(yl,a)V~P(f(yl),v)VS(f(yl),v),P(a,y2)V-S(a,y2)V-P(f(y2),v2)VS(f(y2),v2),~Q(y3,a)V-S(a,y3)V-P(f(y3),

v3)VS(f(y3),v3))

第2題

答：設(shè)有兩個置換sl={a/x}與s2={x/y},合適公式P(x,y)。則：

P(x,y)sls2=P(a,x)

P(x,y)s2sl=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,x)要與f(y,f(y,a))進(jìn)行合一，x置換成y后，y要與f(y,a)進(jìn)行合一，出現(xiàn)了嵌套的情況，因此不能進(jìn)行合一。

(2){~P(A),P(x)}

一個是謂詞P,一個是P的反，不能合一。

(3)(P(f(A),x),P(x,A)}

在合一的過程中，x置換為f(A),而f(A)與A不能合一。

第6題

答：⑴(tDx){[P(x)->P(A)]A[P(x)-P(B)])

目標(biāo)取反化子句集：

~(tDx){[P(x)-P(A)]A(P(x)-P(B)]}

~(Wx){卜P(x)VP(A)]A[-P(x)VP(B)])

(Vx){[P(x)A~P(A)]V[P(x)A-P(B)])

(Vx){[P(x)A~P(A)]VP(x)}A{[P(x)A~P(A)]V~P(B)}}

(Vx){P(x)A[-P(A)VP(x)]A[P(x)V~P(B)]A[-P(A)V~P(B)])

P(x)AhP(A)VP(x)]A[P(x)V-P(B)]A[-P(A)V~P(B)]

得子句集：

l,P(xl)

2,~P(A)VP{x2}

3,P(x3)V~P(B)

4,~P(A)V~P(B)

(2)(Vz)[Q(z)TP(Z)]->{(^x)[Q(x)-P(A)]A[Q(x)->P(B)])

目標(biāo)取反化子句集：

~I(Vz)[Q(z)-P⑵]f(tOx)[Q(x)fP(A)]A[Q(x)-P(B)]}}

~{(Vz)[~Q(z)VP(z)]^{(ffix)[~Q(x)VP(A)]A[~Q(x)VP(B)]))

~l~!(Vz)|~Q(z)VP(z)]}V{(tnx)|~Q(x)VP(A)]A[~Q(x)VP(B)]})

(Vz)(Vx)([~Q(z)VP(z)]A([Q(x)A~P(A)]V[Q(x)A~P(B)]))

NZ)(VX){(~Q⑵VP⑵]A{Q(X)AIQ(X)V~P(B)]A[~P(A)VQ(X)]A[~P(A)V~P(B)]}

[-Q(Z)VP(Z)]AQ(X)A[Q(X)V~P(B)]A[-P(A)VQ(X)]A[-P(A)V~P(B)]

得子句集：

1,~Q(z)VP(z)

2,Q(x2)

3,Q(x3)V~P(B)

4,~P(A)VQ(x4)

5,~P(A)V~P(B)

(3)(tDx)(Wy)([P(f(x))AQ(f(B))]->[P(f(A))AP(y)AQ(y)])

目標(biāo)取反化子句集：

~(t0x)(t0y)([P(f(x))AQ(f(B))]一[P(f(A))AP(y)AQ(y)])

~(?x)(?y)HP(f(x))AQ(f(B))]V[P(f(A))AP(y)AQ(y)])

(x)(y){[P(f(x))AQ(f(B))]A[~P(f(A))V~P(y)V~Q(y)])

P(f(x))AQ(f(B))A[~P(f(A))V~P(y)V~Q(y)]

得子句集：

1.P(f(xl))

2.Q(f(B))

3,~P(f(A))V~P(y3)V~Q(y3)

(4)(t5Jx)(Vy)P(x,y)-*(Vy)(Bx)P(x,y)

目標(biāo)取反化子句集：

~((t0x)(Vy)P(x,y)-?(Vy)(Wx)P(x,y))

~(~[(Wx)(Vy)P(x,y)]V(Vy)(Wx)P(x,y))

~{~[(?x)(Vy)P(x,y)]V(Vv)(tDu)P(u,v)}

[(?x)(Vy)P(x,y)]A(tOv)(Vu)~P(u,v)

(Bx)(Vy)(Bv)(Vu)P(x,y)]A~P(u,v)

P(a,y)A~P(u,f(y))

得子句集：

1,P(a,yl)

2,~P(u,f(y2))

(5)(Vx){P(x)A[Q(A)VQ(B)])->(rax)[P(x)AQ(x)]

目標(biāo)取反化子句集：

~((Vx){P(x)A[Q(A)VQ(B)])->(tDx)[P(x)AQ(x)])

~{~{(Vx)P(X)A|Q(A)VQ(B)|}V(Wx)[P(x)AQ(x)])

{(Vx)P(x)A[Q(A)VQ(B)])A(Vx)[~P(x)V~Q(x)])

{(VX)P(x)A[Q(A)VQ(B)]}A(Vy)[-P(y)V~Q(y)]}

(Vx)(Vy){P(x)A[Q(A)VQ(B)]A[-P(y)V~Q(y)]}

P(x)A[Q(A)VQ(B)]A[-P(y)V~Q(y)]

得子句集：

1.P(x)

2,Q(A)VQ(B)

3.~P(y)V~Q(y)

第7題

答：(1)將(Ex)P(x)取反化為子句：

?(tDx)P(x)=(x)~P(x)

與條件［P(Al)VP(A2)］合在一起得子句集:

{?P(x),P(Al)VP(A2)}

因此，公式(Hx)P(x)是［P(Al)VP(A2)］的邏輯推論。

(2)關(guān)于(ex)P(x)的Skolem形，即P(A),取反后為-P(A),與條件［P(Al)VP(A2)］合在一起得子句集:

{~P(A),P(Al)VP(A2))

該子句集不能進(jìn)行歸結(jié)，故P(A)不是［P(Al)VP(A2)］的邏輯推論。

第8題

答：該問題用謂詞公式描述如下：

已知：

(1)(Vx){Food(x)^Like(John,x)(

(2)Food(Apple)

(3)(Vx)(Vy){［Eat(y,x)八?Kill(x,y)］-Food(x)}

(4)Eat(BilLPeanut)A-Kill(Penut,Bill)

(5)(Vx){Eat(Bill,x)—>Eat(Sue,x)}

目標(biāo)1：Like(John,Peanut)

目標(biāo)2：(tDx)Food(x)AEat(Sue,x)

已知條件化子句集：

(1)(Vx){Food(x)—>Likc(John,x)}

=(Vx){-Food(x)VLike(John,x)}

=>{-Food(x)VLikc(John,x))

(2)Food(Apple)

(3)(Vx)(Vy){[Eat(y,x)A~Kill(x,y)]—Food(x)}

=(Vx)(Vy){~[Eat(y,x)A*-Kill(x,y)]VFood(x))

=(Vx)(Vy){-[Eat(y,x)VKill(x,y)]VFood(x))

=>{~Eat(y,x)VKill(x,y)VFood(x)}

(4)Eat(Bill,Peanut)A-Kill(Penut,Bill)

=>{Eat(Bill,Peanut),-Kill(Penut,Bill))

(5)(Vx){Eat(Bill,x)->Eat(Suc,x)}

=(Vx){-Eat(Bill,x)VEat(Sue,x)J

=>-Eat(Bill,x)VEat(Sue,x)

目標(biāo)1取反化子句集：

~Like(John,Peanut)

目標(biāo)2取反化子句集：

~{(tDx)Food(x)AEat(Sue,x))

=(Vx)-Food(x)V-Eat(Sue,x)

=>-Food(x)V-Eat(Sue,x)

關(guān)于目標(biāo)1,經(jīng)變量換名后，得子句集：

{-Food(x1)VLike(John,x1),Food(Apple),~Eat(y2,x2)VKill(x2,y2)VFood(x2),Eat(Bill,Peanut),-Kill(Penut,Bill),-Eat(Bill,x3)VEat(Sue,

x3),~Likc(John,Peanut))歸結(jié)樹如下：

關(guān)于目標(biāo)2,經(jīng)變量換名后，得子句集：

{-Food(x1)VLike(John,xl),Food(Apple),~Eat(y2,x2)VKill(x2,y2)VFood(x2),Eat(Bill,Peanut),-Kill(Pcnut,Bill),-Eat(Bill,x3)VEat(Sue,

x3),-Food(x)V-Eat(Sue,x)(歸結(jié)樹如下：

修改證明樹如下:

得到解答為：Fcx)d(Peanut)AEat(Sue,Peanut)

第9題

答：該歸結(jié)過程存在錯誤。其原因是由于不一致的子句用了相同的變量名引起的。如上圖中A、B兩個子句的歸結(jié)，兩個子句中的y應(yīng)

該是不一致的變量，在歸結(jié)時，假如用不一致的變量分別表示，就不可能出現(xiàn)這樣的問題了。比如B中的y用yl代替，則歸結(jié)結(jié)果如下:

第10題

答：化子句集：

(Vu)LAST(cons(u,NIL),u)

=>LAST(cons(u,NIL)，u)

(Vx)(Vy)(Vz)(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)

目標(biāo)取反：

?(tDv)LAST(cons(2,cons(1,NIL)),v)

=(Vv)-LAST(cons(2,cons(1,NIL)),v)

=>-LAST(cons(2,cons(1,NIL)),v)

經(jīng)變量換名后，得子句集：

(LAST(cons(u,NIL),u),-LAST(y,z)VLAST(cons(x,y),z),-LAST(cons(2,cons(1,NIL)),v)}

歸結(jié)樹如下：

修改證明樹:

得到解答：LAST(cons(2,cons(1,NIL)),1),表cons(2,cons(LNIL))的最后一個元素為1。

通過以上歸結(jié)過程，我們能夠看出，該方法求解長表的最后一個元素的方法是，每次將長表去掉第一個元素，直到最后得到了只有*

個元素的表，該元素就是長表的最后一個元素。

第12題

答：我們用Skier(x)表示x是滑雪運動員，Alpinist(x)表示x是登山運動員，Alpine(x)表示x是Alpine俱樂部的成員。

問題用謂詞公式表示如下：

已知：

(1)Alpine(Tony)

(2)Alpine(Mike)

(3)Alpine(John)

(4)(x){Alpine(x)—>[Skier(x)VAlpinist(x)])

(5)(x){Alpinist(x)—>-Like(x,Rain)}

(6)(x){-Like(x,Snow)—Skicr(x)}

(7)(x){Like(Tony,x)^-Like(Mike,x)}

(8)(x){-Like(Tony,x)—>Like(Mike,x)}

(9)Like(Tony,Snow)

(10)Like(Tony,Rain)

目標(biāo):(vx)(Alpine(x)AAlpinist(x)A-Skicr(x))

化子句集：

(I)Alpine(Tony)

(2)Alpinc(Mikc)

(3)Alpine(John)

(4)(x){Alpine(x)—>[Skier(x)VAlpinist(x)]}=(x){-Alpine(x)V[Skicr(x)VAlpinist(x)])=>~Alpine(x)VSkier(x)VAlpinist(x)

(5)(x){Alpinist(x)—>-Like(x,Rain))=(x){-Alpinist(x)V-Like(x,Rain))=>~Alpinist(x)V-Like(x,Rain)

(6)(x){?Like(x,Snow)-?Skier(x)}=(x){Like(x,Snow)V-Skier(x)}=>Like(x,Snow)V-Skier(x)

(7)(x){Likc(Tony,x)—?Likc(Mikc,x)}=(x){-Likc(Tony,x)V~Likc(Mikc,x)}=>-Like(Tony,x)V-Like(Mikc,x)

(8)(x){-Like(Tony,x)—>Like(Mike,x)}=(x){Like(Tony,x)VLike(Mike,x))=>Like(Tony,x)VLike(Mike,x)

(9)Like(Tony,Snow)(10