高級人工智能確定性推理

1、人工智能2016年秋季本章內(nèi)容本章內(nèi)容 推理推理的基本概念的基本概念 推理推理的邏輯基礎(chǔ)的邏輯基礎(chǔ) 自然演繹推理自然演繹推理 歸結(jié)推理歸結(jié)推理本章內(nèi)容本章內(nèi)容 推理推理的基本概念的基本概念 推理推理的邏輯基礎(chǔ)的邏輯基礎(chǔ) 自然演繹推理自然演繹推理 歸結(jié)推理歸結(jié)推理什么什么是推理是推理 推理推理是是指按照某種策略從已知事實出發(fā)去推出結(jié)論的過指按照某種策略從已知事實出發(fā)去推出結(jié)論的過程。程。 推理推理所用的事實：所用的事實： 初始初始證據(jù)：證據(jù)：推理前用戶提供的 中間結(jié)論：中間結(jié)論：推理過程中所得到的 推理推理過程：過程：由推理機(jī)來由推理機(jī)來完成完成 推理推理的兩個基本問題的兩個基本問題 推理的方法

2、：推理的方法：解決解決前提和結(jié)論的邏輯關(guān)系，不確定性傳遞前提和結(jié)論的邏輯關(guān)系，不確定性傳遞 推理的控制策略：推理的控制策略：解決推理方向，沖突消解策略解決推理方向，沖突消解策略推理推理方法及其方法及其分類分類 演繹推理：演繹推理： 一般一般到個別的推理到個別的推理方法：方法：從從已知的一般性知識出發(fā)，去推出蘊(yùn)已知的一般性知識出發(fā)，去推出蘊(yùn)含在這些已知知識中的適合于某種個別情況的含在這些已知知識中的適合于某種個別情況的結(jié)論結(jié)論 核心核心：三段論。三段論。 常用常用的的三段論包括：三段論包括：大前提：大前提：已知的一般性知識或推理過程得到的判斷小前提：小前提：關(guān)于某種具體情況或某個具體實例的判斷結(jié)

3、論：結(jié)論：由大前提推出的，并且適合于小前提的判斷。 例如，有如下三個判斷：例如，有如下三個判斷： 計算機(jī)系的學(xué)生都會編程序；計算機(jī)系的學(xué)生都會編程序； （一般性知識）（一般性知識） 程強(qiáng)是計算機(jī)系的一位學(xué)生；程強(qiáng)是計算機(jī)系的一位學(xué)生； （具體情況）（具體情況） 程強(qiáng)會編程序。程強(qiáng)會編程序。 （結(jié)論）（結(jié)論） 歸納推理：歸納推理：由由個別到一般的推理個別到一般的推理方法方法完全歸納推理：完全歸納推理：是是指在進(jìn)行歸納時需要考察相應(yīng)事物的指在進(jìn)行歸納時需要考察相應(yīng)事物的全部對象全部對象，并根，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性據(jù)這些對象是否都具有某種屬性，推出該類事物是否

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

5、系的學(xué)生，就一定會編程序。推理推理方法及其方法及其分類分類類比類比歸納推理：歸納推理：是在兩個或兩類事物有許多屬性都相同或相似的基屬性都相同或相似的基礎(chǔ)上礎(chǔ)上，推出它們在其他屬性上也相同推出它們在其他屬性上也相同或相似的一種歸納推理設(shè)設(shè)A、B分別是兩類事物的集合：分別是兩類事物的集合： A=a1,a2, B=b1,b2,并設(shè)并設(shè)ai與與bi總是成對出現(xiàn)，且當(dāng)總是成對出現(xiàn)，且當(dāng)ai有屬性有屬性P時，時，bi就有屬性就有屬性Q與此對應(yīng)，即與此對應(yīng)，即 P(ai)Q(bi) i=1,2,.則則當(dāng)當(dāng)A與與B中有一新的元素對出現(xiàn)時，若已知中有一新的元素對出現(xiàn)時，若已知a有屬性有屬性P，b有屬性有屬性Q，

6、即，即 P(a)Q(b)類比類比歸納推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個或兩類事物的歸納推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關(guān)程度。關(guān)程度。推理推理方法及其方法及其分類分類演繹推理與歸納推理的區(qū)別演繹推理與歸納推理的區(qū)別演繹推理：演繹推理：在已知領(lǐng)域內(nèi)的一般性知識的前提下，通過演繹或者不能增殖新不能增殖新知識：知識：所得出的結(jié)論蘊(yùn)含在一般性知識的前提中，推理過程是將已有事實揭露出來歸納推理歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的增殖新知識的增殖

7、新知識的過程：過程：是由個別事物或現(xiàn)象推出一般性知識的過程。推理推理方法及其方法及其分類分類 按按所用知識的確定性分類所用知識的確定性分類 確定性確定性推理推理 vs. 不確定性推理不確定性推理 按按推理過程的單調(diào)性分類推理過程的單調(diào)性分類 單調(diào)推理單調(diào)推理 vs. 非單調(diào)推理非單調(diào)推理 單調(diào)：不會由于新知識的加入否定前面的單調(diào)：不會由于新知識的加入否定前面的結(jié)論結(jié)論 (不能不能取消原有的取消原有的結(jié)論結(jié)論) 非非單調(diào)：知識不完全情況下，某些新知識的加入會否單調(diào)：知識不完全情況下，某些新知識的加入會否定前面的定前面的結(jié)論結(jié)論推理推理方法及其方法及其分類分類推理推理的控制策略及其分類的控制策略及

8、其分類推理的控制策略推理的控制策略 推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略 推理的控制策略是指推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達(dá)到目標(biāo)的策略如何使用領(lǐng)域知識使推理過程盡快達(dá)到目標(biāo)的策略控制控制策略的分類策略的分類 推理策略主要推理策略主要解決推理方向、沖突消解等問題解決推理方向、沖突消解等問題，如推理方向控制策略、，如推理方向控制策略、求解策略、限制策略、沖突消解策略等求解策略、限制策略、沖突消解策略等 推理推理方向控制方向控制策略：策略：確定推理的控制方向，可分為正向推理、逆向推理、混合推理及雙

9、向推理。 求解求解策略策略：確定是僅求一個解、求所有解、還是最優(yōu)解等。 限制限制策略：策略：對推理的深度、寬度、時間、空間等進(jìn)行的限制。 沖突消解沖突消解策略：策略：當(dāng)推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。 搜索策略主要搜索策略主要解決推理線路、推理效果、推理效率等解決推理線路、推理效果、推理效率等問題問題正向推理正向推理逆向推理逆向推理混合混合推理推理混合混合推理推理 把把正向推理和逆向推理結(jié)合起來所進(jìn)行的正向推理和逆向推理結(jié)合起來所進(jìn)行的推理推理 用于解決用于解決較復(fù)雜較復(fù)雜問題。問題。混合推理的方法混合推理的方法 先先正向后正向后逆向：逆向：先進(jìn)

10、行正向推理，從已知事實出發(fā)推出部分結(jié)果，然先進(jìn)行正向推理，從已知事實出發(fā)推出部分結(jié)果，然后再用逆向推理對這些結(jié)果進(jìn)行證實或提高它們的可信度。后再用逆向推理對這些結(jié)果進(jìn)行證實或提高它們的可信度。 先逆向后先逆向后正向：正向：先先進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正向推理對這些中間假設(shè)進(jìn)行證實。然后再用正向推理對這些中間假設(shè)進(jìn)行證實。 雙向雙向混合：混合：正向推理和逆向推理同時進(jìn)行，使推理過程在中間的某一正向推理和逆向推理同時進(jìn)行，使推理過程在中間的某一步結(jié)合起來。步結(jié)合起來。本章內(nèi)容本章內(nèi)容 推理推理的基本概念的基本概念 推理推理

11、的邏輯基礎(chǔ)的邏輯基礎(chǔ) 自然演繹推理自然演繹推理 歸結(jié)推理歸結(jié)推理謂詞謂詞公式的公式的解釋解釋（語義）（語義） 命題邏輯命題邏輯 vs. 謂詞邏輯謂詞邏輯 命題邏輯：命題邏輯：命題符號P，Q代表一定的命題，看不出關(guān)系，表達(dá)不出共同特征 謂詞邏輯：謂詞邏輯： 可表示關(guān)系。如：Weather(Tuesday，Rain） 允許包含變元。如： Weather（X，Rain） 命題公式命題公式的的解釋：解釋： 命題公式命題公式的一個解釋就是對該謂詞公式中的一個解釋就是對該謂詞公式中各個命題變各個命題變元的元的一次真一次真值值指派指派 可根據(jù)解釋求出該命題公式可根據(jù)解釋求出該命題公式的的真值真值 謂詞公式謂

12、詞公式的解釋的解釋： 先考慮這些先考慮這些個體常量和函數(shù)在個體域上的取值個體常量和函數(shù)在個體域上的取值， 然后根據(jù)其具體然后根據(jù)其具體取值為取值為謂詞分別指派真值謂詞分別指派真值。 設(shè)設(shè)D是謂詞公式是謂詞公式P的非空個體域，若對的非空個體域，若對P中的個體常量、函數(shù)和中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：謂詞按如下規(guī)定賦值：為為每個個體常量指派每個個體常量指派D D中的一個元素；中的一個元素；對對每一個變元，指派每一個變元，指派D D的一個非空集合，這是該變元的變域的一個非空集合，這是該變元的變域( (個個體域體域) )；為為每個每個n n元函數(shù)指派一個從元函數(shù)指派一個從D Dn n到到D

13、D的一個映射，其中的一個映射，其中 D Dn n =(x=(x1 1, x, x2 2, , x, , xn n)| x)| x1 1, x, x2 2, , x, , xn nDD為為每個每個n n元謂詞指派一個從元謂詞指派一個從D Dn n到到FF，TT的映射。的映射。則稱這些指派為則稱這些指派為P P在在D D上的一個解釋上的一個解釋I I謂詞謂詞公式的公式的解釋解釋（語義）（語義）謂詞公式的謂詞公式的解釋解釋（語義）（語義）例例1 1：設(shè)設(shè)個體域個體域D=1, 2D=1, 2，求，求公式公式A=(A=(x)( y)P(x, y)x)( y)P(x, y)在在D D上上的解釋，并指出在每

14、一種解釋下公式的解釋，并指出在每一種解釋下公式A A的真值。的真值。 解解：由于公式由于公式A A中沒有包含個體常量和函數(shù)，故可直接為謂詞指中沒有包含個體常量和函數(shù)，故可直接為謂詞指派真值，設(shè)有派真值，設(shè)有把把P P理解為一個元素為二元組的集合理解為一個元素為二元組的集合 P=(1,1),(2,1) P=(1,1),(2,1) P(1,1) P(1,2) P(2,1) P(2,2) T F T F謂詞公式的謂詞公式的解釋解釋（語義）（語義）例例1 1：設(shè)設(shè)個體域個體域D=1, 2D=1, 2，求，求公式公式A=(A=(x)( y)P(x, y)x)( y)P(x, y)在在D D上上的解釋，并

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

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

17、真值為的真值為F;F;即對即對x x在在D D上的任意取值，不存在一個上的任意取值，不存在一個y y使得使得P(x,y)P(x,y)的真值為的真值為T T。因此，在此解釋下公式因此，在此解釋下公式A A的真值為的真值為F F。 P(1,1) P(1,2) P(2,1) P(2,2) TT F F謂詞公式的謂詞公式的解釋解釋（語義）（語義）公式公式A=(A=(x)( y)P(x, y)x)( y)P(x, y)P=(1,1),(1,2)P=(1,1),(1,2)例例2 設(shè)個體域設(shè)個體域D=1, 2，給出公式，給出公式B=(x)P(f(x), a)在在D上的解釋，并指出上的解釋，并指出在該解釋下公

18、式在該解釋下公式B的真值。的真值。解解：設(shè)對個體常量：設(shè)對個體常量a和函數(shù)和函數(shù)f(x)的值指派為：的值指派為：對謂詞的真值指派為：對謂詞的真值指派為：根據(jù)根據(jù)此此解釋下有解釋下有 當(dāng)當(dāng)x=1時，時，a=1使使P(1,1)=T 當(dāng)當(dāng)x=2時，時，a=1 使使P(2,1)=T即對即對x在在D上的任意取值，都存在上的任意取值，都存在a=1使使P(f(x), a)的真值為的真值為T。因此，在此。因此，在此解釋下公式解釋下公式B的真值為的真值為T?？梢钥梢钥闯觯闯?，謂詞公式的真值都是針對某一個解釋而言的謂詞公式的真值都是針對某一個解釋而言的，它可能在某一，它可能在某一個解釋下真值為個解釋下真值為T，

19、而在另一個解釋下為，而在另一個解釋下為F。af(1)f(2)112P(1,1)P(1,2)P(2,1)P(2,2)T T謂詞公式的謂詞公式的解釋解釋（語義）（語義）謂詞謂詞公式的永真性和可滿足性公式的永真性和可滿足性 永真性：永真性：如果謂詞公式P對非空個體域D上的任一解釋都取得真值T，則稱P在D 上是永真的；如果P在任何非空個體域上均是永真的，則稱P永真。 可滿足性（相容性）：可滿足性（相容性）：對于謂詞公式P，如果至少存在D上的一個解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。 永假性（不可滿足性）：永假性（不可滿足性）：如果謂詞公式P對非空個體域D上的任一解釋都取真值F

20、，則稱P在D上是永假的；如果P在任何非空個體域上均是永假的，則稱P永假。謂詞公式的等價性謂詞公式的等價性 謂詞公式的等價性：謂詞公式的等價性：設(shè)設(shè)P與與Q是是D上的兩個謂詞公式，若對上的兩個謂詞公式，若對D上的任意解釋，上的任意解釋，P與與Q都有都有相同的真值，則稱相同的真值，則稱P與與Q在在D 上是等價的上是等價的。如果如果D是任意非空個體域，則稱是任意非空個體域，則稱P與與Q是等價的，記作是等價的，記作PQ。 (1) 雙重否定律雙重否定律 P P(2) 交換律交換律 (PQ) (QP)， ( PQ) ( QP)(3) 結(jié)合律結(jié)合律 (PQ)R P(QR) (PQ)R P(QR)(4) 分配

21、律分配律 P(QR) (PQ)(PR) P(QR) (PQ)(PR)(5)德摩根德摩根(否定否定)律律 (PQ) P Q (PQ) P Q(6) 吸收律吸收律 P(PQ) P P(PQ) P(7) 補(bǔ)余律補(bǔ)余律 P P T, P P F (8) 連詞化歸律連詞化歸律 PQ PQ PQ (PQ)(QP) PQ (PQ)( Q P)(9) 量詞轉(zhuǎn)換律量詞轉(zhuǎn)換律 (x)P (x)( P) (x)P (x) ( P)(10) 量詞分配律量詞分配律 (x) (PQ) (x)P(x)Q (x) (PQ) (x)P(x)Q置換律：置換律：(PQ) (QP)常用的等價式常用的等價式謂詞公式的永真蘊(yùn)含式謂詞公式

22、的永真蘊(yùn)含式永真蘊(yùn)含：永真蘊(yùn)含：對對謂詞公式謂詞公式P P和和Q Q，如果，如果PQPQ永真，則稱永真，則稱P P 永真蘊(yùn)含永真蘊(yùn)含Q Q，且稱，且稱Q Q為為P P的的邏輯結(jié)論，邏輯結(jié)論，P P為為Q Q的前提，記作的前提，記作P P Q Q。 (1) 化簡式化簡式 PQ P， PQ Q (2) 附加式附加式 P PQ， Q PQ (3) 析取三段論析取三段論 P, PQ Q (4) 假言推理假言推理 P, PQ Q (5) 拒取式拒取式 Q, PQ P (6) 假言三段論假言三段論 PQ, QR PR (7) 二難推理二難推理 PQ, PR, QR R (9) 存在固化存在固化 (x)P(

23、x) P(y)其其中，中，y是個體域中某一個可以使是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公式中的存在量詞。為真的個體，依此可消去謂詞公式中的存在量詞。等價等價式和永真蘊(yùn)含式也式和永真蘊(yùn)含式也稱推理稱推理規(guī)則規(guī)則謂詞公式的范式謂詞公式的范式范式范式是謂詞公式的標(biāo)準(zhǔn)形式。在謂詞邏輯中，范式分為兩種：是謂詞公式的標(biāo)準(zhǔn)形式。在謂詞邏輯中，范式分為兩種：前束范式前束范式 例如例如，(x) (y) (z)(P(x)Q(y,z)R(x,z)是前束范式。是前束范式。 任任一謂詞公式均可化為與其對應(yīng)的一謂詞公式均可化為與其對應(yīng)的前束范式前束范式Skolem范式范式 任一謂詞公式均可化為與其對應(yīng)

24、的任一謂詞公式均可化為與其對應(yīng)的Skolem范式范式設(shè)設(shè)F為一謂詞公式，如果其中的所有量詞為一謂詞公式，如果其中的所有量詞均非否定地均非否定地出現(xiàn)在公式的最前面，且它出現(xiàn)在公式的最前面，且它們的轄域為整個公式，則稱們的轄域為整個公式，則稱F為前束范式。一般形式：為前束范式。一般形式： (Q1x1)(Qnxn)M(x1,x2,xn)其中，其中，Qi(i=1,2,n)為前綴，它是一個由全稱量詞或存在量詞組成的量詞串；為前綴，它是一個由全稱量詞或存在量詞組成的量詞串； M(x1,x2,xn)為母式，它是一個不含任何量詞的謂詞公式。為母式，它是一個不含任何量詞的謂詞公式。如果前束范式如果前束范式中中不

25、包含存在量詞且不包含存在量詞且母母式式M M是是“合取范式合取范式”，則稱這種形式的謂詞則稱這種形式的謂詞公式為公式為SkolemSkolem范式。范式。置換置換可簡單的理解為是在一個謂詞公式中可簡單的理解為是在一個謂詞公式中置換置換置換置換是形是形如如 t1/x1,t2/x2,tn/xn 的的有限集合。其中，有限集合。其中，t1,t2,tn是項是項；x1,x2, xn是互不相同的變元；是互不相同的變元；ti/xi表示用表示用ti替換替換xi。并且。并且要求要求ti與與xi不能相不能相同，同，xi不能循環(huán)地出現(xiàn)在不能循環(huán)地出現(xiàn)在tj（j=1n）中）中。a/x, c/y, f(b)/z g(y)

26、/x, f(x)/y x與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當(dāng)用g(y)置換x,用f(g(y)置換y時，既沒有消去x，也沒有消去yg(a)/x, f(x)/y 用g(a)置換x ，用f(g(a)置換y ，則消去了x和y通常，置換是用希臘字母通常，置換是用希臘字母、 、 等來表示的等來表示的設(shè)設(shè)=t1/x1,t2/x2,tn/xn是一個置換，是一個置換，F(xiàn)是一個謂詞公式，把公式是一個謂詞公式，把公式F中出現(xiàn)中出現(xiàn)的所有的所有xi換成換成ti(i=1,2,n)，得到一個新的公式，得到一個新的公式G，稱，稱G為為F在置換在置換下的下的例示例示，記作，記作G=F。一個謂詞公式的任何例示都是該公式的邏輯結(jié)論一

27、個謂詞公式的任何例示都是該公式的邏輯結(jié)論合一合一: 尋找尋找項對變量的置換，使兩個謂詞公式項對變量的置換，使兩個謂詞公式一致一致例如，設(shè)有公式集例如，設(shè)有公式集F=P(x,y,f(y), P(a,g(x),z)，則，則=a/x, g(a)/y, f(g(a)/z是它的一個合一是它的一個合一。 一一個公式集的合一不是唯一個公式集的合一不是唯一的的，但最一般合一是唯一的。，但最一般合一是唯一的。合一合一設(shè)有公式集設(shè)有公式集F=F1, F2,Fn，若存在一個置換，若存在一個置換，可使，可使 F1=F2=Fn，則稱則稱是是F的一個合一。稱的一個合一。稱F1,F2,Fn是可合一的是可合一的設(shè)設(shè)是公式集是

28、公式集F的一個合一，如果對的一個合一，如果對F的任一個合一的任一個合一都存都存在一個置換在一個置換，使得，使得=，則稱，則稱是一個是一個最一般合一最一般合一合一合一 如何高效實現(xiàn)合一算法呢？如何高效實現(xiàn)合一算法呢？提示：由于謂詞、函數(shù)等只是符號，合一過程中沒有使提示：由于謂詞、函數(shù)等只是符號，合一過程中沒有使用其語義信息，僅僅使用其語法信息，因此，將其轉(zhuǎn)換用其語義信息，僅僅使用其語法信息，因此，將其轉(zhuǎn)換成成list的表示形式的表示形式合一的算法可以通過遞歸實現(xiàn)本章內(nèi)容本章內(nèi)容 推理推理的基本概念的基本概念 推理推理的邏輯基礎(chǔ)的邏輯基礎(chǔ) 自然演繹推理自然演繹推理 歸結(jié)推理歸結(jié)推理自然自然演繹推理

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

30、 假言推理 因此，Q為真機(jī)器自動推理機(jī)器自動推理 能否設(shè)計一個算法，自動證明能否設(shè)計一個算法，自動證明PQ永永真。真。 如果這個算法存在，則證明過程，變?nèi)绻@個算法存在，則證明過程，變成了一個計算過程成了一個計算過程歸結(jié)歸結(jié)演繹推理演繹推理在在人工智能中人工智能中，很多問題，很多問題都可以轉(zhuǎn)化為一個定理證明都可以轉(zhuǎn)化為一個定理證明問題問題，即對即對前提前提P和結(jié)論和結(jié)論Q，證明，證明PQ永永真。真。 途徑途徑1：證明PQ在任何一個非空的個體域上都永真 （非常困難，甚至不可實現(xiàn)）的 途徑途徑2：反證法. 把把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。即

31、：證明 (PQ) 或 P Q是不可滿足 魯賓遜魯賓遜歸結(jié)原理歸結(jié)原理(亦亦稱為消解稱為消解原理原理): 魯賓遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的基于邏輯的“反證法” 使定理證明的機(jī)械化成為現(xiàn)實。歸結(jié)演繹推理歸結(jié)演繹推理是一種基于魯賓遜（是一種基于魯賓遜（Robinson）歸結(jié)歸結(jié)原理的機(jī)器推理技術(shù)。原理的機(jī)器推理技術(shù)。John Alan RobinsonJ. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 1965, 12(1):23

32、-41機(jī)器自動推理機(jī)器自動推理 子句集的化簡子句集的化簡 歸結(jié)歸結(jié)子句和子句集子句和子句集 魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理的基礎(chǔ)是的基礎(chǔ)是子句集子句集 子句子句和子句集和子句集 文字：文字：原子謂詞公式及其否定 例如：例如：P(x)、Q(x)、 P(x)、 Q(x) 子句：子句：任何文字的析取式 例如：例如：P(x)Q(x)，P(x，f(x)Q(x，g(x) 空子句：空子句：不含任何文字的子句，通常被一般被記為或NIL 空子空子句是永假的，不可滿足的句是永假的，不可滿足的。 子句子句集：集：由子句或空子句所構(gòu)成的集合子句集的化簡子句集的化簡 任何任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化

33、一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集成相應(yīng)的子句集。 化化簡簡步驟：步驟： (1) 消去連接詞消去連接詞“”和和“” 反復(fù)使用例如：例如： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)經(jīng)等價變化后為經(jīng)等價變化后為 (x)(y)P(x,y) (y)(Q(x,y)R(x,y)(2) 減少否定符號的轄域減少否定符號的轄域反復(fù)使用將每個否定符號“”移到緊靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。例如例如： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)經(jīng)經(jīng)等價變換后等價變換后為為 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)

34、子句集的化簡子句集的化簡(3) 對變元標(biāo)準(zhǔn)化對變元標(biāo)準(zhǔn)化在一個量詞的轄域內(nèi)，把謂詞公式中，使不同量詞約束的變元有不同的名字。 例如例如：(x)(y)P(x，y)(y)( Q(x，y) R(x，y) 經(jīng)變換后為經(jīng)變換后為 (x)(y)P(x，y)(z)( Q(x，z) R(x，z)(4) 化為前束范式化為前束范式不能改變其相對順序不能改變其相對順序 移動的可行性：由于變元已被標(biāo)準(zhǔn)化，每個量詞都有自己的變元，消除了任何由變元引起沖突的可能。例如例如，(x)(y)P(x，y)(z)( Q(x，z) R(x，z)化為化為前束范式后前束范式后為為 (x)(y) (z)(P(x，y)( Q(x，z) R(

35、x，z)子句集的化簡子句集的化簡(5) 消去存在量詞消去存在量詞 存在量詞存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞量詞）：）：只要用一個，就可消去該存在量詞 若若存在量詞位于一個或多個全稱量詞的轄域內(nèi)存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如 (x1)(xn) (y)P(x1，x2 , xn ,y)則需要，然后再消去該存在量詞例如例如， (x)(y) (z)(P(x，y)( Q(x，z) R(x，z)替換替換后的式子后的式子為為 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x)子句集的化簡子句集的化簡(6) 化為化為Sko

36、lem標(biāo)準(zhǔn)標(biāo)準(zhǔn)形形 Skolem標(biāo)準(zhǔn)形: (x1)(xn) M(x1,x2,xn)例如例如，為為 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x) 化為化為Skolem標(biāo)準(zhǔn)標(biāo)準(zhǔn) 形后為形后為 (x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)(7) 消去全稱量詞消去全稱量詞 由于，并且全稱量詞的，因此。 剩下剩下的母式，仍假設(shè)其變元是被全稱量詞量化的的母式，仍假設(shè)其變元是被全稱量詞量化的。例如，例如，(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x) 消消去全去全稱量詞后稱量詞后為為 (P(x,f(x)Q(x,g(x) (P(x,f(x

37、)R(x,g(x)子句集的化簡子句集的化簡(8) 消去合取詞消去合取詞，把母式用子句集的形式表示出來例如，例如，(P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x)的的子句集中包含以下兩個子句子句集中包含以下兩個子句 P(x,f(x)Q(x,g(x) P(x,f(x)R(x,g(x)(9) 更換變量名稱更換變量名稱例如例如，對前面的公式，可把第二個子句集中的變元名，對前面的公式，可把第二個子句集中的變元名x更換為更換為y，得到如下子句集得到如下子句集 P(x,f(x)Q(x,g(x) P(y,f(y)R(y,g(y)子句集的化簡子句集的化簡練習(xí)：子句集化簡練習(xí)：子句集化簡1.

38、( X) (a(X)b(X) c(X, l )( Y) (Zc(Y，Z)d(X,Y) ) ) ( X) (e(X) 2.( X) ( a(X) b(X)c(X，l)( y) ( Zc(Y,Z)d(X,Y)(）(e(X)3.( X) ( a(X) b(X)c(X, l)( Y) ( Z) c(Y,Z)d(X,Y)( X)(e(X)4.( X) (a(X) b(X)c(X, l ) ( Y) ( Z) c(Y,Z)d(X,Y)( W) (e(W) 所有量詞移到最左邊而不改變其次序所有量詞移到最左邊而不改變其次序 5.( X)( Y)( Z)( W) ( a(X) b(X)c(X,l) c(Y,Z)

39、d(X,Y)e(W)前束范式前束范式Skolem標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化去掉所有的存在量詞去掉所有的存在量詞練習(xí)：子句集化簡練習(xí)：子句集化簡6. ( X)( Z)( W) (a(X) b(X)c(X,l)c (f(X),Z)d(X,f(X)e(W) 5.( X)(彐彐Y)( Z)( W) ( a(X) b(X)c(X,l) c(Y,Z)d(X,Y)e(W)Skolem標(biāo)準(zhǔn)化后標(biāo)準(zhǔn)化后去掉全稱量詞去掉全稱量詞7.( a(X) b(X)c(X, l) c(f(X), Z)d(X, f(X)e(W)8.a(X) b(X)c(X,l)e(W)a(X) b(X) c(f(X), Z)d(X, f(X)e(W)轉(zhuǎn)換成

40、析取式的合取轉(zhuǎn)換成析取式的合取每個合取式為一個分離的子句每個合取式為一個分離的子句9a: a(X) b(X)c(X,l)e(W)9b: a(X) b(X) c(f(X), Z)d(X, f(X)e(W)把分離的變元歸一化把分離的變元歸一化10a: a(X) b(X)c(X,l)e(W)10b: a(U) b(U) c(f(U), Z) d(U, f(U)e(V)子句集的應(yīng)用子句集的應(yīng)用 注意：注意： 由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化化簡簡后的標(biāo)準(zhǔn)子句集是不唯一的后的標(biāo)準(zhǔn)子句集是不唯一的。 Skolem化并不影響原謂詞公式的永假性化并不影響原謂詞公式的永假性。 Skol

41、em化后得到的公式與原公式化后得到的公式與原公式不等價不等價，但具有，但具有相同的不可相同的不可滿足性滿足性定理定理 設(shè)有謂詞公式設(shè)有謂詞公式F F，其標(biāo)準(zhǔn)子句集為，其標(biāo)準(zhǔn)子句集為S S，則，則F F為不可為不可滿足的充要條件是滿足的充要條件是S S為不可滿足的。為不可滿足的。魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-基本基本思想思想 兩兩個關(guān)鍵個關(guān)鍵: 子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的；一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。 魯魯濱遜歸結(jié)原理基本思想濱遜歸結(jié)原理基本思想 首先首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴(kuò)充把欲證明問題的結(jié)論否定，并

42、加入子句集，得到一個擴(kuò)充的子句集的子句集S。 然后然后設(shè)法檢驗子句集設(shè)法檢驗子句集S是否含有空子句，若含有空子句，則表是否含有空子句，若含有空子句，則表明明S是不可滿足的是不可滿足的； 若若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止子句進(jìn)行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-命題邏輯命題邏輯的的歸結(jié)歸結(jié) 歸結(jié)歸結(jié)推理的核心是求兩個子句的歸結(jié)式推理的核心是求兩個子句的歸結(jié)式 歸結(jié)歸結(jié)式的式的定義定義: 若P是原子謂詞公式，則稱P與P為。 設(shè)C1和C2是子句

43、集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個新的子句C12，則稱這一過程為歸結(jié)歸結(jié)，稱C12為C1和C2的歸結(jié)式歸結(jié)式，稱C1和C2為C12的。 例例: 設(shè)設(shè)C1=PQR，C2=PS，求，求C1和和C2的歸結(jié)式的歸結(jié)式C12。 解：這里L(fēng)1=P，L2=P，通過歸結(jié)可以得到 C12= QRS 例例: 設(shè)設(shè)C1=Q，C2=Q，求，求C1和和C2的歸結(jié)式的歸結(jié)式C12。 解：這里L(fēng)1=Q，L2=Q，通過歸結(jié)可以得到 C12= NIL例例: 設(shè)設(shè)C1 =P Q ，C2=Q，C3=P，求求C1、C2、

44、C3的歸結(jié)式的歸結(jié)式C123。解解：若先對：若先對C1、C2歸結(jié)，可得到歸結(jié)，可得到 C12=P然后再對然后再對C12和和C3歸結(jié)，得到歸結(jié)，得到 C123=NIL歸結(jié)過程可用歸結(jié)過程可用歸結(jié)樹歸結(jié)樹表示表示歸結(jié)過程不唯一歸結(jié)過程不唯一: 如果如果改變歸結(jié)改變歸結(jié)順序，同樣可以得到相同的順序，同樣可以得到相同的結(jié)果結(jié)果P QQP P NILP Q P QQ NIL魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-命題邏輯命題邏輯的的歸結(jié)歸結(jié)證明：設(shè)設(shè)C1=LC1 ，C2=LC2關(guān)于解釋關(guān)于解釋I為為真真只需證明只需證明C12= C1 C2關(guān)于解釋關(guān)于解釋I也為也為真真因為，對于解釋I，L和L中必有一個為假若L為假

45、，則必有C1為真，不然就會使C1為假，這將與前提假設(shè)C1為真矛盾，因此只能有C1為真。同理，若L為假，則必有C2為真。因此，必有C12= C1C2關(guān)于解釋I也為真。即C12是C1和C2的邏輯結(jié)論。魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-命題邏輯命題邏輯的的歸結(jié)歸結(jié)定理：定理：歸結(jié)式歸結(jié)式C C1212是其親本子句是其親本子句C C1 1和和C C2 2的的邏輯邏輯結(jié)論結(jié)論證明證明：設(shè)S= C1，C2，C3，Cn，C12是C1和C2的歸結(jié)式，則用C12代替C1和C2后可得到一個新的子句集 S1= C12，C3，, Cn。設(shè)S1是不可滿足的，則對不滿足S1的任一解釋I，都可能有以下兩種情況： 解釋I使C12

46、為真，則C3，Cn中必有一個為假，即S是不可滿足的。 解釋I使C12為假，即C12為真，根據(jù)上述定理有 (C1C2)永真，即C1C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。 因此可以得出 S1的不可滿足性S的不可滿足性魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-命題邏輯命題邏輯的的歸結(jié)歸結(jié)推論推論1：設(shè)設(shè)C1和和C2是子句集是子句集S中的兩個子句，中的兩個子句，C12是是C1和和C2的歸的歸結(jié)式，若用結(jié)式，若用C12代替代替C1和和C2后得到新的子句集后得到新的子句集S1，則由，則由S1的不的不可滿足性可以推出原子句集可滿足性可以推出原子句集S的不可滿足性。即：的不可滿足性。即：先先證

47、明證明 設(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有 (C1C2)永真，即C1C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。由此可見S與S2的不可滿足性是等價的。即 S的不可滿足性 S2的不可滿足性魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-命題邏輯命題邏輯的的歸結(jié)歸結(jié)推論推論2

48、：設(shè)設(shè)C1和和C2是子句集是子句集S中的兩個子句，中的兩個子句，C12是是C1和和C2的歸的歸結(jié)式，若把結(jié)式，若把C12加入加入S中得到新的子句集中得到新的子句集S2，則，則S與與S2的不可滿的不可滿足性是等價的。即：足性是等價的。即：S2的不可滿足性的不可滿足性S的不可滿足性的不可滿足性 為為證明子句集證明子句集S S的不可滿足性，只要對其中可進(jìn)行歸結(jié)的子的不可滿足性，只要對其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入到子句集句進(jìn)行歸結(jié)，并把歸結(jié)式加入到子句集S S中，或者用歸結(jié)式中，或者用歸結(jié)式代替他的親本子句，然后對新的子句集證明其不代替他的親本子句，然后對新的子句集證明其不可滿足性可滿

49、足性即即可可。 如果如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集得到原子句集S S是不可滿足的結(jié)論。是不可滿足的結(jié)論。 在在命題邏輯中，對不可滿足的子句集命題邏輯中，對不可滿足的子句集S S，歸結(jié)原理，歸結(jié)原理是是的的。魯魯濱遜濱遜歸結(jié)原理歸結(jié)原理-命題邏輯命題邏輯的的歸結(jié)歸結(jié)定理定理 子句集子句集S S是不可滿足的，當(dāng)且僅當(dāng)存在一個從是不可滿足的，當(dāng)且僅當(dāng)存在一個從S S到空到空子句的歸結(jié)過程。子句的歸結(jié)過程。例例 設(shè)已知的公式集為設(shè)已知的公式集為P, (PQ)R, (ST)Q, T，求證結(jié)論，求證結(jié)論R。解：假設(shè)結(jié)論R為假

50、, 將R加入公式集，并化為子句集 S=P,PQR, SQ, TQ, T, R其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。該樹根為空子句。其含義為：先假設(shè)子句集S中的所有子句均為真，即原公式集為真,R也為真；然后利用歸結(jié)原理，對子句集進(jìn)行歸結(jié)，并把所得的歸結(jié)式并入子句集中；重復(fù)這一過程，最后歸結(jié)出了空子句。P QR RP QPQT QTTNIL魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-命題邏輯的歸結(jié)命題邏輯的歸結(jié) 在在謂詞邏輯中，由于子句集中的謂詞一般都含有謂詞邏輯中，由于子句集中的謂詞一般都含有變元變元，因此，因此不能不能象命題邏輯那樣象命題邏輯那樣直接消去互補(bǔ)文字直接消去互補(bǔ)文字。而需要先用一個。而需要先用一個對

51、變元進(jìn)行代換，然后才能進(jìn)行歸結(jié)。對變元進(jìn)行代換，然后才能進(jìn)行歸結(jié)。 謂詞邏輯謂詞邏輯中的歸結(jié)中的歸結(jié)式：式：魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理謂詞謂詞邏輯的歸結(jié)邏輯的歸結(jié)設(shè)設(shè)C1和和C2是兩個是兩個沒有公共變元沒有公共變元的子句，的子句，L1和和L2分別是分別是C1和和C2中中的文字。如果的文字。如果L1和和L2存在最一般合一存在最一般合一，則稱，則稱 C12=(C1- L1)( C2- L2)為為C1和和C2的的二元歸結(jié)式二元歸結(jié)式，而，而L1和和L2為歸結(jié)式上的文字為歸結(jié)式上的文字。例例 設(shè)設(shè)C1=P(a)R(x)，C2=P(y)Q(b)，求，求 C12解：取L1= P(a), L2=P(y)，

52、則L1和L2的最一般合一是=a/y。 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)魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-謂詞邏輯謂詞邏輯的歸結(jié)的歸結(jié)例例 設(shè)設(shè)C1=P(x)Q(a)，C2=P(b)R(x) ，求，求 C12解：由于C1和C2有相同的變元x，不符合定義3.20的要求。為了進(jìn)行歸結(jié)，需要修改C2中變元的名字，令C2=P(b)R(y)。此時L1= P(x), L2 =P(b)，L1和L2的最一般合一是=b/x。則有 C12=( C1-L1) (C2-L2) =

53、(P(b), Q(a)-P(b) (P(b), R(y)-P(b) =(Q(a) (R(y) = Q(a), R(y) =Q(a)R(y)魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-謂詞邏輯謂詞邏輯的歸結(jié)的歸結(jié)例例 設(shè)設(shè)C1=P(x)Q(b)，C2=P(a)Q(y)R(z) 解：對C1和C2通過最一般合一（=a/x, b/y）的作用，可以得到兩個互補(bǔ)對。 注意：求歸結(jié)式不能同時消去兩個互補(bǔ)對，這樣的結(jié)果不是二注意：求歸結(jié)式不能同時消去兩個互補(bǔ)對，這樣的結(jié)果不是二元歸結(jié)式。如在元歸結(jié)式。如在=a/x, b/y下，若同時消去兩個互補(bǔ)對，所得的下，若同時消去兩個互補(bǔ)對，所得的R(z)不是不是C1和和C2的二元歸結(jié)

54、式的二元歸結(jié)式。魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-謂詞邏輯謂詞邏輯的歸結(jié)的歸結(jié)例例: 設(shè)設(shè)C1=P(x)P(f(a)Q(x) ，C2=P(y)R(b)，求，求C12 解：對參加歸結(jié)的某個子句，若其內(nèi)部有可合一的文字，則在若其內(nèi)部有可合一的文字，則在進(jìn)行歸結(jié)之前應(yīng)先對這些文字進(jìn)行合一進(jìn)行歸結(jié)之前應(yīng)先對這些文字進(jìn)行合一。 C1中有可合一的文字P(x)與P(f(a)，用它們的最一般合一=f(a)/x進(jìn)行代換，可得到 C1=P(f(a)Q(f(a) 對C1與C2進(jìn)行歸結(jié)。選L1= P(f(a), L2 =P(y)，L1和L2的最一般合一是=f(a)/y，則可得到C1和C2的二元歸結(jié) C12=R(b)Q(f

55、(a)若若子句子句C中有兩個或兩個以上的文字具有最一般合一中有兩個或兩個以上的文字具有最一般合一，則稱，則稱C為為子句子句C的的因子因子。如果。如果C是一個單文字，則稱它為是一個單文字，則稱它為C的的單元因子單元因子。魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-謂詞邏輯謂詞邏輯的歸結(jié)的歸結(jié)定義定義 若若C1和和C2是無公共變元的子句，則是無公共變元的子句，則 C1和和C2的二元歸結(jié)式的二元歸結(jié)式; C1和和C2的因子的因子C22的二元歸結(jié)式；的二元歸結(jié)式； C1的因子的因子C11和和C2的二元歸結(jié)式；的二元歸結(jié)式； C1的因子的因子C11和和C2的因子的因子C22的二元歸結(jié)式。的二元歸結(jié)式。 這這四種二元歸

56、結(jié)式都是子句四種二元歸結(jié)式都是子句C1和和C2的二元歸結(jié)式，記為的二元歸結(jié)式，記為C12。魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-謂詞邏輯謂詞邏輯的歸結(jié)的歸結(jié)例例3.15 設(shè)設(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)說明說明： 對對謂詞邏輯謂詞邏輯，歸結(jié)歸結(jié)式式C12是其親本子句是其親本子句C1和和C2的邏輯結(jié)論。用歸結(jié)式的邏輯結(jié)論。用歸結(jié)式取代取代它在子句它在子句

57、集集S中的親本子句，所得到的子句集仍然保持著原子句集中的親本子句，所得到的子句集仍然保持著原子句集S的不可滿足性。的不可滿足性。 對謂詞邏輯，從對謂詞邏輯，從不可滿足的意義上說，一階謂詞邏輯的歸結(jié)原理也是完備的不可滿足的意義上說，一階謂詞邏輯的歸結(jié)原理也是完備的 魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理-謂詞邏輯謂詞邏輯的歸結(jié)的歸結(jié)歸結(jié)歸結(jié)演繹推理的歸結(jié)策略演繹推理的歸結(jié)策略歸結(jié)演繹推理實際上就是從子句集中不斷尋找可進(jìn)行歸結(jié)演繹推理實際上就是從子句集中不斷尋找可進(jìn)行歸結(jié)的子句對，并通過對這些子句對的歸結(jié)，最終得歸結(jié)的子句對，并通過對這些子句對的歸結(jié)，最終得出一個空子句的過程。出一個空子句的過程。由于事先并

58、不知道哪些子句對可進(jìn)行歸結(jié)，更不知道由于事先并不知道哪些子句對可進(jìn)行歸結(jié)，更不知道通過對哪些子句對的歸結(jié)能盡快得到空子句，因此就通過對哪些子句對的歸結(jié)能盡快得到空子句，因此就需要對子句集中的需要對子句集中的所有子句逐對進(jìn)行比較所有子句逐對進(jìn)行比較，直到得出，直到得出空子句為止空子句為止。盲目盲目的全面進(jìn)行歸結(jié)的全面進(jìn)行歸結(jié)的方法，不僅會產(chǎn)生許多無用的的方法，不僅會產(chǎn)生許多無用的歸結(jié)式，更嚴(yán)重的是會產(chǎn)生組合爆炸問題歸結(jié)式，更嚴(yán)重的是會產(chǎn)生組合爆炸問題。廣度廣度優(yōu)先是一種優(yōu)先是一種窮盡子句比較窮盡子句比較的復(fù)雜搜索的復(fù)雜搜索方法方法設(shè)設(shè)初始子句集為初始子句集為S0，廣度優(yōu)先策略的歸結(jié)，廣度優(yōu)先策略

59、的歸結(jié)過程：過程：1.從S0出發(fā)，對S0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1;2.用S0中的子句與S1中的子句進(jìn)行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2;3.用S0和S1中的子句與S2中的子句進(jìn)行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3;4.如此繼續(xù)，直到得出空子句或不能再繼續(xù)歸結(jié)為止。歸結(jié)歸結(jié)演繹推理的歸結(jié)策略演繹推理的歸結(jié)策略例設(shè)有例設(shè)有如下子句集如下子句集：S=I(x)R(x), I(a), R(y)L(y), L(a) 用廣度優(yōu)先策略證明用廣度優(yōu)先策略證明S為不可滿足為不可滿足。廣度優(yōu)先策略的歸結(jié)樹如下：廣

60、度優(yōu)先策略的歸結(jié)樹如下：I(x)R(x)I(a)R(y)L(y)L(a)R(a)I(x) L(x)R(a)L(a)L(a)I(a)I(a)NILS0S1S2歸結(jié)歸結(jié)演繹推理的歸結(jié)策略演繹推理的歸結(jié)策略 廣度優(yōu)先廣度優(yōu)先策略的優(yōu)點：策略的優(yōu)點： 當(dāng)問題有解時保證能找到最短歸結(jié)路徑。 是一種完備的歸結(jié)策略。 廣度優(yōu)先策略的廣度優(yōu)先策略的缺點：缺點： 歸結(jié)出了許多無用的子句 既浪費(fèi)時間，又浪費(fèi)空間 廣度廣度優(yōu)先對大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對優(yōu)先對大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對小小問題問題卻仍是一種比較好的歸結(jié)策略。卻仍是一種比較好的歸結(jié)策略。歸結(jié)歸結(jié)演繹推理的歸結(jié)策略演繹推理的歸結(jié)策略 常