人工智能及其應用搜索推理技術修改.pptx

1、第三章 搜索推理技術 知識表示方法是問題求解所必需的。表示問題是為了進一步解決問題。從問題表示到問題的解決，有一個求解的過程 ，也就是搜索過程。在這一過程中，采用適當?shù)乃阉骷夹g，包括各種規(guī)則，過程和算法等推理技術，力求找到問題的解答。 本章首先介紹圖搜索策略的一般過程，接著討論一些早期的搜索技術或用于解決比較簡單的問題的搜索原理，然后研究一些比較新的能夠求解比較復雜問題的推理技術。13.1 圖搜索策略 圖搜索策略可以看成一種在圖中尋找路徑的方法。初始節(jié)點和目標節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一個數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。23.1

2、圖搜索策略 圖搜索(GRAPHSEARCH)的一般過程如下： (1) 建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN的未擴展節(jié)點表中（簡稱OPEN表）。(2) 建立一個叫做CLOSED的已擴展節(jié)點表（簡稱CLOSED表），其初始為空表。(3) LOOP：若OPEN表是空表，則失敗退出。(4) 選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點n，它是CLOSED表中節(jié)點的編號。(5) 若n為一目標節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設置) 33.1 圖搜索策略 圖搜索(GRAPHSEARC

3、H)的一般過程如下：(6) 擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。 (7) 對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設置一個通向n的指針。把M的這些成員加進OPEN表。對已經在OPEN或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。(8) 按某一任意方式或按某個探試值，重排OPEN表。(9) GO LOOP。 43.1 圖搜索策略 圖搜索過程框圖3.153.1 圖搜索策略 圖搜索算法中的

4、幾個重要名詞 1OPEN表 2CLOSED表 3搜索圖與搜索樹 此過程生成一個明確的圖G(稱為搜索圖)和一個G的子集T(稱為搜索樹)，樹T上的每個節(jié)點也在圖G中。搜索樹是由第7步中設置的指針來確定的。G中的每個節(jié)點(除S外)都有一個只指向G中一個父輩節(jié)點的指針，該父輩節(jié)點就指定為樹中那個節(jié)點的唯一父輩節(jié)點。63.1 圖搜索策略圖搜索方法的幾點分析： 圖搜索過程的第8步對OPEN表上的節(jié)點進行排序，以便能夠從中選出一個“最好”的節(jié)點作為第4步擴展用。這種排序可以是任意的即盲目的(屬于盲目搜索)，也可以用以后要討論的各種啟發(fā)思想或其它準則為依據(jù)(屬于啟發(fā)式搜索)。 每當被選作擴展的節(jié)點為目標節(jié)點時

5、，這一過程就宣告成功結束。這時，能夠重現(xiàn)從起始節(jié)點到目標節(jié)點的這條成功路徑，其辦法是從目標節(jié)點按指針向S返回追溯。當搜索樹不再剩有未被擴展的端節(jié)點時，過程就以失敗告終(某些節(jié)點最終可能沒有后繼節(jié)點，所以OPEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點出發(fā)，一定達不到目標節(jié)點。73.2 盲目搜索 盲目搜索又叫做無信息搜索 ，指無須重新安排OPEN表的搜索。它包括寬度優(yōu)先搜索，深度優(yōu)先搜索和等代價搜索等。一般只適用于求解比較簡單的問題。 83.2 盲目搜索 3.2.1寬度優(yōu)先搜索寬度優(yōu)先搜索(breadth-first search)的定義： 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點

6、的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-first search)，如圖3.2所示。從圖可見，這種搜索是逐層進行的；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。 93.2 盲目搜索 3.2.1寬度優(yōu)先搜索3.2寬度優(yōu)先搜索示意圖103.2 盲目搜索 3.2.1寬度優(yōu)先搜索寬度優(yōu)先搜索算法如下： (1) 把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2) 如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED擴展節(jié)點表中。(4) 擴展節(jié)點n。如果沒有后繼節(jié)點，則轉向上述第

7、(2)步。(5) 把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。(6) 如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉向第(2)步。113.2 盲目搜索 3.2.1寬度優(yōu)先搜索寬度優(yōu)先算法框圖3.3123.2 盲目搜索 3.2.1寬度優(yōu)先搜索例：把寬度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕似寰值膯栴}： 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠不會終止)。133.2 盲目

8、搜索 3.2.1寬度優(yōu)先搜索圖 3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹 搜索樹上的所有節(jié)點都標記它們所對應的狀態(tài)描述，每個節(jié)點旁邊的數(shù)字表示節(jié)點擴展的順序(按順時針方向移動空格)。圖中最后一個節(jié)點是目標節(jié)點。143.2 盲目搜索 3.2.2深度優(yōu)先搜索另一種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-first search)。分析深度優(yōu)先搜索示意圖可看出，在深度優(yōu)先搜索中，我們首先擴展最新產生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。 153.2 盲目搜索 3.2.2深度優(yōu)先搜索我們定義節(jié)點的深度如下：(1) 起始節(jié)點(即根節(jié)點)的深度為0。(2) 任何其它節(jié)點的深度等于其父輩節(jié)點深度

9、加上1。首先，擴展最深的節(jié)點的結果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。替代路徑與前面已經試過的路徑不同之處僅僅在于改變最后n步，而且保持n盡可能小。 對于許多問題，其狀態(tài)空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴展下去)，往往給出一個節(jié)點擴展的最大深度深度界限。任何節(jié)點如果達到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。值得說明的是，即使應用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。163.2

10、盲目搜索 3.2.2深度優(yōu)先搜索圖3.5深度優(yōu)先搜索示意圖173.2 盲目搜索 3.2.2深度優(yōu)先搜索含有深度界限的深度優(yōu)先搜索算法如下：(1) 把起始節(jié)點S放到未擴展節(jié)點OPEN表中。如果此節(jié)點為一目標節(jié)點，則得到一個解。(2) 如果OPEN為一空表，則失敗退出。(3) 把第一個節(jié)點(節(jié)點n)從OPEN表移到CLOSED表。(4) 如果節(jié)點n的深度等于最大深度，則轉向(2)。(5) 擴展節(jié)點n，產生其全部后裔，并把它們放入OPEN表的前頭。如果 沒有后裔，則轉向(2)。(6) 如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解，成功退出；否則，轉向(2)。183.2 盲目搜索 3.2.2深度優(yōu)先

11、搜索深度優(yōu)先搜索算法框圖3.6193.2 盲目搜索 3.2.2深度優(yōu)先搜索例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，我們設置深度界限為5。圖3.8繪出了搜索樹，粗線條的路徑表明含有5條應用規(guī)則的一個解。從圖可見，深度優(yōu)先搜索過程是沿著一條路徑進行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。203.2 盲目搜索 3.2.2深度優(yōu)先搜索圖 3.8 八數(shù)碼難題的深度優(yōu)先搜索樹 213.2 盲目搜索 3.2.3等代價搜索 有些問題并不要求有應用算符序列為最少的解，而是要求具有某些特性的解。搜索樹中每條連接弧線上的有關

12、代價以及隨之而求得的具有最小代價的解答路徑，與許多這樣的廣義準則相符合。 寬度優(yōu)先搜索可被推廣用來解決這種尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法。223.2 盲目搜索 3.2.3等代價搜索有如下一些記號：起始節(jié)點記為S；從節(jié)點i到它的后繼節(jié)點j的連接弧線代價記為c(i,j)；從起始節(jié)點S到任一節(jié)點i的路徑代價記為g(i)。在搜索樹上，我們假設g(i)也是從起始節(jié)點S到節(jié)點i的最少代價路徑上的代價，因為它是唯一的路徑； 233.2 盲目搜索 3.2.3等代價搜索等代價搜索算法：等代價搜索方法以g(i)的遞增順序擴展其節(jié)點，其算法如下：(1

13、) 把起始節(jié)點S放到未擴展節(jié)點表OPEN中。如果此起始節(jié)點為一目標節(jié)點，則求得一個解;否則令g(S)=0。(2) 如果OPEN是個空表，則沒有解而失敗退出。(3) 從OPEN表中選擇一個節(jié)點i，使其g(i)為最小。如果有幾個節(jié)點都合格，那么就要選擇一個目標節(jié)點作為節(jié)點i(要是有目標節(jié)點的話)；否則，就從中選一個作為節(jié)點i。把節(jié)點i從OPEN表移至擴展節(jié)點表CLOSED中。 (4) 如果節(jié)點i為目標節(jié)點，則求得一個解。 (5) 擴展節(jié)點i。如果沒有后繼節(jié)點，則轉向第(2)步。(6) 對于節(jié)點i的每個后繼節(jié)點j，計算g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點j放進OPEN表。提供回到節(jié)點i

14、的指針。(7) 轉向第(2)步。243.2 盲目搜索 3.2.3深度優(yōu)先搜索圖 3.9等代價搜索算法框圖 253.3 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費過多的計算空間與時間。 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法,其主要的差別是OPEN表中待擴展節(jié)點的順序問題。人們就試圖找到一種方法用于排列待擴展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴展，那么，搜索效率將會大為提高。啟發(fā)信息：進行搜索技術一般需要某些有關具體問題領域的特性的信息，把此種信息叫做啟發(fā)信息。把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。 263.3 啟發(fā)式搜索 3.2.1 啟發(fā)式搜索策略和估價函數(shù) 1 啟發(fā)式搜

15、索策略假設初始狀態(tài)、算符和目標狀態(tài)的定義都是完全確定的，然后決定一個搜索空間。因此，問題就在于如何有效地搜索這個給定空間。啟發(fā)信息按其用途可分為下列3種：(1) 用于決定要擴展的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。(2) 在擴展一個節(jié)點的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。(3) 用于決定某些應該從搜索樹中拋棄或修剪的節(jié)點。在本節(jié)中，我們只討論利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪個是下一步要擴展的節(jié)點。這種搜索總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。這種搜索叫做有序搜索(ordered search)。

16、 273.3 啟發(fā)式搜索 3.2.1 啟發(fā)式搜索策略和估價函數(shù) 2 估價函數(shù) 估價函數(shù)(evaluation function)：用來估算節(jié)點希望程度的量度。一個節(jié)點的“希望”(promise)有幾種不同的定義方法。在狀態(tài)空間問題中，一種方法是估算目標節(jié)點到此節(jié)點的距離；另一種方法認為，解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。每個不同的衡量標準只能考慮該問題中這個節(jié)點的某些決定性特性，或者對給定節(jié)點與目標節(jié)點進行比較，以決定相關特性。我們用符號f來標記估價函數(shù)，用f(n)表示節(jié)點n的估價函數(shù)值。暫時令f為任意函數(shù)，以后我們將會提出f是從起始節(jié)點約束地通過節(jié)點n而到達目標節(jié)點的最

17、小代價路徑上的一個估算代價。283.3 啟發(fā)式搜索 3.3.2 有序搜索 我們用估價函數(shù)f來排列GRAPHSEARCH第8步中OPEN表上的節(jié)點。根據(jù)習慣，OPEN表上的節(jié)點按照它們f函數(shù)值的遞增順序排列。根據(jù)推測，某個具有低的估價值的節(jié)點較有可能處在最佳路徑上。 應用某個算法(例如等代價算法)選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。這種搜索方法叫做有序搜索或最佳優(yōu)先搜索，而其算法就叫做有序搜索算法或最佳優(yōu)先算法。 可見它總是選擇最有希望的節(jié)點作為下一個要擴展的節(jié)點。有序搜索(ordered search)又稱為最好優(yōu)先搜索(best-first search)。 293.3

18、 啟發(fā)式搜索 3.3.2 有序搜索 有序狀態(tài)空間搜索算法如下： (1) 把起始節(jié)點S放到OPEN表中，計算f(S)并把其值與節(jié)點S聯(lián)系起來。(2) 如果OPEN是個空表，則失敗退出，無解。(3) 從OPEN表中選擇一個f值最小的節(jié)點i。結果有幾個節(jié)點合格，當其中有一個為目標節(jié)點時，則選擇此目標節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點i。(4) 把節(jié)點i從OPEN表中移出，并把它放入CLOSED的擴展節(jié)點表中。(5) 如果i是個目標節(jié)點，則成功退出，求得一個解。303.3 啟發(fā)式搜索 3.3.2 有序搜索 有序狀態(tài)空間搜索算法如下： (6) 擴展節(jié)點i，生成其全部后繼節(jié)點。對于i的每一個后繼節(jié)點j

19、：(a)計算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。(c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值。如果新的f值較小，則(i)以此新值取代舊值。(ii)從j指向i，而不是指向它的父輩節(jié)點。(iii)如果節(jié)點j在CLOSED中,則把它移回OPEN表.(7) 轉向(2)，即GO TO(2)。 313.3 啟發(fā)式搜索 3.3.2 有序搜索 有序搜索算法框圖3.9323.3 啟發(fā)式搜索 3.3.2 有序搜索 寬度

20、優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術的特例。 對于寬度優(yōu)先搜索，我們選擇f(i)作為節(jié)點i的深度。 對于等代價搜索，f(i)是從起始節(jié)點至節(jié)點i這段路徑的代價。有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準確的希望量度，那么f的選擇將涉及兩個方面的內容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。 333.3 啟發(fā)式搜索 3.3.3 A*算法A*算法的估價函數(shù)：讓我們描述一個特別的估價函數(shù)，這個估價函數(shù)f使得在任意節(jié)點上其函數(shù)值f(n)能估算出從節(jié)點S到節(jié)點n的最小代價路徑的代

21、價與從節(jié)點n到某一目標節(jié)點的最小代價路徑的代價之總和，也就是說f(n)是約束通過節(jié)點n的一條最小代價路徑的代價的一個估計。 因此，OPEN表上具有最小f值的那個節(jié)點就是所估計的加有最少嚴格約束條件的節(jié)點，而且下一步要擴展這個節(jié)點是合適的。343.3 啟發(fā)式搜索 3.2.4 A*算法A*算法的估價函數(shù)：在正式討論A*算法之前，我們先介紹幾個有用的記號。 k(ni，nj)表示任意兩個節(jié)點ni和nj之間最小代價路徑的實際代價(對于兩節(jié)點間沒有通路的節(jié)點，函數(shù)k沒有定義)。 于是，從節(jié)點n到某個具體的目標節(jié)點ti，某一條最小代價路徑的代價可由k(n,ti)給出。 h*(n)表示整個目標節(jié)點集合ti上所

22、有k(n,ti)中最小的一個，因此，h*(n)就是從n到目標節(jié)點最小代價路徑的代價，而且從n到目標節(jié)點能夠獲得h*(n)的任一路徑就是一條從n到某個目標節(jié)點的最佳路徑(對于任何不能到達目標節(jié)點的節(jié)點n，函數(shù)h*沒有定義)。 353.3 啟發(fā)式搜索 A*算法的估價函數(shù)：通常我們感興趣的是想知道從已知起始節(jié)點S到任意節(jié)點n的一條最佳路徑的代價k(S,n)。為此，引進一個新函數(shù)g*，這將使我們的記號得到某些簡化。對所有從S開始可達到n的路徑來說，函數(shù)g*定義為g*(n)=k(S,n)其次，我們定義函數(shù)f*，使得在任一節(jié)點n上其函數(shù)值f*(n)就是從節(jié)點S到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到

23、某目標節(jié)點的一條最佳路徑的代價之和，即: f*(n)=g*(n)+ h*(n)因而f*(n)值就是從S開始約束通過節(jié)點n的一條最佳路徑的代價，而f*(S)=h*(S)是一條從S到某個目標節(jié)點中間無約束的一條最佳路徑的代價。我們希望估價函數(shù)f是f*的一個估計，此估計可由下式給出：f(n)=g(n)+h(n)363.3 啟發(fā)式搜索 3.2.4 A*算法A*算法的估價函數(shù)：其中：g是g*的估計；h是h*的估計。對于g(n)來說，一個明顯的選擇就是搜索樹中從S到n這段路徑的代價，這一代價可以由從n到S尋找指針時，把所遇到的各段弧線的代價加起來給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代

24、價路徑)。 這個定義包含了g(n)g*(n)。對于h*(n)的估計h(n)，它依賴于有關問題的領域的啟發(fā)信息。我們把h叫做啟發(fā)函數(shù)。 373.3 啟發(fā)式搜索 A*算法的估價函數(shù)：A算法和A*算法的定義定義1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進行的，則稱該過程為A算法。定義2 在A算法中，如果對所有的x，h(x)h*(x)成立,則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā*算法是一種有序搜索算法，其特點在于對估價

25、函數(shù)的定義上。對于一般的有序搜索，總是選擇f值最小的節(jié)點作為擴展節(jié)點。因此，f是根據(jù)需要找到一條最小代價路徑的觀點來估算節(jié)點的，所以，可考慮每個節(jié)點n的估價函數(shù)值為兩個分量：從起始節(jié)點到節(jié)點n的代價以及從節(jié)點n到達目標節(jié)點的代價。 383.3 啟發(fā)式搜索 3.2.4 A*算法A*算法(1) 把S放入OPEN表，記f=h，令CLOSED為空表。(2) 重復下列過程，直至找到目標節(jié)點為止。若OPEN為空表，則宣告失敗。(3) 選取OPEN表中未設置過的具有最小f值的節(jié)點為最佳節(jié)點BESTNODE，并把它放入CLOSED表。(4) 若BESTNODE為一目標節(jié)點，則成功求得一解。(5) 若BESTN

26、ODE不是目標節(jié)點，則擴展之，產生后繼節(jié)點SUCCSSOR。393.3 啟發(fā)式搜索 3.2.4 A*算法A*算法(6) 對每個SUCCSSOR進行下列過程：(a) 建立從SUCCSSOR返回BESTNODE的指針。(b) 計算g(SUC)=g(BES)+g(BES,SUC)。(c) 如果SUCCSSOROPEN，則稱此節(jié)點為OLD，并把它添至BESTNODE的后繼節(jié)點表中。(d) 比較新舊路徑代價。如果g(SUC)g(OLD),則重新確定OLD的父輩節(jié)點為 BESTNODE，記下較小代價g(OLD),并修正f(OLD)值。(e) 若至OLD節(jié)點的代價較低或一樣，則停止擴展節(jié)點。(f) 若SUC

27、CSSOR不在OPEN表中，則看其是否在CLOSED表中。(g) 若SUCCSSOR在CLOSE表中，則轉向c。(h) 若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，則把它放入OPEN表中，并添入BESTNODE后裔表，然后轉向(7)(7) 計算f值。(8) GO LOOP 403.3 啟發(fā)式搜索 A* 算 法 參 考 框 圖 3 . 1 1413.4消解原理 前面我們討論了一些簡單搜索的基本原理，包括某些推理規(guī)則以及置換合一等概念。但對于許多比較復雜的系統(tǒng)和問題，如果采用前面討論過的搜索方法，那么很難甚至無法使問題獲得解決的。需要應用一些更先進的推理技術和系統(tǒng)求解這種比較復雜

28、的問題，本節(jié)討論消解原理。423.4消解原理 3.4.1化為子句集 第二章中討論過謂詞公式，某些推理規(guī)則以及置換合一等概念。在這個基礎上，我們將進一步研究消解原理(resolution principle)。有些專家把它叫做歸結原理。 消解是一種可用于一定的子句公式的重要推理規(guī)則。 一個子句定義為由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。當消解可使用時，消解過程被應用于母體子句對，以便產生一個導出子句。例如，如果存在某個公理E1E2和另一公理E2E3，那么E1E3在邏輯上成立。這就是消解，而稱E1E3為E1E2和E2E3的消解式(resolvent)。 433.4消解原

29、理 3.4.1化為子句集在說明消解過程之前,我們首先說明任一謂詞演算公式可以化成一個子句集。其變換過程由下列九個步驟組成：(1)消去蘊涵符號 只應用和符號，以AB替換A=B。(2)減少否定符號的轄域 每個否定符號最多只用到一個謂詞符號上，并反復應用狄摩根定律。443.4消解原理 3.4.1化為子句集例如： 以AB代替(AB)以AB代替(AB)以(x)A代替(x)A以(x)A代替(x)A以A代替(A)453.4消解原理 3.4.1化為子句集(3)對變量標準化 在任一量詞轄域內，受該量詞約束的變量為一啞元(虛構變量)，它可以在該轄域內處處統(tǒng)一地被另一個沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值

30、。合適公式中變量的標準化，意味著對啞元改名以保證每個量詞有其自己唯一的啞元。例如，把 標準化而得到: 463.4消解原理 3.4.1化為子句集(4)消去存在量詞Skolem函數(shù): 在公式(y)(x)P(x,y)中，存在量詞是在全稱量詞的轄域內，我們允許所存在的x可能依賴于y值。令這種依賴關系明顯地由函數(shù)g(y)所定義，它把每個y值映射到存在的那個x。這種函數(shù)叫做Skolem函數(shù)。 如果用Skolem函數(shù)代替存在的x,我們就可以消去全部存在量詞，并寫成：從一個公式消去一個存在量詞的一般規(guī)則是以一個Skolem函數(shù)代替每個出現(xiàn)的存在量詞的量化變量，而這個Skolem函數(shù)的變量就是由那些全稱量詞所約

31、束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內。Skolem函數(shù)所使用的函數(shù)符號必須是新的，即不允許是公式中已經出現(xiàn)過的函數(shù)符號。 473.4消解原理 3.4.1化為子句集(4)消去存在量詞Skolem函數(shù): 如果要消去的存在量詞不在任何一個全稱量詞的轄域內，那么我們就用不含變量的Skolem函數(shù)即常量。例如，(x)P(x)化為P(A)，其中常量符號A用來表示我們知道的存在實體。A必須是個新的常量符號，它未曾在公式中其它地方使用過。例如：(z)(y)( x)P(x,y,z)483.4消解原理 3.4.1化為子句集例如：(z)(y)(x)P(x,y,z)被(y)P(g(

32、y),y,A)代替，其中g(y)為一Skolem函數(shù)。 493.4消解原理 3.4.1化為子句集(5)化為前束形到這一步，已不留下任何存在量詞，而且每個全稱量詞都有自己的變量。把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為前束形。前束形公式由前綴和母式組成，前綴由全稱量詞串組成，母式由沒有量詞的公式組成，即前束形 = (前綴) (母 式) 全稱量詞串 無量詞公式 503.4消解原理 3.4.1化為子句集(6)把母式化為合取范式 任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。我們可以反復應用分配律

33、。把任一母式化成合取范式。例如，我們把 ABC化為ABAC 513.4消解原理 3.4.1化為子句集(7)消去全稱量詞到了這一步，所有余下的量詞均被全稱量詞量化了。同時，全稱量詞的次序也不重要了。因此，我們可以消去前綴，即消去明顯出現(xiàn)的全稱量詞。 (8)消去連詞符號 用(AB),(AC)代替(AB)(AC)，以消去明顯的符號。反復代替的結果，最后得到一個有限集，其中每個公式是文字的析取。任一個只由文字的析取構成的合適公式叫做一個子句。523.4消解原理 3.4.1化為子句集(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。例如，對于子集P(x)P(y)Pf(x,

34、y),P(x)Qx,g(x),P(x)Pg(x)，在更改變量名后，可以得到子句集： P(x1)P(y)Pf(x1,y), P(x2)Qx2,g(x2), P(x3)Pg(x3) 按照上述9個步驟。把例子 533.4消解原理3.4.1化為子句集第一步： 第二步： 第三步： 第四步： w=g（x）為一個Skolem函數(shù) 第五步： 前綴母式543.4消解原理 3.4.1化為子句集 第六步： 第七步： 第八步： 第九步：更改變量名稱：553.4消解原理 3.4.2消解推理規(guī)則 令L1為任一原子公式，L2為另一原子公式； L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1和L2，如果L1

35、和L2具有最一般合一者，那么通過消解可以從這兩個父輩子句推導出一個新子句()。這個新子句叫做消解式。它是由取這兩個子句的析取，然后消去互補對而得到的。 下面舉出幾個從父輩子句求消解式的例子: (a) 假言推理 父輩子句消解式563.4消解原理 3.4.2消解推理規(guī)則下面舉出幾個從父輩子句求消解式的例子: (b) 合并 父輩子句消解式573.4消解原理 3.4.2消解推理規(guī)則 下面舉出幾個從父輩子句求消解式的例子: (c) 重言式 父輩子句消解式583.4消解原理 3.4.2消解推理規(guī)則 下面舉出幾個從父輩子句求消解式的例子: (d)空子句(矛盾) 593.4消解原理 3.4.2消解推理規(guī)則 下

36、面舉出幾個從父輩子句求消解式的例子: (e) 鏈式(三段論) 603.4消解原理 3.4.3含有變量的消解式 為了對含有變量的子句使用消解規(guī)則，我們必須找到一個置換，作用于父輩子句使其含有互補文字。 令父輩子句由Li和Mi給出，而且假設這兩個子句中的變量已經分離標準化。設li是Li的一個子集，mi是Mi的一個子集，使得集li和mi的并集存在一個最一般的合一者。 消解兩個子句Li和Mi，得到的新子句: Li-liMi-mi就是這兩個子句的消解式。 消解兩個子句時，可能有一個以上的消解式，因為有多種選擇li和mi的方法。不過，在任何情況下，它們最多具有有限個消解式。 613.4消解原理 作為例子，

37、我們考慮兩個子句: Px,f(A)Px,f(y)Q(y) 和 Pz,f(A)Q(z)如果取 :li=Px,f(A)， mi=Pz,f(A)那么得到消解式: Pz,f(y)Q(z)Q(y)如果取 :li=Q(y)，mi=Q(z)那么得到消解式: Px,f(A)Px,f(y)Py,f(A)進一步消解得消解式為: Py,f(y)可見這兩個子句消解一共可得4個不同的消解式，其中3個是消解P得到的，而另一個是由消解Q得到的。623.4消解原理 3.4.3含有變量的消解式 例1 例2 例3 633.4消解原理 3.4.3含有變量的消解式 下面舉幾個對含有變量的子句使用消解的例子。 例1例3例2643.4消

38、解原理 3.4.3含有變量的消解式P72 本節(jié)中所例舉的對基子句和對含有變量的子句進行消解的例子，其父輩子句和消解式列表示于表4.1。這些例子表示出消解推理的某些常用規(guī)則。 消解推理常用規(guī)則653.4消解原理 3.4.4消解反演求解過程 1 基本思想 把要解決的問題作為一個要證明的命題，其目標公式被否定并化成子句形，然后添加到命題公式集中去,把消解反演系統(tǒng)應用于聯(lián)合集，并推導出一個空子句（NIL)，產生一個矛盾，這說明目標公式的否定式不成立，即有目標公式成立，定理得證，問題得到解決。這與數(shù)學中反證法的思想十分相似。 663.4消解原理 3.4.4消解反演求解過程 (2) 反演求解的正確性 設公

39、式L在邏輯上遵循公式集S，那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足L的，所以不存在能夠滿足并集SL的解釋。 如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。因此，如果L在邏輯上遵循S，那么SL是不可滿足的。 可以證明，如果消解反演反復應用到不可滿足的子句集，那么最終將要產生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集SL消解得到的子句，最后將產生空子句；反之，可以證明，如果從SL的子句消解得到空子句，那么L在邏輯上遵循S。673.4消解原理 3.4.4消解反演求解過程 以下按上述的四個步驟來對問題進行反演求解： (1)否定L，得L；(2)把L添加

40、到S中去；(3)把新產生的集合L，S化成子句集；(4)應用消解原理，力圖推導出一個表示矛盾的空子句NIL。 683.4消解原理 3.4.4消解反演求解過程 (3) 反演求解的舉例 下面舉個例子來說明消解反演過程： 前提：每個儲蓄錢的人都獲得利息。結論：如果沒有利息，那么就沒有人去儲蓄錢。證明：令S(x,y)表示x儲蓄y M(x)表示x是錢 I(x)表示x是利息 E(x，y)表示x獲得y于是上述命題寫成下列形式：結論：693.4消解原理 3.4.4消解反演求解過程 用化為子句集的九步法，可把前提化為下列的子句集： 其中，y=f（x）為Skolem函數(shù)。而結論的否定：703.4消解原理 3.4.4

41、消解反演求解過程（a） 否定L，即有 （b） 把 L添加到 中去，即 （c） 把新產生的集合化成子句集，即（d） 應用消解原理，力圖推導出一個表示矛盾的空子句NIL。 713.4消解原理 3.4.4消解反演求解過程 儲蓄問題反演樹 723.4消解原理 3.4.4消解反演求解過程 可把前提和結論化為下列的子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，y=f(x)為Skolem函數(shù)。I(z),S(a,b),M(b)733.4消解原理 3.4.4消解反演求解過程 (2)反演求解過程 用反演樹求取對某個問題的答案，其過程如下：(1) 把由目標公式的否定產生的每

42、個子句添加到目標公式否定之否定的子句中去。(2) 按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。(3) 用根部的子句作為一個回答語句。 答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個語句的一顆證明樹。由于變換關系涉及到把由目標公式的否定產生的每個子句變換為一個重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。743.4消解原理 ( x)AT(JOHN,X)=AT(FIDO,X)和AT(JOHN,SCHOOL)如果無論約翰(John)到哪里去，菲多

43、(Fido)也就去那里，那么如果約翰在學校里，菲多在哪里呢?” 很清楚，這個問題說明了兩個事實，然后提出一個問題，而問題的答案大概可從這兩個事實推導出。這兩個事實可以解釋為下列公式集S：如果我們首先證明公式( x)AT(FIDO,X)在邏輯上遵循S，然后尋求一個存在x的例，那么就能解決“菲多在哪里”的問題。關鍵想法是把問題化為一個包含某個存在量詞的目標公式，使得此存在量詞量化變量表示對該問題的一個解答。如果問題可以從給出的事實得到答案，那么按這種方法建立的目標函數(shù)在邏輯上遵循S。在得到一個證明之后，我們就試圖求取存在量詞量化變量的一個例，作為一個回答。對于上述例題能夠容易地證明(x)AT(FI

44、DO,X) 遵循S。我們也可以說明，用一種比較簡單的方法來求取合適的答案。 753.4消解原理 3.4.4消解反演求解過程 (2)反演求解過程 消解反演可用一般方式得到，其辦法是首先對被證明的公式加以否定，再把這個否定式附加到集S中去，化這個擴充集的所有成員為子句形，然后用消解證明這個子句集是不可滿足的。圖3.13表示出上例的反演樹。從S中的公式得到的子句叫做公理。注意目標公式( x)AT(FIDO,x)的否定產生 ( x)AT(FIDO,x) 其子句形式為:AT(FIDO,x) 763.4消解原理 3.4.4消解反演求解過程 (2)反演求解過程 對本例應用消解反演求解過程，我們有：(1) 目

45、標公式否定的子句形式為 :AT(FIDO,x) 把它添加至目標公式的否定之否定的子句中去，得重言式 AT(FIDO,x)AT(FIDO,x) (2) 用圖3.14的反演樹進行消解，并在根部得到子句:AT (FIDO，SCHOOL) (3) 從根部求得答案AT(FIDO，SCHOOL)，用此子句作為回答語句。因此，子句 AT (FIDO，SCHOOL)就是這個問題的合適答案，773.4消解原理 3.4.4消解反演求解過程 (2)反演求解過程 “菲多在哪里”例題的反演樹 3.13 從消解求取答案例題的反演樹 3.14783.5 規(guī)則演繹系統(tǒng) 對于許多公式來說，子句形是一種低效率的表達式，因為一些重

46、要信息可能在求取子句形過程中丟失。本章將研究采用易于敘述的if-then(如果-那么)規(guī)則來求解問題。 基于規(guī)則的問題求解系統(tǒng)運用下述規(guī)則: 其中，If部分可能由幾個if組成，而Then部分可能由一個或一個以上的then組成。 在所有基于規(guī)則系統(tǒng)中，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rule based deduction system)。 在這種系統(tǒng)中，通常稱每個if部分為前項(antecedent)，稱每個then部分為后項(co

47、nsequent)。793.5 規(guī)則演繹系統(tǒng) 3.5.1 規(guī)則正向演繹系統(tǒng)基于規(guī)則的演繹系統(tǒng)和產生式系統(tǒng)，均有兩種推理方式：正向推理(forward chanining)和逆向推理(backward chaining)。正向推理：從if部分向then部分推理的過程，它是從事實或狀況向目標或動作進行操作的。 逆向推理：從then部分向if部分推理的過程，它是從目標或動作向事實或狀況進行操作的。803.5 規(guī)則演繹系統(tǒng) 1.事實表達式的與或形變換在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實表示為非蘊涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。我們不想把這些事實化為子句形，而是把它們表示為謂詞演算公式，并把這些公

48、式變換為叫做與或形的非蘊涵形式。要把一個公式化為與或形，可采用下列步驟：(1) 利用(W1=W2)和(W1W2)的等價關系，消去符號=(如果存在該符號的話)。實際上，在事實中間很少有符號=出現(xiàn)，因為可把蘊涵式表示為規(guī)則。(2) 用狄摩根(De Morgan)定律把否定符號移進括號內，直到每個否定符號的轄域最多只含有一個謂詞為止。 (3) 對所得到的表達式進行Skolem化和前束化。 (4) 對全稱量詞轄域內的變量進行改名和變量標準化，而存在量詞量化變量用Skolem函數(shù)代替。 (5) 刪去全稱量詞，而任何余下的變量都被認為具有全稱量化作用。 813.5 規(guī)則演繹系統(tǒng) 例如，我們有事實表達式 對

49、變量更名標準化，使得同一變量不出現(xiàn)在事實表達式的不同主要合取式中。更名后得表達式： Q(w,A)R(v)P(v)S(A,v) 必須注意到Q(v，A)中的變量v可用新變量w代替，而合取式R(v)P(v)中的變量v卻不可更名，因為后者也出現(xiàn)在析取式S(A,v)中。 與或形表達式是由符號和連接的一些文字的子表達式組成的。呈與或形的表達式并不是子句形，而是接近于原始表達式形式，特別是它的子表達式不是復合產生的。 把它化為 Q(v,A)R(v)P(v)S(A,v)823.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實表達式的與或圖表示 與或形的事實表達式可用與或圖來表示。如圖3.15的與或樹表示出

50、上述例子的與或形事實表達。 圖3.15中，每個節(jié)點表示該事實表達式的一個子表達式。某個事實表達式(E1Ek)的析取關系子表達式E1，Ek是用后繼節(jié)點表示的，并由一個k線連接符把它們連接到父輩節(jié)點上。 某個事實表達式(E1En)的每個合取子表達式E1，En是由單一的后繼節(jié)點表示的，并由一個單線連接符接到父輩接點。在事實表達式中，用k線連接符(一個合取記號)來分解析取式，很可能會令人感到意外。在后面的討論中，我們將會了解到采用這種約定的原因。 833.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實表達式的與或圖表示表示某個事實表達式的與或圖的葉節(jié)點均由表達式中的文字來標記。圖中標記有整個事實

51、表達式的節(jié)點，稱為根節(jié)點，它在圖中沒有祖先。公式的與或圖表示有個有趣的性質，即由變換該公式得到的子句集可作為此與或圖的解圖的集合(終止于葉節(jié)點)讀出；也就是說，所得到的每個子句是作為解圖的各個葉節(jié)點上文字的析取。這樣，由表達式 Q(w,A)R(v)P(v)S(A,v)得到的子句為 Q(w,A),S(A,v)R(v),S(A,v)P(v)843.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實表達式的與或圖表示 圖 3.15 一個事實表達式的與或樹表示 853.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實表達式的與或圖表示 上述每個子句都是圖3.15解圖之一的葉節(jié)點上文字的析取。所以

52、，我們可把與或圖看做是對子句集的簡潔表示。不過，實際上表達式的與或圖表示此子句集表示的通用性稍差，因為沒有復合出共同的子表達式會妨礙在子句形中可能做到的某些變量的更名。例如，上面的最后一個子句，其變量v可全部改為u，但無法在與或圖中加以表示，因而失去了通用性，并且可能帶來一些困難。我們一般把事實表達式的與或圖表示倒過來畫，即把根節(jié)點畫在最下面，而把其后繼節(jié)點往上畫。接下來我們將要討論目標公式的與或圖表示，它是按通常方式畫出的，即目標在上面。863.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換這些規(guī)則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。我們把允許用作規(guī)則

53、的公式類型限制為下列形式：L=W 式中：L是單文字；W為與或形的唯一公式。我們也假設出現(xiàn)在蘊涵式中的任何變量都有全稱量化作用于整個蘊涵式。這些事實和規(guī)則中的一些變量被分離標準化，使得沒有一個變量出現(xiàn)在一個以上的規(guī)則中，而且使規(guī)則變量不同于事實變量。單文字前項的任何蘊涵式，不管其量化情況如何都可以化為某種量化轄域為整個蘊涵式的形式。這個變換過程首先把這些變量的量詞局部地調換到前項，然后再把全部存在量詞Skolem化。873.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換舉例說明如下： 公式 ( x)( y)( z)P(x,y,z)=( u)Q(x,u可以通過下列步驟加以變換：

54、 (1) 暫時消去蘊涵符號( x)( y)( z)P(x,y,z)( u)Q(x,u)(2) 把否定符號移進第一個析 取式內，調換變量的量詞 ( x)( y)( z) P(x,y,z)( u)Q(x,u)(3) 進行Skolem化 ( x)( y)P(x,y,f(x,y)( u)Q(x,u)(4) 把所有全稱量詞移至前面然后消去 P(x,y,f(x,y)Q(x,u)(5) 恢復蘊涵式P(x,y,f(x,y)=Q(x,u) 上述變換的動態(tài)演示如下： 883.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換以下用一個自由變量的命題演算情況來說明如何把這類規(guī)則應用于與或圖。 把形式

55、為L=W的規(guī)則應用到任一個具有葉節(jié)點n并由文字L標記的與或圖上，可以得到一個新的與或圖。在新的圖上，節(jié)點n由一個單線連接符接到后繼節(jié)點(也由L標記)，它是表示為W的一個與或圖結構的根節(jié)點。作為例子，考慮把規(guī)則S =(XY)Z應用到圖3.16所示的與或圖中標有S的葉節(jié)點上。所得到的新與或圖結構表示于圖3.17，圖中標記S的兩個節(jié)點由一條叫做匹配弧的弧線連接起來。 應用一條規(guī)則得到的與或圖3.17 不含變量的與或圖 3.16893.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換 在應用某條規(guī)則之前，一個與或圖(如圖3.16)表示一個具體的事實表達式。其中，在葉節(jié)點結束的一組解圖

56、表示該事實表達式的子句形。我們希望在應用規(guī)則之后得到的圖，既能表示原始事實，又能表示從原始事實和該規(guī)則推出的事實表達式。 假設我們有一條規(guī)則L=W，根據(jù)此規(guī)則及事實表達式F(L)，可以推出表達式F(W)。F(W)是用W代替F中的所有L而得到的。當用規(guī)則L= W來變換以上述方式描述的F(L)的與或圖表示時，我們就產生一個含有F(W)表示的新圖；也就是說，它是以葉節(jié)點終止的解圖集以F(W)子句形式代表該子句集。這個子句集包括在F(L)的子句形和L=W的子句形間對L進行所有可能的消解而得到的整集。903.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換再討論圖3.17的情況。規(guī)則S

57、=(XY)Z的子句形是： SXZ, SYZ (PQ)RS(TU)的子句形解圖集為:PQS , RS, PQTU, RTU應用兩個規(guī)則子句中任一個對上述子句形中的S進行消解： 于是我們得到4個子 句對S進行消解的消解式的完備集為：XZPQ , YZPQ , RXZ , RYZ這些消解式全部包含在圖3.17的解圖所表示的子句之中。 913.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換923.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)4.作為終止條件的目標公式應用F規(guī)則的目的在于從某個事實公式和某個規(guī)則集出發(fā)來證明某個目標公式。在正向推理系統(tǒng)中，這種目標表達式只限于可證明的表

58、達式，尤其是可證明的文字析取形的目標公式表達式。 我們用文字集表示此目標公式，并設該集各元都為析取關系。(在以后各節(jié)所要討論的逆向系統(tǒng)和雙向系統(tǒng)，都不對目標表達式作此限制。)目標文字和規(guī)則可用來對與或圖添加后繼節(jié)點，當一個目標文字與該圖中文字節(jié)點n上的一個文字相匹配時，我們就對該圖添加這個節(jié)點n的新后裔，并標記為匹配的目標文字。這個后裔叫做目標節(jié)點，目標節(jié)點都用匹配弧分別接到它們的父輩節(jié)點上。當產生式系統(tǒng)產生一個與或圖，并包含有終止在目標節(jié)點上的一個解圖時，系統(tǒng)便成功地結束。此時，該系統(tǒng)實際上已推出一個等價于目標子句的一部分的子句。 933.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)4.作為

59、終止條件的目標公式圖3.18給出一個滿足以目標公式(CG)為基礎的終止條件的與或圖，可把它解釋為用一個“以事實來推理”的策略對目標表達式(CG)的一個證明。最初的事實表達式為(AB)。由于不知道A或B哪個為真，因此我們可以試著首先假定A為真，然后再假定B為真，分別地進行證明。如果兩個證明都成功，那么我們就得到根據(jù)析取式(AB)的一個證明。而A或B到底哪個為真都無關緊要。圖3.18中標有(AB)的節(jié)點，其兩個后裔由一個2線連接符來連接。因而這兩個后裔都必須出現(xiàn)在最后解圖中，如果對節(jié)點n的一個解圖通過k線連接符包含n的任一后裔，那么此解圖必須包含通過這個k線連接符的所有k個后裔。對應動畫圖示： 9

60、43.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)4.作為終止條件的目標公式滿足中終止條件的與或圖3.18 例子證明過程如下：把規(guī)則化為子句形，得子句集： AC，AD BE，BG 目標的否定為: (CG) 其子句形為: C，G 953.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)用消解反演來證明目標公式，對應動畫圖示： 例子證明過程如下：把規(guī)則化為子句形，得子句集： AC，AD BE，BG 目標的否定為: (CG) 其子句形為: C，G 我們推得一個空子句NIL，從而使目標公式(CG)得到證明。用消解反演求證目標公式的圖解 963.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)用消解反演來證明目