人工智能課后答案

答案第一章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答：1，綜合數(shù)據(jù)庫定義三元組：（m,c,b）其中：，表示傳教士在河左岸的人數(shù)。，表示野人在河左岸的認(rèn)輸。，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)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ī)則集綜合在一起，簡化表示。規(guī)則集如下：r1：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,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)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到入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分別表示三根立柱，均為表，表的元素為1～N之間的整數(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),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個盤子，所以共有種可能。即問題的狀態(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）其中x1～x4為變量。第5題答：1，綜合數(shù)據(jù)庫定義四元組：（x,y,z,n）其中x,y,x∈[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ù)部分。然后根據(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ù)庫D。同樣由可交換系統(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ī)則是將集合中的兩個整數(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)，也與Ｒ1中其他的規(guī)則的執(zhí)行無關(guān)。所以可以認(rè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)。第1題答：為了方便起見，我們用((AB)()())這樣的表表示一個狀態(tài)。這樣得到搜索圖如下：第2題提示：可定義h為：h＝B右邊的W的數(shù)目設(shè)j節(jié)點是i節(jié)點的子節(jié)點，則根據(jù)走法不同，h(i)-h(j)的值和C(i,j)分為如下幾種情況：（1）B或W走到了相鄰的一個空格位置，此時：h(i)-h(j)=0,C(i,j)=1；（2）W跳過了1或2個W，此時h(i)-h(j)=0,C(i,j)=1或2；（3）W向右跳過了一個B（可能同時包含一個W），此時：h(i)-h(j)=-1,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)=1,C(i,j)=1或2；（6）W向左跳過了兩個B，此時：h(i)-h(j)=2,C(i,j)=2；（7）B跳過了1或2個B，此時h(i)-h(j)=0,C(i,j)=1或2；（8）B向右跳過了一個W（可能同時包含一個B），此時：h(i)-h(j)=1,C(i,j)=1或2；（9）B向右跳過了兩個W，此時：h(i)-h(j)=2,C(i,j)=2；（10）B向左跳過了一個W（可能同時包含一個B），此時：h(i)-h(j)=-1,C(i,j)=1或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)≤h*(n)，即滿足A*條件。第3題答：定義h1=n*k，其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小值。h2＝，其中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*條件是很容易的，只需要給出一個反例就可以了。比如狀態(tài)(1,1,1)，h(n)=M+C=1+1=2，而實際上只要一次擺渡就可以達到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。下面我們來證明h(n)＝M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運到右岸，然后再有一個人將船送回來。這樣，船一個來回可以運過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們?nèi)繌淖蟀哆\到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡次。其中分子上的"－3"表示剩下三個留待最后一次運過去。除以"2"是因為一個來回可以運過去2人，需要個來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個用符號表示。而乘以"2"是因為一個來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的"＋1"，則表示將剩下的3個運過去，需要一次擺渡?；営校涸倏紤]船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運到左岸。因此對于狀態(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+1。其中(M+C+1)的"＋1"表示送船回到左岸的那個人，而最后邊的"＋1"，表示送船到左岸時的一次擺渡?；営校?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é)點擴展，當(dāng)該節(jié)點是目標(biāo)節(jié)點時，算法結(jié)束。并且由可采納性定理，知道這時A*找到了從初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，即f(t)=f*(s)。如果這時OPEN中存在f(n)<f*(s)的節(jié)點n，由于f(n)<f(t)，則這時A*算法應(yīng)選擇n擴展，而不是目標(biāo)t，與A*已經(jīng)結(jié)束矛盾。第7題答：因為A*選作擴展的任何一個節(jié)點n，均有f(n)≤f*(s)，因此f(n)>f*(s)的節(jié)點，不會被A*所擴展。所以如果從OPEN表中去掉f(n)>f*(s)的節(jié)點，不會影響A*的可采納性。而F是f*(s)的上界范圍，因此去掉f(n)>F的節(jié)點也同樣不會影響A*的可采納性。第8題提示：對于8數(shù)碼問題，逆向搜索和正向搜索是完全一樣的，只是把目標(biāo)狀態(tài)和初始狀態(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題提示：很多知識對求解問題有好處，這些知識并不一定要寫成啟發(fā)函數(shù)的形式，很多情況下，也不一定能清晰的寫成一個函數(shù)的形式。為了敘述方便，我們將兩個相對的扇區(qū)稱為相對扇區(qū)，圖中陰影部分的扇區(qū)稱為陰影扇區(qū)，非陰影部分的扇區(qū)稱為非陰影扇區(qū)。由題意，在目標(biāo)狀態(tài)下，一個扇區(qū)的數(shù)字之和等于12，一個相對扇區(qū)的數(shù)字之和等于24，而一個陰影扇區(qū)或者非陰影扇區(qū)的數(shù)字之和為48。為此，我們可以將目標(biāo)進行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48（這時非陰影部分的數(shù)字和也一定為48）。為了這個目標(biāo)我們可以通過每次轉(zhuǎn)動圓盤45o實現(xiàn)。在第一個目標(biāo)被滿足的情況下，我們再考慮第二個目標(biāo)：每一個相對扇區(qū)的數(shù)字和為24。在實現(xiàn)這個目標(biāo)的過程中，我們希望不破壞第一個目標(biāo)。為此我們采用轉(zhuǎn)動90o的方式實現(xiàn)，這樣即可以調(diào)整相對扇區(qū)的數(shù)字和，又不破壞第一個目標(biāo)。在第二個目標(biāo)實現(xiàn)之后，我們就可以實現(xiàn)最終目標(biāo)：扇區(qū)內(nèi)的數(shù)字和為12。同樣我們希望在實現(xiàn)這個目標(biāo)的時候，不破壞前兩個目標(biāo)。為此我們采用轉(zhuǎn)動180o的方式實現(xiàn)。這樣同樣是即可以保證前兩個目標(biāo)不被破壞，又可以實現(xiàn)第三個目標(biāo)。經(jīng)過這樣的分析以后，我們發(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é)束時的搜索圖。上面這種做法比較簡單，也可以如下做：第2題答：從該搜索圖可以看出，無論先走者選擇哪個走步，后走者都可以走到標(biāo)記為A的節(jié)點，該節(jié)點只剩下一枚錢幣，所以先走者必輸。對于一般的具有n個錢幣的情況，當(dāng)n＝4×m＋1時，后走者存在取勝策略。因為后走者可以根據(jù)先走者的走法，選擇自己的走法，使得雙方拿走的錢幣數(shù)為4，這樣經(jīng)過m個輪回后，共拿走了4×m個錢幣，只剩下了一枚錢幣，而此時輪到先走者走棋。所以在這種情況下，后走者存在取勝的策略。對于錢幣數(shù)不等于4×m＋1的情況，先走者可以根據(jù)實際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為4×m＋1個，此時先走者相當(dāng)于4×m＋1個錢幣時的后走者了。因此在這種情況下，先走者存在獲勝的策略。第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è)有兩個置換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,x)要與f(y,f(y,a))進行合一，x置換成y后，y要與f(y,a)進行合一，出現(xiàn)了嵌套的情況，所以不能進行合一。（2）{~P（A），P（x）}一個是謂詞P，一個是P的反，不能合一。（3）{P（f（A），x），P（x，A）}在合一的過程中，x置換為f(A)，而f(A)與A不能合一。第5題答：略第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)∨P{x2}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）對于（x）P（x）的Skolem形，即P（A），取反后為~P（A），與條件[P（A1）∨P（A2）]合在一起得子句集：{~P（A）,P（A1）∨P（A2）}該子句集不能進行歸結(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)對于目標(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é)樹如下：對于目標(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é)過程存在錯誤。其原因是由于不同的子句用了相同的變量名引起的。如上圖中A、B兩個子句的歸結(jié)，兩個子句中的y應(yīng)該是不同的變量，在歸結(jié)時，如果用不同的變量分別表示，就不會出現(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))的最后一個元素為1。通過以上歸結(jié)過程，我們可以看出，該方法求解長表的最后一個元素的方法是，每次將長表去掉第一個元素，直到最后得到了只有一個元素的表，該元素就是長表的最后一個元素。第11題答：略第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)∨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){~Alpine(x)∨[Skier(x)∨Alpinist(x)]}=>~Alpine(x)∨Skier(x)∨Alpinist(x)(5)(x){Alpinist(x)→~Like(x,Rain)}=(x){~Alpinist(x)∨~Like(x,Rain)}=>~Alpinist(x)∨~Like(x,Rain)(6)(x){~Like(x,Snow)→~Skier(x)}=(x){Like(x,Snow)∨~Skier(x)}=>Like(x,Snow)∨~Skier(x)(7)(x){Like(Tony,x)→~Like(Mike,x)}=(x){~Like(Tony,x)∨~Like(Mike,x)}=>~Like(Tony,x)∨~Like(Mike,x)(8)(x){~Like(Tony,x)→Like(Mike,x)}=(x){Like(Tony,x)∨Like(Mike,x)}=>Like(Tony,x)∨Like(Mike,x)(9)Like(Tony,Snow)(10)Like(Tony,Rain)目標(biāo)取反：~(vx){Alpine(x)∧Alpinist(x)∧~Skier(x)}=(x){~Alpine(x)∨~Alpinist(x)∨Skier(x)}=>~Alpine(x)∨~Alpinist(x)∨Skier(x)經(jīng)變量換名后，得到子句集：{Alpine(Tony),Alpine(Mike),Alpine(John),~Alpine(x1)∨Skier(x1)∨Alpinist(x1),~Alpinist(x2)∨~Like(x2,Rain),Like(x3,Snow)∨~Skier(x3),~Like(Tony,x4)∨~Like(Mike,x4),Like(Tony,x5)∨Like(Mike,x5),Like(Tony,Snow),Like(Tony,Rain),~Alpine(x)∨~Alpinist(x)∨Skier(x)}歸結(jié)樹如下：第13題答：狀態(tài)草圖：知識的謂詞表示：(x)(y){[BIG(x)∧BLUE(x)]→ON(x,y)∧GREEN(y)}(x){[HEAVY(x)∧WOODEN(x)]→BIG(x)}(x){CLEAR(x)→BLUE(x)}(x){WOODEN(x)→BLUE(x)}目標(biāo)：(x)(y)GREEN(y)∧ON(x,y)對規(guī)則Skolem化，對目標(biāo)用對偶形式Skolem化后，整理得：事實：ONTABLE（A）CLEAR（E）ONTABLE（C）CLEAR（D）ON（D，C）HEAVY（D）ON（B，A）WOODEN（B）HEAVY（B）ON（E，B）規(guī)則：r1:[BIG(x1)∧BLUE(x1)]→ON(x1,f(x1))r2:[BIG(x2)∧BLUE(x2)]→GREEN(f(x2))r3:[HEAVY(x3)∧WOODEN(x3)]→BIG(x3)r4:CLEAR(x4)→BLUE(x4)r5:WOODEN(x5)→BLUE(x5)目標(biāo)：GREEN(y)∧ON(x,y)容易驗證，只有一個解圖是一致的，其合一復(fù)合為：{B/x,f(B)/y}帶入目標(biāo)公式，得到解答：GREEN(f(B))∧ON(B,f(B))其含義是，積木B在綠色積木上邊。這里的f(B)可以理解為B下面那個積木。書本第三章1．將下面的公式化成子句集～(((P∨～Q)→R)→(P∧R))2．命題是數(shù)理邏輯中常用的公式，試使用歸結(jié)法證明它們的正確性：a)P→(Q→P)b)(P→(Q→R))→((P→Q)→(P→R))c)(Q→～P)→((Q→P)→～Q)3．下列子句是否可以合一，如果可以，寫出最一般合一置換a)P(x,B,B)和P(A,y,z)b)P(g(f(v)),g(u))和P(x,x)c)P(x,f(x))和P(y,y)d)P(y,y,B)和P(z,x,z)4．解釋P(f(x,x),A)和P(f(y,f(y,A)),A)為什么不能合一5．將下列公式化為skolem子句形a)((x)P(x)∨(x)Q(x))→(x)(P(x)∨Q(x))b)(x)(P(x)→(y)((z)Q(x,y)→～(z)R(y,x)))c)(x)P(x)→(x)(((z)Q(x,z))∨(z)R(x,y,z))6．用歸結(jié)法證明：存在一個綠色物體，如果有如下條件存在：a)如果可以推動的物體是藍色的，那么不可以推動的物體是綠色的b)所有的物體或者是藍色的，或者是綠色的，但不能同時具有兩種顏色。c)如果存在一個不能推動的物體，那么所有的可推動的物體是藍色的。d)物體O1是可以推動的e)物體O2是不可以推動的7．設(shè)S={P(x),Q(f(x),y)}，試寫出H域上的元素，并寫出S的一個基例。答案第1題解：～(((P∨～Q)→R)→(P∧R))=((P∨～Q)→R)∧～(P∧R)=(～(P∨～Q)∨R)∧(～P∨～R)=(～P∨R)∧(Q∨R)∧(～P∨～R)建立子句集：S={～P∨R,Q∨R,～P∨～R}第2題解：1)要證明P→(Q→P)永真～（Q→P）＝～P∧Q建立子句集：S={～P,Q,P}進行歸結(jié)：Q～P,P□2)要證明(P→(Q→R))→((P→Q)→(P→R))永真即證明～((P→(Q→R))→((P→Q)→(P→R)))為永假。將其化為合取范式：～((P→(Q→R))→((P→Q)→(P→R)))=(P→(Q→R)∧～((P→Q)→(P→R))=(～P∨～Q∨R)∧(P→Q)∧～(P→R)=(～P∨～Q∨R)∧(～P∨Q)∧P∧～R建立子句集：S={～P∨～Q∨R,～P∨Q,P,～R}進行歸結(jié)：1)～P∨～Q∨R2)～P∨Q3)P4)～R5)Q（2）（3）歸結(jié)6)～Q∨R（1）（3）歸結(jié)7)R（5）（6）歸結(jié)8)□（4）（7）歸結(jié)3)要證明(Q→～P)→((Q→P)→～Q)為永真即證明～((Q→～P)→((Q→P)→～Q))為永假將其化為合取范式：～((Q→～P)→((Q→P)→～Q))=(Q→～P)∧(Q→P)∧Q=(～Q∨～P)∧(～Q∨P)∧Q建立子句集：S={～Q∨～P,～Q∨P,Q}進行歸結(jié)：(1)～Q∨～P(2)～Q∨P(3)Q(4)～P（1）（3）歸結(jié)(5)P（1）（2）歸結(jié)(6)□第3題解：1)P(x,B,B)和P(A,y,z)可以合一：Mgu={A/x,B/y,B/z}2)P(g(f(v)),g(u))和P(x,x)不可以合一3)P(x,f(x))和P(y,y)不可以合一4)P(y,y,B)和P(z,x,z)可以合一Mgu={B/x,B/y,B/z}第4題解：因為f(x,x)中的x在置換的時候必須保持相同的形式，因此無論怎么置換都不能置換出而第二式中f(y,f(y,A))的分層嵌套形式，因此兩個公式是不能合一的。第5題解：1)((