人工智能第三章確定性推理80

1、第三章第三章 確定性推理確定性推理 按照推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。 自然演繹推理和歸結(jié)推理是經(jīng)典的確定性推理，它們以數(shù)理邏輯的有關(guān)理論、方法和技術(shù)為理論基礎(chǔ)，是機械化的、可在計算機上加以實現(xiàn)的推理方法。 本章在討論有關(guān)推理的一般概念以及命題和謂詞邏輯的基礎(chǔ)上，介紹自然演繹推理方法和基于一階謂詞邏輯的歸結(jié)推理方法。3.1 推理概述 3.1.1 推理的基本概念推理的基本概念 推理是指從已知事實出發(fā)，運用已掌握的知識，推導(dǎo)出其中蘊含的事實性結(jié)論或歸納出某些新的結(jié)論的過程。其中，推理所用的事實可分為兩種情況，一種是與求解問題有關(guān)的初始證據(jù)；另一種是推理過程中所得到的

2、中間結(jié)論，這些中間結(jié)論可以作為進一步推理的已知事實或證據(jù)。 人工智能系統(tǒng)的構(gòu)成：推理機一些程序來完成的；綜合數(shù)據(jù)庫存放有用于推理的事實或證據(jù)；知識庫存放有用于推理所必須的知識。 3.1 推理概述 3.1.2 推理的方法及其分類 1. 按照推理的邏輯基礎(chǔ)分類 可分為演繹推理、歸納推理和默認推理。 （1）演繹推理 演繹推理是從已知的一般性知識出發(fā)，推理出適合于某種個別情況的結(jié)論的過程。它是一種由一般到個別的推理方法。3.1 推理概述 （2）歸納推理 歸納推理是從大量特殊事例出發(fā)，歸納出一般性結(jié)論的推理過程，是一種由個別到一般的推理方法。其基本思想是：首先從已知事實中猜測出一個結(jié)論，然后對這個結(jié)論的

3、正確性加以證明確認，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。 歸納推理又可分為： 從特殊事例考察范圍看：完全歸納推理、不完全歸納推理； 從使用的方法看：枚舉歸納推理、類比歸納推理。3.1 推理概述 （3）默認推理 默認推理又稱缺省推理，是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。也就是說，在進行推理時，如果對某些證據(jù)不能證明其不成立的情況下，先假設(shè)它是成立的，并將它作為推理的依據(jù)進行推理，但在推理過程中，當(dāng)由于新知識的加入或由于所推出的中間結(jié)論與已有知識發(fā)生矛盾時，就說明前面的有關(guān)證據(jù)的假設(shè)是不正確，這時就要撤消原來的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新按新情況進行推理3.1 推理

4、概述 2. 按所用知識的確定性分類 按推理時所用知識的確定性來劃分，推理可分為確定性推理、不確定性推理。3. 按推理過程的單調(diào)性 按照推理過程中所推出的結(jié)論是否單調(diào)地增加，或者說按照推理過程所得到的結(jié)論是否越來越接近最終目標(biāo)來分類，推理可分為單調(diào)推理與非單調(diào)推理。 3.1 推理概述 3.1.3 推理的控制策略 推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。控制策略包括推理方向、搜索策略、沖突消解策略等；而推理方法則是指在推理控制策略確定之后，在進行具體推理時所要采取的匹配方法或不確定性傳遞算法等方法。 推理方向用來確定推理的驅(qū)動方式，即是數(shù)據(jù)（證據(jù)）驅(qū)動或是目標(biāo)驅(qū)動。所謂數(shù)據(jù)驅(qū)

5、動即指推理過程從初始證據(jù)開始直到目標(biāo)結(jié)束，而目標(biāo)驅(qū)動則是指推理過程從目標(biāo)開始進行反向推理，直到出現(xiàn)與初始證據(jù)相吻合的結(jié)果。 按照對推理方向的控制，推理可分為正向推理、反向推理、混合推理及雙向推理四種情況。3.1 推理概述 l 正向推理是一種從已知事實出發(fā)、正向使用推理規(guī)則的推理方式，它是一種數(shù)據(jù)（或證據(jù)）驅(qū)動的推理方式，又稱前項鏈推理或自底向上推理。l反向推理是一種以某個假設(shè)目標(biāo)為出發(fā)點，反向運用推理規(guī)則的推理方式，它是一種目標(biāo)驅(qū)動的推理方式，又稱反向鏈推理或自頂向下推理。l混合推理是把正向推理和反向推理結(jié)合起來所進行的推理。l所謂雙向混合推理是指正向推理和反向推理同時進行，使推理過程在中間的

6、某一步驟相匯合而結(jié)束的一種推理方法。 3.1 推理概述 3.1.4 推理的沖突消解策略 推理過程中的沖突消解策略，就是確定如何從多條匹配規(guī)則中選出一條規(guī)則作為啟用規(guī)則，將它用于當(dāng)前的推理。 目前已有的多種沖突消解策略的基本思想都是對匹配的知識或規(guī)則進行排序，以決定匹配規(guī)則的優(yōu)先級別，優(yōu)先級高的規(guī)則將作為啟用規(guī)則。常用排序方法有如下幾種:3.1 推理概述 (1)按就近原則排序 (2)按知識特殊性排序 (3)按上下文限制排序 (4)按知識的新鮮性排序 (5)按知識的差異性排序 (6)按領(lǐng)域問題的特點排序 (7)按規(guī)則的次序排序(8)按前提條件的規(guī)模排序 3.2 3.2 命題邏輯命題邏輯 3.2.1

7、 命題 定義 3.1 能夠分辨真假的語句稱作命題。定義3.2 一個語句如果不能再進一步分解成更簡單的語句，并且又是一個命題，則稱此命題為原子命題。 原子命題是命題中最基本的單位。我們一般用P、Q、R、大寫拉丁字母表示命題，而命題的真與假分別用“T”與“F”表示。 用大寫英文字母表示的命題既可以是一個特定的命題，也可以是一個抽象的命題。前者稱為命題常量，后者稱為命題變量。對于命題變量而言，只有把確定的命題代入后，它才可能有明確的邏輯值（T或F）。 3.2 3.2 命題邏輯命題邏輯3.2.2 命題公式 1. 連接詞：稱為“非”或“否定”。：稱為“析取”。：稱為“合取”。：稱為“條件”或者“蘊含”。

8、：稱為“雙條件”。P Q表示“P當(dāng)且僅當(dāng)Q”。表3.1 命題邏輯真值表P QPQPQPQP QPT TTTTTFT FTFFFFF TTFTFTF FFFTTT3.2 3.2 命題邏輯命題邏輯2.命題公式定義3.3 以下面的遞歸形式給出命題公式的定義： l （1）原子命題是命題公式。l （2）A是命題公式，則A也是命題公式。l （3）若A和B都是命題公式，則AB、AB、 AB、ABl（4）只有按（1）（3）所得的公式才是命題公式。 3.2 3.2 命題邏輯命題邏輯命題公式的缺點： l 無法把所描述的客觀事物的結(jié)構(gòu)和邏輯特征反映出來l 不能把不同事物的共同特征反映出來P:“張三是李四的老師”；僅

9、用字母P看不出張三和李四之間的師生關(guān)系。 為了克服命題邏輯的局限性，引入了下面的謂詞邏輯3.3 3.3 謂詞邏輯謂詞邏輯3.3.1 謂詞與個體 在謂詞邏輯中，將原子命題分解為謂詞與個體兩部分。個體是指可以獨立存在的物體，可以是抽象的或具體的。謂詞則是用于刻畫個體的性質(zhì)、狀態(tài)或個體間的關(guān)系的。 例如：“李白是詩人” 可表示為：poet(LiBai) poet稱為謂詞，用以刻畫“是詩人”；LiBai稱為個體 3.3 3.3 謂詞邏輯謂詞邏輯 一個謂詞可以與一個個體相關(guān)聯(lián)，此種謂詞稱作一元謂詞，它刻畫了個體的性質(zhì)。一個謂詞也可以與多個個體相關(guān)聯(lián)，此種謂詞稱為多元謂詞，它刻畫了個體間的“關(guān)系”。 3.

10、3 3.3 謂詞邏輯謂詞邏輯謂詞的一般形式：P(x1,x2,xn )其中P是謂詞，而x1,x2,xn是個體。謂詞通常用大寫字母表示，個體通常用小寫字母表示。 項：在謂詞中，個體可以是常量，也可以是變量，還可以是一個函數(shù)。例如，“小劉的哥哥是個工人”，可以表示為worker(brother(Liu)，其中brother(Liu)是一個函數(shù)。個體常數(shù)、變量和函數(shù)統(tǒng)稱為項。 謂詞的語義：由使用者根據(jù)需要人為地定義. 3.3 3.3 謂詞邏輯謂詞邏輯謂詞的元數(shù)：謂詞中包含的個體數(shù)目稱為謂詞的元數(shù)，例如P(x)是一元謂詞，P(x,y)是二元謂詞，而P(x1,x2,xn )則是n元謂詞。謂詞的階數(shù)：在謂詞

11、P(x1,x2,xn )中，若xi(i=1,2,n)都是個體常量、變元或函數(shù)，則稱它為一階謂詞。如果某個xi本身又是一個一階謂詞，則稱它為二階謂詞，依次類推。謂詞和函數(shù)的區(qū)別：謂詞具有邏輯值“真”或“假”，而函數(shù)則是某個個體到另一個個體（按數(shù)學(xué)上的概念是自變量到因變量）之間的映射。 3.3 3.3 謂詞邏輯謂詞邏輯3.3.2 謂詞公式 1. 連接詞 ， 2. 量詞 為刻畫謂詞與個體間的關(guān)系，引入了兩個量詞：全稱量詞（x）,和存在量詞（x）。 3. 謂詞演算公式定義3.4 謂詞演算中，由單個謂詞構(gòu)成的不含任何連接詞的公式，叫做原子謂詞公式。 3.3 3.3 謂詞邏輯謂詞邏輯由原子公式的定義出發(fā)，

12、可定義謂詞演算的合式公式如下。定義3.5 可按下述規(guī)則得到謂詞演算的合式公式： （1） 原子謂詞公式是合式公式。 （2） 若A是合式公式，則A也是合式公式。 （3）若A和B都是合式公式，則AB、AB、AB、AB也都是合式公式。 （4）若A是合式公式，x是任一個體變元，則(x)A和(x)A也都是合式公式。 （5）只有按（1）（4）所得的公式才是合式公式。 3.3 3.3 謂詞邏輯謂詞邏輯4. 量詞轄域與約束變元 在一個公式中，如果有量詞出現(xiàn)，位于量詞后面的單個謂詞或者用括弧括起來的合式公式稱為量詞的轄域。在轄域內(nèi)與量詞中同名的變元稱為約束變元。 3.3 3.3 謂詞邏輯謂詞邏輯3.3.3 謂詞公

13、式的永真性和可滿足性謂詞公式的永真性和可滿足性1謂詞公式的解釋定義3.6 設(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上的一個解釋。3.3 3.3 謂詞邏輯謂詞邏輯例3.1 設(shè)個體域D=1,2，求公式A=(x)(P(x)Q(f(x),b)在D上的某一個解釋，并指出在此解釋下公式A的真值。 詳細的求解過程參見教材3.3 3.3 謂詞邏輯謂詞邏輯2謂詞公式的

14、永真性定義3.7 如果謂詞公式P，對個體域D上的任何一個解釋都取得真值T，則稱P在D上是永真的；如果P在每個非空個體域上均永真，則稱P永真。定義3.8 如果謂詞公式P對于個體域D上的所有解釋都取得假值F，則稱P在D上是永假的；如果P在每個非空個體域上均永假，則稱P永假。謂詞公式的永假性又稱為不可滿足性或不相容性。3.3 3.3 謂詞邏輯謂詞邏輯3謂詞公式的可滿足性 定義3.9 對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下的真值為T，則稱公式P是可滿足的。按照定義3.9，對謂詞公式P，如果不存在任何解釋，使得P的取值為T，則稱公式P是不可滿足的。所以，謂詞公式P永假與不可滿足是等價的

15、。若P永假，則也可稱P是不可滿足的。 3.3 3.3 謂詞邏輯謂詞邏輯3.3.4 謂詞公式的等價性與永真蘊含 定義3.10 設(shè)P與Q是兩個謂詞公式，D是它們共同的個體域。若對D上的任何一個解釋，P與Q的取值都相同，則公式P和Q在域D上是等價的。如果D是任意個體域，則稱P和Q是等價的，記作P Q。常用的一些等價式參見教材 定義3.11 對于謂詞公式P和Q，如果PQ永真，則稱P永真蘊含Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記作P=Q。 以后要用到的一些永真蘊含式參見教材3.3 3.3 謂詞邏輯謂詞邏輯謂詞邏輯中還有如下一些推理規(guī)則：（1）P規(guī)則：在推理的任何步驟上都可引入前提。（2）T規(guī)則：推

16、理時，如果前面步驟中有一個或多個永真蘊含公式S，則可把S引入推理過程中。（3）CP規(guī)則：如果能從R和前提集合中推出S來，則可從前提集合推出RS來。（4）反證法：P=Q，當(dāng)且僅當(dāng)PQF，即Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)PQ 是不可滿足的。推廣之，可得如下定理。 定理3.1 Q為P1，P2，Pn的邏輯結(jié)論，當(dāng)且僅當(dāng) (P1P2Pn)Q是不可滿足的。3.3 3.3 謂詞邏輯謂詞邏輯3.3.5 置換與合一 1. 置換 置換的定義定義3.12 置換是形如t1/x1,t2/x2,tn/xn的一個有限集。其中xi是變量，ti是不同于xi的項（常量，變量，函數(shù)），且xi xj（Ij），i，j=1,2,n 。 3.

17、3 3.3 謂詞邏輯謂詞邏輯例如，a/x,b/y,f(x)/z，f(z)/x,y/z都是置換。不含任何元素的置換稱為空置換，以 表示。 置換乘法 置換乘法作用是將兩個置換合成為一個置換。定義3.13假設(shè) =t1/x1,t2/x2,tn/xn =u1/y1,u2/y2,um/ym是兩個置換，則它們的乘積是一個新置換，其作用于公式E時，相當(dāng)于先后對E的作用。它的定義如下：3.3 3.3 謂詞邏輯謂詞邏輯先作置換t1 /x1,t2 /x2,tn /xn,u1/y1,u2/y2,um/ym。若yi x1,xn時，先從上述集合中刪除ui/yi 。若 ti =xi時，再從上述集合中刪除ti /xi 。刪除

18、以后剩下元素所構(gòu)成的集合稱作與的乘積，記作 。 置換結(jié)合率一般地說，下列的置換結(jié)合律成立 ( ) = = ( ) ) 但除了空置換外，置換的交換律不成立。即只有= = 。 3.3 3.3 謂詞邏輯謂詞邏輯2. 合一 合一的概念定義3.14 設(shè)有公式集E1,E2,En和置換 ，使 E1 = E2 =En 便稱E1，E2，En是可合一的 ，且稱為合一置換。定義3.15 若E1，E2，En 有合一置換，且對E1，E2，En 的任一置換都存在一個置換，使得= ，則稱是E1，E2，En 的最一般合一置換，記為mgu。3.3 3.3 謂詞邏輯謂詞邏輯 最一般合一置換的求取算法設(shè)有兩個謂詞公式： E1：P(

19、x,y,z); E2：P(x,f(a),g(b)分別從E1與E2的第一個符號開始逐個向右比較，此時發(fā)現(xiàn)E1中的y與E2中的f(a)不同，則它們構(gòu)成了一個不一致集： D1=y,f(a)當(dāng)繼續(xù)向右比較時，又發(fā)現(xiàn)中E1中的z與E2中g(shù)(b)不同，則又得到一個不一致集： D2=z,g(b) 下面給出求公式E1,E2的最一般合一置換的算法：3.3 3.3 謂詞邏輯謂詞邏輯（1） 令W= E1,E2 。（2） 令 k=0，Wk=W，k= ；是空置換，它表示不作置換。（3） 如果Wk只有一個表達式，則算法停止，k就是所要求的mgu。（4） 找出Wk的不一致集Dk 。 （5） 若Dk中存在元素xk和tk ，其

20、中xk是變元，tk是項，且xk不在tk中 出現(xiàn)，則置： k+1=k tk/xk Wk+1=wktk/xk k=k+1 然后轉(zhuǎn)（3）。（6） 算法終止，W的mgu不存在?？梢宰C明，如果E1和E2可合一，則算法必停止于第（3）步。 3.3 3.3 謂詞邏輯謂詞邏輯例3.5 設(shè)E1=P(a,v,f(g(y)，E2=P(z,f(a),f(u)，求E1 和E2的mgu。解題請參見教材 答案為：3= a/z ,f(a)/v,g(y)/u 3就是E1 和E2的mgu。 3.4 3.4 自然演繹推理方法自然演繹推理方法 3.4.1 自然演繹推理的概念自然演繹推理的概念 自然演繹推理是指從一組已知為真的事實出發(fā)

21、，直接運用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過程。 假言三段論的基本形式為 PQ，QRPR 它表示如果謂詞公式PQ和QR均為真，則謂詞公式PR也為真。 假言推理可用下列形式表示 P，PQ Q它表示如果謂詞公式P和PQ都為真，則可推得Q為真結(jié)論。 3.4 3.4 自然演繹推理方法自然演繹推理方法 拒取式的一般形式為 PQ，Q P它表示如果謂詞公式PQ為真且Q為假，則可推得P為假的結(jié)論。2.4.2 2.4.2 利用演繹推理解決問題利用演繹推理解決問題 在利用自然演繹推理方法求解問題時，一定要注意避免兩種類型的錯誤：肯定后件的錯誤和否定前件的錯誤。 3.4 3.4 自然演繹推理方法自然演繹推理

22、方法 肯定后件的錯誤是指當(dāng)PQ為真時，希望通過肯定后件Q為真來推出前件P為真。這顯然是錯誤的推理邏輯，因為當(dāng) PQ及 Q為真時，前件 P既可能為真，也可能為假。 否定前件的錯誤是指當(dāng)PQ為真時，希望通過否定前件P來推出后件Q為假。這也是不允許的，因為當(dāng)PQ及P為假時，后件Q既可能為真，也可能為假。 相關(guān)的例題請參見教材3.4 3.4 自然演繹推理方法自然演繹推理方法 3.4.3 演繹推理的特點演繹推理的特點 參見教材3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 研究用計算機實現(xiàn)定理證明的機械化，已是人工智能研究的一個重要領(lǐng)域。對于定理證明問題，如果用一階謂詞邏輯表示的話，就是要求對前提P和結(jié)論Q證

23、明PQ是永真的。然而，要證明這個謂詞公式的永真性，必須對所有個體域上的每一個解釋進行驗證，這是極其困難的。為了化簡問題，和數(shù)學(xué)上常采用的方法一樣，我們考慮反證法。即，我們先否定邏輯結(jié)論Q，再由否定后的邏輯結(jié)論Q及前提條件P出發(fā)推出矛盾，即可證明原問題。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.1謂詞公式與子句集謂詞公式與子句集 1范式 前束形范式 一個謂詞公式，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且它的轄域一直延伸到公式之末，同時公式中不出現(xiàn)連接詞及 ，這種形式的公式稱作前束形范式。例如，公式( x)(y)( z)(P(x)F(y,z)Q(y,z)即是一個前束形的公式。3.5

24、 3.5 歸結(jié)推理方法歸結(jié)推理方法 斯克林范式 從前束形范式中消去全部存在量詞所得到的公式即為Skolem范式，或稱Skolem標(biāo)準(zhǔn)型。例如，如果用f(x)代替上面前束形范式中的y即得到Skolem范式：( x) ( z)(P(x)F(f(x), z)Q(f(x), z)Skolem標(biāo)準(zhǔn)型的一般形式是( x1)( x2)( xn)M(x1,x2,xn)其中，M(x1,x2,xn)是一個合取范式，稱為Skolem標(biāo)準(zhǔn)型的母式。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 將謂詞公式G化為Skolem標(biāo)準(zhǔn)型的步驟如下：（1） 消去謂詞公式G中的蘊涵（）和雙條件符號（ ），以AB代替AB，以(AB)(A

25、B)替換AB。（2） 減少否定符號（）的轄域，使否定符號“”最多只作用到一個謂詞上。（3） 重新命名變元名，使所有的變元的名字均不同，并且自由變元及約束變元亦不同。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 （4） 消去存在量詞。這里分兩種情況，一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時，只要用一個新的個體常量替換該存在量詞約束的變元，就可以消去存在量詞；另一種情況是，存在量詞位于一個或多個全稱量詞的轄域內(nèi)，這時需要用一個Skolem函數(shù)替換存在量詞而將其消去。（5）把全稱量詞全部移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。（6）母式化為合取范式：任何母式都可以寫成由

26、一些謂詞公式和謂詞公式否定的析取的有限集組成的合取。 需要指出的是，由于在化解過程中，消去存在量詞時作了一些替換，一般情況下，G的Skolem標(biāo)準(zhǔn)型與G并不等值。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 2子句與子句集定義3.16 不含有任何連接詞的謂詞公式叫原子公式，簡稱原子，而原子或原子的否定統(tǒng)稱文字。定義3.17 子句就是由一些文字組成的析取式。定義3.18 不包含任何文字的子句稱為空子句，記為NIL。定義3.199 由子句構(gòu)成的集合稱為子句集。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3不可滿足意義下的一致性定理3.2 設(shè)有謂詞公式G，而其相應(yīng)的子句集為S，則G是不可滿足的充分必要條件

27、是S是不可滿足的。 要再次強調(diào)：公式G與其子句集S并不等值，只是在不可滿足意義下等價。 相關(guān)的例子參見教材中的例3.93.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 4PP1P2Pn的子句集 當(dāng)PP1P2Pn時，若設(shè)P的子句集為SP，Pi的子句集為Si，則一般情況下，SP并不等于S1S2S3Sn，而是要比S1S2S3Sn復(fù)雜得多。但是，在不可滿足的意義下，子句集SP與S1S2S3Sn是一致的，即 SP不可滿足S1S2S3Sn不可滿足3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.2 3.5.2 HerbrandHerbrand理論理論 1H域 定義3.20 設(shè)謂詞公式G的子句集為S，則按下述方法構(gòu)

28、造的個體變元域H。稱為公式G或子句集S的Herbrand域，簡稱H域。（1） 令H0是S中所出現(xiàn)的常量的集合。若S中沒有常量出現(xiàn)，就任取一個常量aD，規(guī)定H0=a。（2） 令Hi+1=HiS中所有的形如f(t1,tn)的元素其中f(t1,tn)是出現(xiàn)于G中的任一函數(shù)符號，而t1，tn是Hi中的元素。i=0，1，2，。 3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例3.10 求子句集ST(x)Q(z),R(f(y)的H域。解 此例中沒有個體常量，任意指定一個常量a作為個體常量；只有一個函數(shù)f(y)，有：H0=aH1=a,f(a)H2=a,f(a),f(f(a)H=a,f(a),f(f(a),f(f

29、(f(a),3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 2原子集定義3.21 下列集合稱為子句集S的原子集： A所有形如P(t1, t2,tn)的元素其中，P(t1, t2,tn)是出現(xiàn)在S中的任一謂詞符號，而t1，t2，tn則是S的H域上的任意元素。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定義3.22 將沒有變元出現(xiàn)的原子、文字、子句和子句集分別稱作基原子、基文字、基子句和基子句集。定義3.23 當(dāng)子句集S中的某個子句C中的所有變元符號均以其H域中的元素替換時，所得到的基子句稱作C的一個基例。 例如，對于子句集 SP(a),P(x)P(f(x) 它的H域為a,f(a),f(f(a),。 對于

30、子句P(a)，因為其中不含有變元，所以它已是基子句，而且aH，所以它也是基例。 3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3H域上的解釋定義3.24 如果子句集S的原子集為A，則對A中各元素的真假值的一個具體設(shè)定都是S的一個H解釋?？梢宰C明，在給定域D上的任一個解釋I，總能在H域上構(gòu)造一個解釋I*與之對應(yīng)，使得如果D域上的解釋能滿足子句集S，則在H域的解釋I*也能滿足S（即若S|I=T，就有S|I*=T）。相關(guān)舉例參見教材3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定理3.3 設(shè)I是子句集S在域D上的一個解釋，則存在對應(yīng)于I的H域解釋I*，使得若有 S|I=T，就必有S|I*=T。定理3.4 子

31、句集S不可滿足的充要條件是S對H域上的一切解釋都為假。 證明 充分性：若S在一般域D上是不可滿足的，必然在H域上是不可滿足的，從而對H域上的一切解釋都為假。必要性：若S在任一H解釋I*下均為假，必然會使S在D域上的每一個解釋為假。否則，如果存在一個解釋I0使S為真，那么依據(jù)定理3.3可知，一定可以在H域找到相對應(yīng)的一個解釋I*0使S為真。這與S在所有H解釋下均為假矛盾。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定理3.5 子句集S不可滿足的充分必要條件是存在一個有限的不可滿足的基例集S。 該定理稱為Herbrand定理，下面給出它的簡要證明。證明 充分性：設(shè)子句集S有一個不可滿足的基例集S，因

32、為它不可滿足，所以一定存在一個解釋I使S為假。根據(jù)H域上的解釋與D域上的解釋的對應(yīng)關(guān)系，可知在D域上一定存在一個解釋使S不可滿足，從而證明了子句集S是不可滿足的。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 必要性：設(shè)子句集S不可滿足，由定理3.4可知，S對H域上的所有解釋均為假。這樣，就至少會存在一個S中的某子句Ci的基例Ci為假。既然至少有一個基例Ci為假，因而S的基例集S是不可滿足的。另外，由于S中的子句是有限的，而每個子句又由有限的文字組成，因而S的不可滿足的基例集也是有限的。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.3 歸結(jié)原理歸結(jié)原理定義3.25 若P是原子謂詞公式或原子命題，

33、則稱P與P為互補文字。1命題邏輯中的歸結(jié)原理歸結(jié)與歸結(jié)式 定義3.26 設(shè)C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，則從C1和C2中可以分別消去L1和L2，并將二子句中余下的部分做析取構(gòu)成一個新的子句C12，稱這一過程為歸結(jié)，所得到的子句C12稱為C1和C2的歸結(jié)式，而稱C1和C2為C12的親本子句。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定理3.6 歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。推論 設(shè)C1和C2是子句集S上的子句，C12是C1和C2的歸結(jié)式。如果把C12加入子句集S后得到新子句集S1，則S1和S在不可滿足的意義下是等價的。即： S是不

34、可滿足的 S1是不可滿足的 歸結(jié)推理過程歸結(jié)推理過程 子句集S不可滿足性的推理過程如下： (1) 對子句集S中的各子句間使用歸結(jié)推理規(guī)則。 (2) 將歸結(jié)所得的歸結(jié)式放入子句集S中，得新子句集S。 (3) 檢查子句集S中是否有空子句(NIL),若有則停止推理;否則轉(zhuǎn)（4）。 (4) 置S=S，轉(zhuǎn)步驟（1）。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 2一階謂詞邏輯中的歸結(jié)原理 下面是謂詞邏輯關(guān)于歸結(jié)的定義。定義定義3.27 設(shè)C1和C2是兩個沒有相同變元的子句，L1 和L2分別是C1 和C2的文字，如果L1與 L2有mgu ，則把 C12 =( C1L1)(C2 L2)稱作子句C1 和C2的一個

35、二元歸結(jié)式，而L1 和L2是被歸結(jié)的文字。 為了說明的方便。將Ci和Li寫成集合形式， 如P(x)Q(y)改寫為P(x),Q(y)。在集合的表示下做減法或做并運算，然后再寫成子句形，如集合運算結(jié)果為P(x),Q(y)，可改寫為P(x)Q(y)。 3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 在謂詞邏輯中，對子句進行歸結(jié)推理時，要注意以下幾個問題：（1）若被歸結(jié)的子句C1 和C2中具有相同的變元時，需要將其中一個子句的變元更名，否則可能無法做合一置換。從而沒有辦法進行歸結(jié)。 （2）在求歸結(jié)式時，不能同時消去兩個互補文字對，消去兩個互補文字對所得的結(jié)果不是兩個親本子句的邏輯推論。（3）如果在參加歸結(jié)的

36、子句內(nèi)含有可合一的文字，則在進行歸結(jié)之前，應(yīng)對這些文字進行合一，以實現(xiàn)這些子句內(nèi)部的化簡。 3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 應(yīng)用因子的概念，可對謂詞邏輯中的歸結(jié)原理定義如下。 定義3.28 設(shè)C1和 C2是沒有相同變元的子句，則下列四種二元歸結(jié)式都叫做C1和C2的歸結(jié)式，仍記作C12。（1） C1與C2的二元歸結(jié)式。（2） C1的因子C11與C2的二元歸結(jié)式。（3） C1與C2的因子C22的二元歸結(jié)式。（4） C1的因子C11與C2的因子C22的二元歸結(jié)式。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例例 設(shè)C1=P(a)Q(x)R(x)，C2 =P(y)Q(b)， 求其二元歸結(jié)式。解

37、解 若選L1=P(a)，L2=P(y)，則L1和L2的mgu是=a/y，于是由定義3.27得C1和C2 的二元歸結(jié)式為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) 若選L1=Q(x)，L2=Q(b)，則二者的mgu=b/x， C12 =P(a)R(b)P(y)3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3歸結(jié)原理的完備性歸結(jié)原理的完備性 對于一階謂詞邏輯，從不可滿足的意義上說，歸結(jié)原理是完備的。即若子句集是不可滿足的，則必存在一個從該子句集到空子句的歸結(jié)推理過程；反之，

38、若從子句集到空子句存在一個歸結(jié)推理過程，則該子句集必是不可滿足的。 3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.4 利用歸結(jié)原理進行定理證明利用歸結(jié)原理進行定理證明 應(yīng)用歸結(jié)原理進行定理證明的步驟如下：應(yīng)用歸結(jié)原理進行定理證明的步驟如下： 設(shè)要被證明的定理可用謂詞公式表示為如下的形式： A1A2AnB(1) 首先否定結(jié)論B，并將否定后的公式B與前提公式集組成如下形式的謂詞公式： G= A1A2AnB(2) 求謂詞公式G的子句集S。(3) 應(yīng)用歸結(jié)原理，證明子句集S的不可滿足性，從而證明謂詞公式G的不可滿足性。這就說明對結(jié)論B的否定是錯誤的，推斷出定理的成立。3.5 3.5 歸結(jié)推理方法歸

39、結(jié)推理方法 例例 已知：A: (x)( y)(P(x,y)Q(y)( y)(R(y)T(x,y)B: ( x)R(x)( x)( y)(P(x,y)Q(y)求證：B是A的邏輯結(jié)論。證明證明 首先將A和B化為子句集(1)P(x,y)Q(y) R(f(x)(2)P(x,y)Q(y) T(x,f(x) /(1)(2)為A(3)R(z)(4)P(a，b)(5)Q(b) /(3)(4)(5)為B3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 下面進行歸結(jié)： （6） P(x,y)Q(y) （1）與（3）歸結(jié)，=f(x)/z （7） Q(b) （4）與（6）歸結(jié)，=a/x,b/y （8） NIL（空子句） （5）

40、與（7）歸結(jié)所以B是A的邏輯結(jié)論。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.5 應(yīng)用歸結(jié)原理進行問題求解應(yīng)用歸結(jié)原理進行問題求解下面是利用歸結(jié)原理求取問題答案的步驟：（1）把已知前提條件用謂詞公式表示出來，并化成相應(yīng)的子句集，設(shè)該子句集的名字為S1。（2）把待求解的問題也用謂詞公式表示出來，然后將其否定，并與一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個專為求解問題而設(shè)置的謂詞，其變量必須與問題公式的變量完全一致。（3）把問題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1合并構(gòu)成子句集S。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 （4）對子句集S應(yīng)用謂詞歸結(jié)原理

41、進行歸結(jié)，在歸結(jié)的過程中，通過合一置換，改變ANSWER中的變元。（5）如果得到歸結(jié)式ANSWER ，則問題的答案即在ANSWER謂詞中。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例例 任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？解解 第一步：將已知條件用謂詞公式表示出來，并化成子句集，那么要先定義謂詞。（1） 定義謂詞：設(shè)Father(x,y)表示x是y的父親。Brother(x,y)表示x和y是兄弟。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 （2） 將已知事實用謂詞公式表示出來。 F1 ：任何兄弟都有同一個父親。 (x)(y)(

42、z)(Brother(x,y)Father(z,x)Father(z,y) F2：John和Peter是兄弟。 Brother(John,Peter) F3： John的父親是David。 Father(David, John)（3） 將它們化成子句集得： S1=Brother(x,y)Father(z,x)Father(z,y), Brother(John,Peter), Father(David,John)3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER作析取。 設(shè)Peter的父親是u，則有：Father(u,Peter)。 將其否定

43、與ANSWER作析取，得： G：Father(u,Peter)ANSWER(u)3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 第三步：將上述公式G化為子句集S2，并將S1和S2合并到S。 S2 =Father(u,Peter)ANSWER(u) S= S1S2將S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）Father(u,Peter)ANSWER(u)。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 第四步：應(yīng)用歸結(jié)原理進行歸結(jié)（5）Brother(John,y)Father(David,y) （1）與（3）歸結(jié) =David/z,John/x（6）Brother(John,Peter)ANSWER(David) （4）與（5）歸結(jié)=David/u,Peter/y（7）ANSWER(David) （2）與（6）歸結(jié)第五步：得到了歸結(jié)式ANSWER(David)，答案即在其中，所以u=David。即Peter的父親是David。3.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.6 歸結(jié)過程的控制策略歸結(jié)過程的控制策略 3.6.1 引入控制策略引入控制策略1引入控制策略的原因 對子句集