第4章-確定性推理+修正版本丁世飛26273435

第4章確定性推理

智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。對于推理的這兩種不同類型，本章重點討論前一種，不確定性推理放到下一章討論。

4.1推理的基本概念4.2推理的邏輯基礎(chǔ)4.3自然演繹推理4.4歸結(jié)演繹推理4.1推理的基本概念4.1.1什么是推理4.1.2推理方法及其分類4.1.3推理的控制策略及其分類4.1.4正向推理4.1.5逆向推理4.1.6混合推理4.1.1什么是推理推理的概念是指按照某種策略從已知事實出發(fā)去推出結(jié)論的過程。推理所用的事實：初始證據(jù)：推理前用戶提供的中間結(jié)論：推理過程中所得到的推理過程：由推理機來完成，所謂推理機就是智能系統(tǒng)中用來實現(xiàn)推理的那些程序。例如，醫(yī)療專家系統(tǒng)，專家知識保存在知識庫中。推理開始時，先把病人的癥狀和檢查結(jié)果放到綜合數(shù)據(jù)庫中，然后再從綜合數(shù)據(jù)庫的初始證據(jù)出發(fā)，按照某種策略在知識庫中尋找，并使用知識，直到推出最終結(jié)論為止。推理的兩個基本問題推理的方法：解決前提和結(jié)論的邏輯關(guān)系，不確定性傳遞推理的控制策略：解決推理方向，沖突消解策略4.1.2推理方法及其分類

1.按推理的邏輯基礎(chǔ)分類(1/4)可分為演繹推理、歸納推理等

演繹推理

演繹推理是從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結(jié)論。是一種由一般到個別的推理方法，其核心是三段論，如假言推理、拒取式和假言三段論。

例：假言三段論

A→B，B→C?A→C

常用的三段論是由一個大前提、一個小前提和一個結(jié)論這三部分組成的。其中，大前提是已知的一般性知識或推理過程得到的判斷；小前提是關(guān)于某種具體情況或某個具體實例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。

例如，有如下三個判斷：①計算機系的學(xué)生都會編程序；（一般性知識）②程強是計算機系的一位學(xué)生；（具體情況）③程強會編程序。（結(jié)論）這是一個三段論推理。其中，①是大前提，②是小前提；③是經(jīng)演繹推出來的結(jié)論?？梢姡浣Y(jié)論是蘊含在大前提中的。4.1.2推理方法及其分類

1.按推理的邏輯基礎(chǔ)分類(2/4)歸納推理是一種由個別到一般的推理方法。歸納推理的類型按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理按照推理所使用的方法可分為枚舉、類比、統(tǒng)計和差異歸納推理等完全歸納推理是指在進行歸納時需要考察相應(yīng)事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。如，計算機質(zhì)量檢驗。不完全歸納推理是指在進行歸納時只考察了相應(yīng)事物的部分對象，就得出了關(guān)于該事物的結(jié)論。例如，計算機，隨機抽查。枚舉歸納推理是指在進行歸納時，如果已知某類事物的有限可數(shù)個具體事物都具有某種屬性，則可推出該類事物都具有此種屬性。例如，設(shè)有如下事例：王強是計算機系學(xué)生，他會編程序；高華是計算機系學(xué)生，她會編程序；

…………

當(dāng)這些具體事例足夠多時，就可歸納出一個一般性的知識：凡是計算機系的學(xué)生，就一定會編程序。4.1.2推理方法及其分類

1.按推理的邏輯基礎(chǔ)分類(3/4)類比歸納推理是指在兩個或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們在其他屬性上也相同或相似的一種歸納推理。設(shè)A、B分別是兩類事物的集合：

A={a1,a2,……}B={b1,b2,……}并設(shè)ai與bi總是成對出現(xiàn)，且當(dāng)ai有屬性P時，bi就有屬性Q與此對應(yīng)，即

P(ai)→Q(bi)i=1,2,…..

則當(dāng)A與B中有一新的元素對出現(xiàn)時，若已知a'有屬性P，b'有屬性Q，即

P(a')→Q(b')

類比歸納推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關(guān)程度。4.1.2推理方法及其分類

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

例如，一位計算機維修員，從書本知識，到通過大量實例積累經(jīng)驗，是一種歸納推理方式。運用這些一般性知識去維修計算機的過程則是演繹推理。

4.1.3推理的控制策略及其分類推理的控制策略推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達到目標(biāo)的策略?？刂撇呗缘姆诸愑捎谥悄芟到y(tǒng)的推理過程一般表現(xiàn)為一種搜索過程，因此，推理的控制策略又可分為推理策略和搜索策略。

推理策略主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等推理方向控制策略用于確定推理的控制方向，可分為正向推理、逆向推理、混合推理及雙向推理。求解策略是指僅求一個解，還是求所有解或最優(yōu)解等。限制策略是指對推理的深度、寬度、時間、空間等進行的限制。沖突消解策略是指當(dāng)推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。搜索策略主要解決推理線路、推理效果、推理效率等問題。本章主要討論推理策略，至于搜索策略將放到第3章單獨討論。4.1.4正向推理

推理算法

從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅(qū)動推理或前向鏈推理。算法描述

(1)把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫；

(2)檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若已包含，則求解結(jié)束，并成功推出；否則執(zhí)行下一步；

(3)檢查知識庫中是否有可用知識，若有，形成當(dāng)前可用知識集，執(zhí)行下一步；否則轉(zhuǎn)(5)。

(4)按照某種沖突消解策略，從當(dāng)前可用知識集中選出一條規(guī)則進行推理，并將推出的新事實加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)(2)。

(5)詢問用戶是否可以進一步補充新的事實，若可補充，則將補充的新事實加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)(3)；否則表示無解，失敗退出。至于如何根據(jù)綜合數(shù)據(jù)庫中的事實到知識庫中選取可用知識，當(dāng)知識庫中有多條知識可用時應(yīng)該先使用哪一條知識等。這些問題涉及到了知識的匹配方法和沖突消解策略，以后將會分別討論。其流程圖如下：把初始證據(jù)放入DBDB中有解嗎？KB中有可用知識嗎？

形成可用知識集可用知識集空嗎？按照沖突消解策略從該知識集中選出一條知識進行推理

推出的是新事實嗎？

將新事實加入到DB把用戶補充的新事實加入到DB中

用戶可補充新事實嗎？

失敗退出

成功退出YNNYNNNYYY4.1.4正向推理

推理例子

例4.1請用正向推理完成以下問題的求解假設(shè)知識庫中包含有以下2條規(guī)則：

r1：IFBTHENCr2：IFATHENB已知初始證據(jù)A，求證目標(biāo)C。解：本例的推理過程如下：推理開始前，綜合數(shù)據(jù)庫為空。推理開始后，先把A放入綜合數(shù)據(jù)庫，然后檢查綜合數(shù)據(jù)庫中是否含有該問題的解，回答為“N”。接著檢查知識庫中是否有可用知識，顯然r2可用，形成僅含r2的知識集。從該知識集中取出r2，推出新的實事B，將B加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標(biāo)C，回答為“N”。再檢查知識庫中是否有可用知識，此時由于B的加入使得r1為可用，形成僅含r1的知識集。從該知識集中取出r1，推出新的實事C，將C加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標(biāo)C，回答為“Y”。它說明綜合數(shù)據(jù)庫中已經(jīng)含有問題的解，推理成功結(jié)束，目標(biāo)C得證。4.1.4正向推理

優(yōu)缺點正向推理的主要優(yōu)點比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設(shè)計、預(yù)測、監(jiān)控等領(lǐng)域的問題求解。正向推理的主要缺點推理無明確目標(biāo)，求解問題是可能會執(zhí)行許多與解無關(guān)的操作，導(dǎo)致推理效率較低。

4.1.5逆向推理

推理算法

從某個假設(shè)目標(biāo)出發(fā)，逆向使用規(guī)則，亦稱為目標(biāo)驅(qū)動推理或逆向鏈推理。算法描述：

(1)將要求證的目標(biāo)（稱為假設(shè)）構(gòu)成一個假設(shè)集；

(2)從假設(shè)集中選出一個假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫中，若在，則該假設(shè)成立，此時，若假設(shè)集為空，則成功退出，否則仍執(zhí)行(2)；若該假設(shè)不在數(shù)據(jù)庫中，則執(zhí)行下一步；

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

(4)將知識庫中可以導(dǎo)出該假設(shè)的所有知識構(gòu)成一個可用知識集；

(5)檢查可用知識集是否為空，若是，失敗退出；否則執(zhí)行下一步；

(6)按沖突消解策略從可用知識集中取出一個知識，繼續(xù)；

(7)將該知識的前提中的每個子條件都作為新的假設(shè)放入假設(shè)集，然后轉(zhuǎn)(2)。

其流程圖如下：初始化DB和假設(shè)集該假設(shè)是DB中的事實嗎？該假設(shè)能被KB中的知識導(dǎo)出嗎？從假設(shè)集中取出一個假設(shè)可用知識集空嗎？按照沖突消解策略從該知識集中選出一條知識將該知識前提中的每個子條件作為新的假設(shè)加入假設(shè)集該假設(shè)成立并放入DB還有新的假設(shè)嗎？失敗退出成功退出YNYYNNNNY將KB中所有能導(dǎo)出此假設(shè)的知識構(gòu)成一個可用知識集

詢問用戶有此事實嗎？該假設(shè)

成立Y4.1.5逆向推理

推理例子對上例，采用逆向推理，其推理過程如下：推理開始前，綜合數(shù)據(jù)庫和假設(shè)集均為空。推理開始后，先將初始證據(jù)A和目標(biāo)C分別放入綜合數(shù)據(jù)庫和假設(shè)集，然后從假設(shè)集中取出一個假設(shè)C，查找C是否為綜合數(shù)據(jù)庫中的已知事實，回答為“N”。再檢查C是否能被知識庫中的知識所導(dǎo)出，發(fā)現(xiàn)C可由r1導(dǎo)出，于是r1被放入可用知識集。由于知識庫中只有r1可用，故可用知識集中僅含r1。接著從可用知識集中取出r1，將其前提條件B作為新的假設(shè)放入假設(shè)集。從假設(shè)集中取出B，檢查B是否為綜合數(shù)據(jù)庫中的實事，回答為“N”。再檢查B是否能被知識庫中的知識所導(dǎo)出，發(fā)現(xiàn)B可由r2導(dǎo)出，于是r2被放入可用知識集。由于知識庫中只有r2可用，故可用知識集中僅含r2。從可用知識集中取出r2，將其前提條件A作為新的假設(shè)放入假設(shè)集。然后從假設(shè)集中取出A，檢查A是否為綜合數(shù)據(jù)庫中的實事，回答為“Y”。他說明該假設(shè)成立，由于無新的假設(shè)，故推理過程成功結(jié)束，于是目標(biāo)C得證。

4.1.5逆向推理

優(yōu)缺點逆向推理的主要優(yōu)點不必尋找和使用那些與假設(shè)目標(biāo)無關(guān)的信息和知識推理過程的目標(biāo)明確也有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。逆向推理的主要缺點當(dāng)用戶對解的情況認(rèn)識不請時，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會影響系統(tǒng)效率。4.1.6混合推理混合推理的概念把正向推理和逆向推理結(jié)合起來所進行的推理稱為混合推理。是一種解決較復(fù)雜問題的方法?；旌贤评淼姆椒?/p>

1.先正向后逆向這種方法先進行正向推理，從已知事實出發(fā)推出部分結(jié)果，然后再用逆向推理對這些結(jié)果進行證實或提高它們的可信度。

2.先逆向后正向這種方法先進行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正向推理對這些中間假設(shè)進行證實。

3.雙向混合是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結(jié)合起來。對于這些方法不再詳細討論。第4章確定性推理

4.1推理的基本概念4.2推理的邏輯基礎(chǔ)4.3自然演繹推理4.4歸結(jié)演繹推理4.2推理的邏輯基礎(chǔ)4.2.1謂詞公式的解釋4.2.2謂詞公式的永真性和可滿足性4.2.3謂詞公式的等價性和永真蘊含性4.2.4謂詞公式的范式4.2.5置換與合一4.2.1謂詞公式的解釋

概念命題公式的解釋在命題邏輯中，命題公式的一個解釋就是對該命題公式中各個命題變元的一次真值指派。有了命題公式的解釋，就可據(jù)此求出該命題公式的真值。謂詞公式的解釋由于謂詞公式中可能包含由個體常量、變元或函數(shù)，因此，必須先考慮這些個體常量和函數(shù)在個體域上的取值，然后才能根據(jù)它們的具體取值為謂詞分別指派真值。定義4.1

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

(1)為每個個體常量指派D中的一個元素；

(2)為每個n元函數(shù)指派一個從Dn到D的一個映射，其中

Dn={(x1,x2,…,xn)|x1,x2,…,xn∈D}(3)為每個n元謂詞指派一個從Dn到{F，T}的映射。則稱這些指派為P在D上的一個解釋I

4.2.1謂詞公式的解釋

例子一(1/2)

例4.2

設(shè)個體域D={1,2}，求公式A=(?x)(y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。

解：由于公式A中沒有包含個體常量和函數(shù)，故可直接為謂詞指派真值，設(shè)有這就是公式A在D上的一個解釋。從這個解釋可以看出：當(dāng)x=1、y=1時，有P(x,y)的真值為T;

當(dāng)x=2、y=1時，有P(x,y)的真值為T;

即對x在D上的任意取值，都存在y=1使P(x,y)的真值為T。因此，在此解釋下公式A的真值為T。

P(1,1)

P(1,2)

P(2,1)P(2,2)

TFTF4.2.1謂詞公式的解釋

例子一(2/2)說明：一個謂詞公式在其個體域上的解釋不是唯一的。例如，對公式A，若給出另一組真值指派這也是公式A在D上的一個解釋。從這個解釋可以看出：當(dāng)x=1、y=1時，有P(x,y)的真值為T;

當(dāng)x=2、y=1時，有P(x,y)的真值為F;即對x在D上的任意取值，不存在一個y使得P(x,y)的真值為T。因此，在此解釋下公式A的真值為F。實際上，A在D上共有16種解釋，這里就不在一一列舉。

P(1,1)

P(1,2)

P(2,1)P(2,2)

TTFF4.2.1謂詞公式的解釋

例子二

例4.3

設(shè)個體域D={1,2}，求公式B=(?x)P(f(x),a)在D上的解釋，并指出在該解釋下公式B的真值。

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

當(dāng)x=2時，a=1

使P(2,1)=T即對x在D上的任意取值，都存在a=1使P(f(x),a)的真值為T。因此，在此解釋下公式B的真值為T。由上面的例子可以看出，謂詞公式的真值都是針對某一個解釋而言的，它可能在某一個解釋下真值為T，而在另一個解釋下為F。af(1)F(2)112P(1,1))P(1,2)P(2,1)P(2,2)T×T×4.2.2謂詞公式的永真性和可滿足性

為了以后推理的需要，下面先定義：定義4.2

如果謂詞公式P對非空個體域D上的任一解釋都取得真值T，則稱P在D上是永真的；如果P在任何非空個體域上均是永真的，則稱P永真?？梢姡卸ㄒ恢^詞公式為永真，必須對每個非空個體域上的每個解釋逐一進行判斷。當(dāng)解釋的個數(shù)為有限時，盡管工作量大，公式的永真性畢竟還可以判定，但當(dāng)解釋個數(shù)為無限時，其永真性就很難判定了。定義4.3

對于謂詞公式P，如果至少存在D上的一個解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。謂詞公式的可滿足性也稱為相容性。定義4.4

如果謂詞公式P對非空個體域D上的任一解釋都取真值F，則稱P在D上是永假的；如果P在任何非空個體域上均是永假的，則稱P永假。謂詞公式的永假性又稱不可滿足性或不相容。后面我們要給出的歸結(jié)推理，就是采用一種邏輯上的反證法，將永真性轉(zhuǎn)換為不可滿足性的證明。4.2.3謂詞公式的等價性和永真蘊含性

1.等價式(1/2)

謂詞公式的等價性和永真蘊含性可分別用相應(yīng)的等價式和永真蘊含式來表示，這些等價式和永真蘊含式都是演繹推理的主要依據(jù)，因此也稱它們?yōu)橥评硪?guī)則。謂詞公式的等價式可定義如下：

定義4.5

設(shè)P與Q是D上的兩個謂詞公式，若對D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D上是等價的。如果D是任意非空個體域，則稱P與Q是等價的，記作P?Q。

4.2.3謂詞公式的等價性和永真蘊含性

1.等價式(2/2)(1)雙重否定律??P?P(2)交換律(P∨Q)?(Q∨P)，(P∧Q)?(Q∧P)(3)結(jié)合律(P∨Q)∨R?P∨(Q∨R)(P∧Q)∧R?P∧(Q∧R)(4)分配律P∨(Q∧R)?(P∨Q)∧(P∨R)P∧(Q∨R)?(P∧Q)∨(P∧R)(5)摩根定律?(P∨Q)??P∧?Q?(P∧Q)??P∨?Q(6)吸收律P∨(P∧Q)?PP∧(P∨Q)?P(7)補余律P∨?P?T,P∧?P?F(8)連詞化歸律P→Q??P∨QP?Q?(P→Q)∧(Q→P)P?Q?(P∧Q)∨(?P∧?Q)(9)量詞轉(zhuǎn)換律?(?x)P?(?x)(?P)?(?x)P?(?x)(?P)(10)量詞分配律(?x)(P∧Q)?(?x)P∧(?x)Q(?x)(P∨Q)?(?x)P∨(?x)Q4.2.3謂詞公式的等價性和永真蘊含性

2.永真蘊含式

定義4.6

對謂詞公式P和Q，如果P→Q永真，則稱P永真蘊含Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作P?Q。常用的永真蘊含式如下：

(1)化簡式P∧Q?P，P∧Q?Q(2)附加式P?P∨Q，Q?P∨Q(3)析取三段論﹁P,P∨Q?Q(4)假言推理P,P→Q?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是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。

(9)存在固化(?x)P(x)?P(y)

其中，y是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公式中的存在量詞。4.2.4謂詞公式的范式

范式是謂詞公式的標(biāo)準(zhǔn)形式。在謂詞邏輯中，范式分為兩種：前束范式

定義4.7

設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，且它們的轄域為整個公式，則稱F為前束范式。一般形式：

(Q1x1)……(Qnxn)M(x1,x2,……,xn)其中，Qi(i=1,2,……,n)為前綴，它是一個由全稱量詞或存在量詞組成的量詞串；M(x1,x2,……,xn)為母式，它是一個不含任何量詞的謂詞公式。

例如，(?x)(?y)(?z)(P(x)∧Q(y,z)∨R(x,z))是前束范式。任一謂詞公式均可化為與其對應(yīng)的前束范式，其化簡方法將在后面子句集的化簡中討論。Skolem范式

定義4.8

如果前束范式中所有的存在量詞都在全稱量詞之前，則稱這種形式的謂詞公式為Skolem范式。

例如，(?x)(?z)(?y)(P(x)∨Q(y,z)∧R(x,z))是Skolem范式。任一謂詞公式均可化為與其對應(yīng)的Skolem范式，其化簡方法也將在后面子句集的化簡中討論。4.2.5置換與合一

概念

在不同謂詞公式中，往往會出現(xiàn)謂詞名相同但其個體不同的情況，此時推理過程是不能直接進行匹配的，需要先進行置換。例如，可根據(jù)全稱固化推理和假言推理由謂詞公式

W1(A)和(?x)(W1(x)→W2(x))推出W2(A)。對謂詞W1(A)可看作是由全程固化推理（即(?x)(W1(x)?W1(A))推出的，其中A是任一個體常量。要使用假言推理，首先需要找到項A對變元x的置換，使W1(A)與W1(x)一致。這種尋找項對變元的置換，使謂詞一致的過程叫做合一的過程。下面討論置換與合一的有關(guān)概念與方法。4.2.5置換與合一

1.置換(1/2)

置換可簡單的理解為是在一個謂詞公式中用置換項去替換變量。定義4.9

置換是形如

{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，t1,t2,…,tn是項；x1,x2,…,xn是互不相同的變元；ti/xi表示用ti替換xi。并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個ti中。例如，{a/x,c/y,f(b)/z}是一個置換。但{g(y)/x,f(x)/y}不是一個置換。原因是它在x與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當(dāng)用g(y)置換x,用f(g(y))置換y時，既沒有消去x，也沒有消去y。若改為{g(a)/x,f(x)/y}即可，原因是用g(a)置換x，用f(g(a))置換y，則消去了x和y。通常，置換是用希臘字母θ、σ、α、λ等來表示的。定義4.10

設(shè)θ={t1/x1,t2/x2,…,tn/xn}是一個置換，F(xiàn)是一個謂詞公式，把公式F中出現(xiàn)的所有xi換成ti(i=1,2,…,n)，得到一個新的公式G，稱G為F在置換θ下的例示，記作G=Fθ。一個謂詞公式的任何例示都是該公式的邏輯結(jié)論。4.2.5置換與合一

1.置換(2/2)定義4.11

設(shè)

θ={t1/x1,t2/x2,…,tn/xn}λ={u1/y1,u2/y2,…,um/ym}是兩個置換。則θ與λ的合成也是一個置換，記作θ°λ。它是從集合

{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym}中刪去以下兩種元素①當(dāng)tiλ=xi時，刪去tiλ/xi(i=1,2,…,n)；②當(dāng)yj∈{x1,x2,…,xn}時，刪去uj/yj(j=1,2,…,m)最后剩下的元素所構(gòu)成的集合。例4.4

設(shè)θ={f(y)/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滿足定義中的條件①，需要刪除；a/x和b/y滿足定義中的條件②，也需要刪除。最后得

θ°λ={f(b)/x,y/z}4.2.5置換與合一

2.合一

合一可理解為是尋找項對變量的置換，使兩個謂詞公式一致?？啥x為：定義4.12

設(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.13

設(shè)σ是公式集F的一個合一，如果對F的任一個合一θ都存在一個置換λ，使得θ=σ°λ，則稱σ是一個最一般合一。一個公式集的最一般合一是唯一的。對如何求取最一般合一的問題，不再討論。第4章確定性推理

4.1推理的基本概念4.2推理的邏輯基礎(chǔ)4.3自然演繹推理4.4歸結(jié)演繹推理4.3自然演繹推理

自然演繹推理

從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。自然演繹推理最基本的推理規(guī)則是三段論推理，它包括：假言推理

P,P→Q?Q

拒取式

﹁

Q,P→Q?﹁P

假言三段論

P→Q,Q→R?P→R

自然演繹推理的例子例4.5

設(shè)已知如下事實：

A,B,A→C,B∧C→D,D→Q

求證：Q為真。證明：因為A,A→C?C假言推理

B,C?B∧C引入合取詞

B∧C，B∧C→D?D假言推理

D,D→Q?Q假言推理因此，Q為真4.3自然演繹推理

例4.6

設(shè)已知如下事實：

(1)只要是需要編程序的課，王程都喜歡。

(2)所有的程序設(shè)計語言課都是需要編程序的課。

(3)C是一門程序設(shè)計語言課。求證：王程喜歡C這門課。證明：首先定義謂詞

Prog(x)x是需要編程序的課。

Like(x,y)x喜歡y。

Lang(x)x是一門程序設(shè)計語言課把已知事實及待求解問題用謂詞公式表示如下：

Prog(x)→Like(Wang,x)(?x)(Lang(x)→Prog(x))Lang(C)應(yīng)用推理規(guī)則進行推理：

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這門課。4.3自然演繹推理

優(yōu)點：定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。缺點：是容易產(chǎn)生知識爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復(fù)雜問題的推理不利，甚至難以實現(xiàn)。

第4章確定性推理

4.1推理的基本概念4.2推理的邏輯基礎(chǔ)4.3自然演繹推理4.4歸結(jié)演繹推理4.4歸結(jié)演繹推理

歸結(jié)演繹推理是一種基于魯賓遜（Robinson）歸結(jié)原理的機器推理技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法”。在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)，就是要對前提P和結(jié)論Q，證明P→Q永真。由4.2節(jié)可知，要證明P→Q永真，就是要證明P→Q在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。為此，人們進行了大量的探索，后來發(fā)現(xiàn)可以采用反證法的思想，把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。即要證明P→Q永真，只要能夠證明P∧﹁Q是不可滿足的就可以了(原因是﹁(P→Q)?﹁(﹁P∨Q)?P∧﹁Q

。這方面最有成效的工作就是魯賓遜歸結(jié)原理。它使定理證明的機械化成為現(xiàn)實。4.4歸結(jié)演繹推理4.4.1子句集及其化簡4.4.2魯濱遜歸結(jié)原理4.4.3歸結(jié)反演推理的歸結(jié)策略4.4.4用歸結(jié)反演求取問題的答案4.4.1子句集及其化簡

1.子句和子句集

魯濱遜歸結(jié)原理是在子句集的基礎(chǔ)上討論問題的。因此，討論歸結(jié)演繹推理之前，需要先討論子句集的有關(guān)概念。子句和子句集定義4.14

原子謂詞公式及其否定統(tǒng)稱為文字。例如，P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。定義4.15

任何文字的析取式稱為子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。定義4.16

不含任何文字的子句稱為空子句。由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的。空子句一般被記為□或NIL。定義4.17

由子句或空子句所構(gòu)成的集合稱為子句集。4.4.1子句集及其化簡

2.子句集的化簡（1/6）

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

(1)消去連接詞“→”和“?”反復(fù)使用如下等價公式：

P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。例如公式

(?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.4.1子句集及其化簡

2.子句集的化簡（2/6）(2)減少否定符號的轄域反復(fù)使用雙重否定率

﹁(﹁P)?P摩根定律

﹁(P∧Q)?﹁P∨﹁Q﹁(P∨Q)?﹁P∧﹁Q量詞轉(zhuǎn)換率

﹁(?x)P(x)?(?x)﹁P(x)﹁(?x)P(x)?(?x)￢P(x)將每個否定符號“﹁”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。例如，上式經(jīng)等價變換后為

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y)))4.4.1子句集及其化簡

2.子句集的化簡（3/6）

(3)對變元標(biāo)準(zhǔn)化在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。例如，上式經(jīng)變換后為

(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))(4)化為前束范式化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進行了標(biāo)準(zhǔn)化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種移動是可行的。例如，上式化為前束范式后為

(?x)(?y)(?z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))4.4.1子句集及其化簡

2.子句集的化簡（4/6）

(5)消去存在量詞消去存在量詞時，需要區(qū)分以下兩種情況：

若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。

若存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如

(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。例如，上步所得公式中存在量詞(?y)和(?z)都位于(?x)的轄域內(nèi)，因此都需要用Skolem函數(shù)來替換。設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為

(?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))4.4.1子句集及其化簡

2.子句集的化簡（5/6）(6)化為Skolem標(biāo)準(zhǔn)形

Skolem標(biāo)準(zhǔn)形的一般形式為

(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標(biāo)準(zhǔn)形的母式，它由子句的合取所構(gòu)成。把謂詞公式化為Skolem標(biāo)準(zhǔn)形需要使用以下等價關(guān)系

P∨(Q∧R)?(P∨Q)∧(P∨R)例如，前面的公式化為Skolem標(biāo)準(zhǔn)形后為

(?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))(7)消去全稱量詞由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。例如，上式消去全稱量詞后為

(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))4.4.1子句集及其化簡

2.子句集的化簡（6/6）(8)消去合取詞在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。例如，上式的子句集中包含以下兩個子句

﹁P(x,f(x))∨Q(x,g(x))﹁P(x,f(x))∨﹁R(x,g(x))(9)更換變量名稱對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關(guān)系。這樣，更換變量名是不會影響公式的真值的。例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集

﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))4.4.1子句集及其化簡

3.子句集的應(yīng)用（1/4）

在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不唯一的。這樣，當(dāng)原謂詞公式為非永假時，它與其標(biāo)準(zhǔn)子句集并不等價。但當(dāng)原謂詞公式為永假（或不可滿足）時，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。這個結(jié)論很重要，是歸結(jié)原理的主要依據(jù)，可用定理的形式來描述。定理4.1

設(shè)有謂詞公式F，其標(biāo)準(zhǔn)子句集為S，則F為不可滿足的充要條件是S為不可滿足的。為證明此定理，先作如下說明：為討論問題方便，設(shè)給定的謂詞公式F已為前束形

(Q1x1)…(Qrxr)…(Qnxn)M(x1,x2,…,xn)其中，M(x1,x2,…,xn)已化為合取范式。由于將F化為這種前束形是一種很容易實現(xiàn)的等價運算，因此這種假設(shè)是可以的。4.4.1子句集及其化簡

3.子句集的應(yīng)用（2/4）

又設(shè)(Qrxr)是第一個出現(xiàn)的存在量詞(?xr)，即F為

F=(x1)…(xr-1)(?xr)(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,xr,xr+1…,xn)為把F化為Skolem形，需要先消去這個(?xr)，并引入Skolem函數(shù)，得到

F1=(x1)…(xr-1)(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…xr-1),xr+1…,xn)

若能證明

F不可滿足?F1不可滿足則同理可證

F1不可滿足?F2不可滿足重復(fù)這一過程，直到證明了

Fm-1不可滿足?Fm不可滿足為止。此時，F(xiàn)m已為F的Skolem標(biāo)準(zhǔn)形。而S只不過是Fm的一種集合表示形式。因此有

Fm不可滿足?S不可滿足下面開始用反證法證明

F不可滿足?F1不可滿足4.4.1子句集及其化簡

3.子句集的應(yīng)用（3/4）先證明?已知F不可滿足，假設(shè)F1是可滿足的，則存在一個解釋I，使F1在解釋I下為真。即對任意x1,…,xr-1在I的設(shè)定下有

(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…,xr-1),xr+1…,xn)為真。亦即對任意的x1,…,xr-1都有一個f(x1,…,xr-1)使

(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…,xr-1),xr+1…,xn)為真。即在I下有

(?x1)…(?xr-1)(?xr)(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,xr,xr+1…,xn)為真。即F在I下為真。但這與前提F是不可滿足的相矛盾，即假設(shè)F1為可滿足是錯誤的。從而可以得出“若F不可滿足，則必有F1不可滿足”。4.4.1子句集及其化簡

3.子句集的應(yīng)用（4/4）再證明已知F1不可滿足，假設(shè)F是可滿足的。于是便有某個解釋I使F在I下為真。即對任意的x1,…,xr-1在I的設(shè)定下都可找到一個xr使

(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,xr,xr+1…,xn)為真。若擴充I，使它包含一個函數(shù)f(x1,…,xr-1)，且有

xr=f(x1,…,xr-1)這樣，就可以把所有的(f(x1,…,xr-1)映射到xr，從而得到一個新的解釋I’，并且在此解釋下對任意的x1,…,xr-1都有

(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…xr-1),xr+1…,xn)為真。即在I’下有

(?x1)…(?xr-1)(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…xr-1),xr+1…,xn)為真。它說明F1在解釋I’下為真。但這與前提F1是不可滿足的相矛盾，即假設(shè)F為可滿足是錯誤的。從而可以得出“若F1不可滿足，則必有F不可滿足”于是，定理得證。由此定理可知，要證明一個謂詞公式是不可滿足的，只要證明其相應(yīng)的標(biāo)準(zhǔn)子句集是不可滿足的就可以了。至于如何證明一個子句集的不可滿足性，由下面的海伯倫理論和魯賓遜歸結(jié)原理來解決。

4.4.2魯濱遜歸結(jié)原理

1.基本思想

注意以下兩個關(guān)鍵第一，子句集中的子句之間是合取關(guān)系。因此，子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的；第二，空子句是不可滿足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。魯濱遜歸結(jié)原理基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴充的子句集S'。然后設(shè)法檢驗子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。魯濱遜歸結(jié)原理包括命題邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（1/8）

歸結(jié)推理的核心是求兩個子句的歸結(jié)式

(1)歸結(jié)式的定義及性質(zhì)定義4.18

若P是原子謂詞公式，則稱P與﹁P為互補文字。定義4.19

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

例4.7

設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的歸結(jié)式C12。

解：這里L(fēng)1=P，L2=﹁P，通過歸結(jié)可以得到

C12=Q∨R∨S

例4.8

設(shè)C1=﹁Q，C2=Q，求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=﹁Q，L2=Q，通過歸結(jié)可以得到

C12=NIL4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（2/8）

例4.9

設(shè)C1=﹁P∨Q

，C2=﹁Q，C3=P，求C1、C2、C3的歸結(jié)式C123。解：若先對C1、C2歸結(jié)，可得到

C12=﹁P然后再對C12和C3歸結(jié)，得到

C123=NIL

如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過程是不唯一的。其歸結(jié)歸結(jié)過程可用右圖來表示，該樹稱為歸結(jié)樹。﹁P∨Q﹁Q﹁PPNIL﹁P∨QPQ﹁QNIL4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（3/8）

定理4.2

歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。證明：（按定義）設(shè)C1=L∨C1’，C2=﹁L∨C2’關(guān)于解釋I為真，則只需證明C12=C1’∨C2’關(guān)于解釋I也為真。對于解釋I，L和﹁L中必有一個為假。

若L為假，則必有C1'為真，不然就會使C1為假，這將與前提假設(shè)C1為真矛盾，因此只能有C1'為真。同理，若﹁L為假，則必有C2'為真。因此，必有C12=C1'∨C2'關(guān)于解釋I也為真。即C12是C1和C2的邏輯結(jié)論。4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（4/8）

上述定理是歸結(jié)原理中的一個重要定理，由它可得到以下兩個推論：

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

S1的不可滿足性?S的不可滿足性

證明：設(shè)S={C1，C2，C3，……，Cn}，C12是C1和C2的歸結(jié)式，則用C12代替C1和C2后可得到一個新的子句集

S1={C12，C3，…,Cn}設(shè)S1是不可滿足的，則對不滿足S1的任一解釋I，都可能有以下兩種情況：①解釋I使C12為真，則C3，……，Cn中必有一個為假，即S是不可滿足的。②解釋I使C12為假，即﹁C12為真，根據(jù)定理3.2有﹁(C1∧C2)永真，即﹁C1∨﹁C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。因此可以得出

S1的不可滿足性?S的不可滿足性4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（5/8）

推論2：設(shè)C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結(jié)式，若把C12加入S中得到新的子句集S2，則S與S2的不可滿足性是等價的。即：

S2的不可滿足性?S的不可滿足性先證明設(shè)S={C1，C2，C3，…，Cn}是不可滿足的，則C1，C2，C3，…，Cn中必有一子句為假，因而S2={C12，C1，C2，C3，……，Cn}必為不可滿足。再證明?設(shè)S2是不可滿足的,則對不滿足S2的任一解釋I,都可能有以下兩種情況：①解釋I使C12為真，則C1，C2，C3，…，Cn中必有一個為假，即S是不可滿足的。②解釋I使C12為假，即﹁C12為真，根據(jù)定理3.2有﹁(C1∧C2)永真，即﹁C1∨﹁C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。由此可見S與S2的不可滿足性是等價的。即

S的不可滿足性?S2的不可滿足性4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（6/8）

上述兩個推論說明，為證明子句集S的不可滿足性，只要對其中可進行歸結(jié)的子句進行歸結(jié)，并把歸結(jié)式加入到子句集S中，或者用歸結(jié)式代替他的親本子句，然后對新的子句集證明其不可滿足性就可以了。如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集S是不可滿足的結(jié)論。在命題邏輯中，對不可滿足的子句集S，其歸結(jié)原理是完備的。這種不可滿足性可用如下定理描述：定理4.3

子句集S是不可滿足的，當(dāng)且僅當(dāng)存在一個從S到空子句的歸結(jié)過程。

4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（7/8）(2)命題邏輯的歸結(jié)反演歸結(jié)原理：假設(shè)F為已知前提，G為欲證明的結(jié)論，歸結(jié)原理把證明G為F的邏輯結(jié)論轉(zhuǎn)化為證明F∧﹁G為不可滿足。再根據(jù)定理3.1，在不可滿足的意義上，公式集F∧﹁G與其子句集是等價的，即把公式集上的不可滿足轉(zhuǎn)化為子句集上的不可滿足。應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。在命題邏輯中，已知F，證明G為真的歸結(jié)反演過程如下：①否定目標(biāo)公式G，得﹁G;②把﹁G并入到公式集F中，得到{F，﹁G}；③把{F，﹁G}化為子句集S。④應(yīng)用歸結(jié)原理對子句集S中的子句進行歸結(jié)，并把每次得到的歸結(jié)式并入S中。如此反復(fù)進行，若出現(xiàn)空子句，則停止歸結(jié)，此時就證明了G為真。4.4.2魯濱遜歸結(jié)原理

2.命題邏輯的歸結(jié)（8/8）

例4.10

設(shè)已知的公式集為{P,(P∧Q)→R,(S∨T)→Q,T}，求證結(jié)論R。解：假設(shè)結(jié)論R為假,將﹁R加入公式集，并化為子句集

S={P,﹁P∨﹁Q∨R,﹁S∨Q,﹁T∨Q,T,﹁R}

其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。該樹根為空子句。其含義為：先假設(shè)子句集S中的所有子句均為真，即原公式集為真,﹁R也為真；然后利用歸結(jié)原理，對子句集進行歸結(jié)，并把所得的歸結(jié)式并入子句集中；重復(fù)這一過程，最后歸結(jié)出了空子句。根據(jù)歸結(jié)原理的完備性，可知子句集S是不可滿足的，即開始時假設(shè)﹁R為真是錯誤的，這就證明了R為真。

﹁P∨﹁Q∨R﹁R﹁P∨﹁QP﹁Q﹁T∨Q﹁TTNIL4.4.2魯濱遜歸結(jié)原理

3.謂詞邏輯的歸結(jié)（1/16）

在謂詞邏輯中，由于子句集中的謂詞一般都含有變元，因此不能象命題邏輯那樣直接消去互補文字。而需要先用一個最一般合一對變元進行代換，然后才能進行歸結(jié)。可見，謂詞邏輯的歸結(jié)要比命題邏輯的歸結(jié)麻煩一些。謂詞邏輯的歸結(jié)原理謂詞邏輯中的歸結(jié)式可用如下定義來描述：定義4.20

設(shè)C1和C2是兩個沒有公共變元的子句，L1和L2分別是C1和C2中的文字。如果L1和L2存在最一般合一σ，則稱

C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})為C1和C2的二元歸結(jié)式，而L1和L2為歸結(jié)式上的文字。4.4.2魯濱遜歸結(jié)原理

3.謂詞邏輯的歸結(jié)（2/16）

例4.11

設(shè)C1=P(a)∨R(x)，C2=﹁P(y)∨Q(b)，求C12

解：取L1=P(a),L2=﹁P(y)，則L1和L2的最一般合一是σ={a/y}。根據(jù)定義3.20,可得

C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})=({P(a),R(x)}-{P(a)})∪({﹁P(a),Q(b)}-{﹁P(a)})=({R(x)})∪({Q(b)})={R(x),Q(b)}=R(x)∨Q(b)

例4.12

設(shè)C1=P(x)∨Q(a)，C2=﹁P(b)∨R(x)，求C12

解：由于C1和C2有相同的變元x，不符合定義3.20的要求。為了進行歸結(jié)，需要修改C2中變元x的名字為，令C2=﹁P(b)∨R(y)。此時L1=P(x),L2=﹁P(b)，L1和L2的最一般合一是σ={b/x}。則有

C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})=({P(b),Q(a)}-{P(b)})∪({﹁P(b),R(y)}-{﹁P(b)})=({Q(a)})∪({R(y)})={Q(a),R(y)}=Q(a)∨R(y)4.4.2魯濱遜歸結(jié)原理

3.謂詞邏輯的歸結(jié)（3/16）

對以上討論做以下兩點說明:

(1)

這里之所以使用集合符號和集合的運算，目的是為了說明問題的方便。即先將子句Ciσ和Liσ寫成集合的形式，在集合表示下做減法和并集運算，然后再寫成子句集的形式。

(2)

定義中還要求C1和C2無公共變元，這也是合理的。例如C1=P(x)，C2=﹁P(f(x))，而S={C1,C2}是不可滿足的。但由于C1和C2的變元相同，就無法合一了。沒有歸結(jié)式，就不能用歸結(jié)法證明S的不可滿足性，這就限制了歸結(jié)法的使用范圍。如果對C1或C2的變元進行換名，便可通過合一，對C1和C2進行歸結(jié)。如上例，若先對C2進行換名，即C2=﹁P(f(y))，則可對C1和C2進行歸結(jié)，得到一個空子句，從而證明了S是不可滿足的。事實上，在由公式集化為子句集的過程中，其最后一步就是做換名處理。因此，定義中假設(shè)C1和C2沒有相同變元是可以的。4.4.2魯濱遜歸結(jié)原理

3.謂詞邏輯的歸結(jié)（4/16）

例4.13

設(shè)C1=P(x)∨﹁Q(b)，C2=﹁P(a)∨Q(y)∨R(z)

解：對C1和C2通過最一般合一（σ={a/x,b/y}）的作用，可以得到兩個互補對。注意：求歸結(jié)式不能同時消去兩個互補對，這樣的結(jié)果不是二元歸結(jié)式。如在σ={a/x,b/y}下，若同時消去兩個互補對，所得的R(z)不是C1和C2的二元歸結(jié)式。例4.14

設(shè)C1=P(x)∨P(f(a))∨Q(x)，C2=﹁P(y)∨R(b)，求C12

解：對參加歸結(jié)的某個子句，若其內(nèi)部有可合一的文字，則在進行歸結(jié)之前應(yīng)先對這些文字進行合一。本例的C1中有可合一的文字P(x)與P(f(a))，若用它們的最一般合一σ={f(a)/x}進行代換，可得到

C1σ=P(f(a))∨Q(f(a))此時可對C1σ與C2進行歸結(jié)。選L1=P(f(a)),L2=﹁P(y)，L1和L2的最一般合一是σ={f(a)/y}，則可得到C1和C2的二元歸結(jié)式為

C12=R(b)∨Q(f(a))

我們把C1σ稱為C1的因子。一般來說，若子句C中有兩個或兩個以上的文字具有最一般合一σ，則稱Cσ為子句C的因子。如果Cσ是一個單文字，則稱它為C的單元因子。應(yīng)用因子概念，可對謂詞邏輯中的歸結(jié)原理給出如下定義：4.4.2魯濱遜歸結(jié)原理

3.謂詞邏輯的歸結(jié)（5/16）

定義4.21若C1和C2是無公共變元的子句，則①C1和C2的二元歸結(jié)式;②C1和C2的因子C2σ2的二元歸結(jié)式；③C1的因子C1σ1和C2的二元歸結(jié)式；④C1的因子C1σ1和C2的因子C2σ2的二元歸結(jié)式。這四種二元歸結(jié)式都是子句C1和C2的二元歸結(jié)式，記為C12。例4.15

設(shè)C1=P(y)∨P(f(x))∨Q(g(x))，C2=﹁P(f(g(a)))∨Q(b)，求C12。解：對C1

，取最一般合一σ={f(x)/y}，得C1的因子

C1σ=P(f(x))∨Q(g(x))對C1的因子和C2歸結(jié)（σ={g(a)/x}），可得到C1和C2的二元歸結(jié)式

C12=Q(g(g(a)))∨Q(b)

說明：對謂詞邏輯，定理3.2仍然適用，即歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。用歸結(jié)式取代它在子句集S中的親本子句，所得到的子句集仍然保持著原子句集S的不可滿足性。此外，對謂詞邏輯定理3.3也仍然適用，即從不可滿足的意義上說，一階謂詞邏