1、1,第4章 確定性推理,智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。對于推理的這兩種不同類型，本章重點討論前一種，不確定性推理放到下一章討論。 4.1 推理的基本概念 4.2 推理的邏輯基礎 4.3 自然演繹推理 4.4 歸結演繹推理 4.5 基于規(guī)則的演繹推理,2,4.1 推理的基本概念,4.1.1 什么是推理 4.1.2 推理方法及其分類 4.1.3 推理的控制策略及其分類 4.1.4 正向推理 4.1.5 逆向推理 4.1.6 混合推理,3,4.1.1 什么是推理,推理的概念 是指按照某種策略從已知事實出發(fā)去推出結論的過程。

2、 推理所用的事實： 初始證據(jù)：推理前用戶提供的 中間結論：推理過程中所得到的 推理過程：由推理機來完成，所謂推理機就是智能系統(tǒng)中用來實現(xiàn)推理的那些程序。 例如，醫(yī)療專家系統(tǒng)，專家知識保存在知識庫中。推理開始時，先把病人的癥狀和檢查結果放到綜合數(shù)據(jù)庫中，然后再從綜合數(shù)據(jù)庫的初始證據(jù)出發(fā)，按照某種策略在知識庫中尋找，并使用知識，直到推出最終結論為止。 推理的兩個基本問題 推理的方法：解決前提和結論的邏輯關系，不確定性傳遞 推理的控制策略：解決推理方向，沖突消解策略,4,4.1.2 推理方法及其分類1. 按推理的邏輯基礎分類(1/4),可分為演繹推理、歸納推理等 演繹推理 演繹推理是從已知的一般性知

3、識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結論。是一種由一般到個別的推理方法，其核心是三段論，如假言推理、拒取式和假言三段論。 例： 假言三段論 AB，BC AC 常用的三段論是由一個大前提、一個小前提和一個結論這三部分組成的。其中，大前提是已知的一般性知識或推理過程得到的判斷；小前提是關于某種具體情況或某個具體實例的判斷；結論是由大前提推出的，并且適合于小前提的判斷。 例如，有如下三個判斷： 計算機系的學生都會編程序； （一般性知識） 程強是計算機系的一位學生； （具體情況） 程強會編程序。 （結論） 這是一個三段論推理。其中，是大前提，是小前提；是經(jīng)演繹推出來的結論。 可見，

4、其結論是蘊含在大前提中的。,5,4.1.2 推理方法及其分類1. 按推理的邏輯基礎分類(2/4),歸納推理 是一種由個別到一般的推理方法。歸納推理的類型 按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理 按照推理所使用的方法可分為枚舉、類比、統(tǒng)計和差異歸納推理等 完全歸納推理 是指在進行歸納時需要考察相應事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。如，計算機質量檢驗。 不完全歸納推理 是指在進行歸納時只考察了相應事物的部分對象，就得出了關于該事物的結論。例如，計算機，隨機抽查。 枚舉歸納推理 是指在進行歸納時，如果已知某類事物的有限可數(shù)個具體事物都具有某

5、種屬性，則可推出該類事物都具有此種屬性。 例如，設有如下事例： 王強是計算機系學生，他會編程序； 高華是計算機系學生，她會編程序； 當這些具體事例足夠多時，就可歸納出一個一般性的知識： 凡是計算機系的學生，就一定會編程序。,6,4.1.2 推理方法及其分類1. 按推理的邏輯基礎分類(3/4),類比歸納推理 是指在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它們在其他屬性上也相同或相似的一種歸納推理。 設A、B分別是兩類事物的集合： A=a1,a2, B=b1,b2, 并設ai與bi總是成對出現(xiàn)，且當ai有屬性P時，bi就有屬性Q與此對應，即 P(ai)Q(bi) i=1,2,. 則當A與

6、B中有一新的元素對出現(xiàn)時，若已知a有屬性P，b有屬性Q，即 P(a)Q(b) 類比歸納推理的基礎是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關程度。,7,4.1.2 推理方法及其分類 1. 按推理的邏輯基礎分類(4/4),演繹推理與歸納推理的區(qū)別 演繹推理是在已知領域內的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結論的正確性。它所得出的結論實際上早已蘊含在一般性知識的前提中，演繹推理只不過是將已有事實揭露出來，因此它不能增殖新知識。 歸納推理所推出的結論是沒有包含在前提內容中的。這種由個別事物或現(xiàn)象推出一般性知識的過程

7、，是增殖新知識的過程。 例如，一位計算機維修員，從書本知識，到通過大量實例積累經(jīng)驗，是一種歸納推理方式。運用這些一般性知識知識去維修計算機的過程則是演繹推理。,8,4.1.3 推理的控制策略及其分類,推理的控制策略 推理過程不僅依賴于所用的推方法，同時也依賴于推理的控制策略。 推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策略。 控制策略的分類 由于智能系統(tǒng)的推理過程一般表現(xiàn)為一種搜索過程，因此，推理的控制策略又可分為推理策略和搜索策略。 推理策略 主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等 推理方向控制策略用于確定推理的控制方向，可分

8、為正向推理、逆向推理、混合推理及雙向推理。 求解策略是指僅求一個解，還是求所有解或最優(yōu)解等。 限制策略是指對推理的深度、寬度、時間、空間等進行的限制。 沖突消解策略是指當推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。 搜索策略 主要解決推理線路、推理效果、推理效率等問題。 本章主要討論推理策略，,9,4.1.4 正向推理推理算法,從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅動推理或前向鏈推理。 算法描述 (1) 把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫； (2) 檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若已包含，則求解結束，并成功推出；否則執(zhí)行下一步； (3) 檢查知

9、識庫中是否有可用知識，若有，形成當前可用知識集，執(zhí)行下一步；否則轉(5)。 (4) 按照某種沖突消解策略，從當前可用知識集中選出一條規(guī)則進行推理，并將推出的新事實加入綜合數(shù)據(jù)庫種，然后轉(2)。 (5) 詢問用戶是否可以進一步補充新的事實，若可補充，則將補充的新事實加入綜合數(shù)據(jù)庫中，然后轉(3)；否則表示無解，失敗退出。 至于如何根據(jù)綜合數(shù)據(jù)庫中的事實到知識庫中選取可用知識，當知識庫中有多條知識可用時應該先使用那一條知識等。這些問題涉及到了知識的匹配方法和沖突消解策略，以后將會分別討論。 其流程圖如下：,10,把初始證據(jù)放入DB,DB中有解嗎？,KB中有可用知識嗎？,形成可用知識集,可用知識集

10、空嗎？,按照沖突消解策略從該知識 集中選出一條知識進行推理,推出的是新事實嗎？,將新事實加入到DB,把用戶補充的新事 實加入到DB中,用戶可補充新事實嗎？,失敗退出,成功退出,Y,N,N,Y,N,N,N,Y,Y,Y,11,4.1.4 正向推理推理例子,例4.1請用正向推理完成以下問題的求解 假設知識庫中包含有以下2條規(guī)則： r1： IF B THEN C r2： IF A THEN B 已知初始證據(jù)A，求證目標C。 解：本例的推理過程如下： 推理開始前，綜合數(shù)據(jù)庫為空。 推理開始后，先把A放入綜合數(shù)據(jù)庫，然后檢查綜合數(shù)據(jù)庫中是否含有該問題的解，回答為“N”。 接著檢查知識庫中是否有可用知識，顯

11、然r2可用，形成僅含r2的知識集。從該知識集中取出r2，推出新的實事B，將B加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標C，回答為“N”。 再檢查知識庫中是否有可用知識，此時由于B的加入使得r1為可用，形成僅含r1的知識集。從該知識集中取出r1，推出新的實事C，將C加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標C，回答為“Y”。 它說明綜合數(shù)據(jù)庫中已經(jīng)含有問題的解，推理成功結束，目標C得證。,12,4.1.4 正向推理優(yōu)缺點,正向推理的主要優(yōu)點 比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設計、預測、監(jiān)控等領域的問題求解。 正向推理的主要缺點 推理無明確目標，求解問題是可能會執(zhí)行許多與

12、解無關的操作，導致推理效率較低。,13,4.1.5 逆向推理推理算法,從某個假設目標出發(fā)，逆向使用規(guī)則，亦稱為目標驅動推理或逆向鏈推理。 算法描述： (1) 將要求證的目標（稱為假設）構成一個假設集； (2) 從假設集中選出一個假設，檢查該假設是否在綜合數(shù)據(jù)庫中，若在，則該假設成立，此時，若假設集為空，則成功退出，否則仍執(zhí)行(2)；若該假設不在數(shù)據(jù)庫中，則執(zhí)行下一步； (3) 檢查該假設是否可由知識庫的某個知識導出，若不能由某個知識導出，則詢問用戶該假設是否為可由用戶證實的原始事實，若是，該假設成立，并將其放入綜合數(shù)據(jù)庫，再重新尋找新的假設，若不是，則轉(5)；若能由某個知識導出，則執(zhí)行下一步

13、； (4) 將知識庫中可以導出該假設的所有知識構成一個可用知識集； (5) 檢查可用知識集是否為空，若是，失敗退出；否則執(zhí)行下一步； (6) 按沖突消解策略從可用知識集中取出一個知識，繼續(xù)； (7) 將該知識的前提中的每個子條件都作為新的假設放入假設集，然后轉(2)。 其流程圖如下：,14,初始化DB和假設集,該假設是DB中的事實嗎？,該假設能被KB中的知識導出嗎？,從假設集中取出一個假設,可用知識集空嗎？,按照沖突消解策略從該知識集中選出一條知識,將該知識前提中的每個子條件作為新的假設加入假設集,該假設成立 并放入DB,還有新的假設嗎？,失敗退出,成功退出,Y,N,Y,Y,N,N,N,N,Y

14、,將KB中所有能導出此假設的知識構成一個可用知識集,詢問用戶有此事實嗎？,該假設 成立,Y,15,4.1.5 逆向推理推理例子,對上例，采用逆向推理，其推理過程如下： 推理開始前，綜合數(shù)據(jù)庫和假設集均為空。 推理開始后，先將初始證據(jù)A和目標C分別放入綜合數(shù)據(jù)庫和假設集，然后從假設集中取出一個假設C，查找C是否為綜合數(shù)據(jù)庫中的已知事實，回答為“N”。 再檢查C是否能被知識庫中的知識所導出，發(fā)現(xiàn)C可由r1導出，于是r1被放入可用知識集。由于知識庫中只有r1可用，故可用知識集中僅含r1。 接著從可用知識集中取出r1，將其前提條件B作為新的假設放入假設集。從假設集中取出B，檢查B是否為綜合數(shù)據(jù)庫中的實

15、事，回答為“N”。再檢查B是否能被知識庫中的知識所導出，發(fā)現(xiàn)B可由r2導出，于是r2被放入可用知識集。由于知識庫中只有r2可用，故可用知識集中僅含r2。 從可用知識集中取出r2，將其前提條件A作為新的假設放入假設集。然后從假設集中取出A，檢查A是否為綜合數(shù)據(jù)庫中的實事，回答為“Y”。 他說明該假設成立，由于無新的假設，故推理過程成功結束，于是目標C得證。,16,4.1.5 逆向推理優(yōu)缺點,逆向推理的主要優(yōu)點 不必尋找和使用那些與假設目標無關的信息和知識 推理過程的目標明確 也有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。 逆向推理的主要缺點 當用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設目

16、標的盲目性比較大，若選擇不好，可能需要多次提出假設，會影響系統(tǒng)效率。,17,4.1.6 混合推理,混合推理的概念 把正向推理和逆向推理結合起來所進行的推理稱為混合推理。是一種解決較復雜問題的方法。 混合推理的方法 1. 先正向后逆向 這種方法先進行正向推理，從已知事實出發(fā)推出部分結果，然后再用逆向推理對這些結果進行證實或提高它們的可信度。 2. 先逆向后正向 這種方法先進行逆向推理，從假設目標出發(fā)推出一些中間假設，然后再用正向推理對這些中間假設進行證實。 3. 雙向混合 是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結合起來。 對于這些方法我不再詳細討論。,18,第4章 確定性推理,

17、4.1 推理的基本概念 4.2 推理的邏輯基礎 4.3 自然演繹推理 4.4 歸結演繹推理 4.5 基于規(guī)則的演繹推理,19,4.2 推理的邏輯基礎,4.2.1 謂詞公式的解釋 4.2.2 謂詞公式的永真性和可滿足性 4.2.3 謂詞公式的等價性和永真蘊含性 4.2.4 謂詞公式的范式 4.2.5 置換與合一,20,4.2.1 謂詞公式的解釋概念,命題公式的解釋 在命題邏輯中，命題公式的一個解釋就是對該命題公式中各個命題變元的一次真值指派。 有了命題公式的解釋，就可據(jù)此求出該命題公式的真值。 謂詞公式的解釋 由于謂詞公式中可能包含由個體常量、變元或函數(shù)，因此，必須先考慮這些個體常量和函數(shù)在個體

18、域上的取值，然后才能根據(jù)它們的具體取值為謂詞分別指派真值。 定義4.1 設D是謂詞公式P的非空個體域，若對P中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值： (1) 為每個個體常量指派D中的一個元素； (2) 為每個n元函數(shù)指派一個從Dn到D的一個映射，其中 Dn =(x1, x2, , xn)| x1, x2, , xnD (3) 為每個n元謂詞指派一個從Dn到F，T的映射。 則稱這些指派為P在D上的一個解釋I,21,4.2.1 謂詞公式的解釋 例子一(1/2),例4.2 設個體域D=1, 2，求公式A=(x)( y)P(x, y)在D上的解釋，并指出在每一種解釋下公式A的真值。 解：由于公式A中沒

19、有包含個體常量和函數(shù)，故可直接為謂詞指派真值，設有 這就是公式A 在D 上的一個解釋。從這個解釋可以看出： 當x=1、y=1時，有P(x,y)的真值為T; 當x=2、y=1時，有P(x,y)的真值為T; 即對x在D上的任意取值，都存在y=1使P(x,y)的真值為T。因此，在此解釋下公式A的真值為T。,22,4.2.1 謂詞公式的解釋 例子一(2/2),說明：一個謂詞公式在其個體域上的解釋不是唯一的。例如，對公式A，若給出另一組真值指派 這也是公式A 在D 上的一個解釋。從這個解釋可以看出： 當x=1、y=1時，有P(x,y)的真值為T; 當x=2、y=1時，有P(x,y)的真值為F; 即對x在

20、D上的任意取值，不存在一個y使得P(x,y)的真值為T。因此，在此解釋下公式A的真值為F。 實際上，A在D上共有16種解釋，這里就不在一一列舉。,23,4.2.1 謂詞公式的解釋 例子二,例4.3 設個體域D=1, 2，求公式B=(x)P(f(x), a)在D上的解釋，并指出在該解釋下公式B的真值。 解：設對個體常量a和函數(shù)f(x)的值指派為： 對謂詞的真值指派為： 由于已指派a=1，因此P(1,2)和P(2,2)不可能出現(xiàn)，故沒給它們指派真值。 上述指派是公式B在D上的一個解釋。在此解釋下有 當x=1時，a=1使P(1,1)=T 當x=2時，a=1使P(2,1)=T 即對x在D上的任意取值，

21、都存在a=1使P(f(x), a)的真值為T。因此，在此解釋下公式B的真值為T。 由上面的例子可以看出，謂詞公式的真值都是針對某一個解釋而言的，它可能在某一個解釋下真值為T，而在另一個解釋下為F。,24,4.2.2 謂詞公式的永真性和可滿足性,為了以后推理的需要，下面先定義： 定義4.2 如果謂詞公式P對非空個體域D上的任一解釋都取得真值T，則稱P在D 上是永真的；如果P在任何非空個體域上均是永真的，則稱P永真。 可見，要判定一謂詞公式為永真，必須對每個非空個體域上的每個解釋逐一進行判斷。當解釋的個數(shù)為有限時，盡管工作量大，公式的永真性畢竟還可以判定，但當解釋個數(shù)為無限時，其永真性就很難判定了

22、。 定義4.3 對于謂詞公式P，如果至少存在D上的一個解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。 謂詞公式的可滿足性也稱為相容性。 定義4.4 如果謂詞公式P對非空個體域D上的任一解釋都取真值F，則稱P在D上是永假的；如果P在任何非空個體域上均是永假的，則稱P永假。 謂詞公式的永假性又稱不可滿足性或不相容。 后面我們要給出的歸結推理，就是采用一種邏輯上的反證法，將永真性轉換為不可滿足性的證明。,25,4.2.3 謂詞公式的等價性和永真蘊含性1. 等價式(1/2),謂詞公式的等價性和永真蘊含性可分別用相應的等價式和永真蘊含式來表示，這些等價式和永真蘊含式都是演繹推理的主要依

23、據(jù)，因此也稱它們?yōu)橥评硪?guī)則。 謂詞公式的等價式可定義如下： 定義4.5 設P與Q是D上的兩個謂詞公式，若對D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D 上是等價的。如果D是任意非空個體域，則稱P與Q是等價的，記作PQ。,26,4.2.3 謂詞公式的等價性和永真蘊含性 1. 等價式(2/2),(1) 雙重否定律 P P (2) 交換律 (PQ) (QP)， ( PQ) ( QP) (3) 結合律 (PQ)R P(QR) (PQ)R P(QR) (4) 分配律 P(QR) (PQ)(PR) P(QR) (PQ)(PR) (5) 摩根定律 (PQ) PQ (PQ) PQ (6) 吸收律 P(

24、PQ) P P(PQ) P (7) 補余律 PP T, PP F (8) 連詞化歸律 PQ PQ PQ (PQ)(QP) PQ (PQ)(QP) (9) 量詞轉換律 (x)P (x)( P) (x)P (x) ( P) (10) 量詞分配律 (x) (PQ) (x)P(x)Q (x) (PQ) (x)P(x)Q,27,4.2.3 謂詞公式的等價性和永真蘊含性2. 永真蘊含式,定義4.6 對謂詞公式P和Q，如果PQ永真，則稱P 永真蘊含Q，且稱Q為P的邏輯結論，P為Q的前提，記作P Q。 常用的永真蘊含式如下： (1) 化簡式 PQ P， PQ Q (2) 附加式 P PQ， Q PQ (3)

25、析取三段論 P, PQ Q (4) 假言推理 P, PQ Q (5) 拒取式 Q, PQ P (6) 假言三段論 PQ, QR PR (7) 二難推理 PQ, PR, QR R (8) 全稱固化 (x)P(x) P(y) 其中，y是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。 (9) 存在固化 (x)P(x) P(y) 其中，y是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公式中的存在量詞。,28,4.2.4 謂詞公式的范式,范式是謂詞公式的標準形式。在謂詞邏輯中，范式分為兩種： 前束范式 定義4.7 設F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，且它們的

26、轄域為整個公式，則稱F為前束范式。一般形式： (Q1x1)(Qnxn)M(x1,x2,xn) 其中，Qi(i=1,2,n)為前綴，它是一個由全稱量詞或存在量詞組成的量詞串； M(x1,x2,xn)為母式，它是一個不含任何量詞的謂詞公式。 例如，(x) (y) (z)(P(x)Q(y,z)R(x,z)是前束范式。 任一謂詞公式均可化為與其對應的前束范式，其化簡方法將在后面子句集的化簡中討論。 Skolem范式 定義4.8 如果前束范式中所有的存在量詞都在全稱量詞之前，則稱這種形式的謂詞公式為Skolem范式。 例如，(x) (z) (y)(P(x)Q(y,z)R(x,z)是Skolem范式。 任

27、一謂詞公式均可化為與其對應的Skolem范式，其化簡方法也將在后面子句集的化簡中討論。,29,4.2.5 置換與合一概念,在不同謂詞公式中，往往會出現(xiàn)謂詞名相同但其個體不同的情況，此時推理過程是不能直接進行匹配的，需要先進行置換。 例如，可根據(jù)全稱固化推理和假言推理由謂詞公式 W1(A) 和 (x)(W1(x)W2(x) 推出W2(A)。對謂詞W1(A)可看作是由全程固化推理（即(x)(W1(x) W1(A)推出的，其中A是任一個體常量。要使用假言推理，首先需要找到項A對變元x的置換，使W1(A)與W1(x)一致。 這種尋找項對變元的置換，使謂詞一致的過程叫做合一的過程。 下面討論置換與合一的

28、有關概念與方法。,30,4.2.5 置換與合一1. 置換(1/2),置換可簡單的理解為是在一個謂詞公式中用置換項去替換變量。 定義4.9 置換是形如 t1/x1,t2/x2,tn/xn 的有限集合。其中，t1,t2,tn是項；x1,x2,xn是互不相同的變元；ti/xi表示用ti替換xi。并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個ti中。 例如， a/x, c/y, f(b)/z 是一個置換。 但g(y)/x, f(x)/y不是一個置換。原因是它在x與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當用g(y)置換x,用f(g(y)置換y時，既沒有消去x，也沒有消去y。 若改為g(a)/x, f(x)

29、/y即可，原因是用g(a)置換x ，用f(g(a)置換y ，則消去了x和y。 通常，置換是用希臘字母、 、 等來表示的。 定義4.10 設=t1/x1,t2/x2,tn/xn是一個置換，F(xiàn)是一個謂詞公式，把公式F中出現(xiàn)的所有xi換成ti(i=1,2,n)，得到一個新的公式G，稱G為F在置換下的例示，記作G=F。 一個謂詞公式的任何例示都是該公式的邏輯結論。,31,4.2.5 置換與合一1. 置換(2/2),定義4.11 設 =t1/x1,t2/x2,tn/xn = u1/y1, u2/y2, , um/ym 是兩個置換。則與的合成也是一個置換，記作。它是從集合 t1/x1, t2/x2, ,

30、tn/xn, u1/y1, u2/y2, , um/ym 中刪去以下兩種元素 當ti=xi時，刪去ti/xi (i=1, 2 , n)； 當yj x1, x2 , xn 時，刪去uj/yj (j=1, 2 , m) 最后剩下的元素所構成的集合。 例4.4 設= f(y)/x, z/y ，=a/x, b/y ,y/z ，求與的合成。 解:先求出集合 f(b/y)/x, (y/z)/y, a/x, b/y , y/z=f(b)/x, y/y, a/x, b/y , y/z 其中，f(b)/x中的f(b)是置換作用于f(y)的結果；y/y 中的y是置換作用于z的結果。在該集合中，y/y滿足定義中的條

31、件，需要刪除；a/x和b/y滿足定義中的條件，也需要刪除。最后得 =f(b)/x, y/z,32,4.2.5 置換與合一2. 合一,合一可理解為是尋找項對變量的置換，使兩個謂詞公式一致?？啥x為： 定義4.12 設有公式集F=F1, F2,Fn，若存在一個置換，可使 F1=F2=Fn， 則稱是F的一個合一。稱F1,F2,Fn是可合一的。 例如，設有公式集F=P(x,y,f(y), P(a,g(x),z)，則 =a/x, g(a)/y, f(g(a)/z 是它的一個合一。 一般來說，一個公式集的合一不是唯一的。 定義4.13 設是公式集F的一個合一，如果對F的任一個合一都存在一個置換，使得=，則

32、稱是一個最一般合一。 一個公式集的最一般合一是唯一的。 對如何求取最一般合一的問題，不再討論。,33,第4章 確定性推理,4.1 推理的基本概念 4.2 推理的邏輯基礎 4.3 自然演繹推理 4.4 歸結演繹推理 4.5 基于規(guī)則的演繹推理,34,4.3 自然演繹推理,自然演繹推理 從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結論的過程稱為自然演繹推理。 自然演繹推理最基本的推理規(guī)則是三段論推理，它包括： 假言推理 P, PQ Q 拒取式 Q, PQ P 假言三段論 PQ, QR PR 自然演繹推理的例子 例4.5 設已知如下事實： A, B, AC, BCD, DQ 求證：Q為

33、真。 證明：因為 A, AC C 假言推理 B, C BC 引入合取詞 BC，BCD D 假言推理 D, DQ Q 假言推理 因此，Q為真,35,4.3 自然演繹推理,例4.6 設已知如下事實： (1) 只要是需要編程序的課，王程都喜歡。 (2) 所有的程序設計語言課都是需要編程序的課。 (3) C+是一門程序設計語言課。 求證：王程喜歡C+這門課。 證明：首先定義謂詞 Prog(x) x是需要編程序的課。 Like(x, y) x喜歡y。 Lang(x) x是一門程序設計語言課 把已知事實及待求解問題用謂詞公式表示如下： Prog(x)Like(Wang , x) (x)( Lang(x)P

34、rog(x) Lang(C+) 應用推理規(guī)則進行推理： Lang(y)Prog(y) 全稱固化 Lang(C+)，Lang(y)Prog(y) Prog(C+) 假言推理 C+/y Prog(C+), Prog(x)Like(Wang , x) Like(Wang , C+) 假言推理 C+/x 因此，王程喜歡C+這門課。,36,4.3 自然演繹推理,優(yōu)點：定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。 缺點：是容易產(chǎn)生知識爆炸，推理過程中得到的中間結論一般按指數(shù)規(guī)律遞增，對于復雜問題的推理不利，甚至難以實現(xiàn)。,37,第4章 確定性推理,4.1 推理的基本概念 4.2 推理的邏輯基礎

35、4.3 自然演繹推理 4.4 歸結演繹推理 4.5 基于規(guī)則的演繹推理,38,4.4 歸結演繹推理,歸結演繹推理是一種基于魯賓遜（Robinson）歸結原理的機器推理技術。魯賓遜歸結原理亦稱為消解原理，是魯賓遜于1965年在海伯倫（Herbrand）理論的基礎上提出的一種基于邏輯的“反證法”。 在人工智能中，幾乎所有的問題都可以轉化為一個定理證明問題。定理證明的實質，就是要對前提P和結論Q，證明PQ永真。 由4.2節(jié)可知，要證明PQ永真，就是要證明PQ在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。 為此，人們進行了大量的探索，后來發(fā)現(xiàn)可以采用反證法的思想，把關于永真性

36、的證明轉化為關于不可滿足性的證明。 即要證明PQ永真，只要能夠證明PQ是不可滿足的就可以了(原因是 (PQ) ( PQ) P Q 。 這方面最有成效的工作就是魯賓遜歸結原理。它使定理證明的機械化成為現(xiàn)實。,39,4.4 歸結演繹推理,4.4.1 子句集及其化簡 4.4.2 魯濱遜歸結原理 4.4.3 歸結反演推理的歸結策略 4.4.4 用歸結反演求取問題的答案,40,4.4.1 子句集及其化簡1. 子句和子句集,魯濱遜歸結原理是在子句集的基礎上討論問題的。因此，討論歸結演繹推理之前，需要先討論子句集的有關概念。 子句和子句集 定義4.14 原子謂詞公式及其否定統(tǒng)稱為文字。 例如，P(x)、Q(

37、x)、 P(x)、 Q(x)等都是文字。 定義4.15 任何文字的析取式稱為子句。 例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子句。 定義4.16 不含任何文字的子句稱為空子句。 由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的。 空子句一般被記為或NIL。 定義4.17 由子句或空子句所構成的集合稱為子句集。,41,4.4.1 子句集及其化簡2. 子句集的化簡（1/6）,在謂詞邏輯中，任何一個謂詞公式都可以通過應用等價關系及推理規(guī)則化成相應的子句集。其化簡步驟如下： (1) 消去連接詞“”和“” 反復使用如下等價公式： PQ PQ PQ (

38、PQ)(PQ) 即可消去謂詞公式中的連接詞“”和“”。 例如公式 (x)(y)P(x,y) (y)(Q(x,y)R(x,y) 經(jīng)等價變化后為 (x)(y)P(x,y) (y)(Q(x,y)R(x,y),42,4.4.1 子句集及其化簡2. 子句集的化簡（2/6）,(2) 減少否定符號的轄域 反復使用雙重否定率 (P) P 摩根定律 (PQ) PQ (PQ) PQ 量詞轉換率 (x)P(x) (x) P(x) (x)P(x) (x)P(x) 將每個否定符號“”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。 例如，上式經(jīng)等價變換后為 (x)(y)P(x，y)(y)( Q(x，y) R

39、(x，y),43,4.4.1 子句集及其化簡2. 子句集的化簡（3/6）,(3) 對變元標準化 在一個量詞的轄域內，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。 例如，上式經(jīng)變換后為 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) (4) 化為前束范式 化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進行了標準化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種移動是可行的。 例如，上式化為前束范式后為 (x)(y) (z)(P(x，y)( Q(x

40、，z) R(x，z),44,4.4.1 子句集及其化簡2. 子句集的化簡（4/6）,(5) 消去存在量詞 消去存在量詞時，需要區(qū)分以下兩種情況： 若存在量詞不出現(xiàn)在全稱量詞的轄域內（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。 若存在量詞位于一個或多個全稱量詞的轄域內，例如 (x1)(xn) (y)P(x1，x2 , xn ,y) 則需要用Skolem函數(shù)f(x1，x2 , xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。 例如，上步所得公式中存在量詞(y)和(z)都位于(x)的轄域內，因此都需要用Skolem函數(shù)來替換。設替換y和

41、z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x),45,4.4.1 子句集及其化簡2. 子句集的化簡（5/6）,(6) 化為Skolem標準形 Skolem標準形的一般形式為 (x1)(xn) M(x1,x2,xn) 其中， M(x1,x2,xn)是Skolem標準形的母式，它由子句的合取所構成。 把謂詞公式化為Skolem標準形需要使用以下等價關系 P(QR) (PQ)(PR) 例如，前面的公式化為Skolem標準形后為 (x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x) (7) 消去全稱量詞

42、由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設其變元是被全稱量詞量化的。 例如，上式消去全稱量詞后為 (P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x),46,4.4.1 子句集及其化簡2. 子句集的化簡（6/6）,(8) 消去合取詞 在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。 例如，上式的子句集中包含以下兩個子句 P(x,f(x)Q(x,g(x) P(x,f(x)R(x,g(x) (9) 更換變量名稱 對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相

43、同的變量名。由于每一個子句都對應著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關系。這樣，更換變量名是不會影響公式的真值的。 例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集 P(x,f(x)Q(x,g(x) P(y,f(y)R(y,g(y),47,4.4.1 子句集及其化簡3. 子句集的應用（1/4）,在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標準子句集是不唯一的。 這樣，當原謂詞公式為非永假時，它與其標準子句集并不等價。但當原謂詞公式為永假（或不可滿足）時，其標準子句集則

44、一定是永假的，即Skolem化并不影響原謂詞公式的永假性。 這個結論很重要，是歸結原理的主要依據(jù)，可用定理的形式來描述。 定理4.1 設有謂詞公式F，其標準子句集為S，則F為不可滿足的充要條件是S為不可滿足的。 為證明此定理，先作如下說明： 為討論問題方便，設給定的謂詞公式F已為前束形 (Q1x1) (Qrxr) (Qnxn)M(x1,x2,xn) 其中，M(x1,x2,xn)已化為合取范式。 由于將F化為這種前束形是一種很容易實現(xiàn)的等價運算，因此這種假設是可以的。,48,4.4.1 子句集及其化簡3. 子句集的應用（2/4）,又設(Qrxr)是第一個出現(xiàn)的存在量詞(xr)，即F為 F=(x1

45、)(xr-1) (xr)(Qr+1xr+1)(Qnxn)M(x1,xr-1,xr,xr+1,xn) 為把F化為Skolem形，需要先消去這個(xr)，并引入Skolem函數(shù)，得到 F1=(x1)(xr-1) (Qr+1xr+1)(Qnxn)M(x1,xr-1,f(x1,xr-1),xr+1,xn) 若能證明 F不可滿足 F1不可滿足 則同理可證 F1不可滿足 F2不可滿足 重復這一過程，直到證明了 Fm-1不可滿足 Fm不可滿足 為止。 此時，F(xiàn)m已為F的Skolem標準形。而S只不過是Fm的一種集合表示形式。因此有 Fm不可滿足 S不可滿足 下面開始用反證法證明 F不可滿足 F1不可滿足,4

46、9,4.4.1 子句集及其化簡3. 子句集的應用（3/4）,先證明 已知F不可滿足，假設F1是可滿足的，則存在一個解釋I，使F1在解釋I下為真。即對任意x1,xr-1在I的設定下有 (Qr+1xr+1)(Qnxn)M(x1,xr-1,f(x1,xr-1),xr+1,xn) 為真。亦即對任意的x1,xr-1都有一個f(x1,xr-1)使 (Qr+1xr+1)(Qnxn)M(x1,xr-1,f(x1,xr-1),xr+1,xn) 為真。即在I下有 (x1)(xr-1) (xr)(Qr+1xr+1)(Qnxn)M(x1,xr-1,xr,xr+1,xn) 為真。即F在I下為真。 但這與前提F是不可滿足

47、的相矛盾，即假設F1為可滿足是錯誤的。從而可以得出“若F不可滿足，則必有F1不可滿足”。,50,4.4.1 子句集及其化簡3. 子句集的應用（4/4）,再證明 已知F1不可滿足，假設F是可滿足的。于是便有某個解釋I使F在I下為真。即對任意的x1,xr-1在I的設定下都可找到一個xr使 (Qr+1xr+1)(Qnxn)M(x1,xr-1,xr,xr+1,xn) 為真。若擴充I，使它包含一個函數(shù)f(x1,xr-1)，且有 xr= f(x1,xr-1) 這樣，就可以把所有的(f(x1,xr-1)映射到xr，從而得到一個新的解釋I，并且在此解釋下對任意的x1,xr-1都有 (Qr+1xr+1)(Qnx

48、n)M(x1,xr-1,f(x1,xr-1),xr+1,xn) 為真。即在I下有 (x1)(xr-1) (Qr+1xr+1)(Qnxn)M(x1,xr-1,f(x1,xr-1),xr+1,xn) 為真。它說明F1在解釋I下為真。但這與前提F1是不可滿足的相矛盾，即假設F為可滿足是錯誤的。從而可以得出“若F1不可滿足，則必有F不可滿足” 于是，定理得證。 由此定理可知，要證明一個謂詞公式是不可滿足的，只要證明其相應的標準子句集是不可滿足的就可以了。至于如何證明一個子句集的不可滿足性，由下面的海伯倫理論和魯賓遜歸結原理來解決。,51,4.4.2 魯濱遜歸結原理1. 基本思想,注意以下兩個關鍵 第一

49、，子句集中的子句之間是合取關系。因此，子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的； 第二，空子句是不可滿足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。 魯濱遜歸結原理基本思想 首先把欲證明問題的結論否定，并加入子句集，得到一個擴充的子句集S。然后設法檢驗子句集S是否含有空子句，若含有空子句，則表明S是不可滿足的；若不含有空子句，則繼續(xù)使用歸結法，在子句集中選擇合適的子句進行歸結，直至導出空子句或不能繼續(xù)歸結為止。 魯濱遜歸結原理包括 命題邏輯歸結原理 謂詞邏輯歸結原理,52,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（1/8）,歸結推理的核心是求

50、兩個子句的歸結式 (1) 歸結式的定義及性質 定義4.18 若P是原子謂詞公式，則稱P與P為互補文字。 定義4.19 設C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關系構成一個新的子句C12，則稱這一過程為歸結，稱C12為C1和C2的歸結式，稱C1和C2為C12的親本子句。 例4.7 設C1=PQR，C2=PS，求C1和C2的歸結式C12。 解：這里L1=P，L2=P，通過歸結可以得到 C12= QRS 例4.8 設C1=Q，C2=Q，求C1和C2的歸結式C12。 解：這里L1=Q，L2

51、=Q，通過歸結可以得到 C12= NIL,53,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（2/8）,例4.9 設設C1 =P Q ，C2=Q，C3=P，求C1、C2、C3的歸結式C123。 解：若先對C1、C2歸結，可得到 C12=P 然后再對C12和C3歸結，得到 C123=NIL 如果改變歸結順序，同樣可以得到相同的結果，即其歸結過程是不唯一的。 其歸結歸結過程可用右圖來表示，該樹稱為歸結樹。,P Q,Q,P,P,NIL,P Q,P,Q,Q,NIL,54,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（3/8）,定理4.2 歸結式C12是其親本子句C1和C2的邏輯結論。 證明：（按定

52、義）設C1=LC1 ，C2=LC2關于解釋I為真，則只需證明C12= C1 C2關于解釋I也為真。 對于解釋I，L和L中必有一個為假。 若L為假，則必有C1為真，不然就會使C1為假，這將與前提假設C1為真矛盾，因此只能有C1為真。 同理，若L為假，則必有C2為真。 因此，必有C12= C1C2關于解釋I也為真。即C12是C1和C2的邏輯結論。,55,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（4/8）,上述定理是歸結原理中的一個重要定理，由它可得到以下兩個推論： 推論1：設C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結式，若用C12代替C1和C2后得到新的子句集S1，則由S1的

53、不可滿足性可以推出原子句集S的不可滿足性。即： S1的不可滿足性 S的不可滿足性 證明：設S= C1，C2，C3，Cn，C12是C1和C2的歸結式，則用C12代替C1和C2后可得到一個新的子句集 S1= C12，C3，, Cn 設S1是不可滿足的，則對不滿足S1的任一解釋I，都可能有以下兩種情況： 解釋I使C12為真，則C3，Cn中必有一個為假，即S是不可滿足的。 解釋I使C12為假，即C12為真，根據(jù)定理3.2有 (C1C2)永真，即C1C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。 因此可以得出 S1的不可滿足性S的不可滿足性,56,4.4.2 魯濱遜歸結原理2. 命題

54、邏輯的歸結（5/8）,推論2：設C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結式，若把C12加入S中得到新的子句集S2，則S與S2的不可滿足性是等價的。即： S2的不可滿足性S的不可滿足性 先證明 設S= C1，C2，C3，Cn是不可滿足的，則C1，C2，C3，Cn中必有一子句為假，因而S2= C12，C1，C2，C3，Cn必為不可滿足。 再證明 設S2是不可滿足的,則對不滿足S2的任一解釋I,都可能有以下兩種情況： 解釋I使C12為真，則C1，C2，C3，Cn中必有一個為假，即S是不可滿足的。 解釋I使C12為假，即C12為真，根據(jù)定理3.2有 (C1C2)永真，即C1C2永真，

55、它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。 由此可見S與S2的不可滿足性是等價的。即 S的不可滿足性 S2的不可滿足性,57,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（6/8）,上述兩個推論說明，為證明子句集S的不可滿足性，只要對其中可進行歸結得子句進行歸結，并把歸結式加入到子句集S中，或者用歸結式代替他的親本子句，然后對新的子句集證明其不可滿足性就可以了。 如果經(jīng)歸結能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集S是不可滿足的結論。 在命題邏輯中，對不可滿足的子句集S，其歸結原理是完備的。 這種不可滿足性可用如下定理描述： 定理4.3 子句集S是不可滿足的，當且僅

56、當存在一個從S到空子句的歸結過程。,58,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（7/8）,(2) 命題邏輯的歸結反演 歸結原理：假設F為已知前提，G為欲證明的結論，歸結原理把證明G為F的邏輯結論轉化為證明FG為不可滿足。 再根據(jù)定理3.1，在不可滿足的意義上，公式集FG與其子句集是等價的，即把公式集上的不可滿足轉化為子句集上的不可滿足。 應用歸結原理證明定理的過程稱為歸結反演。 在命題邏輯中，已知F，證明G為真的歸結反演過程如下： 否定目標公式G，得G; 把G并入到公式集F中，得到F，G； 把F，G化為子句集S。 應用歸結原理對子句集S中的子句進行歸結，并把每次得到的歸結式并入S中。

57、如此反復進行，若出現(xiàn)空子句，則停止歸結，此時就證明了G為真。,59,4.4.2 魯濱遜歸結原理2. 命題邏輯的歸結（8/8）,例4.10 設已知的公式集為P, (PQ)R, (ST)Q, T，求證結論R。 解：假設結論R為假, 將R加入公式集，并化為子句集 S=P,PQR, SQ, TQ, T, R 其歸結過程如右圖的歸結演繹樹所示。該樹根為空子句。 其含義為：先假設子句集S中的所有子句均為真，即原公式集為真,R也為真；然后利用歸結原理，對子句集進行歸結，并把所得的歸結式并入子句集中；重復這一過程，最后歸結出了空子句。 根據(jù)歸結原理的完備性，可知子句集S是不可滿足的，即開始時假設R為真是錯誤的，這就證明了R為真。,P QR, R,P Q,P,Q,T Q,T,T,NIL,60,4.4.2 魯濱遜歸結原理3. 謂詞邏輯的歸結（1/16）,在謂詞邏輯中，由于子句集中的謂詞一般都含有變元，因此不能象命題邏輯那樣直接消去互補文字。而需要先用一個最一般合