礦大人工智能確定性推理_第1頁
礦大人工智能確定性推理_第2頁
礦大人工智能確定性推理_第3頁
礦大人工智能確定性推理_第4頁
礦大人工智能確定性推理_第5頁
已閱讀5頁,還剩116頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、1第第4章章 確定性推理確定性推理 智能系統(tǒng)的推理過程實(shí)際上就是一種思維過程。按照智能系統(tǒng)的推理過程實(shí)際上就是一種思維過程。按照推理過程所用知識(shí)的確定性,推理可分為確定性推理和不推理過程所用知識(shí)的確定性,推理可分為確定性推理和不確定性推理。對(duì)于推理的這兩種不同類型,本章重點(diǎn)討論確定性推理。對(duì)于推理的這兩種不同類型,本章重點(diǎn)討論前一種,不確定性推理放到下一章討論。前一種,不確定性推理放到下一章討論。 4.1 推理的基本概念推理的基本概念 4.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 4.3 自然演繹推理自然演繹推理 4.4 歸結(jié)演繹推理歸結(jié)演繹推理 4.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理24.1

2、推理的基本概念推理的基本概念 4.1.1 什么是推理什么是推理 4.1.2 推理方法及其分類推理方法及其分類 4.1.3 推理的控制策略及其分類推理的控制策略及其分類 4.1.4 正向推理正向推理 4.1.5 逆向推理逆向推理 4.1.6 混合推理混合推理34.1.1 什么是推理什么是推理 推理的概念推理的概念 是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過程。是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過程。 推理所用的事實(shí):推理所用的事實(shí): 初始證據(jù):初始證據(jù):推理前用戶提供的推理前用戶提供的 中間結(jié)論:中間結(jié)論:推理過程中所得到的推理過程中所得到的 推理過程:推理過程:由推理機(jī)來完成,所謂推

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

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

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

6、般性知識(shí))(一般性知識(shí)) 程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生;程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生; (具體情況)(具體情況) 程強(qiáng)會(huì)編程序。程強(qiáng)會(huì)編程序。 (結(jié)論)(結(jié)論) 這是一個(gè)三段論推理。其中,是大前提,是小前提;是經(jīng)演繹推這是一個(gè)三段論推理。其中,是大前提,是小前提;是經(jīng)演繹推出來的結(jié)論。出來的結(jié)論。 可見,其結(jié)論是蘊(yùn)含在大前提中的??梢姡浣Y(jié)論是蘊(yùn)含在大前提中的。54.1.2 推理方法及其分類推理方法及其分類1. 按推理的邏輯基礎(chǔ)分類按推理的邏輯基礎(chǔ)分類(2/4)歸納推理歸納推理是一種由個(gè)別到一般的推理方法。歸納推理的類型是一種由個(gè)別到一般的推理方法。歸納推理的類型 按照所選事例的廣泛性按照所選事例的廣

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

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

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

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

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

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

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

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

15、1.4 正向推理正向推理推理算法推理算法 從已知事實(shí)出發(fā)、正向使用推理規(guī)則,亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈從已知事實(shí)出發(fā)、正向使用推理規(guī)則,亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈推理。推理。 算法描述算法描述 (1) 把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫;把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫; (2) 檢查綜合數(shù)據(jù)庫中是否包含了問題的解,若已包含,則求解結(jié)束,檢查綜合數(shù)據(jù)庫中是否包含了問題的解,若已包含,則求解結(jié)束,并成功推出;否則執(zhí)行下一步;并成功推出;否則執(zhí)行下一步; (3) 檢查知識(shí)庫中是否有可用知識(shí),若有,形成當(dāng)前可用知識(shí)集,執(zhí)行檢查知識(shí)庫中是否有可用知識(shí),若有,形成當(dāng)前可用知識(shí)集,執(zhí)行下一步;否則轉(zhuǎn)下一

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

17、知識(shí)庫中有多條知識(shí)可用時(shí)應(yīng)該先使用那一條知識(shí)等。這些問題涉及到了知識(shí)的中有多條知識(shí)可用時(shí)應(yīng)該先使用那一條知識(shí)等。這些問題涉及到了知識(shí)的匹配方法和沖突消解策略,以后將會(huì)分別討論。匹配方法和沖突消解策略,以后將會(huì)分別討論。 其流程圖如下:其流程圖如下:10把初始證據(jù)放入把初始證據(jù)放入DBDB中有解嗎?中有解嗎?KB中有可用知識(shí)嗎?中有可用知識(shí)嗎? 形成可用知識(shí)集形成可用知識(shí)集可用知識(shí)集空嗎?可用知識(shí)集空嗎?按照沖突消解策略從該知識(shí)按照沖突消解策略從該知識(shí)集中選出一條知識(shí)進(jìn)行推理集中選出一條知識(shí)進(jìn)行推理 推出的是新事實(shí)嗎?推出的是新事實(shí)嗎? 將新事實(shí)加入到將新事實(shí)加入到DB把用戶補(bǔ)充的新事把用戶補(bǔ)充

18、的新事實(shí)實(shí)加入到加入到DB中中 用戶可補(bǔ)充新事實(shí)嗎?用戶可補(bǔ)充新事實(shí)嗎? 失敗退出失敗退出 成功退出成功退出YNNYNNNYYY114.1.4 正向推理正向推理推理例子推理例子 例例4.1請用正向推理完成以下問題的求解請用正向推理完成以下問題的求解 假設(shè)知識(shí)庫中包含有以下假設(shè)知識(shí)庫中包含有以下2條規(guī)則:條規(guī)則: r1: IF B THEN C r2: IF A THEN B已知初始證據(jù)已知初始證據(jù)A,求證目標(biāo),求證目標(biāo)C。 解:本例的推理過程如下:解:本例的推理過程如下: 推理開始前,綜合數(shù)據(jù)庫為空。推理開始前,綜合數(shù)據(jù)庫為空。 推理開始后,先把推理開始后,先把A放入綜合數(shù)據(jù)庫,然后檢查綜合數(shù)

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

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

21、無明確目標(biāo),求解問題是可能會(huì)執(zhí)行許多與解無推理無明確目標(biāo),求解問題是可能會(huì)執(zhí)行許多與解無關(guān)的操作,導(dǎo)致推理效率較低。關(guān)的操作,導(dǎo)致推理效率較低。 134.1.5 逆向推理逆向推理推理算法推理算法 從某個(gè)假設(shè)目標(biāo)出發(fā),逆向使用規(guī)則,亦稱為目標(biāo)驅(qū)動(dòng)推理或逆向鏈推從某個(gè)假設(shè)目標(biāo)出發(fā),逆向使用規(guī)則,亦稱為目標(biāo)驅(qū)動(dòng)推理或逆向鏈推理。理。算法描述:算法描述: (1) 將要求證的目標(biāo)(稱為假設(shè))構(gòu)成一個(gè)假設(shè)集;將要求證的目標(biāo)(稱為假設(shè))構(gòu)成一個(gè)假設(shè)集; (2) 從假設(shè)集中選出一個(gè)假設(shè),檢查該假設(shè)是否在綜合數(shù)據(jù)庫中,若在,從假設(shè)集中選出一個(gè)假設(shè),檢查該假設(shè)是否在綜合數(shù)據(jù)庫中,若在,則該假設(shè)成立,此時(shí),若假設(shè)集

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

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

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

25、1.5 逆向推理逆向推理推理例子推理例子對(duì)上例,采用逆向推理,其推理過程如下:對(duì)上例,采用逆向推理,其推理過程如下: 推理開始前,綜合數(shù)據(jù)庫和假設(shè)集均為空。推理開始前,綜合數(shù)據(jù)庫和假設(shè)集均為空。 推理開始后,先將初始證據(jù)推理開始后,先將初始證據(jù)A和目標(biāo)和目標(biāo)C分別放入綜合數(shù)據(jù)庫和假設(shè)集,然分別放入綜合數(shù)據(jù)庫和假設(shè)集,然后從假設(shè)集中取出一個(gè)假設(shè)后從假設(shè)集中取出一個(gè)假設(shè)C,查找,查找C是否為綜合數(shù)據(jù)庫中的已知事實(shí),回是否為綜合數(shù)據(jù)庫中的已知事實(shí),回答為答為“N”。 再檢查再檢查C是否能被知識(shí)庫中的知識(shí)所導(dǎo)出,發(fā)現(xiàn)是否能被知識(shí)庫中的知識(shí)所導(dǎo)出,發(fā)現(xiàn)C可由可由r1導(dǎo)出,于是導(dǎo)出,于是r1被被放入可用知

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

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

28、 也有利于向用戶提供解釋,在診斷性專家系統(tǒng)中較為也有利于向用戶提供解釋,在診斷性專家系統(tǒng)中較為有效。有效。 逆向推理的主要缺點(diǎn)逆向推理的主要缺點(diǎn) 當(dāng)用戶對(duì)解的情況認(rèn)識(shí)不請時(shí),由系統(tǒng)自主選擇假設(shè)當(dāng)用戶對(duì)解的情況認(rèn)識(shí)不請時(shí),由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大,若選擇不好,可能需要多次提出假目標(biāo)的盲目性比較大,若選擇不好,可能需要多次提出假設(shè),會(huì)影響系統(tǒng)效率。設(shè),會(huì)影響系統(tǒng)效率。174.1.6 混合推理混合推理混合推理的概念混合推理的概念 把正向推理和逆向推理結(jié)合起來所進(jìn)行的推理稱為混合推理。是把正向推理和逆向推理結(jié)合起來所進(jìn)行的推理稱為混合推理。是一種解決較復(fù)雜問題的方法。一種解決較復(fù)雜問題的方

29、法?;旌贤评淼姆椒ɑ旌贤评淼姆椒?1. 先正向后逆向先正向后逆向 這種方法先進(jìn)行正向推理,從已知事實(shí)出發(fā)推出部分結(jié)果,然后這種方法先進(jìn)行正向推理,從已知事實(shí)出發(fā)推出部分結(jié)果,然后再用逆向推理對(duì)這些結(jié)果進(jìn)行證實(shí)或提高它們的可信度。再用逆向推理對(duì)這些結(jié)果進(jìn)行證實(shí)或提高它們的可信度。 2. 先逆向后正向先逆向后正向 這種方法先進(jìn)行逆向推理,從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè),這種方法先進(jìn)行逆向推理,從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè),然后再用正向推理對(duì)這些中間假設(shè)進(jìn)行證實(shí)。然后再用正向推理對(duì)這些中間假設(shè)進(jìn)行證實(shí)。 3. 雙向混合雙向混合 是指正向推理和逆向推理同時(shí)進(jìn)行,使推理過程在中間的某一步是指正向推理和

30、逆向推理同時(shí)進(jìn)行,使推理過程在中間的某一步結(jié)合起來。結(jié)合起來。 對(duì)于這些方法我不再詳細(xì)討論。對(duì)于這些方法我不再詳細(xì)討論。18第4章 確定性推理 4.1 推理的基本概念推理的基本概念 4.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 4.3 自然演繹推理自然演繹推理 4.4 歸結(jié)演繹推理歸結(jié)演繹推理 4.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理194.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 4.2.1 謂詞公式的解釋謂詞公式的解釋 4.2.2 謂詞公式的永真性和可滿足性謂詞公式的永真性和可滿足性 4.2.3 謂詞公式的等價(jià)性和永真蘊(yùn)含性謂詞公式的等價(jià)性和永真蘊(yùn)含性 4.2.4 謂詞公式的范式謂詞公式的范式 4.2

31、.5 置換與合一置換與合一204.2.1 謂詞公式的解釋謂詞公式的解釋概念概念 命題公式的解釋命題公式的解釋 在命題邏輯中,在命題邏輯中,命題公式的一個(gè)解釋就是對(duì)該命題公式中命題公式的一個(gè)解釋就是對(duì)該命題公式中各個(gè)命題變元的一次真值指派。各個(gè)命題變元的一次真值指派。 有了命題公式的解釋,就可據(jù)此求出該命題公式的真值。有了命題公式的解釋,就可據(jù)此求出該命題公式的真值。 謂詞公式的解釋謂詞公式的解釋 由于謂詞公式中可能包含由個(gè)體由于謂詞公式中可能包含由個(gè)體常量、變元或函數(shù)常量、變元或函數(shù),因此,因此,必須先考慮這些個(gè)體常量和函數(shù)在個(gè)體域上的取值,然后才必須先考慮這些個(gè)體常量和函數(shù)在個(gè)體域上的取值,

32、然后才能根據(jù)它們的具體取值為謂詞分別指派真值。能根據(jù)它們的具體取值為謂詞分別指派真值。 定義定義4.1 設(shè)設(shè)D是謂詞公式是謂詞公式P的非空個(gè)體域,若對(duì)的非空個(gè)體域,若對(duì)P中的個(gè)體常中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值:量、函數(shù)和謂詞按如下規(guī)定賦值: (1) 為每個(gè)個(gè)體常量指派為每個(gè)個(gè)體常量指派D中的一個(gè)元素;中的一個(gè)元素; (2) 為每個(gè)為每個(gè)n元函數(shù)指派一個(gè)從元函數(shù)指派一個(gè)從Dn到到D的一個(gè)映射,其中的一個(gè)映射,其中 Dn =(x1, x2, , xn)| x1, x2, , xnD (3) 為每個(gè)為每個(gè)n元謂詞指派一個(gè)從元謂詞指派一個(gè)從Dn到到F,T的映射。的映射。 則稱這些指派為則稱這

33、些指派為P在在D上的一個(gè)解釋上的一個(gè)解釋I 214.2.1 謂詞公式的解釋謂詞公式的解釋 例子一例子一(1/2) 例例4.2 設(shè)個(gè)體域設(shè)個(gè)體域D=1, 2,求公式,求公式A=(x)( y)P(x, y)在在D上的上的解釋,并指出在每一種解釋下公式解釋,并指出在每一種解釋下公式A的真值。的真值。 解:解:由于公式由于公式A中沒有包含個(gè)體常量和函數(shù),故可直接為謂中沒有包含個(gè)體常量和函數(shù),故可直接為謂詞指派真值,設(shè)有詞指派真值,設(shè)有 這就是公式這就是公式A 在在D 上的一個(gè)解釋。從這個(gè)解釋可以看出:上的一個(gè)解釋。從這個(gè)解釋可以看出: 當(dāng)當(dāng)x=1、y=1時(shí),有時(shí),有P(x,y)的真值為的真值為T; 當(dāng)

34、當(dāng)x=2、y=1時(shí),有時(shí),有P(x,y)的真值為的真值為T; 即對(duì)即對(duì)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 F224.2.1 謂詞公式的解釋謂詞公式的解釋 例子一例子一(2/2) 說明:說明:一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如,對(duì)一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如,對(duì)公式公式A,若給出另一組真值指派,若給出另一組真值指派 這也是公式這也是公式A 在在D 上的一個(gè)解釋。從這個(gè)解釋可以看出:

35、上的一個(gè)解釋。從這個(gè)解釋可以看出: 當(dāng)當(dāng)x=1、y=1時(shí),有時(shí),有P(x,y)的真值為的真值為T; 當(dāng)當(dāng)x=2、y=1時(shí),有時(shí),有P(x,y)的真值為的真值為F; 即對(duì)即對(duì)x在在D上的任意取值,不存在一個(gè)上的任意取值,不存在一個(gè)y使得使得P(x,y)的真值為的真值為T。因。因此,在此解釋下公式此,在此解釋下公式A的真值為的真值為F。 實(shí)際上,實(shí)際上,A在在D上共有上共有16種解釋,這里就不在一一列舉。種解釋,這里就不在一一列舉。 P(1,1) P(1,2) P(2,1) P(2,2) TT F F234.2.1 謂詞公式的解釋謂詞公式的解釋 例子二例子二 例例4.3 設(shè)個(gè)體域設(shè)個(gè)體域D=1,

36、2,求公式,求公式B=(x)P(f(x), a)在在D上的解釋,并指出在上的解釋,并指出在該解釋下公式該解釋下公式B的真值。的真值。 解:解:設(shè)對(duì)個(gè)體常量設(shè)對(duì)個(gè)體常量a和函數(shù)和函數(shù)f(x)的值指派為:的值指派為:對(duì)謂詞的真值指派為:對(duì)謂詞的真值指派為: 由于已指派由于已指派a=1,因此,因此P(1,2)和和P(2,2)不可能出現(xiàn),故沒給它們指派真值。不可能出現(xiàn),故沒給它們指派真值。 上述指派是公式上述指派是公式B在在D上的一個(gè)解釋。在此解釋下有上的一個(gè)解釋。在此解釋下有 當(dāng)當(dāng)x=1時(shí),時(shí),a=1使使P(1,1)=T 當(dāng)當(dāng)x=2時(shí),時(shí),a=1 使使P(2,1)=T即對(duì)即對(duì)x在在D上的任意取值,都

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

38、公式如果謂詞公式P對(duì)非空個(gè)體域?qū)Ψ强諅€(gè)體域D上的任一解釋都取得上的任一解釋都取得真值真值T,則稱,則稱P在在D 上是永真上是永真的;如果的;如果P在任何非空個(gè)體域上均是在任何非空個(gè)體域上均是永真的,則稱永真的,則稱P永真永真。 可見,要判定一謂詞公式為永真,必須對(duì)每個(gè)非空個(gè)體域上的可見,要判定一謂詞公式為永真,必須對(duì)每個(gè)非空個(gè)體域上的每個(gè)解釋逐一進(jìn)行判斷。當(dāng)解釋的個(gè)數(shù)為有限時(shí),盡管工作量大,每個(gè)解釋逐一進(jìn)行判斷。當(dāng)解釋的個(gè)數(shù)為有限時(shí),盡管工作量大,公式的永真性畢竟還可以判定,但當(dāng)解釋個(gè)數(shù)為無限時(shí),其永真公式的永真性畢竟還可以判定,但當(dāng)解釋個(gè)數(shù)為無限時(shí),其永真性就很難判定了。性就很難判定了。 定

39、義定義4.3 對(duì)于謂詞公式對(duì)于謂詞公式P,如果至少存在,如果至少存在D上的一個(gè)解釋,使上的一個(gè)解釋,使公式公式P在此解釋下的真值為在此解釋下的真值為T,則稱公式,則稱公式P在在D上是可滿足上是可滿足的。的。 謂詞公式的謂詞公式的可滿足性也稱為相容性可滿足性也稱為相容性。 定義定義4.4 如果謂詞公式如果謂詞公式P對(duì)非空個(gè)體域?qū)Ψ强諅€(gè)體域D上的任一解釋都取真上的任一解釋都取真值值F,則稱,則稱P在在D上是永假上是永假的;如果的;如果P在任何非空個(gè)體域上均是永在任何非空個(gè)體域上均是永假的,則稱假的,則稱P永假永假。 謂詞公式的永假性又稱謂詞公式的永假性又稱不可滿足性或不相容不可滿足性或不相容。 后

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

41、下: 定義定義4.5 設(shè)設(shè)P與與Q是是D上的兩個(gè)謂詞公式,若對(duì)上的兩個(gè)謂詞公式,若對(duì)D上上的任意解釋,的任意解釋,P與與Q都有相同的真值,則稱都有相同的真值,則稱P與與Q在在D 上是等價(jià)的。如果上是等價(jià)的。如果D是任意非空個(gè)體域,則稱是任意非空個(gè)體域,則稱P與與Q是等價(jià)的,記作是等價(jià)的,記作PQ。 264.2.3 謂詞公式的等價(jià)性和永真蘊(yùn)含性謂詞公式的等價(jià)性和永真蘊(yùn)含性 1. 等價(jià)式等價(jià)式(2/2)(1) 雙重否定律雙重否定律 P P(2) 交換律交換律 (PQ) (QP), ( PQ) ( QP)(3) 結(jié)合律結(jié)合律 (PQ)R P(QR) (PQ)R P(QR)(4) 分配律分配律 P(Q

42、R) (PQ)(PR) P(QR) (PQ)(PR)(5) 摩根定律摩根定律 (PQ) PQ (PQ) PQ(6) 吸收律吸收律 P(PQ) P P(PQ) P(7) 補(bǔ)余律補(bǔ)余律 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)QNoImage274.2.3 謂詞公式的等價(jià)性和永真蘊(yùn)含性謂詞公式的等價(jià)性和永真蘊(yùn)含性2. 永真蘊(yùn)含式永真蘊(yùn)含式 定義定義4

43、.6 對(duì)謂詞公式對(duì)謂詞公式P和和Q,如果,如果PQ永真,則稱永真,則稱P 永真蘊(yùn)含永真蘊(yùn)含Q,且稱,且稱Q為為P的邏輯結(jié)論,的邏輯結(jié)論,P為為Q的前提,記作的前提,記作P Q。 常用的永真蘊(yùn)含式如下:常用的永真蘊(yùn)含式如下: (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) 全稱固化全稱固化 (x)P(x) P(y) 其中,其

44、中,y是個(gè)體域中的任一個(gè)體,依此可消去謂詞公式中的全稱量詞。是個(gè)體域中的任一個(gè)體,依此可消去謂詞公式中的全稱量詞。 (9) 存在固化存在固化 (x)P(x) P(y) 其中,其中,y是個(gè)體域中某一個(gè)可以使是個(gè)體域中某一個(gè)可以使P(y)為真的個(gè)體,依此可消去謂詞公式中為真的個(gè)體,依此可消去謂詞公式中的存在量詞。的存在量詞。284.2.4 謂詞公式的范式謂詞公式的范式 范式是謂詞公式的標(biāo)準(zhǔn)形式。在謂詞邏輯中,范式分為兩種:范式是謂詞公式的標(biāo)準(zhǔn)形式。在謂詞邏輯中,范式分為兩種:前束范式前束范式 定義定義4.7 設(shè)設(shè)F為一謂詞公式,如果其中的所有量詞均非否定地出現(xiàn)在公式為一謂詞公式,如果其中的所有量詞

45、均非否定地出現(xiàn)在公式的最前面,且它們的轄域?yàn)檎麄€(gè)公式,則稱的最前面,且它們的轄域?yàn)檎麄€(gè)公式,則稱F為前束范式。一般形式:為前束范式。一般形式: (Q1x1)(Qnxn)M(x1,x2,xn)其中,其中,Qi(i=1,2,n)為前綴,它是一個(gè)由全稱量詞或存在量詞組成的量詞為前綴,它是一個(gè)由全稱量詞或存在量詞組成的量詞串;串; M(x1,x2,xn)為母式,它是一個(gè)不含任何量詞的謂詞公式。為母式,它是一個(gè)不含任何量詞的謂詞公式。 例如例如,(x) (y) (z)(P(x)Q(y,z)R(x,z)是前束范式。是前束范式。 任一謂詞公式均可化為與其對(duì)應(yīng)的前束范式,其化簡方法將在后面子句任一謂詞公式均可

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

47、,往往會(huì)出現(xiàn)謂詞名相同但其個(gè)體不在不同謂詞公式中,往往會(huì)出現(xiàn)謂詞名相同但其個(gè)體不同的情況,此時(shí)推理過程是不能直接進(jìn)行匹配的,需要先同的情況,此時(shí)推理過程是不能直接進(jìn)行匹配的,需要先進(jìn)行置換。進(jìn)行置換。 例如,可根據(jù)例如,可根據(jù)全稱固化全稱固化推理和推理和假言推理假言推理由謂詞公式由謂詞公式 W1(A) 和和 (x)(W1(x)W2(x) 推出推出W2(A)。對(duì)謂詞。對(duì)謂詞W1(A)可看作是由全程固化推理(即可看作是由全程固化推理(即(x)(W1(x) W1(A)推出的,其中推出的,其中A是任一個(gè)體常量。要是任一個(gè)體常量。要使用假言推理,首先需要找到項(xiàng)使用假言推理,首先需要找到項(xiàng)A對(duì)變元對(duì)變元x

48、的的置換置換,使,使W1(A)與與W1(x)一致。一致。 這種尋找項(xiàng)對(duì)變元的置換,使謂詞一致的過程叫做這種尋找項(xiàng)對(duì)變元的置換,使謂詞一致的過程叫做合一合一的過程的過程。 下面討論置換與合一的有關(guān)概念與方法。下面討論置換與合一的有關(guān)概念與方法。304.2.5 置換與合一置換與合一1. 置換置換(1/2) 置換可簡單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去替換變量。置換可簡單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去替換變量。 定義定義4.9 置換是形如置換是形如 t1/x1,t2/x2,tn/xn的有限集合。其中,的有限集合。其中,t1,t2,tn是項(xiàng);是項(xiàng);x1,x2,xn是互不相同的變元;是互不相同的

49、變元;ti/xi表示用表示用ti替換替換xi。并且要求。并且要求ti與與xi不能相同,不能相同,xi不能循環(huán)地出現(xiàn)在另一個(gè)不能循環(huán)地出現(xiàn)在另一個(gè)ti中。中。 例如,例如, a/x, c/y, f(b)/z 是一個(gè)置換。是一個(gè)置換。 但但g(y)/x, f(x)/y不是一個(gè)置換。原因是它在不是一個(gè)置換。原因是它在x與與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當(dāng)用即當(dāng)用g(y)置換置換x,用用f(g(y)置換置換y時(shí),既沒有消去時(shí),既沒有消去x,也沒有消去,也沒有消去y。 若改為若改為g(a)/x, f(x)/y即可,原因是用即可,原因是用g(a)置換置換x ,用,用f(g(a)置換置

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

51、x2,tn/xn = u1/y1, u2/y2, , um/ym 是兩個(gè)置換。則是兩個(gè)置換。則與與的合成也是一個(gè)置換,記作的合成也是一個(gè)置換,記作。它是從集合。它是從集合 t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , um/ym 中刪去以下兩種元素中刪去以下兩種元素 當(dāng)當(dāng)ti=xi時(shí),刪去時(shí),刪去ti/xi (i=1, 2 , n); 當(dāng)當(dāng)yj x1, x2 , xn 時(shí),刪去時(shí),刪去uj/yj (j=1, 2 , m)最后剩下的元素所構(gòu)成的集合。最后剩下的元素所構(gòu)成的集合。 例例4.4 設(shè)設(shè)= f(y)/x, z/y ,=a/x, b/y ,y/z ,求,求與

52、與的合成。的合成。 解解:先求出集合先求出集合 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滿足定義中的條件,需要?jiǎng)h除;滿足定義中的條件,需要?jiǎng)h除;a/x和和b/y滿足定義滿足定義中的條件,也需要?jiǎng)h除。最后得中的條件,也需要?jiǎng)h除。最后得 =f(b)/x, y/z324.2.5 置換與合一置換與合一2. 合一合一 合一合一可理解為可理解為是尋找

53、項(xiàng)對(duì)變量的置換,使兩個(gè)謂詞公式一致是尋找項(xiàng)對(duì)變量的置換,使兩個(gè)謂詞公式一致??啥x為:??啥x為: 定義定義4.12 設(shè)有公式集設(shè)有公式集F=F1, F2,Fn,若存在一個(gè)置換,若存在一個(gè)置換,可使,可使 F1=F2=Fn,則稱則稱是是F的一個(gè)合一。稱的一個(gè)合一。稱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是它的一個(gè)合一。是它的一個(gè)合一。 一般來說,一個(gè)公式集的合一不是唯一的。一般來說,一個(gè)公式集的合一不是唯一的。 定義定義4.13 設(shè)設(shè)是公式集是公式集F的一

54、個(gè)合一,如果對(duì)的一個(gè)合一,如果對(duì)F的任一個(gè)合一的任一個(gè)合一都存在一都存在一個(gè)置換個(gè)置換,使得,使得=,則稱,則稱是一個(gè)最一般合一。是一個(gè)最一般合一。 一個(gè)公式集的最一般合一是唯一的。一個(gè)公式集的最一般合一是唯一的。 對(duì)如何求取最一般合一的問題,不再討論。對(duì)如何求取最一般合一的問題,不再討論。33第第4章章 確定性推理確定性推理 4.1 推理的基本概念推理的基本概念 4.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 4.3 自然演繹推理自然演繹推理 4.4 歸結(jié)演繹推理歸結(jié)演繹推理 4.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理344.3 自然演繹推理自然演繹推理 自然演繹推理自然演繹推理 從一組已知為真的事

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

56、取詞 BC,BCD D 假言推理假言推理 D, DQ Q 假言推理假言推理 因此,因此,Q為真為真354.3 自然演繹推理自然演繹推理 例例4.6 設(shè)已知如下事實(shí):設(shè)已知如下事實(shí): (1) 只要是需要編程序的課,王程都喜歡。只要是需要編程序的課,王程都喜歡。 (2) 所有的程序設(shè)計(jì)語言課都是需要編程序的課。所有的程序設(shè)計(jì)語言課都是需要編程序的課。 (3) C+是一門程序設(shè)計(jì)語言課。是一門程序設(shè)計(jì)語言課。求證:王程喜歡求證:王程喜歡C+這門課。這門課。 證明:證明:首先定義謂詞首先定義謂詞 Prog(x) x是需要編程序的課。是需要編程序的課。 Like(x, y) x喜歡喜歡y。 Lang(x

57、) x是一門程序設(shè)計(jì)語言課是一門程序設(shè)計(jì)語言課把已知事實(shí)及待求解問題用謂詞公式表示如下:把已知事實(shí)及待求解問題用謂詞公式表示如下: Prog(x)Like(Wang , x) (x)( Lang(x)Prog(x) Lang(C+)應(yīng)用推理規(guī)則進(jìn)行推理:應(yīng)用推理規(guī)則進(jìn)行推理: 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+這門課。這門課。 364.

58、3 自然演繹推理自然演繹推理 優(yōu)點(diǎn):優(yōu)點(diǎn):定理證明過程自然,易于理解,并且有豐定理證明過程自然,易于理解,并且有豐富的推理規(guī)則可用。富的推理規(guī)則可用。 缺點(diǎn):缺點(diǎn):是容易產(chǎn)生知識(shí)爆炸,推理過程中得到的是容易產(chǎn)生知識(shí)爆炸,推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增,對(duì)于復(fù)雜問題的推中間結(jié)論一般按指數(shù)規(guī)律遞增,對(duì)于復(fù)雜問題的推理不利,甚至難以實(shí)現(xiàn)。理不利,甚至難以實(shí)現(xiàn)。 37第第4章章 確定性推理確定性推理 4.1 推理的基本概念推理的基本概念 4.2 推理的邏輯基礎(chǔ)推理的邏輯基礎(chǔ) 4.3 自然演繹推理自然演繹推理 4.4 歸結(jié)演繹推理歸結(jié)演繹推理 4.5 基于規(guī)則的演繹推理基于規(guī)則的演繹推理38

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論