人工智能原理ch4.1_經(jīng)典邏輯推理

1、2021-10-311人工智能原理第四講第四講經(jīng)典邏輯推理經(jīng)典邏輯推理主講：王祖喜主講：王祖喜華中科技大學(xué)圖像所華中科技大學(xué)圖像所2021-10-312經(jīng)典邏輯推理經(jīng)典邏輯推理 經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯的邏輯規(guī)則進行經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯的邏輯規(guī)則進行的 一 種 推 理 ， 又 稱 為 機 械的 一 種 推 理 ， 又 稱 為 機 械 - 自 動 定 理 證 明自 動 定 理 證 明(mechanical-automatic theorem proving),主要推理主要推理方法有自然演繹推理，歸結(jié)演繹推理及與或形演方法有自然演繹推理，歸結(jié)演繹推理及與或形演繹推理等。由于這種推理是基于經(jīng)

2、典邏輯的，其繹推理等。由于這種推理是基于經(jīng)典邏輯的，其真值只有真和假兩種，因此它是一種精確推理。真值只有真和假兩種，因此它是一種精確推理。學(xué)習(xí)目的：學(xué)習(xí)目的： 學(xué)習(xí)學(xué)習(xí)運用知識進行推理，求解問題運用知識進行推理，求解問題 。 2021-10-313主要講述內(nèi)容：主要講述內(nèi)容： 1. 簡述與推理相關(guān)的知識：如推理方式及分類、簡述與推理相關(guān)的知識：如推理方式及分類、推理控制策略、模式匹配、沖突消解策略、搜索推理控制策略、模式匹配、沖突消解策略、搜索策略等。策略等。 2. 經(jīng)典邏輯推理：自然演繹推理、歸結(jié)演繹推理經(jīng)典邏輯推理：自然演繹推理、歸結(jié)演繹推理和與和與/或形演繹推理?；蛐窝堇[推理。2021-

3、10-314 什么是推理什么是推理 推理推理從已知事實出發(fā)，運用已掌握的知識，找出其中蘊從已知事實出發(fā)，運用已掌握的知識，找出其中蘊含的事實，或歸結(jié)出新的事實，這一過程稱為推理。含的事實，或歸結(jié)出新的事實，這一過程稱為推理。推理機推理機在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機。在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機。推理包括兩種判斷：一種是已知的判斷，它包括已掌握推理包括兩種判斷：一種是已知的判斷，它包括已掌握的與求解問題有關(guān)的知識以及關(guān)于問題的已知事實；另的與求解問題有關(guān)的知識以及關(guān)于問題的已知事實；另一種是由已知判斷推出的新判斷，即推理的結(jié)論。一種是由已知判斷推出的新判斷，即推理

4、的結(jié)論。推理的基本任務(wù)：是從一種判斷推出另一種判斷。推理的基本任務(wù)：是從一種判斷推出另一種判斷。1 推理的基本概念2021-10-315一般而言，推理有一下五種劃分方式：一般而言，推理有一下五種劃分方式：.演繹推理、歸結(jié)推理、默認(rèn)推理演繹推理、歸結(jié)推理、默認(rèn)推理（從新判斷推（從新判斷推出的途徑來劃分）出的途徑來劃分）演繹推理演繹推理從全稱判斷推導(dǎo)出特稱判斷或單稱判從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程，即由一般性知識推出適合于某一具體情斷的過程，即由一般性知識推出適合于某一具體情況的結(jié)論。這是一種從一般到個別的推理。演繹推況的結(jié)論。這是一種從一般到個別的推理。演繹推理有多種形式，經(jīng)常用的是三

5、段論式，它包括：理有多種形式，經(jīng)常用的是三段論式，它包括：1) 大前提，這是已知的一般性知識或假設(shè)；大前提，這是已知的一般性知識或假設(shè)；2) 小前提，這是關(guān)于所研究的具體情況或個別小前提，這是關(guān)于所研究的具體情況或個別事實的判斷；事實的判斷；推理的方式及其分類2021-10-3163) 結(jié)論，這是由大前提推出的適合于小前提所結(jié)論，這是由大前提推出的適合于小前提所示情況的新判斷。示情況的新判斷。例如：例如： 1) 足球運動員的身體都是強壯的；足球運動員的身體都是強壯的； 2) 高波是一名足球運動員；高波是一名足球運動員； 3) 所以，高波的身體是強壯的。所以，高波的身體是強壯的。這就是一個三段論

6、推理，其中，這就是一個三段論推理，其中，(1) 是大前提，是大前提，(2)是小前提，是小前提，(3) 是經(jīng)演是經(jīng)演 繹推出的結(jié)論。結(jié)論繹推出的結(jié)論。結(jié)論“高高波的身體是強壯的波的身體是強壯的”事實上是蘊含于事實上是蘊含于“足球運動足球運動員的身體都是強壯的員的身體都是強壯的”這一大前提中的。它沒有這一大前提中的。它沒有超出超出2021-10-317 大前提所斷定的范圍。這是演繹推理的一個典大前提所斷定的范圍。這是演繹推理的一個典型特征，即在任何情況下，由演繹推理導(dǎo)出的型特征，即在任何情況下，由演繹推理導(dǎo)出的結(jié)論都是蘊含在大前提的一般性知識中的。因結(jié)論都是蘊含在大前提的一般性知識中的。因此，此，

7、只只要大前提和小前提是正確的，則由它們要大前提和小前提是正確的，則由它們推導(dǎo)出來的結(jié)論也必然是正確的。推導(dǎo)出來的結(jié)論也必然是正確的。 演繹推理是人工智能中的一種重要推理方式，在演繹推理是人工智能中的一種重要推理方式，在直到目前研制成功的各類智能系統(tǒng)中，大多是直到目前研制成功的各類智能系統(tǒng)中，大多是用演繹推理實現(xiàn)的。用演繹推理實現(xiàn)的。2021-10-318歸結(jié)推理歸結(jié)推理歸結(jié)推理是從足夠多的事例中歸結(jié)出歸結(jié)推理是從足夠多的事例中歸結(jié)出一般性結(jié)論的推理過程，是一種從個別到一般的推一般性結(jié)論的推理過程，是一種從個別到一般的推理。歸結(jié)推理又分為完全歸結(jié)和不完全歸結(jié)兩種。理。歸結(jié)推理又分為完全歸結(jié)和不完

8、全歸結(jié)兩種。完全歸結(jié)：指在進行歸結(jié)時考察了相應(yīng)事物的全完全歸結(jié)：指在進行歸結(jié)時考察了相應(yīng)事物的全部對象，并根據(jù)這些對象是否都有某種屬性，從部對象，并根據(jù)這些對象是否都有某種屬性，從而推出這種事物是否具有這個屬性。而推出這種事物是否具有這個屬性。 例如例如: 某廠進行產(chǎn)品質(zhì)量檢查，如果對每一件某廠進行產(chǎn)品質(zhì)量檢查，如果對每一件產(chǎn)品都進行了嚴(yán)格檢查，并且是合格的，則推產(chǎn)品都進行了嚴(yán)格檢查，并且是合格的，則推導(dǎo)出結(jié)論該廠的產(chǎn)品是合格的。導(dǎo)出結(jié)論該廠的產(chǎn)品是合格的。不完全歸結(jié)：指只考察了相應(yīng)事物的部分對象，不完全歸結(jié)：指只考察了相應(yīng)事物的部分對象，就得出了結(jié)論。就得出了結(jié)論。2021-10-319默認(rèn)

9、推理默認(rèn)推理又稱缺省推理，它是在知識不完全的又稱缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。情況下假設(shè)某些條件已經(jīng)具備所進行的推理。在默認(rèn)推理過程中，如果到某一時刻發(fā)現(xiàn)原先所在默認(rèn)推理過程中，如果到某一時刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則就要撤銷所作默認(rèn)，以及由作的默認(rèn)不正確，則就要撤銷所作默認(rèn)，以及由此默認(rèn)推出的所有結(jié)論重新按新情況進行推理。此默認(rèn)推出的所有結(jié)論重新按新情況進行推理。. 確定性推理，不確定性推理確定性推理，不確定性推理（按推理時所用知識（按推理時所用知識的確定性來劃分）的確定性來劃分） 確定性推理確定性推理 指推理時所用的知識都是精確的，指推理時所用的知識

10、都是精確的，推出的結(jié)論也是確定的，其真值或為推出的結(jié)論也是確定的，其真值或為“真真”，或為，或為“假假”，沒有第三種情況出現(xiàn)。，沒有第三種情況出現(xiàn)。下面將要討論的經(jīng)典邏輯推理就屬于這一類。下面將要討論的經(jīng)典邏輯推理就屬于這一類。2021-10-3110 不確定性推理不確定性推理指推理時所用的知識不都是精確的，指推理時所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于推出的結(jié)論也不完全是肯定的，其真值位于“真真”和和“假假”之間，命題的外延模糊不清。之間，命題的外延模糊不清。這里我們要特別強調(diào)不確定性推理。自亞里士多德這里我們要特別強調(diào)不確定性推理。自亞里士多德建立第一個演繹公理系統(tǒng)

11、以來，經(jīng)典邏輯與精確數(shù)建立第一個演繹公理系統(tǒng)以來，經(jīng)典邏輯與精確數(shù)學(xué)的建立與發(fā)展為人類科學(xué)技術(shù)的發(fā)展起了巨大的學(xué)的建立與發(fā)展為人類科學(xué)技術(shù)的發(fā)展起了巨大的作用。然而，現(xiàn)實世界中的事物和現(xiàn)象大都是不嚴(yán)作用。然而，現(xiàn)實世界中的事物和現(xiàn)象大都是不嚴(yán)格、不精確的，許多概念是模糊的，很難用精確的格、不精確的，許多概念是模糊的，很難用精確的數(shù)學(xué)模型來表示和處理。因此。近幾年來，各種非數(shù)學(xué)模型來表示和處理。因此。近幾年來，各種非經(jīng)典邏輯迅速崛起，人工智能亦把不精確知識的表經(jīng)典邏輯迅速崛起，人工智能亦把不精確知識的表示與處理作為重要的研究課題。另外，從人類思維示與處理作為重要的研究課題。另外，從人類思維活動的

12、特征來看，人們經(jīng)常是在知識不完全、不精活動的特征來看，人們經(jīng)常是在知識不完全、不精確的情況下進行多方位的思考及推理的。因此，要確的情況下進行多方位的思考及推理的。因此，要使計算機模擬人類的思維活動，就必須使其具有不使計算機模擬人類的思維活動，就必須使其具有不確定性推理的能力。確定性推理的能力。2021-10-3111. 單調(diào)推理、非單調(diào)推理單調(diào)推理、非單調(diào)推理（按推理過程中推出的結(jié)（按推理過程中推出的結(jié)論是否單調(diào)的增加來劃分）論是否單調(diào)的增加來劃分） 單調(diào)推理單調(diào)推理指在推理過程中隨著推理的向前推進指在推理過程中隨著推理的向前推進及新知識的加入，推出的結(jié)論呈單調(diào)增加的趨勢，及新知識的加入，推出

13、的結(jié)論呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，在推理過程中不會出現(xiàn)并且越來越接近最終目標(biāo)，在推理過程中不會出現(xiàn)反復(fù)的情況，即不會由于新知識的加入而否定前面反復(fù)的情況，即不會由于新知識的加入而否定前面推出的結(jié)論，使推理又退回到前面的一步。推出的結(jié)論，使推理又退回到前面的一步。非單調(diào)推理非單調(diào)推理指在推理過程中由于新知識的加入，指在推理過程中由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使得不僅沒有加強已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。推理退回到前面的某一步，重新開始。2021-10-3112. 啟發(fā)式推理、非啟發(fā)式推理啟發(fā)式推理、非啟發(fā)式推理（按推理

14、中是否運用（按推理中是否運用與問題有關(guān)的啟發(fā)性知識分）與問題有關(guān)的啟發(fā)性知識分） 啟發(fā)式推理啟發(fā)式推理推理中運用與問題有關(guān)的啟發(fā)性知推理中運用與問題有關(guān)的啟發(fā)性知識，即解決問題的策略、技巧、竅門，對解的特性識，即解決問題的策略、技巧、竅門，對解的特性及規(guī)律的估計等實踐經(jīng)驗和知識以加快推理過程、及規(guī)律的估計等實踐經(jīng)驗和知識以加快推理過程、提高搜索效率，這種推理稱為啟發(fā)式推理。提高搜索效率，這種推理稱為啟發(fā)式推理。非啟發(fā)式推理非啟發(fā)式推理比如窮舉式推理等。比如窮舉式推理等。2021-10-3113. 基于知識的推理、統(tǒng)計推理、直覺推理基于知識的推理、統(tǒng)計推理、直覺推理（從方（從方法論的角度劃分）法

15、論的角度劃分）基于知識的推理基于知識的推理根據(jù)已掌握的事實，通過運根據(jù)已掌握的事實，通過運用知識進行的推理。用知識進行的推理。統(tǒng)計推理統(tǒng)計推理根據(jù)對某事物的數(shù)據(jù)統(tǒng)計進行的推根據(jù)對某事物的數(shù)據(jù)統(tǒng)計進行的推理理(相當(dāng)于歸納推理相當(dāng)于歸納推理)。直覺推理直覺推理又稱常識性推理，是根據(jù)常識進行又稱常識性推理，是根據(jù)常識進行的推理。的推理。2021-10-3114推理過程是一個思維過程，即求解問題的過程，推理過程是一個思維過程，即求解問題的過程，求解問題的質(zhì)量和效率不僅依賴于所采用的求解求解問題的質(zhì)量和效率不僅依賴于所采用的求解方法，而且還依賴于求解問題的策略，即推理的方法，而且還依賴于求解問題的策略，

16、即推理的控制策略?？刂撇呗浴Ｍ评淼目刂撇呗灾饕ǎ和评矸较?、搜索策略、推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制策略等。沖突消解策略、求解策略及限制策略等。推理的控制策略2021-10-3115推理方向用于確定推理的驅(qū)動方式，分為正向推推理方向用于確定推理的驅(qū)動方式，分為正向推理、逆向推理、混合理、逆向推理、混合 推理和雙向推理四種。無論推理和雙向推理四種。無論按哪種方向進行推理，一般都要求系統(tǒng)具有一個按哪種方向進行推理，一般都要求系統(tǒng)具有一個存放知識的知識庫，一個存放初始已知事實及問存放知識的知識庫，一個存放初始已知事實及問題狀態(tài)的數(shù)據(jù)庫和一個用于推理的與推理

17、機。題狀態(tài)的數(shù)據(jù)庫和一個用于推理的與推理機。推理方向2021-10-3116正向推理正向推理是以已知事實作為出發(fā)點的一種推理，正向推理是以已知事實作為出發(fā)點的一種推理，又稱數(shù)據(jù)驅(qū)動推理、前向鏈推理及前件推理等。又稱數(shù)據(jù)驅(qū)動推理、前向鏈推理及前件推理等。. 正向推理的基本思想：正向推理的基本思想：從用戶提供的初始已知事實出發(fā)，在知識庫從用戶提供的初始已知事實出發(fā)，在知識庫KB中中找出當(dāng)前可適用的知識，構(gòu)成可適用知識集找出當(dāng)前可適用的知識，構(gòu)成可適用知識集KS，然后按某種沖突消解策略從然后按某種沖突消解策略從KS中選出一條知識進中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫中作為行推理，并將

18、推出的新事實加入到數(shù)據(jù)庫中作為下一步推理的已知事實，在此之后再在知識庫中下一步推理的已知事實，在此之后再在知識庫中選取可適用的知識進行推理，如此重復(fù)，直到求選取可適用的知識進行推理，如此重復(fù)，直到求得了所要求的解，或者知識庫中再無可適用的知得了所要求的解，或者知識庫中再無可適用的知識為止。識為止。 2021-10-3117正向推理過程正向推理過程算法描述：算法描述：開始開始把初始已知事實送入把初始已知事實送入DBDB中包含問題的解？中包含問題的解？KB中有可適用知識？中有可適用知識？KS空？空？把把KB中所有可適用知識都選出來送入中所有可適用知識都選出來送入KS推出的是新事實？推出的是新事實？

19、按沖突消解策略從按沖突消解策略從KS中選出一條知識進行推理中選出一條知識進行推理將該新事實加入到將該新事實加入到DB中中成功，退出成功，退出把用戶提供的新事實加入把用戶提供的新事實加入DB中中用戶用戶 可補充新事實？可補充新事實？失敗，退出失敗，退出YYYYYNNNNN2021-10-3118. 與正向推理相關(guān)的問題：與正向推理相關(guān)的問題：匹配方法匹配方法在以上推理過程中，需要從知識庫在以上推理過程中，需要從知識庫 KB 中選出可適用的知識，這就要用知識庫中的知識與數(shù)中選出可適用的知識，這就要用知識庫中的知識與數(shù)據(jù)庫中的已知事實進行匹配，為此需確定據(jù)庫中的已知事實進行匹配，為此需確定匹配方法匹

20、配方法。 搜索策略搜索策略為了進行匹配，就要查找知識，這就牽為了進行匹配，就要查找知識，這就牽涉到按什么路線進行查找的問題，既按什么涉到按什么路線進行查找的問題，既按什么搜索策略搜索策略搜索知識庫。搜索知識庫。沖突消解策略沖突消解策略如果適用的知識只有一條，這比較如果適用的知識只有一條，這比較簡單，系統(tǒng)立即就可用它進行推理，并將推出的新事簡單，系統(tǒng)立即就可用它進行推理，并將推出的新事實送入數(shù)據(jù)庫實送入數(shù)據(jù)庫DB中；但是，如果當(dāng)前適用的知識有多中；但是，如果當(dāng)前適用的知識有多條，應(yīng)該先用那一條條，應(yīng)該先用那一條? 這是推理中的一個重要問題，這是推理中的一個重要問題，稱為稱為沖突消解策略沖突消解策

21、略?？傊?，為了實現(xiàn)正向推理，有許多具體問題需要解決?？傊?，為了實現(xiàn)正向推理，有許多具體問題需要解決。2021-10-3119例例: 設(shè)在綜合數(shù)據(jù)庫中存放有下列已知事實：設(shè)在綜合數(shù)據(jù)庫中存放有下列已知事實：該動該動物身上有暗斑點，長脖子，長腿，有奶，有蹄物身上有暗斑點，長脖子，長腿，有奶，有蹄且假且假設(shè)綜合數(shù)據(jù)庫中的已知事實與規(guī)則庫中的知識是從設(shè)綜合數(shù)據(jù)庫中的已知事實與規(guī)則庫中的知識是從第一條開始，逐條第一條開始，逐條 進行匹配的，則推理機構(gòu)的工作進行匹配的，則推理機構(gòu)的工作過程如下：過程如下： 從規(guī)則庫中取出第一條規(guī)則從規(guī)則庫中取出第一條規(guī)則r1，檢查前提條件，檢查前提條件與綜合數(shù)據(jù)庫中的已知

22、事實不匹配；取第二條規(guī)與綜合數(shù)據(jù)庫中的已知事實不匹配；取第二條規(guī)則則r2，r2的前提的前提“該動物有奶該動物有奶”與綜合數(shù)據(jù)庫中與綜合數(shù)據(jù)庫中事實匹配，則事實匹配，則rr被執(zhí)行，其結(jié)論被加入綜合數(shù)據(jù)被執(zhí)行，其結(jié)論被加入綜合數(shù)據(jù)庫中，此時綜合數(shù)據(jù)庫中的事實為：庫中，此時綜合數(shù)據(jù)庫中的事實為：該動物身上該動物身上有暗斑點，長脖子，長腿，有奶，有蹄，是哺乳有暗斑點，長脖子，長腿，有奶，有蹄，是哺乳動物動物正向推理求解過程2021-10-3120 接著取接著取r3 r4 r5 r6 都不匹配，取到都不匹配，取到r7時，時，匹配成功，則將匹配成功，則將r7的結(jié)論加入綜合數(shù)據(jù)庫：的結(jié)論加入綜合數(shù)據(jù)庫：該該

23、動物身上有暗斑點動物身上有暗斑點,長脖子長脖子,長腿長腿,有奶有奶,有蹄有蹄,是哺是哺乳動物乳動物,是有蹄動物是有蹄動物 接著取規(guī)則，取到接著取規(guī)則，取到r11時，匹配成功，發(fā)現(xiàn)時，匹配成功，發(fā)現(xiàn)其前提條件與綜合數(shù)據(jù)庫完全匹配，則確定該其前提條件與綜合數(shù)據(jù)庫完全匹配，則確定該動物是：動物是：長頸鹿長頸鹿 至此，問題的求解結(jié)束了。至此，問題的求解結(jié)束了。2021-10-3121逆向推理是以某個假設(shè)目標(biāo)作為出發(fā)點的一種推理，逆向推理是以某個假設(shè)目標(biāo)作為出發(fā)點的一種推理，又稱為目標(biāo)驅(qū)動推理、逆向鏈推理及后件推理等。又稱為目標(biāo)驅(qū)動推理、逆向鏈推理及后件推理等。. 逆向推理的基本思想：逆向推理的基本思想

24、：首先選定一個假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證首先選定一個假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說明原假設(shè)成立；據(jù)，若所需的證據(jù)都能找到，則說明原假設(shè)成立；若無論如何都找不到所需證據(jù)，說明原假設(shè)不成立，若無論如何都找不到所需證據(jù)，說明原假設(shè)不成立，此時需要另作新的假設(shè)。此時需要另作新的假設(shè)。. 推理過程算法描述（圖示）推理過程算法描述（圖示）逆向推理2021-10-3122 逆向推理過逆向推理過程算法描述：程算法描述：開始開始 提出假設(shè)提出假設(shè)該假設(shè)在數(shù)據(jù)庫該假設(shè)在數(shù)據(jù)庫DB中？中？該假設(shè)是證據(jù)？該假設(shè)是證據(jù)？在知識庫中找出所有能在知識庫中找出所有能導(dǎo)出該假設(shè)的知識，形導(dǎo)

25、出該假設(shè)的知識，形成適用知識集成適用知識集KS從從KS中選出一條知識，并中選出一條知識，并將該知識的一個運用條件將該知識的一個運用條件作為一個新的假設(shè)目標(biāo)。作為一個新的假設(shè)目標(biāo)。該假設(shè)成立該假設(shè)成立詢問用戶詢問用戶有此事實？有此事實？該假設(shè)成立，該假設(shè)成立，并將此事實并將此事實存入數(shù)據(jù)庫存入數(shù)據(jù)庫還有假設(shè)？還有假設(shè)？退出退出YYYYNNNN2021-10-3123假設(shè)某用戶希望動物識別系統(tǒng)驗證一下某動物是否假設(shè)某用戶希望動物識別系統(tǒng)驗證一下某動物是否是虎，并設(shè)當(dāng)前數(shù)據(jù)庫為空。其逆向推理過程為：是虎，并設(shè)當(dāng)前數(shù)據(jù)庫為空。其逆向推理過程為： 以虎作為假設(shè)目標(biāo)以虎作為假設(shè)目標(biāo); 檢察數(shù)據(jù)庫中有無虎這

26、個事實。因為數(shù)據(jù)庫初檢察數(shù)據(jù)庫中有無虎這個事實。因為數(shù)據(jù)庫初始為空，顯然不會有虎這個事實始為空，顯然不會有虎這個事實; ; 判斷該目標(biāo)是否是證據(jù)；判斷該目標(biāo)是否是證據(jù)；判斷一個目標(biāo)是否是判斷一個目標(biāo)是否是證據(jù)，只要檢查它是否為某條知識的結(jié)論就可得證據(jù)，只要檢查它是否為某條知識的結(jié)論就可得知。如果它不包含在任何一條知識的結(jié)論部分中，知。如果它不包含在任何一條知識的結(jié)論部分中，那么它就是證據(jù)。那么它就是證據(jù)。這里虎顯然不是證據(jù)，因為它這里虎顯然不是證據(jù)，因為它是規(guī)則是規(guī)則r r1010的結(jié)論；的結(jié)論；逆向推理求解過程2021-10-3124 在知識庫中找出所有能導(dǎo)出該目標(biāo)的知識。該在知識庫中找出所

27、有能導(dǎo)出該目標(biāo)的知識。該問題比較簡單，只有一條知識可導(dǎo)出結(jié)論虎，問題比較簡單，只有一條知識可導(dǎo)出結(jié)論虎，即即r r1010；r10: If r10: If 該動物是哺乳動物該動物是哺乳動物 and and 是食肉是食肉動物動物 and and 是黃褐色是黃褐色 and and 身上有黑色條紋身上有黑色條紋 thethen n 該動物是虎該動物是虎 將將r r1010的運用條件分別作為新的假設(shè)進行驗證。的運用條件分別作為新的假設(shè)進行驗證。 該知識有一個運用條件是該知識有一個運用條件是“是黃褐色是黃褐色”，當(dāng)把，當(dāng)把它它 作為新假設(shè)進行推理時，作為新假設(shè)進行推理時， 首先要檢查數(shù)據(jù)庫中有無該事實，

28、這里顯然沒首先要檢查數(shù)據(jù)庫中有無該事實，這里顯然沒有；有；2021-10-3125 接著判斷它是否是證據(jù)，因在接著判斷它是否是證據(jù)，因在r r1 1-r-r1515中沒有一中沒有一條條 知識的結(jié)論部分包含它，所以知識的結(jié)論部分包含它，所以 它是證據(jù)。它是證據(jù)。 此時詢問用戶：你看到的動物是黃褐色嗎？若此時詢問用戶：你看到的動物是黃褐色嗎？若用戶答是，則該運用條件就得到了驗證，并將它用戶答是，則該運用條件就得到了驗證，并將它存入數(shù)據(jù)庫中；若用戶回答不是，則就否定了原存入數(shù)據(jù)庫中；若用戶回答不是，則就否定了原先關(guān)于虎的假設(shè)，需要作另外的假設(shè)，從頭開始先關(guān)于虎的假設(shè)，需要作另外的假設(shè)，從頭開始進行逆

29、向推理。這里，我們假設(shè)用戶的回答為是，進行逆向推理。這里，我們假設(shè)用戶的回答為是，以便將推理進行下去。以便將推理進行下去。 對于知識的運用條件對于知識的運用條件“身上有黑條紋身上有黑條紋”與上面處與上面處理類似理類似, 因為它也是一個證據(jù)，我們同樣假定用戶因為它也是一個證據(jù)，我們同樣假定用戶的回答為是，這樣數(shù)據(jù)庫中就又增加了一個事實。的回答為是，這樣數(shù)據(jù)庫中就又增加了一個事實。2021-10-3126 現(xiàn)在數(shù)據(jù)庫中有兩個事實：是黃褐色、身上有黑現(xiàn)在數(shù)據(jù)庫中有兩個事實：是黃褐色、身上有黑條紋。條紋。 對于知識的運用條件對于知識的運用條件“是哺乳動物是哺乳動物”，因它沒有，因它沒有在數(shù)據(jù)庫中出現(xiàn)，

30、同時又不是證據(jù)（它是在數(shù)據(jù)庫中出現(xiàn)，同時又不是證據(jù)（它是r1與與r2的的結(jié)論），所以要在知識庫中找出能導(dǎo)出它的所有結(jié)論），所以要在知識庫中找出能導(dǎo)出它的所有知識，即知識，即 r1與與r2： r1: If r1: If 該動物有毛發(fā)該動物有毛發(fā) then then 該動物是哺該動物是哺乳動物乳動物 r2: If r2: If 該動物有奶該動物有奶 then then 該動物是哺該動物是哺乳動物乳動物2021-10-3127此時，因同時有兩條知識可供使用，因而存在先使此時，因同時有兩條知識可供使用，因而存在先使用哪一個的問題。這有多種處理方法，將在以后用哪一個的問題。這有多種處理方法，將在以后討論

31、，這里我們采用最簡單的一種，即哪一個排討論，這里我們采用最簡單的一種，即哪一個排在前面就先使用哪一個，所以用在前面就先使用哪一個，所以用r1。 由于由于r1的運用條件是有毛發(fā)，因此又要把有的運用條件是有毛發(fā)，因此又要把有毛發(fā)作為新假設(shè)進行驗證，顯然它是一個證據(jù)。毛發(fā)作為新假設(shè)進行驗證，顯然它是一個證據(jù)。經(jīng)詢問用戶，假定回答為是，這樣，是哺乳動物經(jīng)詢問用戶，假定回答為是，這樣，是哺乳動物就被肯定。就被肯定。 對于運用條件對于運用條件“是食肉動物是食肉動物”可作類似處理，可作類似處理，只是為證實它，要用到只是為證實它，要用到r5或或r6。 2021-10-3128r5: If r5: If 該動物

32、吃肉該動物吃肉 then then 該動物是食肉動物該動物是食肉動物r6: If r6: If 該動物有犬齒該動物有犬齒 and and 有爪有爪 and and 眼盯前方眼盯前方 then then 該動物是食肉動物該動物是食肉動物 使用使用r5時，若用戶對詢問時，若用戶對詢問“該動物吃肉嗎該動物吃肉嗎”給出肯定的回答。給出肯定的回答。 至此至此r r1010的四個運用條件都被證實，從而肯定的四個運用條件都被證實，從而肯定原假設(shè)原假設(shè)“該動物是虎該動物是虎”的正確性。的正確性。2021-10-3129. 逆向推理的主要優(yōu)點：逆向推理的主要優(yōu)點：不必使用與目標(biāo)無關(guān)的知不必使用與目標(biāo)無關(guān)的知識，

33、識，目的性強目的性強，同時還有利于向用戶提供解釋。，同時還有利于向用戶提供解釋。 逆向推理的逆向推理的主要缺點：主要缺點：初始目標(biāo)的選擇有初始目標(biāo)的選擇有盲目性盲目性，若不符合實際，就要多次提出假設(shè)，影響到系統(tǒng)若不符合實際，就要多次提出假設(shè)，影響到系統(tǒng)效率。效率。2021-10-3130. 正、逆向推理存在的缺陷正、逆向推理存在的缺陷 正向推理正向推理具有盲目、效率低等缺點；具有盲目、效率低等缺點； 逆向推理逆向推理若提出的假設(shè)目標(biāo)不符合事實，若提出的假設(shè)目標(biāo)不符合事實，也會降低系統(tǒng)效率。也會降低系統(tǒng)效率。 為解決這些問題，可把正向推理與逆向推理結(jié)為解決這些問題，可把正向推理與逆向推理結(jié)合起來

34、，取長補短；合起來，取長補短； 象這樣既有正向又有逆向的推理稱為象這樣既有正向又有逆向的推理稱為混合推理。混合推理。 混合推理2021-10-3131. 混合推理的兩種情況混合推理的兩種情況 先正向再逆向先正向再逆向 ： 先進行正向推理，先進行正向推理，幫助選擇某個目標(biāo)，即從幫助選擇某個目標(biāo)，即從已知事實演繹出部分結(jié)果，已知事實演繹出部分結(jié)果，然后再用逆向推理證實該然后再用逆向推理證實該目標(biāo)或提高其可信度。目標(biāo)或提高其可信度。開始開始 進行正向推理進行正向推理 需要逆向推理？需要逆向推理？還需要正向推理？還需要正向推理？以正向推理所得結(jié)果以正向推理所得結(jié)果作為假設(shè)進行逆向推理作為假設(shè)進行逆向推

35、理輸出結(jié)果輸出結(jié)果退出退出YYNN2021-10-3132 先逆向再正向：先逆向再正向：先先假設(shè)一個目標(biāo)進行逆假設(shè)一個目標(biāo)進行逆向推理，然后再利用向推理，然后再利用逆向推理中得到的信逆向推理中得到的信息進行正向推理，以息進行正向推理，以推出更多的結(jié)論。推出更多的結(jié)論。開始開始 進行逆向推理進行逆向推理需要正向推理？需要正向推理？還需要逆向推理？還需要逆向推理？進行正向推理進行正向推理輸出結(jié)果輸出結(jié)果退出退出YYNN2021-10-3133 雙向推理是雙向推理是指正向推理與逆向推理同時進行指正向推理與逆向推理同時進行，且在推理過程中的某一步驟上且在推理過程中的某一步驟上“碰頭碰頭”的一種推的一種

36、推理方式。理方式?；舅枷耄夯舅枷耄?一方面根據(jù)已知事實進行正向推理，但并不推一方面根據(jù)已知事實進行正向推理，但并不推到最終目標(biāo)；另一方面從某假設(shè)目標(biāo)出發(fā)進行逆到最終目標(biāo)；另一方面從某假設(shè)目標(biāo)出發(fā)進行逆向推理，但并不推至原始事實，而是讓它們在中向推理，但并不推至原始事實，而是讓它們在中途相遇，即由正向推理所得的中間結(jié)論恰好是逆途相遇，即由正向推理所得的中間結(jié)論恰好是逆向推理此時所需要的證據(jù)，這時推理就可結(jié)束，向推理此時所需要的證據(jù)，這時推理就可結(jié)束，逆向推理時所做的假設(shè)就是推理的最終結(jié)論。逆向推理時所做的假設(shè)就是推理的最終結(jié)論。雙向推理2021-10-3134 求解策略求解策略 所謂推理的求

37、解策略是指，推理是只求一個解，所謂推理的求解策略是指，推理是只求一個解，還是求所有解以及最優(yōu)解等。還是求所有解以及最優(yōu)解等。 限制策略限制策略 為了防止無窮的推理過程，以及由于推理過程為了防止無窮的推理過程，以及由于推理過程太長增加時間及空間的復(fù)雜性，可在控制策略中指太長增加時間及空間的復(fù)雜性，可在控制策略中指定推理的限制條件，以對推理的深度，寬度，時間，定推理的限制條件，以對推理的深度，寬度，時間，空間等進行限制?？臻g等進行限制。 求解策略和限制策略2021-10-3135 A 概念概念 在推理過程中，系統(tǒng)要不斷地用當(dāng)前已知的事實與知在推理過程中，系統(tǒng)要不斷地用當(dāng)前已知的事實與知識庫中的知識

38、進識庫中的知識進 行匹配，此時可能發(fā)生如下三種情況：行匹配，此時可能發(fā)生如下三種情況： . 已知事實不能與知識庫中的任何知識匹配成功；已知事實不能與知識庫中的任何知識匹配成功； . 已知事實恰好只與知識庫中的一個知識匹配成功；已知事實恰好只與知識庫中的一個知識匹配成功； . 已知事實可以與知識庫中的多個知識匹配成功；已知事實可以與知識庫中的多個知識匹配成功；或者有多個（組）已知事實都可與知識庫中的一個知識或者有多個（組）已知事實都可與知識庫中的一個知識匹配成功；或者有多個（組）已知事實可與知識庫中的匹配成功；或者有多個（組）已知事實可與知識庫中的多個知識匹配成功。多個知識匹配成功。 第三種情況

39、為發(fā)生了沖突，此時需要按一定的策第三種情況為發(fā)生了沖突，此時需要按一定的策略解決沖突，以便從中挑選一個知識用于當(dāng)前的推理，略解決沖突，以便從中挑選一個知識用于當(dāng)前的推理，稱這一解決沖突的過稱為稱這一解決沖突的過稱為沖突消解沖突消解。解決沖突時所用的。解決沖突時所用的方法稱為方法稱為沖突消解策略沖突消解策略。沖突消解策略2021-10-3136 B 以產(chǎn)生式系統(tǒng)為例進行較詳細說明以產(chǎn)生式系統(tǒng)為例進行較詳細說明. 產(chǎn)生式系統(tǒng)沖突產(chǎn)生式系統(tǒng)沖突 在產(chǎn)生式系統(tǒng)中，若出現(xiàn)下列情況就認(rèn)為發(fā)生了在產(chǎn)生式系統(tǒng)中，若出現(xiàn)下列情況就認(rèn)為發(fā)生了沖突：沖突： 對正向推理而言，如果有多條產(chǎn)生式規(guī)則的前對正向推理而言，如

40、果有多條產(chǎn)生式規(guī)則的前件都和已知事實匹配成功；或者有多組不同的已知件都和已知事實匹配成功；或者有多組不同的已知事實都與同一條產(chǎn)生式規(guī)則的前件匹配成功；或者事實都與同一條產(chǎn)生式規(guī)則的前件匹配成功；或者以上兩種情況同時出現(xiàn)。以上兩種情況同時出現(xiàn)。 對逆向推理而言，如果有多條產(chǎn)生式規(guī)則的后對逆向推理而言，如果有多條產(chǎn)生式規(guī)則的后件都和同一個假設(shè)匹配成功；或者有多條產(chǎn)生式規(guī)件都和同一個假設(shè)匹配成功；或者有多條產(chǎn)生式規(guī)則的后件可與多個假設(shè)匹配成功。則的后件可與多個假設(shè)匹配成功。 2021-10-3137. 沖突消解沖突消解 沖突消解的任務(wù)是解決沖突。沖突消解的任務(wù)是解決沖突。 對正向推理來說，它將決定選

41、擇哪一組已知對正向推理來說，它將決定選擇哪一組已知事實來激活哪一條產(chǎn)生式規(guī)則，使它用于當(dāng)前的事實來激活哪一條產(chǎn)生式規(guī)則，使它用于當(dāng)前的推理，產(chǎn)生其后件指出的結(jié)論或執(zhí)行相應(yīng)的操作。推理，產(chǎn)生其后件指出的結(jié)論或執(zhí)行相應(yīng)的操作。 對逆向推理來說，它將決定用哪一個假設(shè)與對逆向推理來說，它將決定用哪一個假設(shè)與哪一個產(chǎn)生式規(guī)則的后件進行匹配，從而推出相哪一個產(chǎn)生式規(guī)則的后件進行匹配，從而推出相應(yīng)的前件，作為新的假設(shè)。應(yīng)的前件，作為新的假設(shè)。2021-10-3138. 沖突消解策略沖突消解策略 目前已有多種消解沖突的策略，其基本思想都是目前已有多種消解沖突的策略，其基本思想都是對對知識進行排序知識進行排序。

42、常用的有以下幾種：。常用的有以下幾種： 按針對性排序按針對性排序本策略是優(yōu)先選用針對性較本策略是優(yōu)先選用針對性較強的產(chǎn)生式規(guī)則。強的產(chǎn)生式規(guī)則。 設(shè)有如下兩條產(chǎn)生式規(guī)則：設(shè)有如下兩條產(chǎn)生式規(guī)則： r r1: 1: IF AIF A1 1 AND A AND A2 2 AND AND A AND AND An n THEN H THEN H1 1 r r2 2：IF BIF B1 1 AND B AND B2 2 AND AND B AND AND Bm m THEN HTHEN H2 2 如果存在最一般合一，使得如果存在最一般合一，使得r r1 1中每一個中每一個Ai都可變成都可變成相應(yīng)的相應(yīng)

43、的B Bi i, ,即即r r2 2中包含中包含r r1 1的全部條件的全部條件A A1 1,A,A2 2,An,An外，還外，還包含其他條件，則稱包含其他條件，則稱r r2 2比比r r1 1有更大的針對性，有更大的針對性，r r1 1比比r r2 2有更大的通用性。有更大的通用性。2021-10-3139 按已知事實的新鮮性排序按已知事實的新鮮性排序把數(shù)據(jù)庫中后生成把數(shù)據(jù)庫中后生成的事實稱為新鮮的事實的事實稱為新鮮的事實 。 在產(chǎn)生式的推理過程中，每應(yīng)用一條產(chǎn)生式規(guī)則在產(chǎn)生式的推理過程中，每應(yīng)用一條產(chǎn)生式規(guī)則就會得到一個或多個結(jié)論或者執(zhí)行某個操作，數(shù)據(jù)庫就會得到一個或多個結(jié)論或者執(zhí)行某個操

44、作，數(shù)據(jù)庫就會增加新的事實。另外，在推理時還會向用戶詢問就會增加新的事實。另外，在推理時還會向用戶詢問有關(guān)的信息，也使數(shù)據(jù)庫的內(nèi)容發(fā)生變化。我們把數(shù)有關(guān)的信息，也使數(shù)據(jù)庫的內(nèi)容發(fā)生變化。我們把數(shù)據(jù)庫中后生成的事實稱為新鮮的事實，據(jù)庫中后生成的事實稱為新鮮的事實，即后生成的事即后生成的事實比先生成的事實具有較大的新鮮性。實比先生成的事實具有較大的新鮮性。 若一條規(guī)則被應(yīng)用后生成了多個結(jié)論，則即可以若一條規(guī)則被應(yīng)用后生成了多個結(jié)論，則即可以認(rèn)為這些結(jié)論有相同的新鮮性，也可認(rèn)為排在前面的認(rèn)為這些結(jié)論有相同的新鮮性，也可認(rèn)為排在前面的結(jié)論有較大的新鮮性，根據(jù)情況而定。結(jié)論有較大的新鮮性，根據(jù)情況而定。

45、2021-10-3140 按匹配度排序按匹配度排序 匹配度大的知識優(yōu)先選用。匹配度大的知識優(yōu)先選用。 在不確定性匹配中，為了確定兩個知識模式在不確定性匹配中，為了確定兩個知識模式是否匹配，需要計算這兩個模式是否匹配，需要計算這兩個模式 的相似程度，當(dāng)?shù)南嗨瞥潭龋?dāng)其達到某個預(yù)先規(guī)定的值時，則認(rèn)為它們是可匹其達到某個預(yù)先規(guī)定的值時，則認(rèn)為它們是可匹配的。相似度又稱為匹配度。配的。相似度又稱為匹配度。 若產(chǎn)生式規(guī)則若產(chǎn)生式規(guī)則r1、r2都可匹配成功，則可根據(jù)都可匹配成功，則可根據(jù)它們的匹配度決定哪個規(guī)則被優(yōu)先選用。它們的匹配度決定哪個規(guī)則被優(yōu)先選用。2021-10-3141 根據(jù)領(lǐng)域問題的特點排序

46、根據(jù)領(lǐng)域問題的特點排序 某些領(lǐng)域問題，預(yù)先可知道它的某些特點，此時某些領(lǐng)域問題，預(yù)先可知道它的某些特點，此時可根據(jù)這些特點把知識排成固定的順序?？筛鶕?jù)這些特點把知識排成固定的順序。 例如：例如： (1) 當(dāng)領(lǐng)域問題有固定的解題次序時，可按該當(dāng)領(lǐng)域問題有固定的解題次序時，可按該次序排列相應(yīng)的知識，排在前面的知識優(yōu)先被應(yīng)次序排列相應(yīng)的知識，排在前面的知識優(yōu)先被應(yīng)用用; (2) 當(dāng)已知某些產(chǎn)生式規(guī)則被應(yīng)用后會明顯的有當(dāng)已知某些產(chǎn)生式規(guī)則被應(yīng)用后會明顯的有利于問題的求解時，就使這些產(chǎn)生式規(guī)則優(yōu)先被利于問題的求解時，就使這些產(chǎn)生式規(guī)則優(yōu)先被應(yīng)用。應(yīng)用。2021-10-3142 按上下文限制排序按上下文限

47、制排序 把產(chǎn)生式規(guī)則按它們所描述的上下文分成若干組，把產(chǎn)生式規(guī)則按它們所描述的上下文分成若干組，在不同的條件下，只能從相應(yīng)的組中選取有關(guān)的產(chǎn)在不同的條件下，只能從相應(yīng)的組中選取有關(guān)的產(chǎn)生式規(guī)則。這樣，不僅可以減少沖突的發(fā)生，而且生式規(guī)則。這樣，不僅可以減少沖突的發(fā)生，而且由于搜索范圍小，也提高了推理效率。由于搜索范圍小，也提高了推理效率。 按冗余限制排序按冗余限制排序 如果一條產(chǎn)生式規(guī)則被應(yīng)用后將產(chǎn)生冗余知識，如果一條產(chǎn)生式規(guī)則被應(yīng)用后將產(chǎn)生冗余知識，則降低了它被應(yīng)用的優(yōu)先級。產(chǎn)生的冗余知識越多，則降低了它被應(yīng)用的優(yōu)先級。產(chǎn)生的冗余知識越多，優(yōu)先級越低。優(yōu)先級越低。 按條件個數(shù)排序按條件個數(shù)排

48、序 如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用，因為要求條件少條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用，因為要求條件少的規(guī)則匹配時花費的時間較少。的規(guī)則匹配時花費的時間較少。2021-10-3143(1) 基本概念基本概念 所謂模式匹配是指對兩個知識模式（如兩個所謂模式匹配是指對兩個知識模式（如兩個謂詞公式、兩個框架片斷或兩個語義網(wǎng)絡(luò)片斷等）謂詞公式、兩個框架片斷或兩個語義網(wǎng)絡(luò)片斷等）的比較與耦合，即的比較與耦合，即 檢查這兩個知識模式是否完全檢查這兩個知識模式是否完全一致或近似一致。如果兩者完全一致，或雖不完一致或近似一致。如果兩者完

49、全一致，或雖不完全一致但其相似程度落在指定的限度內(nèi)，就稱它全一致但其相似程度落在指定的限度內(nèi)，就稱它們是可匹配的，否則為不可匹配。們是可匹配的，否則為不可匹配。 模式匹配是推理中必須進行的一項重要工作，模式匹配是推理中必須進行的一項重要工作，因為只有經(jīng)過模式匹配才能從知識庫中選出當(dāng)前因為只有經(jīng)過模式匹配才能從知識庫中選出當(dāng)前適用的知識，才能進行推理。適用的知識，才能進行推理。 模式匹配2021-10-3144(2) 分類分類 若按匹配時兩個知識模式的相似程度分，可分若按匹配時兩個知識模式的相似程度分，可分 為確定性匹配和不確定性匹配兩種。為確定性匹配和不確定性匹配兩種。 確定性匹配確定性匹配指

50、兩個知識模式完全一致，或指兩個知識模式完全一致，或經(jīng)經(jīng) 過變量代換后變的完全一致。過變量代換后變的完全一致。 例如，設(shè)有兩個知識模式：例如，設(shè)有兩個知識模式： P1：father(李四，李小四）李四，李小四）and man(李小四李小四) P2：father(x, y) and man(y) 若用若用“李四李四”代換變量代換變量 x，用，用“李小四李小四”代換代換 y，則則P1，P2就變得完全一致，若用這兩個知識模式進就變得完全一致，若用這兩個知識模式進行匹配，則稱它們是確定性匹配。行匹配，則稱它們是確定性匹配。 確定性匹配又稱完全匹配或精確匹配。確定性匹配又稱完全匹配或精確匹配。2021-1

51、0-3145 不確定性匹配不確定性匹配指兩個知識模式不完全一致，指兩個知識模式不完全一致，但從總體上看，其相似程度又落在指定的限度內(nèi)。但從總體上看，其相似程度又落在指定的限度內(nèi)。2021-10-3146(3) 變量代換變量代換 無論是確定性匹配或不確定性匹配，在進行匹無論是確定性匹配或不確定性匹配，在進行匹配時一般都需要進行變量的代換。配時一般都需要進行變量的代換。 定義定義11 代換是形如代換是形如tt1 1/x/x1 1,t,t2 2/x/x2 2,t,tn n/x/xn n 的的有限集合。其中，有限集合。其中，t t1 1,t,t2 2,t,tn n是項；是項；x x1 1,x,x2 2

52、,x,xn n是是互不相同的變元；互不相同的變元； t ti i/x/xi i表示用表示用t ti i代代x xi i換，不允許換，不允許t ti i與與x xi i相同，也不允許變元相同，也不允許變元x xi i循環(huán)地出現(xiàn)在另一個循環(huán)地出現(xiàn)在另一個t tj j中。中。 例如：例如： a/x,f(b)/y,w/z a/x,f(b)/y,w/z 是一個代換，是一個代換， g(y)/x,f(x)/y g(y)/x,f(x)/y 不是一個代換。不是一個代換。2021-10-3147 因為代換的目的是使某些變元被另外的變元、因為代換的目的是使某些變元被另外的變元、常量或函數(shù)取代，使之不再在公式中出現(xiàn)，

53、而常量或函數(shù)取代，使之不再在公式中出現(xiàn)，而gg(y)/x,f(x)/y(y)/x,f(x)/y在在x x與與y y之間出現(xiàn)了循環(huán)代換的情況，之間出現(xiàn)了循環(huán)代換的情況，它既沒有消去它既沒有消去x,x,也沒有消去也沒有消去y.y. 如果將它改為如果將它改為g(a)/x,f(x)/yg(a)/x,f(x)/y則是一個代換則是一個代換 它將把公式中的它將把公式中的x x用用g(a)g(a)代換，代換，y y用用f(g(a)f(g(a)代代換，從而消去了變元換，從而消去了變元x x和和y y。2021-10-3148 定義定義22 設(shè)設(shè) =t=t1 1/x/x1 1,t,t2 2/x/x2 2,t,tn

54、 n/x/xn n =u =u1 1/y/y1 1,u,u2 2/y/y2 2,u,um m/y/ym m 是兩個代換，則此兩個代換的復(fù)合也是一個代換，是兩個代換，則此兩個代換的復(fù)合也是一個代換，是從是從tt1 1 /x/x1 1,t,t2 2 /x/x2 2,t,tn n /x/xn n,u,u1 1/y/y1 1,u,u2 2/y/y2 2,u,um m/y/ym m 中刪去如下兩種元素：中刪去如下兩種元素： t ti i /x/xi i 當(dāng)當(dāng) t ti i =x=xi i u ui i/y/yi i 當(dāng)當(dāng) y yi i xx1 1,x,x2 2,x,xn n 后剩下的元素所構(gòu)成的集合，記

55、為后剩下的元素所構(gòu)成的集合，記為 o o 。 例如，設(shè)有代換：例如，設(shè)有代換： =f(y)/x,z/y=f(y)/x,z/y =a/x,b/y,y/z=a/x,b/y,y/z 則則 o o =f(b)/x=f(b)/x，y/zy/z2021-10-3149 定義定義33 設(shè)有公式集設(shè)有公式集F=FF=F1,1,F F2,2,FFn n,若存在一個代若存在一個代換換 使得使得F F1 1 = F= F2 2 = F= Fn n 則稱則稱 為公式集為公式集F F的一的一個合一，且稱個合一，且稱F F1,1,F F2,2,FFn n是可合一的。是可合一的。 例如：例如： 假設(shè)有公式集假設(shè)有公式集 F

56、=P(x,y,f(y),P(a,g(x),z)F=P(x,y,f(y),P(a,g(x),z) 則下式是它的一個合一：則下式是它的一個合一： = a/x,g(a)/y,f(g(a)/z = a/x,g(a)/y,f(g(a)/z 一個公式集的合一一般來說是不唯一的。一個公式集的合一一般來說是不唯一的。2021-10-3150 定義定義44 設(shè)設(shè) 是公式集是公式集F F的一個合一，如果對任一個合的一個合一，如果對任一個合一一 都存在一個代換都存在一個代換 ，使得，使得 = = o o ，則稱則稱 是一是一個最一般的合一。個最一般的合一。 最一般的合一是唯一的。最一般的合一是唯一的。 若用最一般合

57、一去代換那些可合一的謂詞公式若用最一般合一去代換那些可合一的謂詞公式, ,可使它們變成完全一致的謂詞公式。可使它們變成完全一致的謂詞公式。 由此可知，為了使兩個知識模式匹配，可用其最由此可知，為了使兩個知識模式匹配，可用其最一般的合一對他們進行代換。一般的合一對他們進行代換。 2021-10-3151差異集的概念：差異集的概念： 設(shè)有如下兩個謂詞公式：設(shè)有如下兩個謂詞公式： F F1 1: P(x: P(x，y y，z)z) F F2 2: P(x: P(x，f(a)f(a)，h(b)h(b) 分別從分別從F F1 1與與F F2 2的第一個符號開始，逐個向右比的第一個符號開始，逐個向右比較，

58、此時發(fā)現(xiàn)較，此時發(fā)現(xiàn)F F1 1中的中的y y與與F F2 2中的中的f(a)f(a)不同，它們構(gòu)不同，它們構(gòu)成了一個差異集：成了一個差異集： D D1 1=y=y，f(a)f(a) 當(dāng)繼續(xù)向右比較時，又發(fā)現(xiàn)當(dāng)繼續(xù)向右比較時，又發(fā)現(xiàn)F F1 1中的中的z z與與F F2 2中的中的h h(b)(b)不同，則又得到一個差異集：不同，則又得到一個差異集： D D2 2=z=z，h(b)h(b)2021-10-3152下面給出求取最一般合一算法的具體步驟：下面給出求取最一般合一算法的具體步驟： (1) (1) 令令k=0,Fk=0,Fk k=F,=F, k k= = 。這里，。這里，F(xiàn) F是欲求其最

59、一般是欲求其最一般合一的公式集，合一的公式集， 是空代換，它代表不作代換。是空代換，它代表不作代換。 (2) (2) 若若F Fk k只含一個表達式，則算法停止，只含一個表達式，則算法停止， k k就是就是最一般合一。最一般合一。 (3) (3) 找出找出F Fk k的差異集的差異集D Dk k。 (4) (4) 若若D Dk k中存在元素中存在元素x xk k和和t tk k，其中，其中x xk k是變元，是變元，t tk k是項，且是項，且x xk k不在不在t tk k中出現(xiàn)，則置：中出現(xiàn)，則置： k+1k+1= = k k o to tk k/x/xk k ，求取最一般合一的算法202

60、1-10-3153 F Fk+1k+1=F=Fk kttk k/x/xk k k=k+1 k=k+1 然后轉(zhuǎn)（然后轉(zhuǎn)（2 2）。）。 (5) (5) 算法中止，算法中止，F(xiàn) F的最一般合一不存在的最一般合一不存在2021-10-3154例如：例如： 設(shè)設(shè)F=P(a,x,f(g(y),P(z,f(z),f(u)F=P(a,x,f(g(y),P(z,f(z),f(u)求求其最一般合一。其最一般合一。 (1) 令令 0 0= = ，F(xiàn) F0 0=F,=F,因因F F0 0中含有兩個表達式，所以中含有兩個表達式，所以 0 0不是最一般合一；不是最一般合一； (2) 差異集差異集D D0 0=a,z=a