歸結(jié)演繹推理課件

3.1推理的基本概念

1.什么是推理推理是按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過(guò)程。

推理所用事實(shí)可分為兩種：與求解問(wèn)題有關(guān)的初始證據(jù)。推理過(guò)程中所得到的中間結(jié)論。3.1推理的基本概念

1.什么是推理3.1推理的基本概念

通常智能系統(tǒng)的推理過(guò)程是通過(guò)推理機(jī)來(lái)完成的。推理機(jī)就是用來(lái)實(shí)現(xiàn)推理的那些程序。智能系統(tǒng)的推理包括兩個(gè)基本問(wèn)題：推理的方法。推理的控制策略。3.1推理的基本概念通常智能系統(tǒng)3.1推理的基本概念2.推理方法及其分類(lèi)推理方法主要解決在推理過(guò)程中前提與結(jié)論之間的邏輯關(guān)系，以及在非精確性推理中不確定性的傳遞問(wèn)題。(1)按推理的邏輯基礎(chǔ)分類(lèi)演繹推理（一般到個(gè)別）是從已知的一般性知識(shí)出發(fā)，去推出蘊(yùn)涵在這些已知知識(shí)中的適合與某種個(gè)別情況的結(jié)論。其核心是三段論：假言推理、拒取式和假言三段論。3.1推理的基本概念2.推理方法及其分類(lèi)3.1推理的基本概念

常用的三段論是由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論三部分組成。其中:

大前提是已知的一般性知識(shí)或推理過(guò)程得到的判斷；小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。3.1推理的基本概念常用的三段論3.1推理的基本概念例如：摔跤運(yùn)動(dòng)員的身體都是強(qiáng)壯的；（大前提）李名是一名摔跤運(yùn)動(dòng)員；（小前提）所以，李名的身體是強(qiáng)壯的。（結(jié)論）3.1推理的基本概念例如：3.1推理的基本概念歸納推理（個(gè)別到一般）是從一類(lèi)事物的大量特殊實(shí)例出發(fā)，去推出該類(lèi)事物的一般性結(jié)論。按所選事例的廣泛性可分為完全歸納推理和不完全歸納推理。按所選的方法可分為枚舉歸納推理、類(lèi)比歸納推理和差異歸納推理等。默認(rèn)推理是在知識(shí)不完全的情況假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理，也稱(chēng)為缺省推理。3.1推理的基本概念歸納推理（個(gè)別到一般）3.1推理的基本概念(2)按所用知識(shí)的確定性分類(lèi)分為確定性推理與不確定性推理。確定性推理是指推理所使用的知識(shí)和推出的結(jié)論都是可以精確表示的，其值要么為真，要么為假。不確定性推理是指推理所使用的知識(shí)不都是精確的，推出的結(jié)論也不完全是確定的，其值會(huì)位于真與假之間。3.1推理的基本概念(2)按所用知識(shí)的確定性分類(lèi)3.1推理的基本概念(3)按推理過(guò)程的單調(diào)性單調(diào)推理與非單調(diào)推理。單調(diào)推理是指在推理過(guò)程中每當(dāng)使用新的知識(shí)后，所得到的結(jié)論會(huì)愈來(lái)愈接近于目標(biāo)，而不會(huì)出現(xiàn)反復(fù)情況。非單調(diào)推理是指在推理過(guò)程中當(dāng)某些新知識(shí)加入后，會(huì)否定原來(lái)推出的結(jié)論，使推理過(guò)程回到先前的某一步。3.1推理的基本概念(3)按推理過(guò)程的單調(diào)性3.1推理的基本概念3.推理的控制策略及其分類(lèi)推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理過(guò)程盡快達(dá)到目標(biāo)的策略。由于智能系統(tǒng)的推理過(guò)程一般表現(xiàn)為一種搜索過(guò)程，因此推理的控制策略分為:推理策略：主要解決推理方向、沖突消解等問(wèn)題。搜索策略：主要解決推理路線(xiàn)、推理效果、推理效率等問(wèn)題。3.1推理的基本概念3.推理的控制策略及其分類(lèi)3.1推理的基本概念

推理方向用來(lái)確定推理的控制方式，即推理過(guò)程是從初始證據(jù)開(kāi)始到目標(biāo)，還是從目標(biāo)開(kāi)始到初始證據(jù)。按照對(duì)推理方向的控制，推理又分為：正向推理逆向推理混合推理雙向推理無(wú)論哪一種推理方式，系統(tǒng)都需要有一個(gè)存放知識(shí)的知識(shí)庫(kù)，一個(gè)存放初始證據(jù)及中間結(jié)果的綜合數(shù)據(jù)庫(kù)和一個(gè)用于推理的推理機(jī)。3.1推理的基本概念推理方向用來(lái)3.1推理的基本概念4.正向推理（數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈推理）是從已知事實(shí)出發(fā)、正向使用推理規(guī)則的推理方式。正向推理算法描述：（1）把用戶(hù)提供的初始證據(jù)放入綜合數(shù)據(jù)庫(kù)。（2）檢查綜合數(shù)據(jù)庫(kù)中是否包含了問(wèn)題的解，若已包含，則求解結(jié)束，并成功退出；否則執(zhí)行下一步。（3）檢查知識(shí)庫(kù)中是否有可用知識(shí)，若有，形成當(dāng)前可用知識(shí)集，執(zhí)行下一步；否則轉(zhuǎn)（5）。3.1推理的基本概念4.正向推理（數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈推理3.1推理的基本概念

(4）按照某種沖突消解策略，從當(dāng)前可用知識(shí)集中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入綜合數(shù)據(jù)庫(kù)中，然后轉(zhuǎn)（2）。（5）詢(xún)問(wèn)用戶(hù)是否可以進(jìn)一步補(bǔ)充新的事實(shí)，如若可以，則將補(bǔ)充的新事實(shí)加入綜合數(shù)據(jù)庫(kù)中，然后轉(zhuǎn)（3）；否則表示無(wú)解，失敗退出。正向推理的優(yōu)點(diǎn)：直觀，允許用戶(hù)主動(dòng)提供有用的事實(shí)信息，適合于診斷、設(shè)計(jì)、監(jiān)控等領(lǐng)域的問(wèn)題求解。正向推理的缺點(diǎn)：推理無(wú)明確目標(biāo)，求解問(wèn)題可能執(zhí)行許多與解無(wú)關(guān)的操作，導(dǎo)致推理效率低3.1推理的基本概念(4）按照某種沖突消解策略，從當(dāng)前3.1推理的基本概念5.逆向推理（目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理）是一種以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的推理方法。逆向推理算法描述：（1）把要求求證的目標(biāo)（稱(chēng)為假設(shè)）構(gòu)成一個(gè)假設(shè)集；（2）從假設(shè)集中選出一個(gè)假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫(kù)中，若在，則該假設(shè)成立，此時(shí)，若假設(shè)集為空，則成功退出；否則仍執(zhí)行（2）；若不在綜合數(shù)據(jù)庫(kù)中，則執(zhí)行下一步。3.1推理的基本概念5.逆向推理（目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理3.1推理的基本概念（3）檢查該假設(shè)是否可由知識(shí)庫(kù)的某個(gè)知識(shí)導(dǎo)出。若不能由某個(gè)知識(shí)導(dǎo)出，則詢(xún)問(wèn)用戶(hù)該假設(shè)是否為可由用戶(hù)證實(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）。3.1推理的基本概念（3）檢查該假設(shè)是否可由知識(shí)庫(kù)的某個(gè)知3.1推理的基本概念例3.1設(shè)推理開(kāi)始時(shí)，知識(shí)庫(kù)中的規(guī)則和綜合數(shù)據(jù)庫(kù)中的事實(shí)如下：規(guī)則1：IF你丟了自行車(chē)鑰匙，并且車(chē)胎沒(méi)氣THEN自行車(chē)不能騎規(guī)則2：IF自行車(chē)不能騎，并且你只能走路去

THEN你聽(tīng)功課會(huì)遲到事實(shí)1：你丟了自行車(chē)事實(shí)2：車(chē)胎沒(méi)氣

3.1推理的基本概念例3.1設(shè)推理開(kāi)始時(shí)，知識(shí)庫(kù)中的規(guī)則3.1推理的基本概念

如果利用逆向推理求證“你聽(tīng)課會(huì)遲到”這一假設(shè)，其推理過(guò)程如下：（1）從假設(shè)集中取出該假設(shè)，查找綜合數(shù)據(jù)庫(kù)，直該假設(shè)不是綜合數(shù)據(jù)庫(kù)中的事實(shí)。（2）查找知識(shí)庫(kù)，發(fā)現(xiàn)該假設(shè)可由規(guī)則2導(dǎo)出，于是規(guī)則2被放入可用知識(shí)集（3）由于只有這一條規(guī)則可用，故可用知識(shí)集中只有規(guī)則2。從可用知識(shí)集中取出規(guī)則2，將其與兩個(gè)前提條件“自行車(chē)不能騎”和“你只有走路去”都作為新的假設(shè)放入假設(shè)集。3.1推理的基本概念如果利用逆向3.1推理的基本概念（4）從假設(shè)集中取出一個(gè)假設(shè)“自行車(chē)不能騎”，它不是綜合數(shù)據(jù)庫(kù)中的事實(shí)，但可由規(guī)則1導(dǎo)出，于是規(guī)則1被放入可用知識(shí)集，此時(shí)可用知識(shí)集中仍然是只有一條規(guī)則。（5）從可用知識(shí)集中提出規(guī)則1，將其兩個(gè)前提條件“你丟了自行車(chē)鑰匙”和“車(chē)胎沒(méi)氣”也作為新的假設(shè)放入假設(shè)集。3.1推理的基本概念（4）從假設(shè)集中取出一個(gè)假設(shè)“自行車(chē)不3.1推理的基本概念（6）再?gòu)募僭O(shè)集中取出一個(gè)假設(shè)“你只有走路去”，檢查發(fā)現(xiàn)此假設(shè)既不在綜合數(shù)據(jù)庫(kù)中也不能被任何一條規(guī)則所導(dǎo)出，詢(xún)問(wèn)用戶(hù)“你只有走路去嗎？”若用戶(hù)回答“是”，則該假設(shè)成立，并被放入綜合數(shù)據(jù)庫(kù)中。此時(shí)，假設(shè)集中還有兩個(gè)假設(shè)“你丟了自行車(chē)鑰匙”和“車(chē)胎沒(méi)氣”（7）繼續(xù)推理，顯然它們都是綜合數(shù)據(jù)庫(kù)中的事實(shí)，均為真。（8）繼續(xù)推理，假設(shè)庫(kù)也為空，推理過(guò)程結(jié)束，“你聽(tīng)課會(huì)遲到”得證。3.1推理的基本概念（6）再?gòu)募僭O(shè)集中取出一個(gè)假設(shè)“你只有3.1推理的基本概念逆向推理的優(yōu)點(diǎn)：不必尋找和使用那些與假設(shè)目標(biāo)無(wú)關(guān)的信息和知識(shí)，推理過(guò)程的目標(biāo)明確，同時(shí)有利于向用戶(hù)提供解釋?zhuān)谠\斷性專(zhuān)家系統(tǒng)中較為有效。逆向推理的缺點(diǎn)：當(dāng)用戶(hù)對(duì)解的情況不清時(shí)，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會(huì)影響系統(tǒng)效率。3.1推理的基本概念逆向推理的優(yōu)點(diǎn)：3.1推理的基本概念6.混合推理(1).混合推理的方法先正向后逆向的混合推理先逆向后正向的混合推理雙向混合推理3.1推理的基本概念6.混合推理3.1推理的基本概念(2).混合推理的適用場(chǎng)合已知事實(shí)不夠充分由正向推理推出的結(jié)論不可靠希望得出更多的結(jié)論希望從正反兩方向同時(shí)進(jìn)行推理3.1推理的基本概念(2).混合推理的適用場(chǎng)合3.1推理的基本概念7.推理的沖突消解策略

在推理的某一步，如果知識(shí)庫(kù)中有多條知識(shí)可用，則稱(chēng)發(fā)生了沖突，此時(shí)需要按照某種策略從這多條知識(shí)中選擇一條最佳知識(shí)用于推理，稱(chēng)這種解決沖突的過(guò)程為沖突消解。沖突消解所用的策略則稱(chēng)為沖突消解策略。沖突消解的基本思想是對(duì)可用知識(shí)庫(kù)進(jìn)行排序。3.1推理的基本概念7.推理的沖突消解策略3.1推理的基本概念目前，常用的沖突消解策略有：.特殊知識(shí)優(yōu)先新鮮知識(shí)優(yōu)先差異性大的知識(shí)優(yōu)先領(lǐng)域特點(diǎn)優(yōu)先上下文關(guān)系優(yōu)先前提條件少者優(yōu)先3.1推理的基本概念目前，常用的沖突消解策略有：3.2推理的邏輯基礎(chǔ)

1.謂詞公式的解釋

定義3.1設(shè)D是謂詞公式P的非空個(gè)體域，若對(duì)P中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值：（1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；

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

Dn={(x1,x2,…,xn)|x1,x2,…,xnD}（3）為每個(gè)n元謂詞指派一個(gè)從Dn到{F、T}的映射。

則稱(chēng)這些指派為P在D上的一個(gè)解釋。3.2推理的邏輯基礎(chǔ)

1.謂詞公式的解釋3.2推理的邏輯基礎(chǔ)

例3.2設(shè)個(gè)體域D={1,2}，求公式A=(x)(y)P(x,y)在D上的解釋?zhuān)⒅赋鲈诿恳环N解釋下公式的真值。解：由于公式A中沒(méi)有包含個(gè)體域和函數(shù)，因此可以直接為謂詞指派真值，設(shè)有：

P(1,1)P(1,2)P(2,1)P(2,2)TFTF3.2推理的邏輯基礎(chǔ)

例3.2設(shè)個(gè)體域D={1,2}，求3.2推理的邏輯基礎(chǔ)

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

P(1,1)P(1,2)P(2,1)P(2,2)TTFF3.2推理的邏輯基礎(chǔ)

這就是公式A在D上的一個(gè)3.2推理的邏輯基礎(chǔ)

這也是公式A在D上的一個(gè)解釋。從這個(gè)解釋可以看出：當(dāng)x=1、y=1時(shí)，有P(x,y)的真值為T(mén);當(dāng)x=2、y=1時(shí)，有P(x,y)的真值為F;同樣當(dāng)x=1、y=2時(shí)，有P(x,y)的真值為T(mén);當(dāng)x=2、y=2時(shí)，有P(x,y)的真值為F;即對(duì)x在D上的任意取值，不存在一個(gè)y使P(x,y)的真值為T(mén)。因此，在此解釋下公式A的真值為F。實(shí)際上,A在D上共有16種(2的四次方,即P(1,1),P(1,2),P(2,1),P(2,2)每個(gè)均有T、F兩種)解釋。3.2推理的邏輯基礎(chǔ)

這也是公式A在D上的一個(gè)解釋。從這個(gè)3.2推理的邏輯基礎(chǔ)

例3.3設(shè)個(gè)體域D={1,2}，求公式A=(x)P(f(x),a)在D上的解釋?zhuān)⒅赋鲈谠摻忉屜鹿紹的真值。解：設(shè)個(gè)體常量a和函數(shù)f(x)的真值指派為：

af(1)f(2)

1123.2推理的邏輯基礎(chǔ)

例3.3設(shè)個(gè)體域D={1,2}，求3.2推理的邏輯基礎(chǔ)

對(duì)謂詞的真值指派為

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

當(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上的任意取值，都存在a=1使P(f(x),a)的真值為T(mén)。因此在此解釋下公式B的真值為T(mén)。3.2推理的邏輯基礎(chǔ)

對(duì)謂詞的真值指派為P(3.2推理的邏輯基礎(chǔ)

2.謂詞公式的永真性與可滿(mǎn)足性下面定義謂詞公式的永真性、永假性、可滿(mǎn)足性與不可滿(mǎn)足性。定義3.2

如果謂詞公式P對(duì)非空個(gè)體域D上的任一解釋都取得真值T，則稱(chēng)P在D上是永真的；如果P在任何非空個(gè)體域D上均是永真的，則稱(chēng)P永真。要判定一個(gè)謂詞公式為永真，必須對(duì)每個(gè)非空個(gè)體域上的每個(gè)解釋逐一判斷。當(dāng)解釋個(gè)數(shù)無(wú)限時(shí)，其永真性就很難判定了。3.2推理的邏輯基礎(chǔ)

2.謂詞公式的永真性與可滿(mǎn)足性3.2推理的邏輯基礎(chǔ)

定義3.3

對(duì)于謂詞公式P，如果至少存在D上的一個(gè)解釋?zhuān)构絇在此解釋下的真值為T(mén)，則稱(chēng)公式P在D上是可滿(mǎn)足的。謂詞公式的滿(mǎn)足性也稱(chēng)為相容性。定義3.4

如果謂詞公式P對(duì)非空個(gè)體域D上的任一解釋都取得真值F，則稱(chēng)P在D上是永假的；如果P在任何非空個(gè)體域D上均是永假的，則稱(chēng)P永假。

謂詞公式的永假性也稱(chēng)為不可滿(mǎn)足性也稱(chēng)為不相容性。3.2推理的邏輯基礎(chǔ)

定義3.3對(duì)于謂詞公式P，如果至少3.2推理的邏輯基礎(chǔ)

3.謂詞公式的等價(jià)性與永真蘊(yùn)含性謂詞公式的等價(jià)性和永真蘊(yùn)含性可分別用相應(yīng)的等價(jià)式和永真蘊(yùn)含式來(lái)表示，這些等價(jià)式和永真蘊(yùn)含式都是演繹推理的主要依據(jù)，因此也稱(chēng)它們?yōu)橥评硪?guī)則。(1).等價(jià)式定義3.5

設(shè)P與Q是D上的兩個(gè)謂詞公式，若對(duì)D上的任意解釋?zhuān)琍與Q都有相同的真值，則稱(chēng)P與Q在D上是等價(jià)的。如果D是任意非空個(gè)體域，則稱(chēng)P與Q是等價(jià)的，記作PQ。3.2推理的邏輯基礎(chǔ)

3.謂詞公式的等價(jià)性與永真蘊(yùn)含性3.2推理的邏輯基礎(chǔ)常用的等價(jià)公式：（1）雙重否定率：??P

P（2）交換率：P∨Q

Q∨P,P∧QQ∧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)P,

P∧(P∨

Q)

P3.2推理的邏輯基礎(chǔ)常用的等價(jià)公式：3.2推理的邏輯（7）補(bǔ)余率：P∨?PT,

P

∧?P

F（8）連詞化歸率：P→Q

?P∨

Q,PQ

(P→Q)∧(Q→P)PQ

(P∧

Q)∨(?Q∧

?P)（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)Q3.2推理的邏輯（7）補(bǔ)余率：P∨?P3.2推理的邏輯基礎(chǔ)

(2).永真蘊(yùn)含式定義3.6

對(duì)謂詞公式P和Q，如果P→Q永真，則稱(chēng)P永真蘊(yùn)含Q，且稱(chēng)Q為P的邏輯結(jié)論，P為Q的邏輯前提，記作PQ。常用的永真蘊(yùn)含式如下：（1）化簡(jiǎn)式：P∧Q

P，P∧Q

Q（2）附加式：PP∨Q，QP∨Q（3）析取三段論：?P，P∨QQ3.2推理的邏輯基礎(chǔ)

(2).永真蘊(yùn)含式3.2推理的邏輯基礎(chǔ)（4）假言圖理：P，P→QQ（5）抽取式：?Q，P→Q

?P（6）假言三段論：P→Q，Q→R

P→R（7）二難推理：P∨Q，

P→R，Q→R

R（8）全稱(chēng)固化：(x)P(x)P(y)y是個(gè)體域中的任一個(gè)體，利用此永真蘊(yùn)含式可消去謂詞公式中的全程量詞。（9）存在固化：(x)P(x)

P(y)y是個(gè)體域中某一個(gè)可以使P(x)為真的個(gè)體。利用此永真蘊(yùn)含式可消去謂詞公式中的存在量詞。3.2推理的邏輯基礎(chǔ)（4）假言圖理：P，3.2推理的邏輯基礎(chǔ)

4.謂詞公式的范式范式是公式的標(biāo)準(zhǔn)形式，公式往往需要變換為同它等價(jià)的范式，以便對(duì)它們做一般性的處理。在謂詞公式出現(xiàn)的情況可將謂詞公式的范式分為兩種：(1).前束范式：定義3.7

設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，而它們的下域?yàn)檎麄€(gè)公式，則稱(chēng)F為前述范式。一般地，前述范式可寫(xiě)為：（Q1x1)…(Qnxn)M(x1,x2,…,xn)其中Qi（i=1,2,…,n)為前綴，它是一個(gè)由全程量詞或存在量詞組成的量詞串；M(x1,x2,…,xn)為母式，它是一個(gè)不含任何量詞的謂詞公式。3.2推理的邏輯基礎(chǔ)

4.謂詞公式的范式3.2推理的邏輯基礎(chǔ)

例如，(x)(y)(z)(P(x)∨Q(y,z)∧R(x,z)是前束范式

任一謂詞公式均可化為與其對(duì)應(yīng)的前述范式，其簡(jiǎn)化方法將在后面子句集的化簡(jiǎn)中討論。3.2推理的邏輯基礎(chǔ)

例如，(x)(3.2推理的邏輯基礎(chǔ)

(2).Skolem范式：定義3.8

如果前束范式中所有的存在量詞都在全稱(chēng)量詞之前，則稱(chēng)這種形式的謂詞公式為Skolem范式。例如，(x)(z)(y)(P(x)∨Q(y,z)∧R(x,z)是Skolem范式任一謂詞公式均可化為與其對(duì)應(yīng)的Skolem范式，其簡(jiǎn)化方法將在后面子句集的化簡(jiǎn)中討論。3.2推理的邏輯基礎(chǔ)

(2).Skolem范式：3.2推理的邏輯基礎(chǔ)

5.置換與合一在不同謂詞公式中，往往會(huì)出現(xiàn)謂詞名相同但其個(gè)體不同的情況，此時(shí)推理過(guò)程是不能直接進(jìn)行匹配，需要先進(jìn)行置換。例如：可根據(jù)全稱(chēng)固化推理和假言推理由謂詞公式

W1(A)和(

x)(W1(x)→W2(x))推出W2(A)。對(duì)謂詞W1(A)可看作由全稱(chēng)固化推理（即(

x)(W1(x)→W2(x)）)推出的，其中A是任意個(gè)體常量。3.2推理的邏輯基礎(chǔ)

5.置換與合一3.2推理的邏輯基礎(chǔ)

(1).置換（substitution）定義3.9

置換是形如{t1/x2,t2/x2,…,tn/xn}的有限集合。其中，t1,t2,…,tn是項(xiàng)；x1,x2,…,xn是互不相同的變?cè)?；ti/xi表示用ti置換xi。并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。例如：{a/x,c/y,f(b)/z}是一個(gè)置換{g(y)/x,f(x)/y}不是一個(gè)置換{g(a)/x,f(x)/y}是一個(gè)置換3.2推理的邏輯基礎(chǔ)

(1).置換（substitutio3.2推理的邏輯基礎(chǔ)

定義3.10

設(shè)θ=(t1/a1,t2/a2,…,tn/an}是一個(gè)置換，F(xiàn)是一個(gè)謂詞公式，把公式F中的所有ai換成ti（I=1,2,…,n），得到一個(gè)新的公式G，稱(chēng)G為F在置換θ下的例示，記作G=Fθ

。一個(gè)謂詞公式的任何示例都是該公式的邏輯結(jié)論。3.2推理的邏輯基礎(chǔ)

定義3.10設(shè)θ=(t1/a1,t3.2推理的邏輯基礎(chǔ)

定義3.11

設(shè)θ

={t1/a1,t2/a2,…,tn/an}，λ={u1/y1,u2/y2,…,um/ym}是兩個(gè)置換。則θ與λ的合成也是一個(gè)置換，記作θ.λ。它是從集合

{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym}

中刪去以下兩種元素（1）當(dāng)tiλ=xi時(shí)，刪去tiλ/xi

（i=1,2,…,n);（2）當(dāng)yi(x1,x2,…,xi)時(shí)，刪去ui/yi

（i=1,2,…,m)。最后剩下的新元素所構(gòu)成的集合。3.2推理的邏輯基礎(chǔ)

定義3.11設(shè)θ={t1/a13.2推理的邏輯基礎(chǔ)

例3.4：設(shè)θ={f(y)/x,z/y},λ={a/x,b/y,y/z},求θ與λ的合成。解：先求出集合{發(fā){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滿(mǎn)足定義中的條件（1），需要?jiǎng)h除；a/x,b/y滿(mǎn)足定義中的條件（2），需要?jiǎng)h除。最后得：

θ.λ={f(b)/x,y/z}3.2推理的邏輯基礎(chǔ)

例3.4：設(shè)θ={f(y)/x,z/3.2推理的邏輯基礎(chǔ)

(2).合一（Unifier）合一可以簡(jiǎn)單地理解為尋找項(xiàng)對(duì)變量的置換，使兩個(gè)謂詞公式一致。定義3.12

設(shè)有公式集F={F1,F2,…,Fn},若存在一個(gè)置θ，可使F1θ=F2θ

=…=Fnθ,則稱(chēng)θ是F的一個(gè)合一。稱(chēng)F1,F2,…,Fn是可以合一的。例如：是有公式集F={P(x,y,f(y),P(a,g(x),z))},則λ

={a/x,g(a)/y,f(g(a))/z}是它的一個(gè)合一。3.2推理的邏輯基礎(chǔ)

(2).合一（Unifier）3.2推理的邏輯基礎(chǔ)

一般來(lái)說(shuō)，一個(gè)公式集的合一不是唯一的。定義3.13

設(shè)是公式集F的一個(gè)合一，如果隊(duì)F的任意個(gè)合一θ都存在一個(gè)置換λ，使得θ=θ.λ

，則稱(chēng)θ是一個(gè)最一般合一（MostGeneralUnifier,簡(jiǎn)記MGU)。一個(gè)公式集的最一般合一是唯一的。3.2推理的邏輯基礎(chǔ)

一般來(lái)說(shuō)，一個(gè)公式集的合一不是唯一的3.2推理的邏輯基礎(chǔ)

(3).合一算法定義3.14設(shè)F={F1,F2,…,Fn}是一個(gè)非空有限的公式集，從F中每個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較，知道發(fā)現(xiàn)第一個(gè)不相同的符號(hào)為止，從F的各個(gè)公式中取出那些以第一個(gè)不一致符號(hào)開(kāi)始的最大子表達(dá)式，并以這些子表達(dá)式為元素組成一個(gè)集合D,則稱(chēng)D為F的分歧集（DisagreementSet)。3.2推理的邏輯基礎(chǔ)

(3).合一算法3.2推理的邏輯基礎(chǔ)

例3.5：求F={P(x,y,z),P(x,f(a),h(b))的分歧集。解：這里F1=P(x,y,z),F1=P(x,f(a),h(b))，分別從F1和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)}3.2推理的邏輯基礎(chǔ)

例3.5：求F={P(x,y,z),3.2推理的邏輯基礎(chǔ)

合一算法：設(shè)F為非空有限公式集合，求F的最一般合一的合一算法如下：（1）令k=0,Fk=F,θk=σ(空置換,即不含任何元素的置換)；（2）若Fk只含有一個(gè)表達(dá)式，則算法停止,θk就是最一般合一；（3）找出Fk的分歧集Dk;（4）若Dk中存在元素xk和tk，其中xk是變?cè)?，tk是項(xiàng)，且xk不在tk中出現(xiàn)，則置

θk+1=θk.{tk/xk},Fk+1=Fk.{tk/xk},k=k+1,然后轉(zhuǎn)（2）；（5）算法停止，F(xiàn)的最一般合一不存在。3.2推理的邏輯基礎(chǔ)

合一算法：設(shè)F為非空有限公式3.2推理的邏輯基礎(chǔ)

例3.6：求公式集F={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的最一般合一。解：根據(jù)上述合一算法，首先置

k=0:F0=F,θ0=σF0不是單一表達(dá)式，有D0={a,z},其中z為變?cè)?，且z不在a中出現(xiàn)，從而

θ1=θ0.{a/z}F1=F0{a/z}=P(a,x,f(g(y))),P(z,h(z,u),f(u))}3.2推理的邏輯基礎(chǔ)

例3.6：求公式集F={P(a,x,3.2推理的邏輯基礎(chǔ)

k=1:F1也不是單一表達(dá)式，有D1

={x,h(a,u)},

其中x為變?cè)?，從?/p>

θ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(a,h(a,u),f(u))}k=2:F2也不是單一表達(dá)式，有D2

={g(y),u},其中u為變?cè)?，從而?=θ2.{g(y)/u}={a/z,h(a,g(y))/x,g(y)/u}3.2推理的邏輯基礎(chǔ)

k=1:F1也不是單一表達(dá)式，有D3.2推理的邏輯基礎(chǔ)

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)))}k=3:F3已不是單一表達(dá)式，因此θ3={a/z,h(a,g(y))/x,g(y)/u}是F的最一般合一。3.2推理的邏輯基礎(chǔ)

F3=F2{g(y)3.3自然演繹推理

從一組以知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過(guò)程稱(chēng)為自然演繹推理。

在這種推理中，最基本的推理規(guī)則是三段論推理，包括：假言推理、拒取式推理、假言三段論等。3.3自然演繹推理從一組以知為真的事實(shí)出發(fā)，直3.3自然演繹推理兩類(lèi)錯(cuò)誤：（1）肯定后件的錯(cuò)誤：當(dāng)P為真時(shí)，希望通過(guò)肯定后件Q為真來(lái)推出前件P為真，這是不允許的。（2）否定前件的錯(cuò)誤：當(dāng)P為真時(shí)，希望通過(guò)否定前件P來(lái)推出后件Q為假，這也是不允許的。3.3自然演繹推理兩類(lèi)錯(cuò)誤：3.3自然演繹推理例3.7：設(shè)已知如下事實(shí)：

A,B,A→C,B∧C→D,D→Q求證：Q為真證明：A,A→CC假言推理

B,C

B∧C引入合取詞

B∧C,B∧C→DD假言推理

D,D→Q

Q假言推理所以Q為真。3.3自然演繹推理例3.7：設(shè)已知如下事實(shí)：3.3自然演繹推理例3.8：設(shè)已知如下事實(shí)：（1）只要是編程序的課王成都喜歡。（2）所有的程序設(shè)計(jì)語(yǔ)言課都是需要編程序的課。（3）C是一門(mén)程序設(shè)計(jì)語(yǔ)言課。求證：王成喜歡C這門(mén)課。3.3自然演繹推理例3.8：設(shè)已知如下事實(shí)：3.3自然演繹推理證明：首先定義謂詞

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

Like(x,y)x喜歡y。Lang(x)x是一門(mén)程序設(shè)計(jì)語(yǔ)言課。把上述已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下：

Prog(x)→Like(Wang,x)(

x)(Lang(x)→Prog(x))3.3自然演繹推理證明：首先定義謂詞3.3自然演繹推理應(yīng)用推理規(guī)則進(jìn)行推理：Lang(y)→Prog(y)全稱(chēng)固化Lang(C),Lang(y)→Prog(y)?Prog(C)假言推理

Prog(C),Prog(x)→Like(Wang,x)

?

Like(Wang,C)假言推理因此王成喜歡C這門(mén)課。3.3自然演繹推理應(yīng)用推理規(guī)則進(jìn)行推理：3.4歸結(jié)演繹推理

1.子句集及其簡(jiǎn)化(1).子句及子句集定義3.15原子謂詞公式及其否定統(tǒng)稱(chēng)為文字。例如P(x)、Q(x)、?P(x)、?Q(x)等都是文字。定義3.16任何文字的析取式稱(chēng)為子句。例如P(x)∨Q(x)、P(x,f(x))∨Q(x,g(x)))都是子句。定義3.17不包含任何文字的子句稱(chēng)為空子句。一般記為[]或NIL。定義3.18由子句或空子句所構(gòu)成的集合稱(chēng)為子句集。3.4歸結(jié)演繹推理

1.子句集及其簡(jiǎn)化3.4歸結(jié)演繹推理(2).子句集的化簡(jiǎn)化簡(jiǎn)步驟如下：消去連接詞“”“”

減少否定符號(hào)的轄域?qū)ψ冊(cè)獦?biāo)準(zhǔn)化化為前束范式消去存在量詞化為Skolem標(biāo)準(zhǔn)形3.4歸結(jié)演繹推理(2).子句集的化簡(jiǎn)3.4歸結(jié)演繹推理

消去全稱(chēng)量詞消去合取詞更換變?cè)Q(chēng)(3).子句集的應(yīng)用由于在消去存在量詞時(shí)所用的Skolem函數(shù)可以不同，因此化簡(jiǎn)后的標(biāo)準(zhǔn)子句集是不唯一的。這樣當(dāng)原謂詞公式為非永假時(shí)，它與標(biāo)準(zhǔn)子句集并不等價(jià)。但是，當(dāng)原謂詞公式為永假時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響謂詞公式的永假性。3.4歸結(jié)演繹推理消去全稱(chēng)量詞3.4歸結(jié)演繹推理定理3.1設(shè)有謂詞公式F，其標(biāo)準(zhǔn)子句集為S，則F為不可滿(mǎn)足的充要條件是S為不可滿(mǎn)足。證明見(jiàn)書(shū)P943.4歸結(jié)演繹推理定理3.1設(shè)有謂詞公式F，其標(biāo)準(zhǔn)子句3.4歸結(jié)演繹推理2.海伯倫理論如果能對(duì)一個(gè)具體的謂詞公式找到一個(gè)特殊的論域，使得該謂詞公式只要在這個(gè)特殊的論域上不可滿(mǎn)足，就能保證它在任意域論上也都為不可滿(mǎn)足。針對(duì)這一情況，海伯倫構(gòu)造了一個(gè)特殊的域，并且證明只要對(duì)這個(gè)特殊域上的一切解釋進(jìn)行判定，就可得知子句集是否為不可滿(mǎn)足的，這個(gè)特殊的域稱(chēng)為海伯倫域。3.4歸結(jié)演繹推理2.海伯倫理論3.4歸結(jié)演繹推理(1).H域定義3.19設(shè)S為論域D上的一個(gè)子句集，則按下述方法構(gòu)造的域H稱(chēng)為海伯倫域，簡(jiǎn)記為H域。令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則可任取一常量aD,并令H0={a};令Hi+1=Hi∪{S中所有n元函數(shù)f(x1,x2,…,xn)|xj(j=1,2,…,n)是Hi中的元素}，其中，I=0,1,2,…。3.4歸結(jié)演繹推理(1).H域3.4歸結(jié)演繹推理例3.9：求S={P(a),Q(x)∨R(f(x))}的H域。解：在此例中只有一個(gè)個(gè)體常量a，依H域的定義有

H0

={a}

H1

={a}∪{f(a)}={a,f(a)}

H2

={a,f(a)}∪{f(f(a))}={a,f(a),f(f(a))}….H={a,f(a),f(f(a)),...}3.4歸結(jié)演繹推理例3.9：求S={P(a),Q(x)∨R3.4歸結(jié)演繹推理例3.10：求子句集S={P(a),Q(b),R(f(x))}的H域。解：在此例中有兩個(gè)個(gè)體常量a和b，依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={a,b,f(a),f(b),f(f(a)),f(f(b))...}3.4歸結(jié)演繹推理例3.10：求子句集S={P(a),Q(3.4歸結(jié)演繹推理例3.11：求子句集S={P(c),P(f(y)),Q(g(y))}的H域。解：在此例中有一個(gè)體常量和函數(shù)f(y)、g(y)，依H域的定義有

H0

={c}

H1

={c,f(c),g(c)}

H2

={c,f(c),g(c),f(f(c)),g(g(c))}….H={c,f(c),g(c),f(f(c)),g(g(c)),…}3.4歸結(jié)演繹推理例3.11：求子句集S={P(c),P(3.4歸結(jié)演繹推理

如果用H域中的元素代替子句中的變?cè)?則所得到的子句稱(chēng)為基子句?；泳渲械闹^詞稱(chēng)為基原子。子句集中所有基原子構(gòu)成的集合稱(chēng)為原子集。(2).H解釋子句集S在H域上的解釋就是對(duì)S中出現(xiàn)的常量、函數(shù)及謂詞的取值，一次取值就構(gòu)成一個(gè)解釋。3.4歸結(jié)演繹推理如果用H域中的3.4歸結(jié)演繹推理定義3.20子句集S在H域上的一個(gè)解釋IH滿(mǎn)足如下條件：在解釋IH下，常量映射到自身；S中的任一n元函數(shù)是HnH的映射。其中，Hn是一個(gè)由屬于H的n個(gè)元素構(gòu)成的集合。即函數(shù)的變量h1,h2,…,hn∈H,并且有函數(shù)值f(x1,x2,…,xn)∈H；S中的任一n元謂詞是Hn{T,F}的映射。即謂詞的真值可以指派為T(mén)或F。3.4歸結(jié)演繹推理定義3.20子句集S在H域上的一個(gè)解釋3.4歸結(jié)演繹推理例3.13：求子句集S={P(x)∨Q(x)，R(f(y))}在H域上的一個(gè)解釋IH。解：子句集S的H域和原子集分別為

H={a,f(a),f(f(a)),f(f(f(a))),...}

A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),...}對(duì)A中每個(gè)元素真假值的一個(gè)具體設(shè)定，就是S的一個(gè)H解釋。即S的H解釋有：3.4歸結(jié)演繹推理例3.13：求子句集S={P(x)∨Q(3.4歸結(jié)演繹推理IH1

={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),...}IH2

={?P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),...}

IH3

={P(a),?Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),...}

…其中，IHi中出現(xiàn)的P(a),Q(a),R(a),P(f(a))等表示取P(a),Q(a),R(a),P(f(a))的真值為T(mén)，而出現(xiàn)的?P(a),?Q(a),?R(a),?P(f(a))等表示取P(a),Q(a),R(a),P(f(a))的真值為F。顯然,在H解釋IHi下，S的真值就被確定了。3.4歸結(jié)演繹推理IH1={P(a),Q(a)3.4歸結(jié)演繹推理

一般來(lái)說(shuō)，一個(gè)子句集S的基原子有無(wú)限多個(gè)，或者說(shuō)S的原子集A中的元素有無(wú)限多個(gè)。因此，S在H域上的一個(gè)解釋IH也有無(wú)限多個(gè)。3.4歸結(jié)演繹推理一般來(lái)說(shuō)，一個(gè)3.4歸結(jié)演繹推理例3.14：對(duì)S={P(x),Q(x),R(f(y))}，求與I對(duì)應(yīng)的IH。解：S的H域和原子集分別為

H={a,f(a),f(f(a)),f(f(f(a))),...}

A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),...}設(shè)D={1,2},對(duì)解釋I作如下設(shè)定f(1)f(2)P(1)P(2)Q(1)Q(2)R(1)R(2)22TFFTFT3.4歸結(jié)演繹推理例3.14：對(duì)S={P(x),Q(x),3.4歸結(jié)演繹推理可以驗(yàn)證，S在解釋I下為真。對(duì)常量符號(hào)a，若設(shè)定其值為1或2，便有對(duì)應(yīng)于I的兩個(gè)H解釋。當(dāng)a=1時(shí)有P(a)P(1)T

Q(a)Q(1)FR(a)R(1)FP(f(a))P(f(1))P(2)F

Q(f(a))Q(f(1))Q(2)T

R(f(a))R(f(1))R(2)T由此得到一個(gè)H解釋:IH1

={P(a),?Q(a),?R(a),?P(f(a)),Q(f(a)),R(f(a)),...}

3.4歸結(jié)演繹推理可以驗(yàn)證，S在解釋I下為真。3.4歸結(jié)演繹推理當(dāng)a=2時(shí)有P(a)P(2)T

Q(a)Q(2)FR(a)R(2)FP(f(a))P(f(2))P(2)F

Q(f(a))Q(f(2))Q(2)T

R(f(a))R(f(2))R(2)T由此得到一個(gè)H解釋3.4歸結(jié)演繹推理當(dāng)a=2時(shí)有P(a)3.4歸結(jié)演繹推理IH2

={?P(a),Q(a),R(a),?P(f(a)),Q(f(a)),R(f(a)),...}

即有S在H解釋IH1和

IH2下為真。這樣變實(shí)現(xiàn)了由H來(lái)確定相應(yīng)的IH的問(wèn)題。3.4歸結(jié)演繹推理IH2={?P(a),Q(a),R3.4歸結(jié)演繹推理定理3.2設(shè)I是S在D域上的解釋?zhuān)瑒tS存在著對(duì)應(yīng)于I的H解釋IH，使得若有S在解釋I下為真，必有S在IH下也為真。并且由此定理還可推出：定理3.3子句集S不可滿(mǎn)足的充要條件是S的一切解釋都為假。定理3.4（Herbrand)

子句集S不可滿(mǎn)足的充要條件是存在一個(gè)有限集合的不可滿(mǎn)足的基子句集S’。（證明見(jiàn)書(shū)P98)3.4歸結(jié)演繹推理定理3.2設(shè)I是S在D域上的解釋?zhuān)瑒tS3.4歸結(jié)演繹推理3.魯兵遜歸納原理(1).基本思想：首先把欲證明問(wèn)題的結(jié)論否定，并加入子句集，得到一個(gè)擴(kuò)充的子句集S’。然后設(shè)法檢驗(yàn)子句集S’是否包含有空子句，若含有空子句，則表明S’是不可滿(mǎn)足的；若不含有空子句，則繼續(xù)使用歸納法，在子句集中選擇合適的子句進(jìn)行歸納，直至到出空子句或不能繼續(xù)為止。定義3.21若P是原子謂詞公式，則稱(chēng)P與?P為互補(bǔ)文字。3.4歸結(jié)演繹推理3.魯兵遜歸納原理3.4歸結(jié)演繹推理(2).命題邏輯的歸結(jié)歸結(jié)推理的核心是求兩個(gè)子句的歸結(jié)式。歸結(jié)式的定義及性質(zhì)定義3.22設(shè)C1和C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個(gè)新的子句C12，則稱(chēng)這一過(guò)程為歸結(jié)，稱(chēng)C1和C2為C12的親本子句。3.4歸結(jié)演繹推理(2).命題邏輯的歸結(jié)3.4歸結(jié)演繹推理例3.15設(shè)C1=P∨Q∨R,C2=?P∨S,求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=P,L2=?P,通過(guò)歸結(jié)可以得到C12=Q∨R∨S例3.16設(shè)C1=?Q,C2=Q,求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=?Q,L2=Q,通過(guò)歸結(jié)可以得到C12=NIL3.4歸結(jié)演繹推理例3.15設(shè)C1=P∨Q∨R,C2=3.4歸結(jié)演繹推理例3.17設(shè)C1=?P∨Q,C2=?Q,C3=P,求C1和C2、C3的歸結(jié)式C123。解：首先對(duì)C1、C2作歸結(jié)，可得到C12=

?P然后再對(duì)C12和C3作歸結(jié)，可得到C123=NIL

如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即歸結(jié)過(guò)程是不唯一的。3.4歸結(jié)演繹推理例3.17設(shè)C1=?P∨Q,C2=3.4歸結(jié)演繹推理定理3.5歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。（證明見(jiàn)書(shū)P99)推論1設(shè)C1和C2是子句集S中的兩個(gè)子句，C12是C1和C2的歸結(jié)式，若用C12代替C1和C2后得到新的子句集S1，則由S1的不可滿(mǎn)足性可以推出原子句集S的不可滿(mǎn)足性。即

S1的不可滿(mǎn)足性?S的不可滿(mǎn)足性3.4歸結(jié)演繹推理定理3.5歸結(jié)式C12是其親本子句C13.4歸結(jié)演繹推理推論2設(shè)C1和C2是子句集S中的兩個(gè)子句，C12是C1和C2的歸結(jié)式，若把C12加入S中得到新的子句集S2，則S與S2的不可滿(mǎn)足性是等價(jià)的。即:S2的不可滿(mǎn)足性?S的不可滿(mǎn)足性定理3.6子句集S是不可滿(mǎn)足性的，當(dāng)且僅當(dāng)存在一個(gè)從S到空子句的歸結(jié)過(guò)程。（證明見(jiàn)書(shū)P101)3.4歸結(jié)演繹推理推論2設(shè)C1和C2是子句集S中的兩個(gè)子3.4歸結(jié)演繹推理命題邏輯的歸結(jié)反演應(yīng)用歸結(jié)原理證明定理的過(guò)程稱(chēng)為歸結(jié)反演。在命題邏輯中，已知F，證明G為真的歸結(jié)反演過(guò)程如下：否定目標(biāo)公式，得?G；把?G并入到公式集F中，得到{F?G};把{F?G}化為子句集S；應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次得到的歸結(jié)式并入S中。如此反復(fù)，若出現(xiàn)空子句，則停止歸結(jié)，此時(shí)就證明了G為真。3.4歸結(jié)演繹推理命題邏輯的歸結(jié)反演3.4歸結(jié)演繹推理例3.18設(shè)已知的公式集為{P,(P∧Q)R,(S∨T)Q,T}，求證結(jié)論R。解：假設(shè)結(jié)論R為假，即?R為真，將?R加入公式集，并化為子句集S={P,?P∨?Q∨R,?S∨Q,

?T∨Q,T,?R}其歸結(jié)過(guò)程如圖3-7（見(jiàn)書(shū)P101)3.4歸結(jié)演繹推理例3.18設(shè)已知的公式集為{P,(P3.4歸結(jié)演繹推理(3).謂詞邏輯的歸結(jié)

在謂詞邏輯中，由于子句集中的謂詞一般都含有變?cè)虼瞬荒芟竺}邏輯那樣直接消去互補(bǔ)文字。而需要先用一個(gè)最一般合一變?cè)M(jìn)行代換，然后才能進(jìn)行歸結(jié)?？梢?jiàn)謂詞邏輯的歸結(jié)要比命題邏輯的歸結(jié)復(fù)雜些。3.4歸結(jié)演繹推理(3).謂詞邏輯的歸結(jié)3.4歸結(jié)演繹推理謂詞邏輯的歸結(jié)原理謂詞邏輯中的歸結(jié)可用如下定義來(lái)描述。定義3.23設(shè)C1和C2是兩個(gè)沒(méi)有公共變?cè)淖泳洌琇1與L2分別是C1和C2中的文字。如果L1和?L2存在最一般合一σ，則稱(chēng):C12=(C1σ-{L1σ})∪(C2σ-{L2σ})為C1和C2的二元?dú)w結(jié)式，而C1和C2為二元?dú)w結(jié)式上的文字。定義中還要求C1和C2無(wú)公共變?cè)?.4歸結(jié)演繹推理謂詞邏輯的歸結(jié)原理3.4歸結(jié)演繹推理例3.19設(shè)C1=P(a)∨R(x),C2=?P(y)∨Q(b),求C12。解：取L1=P(a),L2=

?P(y)，則L1和?

L2的最一般合一是σ={a/y}。根據(jù)定義3.23，可得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)3.4歸結(jié)演繹推理例3.19設(shè)C1=P(a)∨R(x),3.4歸結(jié)演繹推理例3.20設(shè)C1=P(x)Q(a),C2=?P(b)∨R(x),求C12。解：由于C1和C2有相同的變?cè)獂，不符合定義3.23的要求。為了進(jìn)行歸結(jié)，需要修改C2變?cè)械拿?，令C2=?P(b)∨R(y)。此時(shí)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)3.4歸結(jié)演繹推理例3.20設(shè)C1=P(x)Q(a),3.4歸結(jié)演繹推理例3.21設(shè)C1=P(x)∨?Q(b),C2=?P(a)∨Q(y)∨R(z),求C12。解：對(duì)C1和C2通過(guò)最一般合一的作用，可以得到兩個(gè)互補(bǔ)對(duì)。但是需要注意，求歸結(jié)式不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，同時(shí)消去兩個(gè)互補(bǔ)對(duì)的結(jié)果不是二元?dú)w結(jié)式。如在σ={a/x,b/y}下，若同時(shí)消去兩個(gè)互補(bǔ)對(duì)，所得的R(z)不是C1和C2的二元?dú)w結(jié)式。3.4歸結(jié)演繹推理例3.21設(shè)C1=P(x)∨?Q(b)3.4歸結(jié)演繹推理例3.22設(shè)C1=P(x)∨P(f(a))∨Q(x),C2=?P(y)∨R(b),求C12。解：對(duì)參加歸結(jié)的某個(gè)子句，若其內(nèi)部有可合一的文字，則在進(jìn)行歸結(jié)之前應(yīng)先對(duì)這些文字進(jìn)行合一。本例的C1中有可合一的文字P(x)與P(f(a))，若用它們的最一般合一σ={f(a)/x}進(jìn)行代換，可得到：

C1σ=P(f(a))∨Q(f(a))此時(shí)可對(duì)C1σ和C2σ進(jìn)行歸結(jié)。選L1=P(f(a)),L2=?P(y),L1和?

L2的最一般合一是σ={f(a)/y}。則C1和C2的二元?dú)w結(jié)式:C12=R(b)∨Q(f(a))把C1σ稱(chēng)為C1的因子。3.4歸結(jié)演繹推理例3.22設(shè)C1=P(x)∨P(f(a3.4歸結(jié)演繹推理

一般說(shuō)來(lái)，若子句C中有兩個(gè)或兩個(gè)以上的文字具有最一般合一σ，則稱(chēng)Cσ為子句C的因子。如果Cσ是一個(gè)單文字，則稱(chēng)它為C的單元因子。3.4歸結(jié)演繹推理一般說(shuō)來(lái)，若子3.4歸結(jié)演繹推理定義3.24若C1和C2是沒(méi)有公共變?cè)淖泳洌瑒t（1）C1和C2的二元?dú)w結(jié)式；（2）C1和C2的因子C2σ的二元?dú)w結(jié)式；（3）C1的因子C1σ和C2的二元?dú)w結(jié)式；（4）C1的因子C1σ和C2的因子C2σ的二元?dú)w結(jié)式。這四種二元?dú)w結(jié)式都是子句C1和C2的二元?dú)w結(jié)式，記為C12。3.4歸結(jié)演繹推理定義3.24若C1和C2是沒(méi)有公共變?cè)?.4歸結(jié)演繹推理例3.23設(shè)C1=P(y)∨P(f(x))∨Q(g(x)),C2=?P(f(g(a)))∨Q(b),求C12。解：對(duì)C1，取最一般合一σ={f(x)/y}，得C1的因子

C1σ=P(f(x))∨Q(g(x))

對(duì)C1的因子和C2進(jìn)行歸結(jié)，可得到C1和C2的二元?dú)w結(jié)式:C12=Q(g(g(a)))∨Q(b)3.4歸結(jié)演繹推理例3.23設(shè)C1=P(y)∨P(f(x3.4歸結(jié)演繹推理

對(duì)謂詞邏輯，定理3.5仍然適用，即歸結(jié)式C12是其親子句C1和C2的邏輯結(jié)論。用歸結(jié)式取代它在子句集S中的親本子句，所得到的子句集仍然保持著原子聚集S的不可滿(mǎn)足性。此外，對(duì)謂詞邏輯定理3.6也仍然適用，即從不可滿(mǎn)足的意義上說(shuō)，一階謂詞邏輯的歸結(jié)原理也是完備的。3.4歸結(jié)演繹推理對(duì)謂詞邏輯，定3.4歸結(jié)演繹推理謂詞邏輯的歸結(jié)反演

謂詞邏輯的歸結(jié)反演過(guò)程與命題邏輯的歸結(jié)反演過(guò)程步驟基本相同，但每步的處理對(duì)象不同。3.4歸結(jié)演繹推理謂詞邏輯的歸結(jié)反演3.4歸結(jié)演繹推理例3.24已知F:(?x)((?y)(A(x,y)B(y)(?y)(C(y)D(x,y)))G:?(?x)C(x)(?x)(?y)(A(x,y)?B(y))求證：G是F的邏輯結(jié)論。證明：先把G否定，并放入F中，得到的{F,?G}為:{(?x)((?y)(A(x,y)B(y)(?y)(C(y)D(x,y)))，

?(?(?x)C(x)(?x)(?y)(A(x,y)?B(y)))}3.4歸結(jié)演繹推理例3.24已知3.4歸結(jié)演繹推理再把{F,?G}化成子句集，得到（1）?(A(x,y)∨?B(y)∨C(f(x))（2）?(A(u,v)∨?B(v)∨D(u,f(u))（3）?C(z)（4）A(m,n)（5）B(k)其中（1）、（2）是由F化出的2個(gè)子句，（3）、（4）、（5）是由?G化出的3個(gè)子句。3.4歸結(jié)演繹推理再把{F,?G}化成子句集，得到3.4歸結(jié)演繹推理

最后應(yīng)用謂詞邏輯的歸結(jié)原理，對(duì)上述子句集進(jìn)行歸結(jié)，其過(guò)程為:（6）?A(x,y)∨?B(y)

由（1）和（3）歸結(jié)，取σ={f(x)/z}（7）?B(y)

由（4）和（6）歸結(jié)，取σ={m/x,n/y}（8）NIL

由（5）和（7）歸結(jié)，取σ={k/n}因此G是F的邏輯結(jié)論。歸結(jié)見(jiàn)書(shū)P104圖３－８3.4歸結(jié)演繹推理最后應(yīng)用謂詞邏3.4歸結(jié)演繹推理例3.25“快樂(lè)學(xué)生”問(wèn)題假設(shè)：任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都可以獲獎(jiǎng)。求證：張是快樂(lè)的。3.4歸結(jié)演繹推理例3.25“快樂(lè)學(xué)生”問(wèn)題3.4歸結(jié)演繹推理解：先將問(wèn)題用謂詞表示如下：“任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的都是快樂(lè)的”(?x)((Pass(x,computer)∧Win(x,prize))Happy(x))“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試”(?x)(?y)((Study(x)∨Lucky(x))Pass(x,y))“張不肯學(xué)習(xí)但他是幸運(yùn)的”?Study(zhang)∧Lucky(zhang)“任何幸運(yùn)的人都可以獲獎(jiǎng)”(?x)(Lucky(x)Win(x,prize))3.4歸結(jié)演繹推理解：先將問(wèn)題用謂詞表示如下：3.4歸結(jié)演繹推理結(jié)論“張是快樂(lè)的”的否定?Happy(zhang)將上述謂詞公式轉(zhuǎn)化為子句集如下：（1）?Pass(x,computer)∨?Win(x,prize)∨Happy(x)（2）?Study(y)∨Pass(y,z)（3）?Lucky(u)∨Pass(u,v)（4）?Study(zhang)3.4歸結(jié)演繹推理結(jié)論“張是快樂(lè)的”的否定3.4歸結(jié)演繹推理（5）Lucky(zhang)（6）?Lucky(w)∨Win(w,prize)（7）?Happy(zhang)歸結(jié)見(jiàn)書(shū)P105圖3－93.4歸結(jié)演繹推理（5）Lucky(zhang)3.4歸結(jié)演繹推理例3.26“激動(dòng)人心的生活”問(wèn)題假設(shè)：所有不貧窮并且聰明的人都是快樂(lè)的。那些看書(shū)的人是聰明的。李明能看書(shū)且不貧窮?？鞓?lè)的人過(guò)著激動(dòng)人心的生活。求證：李明過(guò)著激動(dòng)人心的生活。3.4歸結(jié)演繹推理例3.26“激動(dòng)人心的生活”問(wèn)題3.4歸結(jié)演繹推理解：先將問(wèn)題用謂詞表示如下：“所有不貧窮并且聰明的人都是快樂(lè)的。”(?x)((?Poor(x)∧Smart(x))Happy(x))“那些看書(shū)的人是聰明的”(?y)(Read(y)

Smart(y))“李明能看書(shū)且不貧窮”Read(liming)∧?Poor(liming)“快樂(lè)的人過(guò)著激動(dòng)人心的生活”(?z)(Happy(z)Exciting(z))3.4歸結(jié)演繹推理解：先將問(wèn)題用謂詞表示如下：3.4歸結(jié)演繹推理目標(biāo)“李明過(guò)著激動(dòng)人心的生活”的否定?Exciting(liming)將上述謂詞公式轉(zhuǎn)化為子句集如下：（1）?Poor(x)∨?Smart(x)∨Happy(x)（2）?Read(y)∨Smart(y)（3）Read(liming)（4）?Poor(liming)3.4歸結(jié)演繹推理目標(biāo)“李明過(guò)著激動(dòng)人心的生活”的否定3.4歸結(jié)演繹推理（5）Lucky(zhang)（6）?Happy(z)∨Exciting(z)（7）?Exciting(liming)歸結(jié)見(jiàn)書(shū)P106圖3－103.4歸結(jié)演繹推理（5）Lucky(zhang)3.4歸結(jié)演繹推理4.歸結(jié)演繹推理的歸結(jié)策略歸結(jié)演繹推理實(shí)際上就是從子句集中不斷尋找可進(jìn)行歸結(jié)的子句對(duì)，并通過(guò)對(duì)這些子句對(duì)的歸結(jié)，最終得出一個(gè)空子句的過(guò)程。由于事先并不知道那些子句對(duì)可進(jìn)行歸結(jié)，更不知道哪些子句對(duì)的歸結(jié)能盡快得到空子句，因此需要對(duì)子句集中的所有子句逐對(duì)進(jìn)行比較，需要有效的歸結(jié)策略來(lái)解決。3.4歸結(jié)演繹推理4.歸結(jié)演繹推理的歸結(jié)策略3.4歸結(jié)演繹推理歸結(jié)策略分類(lèi)：刪除策略：通過(guò)刪除某些無(wú)用的子句來(lái)縮小范圍限制策略：通過(guò)對(duì)參加的子句進(jìn)行某些限制來(lái)減小歸結(jié)的盲目性，以盡快得到空子句。3.4歸結(jié)演繹推理歸結(jié)策略分類(lèi)：3.4歸結(jié)演繹推理(1).廣度優(yōu)先策略廣度優(yōu)先策略是一種窮盡子句比較的復(fù)雜搜索方法。設(shè)初始子句集為S0，廣度優(yōu)先策略的歸結(jié)過(guò)程可描述如下：從S0出發(fā)，對(duì)S0中的全部子句做所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1；用S0中的子句集與S1中的子句進(jìn)行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2；用S0和S1中的子句與S2中的子句進(jìn)行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3；3.4歸結(jié)演繹推理(1).廣度優(yōu)先策略