人工智能第四部分

1、1第四部分 邏輯推理2 對(duì)很多復(fù)雜的系統(tǒng)和問(wèn)題，如果采用搜索推理方法，可能很難甚至無(wú)法使問(wèn)題獲得解決，需要應(yīng)用一些更先進(jìn)的推理技術(shù)來(lái)求解。 利用知識(shí)表示方法，可以把給定的領(lǐng)域問(wèn)題用某種形式表示出來(lái)，并存放到計(jì)算機(jī)中。但是，一個(gè)智能系統(tǒng)僅有知識(shí)是不夠的，還應(yīng)該能夠很好地利用這些知識(shí)，即運(yùn)用知識(shí)進(jìn)行推理和求解問(wèn)題。 智能系統(tǒng)的推理過(guò)程實(shí)際上是一種思維過(guò)程的模擬。3 推理的基本概念 推理的邏輯基礎(chǔ) 自然演繹推理 歸結(jié)演繹推理內(nèi)容提要4一. 什么是推理二. 推理的基本方法及分類三. 推理的控制策略及其分類四. 正向推理五. 逆向推理六. 混合推理七. 推理的沖突消解策略1. 推理的基本概念5 所謂推理

2、是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過(guò)程。 推理所用的事實(shí)包括兩種情況：一種是與求解問(wèn)題有關(guān)的初始證據(jù)，另一種是推理過(guò)程中所得到的中間結(jié)論。 通常，智能系統(tǒng)的推理過(guò)程是通過(guò)推理機(jī)來(lái)完成的。所謂推理機(jī)就是智能系統(tǒng)中用來(lái)實(shí)現(xiàn)推理的程序。一. 什么是推理6 例如，在醫(yī)療診斷專家系統(tǒng)中，所有與診斷有關(guān)的醫(yī)療常識(shí)和專家經(jīng)驗(yàn)都被保存在知識(shí)庫(kù)中。 當(dāng)系統(tǒng)開(kāi)始診斷疾病時(shí)，首先需要把病人的癥狀和檢查結(jié)果放到事實(shí)庫(kù)中，然后再?gòu)氖聦?shí)庫(kù)中的這些初始證據(jù)出發(fā)，按照某種策略在知識(shí)庫(kù)中尋找可以匹配的知識(shí)，如果得到的是一些中間結(jié)論，還需要把它們作為已知事實(shí)放入事實(shí)庫(kù)中，并繼續(xù)尋找可以匹配的知識(shí)，如此反復(fù)進(jìn)行，直到推出最

3、終結(jié)論為止。 這種由初始事實(shí)出發(fā)到推出最終結(jié)論為止的這一過(guò)程就是推理，實(shí)現(xiàn)這一推理過(guò)程的程序稱為推理機(jī)。7 推理方法主要解決在推理過(guò)程中前提與結(jié)論之間的邏輯關(guān)系，以及在非精確性推理中不確定性的傳遞問(wèn)題。推理可以有多種不同的分類方法，例如，可以按照推理的邏輯基礎(chǔ)、所用知識(shí)的確定性、推理過(guò)程的單調(diào)性以及是否使用啟發(fā)性信息等來(lái)劃分。1按推理的邏輯基礎(chǔ)分類 按照推理的邏輯基礎(chǔ)，常用的推理方法可分為演繹推理、歸納推理和默認(rèn)推理。 二. 推理方法及其分類8（1）演繹推理 演繹推理是從已知的一般性知識(shí)出發(fā)，去推出蘊(yùn)含在這些已知知識(shí)中的適合于某種個(gè)別情況的結(jié)論。是一種由一般到個(gè)別的推理方法，其核心是三段論。

4、常用的三段論是由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論三部分組成的。其中，大前提是已知的一般性知識(shí)或推理過(guò)程得到的判斷；小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。9例如，有三個(gè)判斷： 計(jì)算機(jī)系的學(xué)生都會(huì)編程序； 程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生； 程強(qiáng)會(huì)編程序。 這是一個(gè)三段論推理。 其中，是大前提;是小前提；是經(jīng)演繹推出來(lái)的結(jié)論。 從這個(gè)例子可以看出，“程強(qiáng)會(huì)編程序”這一結(jié)論是蘊(yùn)含在“計(jì)算機(jī)系的學(xué)生都會(huì)編程序”這個(gè)大前提中的。因此，演繹推理就是從已知的大前提中推導(dǎo)出適應(yīng)于小前提的結(jié)論，即從已知的一般性知識(shí)中抽取所包含的特殊性知識(shí)。由此可見(jiàn)，只要大前提和小前

5、提是正確的，則由它們推出的結(jié)論也必然是正確的。10（2）歸納推理 歸納推理是從一類事物的大量特殊事例出發(fā)，去推出該類事物的一般性結(jié)論。它是一種由個(gè)別到一般的推理方法。 歸納推理的基本思想是：先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。 對(duì)于歸納推理，如果按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理；如果按照推理所使用的方法可分為枚舉歸納推理、類比歸納推理、統(tǒng)計(jì)歸納推理和差異歸納推理等。11 所謂完全歸納推理是指在進(jìn)行歸納時(shí)需要考察相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬性，來(lái)推出該類事物是否具有此屬性。 例如，某公

6、司購(gòu)進(jìn)一批計(jì)算機(jī)，如果對(duì)每臺(tái)機(jī)器都進(jìn)行了質(zhì)量檢驗(yàn)，并且都合格，則可得出結(jié)論：這批計(jì)算機(jī)的質(zhì)量是合格的。 所謂不完全歸納推理是指在進(jìn)行歸納時(shí)只考察了相應(yīng)事物的部分對(duì)象，就得出了關(guān)于該事物的結(jié)論。 例如，某公司購(gòu)進(jìn)一批計(jì)算機(jī)，如果只是隨機(jī)地抽查了其中的部分機(jī)器，便可根據(jù)這些被抽查機(jī)器的質(zhì)量來(lái)推出整批機(jī)器的質(zhì)量。 12 所謂枚舉歸納推理是指在進(jìn)行歸納時(shí)，如果已知某類事物的有限個(gè)具體事物都具有某種屬性，則可推出該類事物都具有此種屬性。 設(shè)a1,a2,an是某類事物A中的具體事物，若已知a1，a2，an都具有屬性B，并沒(méi)有發(fā)現(xiàn)反例，那么當(dāng)n足夠大時(shí)，就可得出“A中的所有事物都具有屬性B”這一結(jié)論。13

7、例如，設(shè)有如下事例： 王強(qiáng)是計(jì)算機(jī)系學(xué)生，他會(huì)編程序； 高華是計(jì)算機(jī)系學(xué)生，她會(huì)編程序； 李明是計(jì)算機(jī)系學(xué)生，他會(huì)編程序； 趙杰是計(jì)算機(jī)系學(xué)生，他會(huì)編程序。 當(dāng)這些具體事例足夠多時(shí)，就可歸納出一個(gè)一般性的知識(shí)：凡是計(jì)算機(jī)系的學(xué)生，就一定會(huì)編程序。 按照枚舉法歸納出來(lái)的知識(shí)，盡管可能會(huì)有個(gè)別反例，但一般來(lái)說(shuō)還是合理的。14 所謂類比推理是指在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們?cè)谄渌麑傩陨弦蚕嗤蛳嗨频囊环N歸納推理。 設(shè)A、B分別是兩類事物的集合： A=a1，a2， B=b1，b2，并設(shè)ai與bi總是成對(duì)出現(xiàn)，且當(dāng)ai有屬性P時(shí)，bi就有屬性Q與之對(duì)應(yīng)，即 P（ai）Q（bi）

8、 il，2，則當(dāng)A與B中有一新的元素對(duì)出現(xiàn)時(shí)，若已知a有屬性P，則認(rèn)為b有屬性Q，即 P（a) Q（b) 類比推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個(gè)或兩類事物的相似程度以及這兩個(gè)或兩類事物的相同屬性與推出的那個(gè)屬性之間的相關(guān)程度。15（3）默認(rèn)推理 默認(rèn)推理是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理，因此也稱為缺省推理。 在推理過(guò)程中，如果發(fā)現(xiàn)原先的假設(shè)不正確，就撤消原來(lái)的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新按新情況進(jìn)行推理。 默認(rèn)推理允許在推理過(guò)程中假設(shè)某些條件是成立的，從而解決了在一個(gè)不完備的知識(shí)集中進(jìn)行推理的問(wèn)題。16（4）演繹推理與歸納推理的區(qū)別 演繹推理與歸納推理是

9、兩種完全不同的推理。 演繹推理是在已知領(lǐng)域內(nèi)的一般性知識(shí)的前提下，通過(guò)演繹求解一個(gè)具體問(wèn)題或者證明一個(gè)結(jié)論的正確性。它所得出的結(jié)論實(shí)際上早已蘊(yùn)含在一般性知識(shí)的前提中，演繹推理只不過(guò)是將已有事實(shí)揭示出來(lái)，因此它不能增殖新知識(shí)。17 在歸納推理中，所推出的結(jié)論是沒(méi)有包含在前提內(nèi)容中的。這種由個(gè)別事物或現(xiàn)象推出一般性知識(shí)的過(guò)程，是增殖新知識(shí)的過(guò)程。 例如，一位計(jì)算機(jī)維修員，當(dāng)他剛開(kāi)始從事這項(xiàng)工作時(shí)，只有書本知識(shí)，而無(wú)實(shí)際經(jīng)驗(yàn)。但當(dāng)他經(jīng)過(guò)一段時(shí)間的工作實(shí)踐后，就會(huì)通過(guò)大量實(shí)例積累起來(lái)一些經(jīng)驗(yàn)，這些經(jīng)驗(yàn)就是由一個(gè)個(gè)實(shí)例歸納出來(lái)的一般性知識(shí)，采用的是歸納推理方式。當(dāng)它有了這些一般性知識(shí)后，就可以運(yùn)用這些知

10、識(shí)去完成計(jì)算機(jī)的維修工作。而這種為某一臺(tái)具體的計(jì)算機(jī)運(yùn)用一般性知識(shí)進(jìn)行維修的過(guò)程則是演繹推理。182按所用知識(shí)的確定性分類 按所用知識(shí)的確定性，推理可分為確定性推理和不確定性推理。 所謂確定性推理是指推理所使用的知識(shí)和推出的結(jié)論都是可以精確表示，其真值要么為真，要么為假，不會(huì)有第三種情況出現(xiàn)。 所謂不確定性推理是指推理時(shí)所用的知識(shí)不都是確定的，推出的結(jié)論也不完全是確定的，其真值會(huì)位于真與假之間。由于現(xiàn)實(shí)世界中的大多數(shù)事物都具有一定程度的不確定性，并且這些事物是很難用精確的數(shù)學(xué)模型來(lái)進(jìn)行表示與處理的，因此不確定性推理也就成了人工智能的一個(gè)重要研究課題。193按推理過(guò)程的單調(diào)性 按照推理過(guò)程的單調(diào)

11、性，或者說(shuō)按照推理過(guò)程所得到的結(jié)論是否越來(lái)越接近目標(biāo)，推理可分為單調(diào)推理與非單調(diào)推理。 所謂單調(diào)推理是指在推理過(guò)程中，每當(dāng)使用新的知識(shí)后，所得到的結(jié)論會(huì)越來(lái)越接近于目標(biāo)，而不會(huì)出現(xiàn)反復(fù)情況，即不會(huì)由于新知識(shí)的加入否定了前面推出的結(jié)論，從而使推理過(guò)程又退回到先前的某一步。20 非單調(diào)推理是指在推理過(guò)程中，當(dāng)某些新知識(shí)加入后，會(huì)否定原來(lái)推出的結(jié)論，使推理過(guò)程退回到先前的某一步。 非單調(diào)推理往往是在知識(shí)不完全的情況下發(fā)生的。在這種情況下，為使推理能夠進(jìn)行下去，就需要先作某些假設(shè)，并在此假設(shè)的基礎(chǔ)上進(jìn)行推理。但是，當(dāng)后來(lái)由于新的知識(shí)加入，發(fā)現(xiàn)原來(lái)的假設(shè)不正確時(shí)，就需要撤銷原來(lái)的假設(shè)以及由此假設(shè)為基礎(chǔ)推

12、出的一切結(jié)論，再運(yùn)用新知識(shí)重新進(jìn)行推理。 21 智能系統(tǒng)的推理過(guò)程模擬人的思維過(guò)程，不僅依賴于所用的推理方法，同時(shí)也依賴于推理的控制策略。 推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理過(guò)程盡快達(dá)到目標(biāo)的策略。 智能系統(tǒng)的推理過(guò)程一般表現(xiàn)為一種搜索過(guò)程，推理的控制策略又可分為推理策略和搜索策略。 推理策略主要解決推理方向、沖突消解等問(wèn)題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等； 搜索策略主要解決推理線路、推理效果、推理效率等問(wèn)題。三. 推理的控制策略及其分類22 推理方向用來(lái)確定推理的控制方式，即推理過(guò)程是從初始證據(jù)開(kāi)始到目標(biāo)，還是從目標(biāo)開(kāi)始到初始證據(jù)。 按照對(duì)推理方向的控制，推理可

13、分為正向推理、逆向推理、混合推理及雙向推理四種情況。 無(wú)論哪一種推理方式，系統(tǒng)都需要有一個(gè)存放知識(shí)的知識(shí)庫(kù)，一個(gè)存放初始證據(jù)及中間結(jié)果的綜合數(shù)據(jù)庫(kù)和一個(gè)用于推理的推理機(jī)。 求解策略是指僅求一個(gè)解，還是求所有解或最優(yōu)解等。 限制策略是指對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行限制。 沖突消解策略是指當(dāng)推理過(guò)程有多條知識(shí)可用時(shí)，如何從這多條可用知識(shí)中選出一條最佳知識(shí)用于推理的策略。 23 正向推理是一種從已知事實(shí)出發(fā)、正向使用推理規(guī)則的推理方式，亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前項(xiàng)鏈推理。 其基本思想是：用戶需要事先提供一組初始證據(jù)，并將其放入綜合數(shù)據(jù)庫(kù)。推理開(kāi)始后，推理機(jī)根據(jù)綜合數(shù)據(jù)庫(kù)中的已有事實(shí)，到知識(shí)庫(kù)中尋

14、找當(dāng)前可用知識(shí)，形成一個(gè)當(dāng)前可用知識(shí)集，然后按照沖突消解策略，從該知識(shí)集中選擇一條知識(shí)進(jìn)行推理，并將新推出的事實(shí)加入綜合數(shù)據(jù)庫(kù)，作為后面繼續(xù)推理時(shí)可用的已知事實(shí)，如此重復(fù)這一過(guò)程，直到求出所需要的解或者知識(shí)庫(kù)中再無(wú)可用知識(shí)為止。四. 正向推理24 正向推理算法： （1）把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫(kù)。 （2）檢查綜合數(shù)據(jù)庫(kù)中是否包含了問(wèn)題的解，若已包含，則求解結(jié)束，并成功退出；否則執(zhí)行下一步。 （3）檢查知識(shí)庫(kù)中是否有可用知識(shí)，若有，形成當(dāng)前可用知識(shí)集，執(zhí)行下一步；否則轉(zhuǎn)（5）。 （4）按照某種沖突消解策略，從當(dāng)前可用知識(shí)集中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入綜合數(shù)據(jù)庫(kù)中，然后轉(zhuǎn)（

15、2）。 （5）詢問(wèn)用戶是否可以進(jìn)一步補(bǔ)充新的事實(shí)，若可補(bǔ)充，則將補(bǔ)充的新事實(shí)加入綜合數(shù)據(jù)庫(kù)中，然后轉(zhuǎn)（3）；否則表示無(wú)解，失敗退出。25成功退出失敗退出把初始數(shù)據(jù)放入綜合數(shù)據(jù)庫(kù)綜合數(shù)據(jù)庫(kù)中有解嗎？形成可用知識(shí)集可用知識(shí) 集 空？按照沖突消解策略從該知識(shí)集中選出一條知識(shí)進(jìn)行推理推出的是新事實(shí)？將該新事實(shí)加入到綜合數(shù)據(jù)庫(kù)中把用戶補(bǔ)充的新事實(shí)加入到綜合數(shù)據(jù)庫(kù)中用戶可以補(bǔ)充新事實(shí)嗎？知識(shí)庫(kù)中有可 用知識(shí)嗎？YYYYYNNNNN 正向推理的流程圖26 僅從正向推理的算法來(lái)看比較簡(jiǎn)單，但實(shí)際上推理的每一步都有許多工作要做。 例如，如何根據(jù)綜合數(shù)據(jù)庫(kù)中的事實(shí)到知識(shí)庫(kù)中選取可用知識(shí)；當(dāng)知識(shí)庫(kù)中有多條知識(shí)可用時(shí)

16、應(yīng)該先使用哪一條知識(shí)等。這些問(wèn)題涉及到了知識(shí)的匹配方法和沖突消解策略。 正向推理的優(yōu)點(diǎn)是比較直觀，允許用戶主動(dòng)提供有用的事實(shí)信息，適合于診斷、設(shè)計(jì)、預(yù)測(cè)、監(jiān)控等領(lǐng)域的問(wèn)題求解。 其主要缺點(diǎn)是推理無(wú)明確目標(biāo)，求解問(wèn)題時(shí)可能會(huì)執(zhí)行許多與解無(wú)關(guān)的操作，導(dǎo)致推理效率較低。27 逆向推理是一種以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的推理方法，也稱為目標(biāo)驅(qū)動(dòng)推理或逆向鏈推理。 其基本思想為： 首先根據(jù)問(wèn)題求解的要求，將要求證的目標(biāo)（稱為假設(shè)）構(gòu)成一個(gè)假設(shè)集； 然后從假設(shè)集中取出一個(gè)假設(shè)對(duì)其進(jìn)行驗(yàn)證，檢查該假設(shè)是否在綜合數(shù)據(jù)庫(kù)中、是否為用戶認(rèn)可的事實(shí)，當(dāng)該假設(shè)在數(shù)據(jù)庫(kù)中時(shí)，該假設(shè)成立，此時(shí)若假設(shè)集為空，則成功退出； 若假

17、設(shè)不在綜合數(shù)據(jù)庫(kù)中，但可被用戶證實(shí)為原始證據(jù)時(shí)，將該假設(shè)放入綜合數(shù)據(jù)庫(kù)，此時(shí)若假設(shè)集為空，則成功退出； 若假設(shè)可由知識(shí)庫(kù)中的一個(gè)或多個(gè)知識(shí)導(dǎo)出，則將知識(shí)庫(kù)中所有可以導(dǎo)出該假設(shè)的知識(shí)構(gòu)成一個(gè)可用知識(shí)集，并根據(jù)沖突消解策略從可用知識(shí)集中取出一個(gè)知識(shí)，將其前提中的所有子條件都作為新的假設(shè)放入假設(shè)集。 重復(fù)上述過(guò)程，直到假設(shè)集為空時(shí)成功退出，或假設(shè)集非空但可用知識(shí)集為空時(shí)失敗退出為止。 五. 逆向推理28逆向推理算法： （1）將要求證的目標(biāo)（稱為假設(shè)）構(gòu)成一個(gè)假設(shè)集； （2）從假設(shè)集中選出一個(gè)假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫(kù)中，若在，則該假設(shè)成立，此時(shí)，若假設(shè)集為空，則成功退出，否則仍執(zhí)行（2）；若該

18、假設(shè)不在數(shù)據(jù)庫(kù)中，則執(zhí)行下一步； （3）檢查該假設(shè)是否可由知識(shí)庫(kù)的某個(gè)知識(shí)導(dǎo)出。若不能由某個(gè)知識(shí)導(dǎo)出，則詢問(wèn)用戶該假設(shè)是否為可由用戶證實(shí)的原始事實(shí)，若是，該假設(shè)成立，并將其放入綜合數(shù)據(jù)庫(kù)，再重新尋找新的假設(shè)，若不是，則轉(zhuǎn)（5）；若能由某個(gè)知識(shí)導(dǎo)出，則執(zhí)行下一步； （4）將知識(shí)庫(kù)中可以導(dǎo)出該假設(shè)的所有知識(shí)構(gòu)成一個(gè)可用知識(shí)集； （5）檢查可用知識(shí)集是否為空，若空，失敗退出；否則執(zhí)行下一步； （6）按沖突消解策略從可用知識(shí)集中取出一個(gè)知識(shí)，繼續(xù)執(zhí)行下一步； （7）將該知識(shí)的前提中的每個(gè)子條件都作為新的假設(shè)放入假設(shè)集，轉(zhuǎn)（2）。29建立假設(shè)集從假設(shè)集中取出一個(gè)假設(shè)該假設(shè)是綜合數(shù)據(jù)庫(kù)中的事實(shí)該假設(shè)能被庫(kù)

19、中的知識(shí)導(dǎo)出嗎？將知識(shí)庫(kù)中所有能導(dǎo)出此假設(shè)的知識(shí)構(gòu)成一個(gè)可用知識(shí)集可用知識(shí)集空嗎將該知識(shí)前提中的每個(gè)子條件都作為新的假設(shè)放入假設(shè)集按沖突消解策略從可用知識(shí)庫(kù)中取出一個(gè)知識(shí)該假設(shè)成立還有新的假設(shè)嗎假設(shè)成立，并放入綜合數(shù)據(jù)庫(kù)詢問(wèn)有此事實(shí)嗎？失敗退出失敗退出成功退出成功退出YYYYYNNNN 逆向推理的流程圖逆向推理的流程圖 30 以上算法僅是逆向推理的一個(gè)框架性描述，具體實(shí)現(xiàn)時(shí)有許多問(wèn)題需要考慮。如： 第一，算法開(kāi)始時(shí)，初始假設(shè)應(yīng)該選擇準(zhǔn)確，否則會(huì)影響推理機(jī)的效率?，F(xiàn)有的方法有兩種：一種是由用戶提出，這種方法簡(jiǎn)單，但自動(dòng)化程度差；另一種是系統(tǒng)自主提出，這種方法自動(dòng)化程度較高但盲目性較大。 第二，當(dāng)

20、一個(gè)假設(shè)所對(duì)應(yīng)的知識(shí)的前提為多個(gè)子條件的邏輯組合時(shí)，這些子條件可能是與的關(guān)系，也可能是或的關(guān)系。當(dāng)為與關(guān)系時(shí)，若這些子條件之間隱含有某種必須遵守的隱含順序，則首先按隱含順序求解；若不存在這種隱含順序，則應(yīng)優(yōu)先選擇可能為假的子條件進(jìn)行推理。當(dāng)子條件之間為或關(guān)系時(shí)，則應(yīng)優(yōu)先選擇可能為真的子條件。這樣可以減少推理費(fèi)用。31第三，在驗(yàn)證一個(gè)子條件時(shí)，需要把它作為新的假設(shè)，并查找可以導(dǎo)出此新假設(shè)的知識(shí)，這就又會(huì)產(chǎn)生一組新的子條件，推理過(guò)程如此不斷地進(jìn)行下去，就會(huì)產(chǎn)生處于不同層次上的多組子條件，它將形成一種樹(shù)狀結(jié)構(gòu)。當(dāng)推理到達(dá)一個(gè)葉節(jié)點(diǎn)（即綜合數(shù)據(jù)庫(kù)中存在的事實(shí)或由用戶認(rèn)可的事實(shí)）時(shí)，又會(huì)逐層向上返回，并

21、且在返回過(guò)程中，又可能需要再次向下。如此多次上下反復(fù)，才會(huì)證明初始假設(shè)是否成立，可見(jiàn)這是一個(gè)十分復(fù)雜的過(guò)程。32例：設(shè)推理開(kāi)始時(shí)，知識(shí)庫(kù)中的規(guī)則和綜合數(shù)據(jù)庫(kù)中的事實(shí)如下：例：設(shè)推理開(kāi)始時(shí)，知識(shí)庫(kù)中的規(guī)則和綜合數(shù)據(jù)庫(kù)中的事實(shí)如下： 規(guī)則規(guī)則1 1：IF IF 你丟了自行車鑰匙，并且車胎沒(méi)氣你丟了自行車鑰匙，并且車胎沒(méi)氣 THEN THEN 自行車不能騎自行車不能騎 規(guī)則規(guī)則2 2：IF IF 自行車不能騎，并且你只有走路去自行車不能騎，并且你只有走路去 THEN THEN 你聽(tīng)課會(huì)遲到你聽(tīng)課會(huì)遲到 事實(shí)事實(shí)1 1：你丟了自行車鑰匙：你丟了自行車鑰匙 事實(shí)事實(shí)2 2：車胎沒(méi)氣：車胎沒(méi)氣 如果利用逆

22、向推理求證如果利用逆向推理求證“你聽(tīng)課會(huì)遲到你聽(tīng)課會(huì)遲到”這一假設(shè)，其推理過(guò)程如這一假設(shè)，其推理過(guò)程如下：下：33例：設(shè)推理開(kāi)始時(shí)，知識(shí)庫(kù)中的規(guī)則和綜合數(shù)據(jù)庫(kù)中的事實(shí)如下：例：設(shè)推理開(kāi)始時(shí)，知識(shí)庫(kù)中的規(guī)則和綜合數(shù)據(jù)庫(kù)中的事實(shí)如下： 規(guī)則規(guī)則1 1：IF IF 你丟了自行車鑰匙，并且車胎沒(méi)氣你丟了自行車鑰匙，并且車胎沒(méi)氣 THEN THEN 自行車不能騎自行車不能騎 規(guī)則規(guī)則2 2：IF IF 自行車不能騎，并且你只有走路去自行車不能騎，并且你只有走路去 THEN THEN 你聽(tīng)課會(huì)遲到你聽(tīng)課會(huì)遲到 事實(shí)事實(shí)1 1：你丟了自行車鑰匙：你丟了自行車鑰匙 事實(shí)事實(shí)2 2：車胎沒(méi)氣：車胎沒(méi)氣 如果利用

23、逆向推理求證如果利用逆向推理求證“你聽(tīng)課會(huì)遲到你聽(tīng)課會(huì)遲到”這一假設(shè)，其推理過(guò)程如下：這一假設(shè)，其推理過(guò)程如下：推理開(kāi)始時(shí)，假設(shè)集中只有一個(gè)假設(shè)推理開(kāi)始時(shí)，假設(shè)集中只有一個(gè)假設(shè)“你聽(tīng)課會(huì)遲到你聽(tīng)課會(huì)遲到”。首先從假設(shè)集中取出。首先從假設(shè)集中取出該假設(shè)，然后查找綜合數(shù)據(jù)庫(kù)，知該假設(shè)不是綜合數(shù)據(jù)庫(kù)中的事實(shí)。再查找知識(shí)庫(kù)，該假設(shè)，然后查找綜合數(shù)據(jù)庫(kù)，知該假設(shè)不是綜合數(shù)據(jù)庫(kù)中的事實(shí)。再查找知識(shí)庫(kù)，發(fā)現(xiàn)該假設(shè)可由規(guī)則發(fā)現(xiàn)該假設(shè)可由規(guī)則2 2導(dǎo)出，于是規(guī)則導(dǎo)出，于是規(guī)則2 2被放入可用知識(shí)集。由于只有這一條規(guī)則可被放入可用知識(shí)集。由于只有這一條規(guī)則可用，故可用知識(shí)集中只有規(guī)則用，故可用知識(shí)集中只有規(guī)則2

24、2。 從可用知識(shí)集中取出規(guī)則從可用知識(shí)集中取出規(guī)則2 2，將其兩個(gè)前提條件，將其兩個(gè)前提條件“自行車不能騎自行車不能騎”和和“你只有走你只有走路去路去”都作為新的假設(shè)放入假設(shè)集。此后，從假設(shè)集中取出一個(gè)假設(shè)都作為新的假設(shè)放入假設(shè)集。此后，從假設(shè)集中取出一個(gè)假設(shè)“自行車不能自行車不能騎騎”，它不是綜合數(shù)據(jù)庫(kù)中的事實(shí)，但可由規(guī)則，它不是綜合數(shù)據(jù)庫(kù)中的事實(shí)，但可由規(guī)則1 1導(dǎo)出，于是規(guī)則導(dǎo)出，于是規(guī)則1 1被放入可用知識(shí)被放入可用知識(shí)集，此時(shí)可用知識(shí)集中仍然是只有一條規(guī)則。從可用知識(shí)集中提出規(guī)則集，此時(shí)可用知識(shí)集中仍然是只有一條規(guī)則。從可用知識(shí)集中提出規(guī)則1 1，將其兩個(gè)，將其兩個(gè)前提條件前提條件“

25、你丟了自行車鑰匙你丟了自行車鑰匙”和和“車胎沒(méi)氣車胎沒(méi)氣”也作為新的假設(shè)放入假設(shè)集。此后，也作為新的假設(shè)放入假設(shè)集。此后，再?gòu)募僭O(shè)集中取出一個(gè)假設(shè)再?gòu)募僭O(shè)集中取出一個(gè)假設(shè)“你只有走路去你只有走路去”，檢查發(fā)現(xiàn)此假設(shè)既不在綜合數(shù)據(jù)庫(kù)，檢查發(fā)現(xiàn)此假設(shè)既不在綜合數(shù)據(jù)庫(kù)中，也不能被任何一條規(guī)則所導(dǎo)出，詢問(wèn)用戶中，也不能被任何一條規(guī)則所導(dǎo)出，詢問(wèn)用戶“你只有走路去嗎？你只有走路去嗎？”，若用戶回答，若用戶回答“是是”，則該假設(shè)成立，并被放入綜合數(shù)據(jù)庫(kù)。此時(shí)，假設(shè)集中還有兩個(gè)假設(shè)，則該假設(shè)成立，并被放入綜合數(shù)據(jù)庫(kù)。此時(shí)，假設(shè)集中還有兩個(gè)假設(shè)“你你丟了自行車鑰匙丟了自行車鑰匙”和和“車胎沒(méi)氣車胎沒(méi)氣”，繼續(xù)

26、推理，很顯然它們都是綜合數(shù)據(jù)庫(kù)中的事，繼續(xù)推理，很顯然它們都是綜合數(shù)據(jù)庫(kù)中的事實(shí)，均為真。繼續(xù)推理，假設(shè)庫(kù)也為空，推理過(guò)程結(jié)束，實(shí)，均為真。繼續(xù)推理，假設(shè)庫(kù)也為空，推理過(guò)程結(jié)束，“你聽(tīng)課會(huì)遲到你聽(tīng)課會(huì)遲到”得證。得證。 在上述例子中，如果詢問(wèn)用戶在上述例子中，如果詢問(wèn)用戶“你只有走路嗎？你只有走路嗎？”時(shí)，用戶回答時(shí)，用戶回答“否否”，則，則“你只有走路去你只有走路去”這一假設(shè)不成立，應(yīng)再檢查可用知識(shí)集中是否還有可用知識(shí)，但這一假設(shè)不成立，應(yīng)再檢查可用知識(shí)集中是否還有可用知識(shí)，但此時(shí)可用知識(shí)集中已無(wú)可用知識(shí)，且假設(shè)庫(kù)非空，故失敗退出。此時(shí)可用知識(shí)集中已無(wú)可用知識(shí)，且假設(shè)庫(kù)非空，故失敗退出。34

27、 逆向推理的主要優(yōu)點(diǎn)是不必尋找和使用那些與假設(shè)目標(biāo)無(wú)關(guān)的信息和知識(shí)，推理過(guò)程的目標(biāo)明確，同時(shí)也有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。其主要缺點(diǎn)是當(dāng)用戶對(duì)解的情況認(rèn)識(shí)不清時(shí)，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會(huì)影響系統(tǒng)效率。35 正向推理和逆向推理都有各自的優(yōu)缺點(diǎn)。當(dāng)問(wèn)題較復(fù)雜時(shí)，單獨(dú)使用其中的哪一種，都會(huì)影響到推理效率。為了更好地發(fā)揮這兩種算法各自的長(zhǎng)處，避免各自的短處，互相取長(zhǎng)補(bǔ)短，可以將它們結(jié)合起來(lái)使用。這種把正向推理和逆向推理結(jié)合起來(lái)所進(jìn)行的推理稱為混合推理。1混合推理的方法 混合推理可有多種具體的實(shí)現(xiàn)方法。例如，可以采用先正向推理，后逆

28、向推理的方法；也可以采用先逆向推理，后正向推理的方法；還可以采用隨機(jī)選擇正向和逆向推理的方法。下面分別對(duì)這三種情況進(jìn)行討論。六. 混合推理36（1）先正向后逆向的混合推理 這種方法先進(jìn)行正向推理，從已知事實(shí)出發(fā)推出部分結(jié)果，然后將這些部分結(jié)果作為事實(shí)放入綜合數(shù)據(jù)庫(kù)中，以此為依據(jù)進(jìn)行逆向推理。其推理過(guò)程如右圖所示。 開(kāi)始開(kāi)始進(jìn)行正向推理進(jìn)行正向推理需要逆向推理需要逆向推理嗎？嗎？以正向推理所得結(jié)果作以正向推理所得結(jié)果作為事實(shí)進(jìn)行逆向推理為事實(shí)進(jìn)行逆向推理還需要正向還需要正向推理嗎？推理嗎？退出退出先正向后逆向推理的流程圖先正向后逆向推理的流程圖 NNYY37（2）先逆向后正向的混合推理 這種方法

29、先進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正向推理對(duì)這些中間假設(shè)進(jìn)行證實(shí)。其推理過(guò)程如右圖所示。開(kāi)始開(kāi)始進(jìn)行逆向推理進(jìn)行逆向推理需要正需要正向推理向推理嗎嗎？進(jìn)行正向推理進(jìn)行正向推理還需要逆向還需要逆向推理嗎？推理嗎？退出退出先逆向再正向推理的流程圖 NNYY38（3）雙向混合推理 所謂雙向混合推理是指正向推理和逆向推理同時(shí)進(jìn)行，使推理過(guò)程在中間的某一步結(jié)合起來(lái)。 其基本思想是：依據(jù)某種選擇，先根據(jù)問(wèn)題的已知事實(shí)進(jìn)行正向推理，或從假設(shè)目標(biāo)出發(fā)進(jìn)行逆向推理。在整個(gè)推理過(guò)程中，兩種控制策略依據(jù)一定的算法交替執(zhí)行交替執(zhí)行。正向推理時(shí)不期望從初始證據(jù)一直推到最終目標(biāo)，逆向推理時(shí)也不期望從

30、某個(gè)假設(shè)一直推到原始事實(shí)，而是期望推理過(guò)程在中間的某處匯合。這種匯合表明了正向推理所得到的中間結(jié)果滿足了逆向推這種匯合表明了正向推理所得到的中間結(jié)果滿足了逆向推理的要求，也就表明了雙向混合推理的成功理的要求，也就表明了雙向混合推理的成功。 如果在推理過(guò)程的某一步，正向推理的結(jié)論否認(rèn)了逆向推理中的某個(gè)子假設(shè)，則說(shuō)明逆向推理中該子假設(shè)的選擇錯(cuò)誤，從而可終止該子假設(shè)，這樣可減少由于假設(shè)選擇盲目性所造成的損失。39開(kāi)始開(kāi)始選擇推理方向選擇推理方向是正向嗎是正向嗎？進(jìn)行逆向推理進(jìn)行逆向推理進(jìn)行正向推理進(jìn)行正向推理比較正向推出的結(jié)論和比較正向推出的結(jié)論和逆向推出的結(jié)論逆向推出的結(jié)論匹配嗎匹配嗎？成功，退出

31、成功，退出YNN 雙向混合推理的流程圖雙向混合推理的流程圖 40 2混合推理的適用場(chǎng)合 混合推理通常用于以下幾種情況： （1）已知事實(shí)不夠充分 如果綜合數(shù)據(jù)庫(kù)中的已知事實(shí)不夠充分，當(dāng)用這些事實(shí)與知識(shí)庫(kù)中知識(shí)的前提條件進(jìn)行匹配時(shí)，很可能找不到一個(gè)可以匹配的知識(shí)，這就使得推理無(wú)法進(jìn)行下去。此時(shí)，可把那些條件部分不能匹配的知識(shí)都找出來(lái)，并把這些知識(shí)的結(jié)論作為假設(shè)進(jìn)行逆向推理。由于在逆向推理中可以向用戶詢問(wèn)有關(guān)證據(jù)，這就有可能使推理再進(jìn)行下去。像這種需要先通過(guò)正向推理形成假設(shè)，然后再通過(guò)逆向推理去證實(shí)假設(shè)的情況特別適合采用混合推理。 41 （2）由正向推理推出的結(jié)論可信度不高 有些問(wèn)題，采用正向推理雖

32、然可以推出結(jié)論，但其可信度不高，甚至?xí)陀谝?guī)定的閾值。此時(shí)，可選擇幾個(gè)可信度相對(duì)較高的結(jié)論作為假設(shè)，然后進(jìn)行逆向推理。這樣，通過(guò)進(jìn)一步向用戶詢問(wèn)證據(jù)，有可能會(huì)推出可信度較高的結(jié)論。 42（3）希望得出更多的結(jié)論 在逆向推理中，由于要與用戶對(duì)話，這樣就會(huì)獲得一些原來(lái)未知的證據(jù)。這些證據(jù)不僅可用來(lái)證實(shí)需要證明的假設(shè)，同時(shí)還可能推出其他結(jié)論。此時(shí)，可通過(guò)使用正向推理，充分利用這些新獲得的證據(jù)去推出另外一些結(jié)論。（4）希望從正反兩個(gè)方向同時(shí)進(jìn)行推理 有時(shí)，可能會(huì)希望從正反兩個(gè)方向同時(shí)進(jìn)行推理，即根據(jù)問(wèn)題初始證據(jù)進(jìn)行正向推理，同時(shí)由假設(shè)的結(jié)論進(jìn)行逆向推理。 43 在推理的某一步，如果知識(shí)庫(kù)中有多條知識(shí)可

33、用，則稱發(fā)生了沖突。此時(shí)，需要按照某種策略從這多條知識(shí)中選擇一條最佳知識(shí)用于推理，稱這種解決沖突的過(guò)程為沖突消解。沖突消解所用的策略則稱為沖突消解策略。 七. 推理的沖突消解策略44 沖突消解的基本思想是對(duì)可用知識(shí)進(jìn)行排序。常用的沖突消解策略有:1特殊知識(shí)優(yōu)先 這種策略把知識(shí)的特殊性作為選擇知識(shí)的依據(jù)，優(yōu)先選擇那種更具有特殊性的知識(shí)。在當(dāng)前可用知識(shí)中，特殊性知識(shí)一般是要求前提條件更多的知識(shí)，特殊性知識(shí)比一般性知識(shí)具有針對(duì)性更強(qiáng)，結(jié)論更接近于目標(biāo)的特點(diǎn)。優(yōu)先選擇特殊性知識(shí)，會(huì)縮短推理過(guò)程。452新鮮知識(shí)優(yōu)先 這種策略把知識(shí)的新鮮性作為選擇知識(shí)的依據(jù)，優(yōu)先選擇更新鮮的知識(shí)，認(rèn)為新鮮知識(shí)是對(duì)老知識(shí)的

34、更新和改進(jìn)，比老知識(shí)更有效。 知識(shí)的新鮮性是根據(jù)該知識(shí)前提中所用事實(shí)的新鮮性來(lái)確定的，而事實(shí)的新鮮性則是根據(jù)其在綜合數(shù)據(jù)庫(kù)中生成的先后順序確定的。一般來(lái)說(shuō)，在綜合數(shù)據(jù)庫(kù)中后生成的事實(shí)比先生成的事實(shí)具有更大的新鮮性。 當(dāng)可用知識(shí)的前提均為多個(gè)事實(shí)的邏輯組合時(shí)，比較兩條知識(shí)新鮮性的方法有以下三種：46 （1）按前提中新鮮事實(shí)的個(gè)數(shù)進(jìn)行比較。如果一個(gè)知識(shí)前提中包含的新鮮事實(shí)比另一個(gè)知識(shí)前提中包含的新鮮事實(shí)多，則包含新鮮事實(shí)多的知識(shí)為更新鮮知識(shí)。 （2）按前提中最新鮮的事實(shí)進(jìn)行比較。如果一個(gè)知識(shí)的前提中包含的最新鮮事實(shí)比另一個(gè)知識(shí)前提中包含的最新鮮事實(shí)更新鮮，則包含有更新鮮事實(shí)的知識(shí)為更新鮮知識(shí)。 （

35、3）按前提中最不新鮮的事實(shí)進(jìn)行比較。如果一個(gè)知識(shí)的前提中包含的最不新鮮事實(shí)比另一個(gè)知識(shí)前提中包含的最不新鮮事實(shí)更不新鮮，則包含有更不新鮮事實(shí)的知識(shí)為更不新鮮知識(shí)。473差異性大的知識(shí)優(yōu)先 這種策略把知識(shí)的差異度作為選擇知識(shí)的依據(jù)，優(yōu)先選擇與上一次使用過(guò)的知識(shí)差別大的知識(shí)。這樣，可以避免重復(fù)執(zhí)行那些相近知識(shí)，防止系統(tǒng)在某個(gè)問(wèn)題附近進(jìn)行低效的、重復(fù)性的推理。4領(lǐng)域特點(diǎn)優(yōu)先 這種策略把領(lǐng)域問(wèn)題的特點(diǎn)作為選擇知識(shí)的依據(jù)，即根據(jù)領(lǐng)域問(wèn)題的特點(diǎn)把知識(shí)排成一定順序，然后按照這種順序選擇知識(shí)。5上下文關(guān)系優(yōu)先 這種策略把知識(shí)的上下文關(guān)系作為選擇知識(shí)的依據(jù)，即把知識(shí)庫(kù)中的知識(shí)按照其上下文關(guān)系分成若干組，在推理過(guò)

36、程的任一步，都只能從與當(dāng)時(shí)狀態(tài)有關(guān)的知識(shí)組中選擇知識(shí)。486前提條件少者優(yōu)先 這種策略把知識(shí)的前提條件個(gè)數(shù)作為選擇知識(shí)的依據(jù)，在結(jié)論相同的多個(gè)知識(shí)中優(yōu)先選擇前提條件少的知識(shí)。原因是前提條件少的知識(shí)在匹配時(shí)所花的時(shí)間也少。 除了上面所討論的幾種策略以外，還有一些策略可以使用。例如，在非確定性推理中可以按知識(shí)的匹配度選擇知識(shí)等。同時(shí)，對(duì)上述策略也可以組合起來(lái)使用，形成綜合沖突消解策略。49一. 謂詞公式的解釋二. 謂詞的永真性和可滿足性三. 謂詞公式的等價(jià)性與永真蘊(yùn)含性四. 謂詞公式的范式五. 置換與合一2. 推理的邏輯基礎(chǔ)50 前面討論了知識(shí)表示的一階謂詞邏輯表示法，已經(jīng)具備了謂詞邏輯的一些簡(jiǎn)單

37、概念。本節(jié)主要討論推理所需的邏輯基礎(chǔ)。 在命題邏輯中，命題公式的一個(gè)解釋就是對(duì)該命題公式中各個(gè)命題變?cè)囊淮握嬷抵概?。有了命題公式的解釋，就可以求出該命題公式的真值。 但謂詞邏輯則不同，由于謂詞公式中可能包含有個(gè)體常量、個(gè)體變?cè)蚝瘮?shù)，因此不能像命題公式那樣直接通過(guò)真值指派給出解釋，必須先考慮個(gè)體常量和函數(shù)在個(gè)體域上的取值，然后才能根據(jù)常量與函數(shù)的具體取值為謂詞分別指派真值。下面給出謂詞公式的解釋的定義。一. 謂詞公式的解釋51定義：設(shè)D是謂詞公式P的非空個(gè)體域，若對(duì)P中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值： （1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素； （2）為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的一

38、個(gè)映射，其中 Dn (x1,x2,xn)|x1,x2,xn D （3）為每個(gè)n元謂詞指派一個(gè)從Dn到T,F的映射 則稱這些指派為P在D上的一個(gè)解釋。52例：設(shè)個(gè)體域例：設(shè)個(gè)體域D=1,2，求公式求公式A=( x)(彐彐y)P(x,y) 在在D上的解釋，并指出在每一上的解釋，并指出在每一種解釋下公式種解釋下公式A的真值。的真值。解解: 由于公式由于公式A中沒(méi)有包含個(gè)體常量和函數(shù)，因此可以直接為謂詞指派真值，設(shè)有中沒(méi)有包含個(gè)體常量和函數(shù)，因此可以直接為謂詞指派真值，設(shè)有: 這就是公式這就是公式A在在D上的一個(gè)解釋。從這個(gè)解釋可以看出：上的一個(gè)解釋。從這個(gè)解釋可以看出： 當(dāng)當(dāng)x=1、y=1 時(shí)，有時(shí)

39、，有P(x,y)的真值為的真值為T； 當(dāng)當(dāng)x=2，y=1 時(shí)，有時(shí)，有P(x,y)的真值為的真值為T；即對(duì)即對(duì)x 在在D上的任意取值，都存在上的任意取值，都存在y=1使使P(x,y)的真值為的真值為T。因此，在此解釋下公式因此，在此解釋下公式A的真值為的真值為T。 需要注意，一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如，對(duì)公式需要注意，一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如，對(duì)公式A，若給出另一組真值若給出另一組真值指派指派 這也是公式這也是公式A在在D上的一個(gè)解釋。從這個(gè)解釋可以看出：上的一個(gè)解釋。從這個(gè)解釋可以看出： 當(dāng)當(dāng)x=1、y=1 時(shí)，有時(shí)，有P(x,y) 的真值為的真值為

40、T； 當(dāng)當(dāng)x=2、y=1 時(shí)，有時(shí)，有p(x,y)的真值為的真值為F；同樣同樣 當(dāng)當(dāng)x=1、y=2 時(shí)，有時(shí)，有P(x,y) 的真值為的真值為T； 當(dāng)當(dāng)x=2、y=2 時(shí)，有時(shí)，有P(x,y)的真值為的真值為F；即對(duì)即對(duì)x在在D上的任意取值，不存在一個(gè)上的任意取值，不存在一個(gè)y 使得使得P(x,y)的真值為的真值為T。因此，在此解釋下公式因此，在此解釋下公式A的真值為的真值為F。 實(shí)際上，實(shí)際上，A在在 D上共有上共有 16種解釋，這里就不再種解釋，這里就不再一列舉。一列舉。53例：設(shè)個(gè)體域D=1，2，求公式B=（ x）P（f（x），a）在D上的解釋，并指出在該解釋下公式A的真值。 解：設(shè)對(duì)個(gè)

41、體常量a和函數(shù)f（x）的真值指派為： 對(duì)謂詞的真值指派為： 這里，由于已知指派a=1，所以P（1，2）和P（2，2）不可能出現(xiàn)，故沒(méi)有給它們指派真值。 上述指派是公式B在D上的一個(gè)解釋。在此解釋下有 當(dāng)x=1時(shí)，a=1使P（1，1）=T 當(dāng)x=2時(shí)，a=1使P（2，1）=T即對(duì)x在D上的任意取值，都有P（f(x)，a）的真值為T。因此，在此解釋下公式B的真值為T。 由上面的例子可以看出，謂詞公式的真值都是針對(duì)某一個(gè)解釋而言的，它可由上面的例子可以看出，謂詞公式的真值都是針對(duì)某一個(gè)解釋而言的，它可能在某一個(gè)解釋下真值為能在某一個(gè)解釋下真值為 T T，而在另一個(gè)解釋下為而在另一個(gè)解釋下為 F F。

42、54 為了以后推理的需要，下面先定義謂詞公式的永真性、永假性、可滿足性與不可滿足性。 定義1：如果謂詞公式P對(duì)非空個(gè)體域D上的任一解釋都取得真值T，則稱P在D上是永真的；如果P在任何非空個(gè)體域上均是永真的，則稱P永真。 由此定義可以看出，要判定一個(gè)謂詞公式為永真，必須對(duì)每個(gè)非空個(gè)體域上的每個(gè)解釋逐一進(jìn)行判斷。當(dāng)解釋的個(gè)數(shù)有限時(shí)，盡管工作量大，公式的永真性畢竟還可以判定，但當(dāng)解釋個(gè)數(shù)無(wú)限時(shí)，其永真性就很難判定了。二. 謂詞公式的永真性與可滿足性55 定義2：對(duì)于謂詞公式P，如果至少存在D上的一個(gè)解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。謂詞公式的可滿足性又稱為相容性. 定義

43、3：如果謂詞公式P對(duì)非空個(gè)體域D上的任一解釋都取真值F，則稱P在D上是永假的；如果P在任何非空個(gè)體域上均是永假的，則稱P永假。 謂詞公式的永假性又稱不可滿足性或不相容性。56三. 謂詞公式的等價(jià)性與永真蘊(yùn)含性 謂詞公式的等價(jià)性和永真蘊(yùn)含性可分別用相應(yīng)的等價(jià)式和永真蘊(yùn)含式來(lái)表示，這些等價(jià)式和永真蘊(yùn)含式都是演繹推理的主要依據(jù)，因此也稱它們?yōu)橥评硪?guī)則推理規(guī)則。1等價(jià)式 謂詞公式的等價(jià)式可定義如下： 定義：設(shè)P與Q是D上的兩個(gè)謂詞公式，若對(duì)D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D上是等價(jià)的。如果D是任意非空個(gè)體域，則稱P與Q是等價(jià)的，記作PQ。57常用的等價(jià)式： （1）雙重否定率 P P

44、（2）交換率 PQ QP， PQ QP （3）結(jié)合率 （PQ）R P（QR）,（PQ）RP （QR） （4）分配率 P（QR）（PQ）（PR） P（QR）（PQ）（PR） （5）狄摩根定律 （PQ） P Q （PQ） P Q （6）吸收率 P（PQ）P， P（P Q）P （7）補(bǔ)余率 P P T , P P F （8）連詞化歸率 PQ P V Q , P Q (PQ) (QP) （9）量詞轉(zhuǎn)換率 (彐x）P（ x）（ P）， （ x）P（彐x）( P） （1O）量詞分配率 （ x）（PQ）（ x）P（ x）Q （彐x ）（PQ）（彐x ）P（彐x ）Q582. 永真蘊(yùn)含式謂詞公式的永真蘊(yùn)含式可

45、定義如下： 定義：對(duì)謂詞公式P和Q，如果PQ永真，則稱P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作P=Q。 等價(jià)式和永真蘊(yùn)含式是進(jìn)行演繹推理的重要依據(jù)，因此這些公式也被稱為推理規(guī)則。常用的永真蘊(yùn)含式如下： 59 （1）化簡(jiǎn)式 PQ = P， PQ=Q （2）附加式 P=PQ， Q=PQ （3）析取三段論 P，P V Q = Q （4）假言推理 P，PQ = Q （5）拒取式 Q，P Q = P （6）假言三段論 P Q，Q R = P R （7）二難推理 P Q，P R，Q R = R （8）全稱固化 （ x）P（x） = P（y） 其中，y是個(gè)體域中的任一個(gè)體，利用此永真蘊(yùn)含式可消

46、去謂詞公式中的全程量詞。 （9）存在固化 （彐x）P（x） = P（y） 其中，y是個(gè)體域中某一個(gè)可以使P（y）為真的個(gè)體，利用此永真蘊(yùn)含式可消去謂詞公式中的存在量詞。 60 四謂詞公式的范式 范式是公式的標(biāo)準(zhǔn)形式，公式往往需要變換為同它等價(jià)的范式，以便對(duì)它們作一般性的處理。在謂詞邏輯中，根據(jù)量詞在公式中出現(xiàn)的情況可將謂詞公式的范式分為兩種。611前束范式 定義：設(shè)F為謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，而它們的轄域?yàn)檎麄€(gè)公式，則稱F為前束范式。一般地，前束范式可寫成: （Q1x1）（Qnxn）M(x1,x2,xn)其中，Qi（i=1，2，n）為前綴，它是一個(gè)由全稱量詞或

47、存在量詞組成的量詞串； M(x1,x2,xn)為母式，它是一個(gè)不含任何量詞的謂詞公式。 例如，（ x）( y）(彐z）(P(x) Q(y,z)R(x,z)）是前束范式。 任一謂詞公式均可化為與其對(duì)應(yīng)的前束范式，其化簡(jiǎn)方法將在后面子句集的化簡(jiǎn)中討論。622Skolem范式 定義：如果前束范式中所有的存在量詞都在全稱量詞之前，則稱這種形式的謂詞公式為Skolem范式。 例如，（彐x）（彐z）（ y）（P(x) Q(y，z) R(x，z)是Skolem范式。 任一謂詞公式均可化為與其對(duì)應(yīng)的Skolem范式，其化簡(jiǎn)方法也將在后面子句集的化簡(jiǎn)中討論。63五置換與合一 在不同謂詞公式中，往往會(huì)出現(xiàn)謂詞名相

48、同但其個(gè)體不同的情況，此時(shí)推理過(guò)程是不能直接進(jìn)行匹配的，需要先進(jìn)行置換。例如，可根據(jù)全稱固化推理和假言推理由謂詞公式 W1(A)和（ x）(W1(x) W2(x) 推出W2(A) 。可以看出，要使用假言推理，首先需要找到項(xiàng)A對(duì)變?cè)獂的置換，使W1(A) 與W1(x) 一致。這種尋找項(xiàng)對(duì)變?cè)闹脫Q，使謂詞一致的過(guò)程叫做合一的過(guò)程。下面討論置換與合一的有關(guān)概念與方法。641置換（Substitution） 置換可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去替換變量。其形式定義如下定義：置換是形如t1/x1,t2/x2,tn/xn的有限集合。其中，t1,t2,tn是項(xiàng)；x1,x2,xn是互不相同的變?cè)?/p>

49、；ti/xi表示用ti置換xi。并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。65例如: ax，cy，f(b)z是一個(gè)置換。 但是g(y)/x,f(x)/y不是一個(gè)置換，原因是它在x與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。置換的目的是要將某些變?cè)昧硗獾淖冊(cè)?、常量或函?shù)取代，使其不在公式中出現(xiàn)。但在g(y)/x,f(x)/y中，它用g(y)置換x，用f(g(y)置換y，并沒(méi)有消去y。若改為g(a)/x,f(x)/y就可以了。它將把公式中的x用g(a)來(lái)置換，y用f(g(a) 來(lái)置換，從而消去了x和y. 通常，置換是用希臘字母、等來(lái)表示的。66定義：設(shè)=t1/x1,t2/x2,tn/xn 是

50、一個(gè)置換，F(xiàn)是一個(gè)謂詞公式，把公式F中出現(xiàn)的所有xi換成ti(i=1，2，n），得到一個(gè)新的公式G，稱G為F在置換下的例示，記作G=F 。 一個(gè)謂詞公式的任何例示都是該公式的邏輯結(jié)論。定義：設(shè) =t1/x1,t2/x2,tn/xn , =u1/y1,u2/y2,um/ym 是兩個(gè)置換。則 與 的合成也是一個(gè)置換，記作 它是從集合 t1 /x1,t2 /x2,tn /xn,u1/y1,u2/y2,um/ym中刪去以下兩種元素 當(dāng)ti= xi 時(shí)，刪去ti / xi （i=1，2，n）； 當(dāng) yix1,x2,xn時(shí)，刪去 uiyi（i=1,2,m）。最后剩下的元素所構(gòu)成的集合。67例：設(shè)=f(y)

51、/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)的結(jié)果；y/y中的y是置換作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件，需要?jiǎng)h除；a/x和b/y滿足定義中的條件，也需要?jiǎng)h除。 最后得 =f(b)/x,y/z682合一（Unifier） 合一可以簡(jiǎn)單地理解為是尋找項(xiàng)對(duì)變量的置換，使兩個(gè)謂詞公式一致。其形式定義如下:定義：設(shè)有公式集F=F1,F2,.,Fn ,若存在一個(gè)置換，可使F1= F2= F3= Fn 。則稱

52、是F的一個(gè)合一。稱F1,F2,.,Fn是可合一的。 一般來(lái)說(shuō)一個(gè)公式集的合一不是唯一的。69定義：設(shè)是公式集 F的一個(gè)合一, 如果對(duì)F的任一個(gè)合一都存在一個(gè)置換，可使= , 則稱是一個(gè)最一般合一(Most General Unifier.簡(jiǎn)記MGU)。 一個(gè)公式集的最一般合一是唯一的。如果用最一般合一去置換可合一的謂詞公式,可使它們變成完全一致的謂詞公式、現(xiàn)在的問(wèn)題是如何求取最一般合一，為此，下面討論求取最一 般合一的合一算法。 703合一算法 在討論合一算法之前，先引入分歧集的概念。 定義：設(shè) F=F1,F2,.,Fn是一個(gè)非空有限的公式集,從F中每個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較,直到發(fā)現(xiàn)第

53、一個(gè)不相同的符號(hào)為止, 從F的每個(gè)公式中取出以第一個(gè)不相同符號(hào)開(kāi)始的最大子表達(dá)式,并組成一個(gè)集合D, 則D稱為F的分歧集（Disagreement Set)。71例：求 F=P（x,y,z）， P（x,f(a), h(b)）的分歧集 解: 這里F1=P（x，y，z），F(xiàn)2=P（x,f(a), h（b ） ），分別從FI和F2的第一個(gè)符號(hào)開(kāi)始，逐 個(gè)向后比較會(huì)發(fā)現(xiàn)F1中的y與F2中的f（a）不同，它們構(gòu)成了一個(gè)分歧集： D1=y,f(a) 再繼續(xù)向后比較，又會(huì)發(fā)現(xiàn)F1中的z與F2中的h(b)不同，它們又構(gòu)成了一個(gè)分歧集： D2=z,h(b)72 (1) 令k=0,Fk=F, k=(空置換) ；

54、(2) 若Fk只含有一個(gè)表達(dá)式，則算法停止, k 就是最一般合一; (3) 找出Fk的分歧集DK； (4) 若DK中存在元素xk和tk,xk是變?cè)?tk是項(xiàng),同時(shí)xk不在tk中出現(xiàn),則置 k+1= k tk/xk, Fk+1=Fktk/xk, k=k+1然后轉(zhuǎn)（2）； （5）算法停止，F(xiàn)的最一般合一不存在。 有了分歧集的概念，就可以討論合一算法了。設(shè)F為非空有限集合，求F的最一般合一的合一算法如下：73例：例： 求公式集求公式集F= P(a,x,f(g(y) F= P(a,x,f(g(y) ，P(z,h(a,u),f(u) P(z,h(a,u),f(u) 的最一般合一的最一般合一. .解解:

55、根據(jù)合一算法根據(jù)合一算法,首先置首先置 k=0 ; F0=F ; 0= F0不是單一表達(dá)式不是單一表達(dá)式,有有D0=a,z. 其中其中z為變?cè)獮樽冊(cè)?并且并且z不在不在a中出現(xiàn)中出現(xiàn),從而從而 1= 0 a/z F1 = F0(a/z)= P(a,x,f(g(y) P(a,x,f(g(y) ，P(a,h(a,u),f(u) P(a,h(a,u),f(u) k=1: F1不是單一表達(dá)式不是單一表達(dá)式, D1=x,h(a,u). 其中其中x為變?cè)獮樽冊(cè)?從而從而 2= 1 h(a,u)/x =a/z, h(a,u)/x F2 = F1(h(a,u)/x)= P(a,h(a,u),f(g(y) P(

56、a,h(a,u),f(g(y) ，P(a,h(a,u),f(u) P(a,h(a,u),f(u) k=2: F2不是單一表達(dá)式不是單一表達(dá)式, D2=g(y),u. 其中其中u為變?cè)獮樽冊(cè)?從而從而 3= 2 g(y)/u =a/z, h(a,g(y)/x, g(y)/u F3 = F2(g(y)/u)= P(a,h(a,g(y),f(g(y) P(a,h(a,g(y),f(g(y) ，P(a,h(a,g(y),f(g(y) P(a,h(a,g(y),f(g(y) = P(a,h(a,g(y),f(g(y) = P(a,h(a,g(y),f(g(y) k=3: F3已是單一表達(dá)式已是單一表達(dá)式

57、, 從而從而 3= a/z, h(a,g(y)/x, g(y)/u是是F的最一般合一的最一般合一.743. 自然演繹推理75 從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過(guò)程稱為自然演繹推理。 在這種推理中，最基本的推理規(guī)則是三段論推理，它包括假言推理、拒取式推理、假言三段論等。76 在自然演繹推理中，需要避免兩類錯(cuò)誤：肯定后件的錯(cuò)誤和否定前件的錯(cuò)誤。 所謂肯定后件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過(guò)肯定后件Q為真來(lái)推出前件P為真，這是不允許的。原因是當(dāng)PQ及Q為真時(shí)，前件P既可能為真，也可能為假。 所謂否定前件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過(guò)否定前件P來(lái)推出后件Q為假，這也是

58、不允許的。原因是當(dāng)PQ及P為假時(shí)，后件Q既可能為真，也可能為假。77天下雨天下雨 地濕地濕肯定后件肯定后件: 地濕地濕 下雨下雨? ?否定前件否定前件:天不下雨天不下雨 地不濕地不濕? ?78 例：設(shè)已知如下事實(shí)： A，B，AC，BC D，DQ 求證：Q為真。 證明：因?yàn)锳，AC=C 假言推理 B，C=BC 引入合取詞 B C， B CD=D 假言推理 D，DQ=Q 假言推理 所以Q為真。79 例：設(shè)已知如下事實(shí)： （1）只要是需要編程序的課，王程都喜歡。 （2）所有的程序設(shè)計(jì)語(yǔ)言課都是需要編程序的課。 （3） C是一門程序設(shè)計(jì)語(yǔ)言課。 求證：王程喜歡C這門課。 證明：首先定義謂詞 Prog(

59、x) x是需要編程序的課。 Like(x,y) x喜歡y。 Lang(x) x是一門程序設(shè)計(jì)語(yǔ)言課。 把上述已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下： Prog（x）Like（Wang， x） （ x）（Lang（x）Prog(x) ) Lang（C） 應(yīng)用推理規(guī)則進(jìn)行推理： Lang（y）Prog（y） 全稱固化 Lang（C），Lang（y）Prog（y）=Prog（C） 假言推理 Prog（C），Prog（x）Like（Wang，x）=Like（Wang，C）假言推理. 因此，王程喜歡C這門課。80 一般來(lái)說(shuō)，自然演繹推理由已知事實(shí)推出的結(jié)論可能有多個(gè)，只要其中包含了需要證明的結(jié)論，就認(rèn)為

60、問(wèn)題得到了解。 自然演繹推理的優(yōu)點(diǎn)是定理證明過(guò)程自然，易于理解，并且有豐富的推理規(guī)則可用。 主要缺點(diǎn)是容易產(chǎn)生知識(shí)爆炸，推理過(guò)程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對(duì)于復(fù)雜問(wèn)題的推理不利，甚至難以實(shí)現(xiàn)。81一. 子句集及其化簡(jiǎn)二. 海伯倫理論三. 魯賓遜歸結(jié)原理四. 歸結(jié)演繹推理的歸結(jié)策略五. 用歸結(jié)反演求取問(wèn)題的答案4.歸結(jié)演繹推理82 歸結(jié)演繹推理是一種基于魯賓遜（Robinson）歸結(jié)原理的機(jī)器推理技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法”。 在人工智能中，很多問(wèn)題可以轉(zhuǎn)化為定理證明問(wèn)題。而定理證明的實(shí)質(zhì)