1、1第第3章章 確定性推理確定性推理 智能系統(tǒng)的推理過程實際上就是一種思維過程。按照智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定性，推理可分為確定性推理和不推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。對于推理的這兩種不同類型，本章重點討論確定性推理。對于推理的這兩種不同類型，本章重點討論前一種，不確定性推理放到下一章討論。前一種，不確定性推理放到下一章討論。 3.1 推理的基本概念推理的基本概念 3.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 3.3 自然演繹推理自然演繹推理 3.4 歸結(jié)演繹推理歸結(jié)演繹推理 3.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理23.1

2、推理的基本概念推理的基本概念 3.1.1 什么是推理什么是推理 3.1.2 推理方法及其分類推理方法及其分類 3.1.3 推理的控制策略及其分類推理的控制策略及其分類 3.1.4 正向推理正向推理 3.1.5 逆向推理逆向推理 3.1.6 混合推理混合推理33.1.1 什么是推理什么是推理 推理的概念推理的概念 是指按照某種策略從已知事實出發(fā)去推出結(jié)論的過程。是指按照某種策略從已知事實出發(fā)去推出結(jié)論的過程。 推理所用的事實：推理所用的事實： 初始證據(jù)：初始證據(jù)：推理前用戶提供的推理前用戶提供的 中間結(jié)論：中間結(jié)論：推理過程中所得到的推理過程中所得到的 推理過程：推理過程：由推理機來完成，所謂推

3、理機就是智能系統(tǒng)中由推理機來完成，所謂推理機就是智能系統(tǒng)中用來實現(xiàn)推理的那些程序。用來實現(xiàn)推理的那些程序。 例如，例如，醫(yī)療專家系統(tǒng)，專家知識保存在知識庫中。推理開醫(yī)療專家系統(tǒng)，專家知識保存在知識庫中。推理開始時，先把病人的癥狀和檢查結(jié)果放到綜合數(shù)據(jù)庫中，然后始時，先把病人的癥狀和檢查結(jié)果放到綜合數(shù)據(jù)庫中，然后再從綜合數(shù)據(jù)庫的初始證據(jù)出發(fā)，按照某種策略在知識庫中再從綜合數(shù)據(jù)庫的初始證據(jù)出發(fā)，按照某種策略在知識庫中尋找，并使用知識，直到推出最終結(jié)論為止。尋找，并使用知識，直到推出最終結(jié)論為止。 推理的兩個基本問題推理的兩個基本問題 推理的方法：推理的方法：解決前提和結(jié)論的邏輯關(guān)系，不確定性傳遞解

4、決前提和結(jié)論的邏輯關(guān)系，不確定性傳遞 推理的控制策略：推理的控制策略：解決推理方向，沖突消解策略解決推理方向，沖突消解策略43.1.2 推理方法及其分類推理方法及其分類1. 按推理的邏輯基礎(chǔ)分類按推理的邏輯基礎(chǔ)分類(1/4)可分為演繹推理、歸納推理等可分為演繹推理、歸納推理等 演繹推理演繹推理 演繹推理是從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的演繹推理是從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結(jié)論。是一種由一般到個別的推理方法，其核心是適合于某種個別情況的結(jié)論。是一種由一般到個別的推理方法，其核心是三段論，如三段論，如假言推理、拒取式和假言三段論假言

5、推理、拒取式和假言三段論。 例：例： 假言三段論假言三段論 AB，BC AC 常用的三段論是由一個大前提、一個小前提和一個結(jié)論這三部分組成的。常用的三段論是由一個大前提、一個小前提和一個結(jié)論這三部分組成的。其中，其中，大前提大前提是已知的一般性知識或推理過程得到的判斷；是已知的一般性知識或推理過程得到的判斷；小前提小前提是關(guān)于是關(guān)于某種具體情況或某個具體實例的判斷；某種具體情況或某個具體實例的判斷；結(jié)論結(jié)論是由大前提推出的，并且適合是由大前提推出的，并且適合于小前提的判斷。于小前提的判斷。 例如，有如下三個判斷：例如，有如下三個判斷： 計算機系的學生都會編程序；計算機系的學生都會編程序； （一

6、般性知識）（一般性知識） 程強是計算機系的一位學生；程強是計算機系的一位學生； （具體情況）（具體情況） 程強會編程序。程強會編程序。 （結(jié)論）（結(jié)論） 這是一個三段論推理。其中，是大前提，是小前提；是經(jīng)演繹推這是一個三段論推理。其中，是大前提，是小前提；是經(jīng)演繹推出來的結(jié)論。出來的結(jié)論。 可見，其結(jié)論是蘊含在大前提中的。可見，其結(jié)論是蘊含在大前提中的。53.1.2 推理方法及其分類推理方法及其分類1. 按推理的邏輯基礎(chǔ)分類按推理的邏輯基礎(chǔ)分類(2/4)歸納推理歸納推理是一種由個別到一般的推理方法。歸納推理的類型是一種由個別到一般的推理方法。歸納推理的類型 按照所選事例的廣泛性按照所選事例的廣

7、泛性可分為完全歸納推理和不完全歸納推理可分為完全歸納推理和不完全歸納推理 按照推理所使用的方法按照推理所使用的方法可分為枚舉、類比、統(tǒng)計和差異歸納推理等可分為枚舉、類比、統(tǒng)計和差異歸納推理等 完全歸納推理完全歸納推理 是指在進行歸納時需要考察相應(yīng)事物的全部對象，并根據(jù)這些對象是否是指在進行歸納時需要考察相應(yīng)事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。如，計算機質(zhì)量檢驗。都具有某種屬性，推出該類事物是否具有此屬性。如，計算機質(zhì)量檢驗。 不完全歸納推理不完全歸納推理 是指在進行歸納時只考察了相應(yīng)事物的部分對象，就得出了關(guān)于該事物是指在進行歸納時只考察了相應(yīng)事物的部

8、分對象，就得出了關(guān)于該事物的結(jié)論。例如，計算機，隨機抽查。的結(jié)論。例如，計算機，隨機抽查。 枚舉歸納推理枚舉歸納推理 是指在進行歸納時，如果已知某類事物的有限可數(shù)個具體事物都具有某是指在進行歸納時，如果已知某類事物的有限可數(shù)個具體事物都具有某種屬性，則可推出該類事物都具有此種屬性。種屬性，則可推出該類事物都具有此種屬性。例如，設(shè)有如下事例：例如，設(shè)有如下事例： 王強是計算機系學生，他會編程序；王強是計算機系學生，他會編程序； 高華是計算機系學生，她會編程序；高華是計算機系學生，她會編程序； 當這些具體事例足夠多時，就可歸納出一個一般性的知識：當這些具體事例足夠多時，就可歸納出一個一般性的知識：

9、 凡是計算機系的學生，就一定會編程序。凡是計算機系的學生，就一定會編程序。63.1.2 推理方法及其分類推理方法及其分類1. 按推理的邏輯基礎(chǔ)分類按推理的邏輯基礎(chǔ)分類(3/4)類比歸納推理類比歸納推理 是指在兩個或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出是指在兩個或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們在其他屬性上也相同或相似的一種歸納推理。它們在其他屬性上也相同或相似的一種歸納推理。 設(shè)設(shè)A、B分別是兩類事物的集合：分別是兩類事物的集合： A=a1,a2, B=b1,b2,并設(shè)并設(shè)ai與與bi總是成對出現(xiàn)，且當總是成對出現(xiàn)，且當ai有屬性有屬性P時，時，bi就有屬性就有屬性Q與

10、此對應(yīng)，與此對應(yīng)，即即 P(ai)Q(bi) i=1,2,. 則當則當A與與B中有一新的元素對出現(xiàn)時，若已知中有一新的元素對出現(xiàn)時，若已知a有屬性有屬性P，b有屬有屬性性Q，即，即 P(a)Q(b) 類比歸納推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個或兩類類比歸納推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關(guān)程度。性之間的相關(guān)程度。73.1.2 推理方法及其分類推理方法及其分類 1. 按推理的邏輯基礎(chǔ)分類按推理的邏輯基礎(chǔ)分類(4/4)演繹推理與歸納推理的區(qū)別演繹推理

11、與歸納推理的區(qū)別 演繹推理演繹推理是在已知領(lǐng)域內(nèi)的一般性知識的前提下，是在已知領(lǐng)域內(nèi)的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結(jié)論的正確通過演繹求解一個具體問題或者證明一個結(jié)論的正確性。它所得出的結(jié)論實際上早已蘊含在一般性知識的性。它所得出的結(jié)論實際上早已蘊含在一般性知識的前提中，演繹推理只不過是將已有事實揭露出來，因前提中，演繹推理只不過是將已有事實揭露出來，因此它此它不能增殖新知識不能增殖新知識。 歸納推理歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的。所推出的結(jié)論是沒有包含在前提內(nèi)容中的。這種由個別事物或現(xiàn)象推出一般性知識的過程，這種由個別事物或現(xiàn)象推出一般性知識的過程，是

12、增是增殖新知識殖新知識的過程。的過程。 例如，例如，一位計算機維修員，從書本知識，到通過大一位計算機維修員，從書本知識，到通過大量實例積累經(jīng)驗，是一種量實例積累經(jīng)驗，是一種歸納歸納推理方式。運用這些一推理方式。運用這些一般性知識知識去維修計算機的過程則是般性知識知識去維修計算機的過程則是演繹演繹推理。推理。 83.1.3 推理的控制策略及其分類推理的控制策略及其分類推理的控制策略推理的控制策略 推理過程不僅依賴于所用的推方法，同時也依賴于推理的控制策略。推理過程不僅依賴于所用的推方法，同時也依賴于推理的控制策略。 推理的控制策略是指推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達到目標的策略

13、如何使用領(lǐng)域知識使推理過程盡快達到目標的策略。控制策略的分類控制策略的分類 由于智能系統(tǒng)的推理過程一般表現(xiàn)為一種搜索過程，因此，推理的控制策由于智能系統(tǒng)的推理過程一般表現(xiàn)為一種搜索過程，因此，推理的控制策略又可分為略又可分為推理策略和搜索策略推理策略和搜索策略。 推理策略推理策略 主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等限制策略、沖突消解策略等 推理方向控制策略推理方向控制策略用于確定推理的控制方向，可分為正向推理、逆向推理、用于確定推理的控制方向，可分為正向推理、逆向推理、混合推理

14、及雙向推理。混合推理及雙向推理。 求解策略求解策略是指僅求一個解，還是求所有解或最優(yōu)解等。是指僅求一個解，還是求所有解或最優(yōu)解等。 限制策略限制策略是指對推理的深度、寬度、時間、空間等進行的限制。是指對推理的深度、寬度、時間、空間等進行的限制。 沖突消解策略沖突消解策略是指當推理過程有多條知識可用時，如何從這多條可用知識是指當推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。中選出一條最佳知識用于推理的策略。 搜索策略搜索策略 主要解決主要解決推理線路、推理效果、推理效率等問題推理線路、推理效果、推理效率等問題。 本章主要討論推理策略，本章主要討論推理策略，至于搜

15、索策略將放到第至于搜索策略將放到第4章單獨討論。章單獨討論。93.1.4 正向推理正向推理推理算法推理算法 從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅(qū)動推理或前向鏈從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅(qū)動推理或前向鏈推理。推理。 算法描述算法描述 (1) 把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫；把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫； (2) 檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若已包含，則求解結(jié)束，檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若已包含，則求解結(jié)束，并成功推出；否則執(zhí)行下一步；并成功推出；否則執(zhí)行下一步； (3) 檢查知識庫中是否有可用知識，若有，形成當前可用知識集，執(zhí)行檢查知識庫

16、中是否有可用知識，若有，形成當前可用知識集，執(zhí)行下一步；否則轉(zhuǎn)下一步；否則轉(zhuǎn)(5)。 (4) 按照某種沖突消解策略，從當前可用知識集中選出一條規(guī)則進行推按照某種沖突消解策略，從當前可用知識集中選出一條規(guī)則進行推理，并將推出的新事實加入綜合數(shù)據(jù)庫種，然后轉(zhuǎn)理，并將推出的新事實加入綜合數(shù)據(jù)庫種，然后轉(zhuǎn)(2)。 (5) 詢問用戶是否可以進一步補充新的事實，若可補充，則將補充的新詢問用戶是否可以進一步補充新的事實，若可補充，則將補充的新事實加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)事實加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)(3)；否則表示無解，失敗退出。；否則表示無解，失敗退出。 至于如何根據(jù)綜合數(shù)據(jù)庫中的事實到知識庫中選取可用知識

17、，當知識庫至于如何根據(jù)綜合數(shù)據(jù)庫中的事實到知識庫中選取可用知識，當知識庫中有多條知識可用時應(yīng)該先使用那一條知識等。這些問題涉及到了知識的中有多條知識可用時應(yīng)該先使用那一條知識等。這些問題涉及到了知識的匹配方法和沖突消解策略，以后將會分別討論。匹配方法和沖突消解策略，以后將會分別討論。 其流程圖如下：其流程圖如下：10把初始證據(jù)放入把初始證據(jù)放入DBDB中有解嗎？中有解嗎？KB中有可用知識嗎？中有可用知識嗎？ 形成可用知識集形成可用知識集可用知識集空嗎？可用知識集空嗎？按照沖突消解策略從該知識按照沖突消解策略從該知識集中選出一條知識進行推理集中選出一條知識進行推理 推出的是新事實嗎？推出的是新事

18、實嗎？ 將新事實加入到將新事實加入到DB把用戶補充的新事把用戶補充的新事實實加入到加入到DB中中 用戶可補充新事實嗎？用戶可補充新事實嗎？ 失敗退出失敗退出 成功退出成功退出YNNYNNNYYY113.1.4 正向推理正向推理推理例子推理例子 例例3.1請用正向推理完成以下問題的求解請用正向推理完成以下問題的求解 假設(shè)知識庫中包含有以下假設(shè)知識庫中包含有以下2條規(guī)則：條規(guī)則： r1： IF B THEN C r2： IF A THEN B已知初始證據(jù)已知初始證據(jù)A，求證目標，求證目標C。 解：本例的推理過程如下：解：本例的推理過程如下： 推理開始前，綜合數(shù)據(jù)庫為空。推理開始前，綜合數(shù)據(jù)庫為空。

19、 推理開始后，先把推理開始后，先把A放入綜合數(shù)據(jù)庫，然后檢查綜合數(shù)據(jù)庫中是否含有該放入綜合數(shù)據(jù)庫，然后檢查綜合數(shù)據(jù)庫中是否含有該問題的解，回答為問題的解，回答為“N”。 接著檢查知識庫中是否有可用知識，顯然接著檢查知識庫中是否有可用知識，顯然r2可用，形成僅含可用，形成僅含r2的知識集。的知識集。從該知識集中取出從該知識集中取出r2，推出新的實事，推出新的實事B，將，將B加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標庫中是否含有目標C，回答為，回答為“N”。 再檢查知識庫中是否有可用知識，此時由于再檢查知識庫中是否有可用知識，此時由于B的加入使得的加入使得r1為可用，

20、形成僅為可用，形成僅含含r1的知識集。從該知識集中取出的知識集。從該知識集中取出r1，推出新的實事，推出新的實事C，將，將C加入綜合數(shù)據(jù)庫，加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標檢查綜合數(shù)據(jù)庫中是否含有目標C，回答為，回答為“Y”。 它說明綜合數(shù)據(jù)庫中已經(jīng)含有問題的解，推理成功結(jié)束，目標它說明綜合數(shù)據(jù)庫中已經(jīng)含有問題的解，推理成功結(jié)束，目標C得證。得證。123.1.4 正向推理正向推理優(yōu)缺點優(yōu)缺點 正向推理的主要優(yōu)點正向推理的主要優(yōu)點 比較直觀，允許用戶主動提供有用的事實信息，適合比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設(shè)計、預測、監(jiān)控等領(lǐng)域的問題求解。于診斷、設(shè)計、預測、

21、監(jiān)控等領(lǐng)域的問題求解。 正向推理的主要缺點正向推理的主要缺點 推理無明確目標，求解問題是可能會執(zhí)行許多與解無推理無明確目標，求解問題是可能會執(zhí)行許多與解無關(guān)的操作，導致推理效率較低。關(guān)的操作，導致推理效率較低。 133.1.5 逆向推理逆向推理推理算法推理算法 從某個假設(shè)目標出發(fā)，逆向使用規(guī)則，亦稱為目標驅(qū)動推理或逆向鏈推從某個假設(shè)目標出發(fā)，逆向使用規(guī)則，亦稱為目標驅(qū)動推理或逆向鏈推理。理。算法描述：算法描述： (1) 將要求證的目標（稱為假設(shè)）構(gòu)成一個假設(shè)集；將要求證的目標（稱為假設(shè)）構(gòu)成一個假設(shè)集； (2) 從假設(shè)集中選出一個假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫中，若在，從假設(shè)集中選出一個假設(shè)

22、，檢查該假設(shè)是否在綜合數(shù)據(jù)庫中，若在，則該假設(shè)成立，此時，若假設(shè)集為空，則成功退出，否則仍執(zhí)行則該假設(shè)成立，此時，若假設(shè)集為空，則成功退出，否則仍執(zhí)行(2)；若該；若該假設(shè)不在數(shù)據(jù)庫中，則執(zhí)行下一步；假設(shè)不在數(shù)據(jù)庫中，則執(zhí)行下一步； (3) 檢查該假設(shè)是否可由知識庫的某個知識導出，若不能由某個知識導檢查該假設(shè)是否可由知識庫的某個知識導出，若不能由某個知識導出，則詢問用戶該假設(shè)是否為可由用戶證實的原始事實，若是，該假設(shè)成出，則詢問用戶該假設(shè)是否為可由用戶證實的原始事實，若是，該假設(shè)成立，并將其放入綜合數(shù)據(jù)庫，再重新尋找新的假設(shè)，若不是，則轉(zhuǎn)立，并將其放入綜合數(shù)據(jù)庫，再重新尋找新的假設(shè)，若不是，則

23、轉(zhuǎn)(5)；若；若能由某個知識導出，則執(zhí)行下一步；能由某個知識導出，則執(zhí)行下一步； (4) 將知識庫中可以導出該假設(shè)的所有知識構(gòu)成一個可用知識集；將知識庫中可以導出該假設(shè)的所有知識構(gòu)成一個可用知識集； (5) 檢查可用知識集是否為空，若是，失敗退出；否則執(zhí)行下一步；檢查可用知識集是否為空，若是，失敗退出；否則執(zhí)行下一步； (6) 按沖突消解策略從可用知識集中取出一個知識，繼續(xù)；按沖突消解策略從可用知識集中取出一個知識，繼續(xù)； (7) 將該知識的前提中的每個子條件都作為新的假設(shè)放入假設(shè)集，然后將該知識的前提中的每個子條件都作為新的假設(shè)放入假設(shè)集，然后轉(zhuǎn)轉(zhuǎn)(2)。 其流程圖如下：其流程圖如下：14初

24、始化初始化DB和假設(shè)集和假設(shè)集該假設(shè)是該假設(shè)是DB中的事實嗎？中的事實嗎？該假設(shè)能被該假設(shè)能被KB中中的知識導出嗎？的知識導出嗎？從假設(shè)集中取出一個假設(shè)從假設(shè)集中取出一個假設(shè)可用知識集空嗎？可用知識集空嗎？按照沖突消解策略從該按照沖突消解策略從該知識知識集中選出一條知識集中選出一條知識將該知識前提中的每個子條將該知識前提中的每個子條件作為新的假設(shè)加入假設(shè)集件作為新的假設(shè)加入假設(shè)集該假設(shè)成立該假設(shè)成立并放入并放入DB還有新的假設(shè)嗎？還有新的假設(shè)嗎？失敗退出失敗退出成功退出成功退出YNYYNNNNY將將KB中所有能導出此假設(shè)中所有能導出此假設(shè)的的知識構(gòu)成一個可用知識集知識構(gòu)成一個可用知識集 詢問用

25、戶有詢問用戶有此事實嗎？此事實嗎？該假設(shè)該假設(shè) 成立成立Y153.1.5 逆向推理逆向推理推理例子推理例子對上例，采用逆向推理，其推理過程如下：對上例，采用逆向推理，其推理過程如下： 推理開始前，綜合數(shù)據(jù)庫和假設(shè)集均為空。推理開始前，綜合數(shù)據(jù)庫和假設(shè)集均為空。 推理開始后，先將初始證據(jù)推理開始后，先將初始證據(jù)A和目標和目標C分別放入綜合數(shù)據(jù)庫和假設(shè)集，然分別放入綜合數(shù)據(jù)庫和假設(shè)集，然后從假設(shè)集中取出一個假設(shè)后從假設(shè)集中取出一個假設(shè)C，查找，查找C是否為綜合數(shù)據(jù)庫中的已知事實，回是否為綜合數(shù)據(jù)庫中的已知事實，回答為答為“N”。 再檢查再檢查C是否能被知識庫中的知識所導出，發(fā)現(xiàn)是否能被知識庫中的知

26、識所導出，發(fā)現(xiàn)C可由可由r1導出，于是導出，于是r1被被放入可用知識集。由于知識庫中只有放入可用知識集。由于知識庫中只有r1可用，故可用知識集中僅含可用，故可用知識集中僅含r1。 接著從可用知識集中取出接著從可用知識集中取出r1，將其前提條件，將其前提條件B作為新的假設(shè)放入假設(shè)集。作為新的假設(shè)放入假設(shè)集。從假設(shè)集中取出從假設(shè)集中取出B，檢查，檢查B是否為綜合數(shù)據(jù)庫中的實事，回答為是否為綜合數(shù)據(jù)庫中的實事，回答為“N”。再檢。再檢查查B是否能被知識庫中的知識所導出，發(fā)現(xiàn)是否能被知識庫中的知識所導出，發(fā)現(xiàn)B可由可由r2導出，于是導出，于是r2被放入可用被放入可用知識集。由于知識庫中只有知識集。由于

27、知識庫中只有r2可用，故可用知識集中僅含可用，故可用知識集中僅含r2。 從可用知識集中取出從可用知識集中取出r2，將其前提條件，將其前提條件A作為新的假設(shè)放入假設(shè)集。然后作為新的假設(shè)放入假設(shè)集。然后從假設(shè)集中取出從假設(shè)集中取出A，檢查，檢查A是否為綜合數(shù)據(jù)庫中的實事，回答為是否為綜合數(shù)據(jù)庫中的實事，回答為“Y”。 他說明該假設(shè)成立，由于無新的假設(shè)，故推理過程成功結(jié)束，于是目標他說明該假設(shè)成立，由于無新的假設(shè)，故推理過程成功結(jié)束，于是目標C得證。得證。 163.1.5 逆向推理逆向推理優(yōu)缺點優(yōu)缺點 逆向推理的主要優(yōu)點逆向推理的主要優(yōu)點 不必尋找和使用那些與假設(shè)目標無關(guān)的信息和知識不必尋找和使用那

28、些與假設(shè)目標無關(guān)的信息和知識 推理過程的目標明確推理過程的目標明確 也有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為也有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。有效。 逆向推理的主要缺點逆向推理的主要缺點 當用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設(shè)當用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設(shè)目標的盲目性比較大，若選擇不好，可能需要多次提出假目標的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會影響系統(tǒng)效率。設(shè)，會影響系統(tǒng)效率。173.1.6 混合推理混合推理混合推理的概念混合推理的概念 把正向推理和逆向推理結(jié)合起來所進行的推理稱為混合推理。是把正向推理和逆向推理結(jié)合起來所進行的推

29、理稱為混合推理。是一種解決較復雜問題的方法。一種解決較復雜問題的方法。混合推理的方法混合推理的方法 1. 先正向后逆向先正向后逆向 這種方法先進行正向推理，從已知事實出發(fā)推出部分結(jié)果，然后這種方法先進行正向推理，從已知事實出發(fā)推出部分結(jié)果，然后再用逆向推理對這些結(jié)果進行證實或提高它們的可信度。再用逆向推理對這些結(jié)果進行證實或提高它們的可信度。 2. 先逆向后正向先逆向后正向 這種方法先進行逆向推理，從假設(shè)目標出發(fā)推出一些中間假設(shè)，這種方法先進行逆向推理，從假設(shè)目標出發(fā)推出一些中間假設(shè)，然后再用正向推理對這些中間假設(shè)進行證實。然后再用正向推理對這些中間假設(shè)進行證實。 3. 雙向混合雙向混合 是指

30、正向推理和逆向推理同時進行，使推理過程在中間的某一步是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結(jié)合起來。結(jié)合起來。 對于這些方法我不再詳細討論。對于這些方法我不再詳細討論。18第3章 確定性推理 3.1 推理的基本概念推理的基本概念 3.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 3.3 自然演繹推理自然演繹推理 3.4 歸結(jié)演繹推理歸結(jié)演繹推理 3.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理193.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 3.2.1 謂詞公式的解釋謂詞公式的解釋 3.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性 3.2.3 謂詞公式的等價性和永真蘊含性謂詞公式的等

31、價性和永真蘊含性 3.2.4 謂詞公式的范式謂詞公式的范式 3.2.5 置換與合一置換與合一203.2.1 謂詞公式的解釋謂詞公式的解釋概念概念 命題公式的解釋命題公式的解釋 在命題邏輯中，在命題邏輯中，命題公式的一個解釋就是對該命題公式中命題公式的一個解釋就是對該命題公式中各個命題變元的一次真值指派。各個命題變元的一次真值指派。 有了命題公式的解釋，就可據(jù)此求出該命題公式的真值。有了命題公式的解釋，就可據(jù)此求出該命題公式的真值。 謂詞公式的解釋謂詞公式的解釋 由于謂詞公式中可能包含由個體由于謂詞公式中可能包含由個體常量、變元或函數(shù)常量、變元或函數(shù)，因此，因此，必須先考慮這些個體常量和函數(shù)在個

32、體域上的取值，然后才必須先考慮這些個體常量和函數(shù)在個體域上的取值，然后才能根據(jù)它們的具體取值為謂詞分別指派真值。能根據(jù)它們的具體取值為謂詞分別指派真值。 定義定義3.1 設(shè)設(shè)D是謂詞公式是謂詞公式P的非空個體域，若對的非空個體域，若對P中的個體常中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：量、函數(shù)和謂詞按如下規(guī)定賦值： (1) 為每個個體常量指派為每個個體常量指派D中的一個元素；中的一個元素； (2) 為每個為每個n元函數(shù)指派一個從元函數(shù)指派一個從Dn到到D的一個映射，其中的一個映射，其中 Dn =(x1, x2, , xn)| x1, x2, , xnD (3) 為每個為每個n元謂詞指派一個從元

33、謂詞指派一個從Dn到到F，T的映射。的映射。 則稱這些指派為則稱這些指派為P在在D上的一個解釋上的一個解釋I 213.2.1 謂詞公式的解釋謂詞公式的解釋 例子一例子一(1/2) 例例3.2 設(shè)個體域設(shè)個體域D=1, 2，求公式，求公式A=(x)( y)P(x, y)在在D上的上的解釋，并指出在每一種解釋下公式解釋，并指出在每一種解釋下公式A的真值。的真值。 解：解：由于公式由于公式A中沒有包含個體常量和函數(shù)，故可直接為謂中沒有包含個體常量和函數(shù)，故可直接為謂詞指派真值，設(shè)有詞指派真值，設(shè)有 這就是公式這就是公式A 在在D 上的一個解釋。從這個解釋可以看出：上的一個解釋。從這個解釋可以看出：

34、當當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。 P(1,1) P(1,2) P(2,1) P(2,2) T F T F223.2.1 謂詞公式的解釋謂詞公式的解釋 例子一例子一(2/2) 說明：說明：一個謂詞公式在其個體域上的解釋不是唯一的。例如，對一個謂詞公式在其個體域上的解釋不是唯一的。例如，對公式公式A，若給出另一組真值指派，若給出另一組真值指派

35、這也是公式這也是公式A 在在D 上的一個解釋。從這個解釋可以看出：上的一個解釋。從這個解釋可以看出： 當當x=1、y=1時，有時，有P(x,y)的真值為的真值為T; 當當x=2、y=1時，有時，有P(x,y)的真值為的真值為F; 即對即對x在在D上的任意取值，不存在一個上的任意取值，不存在一個y使得使得P(x,y)的真值為的真值為T。因。因此，在此解釋下公式此，在此解釋下公式A的真值為的真值為F。 實際上，實際上，A在在D上共有上共有16種解釋，這里就不在一一列舉。種解釋，這里就不在一一列舉。 P(1,1) P(1,2) P(2,1) P(2,2) TT F F233.2.1 謂詞公式的解釋謂

36、詞公式的解釋 例子二例子二 例例3.3 設(shè)個體域設(shè)個體域D=1, 2，求公式，求公式B=(x)P(f(x), a)在在D上的解釋，并指出在上的解釋，并指出在該解釋下公式該解釋下公式B的真值。的真值。 解：解：設(shè)對個體常量設(shè)對個體常量a和函數(shù)和函數(shù)f(x)的值指派為：的值指派為：對謂詞的真值指派為：對謂詞的真值指派為： 由于已指派由于已指派a=1，因此，因此P(1,2)和和P(2,2)不可能出現(xiàn)，故沒給它們指派真值。不可能出現(xiàn)，故沒給它們指派真值。 上述指派是公式上述指派是公式B在在D上的一個解釋。在此解釋下有上的一個解釋。在此解釋下有 當當x=1時，時，a=1使使P(1,1)=T 當當x=2時

37、，時，a=1 使使P(2,1)=T即對即對x在在D上的任意取值，都存在上的任意取值，都存在a=1使使P(f(x), a)的真值為的真值為T。因此，在此解釋。因此，在此解釋下公式下公式B的真值為的真值為T。 由上面的例子可以看出，謂詞公式的真值都是針對某一個解釋而言的，它由上面的例子可以看出，謂詞公式的真值都是針對某一個解釋而言的，它可能在某一個解釋下真值為可能在某一個解釋下真值為T，而在另一個解釋下為，而在另一個解釋下為F。af(1)F(2)112P(1,1)P(1,2)P(2,1)P(2,2)T T243.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性 為了以后推理的需要，下面

38、先定義：為了以后推理的需要，下面先定義： 定義定義3.2 如果謂詞公式如果謂詞公式P對非空個體域?qū)Ψ强諅€體域D上的任一解釋都取得上的任一解釋都取得真值真值T，則稱，則稱P在在D 上是永真上是永真的；如果的；如果P在任何非空個體域上均是在任何非空個體域上均是永真的，則稱永真的，則稱P永真永真。 可見，要判定一謂詞公式為永真，必須對每個非空個體域上的可見，要判定一謂詞公式為永真，必須對每個非空個體域上的每個解釋逐一進行判斷。當解釋的個數(shù)為有限時，盡管工作量大，每個解釋逐一進行判斷。當解釋的個數(shù)為有限時，盡管工作量大，公式的永真性畢竟還可以判定，但當解釋個數(shù)為無限時，其永真公式的永真性畢竟還可以判定

39、，但當解釋個數(shù)為無限時，其永真性就很難判定了。性就很難判定了。 定義定義3.3 對于謂詞公式對于謂詞公式P，如果至少存在，如果至少存在D上的一個解釋，使上的一個解釋，使公式公式P在此解釋下的真值為在此解釋下的真值為T，則稱公式，則稱公式P在在D上是可滿足上是可滿足的。的。 謂詞公式的謂詞公式的可滿足性也稱為相容性可滿足性也稱為相容性。 定義定義3.4 如果謂詞公式如果謂詞公式P對非空個體域?qū)Ψ强諅€體域D上的任一解釋都取真上的任一解釋都取真值值F，則稱，則稱P在在D上是永假上是永假的；如果的；如果P在任何非空個體域上均是永在任何非空個體域上均是永假的，則稱假的，則稱P永假永假。 謂詞公式的永假性

40、又稱謂詞公式的永假性又稱不可滿足性或不相容不可滿足性或不相容。 后面我們要給出的歸結(jié)推理，就是采用一種邏輯上的反證法，后面我們要給出的歸結(jié)推理，就是采用一種邏輯上的反證法，將永真性轉(zhuǎn)換為不可滿足性的證明。將永真性轉(zhuǎn)換為不可滿足性的證明。253.2.3 謂詞公式的等價性和永真蘊含性謂詞公式的等價性和永真蘊含性1. 等價式等價式(1/2) 謂詞公式的謂詞公式的等價性等價性和和永真蘊含性永真蘊含性可分別用相應(yīng)的可分別用相應(yīng)的等價式等價式和和永真蘊含式永真蘊含式來表示，這些等價式和永真蘊來表示，這些等價式和永真蘊含式都是演繹推理的主要依據(jù)，因此也稱它們?yōu)橥坪蕉际茄堇[推理的主要依據(jù)，因此也稱它們?yōu)橥评?/p>

41、規(guī)則。理規(guī)則。 謂詞公式的謂詞公式的等價式可定義如下等價式可定義如下： 定義定義3.5 設(shè)設(shè)P與與Q是是D上的兩個謂詞公式，若對上的兩個謂詞公式，若對D上上的任意解釋，的任意解釋，P與與Q都有相同的真值，則稱都有相同的真值，則稱P與與Q在在D 上是等價的。如果上是等價的。如果D是任意非空個體域，則稱是任意非空個體域，則稱P與與Q是等價的，記作是等價的，記作PQ。 263.2.3 謂詞公式的等價性和永真蘊含性謂詞公式的等價性和永真蘊含性 1. 等價式等價式(2/2)(1) 雙重否定率雙重否定率 P P(2) 交換率交換率 (PQ) (QP)， ( PQ) ( QP)(3) 結(jié)合率結(jié)合率 (PQ)

42、R P(QR) (PQ)R P(QR)(4) 分配率分配率 P(QR) (PQ)(PR) P(QR) (PQ)(PR)(5) 摩根定律摩根定律 (PQ) PQ (PQ) PQ(6) 吸收率吸收率 P(PQ) P P(PQ) P(7) 補余率補余率 PP T, PP F (8) 連詞化歸率連詞化歸率 PQ PQ PQ (PQ)(QP) PQ (PQ)(QP)(9) 量詞轉(zhuǎn)換率量詞轉(zhuǎn)換率 (x)P (x)( P) (x)P (x) ( P)(10) 量詞分配率量詞分配率 (x) (PQ) (x)P(x)Q (x) (PQ) (x)P(x)Q273.2.3 謂詞公式的等價性和永真蘊含性謂詞公式的等價

43、性和永真蘊含性2. 永真蘊含式永真蘊含式 定義定義3.6 對謂詞公式對謂詞公式P和和Q，如果，如果PQ永真，則稱永真，則稱P 永真蘊含永真蘊含Q，且稱，且稱Q為為P的邏輯結(jié)論，的邏輯結(jié)論，P為為Q的前提，記作的前提，記作P Q。 常用的永真蘊含式如下：常用的永真蘊含式如下： (1) 化簡式化簡式 PQ P， PQ Q (2) 附加式附加式 P PQ， Q PQ (3) 析取三段論析取三段論 P, PQ Q (4) 假言推理假言推理 P, PQ Q (5) 拒取式拒取式 Q, PQ P (6) 假言三段論假言三段論 PQ, QR PR (7) 二難推理二難推理 PQ, PR, QR R (8)

44、全稱固化全稱固化 (x)P(x) P(y) 其中，其中，y是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。 (9) 存在固化存在固化 (x)P(x) P(y) 其中，其中，y是個體域中某一個可以使是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公式中為真的個體，依此可消去謂詞公式中的存在量詞。的存在量詞。283.2.4 謂詞公式的范式謂詞公式的范式 范式是謂詞公式的標準形式。在謂詞邏輯中，范式分為兩種：范式是謂詞公式的標準形式。在謂詞邏輯中，范式分為兩種：前束范式前束范式 定義定義3.7 設(shè)設(shè)F為一謂詞公式，如果其中的所有量詞

45、均非否定地出現(xiàn)在公式為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，且它們的轄域為整個公式，則稱的最前面，且它們的轄域為整個公式，則稱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)是前束范式。是前束范式。 任一謂詞公式均可化為與其對

46、應(yīng)的前束范式，其化簡方法將在后面子句任一謂詞公式均可化為與其對應(yīng)的前束范式，其化簡方法將在后面子句集的化簡中討論。集的化簡中討論。Skolem范式范式 定義定義3.8 如果前束范式中如果前束范式中所有的存在量詞都在全稱量詞之前所有的存在量詞都在全稱量詞之前，則稱這種形，則稱這種形式的謂詞公式為式的謂詞公式為Skolem范式。范式。 例如例如，(x) (z) (y)(P(x)Q(y,z)R(x,z)是是Skolem范式。范式。 任一謂詞公式均可化為與其對應(yīng)的任一謂詞公式均可化為與其對應(yīng)的Skolem范式，其化簡方法也將在后面范式，其化簡方法也將在后面子句集的化簡中討論。子句集的化簡中討論。293

47、.2.5 置換與合一置換與合一概念 在不同謂詞公式中，往往會出現(xiàn)謂詞名相同但其個體不在不同謂詞公式中，往往會出現(xiàn)謂詞名相同但其個體不同的情況，此時推理過程是不能直接進行匹配的，需要先同的情況，此時推理過程是不能直接進行匹配的，需要先進行置換。進行置換。 例如，可根據(jù)例如，可根據(jù)全稱固化全稱固化推理和推理和假言推理假言推理由謂詞公式由謂詞公式 W1(A) 和和 (x)(W1(x)W2(x) 推出推出W2(A)。對謂詞。對謂詞W1(A)可看作是由全程固化推理（即可看作是由全程固化推理（即(x)(W1(x) W1(A)推出的，其中推出的，其中A是任一個體常量。要是任一個體常量。要使用假言推理，首先需

48、要找到項使用假言推理，首先需要找到項A對變元對變元x的的置換置換，使，使W1(A)與與W1(x)一致。一致。 這種尋找項對變元的置換，使謂詞一致的過程叫做這種尋找項對變元的置換，使謂詞一致的過程叫做合一合一的過程的過程。 下面討論置換與合一的有關(guān)概念與方法。下面討論置換與合一的有關(guān)概念與方法。303.2.5 置換與合一置換與合一1. 置換置換(1/2) 置換可簡單的理解為是在一個謂詞公式中用置換項去替換變量。置換可簡單的理解為是在一個謂詞公式中用置換項去替換變量。 定義定義3.9 置換是形如置換是形如 t1/x1,t2/x2,tn/xn的有限集合。其中，的有限集合。其中，t1,t2,tn是項；

49、是項；x1,x2,xn是互不相同的變元；是互不相同的變元；ti/xi表示用表示用ti替換替換xi。并且要求。并且要求ti與與xi不能相同，不能相同，xi不能循環(huán)地出現(xiàn)在另一個不能循環(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)象。之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當用即當用g(y)置換置換x,用用f(g(y)置換置換y時，既沒有消去時，既沒有消去x，也沒有消去，也沒有消去y。 若改為若改為g(a)/x, f(x)/y即可，原因是用即可，原

50、因是用g(a)置換置換x ，用，用f(g(a)置換置換y ，則消去，則消去了了x和和y。 通常，置換是用希臘字母通常，置換是用希臘字母、 、 等來表示的。等來表示的。 定義定義3.10 設(shè)設(shè)=t1/x1,t2/x2,tn/xn是一個置換，是一個置換，F(xiàn)是一個謂詞公式，把公式是一個謂詞公式，把公式F中出現(xiàn)的所有中出現(xiàn)的所有xi換成換成ti(i=1,2,n)，得到一個新的公式，得到一個新的公式G，稱，稱G為為F在置換在置換下的下的例示例示，記作，記作G=F。 一個謂詞公式的任何例示都是該公式的邏輯結(jié)論。一個謂詞公式的任何例示都是該公式的邏輯結(jié)論。313.2.5 置換與合一置換與合一2. 置換置換(

51、2/2)定義定義3.11 設(shè)設(shè) =t1/x1,t2/x2,tn/xn = u1/y1, u2/y2, , um/ym 是兩個置換。則是兩個置換。則與與的合成也是一個置換，記作的合成也是一個置換，記作。它是從集合。它是從集合 t1/x1, t2/x2, , 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)最后剩下的元素所構(gòu)成的集合。最后剩下的元素所構(gòu)成的集合。 例例3.4 設(shè)設(shè)= f(y)/x,

52、 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)的結(jié)果；的結(jié)果；y/y 中的中的y是置換是置換作用于作用于z的的結(jié)果。在該集合中，結(jié)果。在該集合中，y/y滿足定義中的條件，需要刪除；滿足定義中的條件，需要刪除；a/x和和b/y滿足定義滿足定義中的條件，也需要刪除。最后得中的條件，也需要刪除。最后得 =f(b)/x, y/z323.2.5 置換與合一置換

53、與合一2. 合一合一 合一合一可理解為可理解為是尋找項對變量的置換，使兩個謂詞公式一致是尋找項對變量的置換，使兩個謂詞公式一致。可定義為：。可定義為： 定義定義3.12 設(shè)有公式集設(shè)有公式集F=F1, F2,Fn，若存在一個置換，若存在一個置換，可使，可使 F1=F2=Fn，則稱則稱是是F的一個合一。稱的一個合一。稱F1,F2,Fn是可合一的。是可合一的。 例如，例如，設(shè)有公式集設(shè)有公式集F=P(x,y,f(y), P(a,g(x),z)，則，則 =a/x, g(a)/y, f(g(a)/z是它的一個合一。是它的一個合一。 一般來說，一個公式集的合一不是唯一的。一般來說，一個公式集的合一不是唯

54、一的。 定義定義3.13 設(shè)設(shè)是公式集是公式集F的一個合一，如果對的一個合一，如果對F的任一個合一的任一個合一都存在一都存在一個置換個置換，使得，使得=，則稱，則稱是一個最一般合一。是一個最一般合一。 一個公式集的最一般合一是唯一的。一個公式集的最一般合一是唯一的。 對如何求取最一般合一的問題，不再討論。對如何求取最一般合一的問題，不再討論。33第第3章章 確定性推理確定性推理 3.1 推理的基本概念推理的基本概念 3.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 3.3 自然演繹推理自然演繹推理 3.4 歸結(jié)演繹推理歸結(jié)演繹推理 3.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理343.3 自然演繹推理自然演

55、繹推理 自然演繹推理自然演繹推理 從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。則推出結(jié)論的過程稱為自然演繹推理。 自然演繹推理最基本的推理規(guī)則是三段論推理，它包括：自然演繹推理最基本的推理規(guī)則是三段論推理，它包括： 假言推理假言推理 P, PQ Q 拒取式拒取式 Q, PQ P 假言三段論假言三段論 PQ, QR PR 自然演繹推理的例子自然演繹推理的例子 例例3.5 設(shè)已知如下事實：設(shè)已知如下事實： A, B, AC, BCD, DQ 求證：求證：Q為真。為真。 證明：證明：因為因為 A, AC C

56、 假言推理假言推理 B, C BC 引入合取詞引入合取詞 BC，BCD D 假言推理假言推理 D, DQ Q 假言推理假言推理 因此，因此，Q為真為真353.3 自然演繹推理自然演繹推理 例例3.6 設(shè)已知如下事實：設(shè)已知如下事實： (1) 只要是需要編程序的課，王程都喜歡。只要是需要編程序的課，王程都喜歡。 (2) 所有的程序設(shè)計語言課都是需要編程序的課。所有的程序設(shè)計語言課都是需要編程序的課。 (3) C是一門程序設(shè)計語言課。是一門程序設(shè)計語言課。求證：王程喜歡求證：王程喜歡C這門課。這門課。 證明：證明：首先定義謂詞首先定義謂詞 Prog(x) x是需要編程序的課。是需要編程序的課。 L

57、ike(x, y) x喜歡喜歡y。 Lang(x) x是一門程序設(shè)計語言課是一門程序設(shè)計語言課把已知事實及待求解問題用謂詞公式表示如下：把已知事實及待求解問題用謂詞公式表示如下： Prog(x)Like(Wang , x) (x)( Lang(x)Prog(x) Lang(C)應(yīng)用推理規(guī)則進行推理：應(yīng)用推理規(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因此，王程喜歡因此，王程

58、喜歡C這門課。這門課。 363.3 自然演繹推理自然演繹推理 優(yōu)點：優(yōu)點：定理證明過程自然，易于理解，并且有豐定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。富的推理規(guī)則可用。 缺點：缺點：是容易產(chǎn)生知識爆炸，推理過程中得到的是容易產(chǎn)生知識爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復雜問題的推中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復雜問題的推理不利，甚至難以實現(xiàn)。理不利，甚至難以實現(xiàn)。 37第第3章章 確定性推理確定性推理 3.1 推理的基本概念推理的基本概念 3.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 3.3 自然演繹推理自然演繹推理 3.4 歸結(jié)演繹推理歸結(jié)演繹推理 3.5 基于規(guī)則

59、的演繹推理基于規(guī)則的演繹推理383.4 歸結(jié)演繹推理歸結(jié)演繹推理 歸結(jié)演繹推理是一種基于魯賓遜（歸結(jié)演繹推理是一種基于魯賓遜（Robinson）歸結(jié)原理的機器推理）歸結(jié)原理的機器推理技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法反證法”。 在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)定理證明的實質(zhì)，就是要對前提，就是要對前提P和結(jié)論和結(jié)論Q，證

60、明，證明PQ永真。永真。 由由3.2節(jié)可知，要證明節(jié)可知，要證明PQ永真，就是要證明永真，就是要證明PQ在任何一個非空在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。 為此，人們進行了大量的探索，后來發(fā)現(xiàn)可以為此，人們進行了大量的探索，后來發(fā)現(xiàn)可以采用反證法的思想采用反證法的思想，把關(guān)于把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。 即要證明即要證明PQ永真，只要能夠證明永真，只要能夠證明PQ是不可滿足的就可以了是不可滿足的就可以了(原因是原因是 (PQ) ( PQ) P Q