第5章基于謂詞邏輯的機(jī)器推理

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

第7章幾種結(jié)構(gòu)化知識表示及其推理第8章不確定性知識的表示與推理概述知識及其表示

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

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

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

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

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

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

q：6是偶數(shù)

r：6能被2整除則推理的形式結(jié)構(gòu)符號化為：(p

q)

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

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

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

（1）對全稱量詞，把限定謂詞作為蘊(yùn)含式之前件加入，即x（p（x）→…）。（2）對于存在量詞，把限定謂詞作為一個(gè)合取項(xiàng)加入，即x（p（x）∧…）。例：不存在最大的整數(shù)分析：命題中“不存在最大的”顯然是對所有的整數(shù)而言，所以可理解為“對所有的x，如果x是整數(shù)，則一定還有比x大的整數(shù)”；再具體點(diǎn)，即“對所有的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)結(jié)詞可以表達(dá)相當(dāng)復(fù)雜的命題。抽象的來看，我們把命題的這種符號表達(dá)式稱為謂詞公式。項(xiàng)：（定義1）（1）個(gè)體常元和個(gè)體變元都是項(xiàng)（2）f是n元函數(shù)，若t1,t2,…,tn

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

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

解：表達(dá)式中的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是約束變元。

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

特別地，我們稱xA(x)為全稱命題，xA(x)為特稱命題。當(dāng)個(gè)體域?yàn)橛邢藜瘯r(shí)，如D={a1,a2,…,an}，對于任意的謂詞A(x)，都有①

xA(x)A(a1)

A(a2)…

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

A(a2)…

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

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

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

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

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

解：令S(x)：x是大學(xué)生；M(x)：x學(xué)過計(jì)算機(jī)；a：小王。則上面兩個(gè)命題可用謂詞公式表示為（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）的邏輯結(jié)果。

證：

（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))上述推理過程完全是一個(gè)符號變換過程。類似于人們用自然語言推理的思維過程，因而成為自然演繹推理。這種推理實(shí)際上已幾乎與謂詞公式所表示的含義完全無關(guān)，而是一種形式推理。于是，可將這種推理方法引入機(jī)器推理。自然演繹推理實(shí)施困難，推理規(guī)則太多、應(yīng)用規(guī)則需要很強(qiáng)的模式識別能力、中間結(jié)論呈指數(shù)增長引入新的推理技術(shù)——?dú)w結(jié)演繹推理技術(shù)歸結(jié)——消解（Resolution），由Robinson于1965年提出，大大推動(dòng)了自動(dòng)定理證明的發(fā)展5.2歸結(jié)演繹推理5.2.1子句集定義1原子謂詞公式及其否定稱為文字，若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句，由r個(gè)文字組成的子句叫r—文字子句，1—文字子句叫單元子句，不含任何文字的子句稱為空子句，記為□或NIL。例：

P∨Q∨﹁R

P(x,y)∨﹁

Q(x)

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

①﹁(﹁A)AE1②﹁(A∧B)﹁A∨﹁BE12③﹁(A∨B)﹁A∧﹁BE13④﹁xp(x)x﹁P(X)E29⑤﹁xP(X)﹁xp(x)E30(4)消去存在量詞消去存在量詞時(shí)，同時(shí)還要進(jìn)行變元替換。變元替換分兩種情況：①若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變元，這樣的函數(shù)稱為Skolem函數(shù)。②若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號代替該存在量詞轄域中的相應(yīng)約束變元，這樣的常量符號稱為Skolem常量。(6)化公式為合取范式可使用邏輯等價(jià)式：①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)]}消去蘊(yùn)含詞由步(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))]}消存在量詞，標(biāo)準(zhǔn)型由步(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標(biāo)準(zhǔn)型上述步驟步（4）所得式子就是Skolem標(biāo)準(zhǔn)型：把所有全稱量詞都依次移到整個(gè)式子的最左邊（或者先把所有量詞都依次移到整個(gè)最左邊，再消去存在量詞），再將右部的式子化為合取范式，這時(shí)所得的式子稱為原公式的Skolem標(biāo)準(zhǔn)型。消去Skolem標(biāo)準(zhǔn)型左部的全稱量詞和合取詞，即得公式的子句集。例5.8設(shè)G=xyzuvw(P(x,y,z)∧﹁Q(u,v,w)那么，用a替代x，用f(y,z)替代u，用g(y,z,v)代替w，則得G的Skolem標(biāo)準(zhǔn)型

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)}由此例得出，一個(gè)公式的子句集也可以通過先求前束范式，再求Skolem標(biāo)準(zhǔn)型而得到。量詞在最前面，后面不含量詞的式子注意：引入Skolem函數(shù)，是由于存在量詞在全稱量詞的轄域內(nèi)，其約束變元的取值則完全依賴于全稱量詞的取值。Skolem函數(shù)反應(yīng)了這種依賴關(guān)系。Skolem標(biāo)準(zhǔn)型與原公式一般并不等價(jià)，所以經(jīng)過變換后的子句集S，與謂詞公式G不等價(jià)。定理1謂詞公式G不可滿足當(dāng)且僅當(dāng)其子句集S不可滿足。把證明G的不可滿足轉(zhuǎn)化為證明子句集S的不可滿足。定義3子句集S是不可滿足的，當(dāng)且僅當(dāng)其全部子句的合取式是不可滿足的。5.2.2命題邏輯中的歸結(jié)原理定義4

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

﹁P∨R∨S定理2歸結(jié)式是其親本子句的邏輯結(jié)果。證明：設(shè)C1=L∨C1’,C2=﹁L∨C2’,C1’,C2’都是文字的析取式，則C1,C2的歸結(jié)式為C1’∨C2’,因?yàn)镃1=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是兩個(gè)子句，L1,L2分別是C1,C2中的文字，且L1,L2互補(bǔ)。此規(guī)則就是命題邏輯中的歸結(jié)原理。

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

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

﹁A

解

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

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

L∧﹁L=F所以，空子句恒為假，即□F有了空子句□，那么我們就可以用歸結(jié)原理來推導(dǎo)空子句，反向證明。①求出要證的命題的否定式的子句集；②對子句集進(jìn)行消解，尋找空子句，若存在，則子句集不可滿足，從而原否定式不可滿足，那么原公式是永真的。即，否定式子句集S假，則﹁S為真，要證命題為真。推論設(shè)C1,C2是子句集S的兩個(gè)子句，C12是它們的歸結(jié)式，則：（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用歸結(jié)原理證明R是P,(P∧Q)→R,(S∨U)→Q,U的邏輯結(jié)果。證由所給條件得到子句集S=｛P,﹁

P∨﹁

Q∨R,﹁

S∨Q,﹁

U∨Q,U,﹁

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

P∨﹁

Q∨R)∧(﹁

S∨Q)∧(﹁

U∨Q)∧U∧﹁

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

5.2.3替換與合一一階謂詞邏輯中含有個(gè)體變元，因此應(yīng)用消解原理不像命題邏輯中那樣簡單，尋找含互否文字的子句對的操作比較復(fù)雜。例：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)

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

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

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

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

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

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

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

θ={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}可以證明，替換的乘積滿足結(jié)合律，即(θ·λ)·u=θ·(λ·u)定義9設(shè)S=｛F1,F2,…,Fn｝是一個(gè)原子謂詞公式集，若存在一個(gè)替換θ，可使F1θ=F2θ=…=Fnθ，則稱θ為S的一個(gè)合一(Unifier)，稱S為可合一的。定義10設(shè)σ是原子公式集S的一個(gè)合一，如果對S的任何一個(gè)合一θ，都存在一個(gè)替換λ，使得

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

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

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

θ=σ·λ得出結(jié)論：如果能夠找到一個(gè)公式集的合一，特別是最一般合一，則可使互否文字的形式結(jié)構(gòu)完全一致起來，進(jìn)而達(dá)到消解的目的。怎么求一個(gè)公式集的最一般合一？有一個(gè)算法可以求出，為了解該算法，先引入差異集。定義11設(shè)S是一個(gè)非空的具有相同謂名詞的原子公式集，從S中各公式的左邊第一項(xiàng)開始，同時(shí)向右比較，知道發(fā)現(xiàn)第一個(gè)不都相同的項(xiàng)為止，用這些項(xiàng)的差異部分組成一個(gè)集合，這個(gè)集合就是原公式集S的一個(gè)差異集。例5.15設(shè)S={P(x,y,z),P(x,f(a),h(b))},則不難看出，S有兩個(gè)差異集D1={y,f(a)}D2={z,h(b)}合一算法步1置k=0，Sk=S，σk=ε。步2若Sk只含有一個(gè)謂詞公式，則算法停止，σk就是要求的最一般合一。步3求Sk的差異集Dk。步4若Dk中存在元素xk和tk，其中xk是變元，tk是項(xiàng)且xk不在tk中出現(xiàn)，則置Sk+1=Sk{tk/xk,σk+1=σk·{tk/xk},k=k+1,然后轉(zhuǎn)步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))}只含有一個(gè)謂詞公式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在項(xiàng)f(y)中出現(xiàn)，所以算法停止，不存在最一般合一。兩個(gè)都是變元，所以有兩種替換方法，因此最一般合一可能不唯一。定理3（合一定理）如果S是一個(gè)非空有限可合一公式集，則合一算法總是在步2停止，且最后的σk即是S的最一般合一。5.2.4謂詞邏輯中的歸結(jié)原理定義12設(shè)C1,C2是兩個(gè)無相同變元的子句，L1,L2分別是C1,C2中的兩個(gè)文字，如果L1和L2有最一般合一σ，則子句(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)稱作C1和C2的二元?dú)w結(jié)式(二元消解式)，C1和C2稱作歸結(jié)式的親本子句，L1和L2稱作消解文字。例5.18設(shè)C1=P(x)∨Q(x),C2=﹁P(a)∨R(y)，求C1,C2的歸結(jié)式。解取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的二元?dú)w結(jié)式。

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

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

還需說明的是，如果在參加歸結(jié)的子句內(nèi)部含有可合一的文字，則在進(jìn)行歸結(jié)之前，也應(yīng)對這些文字進(jìn)行合一，從而使子句達(dá)到最簡。例如，設(shè)有兩個(gè)子句：C1=P(x)∨P(f(a))∨Q(x)C2=﹁P(y)∨R(b)定義13如果子句C中，兩個(gè)或兩個(gè)以上的文字有一個(gè)最一般合一σ，則Cσ稱為C的因子，如果Cσ是單元子句，則Cσ稱為C的單因子。例5.20設(shè)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謂詞邏輯中的消解式是它的親本子句的邏輯結(jié)果。由此定理我們即得謂詞邏輯中的推理規(guī)則：

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

例5.21求證G是A1和A2的邏輯結(jié)果。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)然后應(yīng)用消解原理，得(6)R(a)［(2),(3),σ1=｛a/y｝］(7)﹁R(a)［(4),(5),σ2=｛a/z｝］(8)□［(6),(7)］所以S是不可滿足的，從而G是A1和A2的邏輯結(jié)果。(A1)(A2)S例5.22設(shè)已知：(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))需證結(jié)論

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

圖5-2例5.22歸結(jié)演繹樹

定理5（歸結(jié)原理的完備性定理）如果子句集S是不可滿足的，那么必存在一個(gè)由S推出空子句□的消解序列。(該定理的證明要用到Herbrand定理，故從略。)5.3應(yīng)用歸結(jié)原理求取問題答案例5.23已知：（1）如果x和y是同班同學(xué)，則x的老師也是y的老師。（2）王先生是小李的老師。（3）小李和小張是同班同學(xué)。問：小張的老師是誰？解：定義謂詞：T(x,y)：x是y的老師；C(x,y)：x，y是同班同學(xué)改寫已知條件為謂詞公式：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)歸結(jié)演繹，得（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為真，小張的老師存在，為了尋找該老師，給原來求證謂詞的子句增加一個(gè)謂詞ANS(u)。于是有：（4）’﹁T(u,Zhang)∨ANS(u)用（4）’替換（4），則可得到結(jié)果（7）’ANS(Wang)歸結(jié)原理求取問題的方法:（1）尋找問題的合適求證目標(biāo)謂詞；（2）增配（析取形式）一個(gè)輔助謂詞（輔助謂詞中變元與目標(biāo)謂詞變元一致）；（3）歸結(jié)，直至歸結(jié)式剛好剩下輔助謂詞，即得問題答案。5.4歸結(jié)策略問題：前面用歸結(jié)方法是人工的，這不是最終目的，人工智能要實(shí)現(xiàn)的是機(jī)器的推理，那么就需要自動(dòng)推理。這樣，怎樣讓機(jī)器去自動(dòng)歸結(jié)子句就成為一個(gè)需要考慮的重要方面。自動(dòng)推理就是需要把算法用程序表示，讓計(jì)算機(jī)運(yùn)行。算法如下：步1將子句集S置入CLAUSES表。步2若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。步3若CLAUSES表中存在可歸結(jié)的子句對，則將歸結(jié)式并入CLAUSES表，轉(zhuǎn)步2。步4歸結(jié)失敗，退出。該怎樣選擇參與消解的子句？窮舉式歸結(jié)方式

1、讓所有子句兩兩進(jìn)行歸結(jié)，產(chǎn)生歸結(jié)式集合S1，S1并入原CLAUSES中，記為S1’。

2、讓新CLAUSES中子句，即集合S1’與S1中子句兩兩歸結(jié)，產(chǎn)生歸結(jié)式集合S2，S2并入S1’中，記為S2’。

3、以此類推，直至□。例5.25設(shè)有如下的子句集S，我們用上述的窮舉算法歸結(jié)如下：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)□歸