第一章課后習(xí)題答案第1題答： 1，綜合數(shù)據(jù)庫定義三元組：（m, c, b） 其中：，表示傳教士在河左岸的人數(shù)。，表示野人在河左岸的認(rèn)輸。，b=1，表示船在左岸，b=0，表示船在右岸。2，規(guī)則集 規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法： 按每次渡河的人數(shù)分別寫出每一個(gè)規(guī)則，共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八種渡河的可能（其中(x y)表示x個(gè)傳教士和y個(gè)野人上船渡河），因此共有16個(gè)規(guī)則（從左岸到右岸、右岸到左岸各八個(gè)）。注意：這里沒有(1 2)，因?yàn)樵摻M合在船上的傳教士人數(shù)少于野人人數(shù)。規(guī)則集如下：r1：IF (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-1, c-1, 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)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 (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ī)則集綜合在一起，簡(jiǎn)化表示。規(guī)則集如下：r1：IF (m, c, 1) and 0= j or i=0) THEN (m-i, c-j, 0)r2：IF (m, c, 0) and 0= j or i=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)前水量。0=L2=2，表示容量為2升的壺的當(dāng)前水量。2，規(guī)則集r1：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) and L5+L25 THEN (5, L5+L2-5) /* L2到入L5中 */ r7：IF (L5, L2) and L5+L25 THEN (L5+L2-2, 2) /* L5到入L2中 */3，初始狀態(tài)：(5, 0) 4，結(jié)束條件：(x, 1)，其中x表示不定。當(dāng)然結(jié)束條件也可以寫成：(0, 1) 第3題答： 1，綜合數(shù)據(jù)庫定義三元組：(A, B, C) 其中A, B, C分別表示三根立柱，均為表，表的元素為1N之間的整數(shù)，表示N個(gè)不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個(gè)元素表示立柱最上面的柱子，其余類推。2，規(guī)則集為了方便表示規(guī)則集，引入以下幾個(gè)函數(shù)：first(L)：取表的第一個(gè)元素，對(duì)于空表，first得到一個(gè)很大的大于N的數(shù)值。tail(L)：取表除了第一個(gè)元素以外，其余元素組成的表。cons(x, L)：將x加入到表L的最前面。規(guī)則集：r1: 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ī)模： 每一個(gè)盤子都有三中選擇：在A上、或者在B上、或者在C上，共N個(gè)盤子，所以共有種可能。即問題的狀態(tài)規(guī)模為。 第4題答： 1，綜合數(shù)據(jù)庫定義5元組：（M, B, Box, On, H）其中：M：猴子的位置 B：香蕉的位置Box：箱子的位置On=0：猴子在地板上 On=1：猴子在箱子上 H=0：猴子沒有抓到香蕉 H=1：猴子抓到了香蕉 2，規(guī)則集r1: 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, 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,x0,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表示對(duì)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)rule(D)其中rule(D)表示可應(yīng)用于D的規(guī)則集合。由于R是R的逆，所以R應(yīng)用于D后，得到數(shù)據(jù)庫D。同樣由可交換系統(tǒng)的性質(zhì)，有： rule(D)rule(D)綜合上述兩個(gè)式子，有rule(D)rule(D)。 第8題答： 說明一個(gè)產(chǎn)生式系統(tǒng)是可交換的，就是要證明該產(chǎn)生式系統(tǒng)滿足可交換產(chǎn)生式系統(tǒng)的三條性質(zhì)。（1）該產(chǎn)生式系統(tǒng)以整數(shù)的集合為綜合數(shù)據(jù)庫，其規(guī)則是將集合中的兩個(gè)整數(shù)相乘后加入到數(shù)據(jù)庫中。由于原來數(shù)據(jù)庫是新數(shù)據(jù)庫的子集，所以原來的規(guī)則在新數(shù)據(jù)庫中均可以使用。所以滿足可交換產(chǎn)生式系統(tǒng)的第一條性質(zhì)。（2）該產(chǎn)生式系統(tǒng)以某個(gè)整數(shù)的子集的出現(xiàn)為目標(biāo)條件，由于規(guī)則執(zhí)行的結(jié)果只是向數(shù)據(jù)庫中添加數(shù)據(jù)，如果原數(shù)據(jù)庫中已經(jīng)滿足目標(biāo)了，即出現(xiàn)了所需要的整數(shù)子集，規(guī)則的執(zhí)行結(jié)果不會(huì)破壞該整數(shù)子集的出現(xiàn)，因此新的數(shù)據(jù)庫仍然會(huì)滿足目標(biāo)條件。滿足可交換產(chǎn)生式系統(tǒng)的第二個(gè)性質(zhì)。 （3）設(shè)D是該產(chǎn)生式系統(tǒng)的一個(gè)綜合數(shù)據(jù)庫。對(duì)D施以一個(gè)規(guī)則序列后，得到一個(gè)新的數(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)，也與1中其他的規(guī)則的執(zhí)行無關(guān)。所以可以認(rèn)為，先將R1中所有的規(guī)則對(duì)D應(yīng)用，然后再按照原來的次序應(yīng)用R2中的規(guī)則。因此對(duì)于本題的情況，這樣得到的綜合數(shù)據(jù)庫與D是相同的。而由于R1中一條規(guī)則的執(zhí)行與其他的規(guī)則無關(guān)，所以R1中規(guī)則的執(zhí)行順序不會(huì)影響到最終的結(jié)果。因此滿足可交換產(chǎn)生式系統(tǒng)的第三個(gè)條件。因此這樣一個(gè)產(chǎn)生式系統(tǒng)是一個(gè)可交換的產(chǎn)生式系統(tǒng)。第二章 課后習(xí)題第1題答： 為了方便起見，我們用(AB)()()這樣的表表示一個(gè)狀態(tài)。這樣得到搜索圖如下： 第2題提示：可定義h為：hB右邊的W的數(shù)目設(shè)j節(jié)點(diǎn)是i節(jié)點(diǎn)的子節(jié)點(diǎn)，則根據(jù)走法不同，h(i)-h(j)的值和C(i, j)分為如下幾種情況：（1）B或W走到了相鄰的一個(gè)空格位置，此時(shí)： h(i)-h(j)=0, C(i,j)=1；（2）W跳過了1或2個(gè)W，此時(shí) h(i)-h(j)=0, C(i,j)=1或2； （3）W向右跳過了一個(gè)B（可能同時(shí)包含一個(gè)W），此時(shí)： h(i)-h(j)=-1, C(i,j)=1或2；（4）W向右跳過了兩個(gè)B，此時(shí)： h(i)-h(j)=-2, C(i,j)=2； （5）W向左跳過了一個(gè)B（可能同時(shí)包含一個(gè)W），此時(shí)： h(i)-h(j)=1, C(i,j)=1或2； （6）W向左跳過了兩個(gè)B，此時(shí)： h(i)-h(j)=2, C(i,j)=2； （7）B跳過了1或2個(gè)B，此時(shí) h(i)-h(j)=0, C(i,j)=1或2； （8）B向右跳過了一個(gè)W（可能同時(shí)包含一個(gè)B），此時(shí)： h(i)-h(j)=1, C(i,j)=1或2；（9）B向右跳過了兩個(gè)W，此時(shí)： h(i)-h(j)=2, C(i,j)=2；（10）B向左跳過了一個(gè)W（可能同時(shí)包含一個(gè)B），此時(shí)： h(i)-h(j)=-1, C(i,j)=1或2； （11）B向左跳過了兩個(gè)W，此時(shí)： h(i)-h(j)=-2, C(i,j)=2；縱上所述，無論是哪一種情況，具有:h(i)-h(j)C(i,j)且容易驗(yàn)證h(t)=0，所以該h是單調(diào)的。由于h滿足單調(diào)條件，所以也一定有h(n)h*(n)，即滿足A*條件。 第3題答： 定義h1=n*k，其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小值。 h2，其中n是還未走過的城市數(shù)，ki是還未走過的城市間距離中n個(gè)最小的距離。 顯然這兩個(gè)h函數(shù)均滿足A*條件。 第4題提示：對(duì)于四皇后問題，如果放一個(gè)皇后的耗散值為1的話，則任何一個(gè)解的耗散值都是4。因此如果h是對(duì)該耗散值的估計(jì)，是沒有意義的。對(duì)于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對(duì)找到解的可能性的評(píng)價(jià)。比如像課上講到的，利用一個(gè)位置放皇后后，消去的對(duì)角線的長(zhǎng)度來進(jìn)行評(píng)價(jià)。第5題答： 定義h1=M+C-2B，其中M，C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。B1表示船在左岸，B0表示船在右岸。也可以定義h2=M+C。h1是滿足A*條件的，而h2不滿足。要說明h(n)M+C不滿足A*條件是很容易的，只需要給出一個(gè)反例就可以了。比如狀態(tài)(1, 1, 1)，h(n)=M+C=1+1=2，而實(shí)際上只要一次擺渡就可以達(dá)到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。下面我們來證明h(n)M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個(gè)人將船送回來。這樣，船一個(gè)來回可以運(yùn)過河2人，而船仍然在左岸。而最后剩下的三個(gè)人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡次。其中分子上的3表示剩下三個(gè)留待最后一次運(yùn)過去。除以2是因?yàn)橐粋€(gè)來回可以運(yùn)過去2人，需要個(gè)來回，而來回?cái)?shù)不能是小數(shù)，需要向上取整，這個(gè)用符號(hào)表示。而乘以2是因?yàn)橐粋€(gè)來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的1，則表示將剩下的3個(gè)運(yùn)過去，需要一次擺渡。化簡(jiǎn)有：再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個(gè)人將船運(yùn)到左岸。因此對(duì)于狀態(tài)(M，C，0)來說，其所需要的最少擺渡數(shù)，相當(dāng)于船在左岸時(shí)狀態(tài)(M+1，C，1)或(M，C+1，1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因此所需要的最少擺渡數(shù)為：(M+C+1)-2+1 。其中(M+C+1)的1表示送船回到左岸的那個(gè)人，而最后邊的1，表示送船到左岸時(shí)的一次擺渡。化簡(jiǎn)有：(M+C+1)-2+1=M+C。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個(gè)式子表示為：M+C-2B。其中B1表示船在左岸，B0表示船在右岸。 由于該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制條件時(shí)，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。第6題答：題目的另一個(gè)說法是：當(dāng)A*結(jié)束時(shí)，OPEN表中任何一個(gè)具有f(n)f*(s)的節(jié)點(diǎn)都被擴(kuò)展了。用反證法證明。假設(shè)在A*結(jié)束的時(shí)候，OPEN表中有一個(gè)節(jié)點(diǎn)n沒有被擴(kuò)展，且f(n)f*(s)。A*算法每次從OPEN表中取出f值最小的節(jié)點(diǎn)擴(kuò)展，當(dāng)該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)，算法結(jié)束。并且由可采納性定理，知道這時(shí)A*找到了從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑，即f(t)=f*(s)。如果這時(shí)OPEN中存在f(n)f*(s)的節(jié)點(diǎn)n，由于f(n)f*(s)的節(jié)點(diǎn)，不會(huì)被A*所擴(kuò)展。所以如果從OPEN表中去掉f(n)f*(s)的節(jié)點(diǎn)，不會(huì)影響A*的可采納性。而F是f*(s)的上界范圍，因此去掉f(n)F的節(jié)點(diǎn)也同樣不會(huì)影響A*的可采納性。第8題提示：對(duì)于8數(shù)碼問題，逆向搜索和正向搜索是完全一樣的，只是把目標(biāo)狀態(tài)和初始狀態(tài)對(duì)調(diào)就可以了。第9題提示：在搜索期間改善h函數(shù)，是一種動(dòng)態(tài)改變h函數(shù)的方法。像改進(jìn)的A*算法中，對(duì)NEST中的節(jié)點(diǎn)按g值的大小選擇待擴(kuò)展的節(jié)點(diǎn)，相當(dāng)于令這些節(jié)點(diǎn)的h0，就是動(dòng)態(tài)修改h函數(shù)的一種方法。由定理6，當(dāng)h滿足單調(diào)條件時(shí)，A*所擴(kuò)展的節(jié)點(diǎn)序列，其f是非遞減的。對(duì)于任何節(jié)點(diǎn)i，j，如果j是i的子節(jié)點(diǎn)，則有f(i)f(j)。利用該性質(zhì)，我們可以提出另一種動(dòng)態(tài)修改h函數(shù)的方法：f(j)=max(f(i), f(j)以f(j)作為節(jié)點(diǎn)j的f值。f值的改變，隱含了h值的改變。當(dāng)h不滿足單調(diào)條件時(shí)，經(jīng)過這樣修正后的h具有一定的單調(diào)性質(zhì)，可以減少重復(fù)節(jié)點(diǎn)的可能性。第10題提示：很多知識(shí)對(duì)求解問題有好處，這些知識(shí)并不一定要寫成啟發(fā)函數(shù)的形式，很多情況下，也不一定能清晰的寫成一個(gè)函數(shù)的形式。為了敘述方便，我們將兩個(gè)相對(duì)的扇區(qū)稱為相對(duì)扇區(qū)，圖中陰影部分的扇區(qū)稱為陰影扇區(qū)，非陰影部分的扇區(qū)稱為非陰影扇區(qū)。 由題意，在目標(biāo)狀態(tài)下，一個(gè)扇區(qū)的數(shù)字之和等于12，一個(gè)相對(duì)扇區(qū)的數(shù)字之和等于24，而一個(gè)陰影扇區(qū)或者非陰影扇區(qū)的數(shù)字之和為48。為此，我們可以將目標(biāo)進(jìn)行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48（這時(shí)非陰影部分的數(shù)字和也一定為48）。為了這個(gè)目標(biāo)我們可以通過每次轉(zhuǎn)動(dòng)圓盤45o實(shí)現(xiàn)。在第一個(gè)目標(biāo)被滿足的情況下，我們?cè)倏紤]第二個(gè)目標(biāo)：每一個(gè)相對(duì)扇區(qū)的數(shù)字和為24。在實(shí)現(xiàn)這個(gè)目標(biāo)的過程中，我們希望不破壞第一個(gè)目標(biāo)。為此我們采用轉(zhuǎn)動(dòng)90o的方式實(shí)現(xiàn)，這樣即可以調(diào)整相對(duì)扇區(qū)的數(shù)字和，又不破壞第一個(gè)目標(biāo)。在第二個(gè)目標(biāo)實(shí)現(xiàn)之后，我們就可以實(shí)現(xiàn)最終目標(biāo)：扇區(qū)內(nèi)的數(shù)字和為12。同樣我們希望在實(shí)現(xiàn)這個(gè)目標(biāo)的時(shí)候，不破壞前兩個(gè)目標(biāo)。為此我們采用轉(zhuǎn)動(dòng)180o的方式實(shí)現(xiàn)。這樣同樣是即可以保證前兩個(gè)目標(biāo)不被破壞，又可以實(shí)現(xiàn)第三個(gè)目標(biāo)。 經(jīng)過這樣的分析以后，我們發(fā)現(xiàn)該問題就清晰多了。當(dāng)然，是否每一個(gè)第一、第二個(gè)目標(biāo)的實(shí)現(xiàn)，都能夠?qū)崿F(xiàn)第三個(gè)目標(biāo)呢？有可能不一定。在這種情況下，就需要在發(fā)現(xiàn)第三個(gè)目標(biāo)不能實(shí)現(xiàn)時(shí)，重新試探其他的第一、第二個(gè)目標(biāo)。 第三章課后習(xí)題答案第1題答：此題要求按照課中例題的方式，給出算法，以下是每個(gè)循環(huán)結(jié)束時(shí)的搜索圖。上面這種做法比較簡(jiǎn)單，也可以如下做：第2題從該搜索圖可以看出，無論先走者選擇哪個(gè)走步，后走者都可以走到標(biāo)記為A的節(jié)點(diǎn)，該節(jié)點(diǎn)只剩下一枚錢幣，所以先走者必輸。 對(duì)于一般的具有n個(gè)錢幣的情況，當(dāng)n4m1時(shí)，后走者存在取勝策略。因?yàn)楹笞哒呖梢愿鶕?jù)先走者的走法，選擇自己的走法，使得雙方拿走的錢幣數(shù)為4，這樣經(jīng)過m個(gè)輪回后，共拿走了4m個(gè)錢幣，只剩下了一枚錢幣，而此時(shí)輪到先走者走棋。所以在這種情況下，后走者存在取勝的策略。 對(duì)于錢幣數(shù)不等于4m1的情況，先走者可以根據(jù)實(shí)際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為4m1個(gè)，此時(shí)先走者相當(dāng)于4m1個(gè)錢幣時(shí)的后走者了。因此在這種情況下，先走者存在獲勝的策略。第3題答：第四章課后習(xí)題答案第1題答：（1）(x)P(x)P(x)(x)P(x)P(x)P(x)P(x)（2）(x)P(x)(x)P(x) (x)P(x)(x)P(x) (x)P(x)(y)P(y)(x)(y)P(x)P(y) P(x)P(f(a) （3）(x)P(x)(y)P(y)P(f(x，y)(y)Q(x，y)P(y)(x)P(x)(y)P(y)P(f(x，y)(y)Q(x，y)P(y)(x)P(x)(y)P(y)P(f(x，y)(y)Q(x，y)P(y)(x)P(x)(y)P(y)P(f(x，y)(z)Q(x，z)P(z)(x)P(x)(y)P(y)P(f(x，y)(z)Q(x，z)P(z)(x)P(x)(y)P(y)P(f(x，y)(z)Q(x，z)P(z) (x)(y)(z)P(x)P(y)P(f(x，y)Q(x，z)P(z)(x)(y)(z)P(x)P(y)Q(x，z)P(z)P(f(x，y)Q(x，z)P(z) P(a)P(b)Q(a，z)P(z)P(f(a，b)Q(a，z)P(z)P(a), P(b)Q(a，z1)P(z1), P(f(a，b)Q(a，z2)P(z2) （4）(x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(x)(y)P(x，y)S(x，y) (x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(x)(y)P(x，y)S(x，y) (x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(u)(v)P(u，v)S(u，v)(x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(u)(v)P(u，v)S(u，v) (x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(u)(v)P(u，v)S(u，v) (x)(y)(u)(v)P(x，y)Q(y，x)Q(y，x)S(x，y)P(u，v)S(u，v) (x)(y)(u)(v)P(x，y)Q(y，x)P(x，y)S(x，y)Q(y，x)S(x，y)P(u，v)S(u，v) (x)(y)(u)(v)P(x，y)Q(y，x)P(u，v)S(u，v)P(x，y)S(x，y)P(u，v)S(u，v)Q(y，x)S(x，y)P(u，v)S(u，v)P(a，y)Q(y，a)P(f(y)，v)S(f(y)，v)P(a，y)S(a，y)P(f(y)，v)S(f(y)，v)Q(y，a)S(a，y)P(f(y)，v)S(f(y)，v) P(a，y1)Q(y1，a)P(f(y1)，v)S(f(y1)，v), P(a，y2)S(a，y2)P(f(y2)，v2)S(f(y2)，v2), Q(y3，a)S(a，y3)P(f(y3)，v3)S(f(y3)，v3) 第2題答：設(shè)有兩個(gè)置換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) 在合一時(shí)，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）一個(gè)是謂詞P，一個(gè)是P的反，不能合一。 （3）P（f（A），x），P（x，A）在合一的過程中，x置換為f(A)，而f(A)與A不能合一。 第6題答： （1）（x）P（x）P（A）P（x）P（B）目標(biāo)取反化子句集：（x）P（x）P（A）P（x）P（B） （x）P（x）P（A）P（x）P（B） （x）P（x）P（A）P（x）P（B） （x）P（x）P（A）P（x）P（x）P（A）P（B）（x）P（x）P（A）P（x）P（x）P（B）P（A）P（B）P（x）P（A）P（x）P（x）P（B）P（A）P（B）得子句集：1, P(x1)2, P(A)Px2 3, P(x3)P(B)4, P(A)P(B)（2）（z）Q（z）P（z）（x）Q（x）P（A）Q（x）P（B）目標(biāo)取反化子句集：(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(z)(x)Q(z)P(z)Q(x)P(A)Q(x)P(B)(z)(x)Q(z)P(z)Q(x)Q(x)P(B)P(A)Q(x)P(A)P(B)Q(z)P(z)Q(x)Q(x)P(B)P(A)Q(x)P(A)P(B) 得子句集： 1, Q(z)P(z)2, Q(x2) 3, Q(x3)P(B) 4, P(A)Q(x4) 5, P(A)P(B) （3）（x）（y）P（f（x）Q（f（B）P（f（A）P（y）Q（y）目標(biāo)取反化子句集：(x)(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) (x)(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) ( x)( y)P(f(x)Q(f(B)P(f(A)P(y)Q(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) 得子句集：1，P(f(x1)2，Q(f(B) 3，P(f(A)P(y3)Q(y3)（4）（x）（y）P（x，y）（y）（x）P（x，y）目標(biāo)取反化子句集：(x)(y)P(x，y)(y)(x)P(x，y)(x)(y)P(x，y)(y)(x)P(x，y) (x)(y)P(x，y)(v)(u)P(u，v)(x)(y)P(x，y)(v)(u)P(u，v) (x)(y)(v)(u)P(x，y)P(u，v)P(a，y)P(u，f(y)得子句集：1，P(a，y1) 2，P(u，f(y2) （5）（x）P（x）Q（A）Q（B）（x）P（x）Q（x） 目標(biāo)取反化子句集：(x)P(x)Q(A)Q(B)(x)P(x)Q(x)(x)P(x)Q(A)Q(B)(x)P(x)Q(x) (x)P(x)Q(A)Q(B)(x)P(x)Q(x)(x)P(x)Q(A)Q(B)(y)P(y)Q(y) (x)(y)P(x)Q(A)Q(B)P(y)Q(y) P(x)Q(A)Q(B)P(y)Q(y)得子句集：1，P(x) 2，Q(A)Q(B) 3，P(y)Q(y) 第7題答： （1）將（x）P（x）取反化為子句：（x）P（x） =（ x）P（x）與條件P（A1）P（A2）合在一起得子句集：P（x）, P（A1）P（A2）所以，公式（x）P（x）是P（A1）P（A2）的邏輯推論。（2）對(duì)于（x）P（x）的Skolem形，即P（A），取反后為P（A），與條件P（A1）P（A2）合在一起得子句集：P（A）, P（A1）P（A2） 該子句集不能進(jìn)行歸結(jié)，故P（A）不是P（A1）P（A2）的邏輯推論。 第8題答： 該問題用謂詞公式描述如下： 已知： （1）(x)Food(x)Like(John, x)（2）Food(Apple)（3）(x)(y)Eat(y, x)Kill(x, y)Food(x) （4）Eat(Bill, Peanut)Kill(Penut, Bill) （5）(x)Eat(Bill, x)Eat(Sue, x)目標(biāo)1：Like(John, Peanut)目標(biāo)2：(x)Food(x)Eat(Sue, x) 已知條件化子句集： （1）(x)Food(x)Like(John, x)= (x)Food(x)Like(John, x) = Food(x)Like(John, x) （2）Food(Apple) （3）(x)(y)Eat(y, x)Kill(x, y)Food(x)= (x)(y)Eat(y, x)Kill(x, y)Food(x) = (x)(y)Eat(y, x)Kill(x, y)Food(x) = Eat(y, x)Kill(x, y)Food(x) （4）Eat(Bill, Peanut)Kill(Penut, Bill)= Eat(Bill, Peanut), Kill(Penut, Bill) （5）(x)Eat(Bill, x)Eat(Sue, x)= (x)Eat(Bill, x)Eat(Sue, x) = Eat(Bill, x)Eat(Sue, x) 目標(biāo)1取反化子句集：Like(John, Peanut) 目標(biāo)2取反化子句集：(x)Food(x)Eat(Sue, x) = (x)Food(x)Eat(Sue, x) = Food(x)Eat(Sue, x) 對(duì)于目標(biāo)1，經(jīng)變量換名后，得子句集：Food(x1)Like(John, x1)，F(xiàn)ood(Apple)，Eat(y2, x2)Kill(x2, y2)Food(x2)，Eat(Bill, Peanut), Kill(Penut, Bill), Eat(Bill, x3)Eat(Sue, x3), Like(John, Peanut) 歸結(jié)樹如下：對(duì)于目標(biāo)2，經(jīng)變量換名后，得子句集：Food(x1)Like(John, x1)，F(xiàn)ood(Apple)，Eat(y2, x2)Kill(x2, y2)Food(x2)，Eat(Bill, Peanut), Kill(Penut, Bill), Eat(Bill, x3)Eat(Sue, x3), Food(x)Eat(Sue, x) 歸結(jié)樹如下：修改證明樹如下：得到解答為：Food(Peanut)Eat(Sue, Peanut) 第9題答： 該歸結(jié)過程存在錯(cuò)誤。其原因是由于不同的子句用了相同的變量名引起的。如上圖中A、B兩個(gè)子句的歸結(jié)，兩個(gè)子句中的y應(yīng)該是不同的變量，在歸結(jié)時(shí)，如果用不同的變量分別表示，就不會(huì)出現(xiàn)這樣的問題了。比如B中的y用y1代替，則歸結(jié)結(jié)果如下： 第10題答： 化子句集：（u）LAST（cons（u，NIL），u） = LAST（cons（u，NIL），u）（x）（y）（z）（LAST（y，z）LAST（cons（x，y），z）= （x）（y）（z）（LAST（y，z）LAST（cons（x，y），z）= LAST（y，z）LAST（cons（x，y），z）目標(biāo)取反： （v）LAST（cons（2，cons（1，NIL），v）=（v）LAST（cons（2，cons（1，NIL），v）= LAST（cons（2，cons（1，NIL），v）經(jīng)變量換名后，得子句集：LAST（cons（u，NIL），u）, LAST（y，z）LAST（cons（x，y），z）, LAST（cons（2，cons（1，NIL），v）歸結(jié)樹如下：修改證明樹：得到解答：LAST(cons(2，cons(1，NIL)，1)，表cons(2，cons(1，NIL)的最后一個(gè)元素為1。通過以上歸結(jié)過程，我們可以看出，該方法求解長(zhǎng)表的最后一個(gè)元素的方法是，每次將長(zhǎng)表去掉第一個(gè)元素，直到最后得到了只有一個(gè)元素的表，該元素就是長(zhǎng)表的最后一個(gè)元素。 第12題答： 我們用Skier(x)表示x是滑雪運(yùn)動(dòng)員，Alpinist(x)表示x是登山運(yùn)動(dòng)員，Alpine(x)表示x是Alpine俱樂部的成員。問題用謂詞公式表示如下：已知：(1) Alpine(Tony) (2) Alpine(Mike) (3) Alpine(John) (4) ( x)Alpine(x)Skier(x)Alpinist(x) (5) ( x)Alpinist(x)Like(x, Rain)(6) ( x)Like(x, Snow) Skier(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)Alpinist(x)Skier(x) 化子句集：(1) Alpine(Tony)(2) Alpine(Mike) (3) Alpine(John) (4) ( x)Alpine(x)Skier(x)Alpinist(x) = ( x)Al