1、第三章 確定性推理方法按照推理過(guò)程所用知識(shí)的確定性，推理可分為確定性推理和不確定性推理。 自然演繹推理和歸結(jié)推理是經(jīng)典的確定性推理，它們以數(shù)理邏輯的有關(guān)理論、方法和技術(shù)為理論基礎(chǔ)，是機(jī)械化的、可在計(jì)算機(jī)上加以實(shí)現(xiàn)的推理方法。 3.1 推理概述 推理的基本概念 推理是指從已知事實(shí)出發(fā)，運(yùn)用已掌握的知識(shí)，推導(dǎo)出其中蘊(yùn)含的事實(shí)性結(jié)論或歸納出某些新的結(jié)論的過(guò)程。其中，推理所用的事實(shí)可分為兩種情況，一種是與求解問(wèn)題有關(guān)的初始證據(jù)；另一種是推理過(guò)程中所得到的中間結(jié)論，這些中間結(jié)論可以作為進(jìn)一步推理的已知事實(shí)或證據(jù)。 人工智能系統(tǒng)的構(gòu)成：推理機(jī)一些程序來(lái)完成的；綜合數(shù)據(jù)庫(kù)存放有用于推理的事實(shí)或證據(jù)；知識(shí)庫(kù)存

2、放有用于推理所必須的知識(shí)。 推理的方法及其分類 1. 按照推理的邏輯基礎(chǔ)分類 可分為演繹推理、歸納推理和默認(rèn)推理。（1）演繹推理 演繹推理是從已知的一般性知識(shí)出發(fā)，推理出適合于某種個(gè)別情況的結(jié)論的過(guò)程。它是一種由一般到個(gè)別的推理方法。（2）歸納推理 歸納推理是從大量特殊事例出發(fā)，歸納出一般性結(jié)論的推理過(guò)程，是一種由個(gè)別到一般的推理方法。其基本思想是：首先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。 歸納推理又可分為： 從特殊事例考察范圍看：完全歸納推理、不完全歸納推理； 從使用的方法看：枚舉歸納推理、類比歸納推理。（3）默認(rèn)推理 默認(rèn)推

3、理又稱缺省推理，是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。也就是說(shuō)，在進(jìn)行推理時(shí)，如果對(duì)某些證據(jù)不能證明其不成立的情況下，先假設(shè)它是成立的，并將它作為推理的依據(jù)進(jìn)行推理，但在推理過(guò)程中，當(dāng)由于新知識(shí)的加入或由于所推出的中間結(jié)論與已有知識(shí)發(fā)生矛盾時(shí)，就說(shuō)明前面的有關(guān)證據(jù)的假設(shè)是不正確，這時(shí)就要撤消原來(lái)的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新按新情況進(jìn)行推理2. 按所用知識(shí)的確定性分類 按推理時(shí)所用知識(shí)的確定性來(lái)劃分，推理可分為確定性推理、不確定性推理。3. 按推理過(guò)程的單調(diào)性 按照推理過(guò)程中所推出的結(jié)論是否單調(diào)地增加，或者說(shuō)按照推理過(guò)程所得到的結(jié)論是否越來(lái)越接近最終目標(biāo)來(lái)分類，推理

4、可分為單調(diào)推理與非單調(diào)推理。 推理的控制策略 推理過(guò)程不僅依賴于所用的推理方法，同時(shí)也依賴于推理的控制策略。控制策略包括推理方向、搜索策略、沖突消解策略等；而推理方法則是指在推理控制策略確定之后，在進(jìn)行具體推理時(shí)所要采取的匹配方法或不確定性傳遞算法等方法。 推理方向用來(lái)確定推理的驅(qū)動(dòng)方式，即是數(shù)據(jù)（證據(jù)）驅(qū)動(dòng)或是目標(biāo)驅(qū)動(dòng)。所謂數(shù)據(jù)驅(qū)動(dòng)即指推理過(guò)程從初始證據(jù)開始直到目標(biāo)結(jié)束，而目標(biāo)驅(qū)動(dòng)則是指推理過(guò)程從目標(biāo)開始進(jìn)行反向推理，直到出現(xiàn)與初始證據(jù)相吻合的結(jié)果。 按照對(duì)推理方向的控制，推理可分為正向推理、反向推理、混合推理及雙向推理四種情況。 正向推理是一種從已知事實(shí)出發(fā)、正向使用推理規(guī)則的推理方式，它

5、是一種數(shù)據(jù)（或證據(jù)）驅(qū)動(dòng)的推理方式，又稱前項(xiàng)鏈推理或自底向上推理。 反向推理是一種以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)，反向運(yùn)用推理規(guī)則的推理方式，它是一種目標(biāo)驅(qū)動(dòng)的推理方式，又稱反向鏈推理或自頂向下推理。 混合推理是把正向推理和反向推理結(jié)合起來(lái)所進(jìn)行的推理。 所謂雙向混合推理是指正向推理和反向推理同時(shí)進(jìn)行，使推理過(guò)程在中間的某一步驟相匯合而結(jié)束的一種推理方法。 推理的沖突消解策略 推理過(guò)程中的沖突消解策略，就是確定如何從多條匹配規(guī)則中選出一條規(guī)則作為啟用規(guī)則，將它用于當(dāng)前的推理。 目前已有的多種沖突消解策略的基本思想都是對(duì)匹配的知識(shí)或規(guī)則進(jìn)行排序，以決定匹配規(guī)則的優(yōu)先級(jí)別，優(yōu)先級(jí)高的規(guī)則將作為啟用規(guī)則。常

6、用排序方法有如下幾種:l 按就近原則排序 l 按知識(shí)特殊性排序 l 按上下文限制排序 l 按知識(shí)的新鮮性排序 l 按知識(shí)的差異性排序 l 按領(lǐng)域問(wèn)題的特點(diǎn)排序 l 按規(guī)則的次序排序l 按前提條件的規(guī)模排序 3.2 命題邏輯 命題定義 3.1 能夠分辨真假的語(yǔ)句稱作命題。定義3.2 一個(gè)語(yǔ)句如果不能再進(jìn)一步分解成更簡(jiǎn)單的語(yǔ)句，并且又是一個(gè)命題，則稱此命題為原子命題。 原子命題是命題中最基本的單位。我們一般用P、Q、R、大寫拉丁字母表示命題，而命題的真與假分別用“T”與“F”表示。 用大寫英文字母表示的命題既可以是一個(gè)特定的命題，也可以是一個(gè)抽象的命題。前者稱為命題常量，后者稱為命題變量。對(duì)于命題

7、變量而言，只有把確定的命題代入后，它才可能有明確的邏輯值（T或F）。 命題公式1. 連接詞：稱為“非”或“否定”。 ：稱為“析取”。：稱為“合取”。 ：稱為“條件”或者“蘊(yùn)含”。«：稱為“雙條件”。P « Q表示“P當(dāng)且僅當(dāng)Q”。表3.1 命題邏輯真值表2.命題公式定義3.3 以下面的遞歸形式給出命題公式的定義： （1）原子命題是命題公式。（2）A是命題公式，則A也是命題公式。（3）若A和B都是命題公式，則AB、AB、 AB、A«B（4）只有按（1）（3）所得的公式才是命題公式。 命題公式的缺點(diǎn)： 無(wú)法把所描述的客觀事物的結(jié)構(gòu)和邏輯特征反映出來(lái)不能把不同事物的共同

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

9、1,x2,xn )其中P是謂詞，而x1,x2,xn是個(gè)體。謂詞通常用大寫字母表示，個(gè)體通常用小寫字母表示。 項(xiàng)：在謂詞中，個(gè)體可以是常量，也可以是變量，還可以是一個(gè)函數(shù)。例如，“小劉的哥哥是個(gè)工人”，可以表示為worker(brother(Liu)，其中brother(Liu)是一個(gè)函數(shù)。個(gè)體常數(shù)、變量和函數(shù)統(tǒng)稱為項(xiàng)。 謂詞的語(yǔ)義：由使用者根據(jù)需要人為地定義. 謂詞的元數(shù)：謂詞中包含的個(gè)體數(shù)目稱為謂詞的元數(shù)，例如P(x)是一元謂詞，P(x,y)是二元謂詞，而P(x1,x2,xn )則是n元謂詞。謂詞的階數(shù)：在謂詞P(x1,x2,xn )中，若xi(i=1,2,n)都是個(gè)體常量、變?cè)蚝瘮?shù)，則稱

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

11、是合式公式。（3）若A和B都是合式公式，則AB、AB、AB、A«B也都是合式公式。 （4）若A是合式公式，x是任一個(gè)體變?cè)瑒t("x)A和($x)A也都是合式公式。 （5）只有按（1）（4）所得的公式才是合式公式。4. 量詞轄域與約束變?cè)?在一個(gè)公式中，如果有量詞出現(xiàn)，位于量詞后面的單個(gè)謂詞或者用括弧括起來(lái)的合式公式稱為量詞的轄域。在轄域內(nèi)與量詞中同名的變?cè)Q為約束變?cè)?謂詞公式的永真性和可滿足性1謂詞公式的解釋定義3.6 設(shè)D為謂詞公式P的個(gè)體域，若對(duì)P中的個(gè)體常量、函數(shù)和謂詞按照如下規(guī)定賦值：（1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；（2）為每個(gè)n元函數(shù)指派一個(gè)從Dn到

12、D的映射，其中 Dn=(x1,x2,xn)|x1,x2,xn ÎD（3）為每個(gè)n元謂詞指派一個(gè)從Dn到F,T的映射；則稱這些指派為公式P在D上的一個(gè)解釋。例3.1 設(shè)個(gè)體域D=1,2，求公式A=("x)(P(x)Q(f(x),b)在D上的某一個(gè)解釋，并指出在此解釋下公式A的真值。(詳細(xì)的求解過(guò)程參見教材)2謂詞公式的永真性定義3.7 如果謂詞公式P，對(duì)個(gè)體域D上的任何一個(gè)解釋都取得真值T，則稱P在D上是永真的；如果P在每個(gè)非空個(gè)體域上均永真，則稱P永真。定義3.8 如果謂詞公式P對(duì)于個(gè)體域D上的所有解釋都取得假值F，則稱P在D上是永假的；如果P在每個(gè)非空個(gè)體域上均永假，則稱

13、P永假。謂詞公式的永假性又稱為不可滿足性或不相容性。3謂詞公式的可滿足性 定義3.9 對(duì)于謂詞公式P，如果至少存在一個(gè)解釋使得公式P在此解釋下的真值為T，則稱公式P是可滿足的。按照定義3.9，對(duì)謂詞公式P，如果不存在任何解釋，使得P的取值為T，則稱公式P是不可滿足的。所以，謂詞公式P永假與不可滿足是等價(jià)的。若P永假，則也可稱P是不可滿足的。 謂詞公式的等價(jià)性與永真蘊(yùn)含定義3.10 設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域。若對(duì)D上的任何一個(gè)解釋，P與Q的取值都相同，則公式P和Q在域D上是等價(jià)的。如果D是任意個(gè)體域，則稱P和Q是等價(jià)的，記作PÛ Q。常用的一些等價(jià)式參見教材 定義3

14、.11 對(duì)于謂詞公式P和Q，如果PQ永真，則稱P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記作P=>Q。 以后要用到的一些永真蘊(yùn)含式參見教材謂詞邏輯中還有如下一些推理規(guī)則：（1）P規(guī)則：在推理的任何步驟上都可引入前提。（2）T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)永真蘊(yùn)含公式S，則可把S引入推理過(guò)程中。（3）CP規(guī)則：如果能從R和前提集合中推出S來(lái)，則可從前提集合推出RS來(lái)。（4）反證法：P=>Q，當(dāng)且僅當(dāng)PQÛF，即Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)PQ 是不可滿足的。推廣之，可得如下定理。定理3.1 Q為P1，P2，Pn的邏輯結(jié)論，當(dāng)且僅當(dāng)(P1P2Pn)Q是不可滿

15、足的。 置換與合一1. 置換置換的定義定義3.12 置換是形如t1/x1,t2/x2,tn/xn的一個(gè)有限集。其中xi是變量，ti是不同于xi的項(xiàng)（常量，變量，函數(shù)），且xi ¹xj（I¹j），i，j=1,2,n 。 例如，a/x,b/y,f(x)/z，f(z)/x,y/z都是置換。不含任何元素的置換稱為空置換，以表示。 置換乘法 置換乘法作用是將兩個(gè)置換合成為一個(gè)置換。定義3.13假設(shè) q=t1/x1,t2/x2,tn/xn，l=u1/y1,u2/y2,um/ym是兩個(gè)置換，則它們的乘積是一個(gè)新置換，其作用于公式E時(shí)，相當(dāng)于先q后對(duì)E的作用。它的定義如下：先作置換t1&#

16、183;l/x1,t2·l/x2,tn·l/xn,u1/y1,u2/y2,um/ym。若yiÎ x1,xn時(shí)，先從上述集合中刪除ui/yi 。若 ti· l =xi時(shí)，再?gòu)纳鲜黾现袆h除ti· l /xi 。刪除以后剩下元素所構(gòu)成的集合稱作q與l的乘積，記作q · l 。置換結(jié)合率一般地說(shuō)，下列的置換結(jié)合律成立 (q · l) · m= q ·(l · m) ，但除了空置換外，置換的交換律不成立。即只有e·q=q·e = q 。 2. 合一合一的概念定義3.14 設(shè)有公式集E

17、1,E2,En和置換 ，使 E1 = E2 =En ，便稱E1，E2，En是可合一的 ，且稱為合一置換。定義3.15 若E1，E2，En 有合一置換，且對(duì)E1，E2，En 的任一置換都存在一個(gè)置換，使得= · ，則稱是E1，E2，En 的最一般合一置換，記為mgu。最一般合一置換的求取算法設(shè)有兩個(gè)謂詞公式： E1：P(x,y,z); E2：P(x,f(a),g(b)分別從E1與E2的第一個(gè)符號(hào)開始逐個(gè)向右比較，此時(shí)發(fā)現(xiàn)E1中的y與E2中的f(a)不同，則它們構(gòu)成了一個(gè)不一致集：D1=y,f(a) ，當(dāng)繼續(xù)向右比較時(shí)，又發(fā)現(xiàn)中E1中的z與E2中g(shù)(b)不同，則又得到一個(gè)不一致集： D2

18、=z,g(b)。 下面給出求公式E1,E2的最一般合一置換的算法：（1）令W= E1,E2 。（2）令 k=0,Wk=W,k=;是空置換,它表示不作置換。（3）如果Wk只有一個(gè)表達(dá)式，則算法停止，k就是所要求的mgu。（4）找出Wk的不一致集Dk 。 （5）若Dk中存在元素xk和tk ，其中xk是變?cè)瑃k是項(xiàng)，且xk不在tk中出現(xiàn)，則置： k+1=k ·tk/xk Wk+1=wktk/xk k=k+1 然后轉(zhuǎn)（3）。（6）算法終止，W的mgu不存在。可以證明，如果E1和E2可合一，則算法必停止于第（3）步。 例3.5 設(shè)E1=P(a,v,f(g(y)，E2=P(z,f(a),f(u

19、)，求E1 和E2的mgu。解題請(qǐng)參見教材 答案為：3= a/z ,f(a)/v,g(y)/u。 3就是E1 和E2的mgu。3.4 自然演繹推理方法 自然演繹推理的概念 自然演繹推理是指從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過(guò)程。 假言三段論的基本形式為： PQ，QRÞPR 它表示如果謂詞公式PQ和QR均為真，則謂詞公式PR也為真。 假言推理可用下列形式表示： P，PQ Þ Q它表示如果謂詞公式P和PQ都為真，則可推得Q為真結(jié)論。 拒取式的一般形式為： PQ，Q Þ P它表示如果謂詞公式PQ為真且Q為假，則可推得P為假的結(jié)論。

20、 利用演繹推理解決問(wèn)題 在利用自然演繹推理方法求解問(wèn)題時(shí)，一定要注意避免兩種類型的錯(cuò)誤：肯定后件的錯(cuò)誤和否定前件的錯(cuò)誤。 肯定后件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過(guò)肯定后件Q為真來(lái)推出前件P為真。這顯然是錯(cuò)誤的推理邏輯，因?yàn)楫?dāng) PQ及 Q為真時(shí)，前件 P既可能為真，也可能為假。 否定前件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過(guò)否定前件P來(lái)推出后件Q為假。這也是不允許的，因?yàn)楫?dāng)PQ及P為假時(shí)，后件Q既可能為真，也可能為假。 3.4 自然演繹推理方法 演繹推理的特點(diǎn)3.5 歸結(jié)推理方法 研究用計(jì)算機(jī)實(shí)現(xiàn)定理證明的機(jī)械化，已是人工智能研究的一個(gè)重要領(lǐng)域。對(duì)于定理證明問(wèn)題，如果用一階謂詞邏輯表示的話，就是要求對(duì)

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

22、形范式中消去全部存在量詞所得到的公式即為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)是一個(gè)合取范式，稱為Skolem標(biāo)準(zhǔn)型的母式。將謂詞公式G化為Skolem標(biāo)準(zhǔn)型的步驟如下：（1）消去謂詞公式G中的蘊(yùn)涵（）和雙條件符號(hào)（ « ），以AB代替AB，以(AB)(AB)替換A«

23、;B。（2）減少否定符號(hào)（）的轄域，使否定符號(hào)“”最多只作用到一個(gè)謂詞上。（3）重新命名變?cè)?，使所有的變?cè)拿志煌?，并且自由變?cè)凹s束變?cè)嗖煌?。?）消去存在量詞。這里分兩種情況，一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時(shí)，只要用一個(gè)新的個(gè)體常量替換該存在量詞約束的變?cè)?，就可以消去存在量詞；另一種情況是，存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，這時(shí)需要用一個(gè)Skolem函數(shù)替換存在量詞而將其消去。（5）把全稱量詞全部移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。（6）母式化為合取范式：任何母式都可以寫成由一些謂詞公式和謂詞公式否定的析取的有限集組成的合取。 需

24、要指出的是，由于在化解過(guò)程中，消去存在量詞時(shí)作了一些替換，一般情況下，G的Skolem標(biāo)準(zhǔn)型與G并不等值。2子句與子句集定義3.16 不含有任何連接詞的謂詞公式叫原子公式，簡(jiǎn)稱原子，而原子或原子的否定統(tǒng)稱文字。定義3.17 子句就是由一些文字組成的析取式。定義3.18 不包含任何文字的子句稱為空子句，記為NIL。定義3.19 由子句構(gòu)成的集合稱為子句集。3不可滿足意義下的一致性定理3.2 設(shè)有謂詞公式G，而其相應(yīng)的子句集為S，則G是不可滿足的充分必要條件是S是不可滿足的。 要再次強(qiáng)調(diào)：公式G與其子句集S并不等值，只是在不可滿足意義下等價(jià)。 4PP1P2Pn的子句集 當(dāng)PP1P2Pn時(shí)，若設(shè)P的

25、子句集為SP，Pi的子句集為Si，則一般情況下，SP并不等于S1S2S3Sn，而是要比S1S2S3Sn復(fù)雜得多。但是，在不可滿足的意義下，子句集SP與S1S2S3Sn是一致的，即 SP不可滿足ÛS1S2S3Sn不可滿足 Herbrand理論1H域 定義3.20 設(shè)謂詞公式G的子句集為S，則按下述方法構(gòu)造的個(gè)體變?cè)騂。稱為公式G或子句集S的Herbrand域，簡(jiǎn)稱H域。（1） 令H0是S中所出現(xiàn)的常量的集合。若S中沒有常量出現(xiàn)，就任取一個(gè)常量aÎD，規(guī)定H0=a。（2） 令 Hi+1=HiS中所有的形如f(t1,tn)的元素，其中f(t1,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，

26、而t1，tn是Hi中的元素。i=0，1，2，。例3.10 求子句集ST(x)Q(z),R(f(y)的H域。解 此例中沒有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量；只有一個(gè)函數(shù)f(y)，有：H0=aH1=a,f(a)H2=a,f(a),f(f(a)H=a,f(a),f(f(a),f(f(f(a),2原子集定義3.21 下列集合稱為子句集S的原子集：A所有形如P(t1, t2,tn)的元素其中，P(t1, t2,tn)是出現(xiàn)在S中的任一謂詞符號(hào)，而t1，t2，tn則是S的H域上的任意元素。定義3.22 將沒有變?cè)霈F(xiàn)的原子、文字、子句和子句集分別稱作基原子、基文字、基子句和基子句集。定義3.23

27、當(dāng)子句集S中的某個(gè)子句C中的所有變?cè)?hào)均以其H域中的元素替換時(shí)，所得到的基子句稱作C的一個(gè)基例。 例如，對(duì)于子句集 SP(a),P(x)P(f(x) 它的H域?yàn)閍,f(a),f(f(a),。 對(duì)于子句P(a)，因?yàn)槠渲胁缓凶冊(cè)运咽腔泳?，而且aÎH，所以它也是基例。 3H域上的解釋定義3.24 如果子句集S的原子集為A，則對(duì)A中各元素的真假值的一個(gè)具體設(shè)定都是S的一個(gè)H解釋?？梢宰C明，在給定域D上的任一個(gè)解釋I，總能在H域上構(gòu)造一個(gè)解釋I*與之對(duì)應(yīng)，使得如果D域上的解釋能滿足子句集S，則在H域的解釋I*也能滿足S（即若S|I=T，就有S|I*=T）。定理3.3 設(shè)I是子句

28、集S在域D上的一個(gè)解釋，則存在對(duì)應(yīng)于I的H域解釋I*，使得若有 S|I=T，就必有S|I*=T。定理3.4 子句集S不可滿足的充要條件是S對(duì)H域上的一切解釋都為假。 證明 充分性：若S在一般域D上是不可滿足的，必然在H域上是不可滿足的，從而對(duì)H域上的一切解釋都為假。必要性：若S在任一H解釋I*下均為假，必然會(huì)使S在D域上的每一個(gè)解釋為假。否則，如果存在一個(gè)解釋I0使S為真，那么依據(jù)定理3.3可知，一定可以在H域找到相對(duì)應(yīng)的一個(gè)解釋I*0使S為真。這與S在所有H解釋下均為假矛盾。定理3.5 子句集S不可滿足的充分必要條件是存在一個(gè)有限的不可滿足的基例集S。該定理稱為Herbrand定理，下面給出

29、它的簡(jiǎn)要證明。證明 充分性：設(shè)子句集S有一個(gè)不可滿足的基例集S，因?yàn)樗豢蓾M足，所以一定存在一個(gè)解釋I使S為假。根據(jù)H域上的解釋與D域上的解釋的對(duì)應(yīng)關(guān)系，可知在D域上一定存在一個(gè)解釋使S不可滿足，從而證明了子句集S是不可滿足的。必要性：設(shè)子句集S不可滿足，由定理3.4可知，S對(duì)H域上的所有解釋均為假。這樣，就至少會(huì)存在一個(gè)S中的某子句Ci的基例Ci為假。既然至少有一個(gè)基例Ci為假，因而S的基例集S是不可滿足的。另外，由于S中的子句是有限的，而每個(gè)子句又由有限的文字組成，因而S的不可滿足的基例集也是有限的。 歸結(jié)原理定義3.25 若P是原子謂詞公式或原子命題，則稱P與P為互補(bǔ)文字。1命題邏輯中的

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

31、性的推理過(guò)程如下： (1)  對(duì)子句集S中的各子句間使用歸結(jié)推理規(guī)則。 (2)  將歸結(jié)所得的歸結(jié)式放入子句集S中，得新子句集S。 (3)  檢查子句集S中是否有空子句(NIL),若有則停止推理;否則轉(zhuǎn)（4）。 (4)  置S=S，轉(zhuǎn)步驟（1）。2一階謂詞邏輯中的歸結(jié)原理下面是謂詞邏輯關(guān)于歸結(jié)的定義。定義3.27 設(shè)C1和C2是兩個(gè)沒有相同變?cè)淖泳?，L1 和L2分別是C1 和C2的文字，如果L1與 L2有mgu ，則把 C12 =( C1L1)(C2 L2) 稱作子句C1 和C2的一個(gè)二元?dú)w結(jié)式，而L1 和L2是被歸結(jié)的文字。 為了說(shuō)明的方便。將Ci和

32、Li寫成集合形式， 如P(x)Q(y)®P(x),Q(y)。在集合的表示下做減法或做并運(yùn)算，然后再寫成子句形，如集合運(yùn)算結(jié)果為P(x),Q(y)，可改寫為P(x)Q(y)。 在謂詞邏輯中，對(duì)子句進(jìn)行歸結(jié)推理時(shí)，要注意以下幾個(gè)問(wèn)題：（1）若被歸結(jié)的子句C1 和C2中具有相同的變?cè)獣r(shí)，需要將其中一個(gè)子句的變?cè)?，否則可能無(wú)法做合一置換。從而沒有辦法進(jìn)行歸結(jié)。 （2）在求歸結(jié)式時(shí)，不能同時(shí)消去兩個(gè)互補(bǔ)文字對(duì)，消去兩個(gè)互補(bǔ)文字對(duì)所得的結(jié)果不是兩個(gè)親本子句的邏輯推論。（3）如果在參加歸結(jié)的子句內(nèi)含有可合一的文字，則在進(jìn)行歸結(jié)之前，應(yīng)對(duì)這些文字進(jìn)行合一，以實(shí)現(xiàn)這些子句內(nèi)部的化簡(jiǎn)。 應(yīng)用因子的概

33、念，可對(duì)謂詞邏輯中的歸結(jié)原理定義如下。 定義3.28 設(shè)C1和 C2是沒有相同變?cè)淖泳洌瑒t下列四種二元?dú)w結(jié)式都叫做C1和C2的歸結(jié)式，仍記作C12。（1）  C1與C2的二元?dú)w結(jié)式。（2）  C1的因子C11與C2的二元?dú)w結(jié)式。（3）  C1與C2的因子C22的二元?dú)w結(jié)式。（4）  C1的因子C11與C2的因子C22的二元?dú)w結(jié)式。例 設(shè)C1=P(a)Q(x)R(x)，C2 =P(y)Q(b)， 求其二元?dú)w結(jié)式。解 若選L1=P(a)，L2=P(y)，則L1和L2的mgu是=a/y，于是由定義3.27得C1和C2 的二元?dú)w結(jié)式為 C12 =(

34、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歸結(jié)原理的完備性 對(duì)于一階謂詞邏輯，從不可滿足的意義上說(shuō)，歸結(jié)原理是完備的。即若子句集是不可滿足的，則必存在一個(gè)從該子句集到空子句的歸結(jié)推理過(guò)程；反之，若從子句集到空子句存在一個(gè)歸結(jié)推理過(guò)程，則該子句集必是不可滿足的。 利用歸結(jié)原理進(jìn)行定理證明應(yīng)用歸結(jié)原理進(jìn)行定理證明的步驟如下： 設(shè)要被證明的定理可用謂詞公式表示為如下的形式： A1A2An

35、B(1)  首先否定結(jié)論B，并將否定后的公式B與前提公式集組成如下形式的謂詞公式： G= A1A2AnB(2)  求謂詞公式G的子句集S。(3)  應(yīng)用歸結(jié)原理，證明子句集S的不可滿足性，從而證明謂詞公式G的不可滿足性。這就說(shuō)明對(duì)結(jié)論B的否定是錯(cuò)誤的，推斷出定理的成立。例 已知：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化為子句集P(x,y)Q(y) R(f(x)P(x,y

36、)Q(y) T(x,f(x) /(1)(2)為AR(z)P(a，b)Q(b) /(3)(4)(5)為B下面進(jìn)行歸結(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）與（7）歸結(jié)所以B是A的邏輯結(jié)論。 應(yīng)用歸結(jié)原理進(jìn)行問(wèn)題求解下面是利用歸結(jié)原理求取問(wèn)題答案的步驟：（1）把已知前提條件用謂詞公式表示出來(lái)，并化成相應(yīng)的子句集，設(shè)該子句集的名字為S1。（2）把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后將其否定，并與一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個(gè)專為求解問(wèn)題而設(shè)置的謂詞，其變量必

37、須與問(wèn)題公式的變量完全一致。（3）把問(wèn)題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1合并構(gòu)成子句集S。（4）對(duì)子句集S應(yīng)用謂詞歸結(jié)原理進(jìn)行歸結(jié)，在歸結(jié)的過(guò)程中，通過(guò)合一置換，改變ANSWER中的變?cè)＃?）如果得到歸結(jié)式ANSWER ，則問(wèn)題的答案即在ANSWER謂詞中。例任何兄弟都有同一個(gè)父親，John和Peter是兄弟，且John的父親是David，問(wèn)Peter的父親是誰(shuí)？解第一步：將已知條件用謂詞公式表示出來(lái)，并化成子句集，那么要先定義謂詞。（1） 定義謂詞：設(shè)Father(x,y)表示x是y的父親。Brother(x,y)表示x和y是兄弟。（2） 將已知事實(shí)用謂詞公

38、式表示出來(lái)。 F1 ：任何兄弟都有同一個(gè)父親。 (x)(y)(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)第二步：把問(wèn)題用謂詞公式表示出來(lái)，并將其否定與謂詞ANSWER作析取。 設(shè)Peter的父親是u，則有：Father(u,Pete

39、r)。 將其否定與ANSWER作析取，得： G：Father(u,Peter)ANSWER(u)第三步：將上述公式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)。第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(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(píng)=David。即Peter的父親