第4章-確定性推理

1、第第4章章 確定性推理確定性推理 n智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定性，推理可分為確定性推理和不確定過程所用知識的確定性，推理可分為確定性推理和不確定性推理。對于推理的這兩種不同類型，本章重點討論前一性推理。對于推理的這兩種不同類型，本章重點討論前一種，不確定性推理放到下一章討論。種，不確定性推理放到下一章討論。 n4.1 推理的基本概念推理的基本概念n4.2 推理的邏輯基礎推理的邏輯基礎n4.3 自然演繹推理自然演繹推理n4.4 歸結演繹推理歸結演繹推理4.1 推理的基本概念推理的基本概念n4.1.1 什么

2、是推理什么是推理n4.1.2 推理方法及其分類推理方法及其分類n4.1.3 推理的控制策略及其分類推理的控制策略及其分類4.1.1 什么是推理什么是推理n推理的概念推理的概念n 是指按照某種策略從已知事實出發(fā)去推出結論的過程。是指按照某種策略從已知事實出發(fā)去推出結論的過程。n 推理所用的事實：推理所用的事實：n 初始證據：初始證據：推理前用戶提供的推理前用戶提供的n 中間結論：中間結論：推理過程中所得到的推理過程中所得到的n 推理過程：推理過程：由推理機來完成，所謂推理機就是智能系統(tǒng)由推理機來完成，所謂推理機就是智能系統(tǒng)中用來實現(xiàn)推理的那些程序。中用來實現(xiàn)推理的那些程序。n推理的兩個基本問題推

3、理的兩個基本問題n 推理的方法：推理的方法：解決前提和結論的邏輯關系，不確定性傳解決前提和結論的邏輯關系，不確定性傳遞遞n 推理的控制策略：推理的控制策略：解決推理方向，沖突消解策略解決推理方向，沖突消解策略4.1.2 推理方法及其分類推理方法及其分類n可分為演繹推理、歸納推理、默認推理可分為演繹推理、歸納推理、默認推理 n演繹推理演繹推理n 演繹推理是從已知的一般性知識出發(fā)，去推出蘊含在這些已知演繹推理是從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結論。是一種由一般到個別的推理知識中的適合于某種個別情況的結論。是一種由一般到個別的推理方法，其核心是三段論。方法，其

4、核心是三段論。n 例： 假言三段論n AB，BC ACn 常用的三段論是由一個大前提、一個小前提和一個結論這三部常用的三段論是由一個大前提、一個小前提和一個結論這三部分組成的。其中，分組成的。其中，大前提大前提是已知的一般性知識或推理過程得到的判是已知的一般性知識或推理過程得到的判斷；斷；小前提小前提是關于某種具體情況或某個具體實例的判斷；是關于某種具體情況或某個具體實例的判斷；結論結論是由是由大前提推出的，并且適合于小前提的判斷。大前提推出的，并且適合于小前提的判斷。n 1. 1. 按推理的邏輯基礎分類按推理的邏輯基礎分類(1/5)(1/5)例如：例如：有如下三個判斷：有如下三個判斷： 計算

5、機系的學生都會編程序；（一計算機系的學生都會編程序；（一般性知識）般性知識） 程強是計算機系的一位學生；（具程強是計算機系的一位學生；（具體情況）體情況） 程強會編程序。程強會編程序。 （結論）（結論） 這是一個三段論推理。其中，是大前這是一個三段論推理。其中，是大前提，是小前提；是經演繹推出來的結提，是小前提；是經演繹推出來的結論。論。 可見，其結論是蘊含在大前提中的?？梢?，其結論是蘊含在大前提中的。n歸納推理歸納推理n是一種由個別到一般的推理方法。歸納推理的類型是一種由個別到一般的推理方法。歸納推理的類型n 按照所選事例的廣泛性按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理可分為完

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

7、計算機，隨機抽查。事物的結論。例如，計算機，隨機抽查。n 枚舉歸納推理枚舉歸納推理n 是指在進行歸納時，如果已知某類事物的有限可數個具體事物都是指在進行歸納時，如果已知某類事物的有限可數個具體事物都具有某種屬性，則可推出該類事物都具有此種屬性。具有某種屬性，則可推出該類事物都具有此種屬性。4.1.2 推理方法及其分類推理方法及其分類1. 1. 按推理的邏輯基礎分類按推理的邏輯基礎分類(2/5)(2/5)例如：設有如下事例：例如：設有如下事例： 王強是計算機系學生，他會編程序；王強是計算機系學生，他會編程序； 高華是計算機系學生，她會編程序；高華是計算機系學生，她會編程序； 當這些具體事例足夠多

8、時，就可歸納出一個一般性的知識：當這些具體事例足夠多時，就可歸納出一個一般性的知識： 凡是計算機系的學生，就一定會編程序。凡是計算機系的學生，就一定會編程序。n類比歸納推理類比歸納推理n 是指在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它是指在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它們在其他屬性上也相同或相似的一種歸納推理。們在其他屬性上也相同或相似的一種歸納推理。n 設設A、B分別是兩類事物的集合：分別是兩類事物的集合：n A=a1,a2,n B=b1,b2,n并設并設ai與與bi總是成對出現(xiàn)，且當總是成對出現(xiàn)，且當ai有屬性有屬性P時，時，bi就有屬性就有屬性Q與此對應

9、，即與此對應，即n P(ai)Q(bi) i=1,2,.n 則當則當A與與B中有一新的元素對出現(xiàn)時，若已知中有一新的元素對出現(xiàn)時，若已知a有屬性有屬性P，b有屬性有屬性Q，即，即n P(a)Q(b)n 類比歸納推理的基礎是相似原理，其可靠程度取決于兩個或兩類事物的相類比歸納推理的基礎是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關程度。似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關程度。4.1.2 推理方法及其分類推理方法及其分類1. 1. 按推理的邏輯基礎分類按推理的邏輯基礎分類(3/5)(3/5)n默認推理默認推理

10、n 默認推理又被稱為缺省推理，它是在知識不完全的情況下假設某些默認推理又被稱為缺省推理，它是在知識不完全的情況下假設某些條件已經具備所進行的推理。條件已經具備所進行的推理。n 例如：在條件例如：在條件A已成立的情況下，如果沒有足夠的證據能證明條件已成立的情況下，如果沒有足夠的證據能證明條件B不成立，則默認不成立，則默認B是成立的，并在此默認的前提下進行推理，推導出某是成立的，并在此默認的前提下進行推理，推導出某個結論。個結論。n 由于這種推理允許某些默認條件是成立的，這就擺脫了需要知道全部由于這種推理允許某些默認條件是成立的，這就擺脫了需要知道全部有關事實才能進行推理的束縛，使得推理在知識不完

11、全的情況下也能進有關事實才能進行推理的束縛，使得推理在知識不完全的情況下也能進行。行。n 在默認推理中，如果到某一時刻發(fā)現(xiàn)原先所做的默認不正確，則要撤在默認推理中，如果到某一時刻發(fā)現(xiàn)原先所做的默認不正確，則要撤銷所做的默認以及由此默認推出的所有結論，重新按新情況進行推理。銷所做的默認以及由此默認推出的所有結論，重新按新情況進行推理。4.1.2 推理方法及其分類推理方法及其分類1. 1. 按推理的邏輯基礎分類按推理的邏輯基礎分類(4/5)(4/5)n演繹推理與歸納推理的區(qū)別演繹推理與歸納推理的區(qū)別n 演繹推理演繹推理是在已知領域內的一般性知識的前提下，通過演是在已知領域內的一般性知識的前提下，通

12、過演繹求解一個具體問題或者證明一個結論的正確性。它所得出繹求解一個具體問題或者證明一個結論的正確性。它所得出的結論實際上早已蘊含在一般性知識的前提中，演繹推理只的結論實際上早已蘊含在一般性知識的前提中，演繹推理只不過是將已有事實揭露出來，因此它不過是將已有事實揭露出來，因此它不能增殖新知識不能增殖新知識。n 歸納推理歸納推理所推出的結論是沒有包含在前提內容中的。這種所推出的結論是沒有包含在前提內容中的。這種由個別事物或現(xiàn)象推出一般性知識的過程，由個別事物或現(xiàn)象推出一般性知識的過程，是增殖新知識是增殖新知識的的過程。過程。n 例如，例如，一位計算機維修員，從書本知識，到通過大量實例一位計算機維修

13、員，從書本知識，到通過大量實例積累經驗，是一種積累經驗，是一種歸納歸納推理方式。運用這些一般性知識知識推理方式。運用這些一般性知識知識去維修計算機的過程則是去維修計算機的過程則是演繹演繹推理。推理。 4.1.2 推理方法及其分類推理方法及其分類1. 1. 按推理的邏輯基礎分類按推理的邏輯基礎分類(5/5)(5/5)4.1.2 推理方式及其分類 按推理過程中推出的結論是否單調地增加，或推出的結按推理過程中推出的結論是否單調地增加，或推出的結論是否越來越接近目標，可分為單調推理和非單調推理論是否越來越接近目標，可分為單調推理和非單調推理。 單調推理：單調推理：在推理過程中隨著推理的向前及新知識的加

14、在推理過程中隨著推理的向前及新知識的加入，推出的結論是呈單調增加的趨勢，并且越來越接近入，推出的結論是呈單調增加的趨勢，并且越來越接近最終目標，在推理過程中不出現(xiàn)反復的情況，即不會由最終目標，在推理過程中不出現(xiàn)反復的情況，即不會由于新知識的加入否定了前面推出的結論，從而使推理又于新知識的加入否定了前面推出的結論，從而使推理又回到前面的某一步?；氐角懊娴哪骋徊?。2 2、單調推理、非單調推理、單調推理、非單調推理(1/2)(1/2)4.1.2 推理方式及其分類 非單調推理：非單調推理：在推理過程中由于新知識的加入，不僅沒有在推理過程中由于新知識的加入，不僅沒有加強已推出的結論，反而要否定它，使得推

15、理退回到前面加強已推出的結論，反而要否定它，使得推理退回到前面的某一步，重新開始。的某一步，重新開始。 注意：注意：非單調推理是在知識不完全的情況下發(fā)生的。由于非單調推理是在知識不完全的情況下發(fā)生的。由于知識不完全，為使推理進行下去，就要先做某些假設，并知識不完全，為使推理進行下去，就要先做某些假設，并在此基礎上進行推理，當以后由于新知識的加入發(fā)現(xiàn)原先在此基礎上進行推理，當以后由于新知識的加入發(fā)現(xiàn)原先的假設不正確的時候，就需要推翻該假設以及基于此假設的假設不正確的時候，就需要推翻該假設以及基于此假設而推出的一切結論，再用新的知識重新進行推理。而推出的一切結論，再用新的知識重新進行推理。2 2、

16、單調推理、非單調推理、單調推理、非單調推理(2/2)(2/2)4.1.2 推理方式及其分類 按推理時所用知識的確定性來劃分，推理可分為確定性推理、按推理時所用知識的確定性來劃分，推理可分為確定性推理、不確定性推理。不確定性推理。 確定性推理（精確推理）：確定性推理（精確推理）：如果在推理中所用的知識都是精確如果在推理中所用的知識都是精確的，即可以把知識表示成必然的因果關系，然后進行邏輯推理的，即可以把知識表示成必然的因果關系，然后進行邏輯推理，推理的結論或者為真，或者為假，這種推理就稱為確定性推，推理的結論或者為真，或者為假，這種推理就稱為確定性推理。理。 如：在如：在MYCINMYCIN中采

17、用確定性方法是一種簡單有效的方法，僅中采用確定性方法是一種簡單有效的方法，僅采用一些簡單直觀的證據合并規(guī)則，其缺點是缺乏良好的理論采用一些簡單直觀的證據合并規(guī)則，其缺點是缺乏良好的理論基礎?；A。3 3、確定性推理、不確定性推理、確定性推理、不確定性推理(1/3)(1/3)4.1.2 推理方式及其分類 按推理時所用知識的確定性來劃分，推理可分為確定性推理、不按推理時所用知識的確定性來劃分，推理可分為確定性推理、不確定性推理。確定性推理。 不確定性推理（不精確推理）：不確定性推理（不精確推理）：在人類知識中，有相當一部分屬在人類知識中，有相當一部分屬于人們的主觀判斷，是不精確的和含糊的。由這些知

18、識歸納出來的于人們的主觀判斷，是不精確的和含糊的。由這些知識歸納出來的推理規(guī)則往往是不確定的?；谶@種不確定的推理規(guī)則進行推理，推理規(guī)則往往是不確定的。基于這種不確定的推理規(guī)則進行推理，形成的結論也是不確定的，這種推理稱為不確定性推理。形成的結論也是不確定的，這種推理稱為不確定性推理。 在專家系統(tǒng)中，主要使用的是不確定性推理。在專家系統(tǒng)中，主要使用的是不確定性推理。3 3、確定性推理、不確定性推理、確定性推理、不確定性推理(2/3)(2/3)4.1.2 推理方式及其分類 不確定性研究的重點可能會：不確定性研究的重點可能會： 一是：一是：解決現(xiàn)有處理不確定性的理論中存在的問題；解決現(xiàn)有處理不確定

19、性的理論中存在的問題； 二是：二是：大力研究人類高效、準確的識別能力和判斷機智大力研究人類高效、準確的識別能力和判斷機智，開拓新的處理不確定性的理論和方法；，開拓新的處理不確定性的理論和方法； 三是：三是：探索可以綜合處理多種不確定性的放法和技術。探索可以綜合處理多種不確定性的放法和技術。3 3、確定性推理、不確定性推理、確定性推理、不確定性推理(3/3)(3/3)4.1.2 推理方式及其分類 按推理過程中推出的結論是否單調地增加，或推出的結按推理過程中推出的結論是否單調地增加，或推出的結論是否越來越接近目標，可分為單調推理和非單調推理論是否越來越接近目標，可分為單調推理和非單調推理。 單調推

20、理：單調推理：在推理過程中隨著推理的向前及新知識的加在推理過程中隨著推理的向前及新知識的加入，推出的結論是呈單調增加的趨勢，并且越來越接近入，推出的結論是呈單調增加的趨勢，并且越來越接近最終目標，在推理過程中不出現(xiàn)反復的情況，即不會由最終目標，在推理過程中不出現(xiàn)反復的情況，即不會由于新知識的加入否定了前面推出的結論，從而使推理又于新知識的加入否定了前面推出的結論，從而使推理又回到前面的某一步?；氐角懊娴哪骋徊?。4 4、單調推理、非單調推理、單調推理、非單調推理(1/2)(1/2)4.1.2 推理方式及其分類 按推理過程中推出的結論是否單調地增加，或推出的結論是否按推理過程中推出的結論是否單調地

21、增加，或推出的結論是否越來越接近目標，可分為單調推理和非單調推理。越來越接近目標，可分為單調推理和非單調推理。 非單調推理：非單調推理：在推理過程中由于新知識的加入，不僅沒有加強在推理過程中由于新知識的加入，不僅沒有加強已推出的結論，反而要否定它，使得推理退回到前面的某一步已推出的結論，反而要否定它，使得推理退回到前面的某一步，重新開始。，重新開始。 注意：注意：非單調推理是在知識不完全的情況下發(fā)生的。由于知識不完非單調推理是在知識不完全的情況下發(fā)生的。由于知識不完全，為使推理進行下去，就要先做某些假設，并在此基礎上進行推理全，為使推理進行下去，就要先做某些假設，并在此基礎上進行推理，當以后由

22、于新知識的加入發(fā)現(xiàn)原先的假設不正確的時候，就需要推，當以后由于新知識的加入發(fā)現(xiàn)原先的假設不正確的時候，就需要推翻該假設以及基于此假設而推出的一切結論，再用新的知識重新進行翻該假設以及基于此假設而推出的一切結論，再用新的知識重新進行推理。推理。4 4、單調推理、非單調推理、單調推理、非單調推理(2/2)(2/2)4.1.2 推理方式及其分類 如果按推理程中是否運用于問題有關的啟發(fā)性知識，推如果按推理程中是否運用于問題有關的啟發(fā)性知識，推理可分為啟發(fā)式推理與非啟發(fā)式推理。理可分為啟發(fā)式推理與非啟發(fā)式推理。 啟發(fā)式推理：啟發(fā)式推理：如果在推理過程中，運用了與問題有關的如果在推理過程中，運用了與問題有

23、關的啟發(fā)性知識，即解決問題的策略、技巧及經驗，以加快啟發(fā)性知識，即解決問題的策略、技巧及經驗，以加快推理過程，提高搜索效率，這種推理過程就被稱為啟發(fā)推理過程，提高搜索效率，這種推理過程就被稱為啟發(fā)式推理。式推理。 如第三章的如第三章的A A* *、AOAO* *等算法就屬于此類推理。等算法就屬于此類推理。5 5、啟發(fā)式推理、非啟發(fā)式推理、啟發(fā)式推理、非啟發(fā)式推理(1/2)(1/2)4.1.2 推理方式及其分類 非啟發(fā)式推理：非啟發(fā)式推理：如果在推理過程中，不運用啟發(fā)性知識，如果在推理過程中，不運用啟發(fā)性知識，只按照一般的控制邏輯進行推理，這種推理過程就被稱為只按照一般的控制邏輯進行推理，這種推

24、理過程就被稱為非啟發(fā)式推理。非啟發(fā)式推理。 注意：注意：這種推理缺乏對待求解問題的針對性，所以推理效這種推理缺乏對待求解問題的針對性，所以推理效率較低，容易出現(xiàn)組合爆炸問題。如圖搜索策略頭重的寬率較低，容易出現(xiàn)組合爆炸問題。如圖搜索策略頭重的寬度優(yōu)先搜索法，雖然是完備的算法，但是對復雜問題的求度優(yōu)先搜索法，雖然是完備的算法，但是對復雜問題的求解，將出現(xiàn)組合爆炸現(xiàn)象，其搜索效率較低。解，將出現(xiàn)組合爆炸現(xiàn)象，其搜索效率較低。5 5、啟發(fā)式推理、非啟發(fā)式推理、啟發(fā)式推理、非啟發(fā)式推理(2/2)(2/2)4.1.3 推理的控制策略n推理的控制策略推理的控制策略主要包括推理方向、搜索策略、沖突消解策略、

25、求解策略及限制策略等。1、推理方向n推理方向用于確定推理的驅動方式，分為四種： 正向推理 逆向推理 混合推理 雙向推理4.1.3 推理的控制策略n正向推理正向推理 正向推理是從初始狀態(tài)出發(fā)，使用規(guī)則，到達正向推理是從初始狀態(tài)出發(fā)，使用規(guī)則，到達目標狀態(tài)。又稱為數據驅動推理、前向鏈推理、模目標狀態(tài)。又稱為數據驅動推理、前向鏈推理、模式制導推理及前件推理。式制導推理及前件推理。n逆向推理逆向推理 逆向推理是以某個假設目標為出發(fā)點的一種推逆向推理是以某個假設目標為出發(fā)點的一種推理，又稱為目標驅動推理、逆向鏈推理、目標制導理，又稱為目標驅動推理、逆向鏈推理、目標制導推理及后件推理。推理及后件推理。4.

26、1.3 推理的控制策略n混合推理混合推理 已知的事實不充分。通過正向推理先把其運用條件不已知的事實不充分。通過正向推理先把其運用條件不能完全匹配的知識都找出來，并把這些知識可導出的結能完全匹配的知識都找出來，并把這些知識可導出的結論作為假設，然后分別對這些假設進行逆向推理。論作為假設，然后分別對這些假設進行逆向推理。n推理的形式：推理的形式：先正向再逆向，通過正向推理，即從已知事實演繹先正向再逆向，通過正向推理，即從已知事實演繹出部分結果，然后再用逆向推理證實該目標或提高出部分結果，然后再用逆向推理證實該目標或提高其可信度。其可信度。先逆向再正向，先假設一個目標進行逆向推理，然先逆向再正向，先

27、假設一個目標進行逆向推理，然后再利用逆向推理中得到的信息進行正向推理，以后再利用逆向推理中得到的信息進行正向推理，以推出更多的結論。推出更多的結論。4.1.3 推理的控制策略n雙向推理雙向推理雙向推理是指正向推理與逆向推理同時進行，且在推雙向推理是指正向推理與逆向推理同時進行，且在推理過程中的某一步驟上理過程中的某一步驟上“碰頭碰頭”的一種推理。的一種推理。正向推理所得的中間結論恰好是逆向推理此時要求的正向推理所得的中間結論恰好是逆向推理此時要求的證據證據2、求解策略 推理是只求一個解還是求所有解以及最優(yōu)解等推理是只求一個解還是求所有解以及最優(yōu)解等3、限制策略 對推理的深度、寬度、時間、空間等

28、進行限制對推理的深度、寬度、時間、空間等進行限制4.1.3 推理的控制策略4、沖突消解策略沖突消解策略 n在推理過程中，匹配會出現(xiàn)三種情況：在推理過程中，匹配會出現(xiàn)三種情況：已知事實不能與知識庫中的任何知識匹配成功已知事實不能與知識庫中的任何知識匹配成功已知事實恰好只與知識庫中的一個知識匹配成功已知事實恰好只與知識庫中的一個知識匹配成功已知事實可與知識庫中的多個知識匹配成功；或者有多已知事實可與知識庫中的多個知識匹配成功；或者有多個（組）已知事實都可與知識庫中某一知識匹配成功；個（組）已知事實都可與知識庫中某一知識匹配成功；或者有多個（組）已知事實可與知識庫中的多個知識匹或者有多個（組）已知事

29、實可與知識庫中的多個知識匹配成功配成功4.1.3 推理的控制策略4、沖突消解策略沖突消解策略 出現(xiàn)沖突的情況出現(xiàn)沖突的情況對正向推理而言，如果有多條產生式規(guī)則的前件都和已知對正向推理而言，如果有多條產生式規(guī)則的前件都和已知的事實匹配成功；或者有多組不同的已知事實都與同一條的事實匹配成功；或者有多組不同的已知事實都與同一條產生式規(guī)則的前件匹配成功；或者兩種情況同時出現(xiàn)產生式規(guī)則的前件匹配成功；或者兩種情況同時出現(xiàn)對逆向推理而言，如果有多條產生式的后件都和同一假設對逆向推理而言，如果有多條產生式的后件都和同一假設匹配成功，或者有多條產生式后件可與多個假設匹配成功匹配成功，或者有多條產生式后件可與多

30、個假設匹配成功。4.1.3 推理的控制策略沖突消解策略沖突消解策略按就近原則排序按就近原則排序l該策略把最近被使用過的規(guī)則賦予較高的優(yōu)先級。該策略把最近被使用過的規(guī)則賦予較高的優(yōu)先級。 按已知事實的新鮮性排序按已知事實的新鮮性排序 l一般我們認為新鮮事實是對舊知識的更新和改進，比一般我們認為新鮮事實是對舊知識的更新和改進，比老知識更有效，即后生成的事實比先生成的事實具有老知識更有效，即后生成的事實比先生成的事實具有較大的優(yōu)先性。較大的優(yōu)先性。 4.1.3 推理的控制策略沖突消解策略沖突消解策略n按匹配度排序按匹配度排序 l在不確定推理時，匹配度不僅可確定兩個知識在不確定推理時，匹配度不僅可確定

31、兩個知識模式是否可匹配，還可用于沖突消解。根據匹模式是否可匹配，還可用于沖突消解。根據匹配程度來決定哪一個產生式規(guī)則優(yōu)先被應用。配程度來決定哪一個產生式規(guī)則優(yōu)先被應用。l按領域問題特點排序按領域問題特點排序 l該方法按照求解問題領域的特點將知識排成固該方法按照求解問題領域的特點將知識排成固定的次序定的次序4.1.3 推理的控制策略沖突消解策略沖突消解策略l按上下文限制排序按上下文限制排序l該策略將知識按照所描述的上下文分成若干組，在推該策略將知識按照所描述的上下文分成若干組，在推理過程中根據當前數據庫中的已知事實與上下文的匹理過程中根據當前數據庫中的已知事實與上下文的匹配情況，確定選擇某組中的

32、某條知識。配情況，確定選擇某組中的某條知識。n按條件個數排序按條件個數排序l多條規(guī)則生成的結論相同的情況下，由于條件個數較多條規(guī)則生成的結論相同的情況下，由于條件個數較少的規(guī)則匹配所花費的時間較少而且容易實現(xiàn)，所以少的規(guī)則匹配所花費的時間較少而且容易實現(xiàn)，所以將條件少的規(guī)則賦予較高的優(yōu)先級，優(yōu)先被啟用。將條件少的規(guī)則賦予較高的優(yōu)先級，優(yōu)先被啟用。 4.1.3 推理的控制策略沖突消解策略沖突消解策略l按規(guī)則的次序排序按規(guī)則的次序排序 l該策略是以知識庫中預先存入規(guī)則的排列順序作該策略是以知識庫中預先存入規(guī)則的排列順序作為知識排序的依據，排在前面的規(guī)則具有較高的為知識排序的依據，排在前面的規(guī)則具有

33、較高的優(yōu)先級。優(yōu)先級。 第4章 確定性推理 n4.1 推理的基本概念推理的基本概念n4.2 推理的邏輯基礎推理的邏輯基礎n4.3 自然演繹推理自然演繹推理n4.4 歸結演繹推理歸結演繹推理4.2 推理的邏輯基礎推理的邏輯基礎n4.2.1 謂詞與個體謂詞與個體n4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n4.2.3 置換與合一置換與合一4.2.1 謂詞與個體謂詞與個體n在謂詞邏輯中，可以將原子命題分解為在謂詞邏輯中，可以將原子命題分解為謂詞謂詞與與個體個體兩部分。兩部分。個體：個體：是指可以獨立存在的物體，可以是抽象的或具是指可以獨立存在的物體，可以是抽象的或具體的。體的。

34、謂詞：謂詞：則用于刻畫個體的性質、狀態(tài)或個體間的關系。則用于刻畫個體的性質、狀態(tài)或個體間的關系。例如：例如：“李白是詩人李白是詩人”可表示為可表示為poet(LiBai)，poet稱稱為謂詞，用以刻畫為謂詞，用以刻畫“是詩人是詩人”；LiBai稱為個體。稱為個體。4.2.1 謂詞與個體謂詞與個體n一元謂詞：一元謂詞：一個謂詞，可以與一個個體相關聯(lián)，這種一個謂詞，可以與一個個體相關聯(lián)，這種謂詞稱作一元謂詞，謂詞稱作一元謂詞，它刻畫了個體的性質。它刻畫了個體的性質。n多元謂詞：多元謂詞：一個謂詞，可以與多個個體相關聯(lián)，這種一個謂詞，可以與多個個體相關聯(lián)，這種謂詞稱作多元謂詞，謂詞稱作多元謂詞，它刻

35、畫了個體間的關系。它刻畫了個體間的關系。n謂詞的一般形式謂詞的一般形式可表示為：可表示為： P(x1,x2, ,xn)n其中其中P P是謂詞，而是謂詞，而x x1 1,x,x2 2, ,x, ,xn n是個體。謂詞通常用大是個體。謂詞通常用大寫字母表示，個體通常用小寫字母表示。寫字母表示，個體通常用小寫字母表示。4.2.1 謂詞與個體謂詞與個體n注意事項：注意事項：n謂詞的項：謂詞的項：在謂詞中，個體可以是常量，也可以是變量，在謂詞中，個體可以是常量，也可以是變量，還可以是一個函數。例如：還可以是一個函數。例如：“小劉的哥哥是個個人小劉的哥哥是個個人”，可，可以表示為以表示為worker(br

36、other(Liu)，其中，其中brother(Liu)是一個是一個函數。個體常量、變量和函數統(tǒng)稱為項。函數。個體常量、變量和函數統(tǒng)稱為項。n謂詞的語義：謂詞的語義：由使用者根據需要人為地定義。由使用者根據需要人為地定義。n謂詞的元數：謂詞的元數：謂詞中包含的個體變量的數目稱為謂詞的元謂詞中包含的個體變量的數目稱為謂詞的元數。數。4.2.1 謂詞與個體謂詞與個體n注意事項：注意事項：n謂詞的階數：謂詞的階數：在謂詞在謂詞P(x1,x2, ,xn)中，若中，若xi(i=1,2, ,n)都都是個體常量、變量或函數，則稱它為一階謂詞。若某個是個體常量、變量或函數，則稱它為一階謂詞。若某個xi本身又是

37、一個一階謂詞，則稱它為二階謂詞，依次類推。本身又是一個一階謂詞，則稱它為二階謂詞，依次類推。n謂詞與函數的區(qū)別：謂詞與函數的區(qū)別：謂詞具有邏輯值謂詞具有邏輯值“真真”或或“假假”，而，而函數則是某個個體到另一個個體（數學上：自變量到因變函數則是某個個體到另一個個體（數學上：自變量到因變量）之間的映射。量）之間的映射。4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n定義定義4.1 設設D是謂詞公式是謂詞公式P的非空個體域，若對的非空個體域，若對P中的個體中的個體常量、函數和謂詞按如下規(guī)定賦值：常量、函數和謂詞按如下規(guī)定賦值：n (1) 為每個個體常量指派為每個個體常量指派D中的

38、一個元素；中的一個元素；n (2) 為每個為每個n元函數指派一個從元函數指派一個從Dn到到D的一個映射，其中的一個映射，其中n Dn =(x1, x2, , xn)| x1, x2, , xnDn (3) 為每個為每個n元謂詞指派一個從元謂詞指派一個從Dn到到F，T的映射。的映射。n則稱這些指派為則稱這些指派為P在在D上的一個解釋上的一個解釋。n1、謂詞公式的解釋、謂詞公式的解釋n 例例4.1 設個體域設個體域D=1, 2，求公式，求公式A=(x)( y)P(x, y)在在D上的解釋，并上的解釋，并指出在每一種解釋下公式指出在每一種解釋下公式A的真值。的真值。 n 解：解：由于公式由于公式A中

39、沒有包含個體常量和函數，故可直接為謂詞指派真中沒有包含個體常量和函數，故可直接為謂詞指派真值，設有值，設有n這就是公式這就是公式A 在在D 上的一個解釋。從這個解釋可以看出：上的一個解釋。從這個解釋可以看出：n 當當x=1、y=1時，有時，有P(x,y)的真值為的真值為T;n 當當x=2、y=1時，有時，有P(x,y)的真值為的真值為T;n 即對即對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 F4.2.2 謂詞公式的

40、永真性和可滿足性謂詞公式的永真性和可滿足性n1、謂詞公式的解釋、謂詞公式的解釋n說明：說明：一個謂詞公式在其個體域上的解釋不是唯一的。例如，對公式一個謂詞公式在其個體域上的解釋不是唯一的。例如，對公式A，若給出另一組真值指派若給出另一組真值指派n這也是公式這也是公式A 在在D 上的一個解釋。從這個解釋可以看出：上的一個解釋。從這個解釋可以看出：n 當當x=1、y=1時，有時，有P(x,y)的真值為的真值為T;n 當當x=2、y=1時，有時，有P(x,y)的真值為的真值為F;n即對即對x在在D上的任意取值，不存在一個上的任意取值，不存在一個y使得使得P(x,y)的真值為的真值為T。因此，。因此，

41、在此解釋下公式在此解釋下公式A的真值為的真值為F。n 實際上，實際上，A在在D上共有上共有16種解釋，這里就不在一一列舉。種解釋，這里就不在一一列舉。 P(1,1) P(1,2) P(2,1) P(2,2) TT F F4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n定義定義4.2 如果謂詞公式如果謂詞公式P對非空個體域對非空個體域D上的任一解釋都取上的任一解釋都取得真值得真值T，則稱，則稱P在在D 上是永真的上是永真的；如果；如果P在任何非空個體域在任何非空個體域上均是永真的，則稱上均是永真的，則稱P永真。永真。n 可見，要判定一謂詞公式為永真，必須對每個非空個體域可見，要

42、判定一謂詞公式為永真，必須對每個非空個體域上的每個解釋逐一進行判斷。當解釋的個數為有限時，盡上的每個解釋逐一進行判斷。當解釋的個數為有限時，盡管工作量大，公式的永真性畢竟還可以判定，但當解釋個管工作量大，公式的永真性畢竟還可以判定，但當解釋個數為無限時，其永真性就很難判定了。數為無限時，其永真性就很難判定了。4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n2、謂詞公式的永真性、謂詞公式的永真性n定義定義4.3 如果謂詞公式如果謂詞公式P對非空個體域對非空個體域D上的任一解釋都取假上的任一解釋都取假值值F，則稱，則稱P在在D上是永假的上是永假的；如果；如果P在任何非空個體域上均

43、在任何非空個體域上均是永假的，則稱是永假的，則稱P永假。永假。n謂詞公式的永假性又稱謂詞公式的永假性又稱不可滿足性或不相容。不可滿足性或不相容。4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n2、謂詞公式的永真性、謂詞公式的永真性n定義定義4.4 對于謂詞公式對于謂詞公式P，如果至少存在，如果至少存在D上的一個解釋，上的一個解釋，使公式使公式P在此解釋下的真值為在此解釋下的真值為T，則稱公式，則稱公式P在在D上是可滿上是可滿足的。足的。n謂詞公式的謂詞公式的可滿足性也稱為相容性?？蓾M足性也稱為相容性。n按照定義按照定義4.4，對謂詞公式，對謂詞公式P，如果不存在任何解釋，使得

44、，如果不存在任何解釋，使得P的取值為的取值為T，則稱公式，則稱公式P是不可滿足的。所以謂詞公式是不可滿足的。所以謂詞公式P的永假與不可滿足是等價的。的永假與不可滿足是等價的。n后面我們要給出的歸結推理，就是采用一種邏輯上的反證后面我們要給出的歸結推理，就是采用一種邏輯上的反證法，將永真性轉換為不可滿足性的證明。法，將永真性轉換為不可滿足性的證明。4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n3、謂詞公式的可滿足性、謂詞公式的可滿足性n謂詞公式的謂詞公式的等價式可定義如下：等價式可定義如下：n定義定義4.5 設設P與與Q是是D上的兩個謂詞公式，上的兩個謂詞公式，D是它是它們共

45、同的個體域。若對們共同的個體域。若對D上的任意解釋，上的任意解釋，P與與Q的的取值都相同，則稱公式取值都相同，則稱公式P與與Q在域在域D上是等價的。上是等價的。如果如果D是任意非空個體域，則稱是任意非空個體域，則稱P與與Q是等價的。是等價的。記作：記作：PQ。 4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n4、謂詞公式的等價性與永真蘊含、謂詞公式的等價性與永真蘊含n雙重否定律雙重否定律(double negation law): (P(x) P(x)n德德摩根定律摩根定律(Mogen law): (P(x)Q(x) P(x) Q(x) (P(x)Q(x) P(x) Q(x)

46、n逆否律逆否律(inverse-negation law):P(x) Q(x) Q(x) P(x)n分配律分配律(assignment law):P(x)(Q(x)R(x)(P(x)Q(x)(P(x)R(x)P(x)(Q(x)R(x)(P(x)Q(x)(P(x)R(x)附附1 1：謂詞演算的基本等價式謂詞演算的基本等價式4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n結合律結合律(association law): （P(x)Q(x)R(x)P(x)(Q(x)R(x) （P(x)Q(x)R(x)P(x)(Q(x)R(x)n蘊含等價式蘊含等價式(implication law)

47、: P(x)Q(x)P(x)Q(x)n易名規(guī)則易名規(guī)則(rename law): xP(x) xQ(x) x P(x) yQ(y)n量詞轉換律量詞轉換律(quantifier transform law): xP(x) xP(x) xP(x) xP(x)附附1 1：謂詞演算的基本等價式謂詞演算的基本等價式4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n量詞分配律量詞分配律(quantifier assignment law): x(P(x)Q(x) xP(x) xQ(x) x(P(x)Q(x) xP(x) xQ(x) x(PQ(x)P xQ(x) x(PQ(x)P xQ(x)

48、n量詞交換律量詞交換律(quantifier commutative law): 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) ) y x(P(x, y) x y(P(x, y) )y x(P(x, y)附附1 1：謂詞演算的基本等價式謂詞演算的基本等價式4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n量詞轄域變換等價式量詞轄域變換等價式: xP(x)Q x(P(x)Q) xP(x)Q x(P(x)Q) xP(x)Q x(P(x)Q) xP(x)Q x(P(x)Q)Q中不含變量中不含變量附附1 1：

49、謂詞演算的基本等價式謂詞演算的基本等價式4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性 全稱量詞消去規(guī)則全稱量詞消去規(guī)則: xP(x)P(y) 全稱量詞引入規(guī)則全稱量詞引入規(guī)則: P(y) xP(x) 存在量詞消去規(guī)則存在量詞消去規(guī)則: xQ(x)Q(c)(c為常量為常量) 存在量詞引人規(guī)則存在量詞引人規(guī)則: Q(c) xQ(x) 有限域量詞消去規(guī)則有限域量詞消去規(guī)則:設有限個體域為設有限個體域為D d1,d2,dn xP(x)P(d1)P(d2),P(dn) xQ(x)Q(d1) Q(d2),Q(dn)附附2 2：量詞消去及引入規(guī)則量詞消去及引入規(guī)則4.2.2 謂詞公式的永

50、真性和可滿足性謂詞公式的永真性和可滿足性n 定義定義4.6 對謂詞公式對謂詞公式P和和Q，如果，如果PQ永真，則稱永真，則稱P 永真蘊永真蘊含含Q，且稱，且稱Q為為P的邏輯結論，的邏輯結論，P為為Q的前提。的前提。記作記作P Q。 4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n4、謂詞公式的等價性與永真蘊含、謂詞公式的等價性與永真蘊含n推理規(guī)則：推理規(guī)則：nP規(guī)則：規(guī)則：在推理的任何步驟上都可引入前提。在推理的任何步驟上都可引入前提。nT規(guī)則：規(guī)則：推理時，如果前面步驟中有一個或多個永真蘊含公式推理時，如果前面步驟中有一個或多個永真蘊含公式S，則可把，則可把S引入推理過程中

51、。引入推理過程中。nCP規(guī)則：規(guī)則：如果能從如果能從R和前提集合中推出和前提集合中推出S來，則可從前提集合推出來，則可從前提集合推出RS。n反證法：反證法： P Q，當且僅當，當且僅當P Q F，即，即Q為為P的邏輯結論，當且僅的邏輯結論，當且僅當當P Q 是不可滿足的。是不可滿足的。由此得到如下定理：由此得到如下定理：定理定理4.1：Q為為P1,P2,Pn的邏輯的邏輯結論，當且僅當（結論，當且僅當（ P1P2 Pn)Q是不可滿足的。是不可滿足的。 n常用的永真蘊含式如下：常用的永真蘊含式如下：n (1) 化簡式化簡式 PQ P， PQ Qn (2) 附加式附加式 P PQ， Q PQn (3

52、) 析取三段論析取三段論 P, PQ Qn (4) 假言推理假言推理 P, PQ Qn (5) 拒取式拒取式 Q, PQ Pn (6) 假言三段論假言三段論 PQ, QR PRn (7) 二難推理二難推理 PQ, PR, QR R n (8) 全稱固化全稱固化 (x)P(x) P(y)n 其中，其中，y是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。n (9) 存在固化存在固化 (x)P(x) P(y)n 其中，其中，y是個體域中某一個可以使是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公為真的個體，依此可消去謂詞公式中的存

53、在量詞。式中的存在量詞。4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n4、謂詞公式的等價性與永真蘊含、謂詞公式的等價性與永真蘊含4.2 推理的邏輯基礎推理的邏輯基礎n4.2.1 謂詞與個體謂詞與個體n4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性n4.2.3 置換與合一置換與合一n置換可簡單的理解為是在一個謂詞公式中用置換項去替換變量。置換可簡單的理解為是在一個謂詞公式中用置換項去替換變量。n定義定義4.74.7 置換是形如置換是形如t1/x1,t2/x2,tn/xn的有限集合。其中，的有限集合。其中，t1,t2,tn是項；是項；x1,x2,xn是互不相同

54、的變元；是互不相同的變元；ti/xi表示用表示用ti替換替換xi。并且要求并且要求ti與與xi不能相同，不能相同，xi不能循環(huán)地出現(xiàn)在另一個不能循環(huán)地出現(xiàn)在另一個ti中。中。n例如，例如， a/x, c/y, f(b)/z 是一個置換。是一個置換。n但但g(y)/x, f(x)/y不是一個置換。原因是它在不是一個置換。原因是它在x與與y之間出現(xiàn)了循之間出現(xiàn)了循環(huán)置換現(xiàn)象。通常，置換是用希臘字母環(huán)置換現(xiàn)象。通常，置換是用希臘字母、 、 等來表示的。等來表示的。n不含任何元素的置換稱為空置換，以不含任何元素的置換稱為空置換，以 表示。表示。4.2.3 置換與合一置換與合一n1、置換、置換(1) 空

55、置換空置換 是左么元和右么元，即對任意的置換是左么元和右么元，即對任意的置換 , 恒有恒有 (2) 對任意表達式對任意表達式E，恒有，恒有E( )(E ) 。(3) 若對任意表達式若對任意表達式E恒有恒有E E ，則，則 。(4) 對任意置換對任意置換 ， ， , 恒有恒有 即置換的合成滿足結合律。即置換的合成滿足結合律。(5) 設設A和和B為表達式集合，則為表達式集合，則 注意注意: 置換的合成不滿足交換律。置換的合成不滿足交換律。()ABAB n2、置換的性質、置換的性質4.2.3 置換與合一置換與合一n3、置換乘法、置換乘法定義定義4.8 設設 =t1/x1,t2/x2,tn/xn =

56、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)最后剩下的元素所構成的集合。最后剩下的元素所構成的集合。4.2.3 置換與合一置換與合一n例例4.2 設設= f(y)/x, z/y ，=

57、a/x, b/y ,y/z ，求，求與與的合成。的合成。n 解解:先求出集合先求出集合n f(y)/x, (z)/y, a/x, b/y , y/z=f(b)/x, y/y, a/x, b/y , y/zn其中，其中，f(b)/x中的中的f(b)是置換是置換作用于作用于f(y)的結果；的結果；y/y 中的中的y是置是置換換作用于作用于z的結果。在該集合中，的結果。在該集合中，y/y滿足定義中的條件，滿足定義中的條件，需要刪除；需要刪除；a/x和和b/y滿足定義中的條件，也需要刪除。最后滿足定義中的條件，也需要刪除。最后得得:=f(b)/x, y/zn3、置換乘法、置換乘法4.2.3 置換與合一

58、置換與合一n合一合一可理解為可理解為是尋找項對變量的置換，使兩個謂詞公式一致是尋找項對變量的置換，使兩個謂詞公式一致?？啥ā？啥x為：義為：n定義定義4.94.9 設有公式集設有公式集F=F1, F2,Fn，若存在一個置換，若存在一個置換，可使，可使n F1=F2=Fn，n則稱則稱是是F的一個合一。稱的一個合一。稱F1,F2,Fn是可合一的。是可合一的。n 例例4.34.3 設有公式集設有公式集F=P(x,y,f(y), P(a,g(x),z)，則，則n =a/x, g(a)/y, f(g(a)/zn是它的一個合一。是它的一個合一。n 一般來說，一個公式集的合一不是唯一的。一般來說，一個公式集

59、的合一不是唯一的。n4、合一、合一4.2.3 置換與合一置換與合一n定義定義4.104.10 設設是公式集是公式集F的一個合一，如果對的一個合一，如果對F的任一個的任一個合一合一都存在一個置換都存在一個置換，使得，使得=，則稱，則稱是一個最一是一個最一般合一般合一(MGU)。n 一個公式集的最一般合一是唯一的。一個公式集的最一般合一是唯一的。n5、最一般合一、最一般合一(MGU, Most General Unifier)4.2.3 置換與合一置換與合一n6、MGU算法算法4.2.3 置換與合一置換與合一 定義定義4.11 表達式的非空集合表達式的非空集合W的差異集的差異集(differenc

60、e set)是按下述是按下述方法得出的子表達式的集合方法得出的子表達式的集合： （1）在在W的所有表達式中找出對應符號不全相同的第一個符號的所有表達式中找出對應符號不全相同的第一個符號(自左算起自左算起)。 （2）在在W的每個表達式中的每個表達式中，提取出占有該符號位置的子表達式提取出占有該符號位置的子表達式。這些子表達式的集合便是。這些子表達式的集合便是W的的差異集差異集D。例例4.44.4：W=P(x,f(y,z),P(x,a),P(x,g(h(k(x),在在W的的3個表達式中，個表達式中，前前4個符號個符號-“P(x,”是相同的，第是相同的，第5個符號不全相同，所以個符號不全相同，所以W