第5章基于謂詞邏輯的機器推理

第3篇知識與推理概述第5章基于謂詞邏輯的機器推理第6章基于產生式規(guī)則的機器推理

第7章幾種結構化知識表示及其推理第8章不確定性知識的表示與推理概述知識及其表示

◆一些常用的知識表示形式：一階謂詞邏輯、產生式規(guī)則、框架、語義網絡、類和對象、模糊集合、貝葉斯網絡、腳本、過程等。機器推理

◆演繹推理、歸納推理和類比推理

◆不確定性推理和不確切性推理◆約束推理、定性推理、范例推理、非單調推理第5章基于謂詞邏輯的機器推理主要內容1、一階謂詞邏輯2、歸結演繹推理3、應用歸結原理求取問題答案4、歸結策略5、Horn子句歸結與邏輯程序

基于謂詞邏輯的機器推理也稱自動推理。它是人工智能早期的主要研究內容之一。一階謂詞邏輯是一種表達力很強的形式語言，而且這種語言很適合當前的數(shù)字計算機。因而就成為知識表示的首選。基于這種語言，不僅可以實現(xiàn)類似于人推理的自然演繹法自動推理，而且也可實現(xiàn)不同于人的歸結（或稱消解）法自動推理。本節(jié)主要介紹基于謂詞邏輯歸結演繹推理。5.1一階謂詞邏輯5.1.1謂詞、函數(shù)、量詞

命題：凡可確定真假的陳述句稱為命題?？梢匀≈怠罢妗保═）或“假”（F）在一定的條件下，只能取其中一個值例：（1）北京是中國的首都√（2）3+2>10×（3）禁止吸煙（祈使句）

A(a1,a2,…,an)在謂詞邏輯中就表示一個原子命題。如：素數(shù)（2），表示命題“2是個素數(shù)”。命題的表達例：凡偶數(shù)都能被2整除，6是偶數(shù)。所以，6能被2整除將它們命題符號化：p：凡偶數(shù)都能被2整除

q：6是偶數(shù)

r：6能被2整除則推理的形式結構符號化為：(p

q)

r由于上式不是重言式（永真式），所以不能由它判斷推理的正確性。為了克服命題邏輯的局限性，就應該將簡單命題再細分，分析出個體詞、謂詞和量詞，以期達到表達出個體與總體的內在聯(lián)系和數(shù)量關系，這就是謂詞邏輯。(1)８是自然數(shù)。(2)21世紀末，人類將住在月球。(3)x+y=y+x(4)只有x能被2整除，x才能被4整除。個體詞x,y的取值范圍：復數(shù)域a的取值范圍：整數(shù)域表示具體或特定的客體的個體詞稱作個體常項；常用a,b,c,…表示。表示抽象或泛指的客體的個體詞稱作個體變項；常用x,y,z,…表示。個體變項的取值范圍為個體域，個體域可以是有窮集合，也可以是無窮集合。全總個體域：由宇宙間一切事物組成的域為全總個體域。

謂詞謂詞：是用來刻畫個體詞的性質或個體詞之間的關系的詞（帶參量的命題叫謂詞）n元謂詞，P（x1,x2,x3,…,xn）P是謂詞符號，代表一個確定的特征（一個參量）或關系（多個參量）x1,x2,x3,…,xn

稱為參量或項（個體常元或個體變元）論述域（個體域）：個體變元的取值范圍例：北京是一個城市——CITY（北京）x是人——HUMAN（x）A是B的兄弟——兄弟（A，B）x大于y——G（x，y）不帶個體變元的謂詞公式叫命題，命題是謂詞公式的特例一般的用F(a)表示個體常項a具有性質F（F是謂詞常項或謂詞變項），用F(x)表示個體變項x具有性質F。而用F(a,b)表示個體常項a,b具有關系F，用F(x,y)表示個體變項x,y具有關系F。函數(shù)為了表達個體之間的關系，我們引入通常數(shù)學中函數(shù)的概念和記法。例如我們用father(x)表示x的父親，用sum(x,y)表示x和y之和，一般地，我們用如下形式：f(x1,x2,…,xn)表示個體變元x1，x2，…，xn所對應的個體y，并稱之為n元個體函數(shù)，簡稱函數(shù)（或函詞、函詞命名式）。有了函數(shù)的概念和記法，謂詞的表達能力就更強了。例如，Doctor(father(Li))表示“小李的父親是醫(yī)生）。我們約定：（1）用大寫應為字母作為謂詞符號；（2）用小寫字母f，g，h等表示函數(shù)符號；（3）用小寫字母x，y，z等作為個體變元符號；（4）用小寫字母a，b，c等作為個體常元符號。邏輯連接詞：研究單個謂詞是不夠的，還必須研究多個謂詞之間的關系，這需要引入邏輯連接詞?：否定詞?A讀為“非A”，當A為真時，?A為假，當A為假時，?A為真∧：合取詞A∧B讀為“A并且B”，當且僅當A和B都為真時，A∧B為真，否則A∧B為假∨：析取詞A∨B讀為“A或者B”，當且僅當A和B都為假時，A∨B為假，否則A∨B為真→：蘊涵詞A→B讀為“若A則B”，當且僅當A為真，且B為假時，A→B為假，否則A→B為真在A→B中，A稱為前件，B稱為后件：等值詞AB讀為“A等值于B”，當且僅當A和B同為真或同為假時，AB為真，否則AB為假量詞有些陳述句包含表示數(shù)量的詞，如“所有”、“任一”、“存在”、“至少有一個”等，為了表示這樣的陳述句，需引入新的符號，稱為量詞。全稱量詞（x）表示“對于所有的x…”例：凡是人都有名字——（x）（M（x）→N（x））（x）A（x）A（a1）∧A（a2）∧…∧A（an），若論域為有限集合，且a1、a2、…、an是論域中的所有個體。存在量詞（x）表示“對于某個x…”例：存在不是偶數(shù)的整數(shù)——（x）（G（x）∧?E（x））（x）A（x）A（a1）∨A（a2）∨…∨A（an）不同的個體變元，可能有不同的個體域。為了方便和統(tǒng)一起見，我們用謂詞表示命題時，一般總取全總個體域，然后再采取使用限定謂詞的辦法來指出每個個體變元的個體域。具體來講，有下面兩條：

（1）對全稱量詞，把限定謂詞作為蘊含式之前件加入，即x（p（x）→…）。（2）對于存在量詞，把限定謂詞作為一個合取項加入，即x（p（x）∧…）。例：不存在最大的整數(shù)分析：命題中“不存在最大的”顯然是對所有的整數(shù)而言，所以可理解為“對所有的x，如果x是整數(shù)，則一定還有比x大的整數(shù)”；再具體點，即“對所有的x如果x是整數(shù)，則一定存在y，y也是整數(shù)，并且y比x大”。則可以翻譯成如下形式：﹁x（G（x）∧y（G（y）→D（x，y））或x（G（x）→y（G（y）∧D（y，x））例：對于所有的自然數(shù)，均有x+y>x

xy（N(x)∧N(y）→S(x，y，x））例：某些人對某些食物過敏xy（M（x）∧F（y）G（x，y）5.1.2謂詞公式用謂詞、量詞及真值聯(lián)結詞可以表達相當復雜的命題。抽象的來看，我們把命題的這種符號表達式稱為謂詞公式。項：（定義1）（1）個體常元和個體變元都是項（2）f是n元函數(shù)，若t1,t2,…,tn

是項，則f(t1,t2,…,tn)是項，（3）只有有限次使用（1）、（2）得到的符號串才是項原子公式：（定義2）設P為n元謂詞符號，t1,t2,…,tn是項，則P（t1,t2,…,tn）稱為原子謂詞公式，簡稱原子公式謂詞公式：（定義3）（1）原子公式是謂詞公式（2）若A、B是謂詞公式，則A∧B、A∨B、?A、A→B、AB、xA、xA也是謂詞公式（3）只有有限次應用（1）、（2）生成的公式才是謂詞公式謂詞公式又稱為謂詞邏輯中的合式公式，記為Wff(well-formedformula)幾個概念：轄域：緊接于量詞之后被量詞作用的（說明的）謂詞公式稱為該量詞的轄域指導變元、約束變元和自由變元改名規(guī)則，保證一個變元或者是約束變元，或者是自由變元例：x（H（x）→G（x,y））∧xA（x）∧B（x）量詞的轄域定義:量詞的轄域是鄰接量詞之后的最小子公式，故除非轄域是個原子公式，否則應在該子公式的兩端有括號。例：XP(X)→Q(X)

X的轄域是P(X)X(P(X,Y)→Q(X，Y))P(Y,Z)

X的轄域是P(X，Y)→Q(X，Y)定義：量詞后的變元如x，y中的x，y成為量詞的指導變元（或作用變元）。在量詞X，X轄域內變元X的一切出現(xiàn)叫約束出現(xiàn)，稱這樣的X為約束變元。

變元的非約束出現(xiàn)稱為自由出現(xiàn),稱這樣的變元為自由變元。例：指出下列謂詞公式中的自由變元和約束變元，并指明量詞的轄域（1）X(P(X)R(X))→XP(X)Q(X)

解：表達式中的X(P(X)R(X))中X的轄域是P(X)R(X),其中的X是約束出現(xiàn)

Q(X)中的X是自由變元

例：指出下列謂詞公式中的自由變元和約束變元。并指明量詞的轄域(2)X(P(X，Y)→YR(X，Y))解：其中的P(X，Y)中的Y是自由變元，X是約束變元，R(X，Y)中的X，Y是約束變元。

注：在一個公式中，一個變元既可以約束出現(xiàn)，又可以自由出現(xiàn)。為避免混淆可用改名規(guī)則對變元改名。約束變元改名規(guī)則（1）對需改名的變元，應同時更改該變元在量詞及其轄域中的所有出現(xiàn)。（2）新變元符號必須事量詞轄域內原先沒有的，最好是公式中也未出現(xiàn)過的。例如公式xP(x)Q(x)可改為yP(y)Q(x)，二者意義相同。量化在謂詞前加上量詞，稱作謂詞中相應的個體變元被量化，例如xA(x)中的x被量化。如果一個謂詞中的所有個體變元都被量化，則這個謂詞就變成了一個命題。這樣，我們就有兩種從謂詞得到命題的方法：（1）給謂詞中的個體變元代入個體常元。（2）把謂詞中的個體變元全部量化。一階謂詞：僅個體變元被量化的謂詞稱為一階謂詞。二階謂詞：不僅個體變元被量化，而且函數(shù)符號和謂詞符號也被量化，這樣的謂詞稱為二階謂詞。

特別地，我們稱xA(x)為全稱命題，xA(x)為特稱命題。當個體域為有限集時，如D={a1,a2,…,an}，對于任意的謂詞A(x)，都有①

xA(x)A(a1)

A(a2)…

A(an)②xA(x)A(a1)

A(a2)…

A(an)這實際上是將謂詞邏輯中命題公式轉化為命題邏輯中的命題公式問題。合取范式：（定義4）A為合取范式，B1∧B2∧…∧Bn,其中Bi形如L1∨

L2∨…∨Lm,Lj為原子公式或其否定例：（P（x）∨Q（y））∧（?P（x）∨Q（y）∨R（x，y））∧…任一謂詞公式均可化為與之等價的合取范式，但一般不唯一析取范式：（定義5）A為析取范式，B1∨B2∨…∨Bn,其中Bi形如L1∧

L2∧…∧Lm,Lj為原子公式或其否定例：（P（x）∧Q（y））∨（?P（x）∧Q（y）∧R（x，y））∨…任一謂詞公式均可化為與之等價的析取范式，但一般不唯一定義6設P為謂詞公式，D為其個體域，對于D中的任一解釋I：（1）若P恒為真，則稱P在D上永真（或有效）或是D上的永真式。（2）若P恒為假，則稱P在D上永假（或不可滿足）或是D上的永假式。（3）若至少有一個解釋，可使P為真，則稱P在D上可滿足或是D上的可滿足式。定義7設P為謂詞公式，對于任何個體域：（1）若P都永真，則稱P為永真式。（2）若P都永假，則稱P為永假式。（3）若P都可滿足，則稱P為可滿足式。5.1.3謂詞邏輯中的形式演繹推理謂詞公式之間的關系常用邏輯等價式表5.1注意與的區(qū)別，是等價符號，說明兩個謂詞公式之間的等價性，是邏輯連接詞，是謂詞公式的組成部分

常用邏輯蘊涵式表5.2注意與的區(qū)別，是推導符號，說明由左邊的謂詞公式可以推導出右邊的謂詞公式，是邏輯連接詞，是謂詞公式的組成部分

自然演繹推理：（1）將自然語言命題轉化為謂詞公式（2）利用上面的邏輯等價式和邏輯蘊涵式，可以進行推理，得出一些隱含在謂詞公式中的結論利用一階謂詞邏輯的這種形式語言，就可以把關于自然語言的邏輯推理問題，轉換為這種符號表達式的推演變換。例5.4設有前提：（1）凡是大學生都學過計算機；（2）小王是大學生。試問：小王學過計算機嗎？

解：令S(x)：x是大學生；M(x)：x學過計算機；a：小王。則上面兩個命題可用謂詞公式表示為（1）x(S(X)→M(x))（2）S(a)問題：M(a)是否成立？形式推理如下：（1）x(S(X)→M(x))[前提]（2）S(a)→M(x)[(1)，US]（3）S(a)[前提]（4）M(a)[（2），（3），I3]例5.5證明﹁P(a，b)是xy（P(x，y)→W（x，y）和﹁W（a，b）的邏輯結果。

證：

（1）xy（P(x，y)→W（x，y）[前提]（2）y（P(a，y)→W（a，y）[(1),US]（3）（P(a，b)→W（a，b）[(2),US]（4）﹁W（a，b）[前提]（5）﹁P(a，b)[(3),(4),I4]例5.6證明x(P(x)→Q(x))∧x(R(x)→﹁Q(x))x(R(x)→﹁(P(x))。

證：

（1）x(P(x)→Q(x))[前提]（2）P(y)→Q(y)[(1),US]（3）﹁Q(y)→﹁P(y)[(2),E24]（4）x(R(x)→﹁Q(x))[前提]（5）R(y)→﹁Q(y)[(3),US]（6）R(y)→﹁P(y)[(3),(5),I6]（7）x(R(x)→﹁(P(x))上述推理過程完全是一個符號變換過程。類似于人們用自然語言推理的思維過程，因而成為自然演繹推理。這種推理實際上已幾乎與謂詞公式所表示的含義完全無關，而是一種形式推理。于是，可將這種推理方法引入機器推理。自然演繹推理實施困難，推理規(guī)則太多、應用規(guī)則需要很強的模式識別能力、中間結論呈指數(shù)增長引入新的推理技術——歸結演繹推理技術歸結——消解（Resolution），由Robinson于1965年提出，大大推動了自動定理證明的發(fā)展5.2歸結演繹推理5.2.1子句集定義1原子謂詞公式及其否定稱為文字，若干個文字的一個析取式稱為一個子句，由r個文字組成的子句叫r—文字子句，1—文字子句叫單元子句，不含任何文字的子句稱為空子句，記為□或NIL。例：

P∨Q∨﹁R

P(x,y)∨﹁

Q(x)

定義2對一個謂詞公式G，通過以下步驟所得的子句集合S，稱為G的子句集。(1)消去蘊含詞→和等值詞←→。(2)縮小否定詞﹁的作用范圍，直到其僅作用于原子公式。(3)適當改名，使量詞間不含同名指導變元和約束變元。(4)消去存在量詞。(5)消去所有全稱量詞。(6)化公式為合取范式。(7)適當改名，使子句間無同名變元。(8)消去合取詞∧，以子句為元素組成集合S。(1)消去蘊含詞→和等值詞←→使用邏輯等價式①A→B﹁A∨BE14②AB(﹁A∨B)∧(﹁B∨A)E15（2）縮小否定詞﹁的作用范圍，直到其僅作用于原子公式使用邏輯等價式：

①﹁(﹁A)AE1②﹁(A∧B)﹁A∨﹁BE12③﹁(A∨B)﹁A∧﹁BE13④﹁xp(x)x﹁P(X)E29⑤﹁xP(X)﹁xp(x)E30(4)消去存在量詞消去存在量詞時，同時還要進行變元替換。變元替換分兩種情況：①若該存在量詞在某些全稱量詞的轄域內，則用這些全稱量詞指導變元的一個函數(shù)代替該存在量詞轄域中的相應約束變元，這樣的函數(shù)稱為Skolem函數(shù)。②若該存在量詞不在任何全稱量詞的轄域內，則用一個常量符號代替該存在量詞轄域中的相應約束變元，這樣的常量符號稱為Skolem常量。(6)化公式為合取范式可使用邏輯等價式：①A∨(B∧C)(A∨B)∧(A∨C)②(A∧B)∨C(A∨C)∧(B∨C)例5.7求下面謂詞公式的子句集

x{yP(x,y)﹁y[Q(x,y)R(x,y)]}解：由步(1)得x{﹁yP(x,y)∨﹁y[﹁Q(x,y)∨R(x,y)]}消去蘊含詞由步(2)得x{y﹁P(x,y)∨y[Q(x,y)∧﹁R(x,y)]}縮小否定詞﹁范圍由步(3)得x{y﹁P(x,y)∨z[Q(x,z)∧﹁R(x,z)]}改名由步(4)得x{﹁P(x,f(x))∨[Q(x,g(x))∧﹁R(x,g(x))]}消存在量詞，標準型由步(5)得﹁P(x,f(x))∨[Q(x,g(x))∧﹁R(x,g(x))]消全稱量詞，US由步(6)得[﹁P(x,f(x))∨Q(x,g(x))]∧[﹁P(x,f(x))∨﹁R(x,g(x))]E9由步(7)得[﹁P(x,f(x))∨Q(x,g(x))]∧[﹁P(y,f(y))∨﹁R(y,g(y))]改名由步(8)得{﹁P(x,f(x))∨Q(x,g(x)),﹁P(y,f(y))∨﹁R(y,g(y))}消去合取詞或﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))Skolem標準型上述步驟步（4）所得式子就是Skolem標準型：把所有全稱量詞都依次移到整個式子的最左邊（或者先把所有量詞都依次移到整個最左邊，再消去存在量詞），再將右部的式子化為合取范式，這時所得的式子稱為原公式的Skolem標準型。消去Skolem標準型左部的全稱量詞和合取詞，即得公式的子句集。例5.8設G=xyzuvw(P(x,y,z)∧﹁Q(u,v,w)那么，用a替代x，用f(y,z)替代u，用g(y,z,v)代替w，則得G的Skolem標準型

yzv(P(a,y,z)∧﹁Q(f(y,z),v,g(y,z,v)那么可以得到G的子句集為{P(a,x,y),﹁Q(f(u,v),w,g(u,v,w)}由此例得出，一個公式的子句集也可以通過先求前束范式，再求Skolem標準型而得到。量詞在最前面，后面不含量詞的式子注意：引入Skolem函數(shù)，是由于存在量詞在全稱量詞的轄域內，其約束變元的取值則完全依賴于全稱量詞的取值。Skolem函數(shù)反應了這種依賴關系。Skolem標準型與原公式一般并不等價，所以經過變換后的子句集S，與謂詞公式G不等價。定理1謂詞公式G不可滿足當且僅當其子句集S不可滿足。把證明G的不可滿足轉化為證明子句集S的不可滿足。定義3子句集S是不可滿足的，當且僅當其全部子句的合取式是不可滿足的。5.2.2命題邏輯中的歸結原理定義4

設L為一個文字，則稱L與﹁L為互補文字。定義5設C1,C2是命題邏輯中的兩個子句，C1中有文字L1，C2中有文字L2，且L1與L2互補，從C1,C2中分別刪除L1,L2，再將剩余部分析取起來，記構成的新子句為C12，則稱C12為C1,C2的歸結式(或消解式)，C1,C2稱為其歸結式的親本子句，L1,L2稱為消解基。例5.9設C1=﹁P∨Q∨R,C2=﹁Q∨S,則C1,C2的歸結式為

﹁P∨R∨S定理2歸結式是其親本子句的邏輯結果。證明：設C1=L∨C1’,C2=﹁L∨C2’,C1’,C2’都是文字的析取式，則C1,C2的歸結式為C1’∨C2’,因為C1=C1’∨L=﹁C1’LC2=﹁L∨C2’=LC2’所以C1∧C2=(﹁C1’L)∧(LC2’)﹁C1’C2’=C1’∨C2’I6假言三段論由定理2即得推理規(guī)則：

C1∧C2(C1-｛L1｝)∪(C2-｛L2｝)其中C1,C2是兩個子句，L1,L2分別是C1,C2中的文字，且L1,L2互補。此規(guī)則就是命題邏輯中的歸結原理。

例5.10用歸結原理驗證分離規(guī)則和拒取式

A∧(A→B)B(A→B)∧﹁B

﹁A

解

A∧(A→B)＝A∧(﹁A∨B)B(A→B)∧﹁B＝(﹁A∨B)∧(﹁B)

﹁A類似可以驗證其他推理規(guī)則也都可以經消解原理推出。如果兩個互否的單元子句進行歸結，則歸結式為空子句，即L∧﹁L=□并且

L∧﹁L=F所以，空子句恒為假，即□F有了空子句□，那么我們就可以用歸結原理來推導空子句，反向證明。①求出要證的命題的否定式的子句集；②對子句集進行消解，尋找空子句，若存在，則子句集不可滿足，從而原否定式不可滿足，那么原公式是永真的。即，否定式子句集S假，則﹁S為真，要證命題為真。推論設C1,C2是子句集S的兩個子句，C12是它們的歸結式，則：（1）若用C12代替C1,C2，得到新子句集S1，則由S1的不可滿足可推出原子句集S的不可滿足。即S1不可滿足S不可滿足（2）若把C12加入到S中，得到新子句集S2，則S2與原S的不可滿足等同。即S2不可滿足S不可滿足例5.11證明子句集{P∨﹁Q,﹁P,Q}是不可滿足的。證(1)P∨﹁Q(2)﹁P(3)Q(4)﹁Q由(1),(2)(5)□由(3),(4)所以，子句集S不可滿足。例5.12用歸結原理證明R是P,(P∧Q)→R,(S∨U)→Q,U的邏輯結果。證由所給條件得到子句集S=｛P,﹁

P∨﹁

Q∨R,﹁

S∨Q,﹁

U∨Q,U,﹁

R｝然后對該子句集施行歸結，歸結過程用下面的歸結演繹樹表示（見圖5―1）。由于最后推出了空子句，所以子句集S不可滿足，即命題公式P∧(﹁

P∨﹁

Q∨R)∧(﹁

S∨Q)∧(﹁

U∨Q)∧U∧﹁

R不可滿足，從而R是題設前提的邏輯結果。圖5―1例5.12歸結演繹樹

5.2.3替換與合一一階謂詞邏輯中含有個體變元，因此應用消解原理不像命題邏輯中那樣簡單，尋找含互否文字的子句對的操作比較復雜。例：C1=P(x)∨Q(x)C2=﹁P(a)∨R(y)若用a替換C1中的x，則得到C1′=P(a)∨Q(a)C2′=﹁P(a)∨R(y)則消解式為

C3’=C1’∧C2’=Q(a)∨R(y)

結論：要在謂詞邏輯中應用消解原理，則一般需要對個體變元作適當?shù)奶鎿Q。定義6

一個替換(Substitution)是形如｛t1/x1,t2/x2,…,tn/xn｝的有限集合，其中t1,t2,…,tn是項，稱為替換的分子；x1,x2,…,xn是互不相同的個體變元，稱為替換的分母；ti不同于xi，xi也不循環(huán)地出現(xiàn)在tj(i,j=1,2,…,n)中；ti/xi表示用ti替換xi。若t1,t2,…,tn都是不含變元的項（稱為基項）時，該替換稱為基替換；沒有元素的替換稱為空替換，記作ε，它表示不作替換。例如：

｛a/x,g(y)/y,f(g(b))/z｝就是一個替換，而

{g(y)/x,f(x)/y}則不是一個替換,因為x與y出現(xiàn)了循環(huán)替換。下面我們將項、原子公式、文字、子句等統(tǒng)稱為表達式，沒有變元的表達式稱為基表達式，出現(xiàn)在表達式E中的表達式稱為E的子表達式。定義7設θ=｛t1/x1,…,tn/xn｝是一個替換，E是一個表達式，把對E施行替換θ，即把E中出現(xiàn)的個體變元xj(1≤j≤n)都用tj替換，記為Eθ，所得的結果稱為E在θ下的例(instance)。例如，若θ={a/x,f(b)/y,c/z},則Gθ=P(a,f(b),c)。定義8設θ=｛t1/x1,…,tn/xn｝，

λ={u1/y1,…，um/ym}是兩個替換，則將集合

{t1λ/x1，…，tnλ/xn，u1/y1,…，um/ym}中凡符合下列條件的元素刪除：（1）tiλ/xi當tiλ=xi

（2）ui/yi當yi?{x1，…，xi}這樣得到的集合仍然是一個替換，該替換稱為θ與λ的復合或乘積，記為θ·λ。例5.13設

θ={f(y)/x,z/y}

λ={a/x,b/y,y/z}于是，{t1λ/x1，t2λ/x2，u1/y1，u2/y2，u3/y3}={f(b)/x,y/y,a/x,b/y,y/z}可以證明，替換的乘積滿足結合律，即(θ·λ)·u=θ·(λ·u)定義9設S=｛F1,F2,…,Fn｝是一個原子謂詞公式集，若存在一個替換θ，可使F1θ=F2θ=…=Fnθ，則稱θ為S的一個合一(Unifier)，稱S為可合一的。定義10設σ是原子公式集S的一個合一，如果對S的任何一個合一θ，都存在一個替換λ，使得

θ=σ·λ則稱σ為S的最一般合一(MostGeneralUnifier)，簡稱MGU。

例5.14設S=｛P(u,y,g(y)),P(x,f(u),z)｝，S有一個最一般合一σ=｛u/x,f(u)/y,g(f(u))/z｝對S的任一合一，例如：

θ=｛a/x,f(a)/y,g(f(a))/z,a/u｝存在一個替換λ=｛a/u｝使得

θ=σ·λ得出結論：如果能夠找到一個公式集的合一，特別是最一般合一，則可使互否文字的形式結構完全一致起來，進而達到消解的目的。怎么求一個公式集的最一般合一？有一個算法可以求出，為了解該算法，先引入差異集。定義11設S是一個非空的具有相同謂名詞的原子公式集，從S中各公式的左邊第一項開始，同時向右比較，知道發(fā)現(xiàn)第一個不都相同的項為止，用這些項的差異部分組成一個集合，這個集合就是原公式集S的一個差異集。例5.15設S={P(x,y,z),P(x,f(a),h(b))},則不難看出，S有兩個差異集D1={y,f(a)}D2={z,h(b)}合一算法步1置k=0，Sk=S，σk=ε。步2若Sk只含有一個謂詞公式，則算法停止，σk就是要求的最一般合一。步3求Sk的差異集Dk。步4若Dk中存在元素xk和tk，其中xk是變元，tk是項且xk不在tk中出現(xiàn)，則置Sk+1=Sk{tk/xk,σk+1=σk·{tk/xk},k=k+1,然后轉步2。步5算法停止，S的最一般合一不存在。例5.16求公式集S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的最一般合一。解：k=0：S0=S,σ0=ε,S0不是單元集，求得D0={a，z}，其中z是變元，且不在a中出現(xiàn)，所以有

σ1=σ0·{a/z}=ε·{a/z}={a/z}S1=S0{a/z}={P(a,x,f(g(y))),P(a,h(a,u),f(u))}k=1:S1不是單元集,D1={x，h(a,u)},所以

σ2=σ1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x}S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}只含有一個謂詞公式k=2:S2不是單元集,D2={g(y)，u}，所以

σ3=σ2·{g(y)/u}={{a/z,h(a,u)/x}·{g(y)/u}={a/z,h(a,g(y))/u}S3=S2{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:S3是單元集，所以σ3就是S的最一般合一。例5.17判定S={P(x,x),P(y,f(y))是否可合一？解：k=0：S0=S,σ0=ε,S0不是單元集，求得D0={x,y}

σ1=σ0·{y/x}=ε·{y/x}={y/x}S1=S0{y/x}={P(y,y),P(y,f(y))k=1：S1不是單元集，求得D1={y,f(y)}，變元y在項f(y)中出現(xiàn)，所以算法停止，不存在最一般合一。兩個都是變元，所以有兩種替換方法，因此最一般合一可能不唯一。定理3（合一定理）如果S是一個非空有限可合一公式集，則合一算法總是在步2停止，且最后的σk即是S的最一般合一。5.2.4謂詞邏輯中的歸結原理定義12設C1,C2是兩個無相同變元的子句，L1,L2分別是C1,C2中的兩個文字，如果L1和L2有最一般合一σ，則子句(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)稱作C1和C2的二元歸結式(二元消解式)，C1和C2稱作歸結式的親本子句，L1和L2稱作消解文字。例5.18設C1=P(x)∨Q(x),C2=﹁P(a)∨R(y)，求C1,C2的歸結式。解取L1=P(x),L2=﹁P(a),則L1與﹁L2的最一般合一σ=｛a/x｝，于是,(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)=(｛P(a),Q(a)｝-｛P(a)｝)∪(｛﹁P(a),R(y)｝-｛﹁P(a)｝)=｛Q(a),R(y)｝=Q(a)∨R(y)所以，Q(a)∨R(y)是C1和C2的二元歸結式。

例5.19設C1=P(x,y)∨﹁Q(a),C2=Q(x)∨R(y),求C1,C2的歸結式。

解由于C1,C2中都含有變元x,y，所以需先對其中一個進行改名,方可歸結（歸結過程是顯然的，故從略）。

還需說明的是，如果在參加歸結的子句內部含有可合一的文字，則在進行歸結之前，也應對這些文字進行合一，從而使子句達到最簡。例如，設有兩個子句：C1=P(x)∨P(f(a))∨Q(x)C2=﹁P(y)∨R(b)定義13如果子句C中，兩個或兩個以上的文字有一個最一般合一σ，則Cσ稱為C的因子，如果Cσ是單元子句，則Cσ稱為C的單因子。例5.20設C=P(x)∨P(f(y))∨﹁Q(x),令σ=｛f(y)/x｝，于是Cσ=P(f(y))∨﹁Q(f(y))是C的因子。定義14子句C1,C2的消解式，是下列二元消解式之一：(1)C1和C2的二元消解式;(2)C1和C2的因子的二元消解式;(3)C1的因子和C2的二元消解式;(4)C1的因子和C2的因子的二元消解式。定理4謂詞邏輯中的消解式是它的親本子句的邏輯結果。由此定理我們即得謂詞邏輯中的推理規(guī)則：

C1∧C2(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)其中C1,C2是兩個無相同變元的子句，L1,L2分別是C1,C2中的文字，σ為L1與L2的最一般合一。此規(guī)則稱為謂詞邏輯中的消解原理（或歸結原理）。

例5.21求證G是A1和A2的邏輯結果。A1:x(P(x)→(Q(x)∧R(x)))A2:x(P(x)∧S(x))G:x(S(x)∧R(x))

證我們用反證法，即證明A1∧A2﹁G不可滿足。首先求得子句集S：

(1)﹁P(x)∨Q(x)(2)﹁P(y)∨R(y)(3)P(a)(4)S(a)(5)﹁S(z)∨﹁R(z)(﹁G)然后應用消解原理，得(6)R(a)［(2),(3),σ1=｛a/y｝］(7)﹁R(a)［(4),(5),σ2=｛a/z｝］(8)□［(6),(7)］所以S是不可滿足的，從而G是A1和A2的邏輯結果。(A1)(A2)S例5.22設已知：(1)能閱讀者是識字的；(2)海豚不識字；(3)有些海豚是很聰明的。試證明：有些聰明者并不能閱讀。證首先，定義如下謂詞：R(x)：x能閱讀。L(x)：x識字。I(x)：x是聰明的。D(x)：x是海豚。然后把上述各語句翻譯為謂詞公式：(1)x(R(x)→L(x))(2)x(D(x)→﹁L(x))已知條件(3)x(D(x)∧I(x))(4)x(I(x)∧﹁R(x))需證結論

求題設與結論否定的子句集，得(1)﹁R(x)∨L(x)(2)﹁D(y)∨﹁L(y)(3)D(a)(4)I(a)(5)﹁I(z)∨R(z)歸結得(6)R(a)(5)，(4)，{a/z}(7)L(a)(6)，(1)，{a/x}(8)﹁D(a)(7),(2),{a/y}(9)□(8),(3)這個歸結過程的演繹樹如圖5―2所示。

圖5-2例5.22歸結演繹樹

定理5（歸結原理的完備性定理）如果子句集S是不可滿足的，那么必存在一個由S推出空子句□的消解序列。(該定理的證明要用到Herbrand定理，故從略。)5.3應用歸結原理求取問題答案例5.23已知：（1）如果x和y是同班同學，則x的老師也是y的老師。（2）王先生是小李的老師。（3）小李和小張是同班同學。問：小張的老師是誰？解：定義謂詞：T(x,y)：x是y的老師；C(x,y)：x，y是同班同學改寫已知條件為謂詞公式：F1：xyz(C(x,y)∧T(z,x)T(z,y)F2：T(Wang,Li)F2：C(Li,Zhang)為了得到問題的答案，我們先證明小張的老師是存在的，即證明公式：G：xT(x,Zhang)反證法：求F1∧

F2∧

F3∧﹁G的子句集：（1）﹁

C(x,y)∨﹁

T(z,x)∨

T(z,y)（2）T(Wang,Li)（3）C(Li,Zhang)（4）﹁T(u,Zhang)歸結演繹，得（5）﹁

C(Li,y)∨T(Wang,Li)由(1),(2),{Wang/z,Li/x}（6）﹁

C(Li,Zhang)由(4),(5),{Wang/u,Zhang/y}（7）□由(3),(6)G為真，小張的老師存在，為了尋找該老師，給原來求證謂詞的子句增加一個謂詞ANS(u)。于是有：（4）’﹁T(u,Zhang)∨ANS(u)用（4）’替換（4），則可得到結果（7）’ANS(Wang)歸結原理求取問題的方法:（1）尋找問題的合適求證目標謂詞；（2）增配（析取形式）一個輔助謂詞（輔助謂詞中變元與目標謂詞變元一致）；（3）歸結，直至歸結式剛好剩下輔助謂詞，即得問題答案。5.4歸結策略問題：前面用歸結方法是人工的，這不是最終目的，人工智能要實現(xiàn)的是機器的推理，那么就需要自動推理。這樣，怎樣讓機器去自動歸結子句就成為一個需要考慮的重要方面。自動推理就是需要把算法用程序表示，讓計算機運行。算法如下：步1將子句集S置入CLAUSES表。步2若空子句NIL在CLAUSES中，則歸結成功，結束。步3若CLAUSES表中存在可歸結的子句對，則將歸結式并入CLAUSES表，轉步2。步4歸結失敗，退出。該怎樣選擇參與消解的子句？窮舉式歸結方式

1、讓所有子句兩兩進行歸結，產生歸結式集合S1，S1并入原CLAUSES中，記為S1’。

2、讓新CLAUSES中子句，即集合S1’與S1中子句兩兩歸結，產生歸結式集合S2，S2并入S1’中，記為S2’。

3、以此類推，直至□。例5.25設有如下的子句集S，我們用上述的窮舉算法歸結如下：S：(1)P∨Q(2)﹁P∨Q(3)P∨﹁Q(4)﹁P∨﹁QS1：(5)Q[(1),(2)]

(6)P[(1),(3)](7)Q∨﹁Q[(1),(4)](8)P∨﹁P[(1),(4)]

(9)Q∨﹁Q[(2),(3)](10)P∨﹁P[(2),(3)]

(11)﹁P[(2),(4)](12)﹁Q[(3),(4)]S2：(13)P∨Q[(1),(7)](14)P∨Q[(1),(8)](15)P∨Q[(1),(9)](16)P∨Q[(1),(10)](17)Q[(1),(11)](18)P∨Q[(1),(10)](19)Q[(2),(6)]……(39)□歸