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

人工智能原理第四講經(jīng)典邏輯推理主講：王祖喜zuxiw@163.com華中科技大學(xué)圖像所4/21/20241經(jīng)典邏輯推理經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯的邏輯規(guī)則進(jìn)行的一種推理，又稱為機械-自動定理證明(mechanical-automatictheoremproving),主要推理方法有自然演繹推理，歸結(jié)演繹推理及與或形演繹推理等。由于這種推理是基于經(jīng)典邏輯的，其真值只有真和假兩種，因此它是一種精確推理。學(xué)習(xí)目的：

?學(xué)習(xí)運用知識進(jìn)行推理，求解問題。

4/21/20242主要講述內(nèi)容：

1.簡述與推理相關(guān)的知識：如推理方式及分類、推理控制策略、模式匹配、沖突消解策略、搜索策略等。2.經(jīng)典邏輯推理：自然演繹推理、歸結(jié)演繹推理和與/或形演繹推理。4/21/20243什么是推理推理從已知事實出發(fā)，運用已掌握的知識，找出其中蘊含的事實，或歸結(jié)出新的事實，這一過程稱為推理。推理機在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機。推理包括兩種判斷：一種是已知的判斷，它包括已掌握的與求解問題有關(guān)的知識以及關(guān)于問題的已知事實；另一種是由已知判斷推出的新判斷，即推理的結(jié)論。推理的基本任務(wù)：是從一種判斷推出另一種判斷。1推理的基本概念4/21/20244一般而言，推理有一下五種劃分方式：Ⅰ.演繹推理、歸結(jié)推理、默認(rèn)推理（從新判斷推出的途徑來劃分）演繹推理——從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程，即由一般性知識推出適合于某一具體情況的結(jié)論。這是一種從一般到個別的推理。演繹推理有多種形式，經(jīng)常用的是三段論式，它包括：1)大前提，這是已知的一般性知識或假設(shè)；2)小前提，這是關(guān)于所研究的具體情況或個別事實的判斷；推理的方式及其分類4/21/202453)結(jié)論，這是由大前提推出的適合于小前提所示情況的新判斷。例如：1)足球運動員的身體都是強壯的；2)高波是一名足球運動員；3)所以，高波的身體是強壯的。這就是一個三段論推理，其中，(1)是大前提，(2)是小前提，(3)是經(jīng)演繹推出的結(jié)論。結(jié)論“高波的身體是強壯的”事實上是蘊含于“足球運動員的身體都是強壯的”這一大前提中的。它沒有超出4/21/20246

大前提所斷定的范圍。這是演繹推理的一個典型特征，即在任何情況下，由演繹推理導(dǎo)出的結(jié)論都是蘊含在大前提的一般性知識中的。因此，只要大前提和小前提是正確的，則由它們推導(dǎo)出來的結(jié)論也必然是正確的。演繹推理是人工智能中的一種重要推理方式，在直到目前研制成功的各類智能系統(tǒng)中，大多是用演繹推理實現(xiàn)的。4/21/20247歸結(jié)推理——歸結(jié)推理是從足夠多的事例中歸結(jié)出一般性結(jié)論的推理過程，是一種從個別到一般的推理。歸結(jié)推理又分為完全歸結(jié)和不完全歸結(jié)兩種。完全歸結(jié)：指在進(jìn)行歸結(jié)時考察了相應(yīng)事物的全部對象，并根據(jù)這些對象是否都有某種屬性，從而推出這種事物是否具有這個屬性。例如:某廠進(jìn)行產(chǎn)品質(zhì)量檢查，如果對每一件產(chǎn)品都進(jìn)行了嚴(yán)格檢查，并且是合格的，則推導(dǎo)出結(jié)論該廠的產(chǎn)品是合格的。不完全歸結(jié)：指只考察了相應(yīng)事物的部分對象，就得出了結(jié)論。4/21/20248默認(rèn)推理——又稱缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。在默認(rèn)推理過程中，如果到某一時刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則就要撤銷所作默認(rèn)，以及由此默認(rèn)推出的所有結(jié)論重新按新情況進(jìn)行推理。Ⅱ.確定性推理，不確定性推理（按推理時所用知識的確定性來劃分）確定性推理——指推理時所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或為“真”，或為“假”，沒有第三種情況出現(xiàn)。下面將要討論的經(jīng)典邏輯推理就屬于這一類。4/21/20249

不確定性推理——指推理時所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于“真”和“假”之間，命題的外延模糊不清。這里我們要特別強調(diào)不確定性推理。自亞里士多德建立第一個演繹公理系統(tǒng)以來，經(jīng)典邏輯與精確數(shù)學(xué)的建立與發(fā)展為人類科學(xué)技術(shù)的發(fā)展起了巨大的作用。然而，現(xiàn)實世界中的事物和現(xiàn)象大都是不嚴(yán)格、不精確的，許多概念是模糊的，很難用精確的數(shù)學(xué)模型來表示和處理。因此。近幾年來，各種非經(jīng)典邏輯迅速崛起，人工智能亦把不精確知識的表示與處理作為重要的研究課題。另外，從人類思維活動的特征來看，人們經(jīng)常是在知識不完全、不精確的情況下進(jìn)行多方位的思考及推理的。因此，要使計算機模擬人類的思維活動，就必須使其具有不確定性推理的能力。4/21/202410Ⅲ.單調(diào)推理、非單調(diào)推理（按推理過程中推出的結(jié)論是否單調(diào)的增加來劃分）

單調(diào)推理——指在推理過程中隨著推理的向前推進(jìn)及新知識的加入，推出的結(jié)論呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，在推理過程中不會出現(xiàn)反復(fù)的情況，即不會由于新知識的加入而否定前面推出的結(jié)論，使推理又退回到前面的一步。非單調(diào)推理——指在推理過程中由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。4/21/202411Ⅳ.啟發(fā)式推理、非啟發(fā)式推理（按推理中是否運用與問題有關(guān)的啟發(fā)性知識分）

啟發(fā)式推理——推理中運用與問題有關(guān)的啟發(fā)性知識，即解決問題的策略、技巧、竅門，對解的特性及規(guī)律的估計等實踐經(jīng)驗和知識以加快推理過程、提高搜索效率，這種推理稱為啟發(fā)式推理。非啟發(fā)式推理——比如窮舉式推理等。4/21/202412Ⅴ.基于知識的推理、統(tǒng)計推理、直覺推理（從方法論的角度劃分）基于知識的推理——根據(jù)已掌握的事實，通過運用知識進(jìn)行的推理。統(tǒng)計推理——根據(jù)對某事物的數(shù)據(jù)統(tǒng)計進(jìn)行的推理(相當(dāng)于歸納推理)。直覺推理——又稱常識性推理，是根據(jù)常識進(jìn)行的推理。4/21/202413推理過程是一個思維過程，即求解問題的過程，求解問題的質(zhì)量和效率不僅依賴于所采用的求解方法，而且還依賴于求解問題的策略，即推理的控制策略。推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制策略等。推理的控制策略4/21/202414推理方向用于確定推理的驅(qū)動方式，分為正向推理、逆向推理、混合推理和雙向推理四種。無論按哪種方向進(jìn)行推理，一般都要求系統(tǒng)具有一個存放知識的知識庫，一個存放初始已知事實及問題狀態(tài)的數(shù)據(jù)庫和一個用于推理的與推理機。推理方向4/21/202415正向推理正向推理是以已知事實作為出發(fā)點的一種推理，又稱數(shù)據(jù)驅(qū)動推理、前向鏈推理及前件推理等。Ⅰ.正向推理的基本思想：從用戶提供的初始已知事實出發(fā)，在知識庫KB中找出當(dāng)前可適用的知識，構(gòu)成可適用知識集KS，然后按某種沖突消解策略從KS中選出一條知識進(jìn)行推理，并將推出的新事實加入到數(shù)據(jù)庫中作為下一步推理的已知事實，在此之后再在知識庫中選取可適用的知識進(jìn)行推理，如此重復(fù)，直到求得了所要求的解，或者知識庫中再無可適用的知識為止。4/21/202416正向推理過程算法描述：開始把初始已知事實送入DBDB中包含問題的解？KB中有可適用知識？KS空？把KB中所有可適用知識都選出來送入KS推出的是新事實？按沖突消解策略從KS中選出一條知識進(jìn)行推理將該新事實加入到DB中成功，退出把用戶提供的新事實加入DB中用戶可補充新事實？失敗，退出YYYYYNNNNN4/21/202417Ⅱ.與正向推理相關(guān)的問題：匹配方法——在以上推理過程中，需要從知識庫KB中選出可適用的知識，這就要用知識庫中的知識與數(shù)據(jù)庫中的已知事實進(jìn)行匹配，為此需確定匹配方法。搜索策略——為了進(jìn)行匹配，就要查找知識，這就牽涉到按什么路線進(jìn)行查找的問題，既按什么搜索策略搜索知識庫。沖突消解策略——如果適用的知識只有一條，這比較簡單，系統(tǒng)立即就可用它進(jìn)行推理，并將推出的新事實送入數(shù)據(jù)庫DB中；但是，如果當(dāng)前適用的知識有多條，應(yīng)該先用那一條?這是推理中的一個重要問題，稱為沖突消解策略?？傊?，為了實現(xiàn)正向推理，有許多具體問題需要解決。4/21/202418例:設(shè)在綜合數(shù)據(jù)庫中存放有下列已知事實：該動物身上有暗斑點，長脖子，長腿，有奶，有蹄且假設(shè)綜合數(shù)據(jù)庫中的已知事實與規(guī)則庫中的知識是從第一條開始，逐條進(jìn)行匹配的，則推理機構(gòu)的工作過程如下：①從規(guī)則庫中取出第一條規(guī)則r1，檢查前提條件與綜合數(shù)據(jù)庫中的已知事實不匹配；取第二條規(guī)則r2，r2的前提“該動物有奶”與綜合數(shù)據(jù)庫中事實匹配，則rr被執(zhí)行，其結(jié)論被加入綜合數(shù)據(jù)庫中，此時綜合數(shù)據(jù)庫中的事實為：該動物身上有暗斑點，長脖子，長腿，有奶，有蹄，是哺乳動物正向推理求解過程4/21/202419②接著取r3r4r5r6都不匹配，取到r7時，匹配成功，則將r7的結(jié)論加入綜合數(shù)據(jù)庫：該動物身上有暗斑點,長脖子,長腿,有奶,有蹄,是哺乳動物,是有蹄動物③接著取規(guī)則，取到r11時，匹配成功，發(fā)現(xiàn)其前提條件與綜合數(shù)據(jù)庫完全匹配，則確定該動物是：長頸鹿至此，問題的求解結(jié)束了。4/21/202420逆向推理是以某個假設(shè)目標(biāo)作為出發(fā)點的一種推理，又稱為目標(biāo)驅(qū)動推理、逆向鏈推理及后件推理等。Ⅰ.逆向推理的基本思想：首先選定一個假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說明原假設(shè)成立；若無論如何都找不到所需證據(jù)，說明原假設(shè)不成立，此時需要另作新的假設(shè)。Ⅱ.推理過程算法描述（圖示）逆向推理4/21/202421逆向推理過程算法描述：開始提出假設(shè)該假設(shè)在數(shù)據(jù)庫DB中？該假設(shè)是證據(jù)？在知識庫中找出所有能導(dǎo)出該假設(shè)的知識，形成適用知識集KS從KS中選出一條知識，并將該知識的一個運用條件作為一個新的假設(shè)目標(biāo)。該假設(shè)成立詢問用戶有此事實？該假設(shè)成立，并將此事實存入數(shù)據(jù)庫還有假設(shè)？退出YYYYNNNN4/21/202422假設(shè)某用戶希望動物識別系統(tǒng)驗證一下某動物是否是虎，并設(shè)當(dāng)前數(shù)據(jù)庫為空。其逆向推理過程為：

①以虎作為假設(shè)目標(biāo);

②檢察數(shù)據(jù)庫中有無虎這個事實。因為數(shù)據(jù)庫初始為空，顯然不會有虎這個事實;

③判斷該目標(biāo)是否是證據(jù)；判斷一個目標(biāo)是否是證據(jù)，只要檢查它是否為某條知識的結(jié)論就可得知。如果它不包含在任何一條知識的結(jié)論部分中，那么它就是證據(jù)。這里虎顯然不是證據(jù)，因為它是規(guī)則r10的結(jié)論；逆向推理求解過程4/21/202423

④

在知識庫中找出所有能導(dǎo)出該目標(biāo)的知識。該問題比較簡單，只有一條知識可導(dǎo)出結(jié)論虎，即r10；r10:If該動物是哺乳動物and是食肉動物and是黃褐色and身上有黑色條紋then該動物是虎⑤

將r10的運用條件分別作為新的假設(shè)進(jìn)行驗證。該知識有一個運用條件是“是黃褐色”，當(dāng)把它作為新假設(shè)進(jìn)行推理時，

?首先要檢查數(shù)據(jù)庫中有無該事實，這里顯然沒有；4/21/202424

?接著判斷它是否是證據(jù)，因在r1-r15中沒有一條知識的結(jié)論部分包含它，所以它是證據(jù)。

?此時詢問用戶：你看到的動物是黃褐色嗎？若用戶答是，則該運用條件就得到了驗證，并將它存入數(shù)據(jù)庫中；若用戶回答不是，則就否定了原先關(guān)于虎的假設(shè)，需要作另外的假設(shè)，從頭開始進(jìn)行逆向推理。這里，我們假設(shè)用戶的回答為是，以便將推理進(jìn)行下去。⑥對于知識的運用條件“身上有黑條紋”與上面處理類似,因為它也是一個證據(jù)，我們同樣假定用戶的回答為是，這樣數(shù)據(jù)庫中就又增加了一個事實。4/21/202425

現(xiàn)在數(shù)據(jù)庫中有兩個事實：是黃褐色、身上有黑條紋。⑦

對于知識的運用條件“是哺乳動物”，因它沒有在數(shù)據(jù)庫中出現(xiàn)，同時又不是證據(jù)（它是r1與r2的結(jié)論），所以要在知識庫中找出能導(dǎo)出它的所有知識，即r1與r2：

r1:If該動物有毛發(fā)then該動物是哺乳動物r2:If該動物有奶then該動物是哺乳動物4/21/202426此時，因同時有兩條知識可供使用，因而存在先使用哪一個的問題。這有多種處理方法，將在以后討論，這里我們采用最簡單的一種，即哪一個排在前面就先使用哪一個，所以用r1。由于r1的運用條件是有毛發(fā)，因此又要把有毛發(fā)作為新假設(shè)進(jìn)行驗證，顯然它是一個證據(jù)。經(jīng)詢問用戶，假定回答為是，這樣，是哺乳動物就被肯定。

⑧

對于運用條件“是食肉動物”可作類似處理，只是為證實它，要用到r5或r6。4/21/202427r5:If該動物吃肉then該動物是食肉動物r6:If該動物有犬齒and有爪and眼盯前方then該動物是食肉動物使用r5時，若用戶對詢問“該動物吃肉嗎”給出肯定的回答。至此r10的四個運用條件都被證實，從而肯定原假設(shè)“該動物是虎”的正確性。4/21/202428Ⅲ.逆向推理的主要優(yōu)點：不必使用與目標(biāo)無關(guān)的知識，目的性強，同時還有利于向用戶提供解釋。

逆向推理的主要缺點：初始目標(biāo)的選擇有盲目性，若不符合實際，就要多次提出假設(shè)，影響到系統(tǒng)效率。4/21/202429Ⅰ.正、逆向推理存在的缺陷

正向推理——具有盲目、效率低等缺點；逆向推理——若提出的假設(shè)目標(biāo)不符合事實，也會降低系統(tǒng)效率。為解決這些問題，可把正向推理與逆向推理結(jié)合起來，取長補短；

象這樣既有正向又有逆向的推理稱為混合推理。

混合推理4/21/202430Ⅱ.混合推理的兩種情況

?先正向再逆向：

先進(jìn)行正向推理，幫助選擇某個目標(biāo)，即從已知事實演繹出部分結(jié)果，然后再用逆向推理證實該目標(biāo)或提高其可信度。開始進(jìn)行正向推理需要逆向推理？還需要正向推理？以正向推理所得結(jié)果作為假設(shè)進(jìn)行逆向推理輸出結(jié)果退出YYNN4/21/202431?先逆向再正向：先假設(shè)一個目標(biāo)進(jìn)行逆向推理，然后再利用逆向推理中得到的信息進(jìn)行正向推理，以推出更多的結(jié)論。開始進(jìn)行逆向推理需要正向推理？還需要逆向推理？進(jìn)行正向推理輸出結(jié)果退出YYNN4/21/202432雙向推理是指正向推理與逆向推理同時進(jìn)行，且在推理過程中的某一步驟上“碰頭”的一種推理方式。基本思想：一方面根據(jù)已知事實進(jìn)行正向推理，但并不推到最終目標(biāo)；另一方面從某假設(shè)目標(biāo)出發(fā)進(jìn)行逆向推理，但并不推至原始事實，而是讓它們在中途相遇，即由正向推理所得的中間結(jié)論恰好是逆向推理此時所需要的證據(jù)，這時推理就可結(jié)束，逆向推理時所做的假設(shè)就是推理的最終結(jié)論。雙向推理4/21/202433求解策略所謂推理的求解策略是指，推理是只求一個解，還是求所有解以及最優(yōu)解等。限制策略為了防止無窮的推理過程，以及由于推理過程太長增加時間及空間的復(fù)雜性，可在控制策略中指定推理的限制條件，以對推理的深度，寬度，時間，空間等進(jìn)行限制。

求解策略和限制策略4/21/202434A概念

在推理過程中，系統(tǒng)要不斷地用當(dāng)前已知的事實與知識庫中的知識進(jìn)行匹配，此時可能發(fā)生如下三種情況：Ⅰ.已知事實不能與知識庫中的任何知識匹配成功；Ⅱ.已知事實恰好只與知識庫中的一個知識匹配成功；Ⅲ.已知事實可以與知識庫中的多個知識匹配成功；或者有多個（組）已知事實都可與知識庫中的一個知識匹配成功；或者有多個（組）已知事實可與知識庫中的多個知識匹配成功。

第三種情況為發(fā)生了沖突，此時需要按一定的策略解決沖突，以便從中挑選一個知識用于當(dāng)前的推理，稱這一解決沖突的過稱為沖突消解。解決沖突時所用的方法稱為沖突消解策略。沖突消解策略4/21/202435

B以產(chǎn)生式系統(tǒng)為例進(jìn)行較詳細(xì)說明Ⅰ.產(chǎn)生式系統(tǒng)沖突在產(chǎn)生式系統(tǒng)中，若出現(xiàn)下列情況就認(rèn)為發(fā)生了沖突：?對正向推理而言，如果有多條產(chǎn)生式規(guī)則的前件都和已知事實匹配成功；或者有多組不同的已知事實都與同一條產(chǎn)生式規(guī)則的前件匹配成功；或者以上兩種情況同時出現(xiàn)。

?對逆向推理而言，如果有多條產(chǎn)生式規(guī)則的后件都和同一個假設(shè)匹配成功；或者有多條產(chǎn)生式規(guī)則的后件可與多個假設(shè)匹配成功。4/21/202436Ⅱ.沖突消解沖突消解的任務(wù)是解決沖突。對正向推理來說，它將決定選擇哪一組已知事實來激活哪一條產(chǎn)生式規(guī)則，使它用于當(dāng)前的推理，產(chǎn)生其后件指出的結(jié)論或執(zhí)行相應(yīng)的操作。對逆向推理來說，它將決定用哪一個假設(shè)與哪一個產(chǎn)生式規(guī)則的后件進(jìn)行匹配，從而推出相應(yīng)的前件，作為新的假設(shè)。4/21/202437Ⅲ.沖突消解策略目前已有多種消解沖突的策略，其基本思想都是對知識進(jìn)行排序。常用的有以下幾種：①

按針對性排序——本策略是優(yōu)先選用針對性較強的產(chǎn)生式規(guī)則。

設(shè)有如下兩條產(chǎn)生式規(guī)則：r1:IFA1ANDA2AND…ANDAnTHENH1

r2：IFB1ANDB2AND…ANDBmTHENH2如果存在最一般合一，使得r1中每一個Ai都可變成相應(yīng)的Bi,即r2中包含r1的全部條件A1,A2,…An外，還包含其他條件，則稱r2比r1有更大的針對性，r1比r2有更大的通用性。4/21/202438

②

按已知事實的新鮮性排序——把數(shù)據(jù)庫中后生成的事實稱為新鮮的事實。在產(chǎn)生式的推理過程中，每應(yīng)用一條產(chǎn)生式規(guī)則就會得到一個或多個結(jié)論或者執(zhí)行某個操作，數(shù)據(jù)庫就會增加新的事實。另外，在推理時還會向用戶詢問有關(guān)的信息，也使數(shù)據(jù)庫的內(nèi)容發(fā)生變化。我們把數(shù)據(jù)庫中后生成的事實稱為新鮮的事實，即后生成的事實比先生成的事實具有較大的新鮮性。若一條規(guī)則被應(yīng)用后生成了多個結(jié)論，則即可以認(rèn)為這些結(jié)論有相同的新鮮性，也可認(rèn)為排在前面的結(jié)論有較大的新鮮性，根據(jù)情況而定。4/21/202439③按匹配度排序——匹配度大的知識優(yōu)先選用。在不確定性匹配中，為了確定兩個知識模式是否匹配，需要計算這兩個模式的相似程度，當(dāng)其達(dá)到某個預(yù)先規(guī)定的值時，則認(rèn)為它們是可匹配的。相似度又稱為匹配度。若產(chǎn)生式規(guī)則r1、r2都可匹配成功，則可根據(jù)它們的匹配度決定哪個規(guī)則被優(yōu)先選用。4/21/202440

④

根據(jù)領(lǐng)域問題的特點排序

某些領(lǐng)域問題，預(yù)先可知道它的某些特點，此時可根據(jù)這些特點把知識排成固定的順序。例如：

(1)

當(dāng)領(lǐng)域問題有固定的解題次序時，可按該次序排列相應(yīng)的知識，排在前面的知識優(yōu)先被應(yīng)用;

(2)當(dāng)已知某些產(chǎn)生式規(guī)則被應(yīng)用后會明顯的有利于問題的求解時，就使這些產(chǎn)生式規(guī)則優(yōu)先被應(yīng)用。4/21/202441

⑤按上下文限制排序

把產(chǎn)生式規(guī)則按它們所描述的上下文分成若干組，在不同的條件下，只能從相應(yīng)的組中選取有關(guān)的產(chǎn)生式規(guī)則。這樣，不僅可以減少沖突的發(fā)生，而且由于搜索范圍小，也提高了推理效率。

⑥

按冗余限制排序

如果一條產(chǎn)生式規(guī)則被應(yīng)用后將產(chǎn)生冗余知識，則降低了它被應(yīng)用的優(yōu)先級。產(chǎn)生的冗余知識越多，優(yōu)先級越低。

⑦

按條件個數(shù)排序

如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用，因為要求條件少的規(guī)則匹配時花費的時間較少。4/21/202442(1)基本概念

所謂模式匹配是指對兩個知識模式（如兩個謂詞公式、兩個框架片斷或兩個語義網(wǎng)絡(luò)片斷等）的比較與耦合，即檢查這兩個知識模式是否完全一致或近似一致。如果兩者完全一致，或雖不完全一致但其相似程度落在指定的限度內(nèi)，就稱它們是可匹配的，否則為不可匹配。模式匹配是推理中必須進(jìn)行的一項重要工作，因為只有經(jīng)過模式匹配才能從知識庫中選出當(dāng)前適用的知識，才能進(jìn)行推理。

模式匹配4/21/202443(2)分類

若按匹配時兩個知識模式的相似程度分，可分

為確定性匹配和不確定性匹配兩種。

確定性匹配——指兩個知識模式完全一致，或經(jīng)過變量代換后變的完全一致。

例如，設(shè)有兩個知識模式：P1：father(李四，李小四）andman(李小四)P2：father(x,y)andman(y)若用“李四”代換變量x，用“李小四”代換y，則P1，P2就變得完全一致，若用這兩個知識模式進(jìn)行匹配，則稱它們是確定性匹配。確定性匹配又稱完全匹配或精確匹配。4/21/202444不確定性匹配——指兩個知識模式不完全一致，但從總體上看，其相似程度又落在指定的限度內(nèi)。4/21/202445(3)變量代換無論是確定性匹配或不確定性匹配，在進(jìn)行匹配時一般都需要進(jìn)行變量的代換。

[定義1]代換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，t1,t2,…,tn是項；x1,x2,…,xn是互不相同的變元；ti/xi表示用ti代xi換，不允許ti與xi相同，也不允許變元xi循環(huán)地出現(xiàn)在另一個tj中。

例如：

{a/x,f(b)/y,w/z}是一個代換，

{g(y)/x,f(x)/y}不是一個代換。4/21/202446因為代換的目的是使某些變元被另外的變元、常量或函數(shù)取代，使之不再在公式中出現(xiàn)，而{g(y)/x,f(x)/y}在x與y之間出現(xiàn)了循環(huán)代換的情況，它既沒有消去x,也沒有消去y.如果將它改為{g(a)/x,f(x)/y}則是一個代換

它將把公式中的x用g(a)代換，y用f(g(a))代換，從而消去了變元x和y。4/21/202447[定義2]設(shè)

={t1/x1,t2/x2…,tn/xn}

={u1/y1,u2/y2,…,um/ym}是兩個代換，則此兩個代換的復(fù)合也是一個代換，是從{t1

/x1,t2

/x2…,tn

/xn,u1/y1,u2/y2,…,um/ym}中刪去如下兩種元素：ti

/xi當(dāng)ti

=xi

ui/yi當(dāng)yi

{x1,x2,…xn}后剩下的元素所構(gòu)成的集合，記為

o。例如，設(shè)有代換：

={f(y)/x,z/y}

={a/x,b/y,y/z}則

o

={f(b)/x，y/z}4/21/202448[定義3]設(shè)有公式集F={F1,F2,…Fn},若存在一個代換

使得F1

=F2

=…Fn

則稱

為公式集F的一個合一，且稱F1,F2,…Fn是可合一的。例如：假設(shè)有公式集F={P(x,y,f(y)),P(a,g(x),z)}則下式是它的一個合一：

={a/x,g(a)/y,f(g(a))/z}

一個公式集的合一一般來說是不唯一的。4/21/202449[定義4]設(shè)

是公式集F的一個合一，如果對任一個合一

都存在一個代換

，使得

=

o

，則稱

是一個最一般的合一。最一般的合一是唯一的。若用最一般合一去代換那些可合一的謂詞公式,可使它們變成完全一致的謂詞公式。由此可知，為了使兩個知識模式匹配，可用其最一般的合一對他們進(jìn)行代換。

4/21/202450差異集的概念：

設(shè)有如下兩個謂詞公式：F1:P(x，y，z)F2:P(x，f(a)，h(b)分別從F1與F2的第一個符號開始，逐個向右比較，此時發(fā)現(xiàn)F1中的y與F2中的f(a)不同，它們構(gòu)成了一個差異集：D1={y，f(a)}當(dāng)繼續(xù)向右比較時，又發(fā)現(xiàn)F1中的z與F2中的h(b)不同，則又得到一個差異集： D2={z，h(b)}4/21/202451下面給出求取最一般合一算法的具體步驟：(1)令k=0,Fk=F,

k=

。這里，F(xiàn)是欲求其最一般合一的公式集，

是空代換，它代表不作代換。(2)若Fk只含一個表達(dá)式，則算法停止，

k就是最一般合一。(3)

找出Fk的差異集Dk。(4)

若Dk中存在元素xk和tk，其中xk是變元，tk是項，且xk不在tk中出現(xiàn)，則置：

k+1=

ko{tk/xk}，…求取最一般合一的算法4/21/202452Fk+1=Fk{tk/xk}k=k+1然后轉(zhuǎn)（2）。(5)算法中止，F(xiàn)的最一般合一不存在4/21/202453例如：設(shè)F={P(a,x,f(g(y)),P(z,f(z),f(u))}求其最一般合一。(1)令

0=

，F(xiàn)0=F,因F0中含有兩個表達(dá)式，所以

0不是最一般合一；(2)

差異集D0={a,z}；(3)

1=

0o{a/z}={a/z},F1={P(a,x,f(g(y)),P(a,f(a),f(u))}；(4)D1={x,f(a)}；…求取實例4/21/202454(5)

2=

1o{f(a)/x}={a/z,f(a)/x}F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))}；(6)D2={g(y),u}；(7)

3=

2o{g(y)/u}={a/z,f(a)/x,g(y)/u}；(8)F3=F2{g(y)/u}={P(a,f(a),f(g(y)))}因為F3只含一個表達(dá)式，所以

3就是最一般合一，即

{a/z,f(a)/x,g(y)/u}4/21/202455經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯（命題邏輯和一階謂詞邏輯）的邏輯規(guī)則進(jìn)行的一種推理，又稱機械—自動定理證明。主要推理方法有自然演繹推理、歸結(jié)演繹推理和與/或形演繹推理等。這種推理是基于經(jīng)典邏輯的，其真值只有“真”與“假”兩種，因此它是一種精確推理，或稱為確定性推理。2經(jīng)典邏輯推理4/21/202456數(shù)學(xué)基礎(chǔ)—謂詞演算

(1)謂詞公式P（x1，x2，……，xn）其中，P是謂詞名，x1，x2，……，xn是個體。在謂詞中，個體可以是常量、變元、也可以是函數(shù)；個體變元的取值范圍稱為個體域；4/21/202457(2)謂詞公式的解釋[定義1]

設(shè)D為謂詞公式P的個體域，若對P中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：

Ⅰ.為每個個體常量指派D中的一個元素；Ⅱ.為每個n元函數(shù)指派一個從Dn到D的映射，其中Dn={(x1，x2，…，xn)/x1，x2，…，xnD}

Ⅲ.為每個n元謂詞指派一個從Dn到{F,T}的映射。

則稱這些指派為公式P在D上的一個解釋。

4/21/202458例1：設(shè)個體域D={1,2}，求公式A=(x)(y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。在公式中沒有個體常量和函數(shù)，所以直接給謂詞指派真值，設(shè)為：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F這就是謂詞公式A在D上的一個解釋。公式A的真值為：T（即對所有的x(1，2)，都存在一個y（1），使P(x,y)=T）4/21/202459

一個謂詞公式的解釋可能有很多個，對每一個解釋，謂詞公式都可以得到一個真值。對公式A中的謂詞還可以指派另一組真值：

P(1,1)=T,P(1,2)=T,P(2,1)=F,P(2,2)=F這是對公式A的另一種解釋，在此解釋下，公式A的真值為F（對所有的x(1，2)，不存在一個y，使P(x,y)=T）

公式A在D上共有16種解釋。4/21/202460(3)謂詞公式的永真性

[定義2]

如果謂詞公式P對個體域D上的任何一個解釋都取得真值T,則稱P在D上是永真的；如果P在每個非空個體域上均永真，則稱P永真。由定義1可知，要判斷一個公式永真，必須對每個個體域上的每一個解釋逐一判定，工作量太大，經(jīng)常是完成不了的。4/21/202461

[定義3]對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下真值為T，則稱公式P是可滿足的。[定義4]如果謂詞公式P對于個體域D上的任何一個解釋都取得真值F，則稱公式P在D上是永假的；如果P在每個非空個體域上均永假，則稱P永假。

謂詞公式的永假性又可稱為不滿足性或不相容性。4/21/202462(4)謂詞公式的等價性[定義5]

設(shè)P與Q是兩個謂詞公式，D是它們共同的個體域，若對D上的任何一個解釋，P與Q都有相同的真值，則稱P與Q在D上是等價的。如果D是任意個體域，則稱P與Q是等價的，記作：PQ。一些相關(guān)的等價式：交換律:PQQP

結(jié)合律:(PQ)RP(QR)

……

4/21/202463分配律：P(QR)(PQ)(PR)德.摩根律：(PQ)PQ(PQ)PQ連接詞化歸律：PQPQ量詞轉(zhuǎn)換律：(x)P(x)(P)(x)P(x)(P)

4/21/202464(5)謂詞公式的永真蘊含

[定義6]

對于謂詞公式P和Q，如果P

Q永真，則稱P永真蘊含Q。且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記為：PQ。

一些相關(guān)的永真蘊含式：

假言推理P,PQQ由PQ及P為真，可推出Q為真。拒取式Q,PQP由PQ及Q為假，可推出P為假。

假言三段論PQ，Q

RPR

永真蘊含式是進(jìn)行演繹推理的重要依據(jù)，應(yīng)用這些公式可確保推理的有效性，因此這些公式又稱為推理規(guī)則。4/21/202465除此之外，謂詞邏輯中還有如下一些推理規(guī)則：P規(guī)則：在推理的任何步驟上都可引入前提。T規(guī)則：推理時，如果前面步驟中有一個或多個公式永真蘊含公式S，則可把S引入推理過程中。反證法：PQ，當(dāng)且僅當(dāng)PQF。即，Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)PQ是不可滿足的?！逊醋C法推廣到謂詞公式集，可得到如下反證法定理：

[定理1]Q為P1,P2,…,Pn的邏輯結(jié)論，當(dāng)且僅當(dāng)(P1P2…Pn)Q是不可滿足的。4/21/202466從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理?；镜耐评硪?guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。假言推理P,PQQ由PQ及P為真，可推出Q為真。拒取式Q,PQP由PQ及Q為假，可推出P為假。P規(guī)則：在推理的任何步驟上都可引入前提。T規(guī)則：推理時，如果前面步驟中有一個或多個公式永真蘊含公式S，則可把S引入推理過程中。自然演繹推理4/21/202467這里應(yīng)避免如下兩類錯誤：一是肯定后件(Q)的錯誤；另一是否定前件(P)的錯誤；所謂肯定后件是指，當(dāng)P

Q為真時，希望通過肯定后件Q為真來推出前件P為真，這是不允許的。例1:伽利略在證明哥白尼的日心說時，曾使用了如下推理：(1)

如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相的變化;(2)

金星顯出位相變化;(3)

所以行星系統(tǒng)是以太陽為中心的。這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。4/21/202468例2：下面的推理就使用了否定前件的推理，違反了邏輯規(guī)則：(1)

如果下雨，則地上是濕的;(2)

沒有下雨;(3)

所以地上不濕。這顯然是錯誤的。4/21/202469(2)用自然演繹推理求解問題例：已知如下事實：(1)凡是容易的課程小王（Wang）都喜歡；(2)C班的課程都是容易的；(3)ds是C班的一門課程；求證：小王喜歡ds這門課。

證明：首先定義謂詞：

EASY(x)：x是容易的；LIKE(x,y)：x喜歡y;C(x)：x是C班的一門課。4/21/202470把上述已知事實及待求證的問題用謂詞公式表示出來：

EASY(x)LIKE(Wang,x)凡是容易的課程小王（Wang）都喜歡；

(x)(C(x)EASY(x))C班的課程都是容易的；C(ds)ds是C班的一門課程；LIKE(Wang,ds)小王喜歡ds這門課（待求證問題）。4/21/202471應(yīng)用推理規(guī)則進(jìn)行推理：因為：(x)(C(x)EASY(x))

所以：C(y)EASY(y)全稱固化因為：C(ds),C(y)EASY(y)EASY(ds)P規(guī)則及假言推理所以：EASY(ds)，EASY(x)LIKE(Wang,x)LIKE(Wang,ds)T規(guī)則及假言推理即：小王喜歡ds這門課程。4/21/202472(3)自然演繹推理優(yōu)缺點

優(yōu)點：表達(dá)定理證明過程自然，容易理解，而且其擁有豐富的推理規(guī)則，推理過程靈活，便于在其推理規(guī)則中嵌入領(lǐng)域啟發(fā)性知識。

缺點：容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般成指數(shù)形式遞增。4/21/202473自動定理證明是人工智能的一個重要研究領(lǐng)域，這不僅是由于許多數(shù)學(xué)問題需要通過定理證明得以解決，而且很多非數(shù)學(xué)問題(如醫(yī)療診斷、機器人行動規(guī)劃等）也都可歸結(jié)為一個定理證明問題。定理證明的實質(zhì)是對前提P和結(jié)論Q證明P

Q的永真性。但是要證明一個謂詞公式的永真性是很困難的。通過研究發(fā)現(xiàn)應(yīng)用反證法的思想可把關(guān)于永真性的證明轉(zhuǎn)化為不可滿足性的證明。欲證明P

Q永真，只要證明P∧Q不滿足就可以了。歸結(jié)演繹推理4/21/202474關(guān)于不可滿足性的證明，海伯倫及魯賓遜先后進(jìn)行了卓有成效的研究，提出了相應(yīng)的理論和方法。海伯倫提出的海伯倫域及海伯倫定理為自動定理的證明奠定了理論基礎(chǔ)；魯賓遜提出的歸結(jié)原理對機械化推理有了重大的突破。無論是海伯倫還是魯賓遜的理論，都是以子句集為背景開展研究的。4/21/202475在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱為文字。

[定義1]任何文字的析取式稱為子句。

例如：P(x)

Q(x)；

P(x,f(x))Q(x,g(x))等

[定義2]不包含任何文字的字句稱為空子句。由于空子句不含有文字，它不能被任何解釋滿足，所以空子句是永假的，不可滿足的。由子句構(gòu)成的集合稱為子句集。

在謂詞邏輯中，任何一個謂詞公式都可通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集。子句4/21/202476下面給出謂詞公式化成子句集的步驟：

①

利用等價關(guān)系消去蘊含符號（）：如：PQPQ（連接詞化規(guī)律）

例如公式(x)((y)P(x,y)(y)(Q(x,y)R(x,y)))經(jīng)等價變換后得：

(x)((y)P(x,y)

(y)(Q(x,y)

R(x,y)))

4/21/202477②利用等價關(guān)系把否定符號移到每個謂詞符號的前面：如：(x)P(x)(P)（量詞轉(zhuǎn)換律）(PQ)PQ（德.摩根律）

上式經(jīng)等價變換后得：

(x)((

y)P(x,y)

(

y)(Q(x,y)

R(x,y)))

③

重新命名變元名：使不同量詞約束的變元有不同的名字：

上式經(jīng)等價變換后得：(x)((

y)P(x,y)

(

z)(Q(x,z)

R(x,z)))4/21/202478④

用斯柯林（skolem）函數(shù)消去存在量詞：這里分兩種情況：?存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，變量y不依賴于其它變量，y用常量A代替。?存在量詞位于一個或多個全稱量詞的轄域內(nèi)，變量y的取值依賴于變量x的取值，此時需要用skolem函數(shù)f(x1,x2,…,xn)替換受該存在量詞約束的變元。上式中，存在量詞(

y)、(

z)都位于（x)的轄域內(nèi)，所以都需要用skolem函數(shù)替換，設(shè)y和z的skolem函數(shù)分別為f(x)和g(x)，

上式經(jīng)等價變換后得：

(x)(P(x,f(x))

(Q(x,g(x))

R(x,g(x))))4/21/202479⑤把所有的全稱量詞移到公式的左邊：如果公式內(nèi)部有全稱量詞，需要把它們都移到公式的左邊。上式只有一個全稱量詞，且已位于公式的最左邊。⑥利用等價關(guān)系P∨(Q∧R）

（P∨Q）∧（P∨R）把公式化為skolem標(biāo)準(zhǔn)形：skolem標(biāo)準(zhǔn)形為：(x1)(x2)…(xn)M其中，M是子句的合取式，稱為skolem標(biāo)準(zhǔn)形的母式。

上式經(jīng)等價變換后得：

(x)((P(x,f(x))(Q(x,g(x)))(P(x,f(x))

R(x,g(x))))4/21/202480⑦

消去全稱量詞。由于此時公式中所有變量都是約束的，全稱變量不必要，故可消去：

(P(x,f(x))

(Q(x,g(x)))

(P(x,f(x))

R(x,g(x)))⑧

對變元更名，使不同子句中的變元不同名。上式經(jīng)更名后得到：(P(x,f(x))

(Q(x,g(x)))

(P(y,f(y))

R(y,g(y)))

4/21/202481⑨消去合取詞。消去合取詞后，上式變?yōu)橄率鲎泳浼?/p>

P(x,f(x))Q(x,g(x))P(y,f(y))

R(y,g(y))[定理2]設(shè)有謂詞公式F，其標(biāo)準(zhǔn)形的子句集為S，則F不可滿足的充要條件是S不可滿足。4/21/202482為了判斷一個子句的不可滿足性，需要對個體域上的一切解釋逐個進(jìn)行判定，只有當(dāng)該子句對任何非空的個體域上的任何一個解釋都是不可滿足的，才能判斷該子句不可滿足。這幾乎是不可實現(xiàn)的。對此，海伯倫構(gòu)造了一個特殊的域，并證明只要對這個特殊域上的一切解釋進(jìn)行判定，就可得知子句集是否不可滿足。這個特殊域稱為海伯倫域。

海伯倫理論4/21/202483[定義3]設(shè)S為子句集，則按下述方法構(gòu)造的域H

稱為海伯倫域，簡記為H域。

(1)令H0是S中所有個體常量的集合，若S中不包含個體常量，則令H0={a},其中a為任意指定的一個個體常量。(2)令Hi+1=Hi

{S中所有n元函數(shù)f(x1,x2,…xn)|xj(j=1,2…n)是Hi中的元素},其中i=1,2,…4/21/202484

例1：求子句集S={P(x)

Q(x),R(f(y))}的H域。解：此例中沒有個體常量，故任意指定一個為a，則:H0={a}H1={a,f(a)}H2={a,f(a),f(f(a))}H3={a,f(a),f(f(f(a)))}……H

={a,f(a),f(f(f(a)))…}H域求解事例(一)4/21/202485例2:

求子句集S={P(a),Q(b),R(f(x))}的H域

解：根據(jù)H域的定義：H0={a,b}H1={a,b,f(a),f(b)}H2={a,b,f(a),f(b),f(f(a)),f(f(b))}……H域求解事例(二)4/21/202486例3:求子句集S={P(a),Q(f(x),R(g(y)))的H域解：根據(jù)H域的定義得到H0={a}H1={a,f(a),g(a)}H2={a,f(a),g(a),f(g(a)),g(f(a)),f(f(a)),g(g(a))}……H域求解事例(三)4/21/202487例4:

求子句集S={P(x),Q(y)

R(y)}的H域

解：由于該子句集中既無個體常量，又無函數(shù)，所以可任意指定一個常量a作為個體常量，從而得到H0=H1=…=H={a}H域求解事例(四)4/21/202488

基子句——如果用H域的元素代換子句中的變元，則所得的子句為基子句；基原子——基子句中的謂詞稱為基原子；原子集——子句集中的所有基原子構(gòu)成的集合稱為原子集。子句集S在H域上的解釋就是對S中出現(xiàn)的常量、函數(shù)及謂詞取值，一次取值就是一個解釋。下面給出S在H域上解釋的定義。4/21/202489[定義4]

子句集S在H域上的一個解釋I滿足下列條件：

(1)

在解釋I下，常量映射到自身；(2)S中的任一個n元函數(shù)是Hn

H的映射。即，設(shè)h1,h2,…

H,則f(h1,h2,…h(huán)n)

H(3)S中的任一個n元謂詞是Hn

{T,F}的映射。謂詞的真值可以指派為T,也可以指派為F。例如：設(shè)子句集S={P(a),Q(f(x))},它的H域為{a,f(a),f(f(a)),…}。S的原子集為{P(a),Q(f(a)),Q(f(f(a))),…},則S的解釋為：I1={P(a),Q(f(a)),Q(f(f(a))),…}I2={P(a),

Q(f(a)),Q(f(f(a))),…}……4/21/202490一般來說，一個子句集的基原子有無限多個，它在H域上的解釋也有無限多個?？梢宰C明，對給定域D上的任一個解釋，總能在H域上構(gòu)造一個解釋與它對應(yīng)，如果D域上的解釋能滿足子句集S，則在H域上的相應(yīng)解釋也能滿足S，由此可推出如下兩個定理：

[定理3]子句集S不可滿足的充要條件是S對H域上的一切解釋為假；

[定理4]子句集不可滿足的充要條件是存在一個有限的不可滿足的基子句集S’。該定理稱為海伯倫定理。4/21/202491海伯倫定理只從理論上給出了證明子句集不可滿足性的可行性及方法，但要在計算機上實現(xiàn)其證明過程是很困難的。1965年魯賓遜提出了歸結(jié)原理，這才使機器定理證明變?yōu)楝F(xiàn)實。4/21/202492

歸結(jié)原理又稱為消解原理，是魯賓遜提出的一種證明子句集不可滿足性，從而實現(xiàn)定理證明的一種理論及方法。?由謂詞公式轉(zhuǎn)化子句集的過程可以看出，在子句集中子句之間是合取關(guān)系，其中只要有一個子句不可滿足，則子句集就不可滿足;?空子句是不可滿足的，若一個子句集包含空子句集，則這個子句集一定是不可滿足的。魯賓遜歸結(jié)原理就是基于這一認(rèn)識提出來的。魯賓遜歸結(jié)推理4/21/202493基本思想魯賓遜歸結(jié)推理基本思想如下：

檢查子句集S中是否包含空子句，若包含，則S不可滿足；若不包含，就在子句集中選擇合適的子句進(jìn)行歸結(jié)，一旦通過歸結(jié)能推出空子句，就說明子句集S是不可滿足的。4/21/202494[定義5]若P是原子謂詞公式，則稱P與

P為互補文字。[定義6]設(shè)C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么從C1與C2中分別消去L1和L2，并將兩個子句中余下的部分析取，構(gòu)成一個新子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。

例1：設(shè)C1=

P

Q

R,C2=

Q

S這里L(fēng)1=Q,L2=

Q,通過歸結(jié)可得：C12=

P

R

S例2：設(shè)C1=P,C2=

P，通過歸結(jié)可得：C12=NIL命題邏輯中的歸結(jié)推理4/21/202495例3：設(shè)C1=

P

Q,C2=

Q

R,C3=P首先對C1與C2進(jìn)行歸結(jié)，得到：C12=

P

R然后再對C12與C3進(jìn)行歸結(jié)，得到：C123=R歸結(jié)可用一棵樹直觀的表示出來，如上例可用下圖表示其歸結(jié)過程：

P

Q

Q

R

P

RPR4/21/202496

[定理5]

歸結(jié)式C12是其親本子句C1與C2的邏輯結(jié)論。這是歸結(jié)原理中很重要的一個定理，由此可得到如下兩個推論：

[推論1]設(shè)C1與C2是子句集S中的兩個子句，C12是它們的歸結(jié)式，若用C12代替C1和C2后得到新子句集S1,則由S1的不可滿足性可推出原子句集S的不可滿足性，即：S1的不可滿足性

S的不可滿足性。4/21/202497[推論2]設(shè)C1與C2是子句集S中的兩個子句，C12是它們的歸結(jié)式，若把C12加入S中，得到新子句集S2，則S與S2在不可滿足的意義上是等價的，即：S2的不可滿足性

S的不可滿足性。這兩個推論告訴我們：為要證明子句集S的不可滿足性，只要對其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或者用歸結(jié)式替換它的親本子句，然后對新子句集證明不可滿足性就可以了。如果經(jīng)過歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，立即可得到原子句集S是不可滿足的結(jié)論。這就是用歸結(jié)原理證明子句集不可滿足的基本思想。4/21/202498

在謂詞邏輯中，由于子句中含有變元，所以不像命題邏輯那樣可直接消去互補文字，而需要先用最一般合一對變元進(jìn)行代換，然后才能進(jìn)行歸結(jié)。例:設(shè)由如下兩個子句：C1=P(x)

Q(x)；C2=

P(a)

R(y)由于P(x)與P(a)不同，所以C1與C2不能直接進(jìn)行歸結(jié)，但若用最一般合一

={a/x}對兩個子句分別進(jìn)行代換：C1

=P(a)

Q(a)；C2

=

P(a)

R(y)就可對他們進(jìn)行歸結(jié)，消去P(a)與P(a),得到如下的歸結(jié)式：Q(a)

R(y)謂詞邏輯中的歸結(jié)推理4/21/202499下面給出謂詞邏輯中關(guān)于歸結(jié)的定義。[定義7]設(shè)C1與C2是兩個沒有相同變元的子句，L1和L2分別是C1和C2中的文字，若

是L1和

L2的最一般合一，則稱：C12=(C1

－｛L1

｝)

(C2

－{L2

})為C1和C2的二元歸結(jié)式，L1和L2稱為歸結(jié)式上的文字。4/21/2024100例1：設(shè)C1=P(a)

Q(x)

R(x)，C2=

P(y)

Q(b)

(1)若選L1=P(a),L2=P(y),則

={a/y}是L1與L2的最一般合一。根據(jù)[定義7]可得：C12=(C1

－｛L1

｝)

(C2

－{L2

})=({P(a),

Q(x),R(x)}－{P(a)})

({

P(a),Q(b)}－｛P(a)｝)=({

Q(x),R(x)})

({Q(b)})={

Q(x),R(x),Q(b)}=

Q(x)

R(x)

Q(b)4/21/2024101(2)若選L1=

Q(x),L2=Q(b),

={b/x},則可得:C12=({P(a),

Q(b),R(b)}－{

Q(b)})

({

P(y),Q(b)}－{Q(b)})=({P(a),R(b)})

({

P(y)})={P(a),R(b),

P(y)}=P(a)

R(b)

P(y)4/21/2024102例2：設(shè)C1=P(x)

Q(a),C2=

P(b)

R(x)由于C1與C2有相同的變元，不符合[定義7]的要求。為了進(jìn)行歸結(jié)，需修改C2中變元的名字，令C2=

P(b)

R(y)。此時L1=P(x),L2=

P(b)L1與L2的最一般合一

={b/x}。則：C12=({P(b),Q(a)}-{P(b)})

({

P(b),R(y)}－{

P(b)})={Q(a),R(y)}=Q(a)

R(y)4/21/2024103Attention1.如果在參加歸結(jié)的子句內(nèi)部含有可合一的文字，則在進(jìn)行歸結(jié)之前應(yīng)對這些文字先進(jìn)行合一。2.對于謂詞邏輯，[定理4]仍然適用，即歸結(jié)式是它的親本子句的邏輯結(jié)論。用歸結(jié)式取代它在子句集S中的親本子句所得的新子句集仍然保持著原子句集S的不可滿足性。3.對于一階謂詞邏輯，從不可滿足的意義上說，歸結(jié)原理也是完備的。即若子句集是不可滿足的，則必然存在一個從該子句集到空子句的歸結(jié)演繹；若從子句集存在一個到空子句的演繹，則該子句集是不可滿足的。4/21/2024104歸結(jié)原理給出了證明子句集不可滿足性的方法。

?根據(jù)[定理1]：如欲證明Q為P1,P2,…Pn的邏輯推論，只需證明(P1

P2

…

Pn)

Q是不可滿足的。

?再根據(jù)[定理2]：公式(P1

P2

…

Pn)

Q的不可滿足性與其子句集的不可滿足性是等價的。因此我們可用歸結(jié)原理來進(jìn)行定理的自動證明。應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。設(shè)F為已知前提的公式集，Q為目標(biāo)公式（結(jié)論）。歸結(jié)反演4/21/2024105歸結(jié)反演證明用歸結(jié)反演證明Q為真的步驟是：

(1)

否定Q，得到

Q；(2)把

Q并入到公式集F中，得到{F,

Q}(3)

把公式集{F,

Q}化為子句集S;

(4)應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時就證明了Q為真。4/21/2024106例1：已知：F1:(

x)((N(x)

GZ(x)

I(x))自然數(shù)都是大于零的整數(shù)；F2:(

x)(I(x)

E(x)O(x))所有整數(shù)不是偶數(shù)就是奇數(shù)；F3:(

x)(E(x)

I(S(x)))偶數(shù)除以2是整數(shù)；求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證明：

?首先把要證明的問題用謂詞公式表達(dá)出來：G:(

x)(N(x)

O(x)

I(S(x)))

?把F1,F2,F3及G化成子句集：(1)

N(x)

GZ(x)(2)

N(u)

I(u)(3)

I(y)

E(y)

O(y)F2

(4)

E(z)

I(S(z))F3

(5)

N(t)(6)

O(t)

G(7)

I(S(t))F1對子句進(jìn)行歸結(jié)：(8)

I(y)

E(y)(3)與(6)歸結(jié){y/t}(9)

E(z)(4)與(7)歸結(jié){z/t}(10)

I(y)(8)與(9)歸結(jié){y/z}(11)

N(u)(2)與(10)歸結(jié){u/y}(12)NIL(5)與(11)歸結(jié){u/t}

所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)4/21/2024107上述過程可用如下歸結(jié)樹表示:

I(y)

E(y)

O(y)

O(t)

E(z)

I(S(z))

I(S(t))

I(y)

E(y)

E(z)

I(y)

N(u)

I(u)

N(u)N(t)NIL4/21/2024108例2：某公司招聘工作人員，A、B、C三人應(yīng)試，經(jīng)面試后公司表示如下想法：(1)三人中至少錄取一人；(2)如果錄取A而不錄取B,則一定錄取C;(3)如果錄取B，則一定錄取C;求證：公司一定錄取C。

證明:設(shè)用P(x)表示錄取x。

把公司的想法用謂詞公式表示如下：

F1:P(A)P(B)P(C)

F2:P(A)P(B)P(C)F3:P(B)P(C)

把要求證的問題否定，并用謂詞公式表示出來：

G:P(C)

把上述公式化成子句集：

(1)P(A)P(B)P(C)

(2)

P(A)P(B)P(C)(3)P(B)P(C)(4)P(C)應(yīng)用歸結(jié)原理進(jìn)行歸結(jié):(5)P(B)P(C)(1)與(2)歸結(jié)(6)P(C)(3)與(5)歸結(jié)(7)NIL(4)與6)歸結(jié)

公司一定錄取B。4/21/2024109上述歸結(jié)過程可用歸結(jié)樹表示:P(A)P(B)P(C)

P(A)P(B)P(C)P(B)P(C)P(B)P(C)P(C)P(C)NIL4/21/2024110歸結(jié)原理除了可用于定理證明外，還可用來求取問題的答案，其求解的步驟如下：

Ⅰ.把已知前提用謂詞公式表示出來，并且化為相應(yīng)的子句集，設(shè)該子句集的名字為S；Ⅱ.把待求解的問題也用謂詞公式表示出來，然后把它否定，并與謂詞ANSWER(一個為求解問題而專設(shè)的謂詞，其變元必須與問題公式的變元一致)構(gòu)成析?。虎?把此析取式化為子句集，并且把該子句集并入到子句集S中，得到子句集S’；Ⅳ.對S’應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)；Ⅴ.若得到歸結(jié)式ANSWER，則答案就ANSWER中。歸結(jié)反演求解4/21/2024111例1:已知：F1：王（Wang）先生是小李（Li）的老師；F2：小李與小張（Zhang）是同班同學(xué)；F3：如果x與y是同班同學(xué)，則x的老師也是y的老師。求：小張的老師是誰？解:首先定義謂詞：

T(x,y)：x是y的老師；C(x,y)：x與y是同班同學(xué)。把已知前提及待求解的問題表示成謂詞公式：

F1