1、2020/9/1,1,基本的推理技術,課程的基本內容及要求： 基本內容 推理的概念和類型，推理的控制策略； 歸結反演系統歸結原理、歸結反演及其控制策略、應用歸結反演求取問題的答案等； 基于規(guī)則的演繹推理（包括正向、反向和雙向的演繹推理）。 要求 熟練掌握與運用歸結原理； 理解各種歸結反演的控制策略； 學會如何從一歸結反演系統中提取回答； 掌握基于規(guī)則的演繹推理的工作過程。,2020/9/1,2,課程的安排： 1，2（2小節(jié)）節(jié)（學時） 重點：1節(jié)2小節(jié)；2節(jié)1小節(jié) 2（2，3小節(jié)）（學時） 重點：2節(jié)2，3小節(jié) 2（4小節(jié)），3（學時） 重點：2節(jié)（4小節(jié)）3節(jié)（1，2小節(jié)）,2020/9/1

2、,3,1 推理技術概述,確定知識表達方法將知識表示出來并存儲到計算機中去 表達知識并存儲知識目的為了更好地利用知識來解決實際問題 利用知識進行推理是知識利用的基礎；是問題求解的主要手段 如專家系統、智能機器人、模式識別、自然語言理解等 本章介紹的推理歸結反演、基于規(guī)則的演繹系統等是基于邏輯的推理，屬于確定性推理,2020/9/1,4,1 推理技術概述,推理的概念和類型 推理人類求解問題主要思維方法，其任務是利用知識 與知識表達方法的關系 推理按照某種策略從已有事實和知識推出結論的過程。推理是由程序實現的，稱為推理機 在人工智能系統中，推理機利用知識庫中的知識，按一定的控制策略去求解問題 醫(yī)療診

3、斷專家系統：知識庫中存儲經驗及醫(yī)學常識，數據庫中存放病人的癥狀、化驗結果等初始事實，為病人診治疾病實際上就是一次推理過程即從病人的癥狀及化驗結果等初始事實出發(fā)，利用知識庫中的知識及一定的控制策略，對病情作出診斷，并開出醫(yī)療處方 從初始事實出發(fā)，不斷運用知識庫中的已知知識，逐步推出結論的過程就是推理,2020/9/1,5,1 推理技術概述,推理的概念和類型 人類的智能活動有多種思維方式，人工智能作為對人類智能的模擬，相應地也有多種推理方式推理的基本任務是從一種判斷推出另一種判斷分類 1演繹推理、歸納推理、默認推理 2.確定性推理、不精確推理 3單調推理、非單調推理 4啟發(fā)式推理、非啟發(fā)式推理,2

4、020/9/1,6,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認推理 1）演繹推理 從全稱判斷推出特稱判斷或單稱判斷的過程，即從一般到個別的推理 演繹推理中最常用的形式是三段論法（大前提和小前提，及結論） 例如： （1）所有的推理系統都是智能系統一般的知識 （2）專家系統是推理系統個體的判斷 （3）所以，專家系統是智能系統新判斷 沒有增加新的知識,2020/9/1,7,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認推理 2）歸納推理 人們對客觀事物的認識總是由認識個別事物開始，進而認識事物的普遍規(guī)律，其中歸納推理起了

5、重要的作用 歸納推理是從足夠多的事例中歸納出一般性結論的推理過程，是一種從個別到一般的推理過程 常用的歸納推理有簡單枚舉法和類比法,2020/9/1,8,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認推理 2）歸納推理 枚舉法歸納推理是由已觀察到的事物都有某屬性，而沒有觀察到相反的事例，從而推出某類事物都有某屬性 推理過程可以形式地表示為： S1 是 P S2 是 P Sn 是 P (S1,S2, Sn 是S 類中的個別事物，在枚舉中兼容) S 都是 P,2020/9/1,9,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、

6、默認推理 2）歸納推理 枚舉法歸納推理分完全歸納推理與不完全歸納推理 完全歸納推理在進行歸納時考察了相應事物的全部對象，并根據這些對象是否都具有某種屬性，從而推出這個事物是否具有這個屬性 完全歸納推理是必然性推理 不完全歸納推理只考察了相應事物的部分對象，就得出了結論 不完全推理得出的結論不具有必然性，屬于非必然性推理,2020/9/1,10,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認推理 2）歸納推理 在兩個或兩類事物在許多屬性上都相同的基礎上，推出它們在其它屬性上也相同，這就是類比法歸納推理 類比法歸納可形式化地表示為： A 具有屬性a,b,c,d

7、,e B 具有屬性a,b,c,d, B 也具有屬性e,2020/9/1,11,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認推理 2）歸納推理 類比法的可靠程度決定于兩個或兩類事物的相同屬性與推出的那個屬性之間的相關程度，相關程度越高，則類比法的可靠性就越高 歸納推理是人類思維活動中最基本、最常用的一種推理形式 歸納推理增加了知識（在機器學習部分稱為歸納學習）,2020/9/1,12,1 推理技術概述,推理的概念和類型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認推理 3）歸納推理 默認推理又稱為缺省推理，是在知識不完全的情況下假設某些條件已經具備所進

8、行的推理 如：在條件A已成立的情況下，如果沒有足夠的證據能證明條件B不成立，則就默認B是成立的，并在此默認的前提下進行推理，推導出某個結論 由于這種推理允許默認某些條件是成立的，這就擺脫了需要知道全部有關事實才能進行推理的要求，能在知識不完全的情況下也能進行推理 在默認推理過程中，如果到某一時刻發(fā)現原先所作的默認不正確，則就要撤消所作的默認以及由此默認推出的所有結論，重新按新情況進行推理,2020/9/1,13,1 推理技術概述,推理的概念和類型 2按推理時所用的知識的確定性來分： 確定性推理、不精確推理 1）確定性推理（精確推理） 如在推理中所用的知識都是精確的，即可以把知識表示成必然的因果

9、關系，然后進行邏輯推理，推理的結論或者為真，或者為假，這種推理就稱為確定性推理 歸結反演、基于規(guī)則的演繹系統等都是確定性推理,2020/9/1,14,1 推理技術概述,推理的概念和類型 2按推理時所用的知識的確定性來分： 確定性推理、不精確推理 1）不精確推理 （不確定推理） 在人類知識中，有相當一部分屬于人們的主觀判斷，是不精確的和含糊的。由這些知識歸納出來的推理規(guī)則往往是不確定的 基于不確定的推理規(guī)則進行推理，形成的結論也是不確定的，這種推理稱為不精確推理 專家系統中主要使用的是不精確推理,2020/9/1,15,1 推理技術概述,推理的概念和類型 3按推理過程中推出的結論是否單調增加，或

10、者說推出的結論是否越來越接近最終目標來劃分： 單調推理、非單調推理 1）單調推理 在推理過程中隨著推理的向前推進及新知識的加入，推出的結論呈單調增加的趨勢，并且越來越接近最終目標單調推理 一個演繹推理的邏輯系統有一個無矛盾的公理系統，新加入的結論必須與公理系統兼容，因此新的結論與已有的知識不發(fā)生矛盾，結論總是越來越多，所以演繹推理是單調推理,2020/9/1,16,1 推理技術概述,推理的概念和類型 3按推理過程中推出的結論是否單調增加，或者說推出的結論是否越來越接近最終目標來劃分： 單調推理、非單調推理 2）非單調推理 在推理過程中隨著推理的向前推進及新知識的加入，不僅沒有加強已推出的結論，

11、反而要否定它，使得推理退回到前面的某一步，重新開始非單調推理 一般非單調推理是在知識不完全的情況下進行的，由于知識不完全，為使推理進行下去，就要先做某些假設，并在此假設的基礎上進行推理，當以后由于新知識的加入發(fā)現原先的假設不正確時，就需要推翻該假設以及由此假設為基礎的一切結論，再用新知識重新進行推理,2020/9/1,17,1 推理技術概述,推理的概念和類型 4按推理中是否運用與問題有關的啟發(fā)性知識可分： 啟發(fā)式推理、非啟發(fā)式推理 1）啟發(fā)式推理 如果在推理過程中，運用與問題有關的啟發(fā)性知識，即解決問題的策略、技巧及經驗，以加快推理過程，提高搜索效率，這種推理過程稱為啟發(fā)式推理 A*、AO*等

12、算法就屬于此類推理,2020/9/1,18,1 推理技術概述,推理的概念和類型 4按推理中是否運用與問題有關的啟發(fā)性知識可分： 啟發(fā)式推理、非啟發(fā)式推理 2）非啟發(fā)式推理 如果在推理過程中，不運用啟發(fā)性知識，只按照一般的控制邏輯進行推理，這種推理稱為非啟發(fā)式推理 這種方法缺乏對求解問題的針對性，所以推理效率較低，容易出現“組合爆炸”問題 圖搜索策略中的寬度優(yōu)先搜索法，雖然是完備的算法，但是對于復雜問題的求解，將出現“組合爆炸”現象，其搜索效率低,2020/9/1,19,1 推理技術概述,推理的控制策略 推理的控制策略主要是指推理方向的選擇、推理時所用的搜索策略及沖突解決策略等 一般推理的控制策

13、略與知識表達方法有關 1推理方向 推理方向用于確定推理的驅動方式 根據推理方向的不同，可將推理分為正向推理、反向推理和正反向混合推理 無論按哪種方式進行推理，一般都要求系統具有一個存放知識的知識庫（KB）、一個存放初始事實和中間結果的數據庫（DB）和一個用于推理的推理機,2020/9/1,20,1 推理技術概述,推理的控制策略 1推理方向 (1) 正向推理 正向推理（事實驅動推理）是由已知事實出發(fā)向結論方向的推理 基本思想是：系統根據用戶提供的初始事實，在知識庫中搜索能與之匹配的規(guī)則即當前可用的規(guī)則，構成可適用的規(guī)則集RS，然后按某種沖突解決策略從RS中選擇一條知識進行推理，并將推出的結論作為

14、中間結果加入到數據庫DB中作為下一步推理的事實，在此之后，再在知識庫中選擇可適用的知識進行推理，如此重復進行這一過程，直到得出最終結論或者知識庫中沒有可適用的知識為止,2020/9/1,21,1 推理技術概述,推理的控制策略 1推理方向 （1）正向推理,是,2020/9/1,22,1 推理技術概述,推理的控制策略 1推理方向 （1）正向推理 正向推理簡單、易實現，但目的性不強，效率低 需要用啟發(fā)性知識解除沖突并控制中間結果的選取，其中包括必要的回溯 由于不能反推，系統的解釋功能受到影響,2020/9/1,23,1 推理技術概述,推理的控制策略 1推理方向 （2）反向推理,2020/9/1,24

15、,1 推理技術概述,推理的控制策略 1推理方向 （2）反向推理 反向推理以某個假設目標作為出發(fā)點的一種推理，又稱為目標驅動推理或逆向推理 反向推理的基本思想是：首先提出一個假設目標，然后由此出發(fā)，進一步尋找支持該假設的證據，若所需的證據都能找到，則該假設成立，推理成功；若無法找到支持該假設的所有證據，則說明此假設不成立，需要另作新的假設,2020/9/1,25,1 推理技術概述,推理的控制策略 1推理方向 （2）反向推理 與正向推理相比，反向推理的主要優(yōu)點是不必使用與目標無關的知識，目的性強，同時它還有利于向用戶提供解釋 反向推理的缺點是在選擇初始目標時具有很大的盲目性，若假設不正確，就有可能

16、要多次提出假設，影響了系統的效率 反向推理比較適合結論單一或直接提出結論要求證實的系統,2020/9/1,26,1 推理技術概述,推理的控制策略 1推理方向 （3）正反向混合推理,2020/9/1,27,1 推理技術概述,推理的控制策略 1推理方向 （3）正反向混合推理,正向推理 效率低，推出大量無關子目標,反向推理 假設的盲目性降低效率,正反向混合推理,2020/9/1,28,1 推理技術概述,推理的控制策略 1推理方向 （3）正反向混合推理 正反向混合推理的一般過程是：先根據初始事實進行正向推理以幫助提出假設，再用反向推理進一步尋找支持假設的證據，反復這個過程，直到得出結論為止 正反向混合

17、推理集中了正向推理和反向推理的優(yōu)點，但其控制策略相對復雜,2020/9/1,29,1 推理技術概述,推理的控制策略 2搜索策略 推理時，要反復用到知識庫中的規(guī)則，而知識庫中的規(guī)則又很多，這樣就存在著如何在知識庫中尋找可用規(guī)則的問題，即如何確定推理路線，使其付出的代價盡可能的少，而問題又能得到較好的解決 為了有效地控制規(guī)則的選取，可以采用各種搜索策略 常用搜索策略： 狀態(tài)空間搜索（寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索等） 啟發(fā)式搜索等（第三章）,2020/9/1,30,1 推理技術概述,推理的控制策略 3沖突解決策略 在推理過程中，系統要不斷地用數據庫中的事實與知識庫中的規(guī)則進行匹配，當

18、有一個以上規(guī)則的條件部分和當前數據庫相匹配時，就需要有一種策略來決定首先使用哪一條規(guī)則，這就是沖突解決策略 沖突解決策略實際上就是確定規(guī)則的啟用順序,2020/9/1,31,1 推理技術概述,推理的控制策略 3沖突解決策略 (1) 專一性排序 如果某一規(guī)則的條件部分規(guī)定的情況比另一規(guī)則的條件部分所規(guī)定的情況更專門，則這條規(guī)則具有較高的優(yōu)先級 例，有如下規(guī)則： 規(guī)則1：IF A AND B AND C THEN E； 規(guī)則2：IF A AND B AND C AND D THEN F； 數據庫中A、B、C、D均為真，這時規(guī)則1和規(guī)則2都與數據庫相匹配，但因為規(guī)則2的條件部分包括了更多的限制，所以

19、具有較高的優(yōu)先級 本策略是優(yōu)先使用針對性較強的產生式規(guī)則,2020/9/1,32,1 推理技術概述,推理的控制策略 3沖突解決策略 (2) 規(guī)則排序 如果規(guī)則編排的順序就表示了啟用的優(yōu)先級，則稱之為規(guī)則排序 (3) 數據排序 數據排序就是把規(guī)則條件部分的所有條件排序，即按優(yōu)先級次序編排起來，當發(fā)生沖突時，首先使用在條件部分包含較高優(yōu)先級數據的規(guī)則 (4) 就近排序 就近排序就是把最近使用的規(guī)則放在最優(yōu)先的位置。如果某一規(guī)則經常使用，則傾向于更多地使用這條規(guī)則,2020/9/1,33,1 推理技術概述,推理的控制策略 3沖突解決策略 (5) 上下文限制 上下文限制就是把產生式規(guī)則按它們所描述的上

20、下文分組，在某種上下文條件下，只能從與其相對應的那組規(guī)則中選擇可應用的規(guī)則 不僅可以減少沖突，而且由于搜索范圍小，也提高了推理的效率,2020/9/1,34,1 推理技術概述,推理的控制策略 3沖突解決策略 (6) 按匹配度排序 在不精確匹配中，為了確定兩個知識模式是否可以進行匹配，需要計算這兩個模式的相似程度，當其相似度達到某個預先規(guī)定的值時，就認為它們是可匹配的 相似度又稱為匹配度，它除了可用來確定兩個知識模式是否可匹配外，還可用于沖突解除。若有幾條規(guī)則均可匹配成功，則可根據它們的匹配度來決定哪一個產生式規(guī)則可優(yōu)先被應用,2020/9/1,35,1 推理技術概述,推理的控制策略 3沖突解決

21、策略 (6) 按條件個數排序 如果有多條產生式規(guī)則生成的結論相同，則要求條件少的產生式規(guī)則被優(yōu)先應用，因為要求條件少的規(guī)則匹配時花費的時間較少 不同的系統，可使用上述這些策略的不同組合，目的是盡量減少沖突的發(fā)生，使推理有較快的速度和較高的效率 如何選擇沖突解決策略完全是由啟發(fā)性知識決定的,2020/9/1,36,2 歸結反演系統,歸結原理 在謂詞演算（第二章）中，利用前面列出的等價式和永真蘊含式可以從已知的一些公式推導出新的公式，這個導出的公式叫做定理，在推導過程中使用的推理規(guī)則序列就成了該定理的一個證明 將要介紹的歸結原理是定理證明的基礎，它應用于稱為子句的一種公式類的推理,2020/9/1

22、,37,2 歸結反演系統,歸結原理,難；繁,2020/9/1,38,2 歸結反演系統,歸結原理 1子句 謂詞邏輯中，把原子公式及原子公式的否定統稱為文字 【定義41】任何文字的析取式稱為子句。 例如PQ、P（x，f(x)，y）Q(y)R(f(x) 都是子句 【定義42】不包含任何文字的子句稱為空子句，表示為NIL 由于空子句不包含有文字，它不能被任何解釋滿足，所以空子句是永假的，不可滿足的 由子句構成的集合稱為子句集 謂詞邏輯中，任何一個謂詞公式都可以化成一個子句集,2020/9/1,39,2 歸結反演系統,歸結原理 1子句 將謂詞公式化為子句集的步驟： (1)利用PQ = PQ；PQ =（P

23、Q）（PQ）等價關系消去蘊含符“”和雙條件符“” (2) 利用P = P；（PQ）= P Q；（PQ）= P Q；($x)P = (x)(P)；(x)P = ($x)(P)等價關系把否定符號“”移到緊靠謂詞位置上(3) 利用(x)P（x）= (y)P（y）；($x)P（x）= ($y)P（y）等價關系將變量標準化，即使每個量詞采用不同的變量 (4) 消去存在量詞$ 如果存在量詞不在任何一個全稱量詞的轄域內，則該存在量詞不依賴于任何其它的變量，因此可用一個新的個體常量代替 如將($x)P（x）化為P(A) 如果存在量詞是在全稱量詞的轄域內（如在公式(“y)（($x)P（x，y）中，變量x的取值依

24、賴于變量y的取值） 由Skolem函數表示依賴關系 注意，函數名應是原合式公式中沒有的符號 （續(xù)）,2020/9/1,40,2 歸結反演系統,歸結原理 1子句 將謂詞公式化為子句集的步驟： (5)將公式化為前束形把所有全稱量詞（已不留下任何存在量詞，而且每個全稱量詞都有自己的變量）移到公式的左邊，并使每個量詞的轄域包含這個量詞后面的整個部分，所得的公式稱為前束形 (6)利用P（QR）=（PQ）（PR）；（PQ）（PR）= P（QR）等價關系將母式化為合取范式（子句的合取式） (7)略去全稱量詞母式中的變量被默認為是全稱量詞量化的變量 (8)消去合取符號，把母式用子句集表示 如：PQ可表示為成子

25、句集： P Q (9)子句變量標準化重新命名變量，使每個子句中的變量符號不同,2020/9/1,41,2 歸結反演系統,歸結原理 1子句 【例41】將(x)P(x)Q(x)($ y)S(x,y)Q(x)(x)P(x)B(x)化成子句集 轉換過程遵照上述9個步驟： 錯 (1) (x)P（x）Q(x)($ y)S(x，y)Q(x)(x)P（x）B（x） (2) (x)P（x）Q(x)($ y)S(x，y)Q(x)(x)P（x）B（x） (3) (x)P（x）Q(x)($ y)S(x，y)Q(x)(w)P（w）B（w） (4) (x)P（x）Q(x )S(x，f (x) ) Q(x ) ( w) P

26、（w）B（w） (5) (x)(w)P（x）Q(x)S(x，f(x)Q(x)P（w）B（w） (6) (x)(w)P（x）S(x，f(x)Q(x)P（w）B（w） (7) P（x）S(x，f(x)Q(x)P（w）B（w） (8) 子句集為： P（x）S(x，f(x)）；Q(x)；P（w）B（w） (9) 子句變量標準化后，最終的子句集為： P（x）S（x，f(x)） Q（y） P（w）B（w）,2020/9/1,42,2 歸結反演系統,歸結原理 2置換和合一 為了使用推理規(guī)則，如假言推理、假言三段論等，一個推理系統必須決定兩個表達式是否相同或匹配： 兩個表達式匹配當且僅當其語法是等價的 一個表

27、達式的項可以是常量、變量或函數，合一就是尋找項對變量的置換而使表達式一致的過程，合一是人工智能中很重要的過程 如，為了使公式( x)P（x）與P（A）匹配，可以用常量A代替變量x，從而使兩個公式一致,2020/9/1,43,2 歸結反演系統,歸結原理 2置換和合一 置換可用有序對的集合s=t1/v1，t2/v2，tn/vn表示，其中ti/vi表示將表達式中所有的變量vi都用項ti代替，ti可以是變量、常量或函數 注意，一個變量不能用含有同一變量的項來代替 一般可用Es表示一個表達式E用一個置換s所得到的表達式的置換 如：P（z，f（w），A）= （P（x，f（y），A）s,2020/9/1,4

28、4,2 歸結反演系統,歸結原理 2置換和合一 例如有表達式P（x，f（y），A），通過不同的置換，可分別得到： P（z，f（w），A） 相應的置換為 s1 = z/x ，w/y P（x，f（B），A） 相應的置換為 s2 = B/ y P（g(z)，f（B），A） 相應的置換為 s3 = g(z)/x ，B /y P（C，f（B），A） 相應的置換為 s4 = C/x ，B/y ,2020/9/1,45,2 歸結反演系統,歸結原理 2置換和合一 置換是可結合的 用s1 s2表示兩個置換s1和 s2的合成，E表示一表達式，則有： （E s1）s2 = E（s1 s2） （s1 s2）s3= s1

29、（s2 s3） 把置換s作用于集合Ei中每一個公式得到的例的集合用Eis表示 如果存在一個置換s，使(E1)s=(E2)s=(E3)s=，則稱公式集Ei是可合一的，置換s稱為Ei的合一者 如：公式集P(x,f(y),B),P(x,f(B),B)的合一者為s = A/x,B/y,2020/9/1,46,2 歸結反演系統,歸結原理 2置換和合一 在P(x,f(y),B)s=P(x,f(B),B)s=P(A,f(B),B)s,s=A/x,B/y中，s并不是最簡單的，因置換B/y就可使上述公式集合一 如果s是Ei的任一合一者，又存在某個s，使得公式Eis=Eig s，則稱g為公式集Ei的最簡單合一者m

30、gu（Most General Unifier） 置換 B/y 為公式集P(x，f( y )，B), P(x , f(B)，B)的最簡單合一者,2020/9/1,47,2 歸結反演系統,歸結原理2置換和合一 最簡單的合一者的遞歸算法UNIFY（E1，E2） (1) if E1或E2是一個原子，如果有必要則交換E1和E2的位置，使E1是一個原子，do： (2) if E1和E2是相同的，return NIL (3) else if E1是個變量，do： (4) if E1出現在E2中，return FAIL else return E2/E1 (5) if E2是一個變量，return E1/E

31、2 else return FAIL (6) else F1E1的第一個元素，T1E1的其余元素 (7) F2E2的第一個元素，T2E2的其余元素 (8) Z1UNIFY（F1，F2） (9) if Z1 = FAIL, return FAIL (10) G1Z1作用到T1的結果 (11) G2Z1作用到T2的結果 (12) Z2UNIFY（G1，G2） (13) if Z2 = FAIL, return FAIL else Return Z1 和Z2的合成,2020/9/1,48,2 歸結反演系統,歸結原理 3歸結原理 歸結原理又稱為消解原理，它是定理證明基礎 由謂詞公式轉化為子句集的過程中

32、可以看出，在子句集中子句之間是合取關系，其中只要有一個子句不可滿足，則子句集就不可滿足。若一個子句集中包含空子句，則這個子句集一定是不可滿足的歸結原理就是基于這一認識提出來的 【定義43】若P是原子謂詞公式，則稱P與P為互補文字,2020/9/1,49,2 歸結反演系統,歸結原理 3歸結原理 (1) 基子句的歸結 所謂基子句，是指沒有變量的子句 【定義44】設C1與C2是子句集中的任意兩個基子句，如果C1中的文字L1與C2中的文字L2互補，那么從C1和C2中分別消去L1和L2，并將二個子句余下的部分析取，構成一個新子句C12，則稱一過程為歸結，稱C12為基子句C1和C2的歸結式，稱C1和C2為

33、C12的父輩子句,2020/9/1,50,2 歸結反演系統,歸結原理 3歸結原理 【例42】設C1=PQR，C2=PST歸結為： C12=QRST,2020/9/1,51,2 歸結反演系統,歸結原理 3歸結原理(多子句則逐步歸結) 【例43】設子句集S=PQ，QR，P，RT ，則其歸結過程如圖 歸結結果為T,2020/9/1,52,2 歸結反演系統,歸結原理 3歸結原理 (2)含有變量的子句的歸結 在謂詞邏輯中，子句中含有變量 為將歸結原理應用于含有變量的子句，應找出一個置換，作用于給定的兩個子句，使它們包括互補的文字，然后才能進行歸結 例:子句集S=P(x)Q(x)，P(A)R(y)，子句集

34、中的兩個子句不能直接歸結，但若對子句集先進行置換s=A/x，則兩個子句分別為P(A)Q(A)和P(A)R(y)，這時再進行歸結，歸結結果為Q(A)R(y),2020/9/1,53,2 歸結反演系統,歸結原理 3歸結原理 【定義45】設C1和C2是兩個沒有相同變量的子句，并分別表示成兩個文字集合Li和Mi，li是Li的一個子集，mi是Mi的一個子集，若s是集合li和mi的并集的最簡合一者，則稱 C12 = Li-lisMi-mi s 為C1和C2的歸結式。 當兩個子句作歸結時，子集li和mi的選取可能有多種形式，所以得到的歸結式不是唯一的,2020/9/1,54,2 歸結反演系統,歸結原理 3歸

35、結原理 例:設有兩個子句P(A)Q(x)R(x)和P(y)Q(B)，則由如下兩種歸結方法： 取li=P(A)，mi=P(y)，li和mi的最簡合一者為s=A/y，此時歸結結果為Q(x)R(x)Q(B) 取li=Q(x)，mi=Q(B)，li和mi的最簡合一者為s=B/x，此時歸結結果為P(A)R(B)P(y),2020/9/1,55,2 歸結反演系統,歸結原理 3歸結原理 例的歸結過程：,2020/9/1,56,2 歸結反演系統,歸結反演,初始公式,目標公式,初始子句集,目標子句,難；繁,初始子句集,空子句,可判定的！,永真：半可判定的,2020/9/1,57,2 歸結反演系統,歸結反演 歸結

36、反演就是利用歸結和反演實現定理的證明 具體過程： (1) 將定理證明的前提謂詞公式轉化為子句集F (2) 將求證的目標表示成合適的謂詞公式G（目標公式） (3)將目標公式的否定式G轉化成子句的形式，并加入到子句集F中，得到子句集S (4) 應用歸結原理對子句集中的子句進行歸結，并把每次歸結得到的歸結式都并入S中。如此反復進行，若歸結得到一個空子句NIL，則停止歸結 證明了G為真,2020/9/1,58,2 歸結反演系統,歸結反演 【例44】 已知前提為F:(x)P(x,y)Q(y)(y)R(y)S(x,y) 求證結論G:(x)R(x)(x)(y)P(x,y)Q(y)成立 證明：先按前面所講的方

37、法將前提和結論化為子句集： 前提F所對應的子句集為：P(x,y)Q(y)R(f(x) P(x,y)Q(y)S(x, f(x) 結論G否定對應子句集為：R(z) P(A,B) Q(B),2020/9/1,59,2 歸結反演系統,歸結反演 【例44】 歸結過程 經過歸結最后得到NIL， 所以結論G成立,2020/9/1,60,2 歸結反演系統,歸結反演 【例45】已知: 能閱讀的都是有文化的; 海豚是沒有文化的; 某些海豚是有智能的; 用歸結反演法證明:某些有智能的并不能閱讀 證明：設 R(x)：x能閱讀 L(x): x有文化 D(x): x是海豚 I(x): x有智能,2020/9/1,61,2

38、 歸結反演系統,歸結反演 【例45】 將前提形式化地表示為： (x)（R(x)L(x)） (y)（D(y) L(y)） (z)（D(z)I(z) 將結論形式化地表示為： (w)(I(w)R(w) 首先將前提化成子句集： R(x)L(x) D(y) L(y) D(A) I(A) 將結論的否定式為化成子句：I(w)R(w),2020/9/1,62,2 歸結反演系統,歸結反演 【例45】 歸結后得到空子句NIL， 證明完畢,2020/9/1,63,2 歸結反演系統,歸結反演 歸結反演過程主要就是證明一個集合S是不可滿足的過程，即從集合S中歸結出空子句的過程 算法描述： 過程RESOLUTION (1

39、) CLAUSESS (2) Until NIL是CLAUSES的成員，do: (3) Begin (4) 在CLAUSES中選擇兩個不同的可歸結的子句Ci和Cj (5) 計算Ci和Cj的歸結式Cij (6) CLAUSES附加Cij到CLAUSES產生的子句集 （7）end,2020/9/1,64,2 歸結反演系統,歸結反演的控制策略 對子句集進行歸結時，關鍵的一步是從子句集中找出可進行歸結的子句 由于事先不知道哪兩個子句可以進行歸結，更不知道通過對哪些子句對的歸結可以盡快地得到空子句，因而必須對子句集中的所有子句逐對地進行比較，對任何一對可歸結的子句對都進行歸結，這樣的效率是很低的 歸結反

40、演的控制策略,2020/9/1,65,2 歸結反演系統,歸結反演的控制策略 1寬度優(yōu)先策略 基本思想：首先從基本子句集生成所有的歸結式，稱為第一級歸結式。在這一輪歸結中，子句集中的每個子句都要和子句集中的其它子句比較以確定是否進行歸結。然后，從基本子句集和第一級歸結式生成第二級歸結式。以此類推，直到出現了空子句或者不能再歸結為止 寬度優(yōu)先策略是完備的，但會歸結出許多無用的子句，而且有一些歸結式還是重復的，所以是低效的，即浪費時間又多占空間,2020/9/1,66,2 歸結反演系統,歸結反演的控制策略 1寬度優(yōu)先策略,2020/9/1,67,2 歸結反演系統,歸結反演的控制策略 2支持集策略 支

41、持集策略是一種改進的歸結策略 對參加歸結的子句提出了如下限制：每一次歸結時，其父輩子句中至少有一個是由目標公式的否定所得到的子句或者是它們的后代（即支持集） 可以證明，支持集策略是完備的，即若子句集是不可滿足的，則由支持集策略一定可以歸結出空子句 支持集策略相當于在寬度優(yōu)先策略中引入了約束條件，因此效率比寬度優(yōu)先策略要高,2020/9/1,68,2 歸結反演系統,歸結反演的控制策略2支持集策略,2020/9/1,69,2 歸結反演系統,歸結反演的控制策略 3單文字子句優(yōu)先策略 如果一個子句只包含一個文字，則稱它為單文字子句 單文字子句優(yōu)先策略要求參加歸結的子句中必須至少有一個是單文字子句 每次

42、歸結時優(yōu)先選擇單文字子句進行歸結，所以得到的歸結式的文字數目必然比其另外一個父輩子句少。這有利于歸結式向空子句的方向生成，提高了效率,2020/9/1,70,2 歸結反演系統,歸結反演的控制策略 3單文字子句優(yōu)先策略,2020/9/1,71,2 歸結反演系統,歸結反演的控制策略 4線性輸入形策略 歸結策略對參加歸結的子句提出了如下限制：參加歸結的兩個子句中必須至少有一個是基本子句集中的子句 線性輸入形策略可提高效率，但不完備(祖先過濾策略能使之完備） 例見下頁 其它的歸結策略如祖先過濾策略、模型策略、有序策略等。在具體應用中可根據實際情況選擇適當的歸結策略，有時可把幾種策略組合在一起使用,20

43、20/9/1,72,2 歸結反演系統,歸結反演的控制策略 4線性輸入形策略,2020/9/1,73,2 歸結反演系統,應用歸結反演求取問題的答案 歸結反演除了可用于定理證明外，還可用來求取問題的答案，其思想與定理證明類似 用歸結反演求取問題答案的一般步驟是： (1) 把已知前提用謂詞公式表示出來，并且化為子句集，設該子句集為S (2) 把目標也用謂詞公式表示出來 (3)在目標公式的否定的子句形式中，附加上該子句的否定（即目標公式否定之否定）。然后一起加入到子句集S中，得到子句集S (4) 對S進行歸結，形成歸結反演樹修改的證明樹 (5) 用根部的子句作為解答子句,2020/9/1,74,2 歸

44、結反演系統,應用歸結反演求取問題的答案 【例46】已知：F1：王(Wang)先生是小李(Li)的老師， F2：小李與小張(Zhang)是同班同學。 F3：如果x和y是同班同學，則x的老師就是y的老師 求：小張的老師是誰？ 解：先定義謂詞：T（x，y）：x是y的老師 C（x，y）：x與y是同班同學 把已知前提及目標表示成謂詞公式： 前提 F1：T（Wang，Li） F2：C（ Li，Zhang） F3：C（x，y）T（z，x）T（z，y） 目標 G：(x)T(x，Zhang) G的否定：(x)T(x，Zhang),2020/9/1,75,2 歸結反演系統,應用歸結反演求取問題的答案 【例46】將

45、以上前提和目標的否定化成子句集： F1:T(Wang,Li) F2:C(Li,Zhang) F3:C(x,y)T(z,x)T(z,y) 目標重言式：T(u,Zhang)T(u,Zhang) 根部子句：T(Wang,Zhang)， 這就是答案， 表示小張（Zhang）的老師是王（Wang）,2020/9/1,76,2 歸結反演系統,應用歸結反演求取問題的答案 【例47】已知事實如下： (1) 對所有的x和y，如果x是y的父輩而y是z的父輩，則x是z的祖輩。 (2) 每個人都有父輩。 問：是否存在具體的x和y，使得x是y的祖輩？ 解：先定義謂詞： P（x，y）：x是y的父輩 G（x，y）：x是y的

46、祖輩 把已知前提及目標表示成謂詞公式： 前提1：P（x，y）P（y，z）G(x，z) 前提2：（y）（x）P（x，y） 目標G：（x）（y）G（x，y） G的否定：（x）（y）G（x，y）,2020/9/1,77,2 歸結反演系統,應用歸結反演求取問題的答案 【例47】將前提和目標的否定化成子句集： 前提1：P（x，y） P（y，z）G(x，z) 前提2：P（f(w)，w） G的否定： G（u，v） 把它添加到目標公式否定之否定的子句中去，得到重言式： G（u，v）G（u，v）。 通過歸結，在根部得到子句：G(f(f(v)，v)，這就是答案，表示v的父輩的父輩就為v的祖輩,2020/9/1,7

47、8,2 歸結反演系統,應用歸結反演求取問題的答案 【例47】,2020/9/1,79,2 歸結反演系統,應用歸結反演求取問題的答案 目標公式中含有全稱量詞稍復雜些 基于歸結原理的歸結反演推理比較簡單且又便于在計算機上實現，所以對自動定理證明領域影響較大。但是歸結反演要求把前提、結論等所有邏輯表達式轉化為子句集，因此喪失了許多有用的信息 如邏輯式PQ與子句PQ在邏輯上是等價的，但它們所表達的信息是不同的，相比之下，PQ的含義更易于理解 提出多種非子句定理證明方法 如自然演繹和基于規(guī)則的演繹法等,2020/9/1,80,3 基于規(guī)則的演繹推理,知識一般是由蘊含式直接表示的，但在歸結反演中，必須首先

48、將它們轉化為子句的形式，所以這種推理是比較低效的 基于規(guī)則的演繹推理則是一種直接的推理方法。它不再把有關的知識轉化為子句集，而是把有關問題的知識和信息劃分為規(guī)則與事實兩種類型 規(guī)則：包含蘊含形式的表達式表示 事實：無蘊含式的表達式表示 畫出相應的與/或圖，然后通過規(guī)則進行演繹推理,2020/9/1,81,3 基于規(guī)則的演繹推理,基于規(guī)則的演繹推理可分為正向演繹推理、反向演繹推理和正反向混合演繹推理 在正向演繹推理中，作為F規(guī)則用的蘊含式對事實的總數據庫進行操作運算，直至得到該目標公式的一個終止條件為止 在反向演繹推理中，作為B規(guī)則用的蘊含式對目標的總數據庫進行操作運算，直至得到包含這些事實的終

49、止條件為止 在雙向演繹推理中，分別從兩個方向應用不同的規(guī)則（F規(guī)則和B規(guī)則）進行操作運算,2020/9/1,82,3 基于規(guī)則的演繹推理,正向演繹推理 正向演繹推理對應于41中介紹的正向推理，它是從已知事實出發(fā)，反復嘗試所有可利用的規(guī)則（F規(guī)則）進行演繹推理，直至得到某個目標公式的一個終止條件為止,2020/9/1,83,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實表達式及其與或圖表示 正向演繹要求事實用不包含蘊含符號“”的與/或形表示 一個表達式轉化為標準的與/或形的步驟如下： 利用等價式PQ與PQ消去蘊含符“” 把否定符號“”移到每個謂詞符號的前面 變量標準化，即重新命名變量，使不同量

50、詞約束變量有不同的名字 引入Skolem函數消去存在量詞 將公式化為前束形 略去全稱量詞(默認事實表達式中尚存的變量是全稱量詞量化的變量) 重新命名變量，使同一變量不出現在不同的主要合取式中,2020/9/1,84,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實表達式及其與或圖表示 如表達式:（x）(y)Q(y,x)(R(y)P(y)S(x，y) 轉化為標準的與/或形: Q(z,A) R(y) P(y) S(A，y) 事實表達式的標準與/或形樹:,2020/9/1,85,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實表達式及其與或圖表示 在與/或圖中，結點表示事實表達式及其子表達式 根結點

51、表示整個表達式，葉結點表示表達式中的單個文字 對于一個表示析取表達式（E1E2En）的結點，用一個n連接符（圖中的半圓?。┻B接它的n個子表達式結點； 對于一個表示合取表達式（E1E2En）的結點，則直接用單線連接符與它的n個子表達式結點相連 事實表達式:用n連接符（一個合取記號）來分解析取式,2020/9/1,86,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實表達式及其與或圖表示 一重要性質：由變換表達式得到的一組子句則可從與或圖中讀出，每子句相當于與/或圖的一個解圖，每個子句是由葉結點組成的公式 從上上頁可以讀出上例表達式的三個子句： Q(z,A) S(A，y) R(y) S(A，y)

52、P(y) 這三個子句正是原表達式化成的子句集與/或圖可看成是一組子句的一個簡潔的表達形式,2020/9/1,87,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 基于規(guī)則的正向演繹推理中，通常要求F規(guī)則具有以下形式： L W 具體要求如下： L是單文字，W是任意的與或形表達式 L和W中的所有變量都是全稱量詞量化的，默認的全稱量詞作用于整個蘊含式 各條規(guī)則的變量各不相同，而且規(guī)則中的變量與事實表達式中的變量也不相同,2020/9/1,88,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 將F規(guī)則的左部限制為單文字，是因為在進行演繹推理時，要用F規(guī)則作用于表示事實的與/

53、或圖，而該與/或圖的葉結點都是單文字，這樣就可用F規(guī)則的左部與葉結點進行匹配，大大簡化了規(guī)則的應用過程,2020/9/1,89,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 變換成標準形式的步驟： 暫時消去蘊含符號“” 把否定號“”移到每個謂詞的前面 引入Skolem函數消去存在量詞 將公式化為前束形，并略去全稱量詞 恢復為蘊含式,2020/9/1,90,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 變換成標準形式的例： 原公式(x)(y)(z)P(x,y,z)(u)Q(x,u) 消蘊含符(x)(y)(z)P(x,y,z)(u)Q(x,u) 否定號移入(x)(y

54、)(z)P(x,y,z)(u)Q(x,u) Skolem函數(x)(y)P(x,y,f(x,y)(u)Q(x,u) 前束形/略全稱量詞P(x,y,f(x,y)Q(x,u) 恢復蘊含式P(x,y,f(x,y)Q(x,u),2020/9/1,91,3 基于規(guī)則的演繹推理,正向演繹推理 （3）目標公式的表示形式 在基于規(guī)則的正向演繹推理中，要求目標公式用子句表示，否則就要化成子句形式,2020/9/1,92,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過程 基于規(guī)則的正向演繹推理應用F規(guī)則作用于表示事實的與/或圖，改變與/或圖的結構，從而產生新的事實，直至推出了目標公式，則推理就成功結束 正向演

55、繹中的目標公式規(guī)定為文字的析取式，當一個目標文字和與/或圖中的一個文字匹配時，可以將表示該目標文字的結點通過匹配弧連接到與/或圖中相應的文字的結點上 表示目標文字的結點為目標結點，當演繹產生的與/或圖包括一個在目標結點上結束的解圖時，推理便成功結束,2020/9/1,93,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過程 推理過程為： 首先用與/或圖把已知事實表示出來 用F規(guī)則的左部和與/或圖的葉結點進行匹配，并將匹配成功的F規(guī)則加入到與/或圖中，即利用F規(guī)則轉換與/或圖 重復第步，直到產生一個含有以目標結點作為終止結點的解圖為止,2020/9/1,94,3 基于規(guī)則的演繹推理,正向演繹推

56、理 （4）推理過程 【例48】設已知事實為：AB F規(guī)則為：ACD ，BEG 目標公式為：CGF 證明：1.將事實表達式用與/或圖表示,2020/9/1,95,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過程 【例48】證明 2.用F規(guī)則的左部與上頁中的葉結點匹配，并轉換與或圖新與/或圖 圖中包括一個在目標結點上結束的解圖，該解圖對應的子句為CG（注意此子句與目標公式CGF不同，但比目標公式更一般，所以目標公式成立）,2020/9/1,96,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過程 【例48】證明,2020/9/1,97,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過程 【

57、例48】驗證其推理的正確性，再用歸結反演來證明 由已知事實、F規(guī)則及目標的 否定所構成的子句集為： AB AC，AD BE，BG C，G，F 子句的歸結過程：（歸結得空子句NIL）,2020/9/1,98,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達式 如果事實表達式、規(guī)則和目標表達式中有變量，則在推理中需要用最一般的合一進行變量的代換,2020/9/1,99,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達式 【例49】設已知 事實為： P(A)Q(A)R(A) F規(guī)則為：R1：P(x)S(x) R2：Q(y)N(y) 證明目標公式：S(z)N(z) 證明： 解圖對應

58、的子句為： S(z) N(z),2020/9/1,100,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達式 【例49】驗證（歸結反演） 已知事實、F規(guī)則及目標的否定 所構成的子句集為： P(A)Q(A)，P(A)R(A) P(x)S(x) Q(y)N(y) S(z)，N(z) 歸結反演圖： 歸結出空子句，證明目標公式成立,2020/9/1,101,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達式 當事實表達式、F規(guī)則和目標表達式中包含變量時，只有當解圖中所用的置換是一致時，該解圖對應的子句才成立 在【例49】解圖中使用的置換A/x，A/z和A/y，A/z是一致的，所以該

59、子句成立 將兩個置換的合一復合A/x，A/y，A/z作用于子句S(z)N(z)得到：S(A)N(A)，這才是真正的結論,2020/9/1,102,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達式 【定義46】設有一個置換集U=u1,u2,un ,每個ui是一個置換對的集合， ui=ti1/vi1 , ti2 /vi2, , tim (i)/vim(i) 其中t為項，v為變量， 令： U1=( v11, ,v1m(1),v21, ,v2m(2) ,vnm(n) U2=( t11, , t1m(1), t21, , t2m(2) ,tnm(n) 則置換U是一致的充要條件是U1和U2可合一。而U的合一復合u=mgu(U1,U2),2020/9/1,103,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達式 置換的一致性和置換的合一復合例： 1)u1=A/x,A/z, u2=A/y, A/z, 則U=u1，u2是一致的，其合一復合為 A/x，A/y, A/z 2)u