1、基于謂詞邏輯的機(jī)器推理人類的智能活動(dòng)過(guò)程主要是一個(gè)獲得知識(shí)并運(yùn)用知識(shí)的過(guò)程，知識(shí)是智能的基礎(chǔ)。為了使計(jì)算機(jī)具有智能，使它能模擬人類的智能行為，就必須使它具有知識(shí)。但是，需要把人類擁有的知識(shí)采用適當(dāng)?shù)哪Ｊ奖硎境鰜?lái)，才能存儲(chǔ)到計(jì)算機(jī)中去，這就是用知識(shí)表示要解決的問(wèn)題。知識(shí)表示是對(duì)知識(shí)的一種描述?；蛘哒f(shuō)是一組約定，是一種計(jì)算機(jī)可以接受的、用于描述知識(shí)的數(shù)據(jù)結(jié)構(gòu)，對(duì)知識(shí)進(jìn)行表示就是把知識(shí)表示成便于計(jì)算機(jī)存儲(chǔ)和利用的某種數(shù)據(jù)結(jié)構(gòu)。目前使用較多的知識(shí)表示方法主要有：一階謂詞邏輯表示法、產(chǎn)生式表示法、框架表示法、語(yǔ)義網(wǎng)絡(luò)表示法等。第5章 基于謂詞邏輯的機(jī)器推理本章介紹一階謂詞邏輯(Predicate Log

2、ic)表示法及基于一階謂詞邏輯的機(jī)器推理，主要介紹基于謂詞邏輯的歸結(jié)演繹推理。謂詞邏輯是一種形式語(yǔ)言，也是目前能夠表達(dá)人類思維活動(dòng)的一種最精確的語(yǔ)言，它與人類的自然語(yǔ)言比較接近，又可以方便地存儲(chǔ)到計(jì)算機(jī)中，并被計(jì)算機(jī)進(jìn)行精確處理。因此，它成為最早應(yīng)用于人工智能中表示知識(shí)的一種邏輯表示法。第5章 基于謂詞邏輯的機(jī)器推理謂詞邏輯是在命題(Propositional)邏輯的基礎(chǔ)上發(fā)展起來(lái)的，對(duì)于知識(shí)的形式化表示，特別是在定理的自動(dòng)證明中發(fā)揮了重要作用，在人工智能發(fā)展史中占有重要地位。命題是具有真假意義的語(yǔ)句。命題代表人們進(jìn)行思維時(shí)的一種判斷，或是肯定，或是否定，只有這兩種情況。一個(gè)命題不能同時(shí)即為真

3、又為假，但可以在一定條件下為真，在另一種條件下為假。沒有真假意義的語(yǔ)句（如感嘆句、疑問(wèn)句等）不是命題。在謂詞邏輯中，命題是用謂詞表示的。第5章 基于謂詞邏輯的機(jī)器推理本章主要介紹基于謂詞邏輯的歸結(jié)演繹推理。內(nèi)容如下：5.1 一階謂詞邏輯 5.2 歸結(jié)演繹推理5.3 應(yīng)用歸結(jié)原理求取問(wèn)題答案5.4 歸結(jié)策略5.5 歸結(jié)反演程序舉例5.6 Horn子句歸結(jié)與邏輯程序 5.7 非歸結(jié)演繹推理第5章 基于謂詞邏輯的機(jī)器推理本章主要介紹基于謂詞邏輯的歸結(jié)演繹推理。內(nèi)容如下：5.1 一階謂詞邏輯 5.1.1 謂詞、函數(shù)、量詞5.1.2 謂詞公式5.1.3 謂詞邏輯中的形式演繹推理第5章 基于謂詞邏輯的機(jī)器

4、推理5.1. 一階謂詞邏輯 5.1.1. 謂詞、函數(shù)、量詞謂詞：一個(gè)謂詞可分為謂詞名與個(gè)體兩個(gè)部分。個(gè)體表示某個(gè)獨(dú)立存在的事物或者某個(gè)抽象的概念，謂詞名用來(lái)刻畫個(gè)體的屬性、狀態(tài)或個(gè)體之間的關(guān)系。一般地，表達(dá)式 P(x1，x2，xn)在謂詞邏輯中稱為n元謂詞。其中P是謂詞符號(hào)，也稱謂詞，代表一個(gè)確定的特征或關(guān)系。x1，x2，xn稱為謂詞的參量或者項(xiàng)，一般表示個(gè)體。 設(shè)a1，a2，an表示個(gè)體對(duì)象，A表示它們的屬性、狀態(tài)或關(guān)系，則表達(dá)式 A(a1，a2，an)。在謂詞邏輯中就表示一個(gè)(原子)命題。例如，(1)素?cái)?shù)(2)，就表示命題“2是個(gè)素?cái)?shù)”。質(zhì)數(shù)又稱素?cái)?shù)。指在一個(gè)大于1的自然數(shù)中，除了1和此整

5、數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。換句話說(shuō)，只有兩個(gè)正因數(shù)（1和自己）的自然數(shù)即為素?cái)?shù)。比1大但不是素?cái)?shù)的數(shù)稱為合數(shù)。1和0既非素?cái)?shù)也非合數(shù)。素?cái)?shù)在數(shù)論中有著很重要的地位。(2)好朋友(張三，李四)，就表示命題“張三和李四是好朋友”。P(x1，x2，xn)個(gè)體變?cè)淖兓秶Q為個(gè)體域（或論述域）個(gè)體域可以是有限的，也可以是無(wú)限的，包攬一切事物的集合稱為全總個(gè)體域。5.1.1. 謂詞、函數(shù)、量詞5.1.1. 謂詞、函數(shù)、量詞為了表達(dá)個(gè)體之間的對(duì)應(yīng)關(guān)系，我們引入通常數(shù)學(xué)中函數(shù)的概念和記法。例如我們用father(x)表示x的父親，用sum(x,y)表示數(shù)x和y之和。一般地，我們用如下形式： f(

6、x1，x2，xn)表示個(gè)體變?cè)獂1，x2，xn所對(duì)應(yīng)的個(gè)體yy=f(x1，x2，xn) ，并稱之為n元個(gè)體函數(shù)，簡(jiǎn)稱函數(shù)(或函詞、函詞命名式)。其中f是函數(shù)符號(hào)，有了函數(shù)的概念和記法，謂詞的表達(dá)能力就更強(qiáng)了。例如，我們用Doctor(father(Li)表示“小李的父親是醫(yī)生”，用E(sq(x),y)表示“x的平方等于y”。 5.1.1. 謂詞、函數(shù)、量詞謂詞中的個(gè)體可以是常元，也可以是變?cè)€可以是一個(gè)函數(shù)。個(gè)體常元、個(gè)體變?cè)?、函?shù)統(tǒng)稱為“項(xiàng)”。以后我們約定用大寫英文字母作為謂詞符號(hào)，用小寫字母f，g，h等表示函數(shù)符號(hào)，用小寫字母x，y，z等作為個(gè)體變?cè)?hào)，用小寫字母a，b，c等作為個(gè)體常

7、元符號(hào)。5.1.1. 謂詞、函數(shù)、量詞量詞分為：全稱量詞(Universal Quantification)記為x和存在量詞(Existential Quantification)記為y。我們把“所有”、“一切”、“任一”、“全體”、“凡是”等詞統(tǒng)稱為全稱量詞，記為x ；把“存在”、“有些”、“至少有一個(gè)”、“有的”等詞統(tǒng)稱為存在量詞，記為y 。引入量詞后，謂詞的表達(dá)能力就大大擴(kuò)充了。例如命題“凡是人都有名字”就可以表示為： x(M(x) N(x)5.1.1. 謂詞、函數(shù)、量詞例如命題“凡是人都有名字”就可以表示為：x(M(x) N(x)其中M(x)表示“x是人”，N(x)表示“x有名字”，該

8、式可讀作“對(duì)于任意的x ，如果x是人，則x有名字”。這里的個(gè)體域取為全總個(gè)體域。如果把個(gè)體域取為人類集合，則該命題就可以表示為 x N(x)5.1.1. 謂詞、函數(shù)、量詞同理，我們可以把命題“存在不是偶數(shù)的整數(shù)”表示為 ：x(G(x) E(x) 其中G(x)表示“x是整數(shù)”， E(x)表示“x是偶數(shù)”。此式可讀作“存在x，x是整數(shù)并且x不是偶數(shù)”。5.1.1. 謂詞、函數(shù)、量詞例 不存在最大的整數(shù)，我們可以把它翻譯為 x(G(x) y (G(y) D(x,y)或x(G(x) y(G(y) D(y,x) 其中D(x,y)表示xy ， G(x)表示x是整數(shù)。例 對(duì)于所有的自然數(shù)，均有x+yx xy

9、(N(x) N(y) S(x,y,x)其中S(x,y,x)表示x+yx 。例 某些人對(duì)某些食物過(guò)敏xy(M(x) F(y) G(x,y)其中G(x,y)表示x人對(duì)y食物過(guò)敏。常用的邏輯聯(lián)結(jié)詞有下列五個(gè)：1）聯(lián)結(jié)詞“非”(Negation)，記作“ ”；2）聯(lián)結(jié)詞“與”或者“合取”(Conjunction)，記作“”；3）聯(lián)結(jié)詞“或”或者“析取”(Disjunction)，記作“”；4）聯(lián)結(jié)詞“蘊(yùn)含”或者“蘊(yùn)涵”(Implication) ，記作“”； 它表示被它連接的兩個(gè)命題的“蘊(yùn)含”關(guān)系。如PQ表示“P蘊(yùn)含Q”， 即“如果P，則Q”， 其中P稱為前提，Q稱為后件。聯(lián)結(jié)詞的優(yōu)先級(jí)別是： ， ，

10、 ， ， n 。邏輯聯(lián)結(jié)詞又稱真值聯(lián)結(jié)詞。聯(lián)接詞又稱聯(lián)接詞、連詞、連接詞。5）聯(lián)結(jié)詞“等價(jià)” (Equivalence) ，記作“n”。5.1.1. 謂詞、函數(shù)、量詞常用的邏輯聯(lián)結(jié)詞的真值表設(shè)：G(a)表示“a同學(xué)學(xué)習(xí)好”。G(張三 ) G(李四)如果張三學(xué)習(xí)好，則李四學(xué)習(xí)好。說(shuō)明李四比張三要好。(一大點(diǎn)，一小點(diǎn))。如果G(張三 ) G(李四)，并且同時(shí)G(李四) G(張三)，說(shuō)明什么？TFTTTTFFFFFTFTTTFFTTTTFTFFTF5.1.1. 謂詞、函數(shù)、量詞由上節(jié)可以看出，用謂詞、量詞及真值聯(lián)結(jié)詞可以表達(dá)相當(dāng)復(fù)雜的命題。 抽象的來(lái)看，我們把命題的符號(hào)表達(dá)式稱為謂詞公式。什么是謂詞

11、公式？定義1 (什么是項(xiàng)？)(1)個(gè)體常元和個(gè)體變?cè)际琼?xiàng)。(2)設(shè)f是n元函數(shù)符號(hào)，若t1,t2,tn是項(xiàng)，則f(t1,t2,tn)是項(xiàng)。(3)只有有限次使用(1)，(2)得到的符號(hào)串也（才）是項(xiàng)。定義2 (什么是原子謂詞公式？)設(shè)P為n元謂詞符號(hào)，t1,t2,tn為項(xiàng)，則P(t1,t2,tn)稱為原子謂詞公式，簡(jiǎn)稱原子公式或者原子。 從原子謂詞公式出發(fā)，通過(guò)命題聯(lián)結(jié)詞和量詞，可以組成復(fù)合謂詞公式。下面我們給出謂詞公式的嚴(yán)格定義，即謂詞公式的生成規(guī)則。5.1.2. 謂詞公式定義3 (什么是謂詞公式？)(1) 原子公式是謂詞公式。(2) 若A，B是謂詞公式，則A，AB，AB，AB，AnB也是謂

12、詞。(2)若A(x)是謂詞公式，x是個(gè)體變?cè)瑒txA(x)，xA(x)也是謂詞。(3) 只有有限步應(yīng)用(1)，(2)(2)生成的公式才是謂詞公式。謂詞公式在不會(huì)發(fā)生誤解時(shí)，可簡(jiǎn)稱為公式。由項(xiàng)的定義，當(dāng)t1，t2，tn全為個(gè)體常元時(shí)，所得的原子謂詞公式就是原子命題公式（命題符號(hào)）。所以，全體命題公式也都是謂詞公式。5.1.2. 謂詞公式量詞分為：全稱量詞記為x和存在量詞記為y。緊接于量詞之后被量詞作用(即說(shuō)明)的謂詞公式稱為該量詞的轄域。例：(1) xP(x) P(x)為x的轄域，(2) x(H(x) G(x,y) (H(x) G(y,x) 為x的轄域，(3) xA(x) B(x) A(x)為x

13、的轄域，但B(x)并非x的轄域。量詞后的變?cè)鐇，y中的x， y稱為量詞的指導(dǎo)變?cè)?或作用變?cè)?，而在一個(gè)量詞的轄域中與該量詞的指導(dǎo)變?cè)嗤淖冊(cè)Q為約束變?cè)?，其他變?cè)?如果有的話)稱為自由變?cè)?，例?2)中的x為約束變?cè)鴜為自由變?cè)?3)中A(x)中x的為約束變?cè)?，但B(x)中x的為自由變?cè)?。例?3)，一個(gè)變?cè)谝粋€(gè)公式中既可約束出現(xiàn)，又可自由出現(xiàn)，但為了避免混淆，通常通過(guò)改名規(guī)則，使得一個(gè)公式中一個(gè)變?cè)獌H以一種形式出現(xiàn)。5.1.2. 謂詞公式約束變?cè)母拿?guī)則如下：(1)對(duì)需改名的變?cè)?，?yīng)同時(shí)更改該變?cè)诹吭~及其轄域中的所有出現(xiàn)。(2)新變?cè)?hào)必須是量詞轄域內(nèi)原先沒有的，最好是公

14、式中也未出現(xiàn)過(guò)的。例如公式xA(x) B(x)可改為xA(x) B(y) ，但兩者的意義相同。（ yA(y) B(x)可以嗎？ ）在謂詞前加上量詞，稱作謂詞中的相應(yīng)的個(gè)體變?cè)急涣炕鐇A(x)中的x被量化， yB(y)中的y被量化。5.1.2. 謂詞公式如果一個(gè)謂詞中的所有個(gè)體變?cè)急涣炕?，則這個(gè)謂詞就變?yōu)橐粋€(gè)命題。例如，設(shè)P(x)表示“x是素?cái)?shù)”，則xP(x), xP(x)就都是命題。這樣我們就有兩種從謂詞（即命題函數(shù)）得到命題的方法：一種是給謂詞中的個(gè)體變?cè)雮€(gè)體常元，另一種就是把謂詞中的個(gè)體變?cè)苛炕?。需要說(shuō)明的是，僅個(gè)體變?cè)涣炕闹^詞稱為一階謂詞。如果不僅個(gè)體變?cè)涣炕?/p>

15、且函數(shù)符號(hào)和謂詞符號(hào)也被量化，則那樣的謂詞稱為二階謂詞。在謂詞P(x1, x2, , xn)中，若xi(i=1, 2, , n)都是個(gè)體常元、變?cè)蚝瘮?shù), 則稱它為一階謂詞。若某個(gè)xi本身又是一個(gè)一階謂詞, 則稱P為二階謂詞。余者類推。 本書只涉及一階謂詞, 以后提及的謂詞都是指一階謂詞。5.1.2. 謂詞公式如果一個(gè)公式中的所有個(gè)體變?cè)急涣炕?，或者所有變?cè)际羌s束變?cè)ɑ驘o(wú)自由變?cè)瑒t這個(gè)公式就是一個(gè)命題。特別地，我們稱xA(x)為全稱命題， xA(x)為特稱命題（存量命題）。對(duì)于這兩種命題，當(dāng)個(gè)體域?yàn)橛邢藜瘯r(shí)(設(shè)n有個(gè)元素)，有下面的等價(jià)式：xA(x) A(a1) A(a2) A(an

16、) xA(x) A(a1) A(a2) A(an)這兩個(gè)式子也可以推廣到個(gè)體域?yàn)榭蓴?shù)無(wú)限集。xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) 5.1.2. 謂詞公式定義4（什么是合取范式？）設(shè)A為如下形式的謂詞公式： B1B2Bn其中 Bi (i=1, 2, , n)形如 L1L2 Lm，Lj(j= 1, 2, , m)為原子公式或其否定，則A稱為合取范式。例如：(P(x)Q(y)(P(x)Q(y)R(x,y) (Q(y)R(x,y)就是一個(gè)合取范式。 應(yīng)用邏輯等價(jià)式(P.99-100)，任一謂詞公式都可以化為與之等價(jià)的合取范式，這個(gè)合取范式就是稱

17、為原公式的合取范式。但應(yīng)指出，一個(gè)謂詞公式的合取范式一般不(是)唯一(的)。定義5（析取范式）設(shè)A為如下形式的命題(改為：謂詞)公式：( P.98)例如: (P(x)Q(y)R(x,y)(P(x)Q(y)(P(x)R(x,y)5.1.2. 謂詞公式定義6 設(shè)P為謂詞公式，D為其個(gè)體域，對(duì)于D中的任一解釋I ：(1)若P恒為真, 則稱P在D上永真(或有效)或是D上的永真式。(2)若P恒為假, 則稱P在D上永假(或不可滿足)或是D上的永假式。(3)若至少有一個(gè)解釋, 可使P為真, 則稱P在D上可滿足或是D上的可滿足式。 定義7 設(shè)P為謂詞公式，對(duì)于任何個(gè)體域:(1)若P恒為真，則稱P為的永真式。(

18、2)若P恒為假，則稱P為永假式。(3)若P都可滿足，則稱P為可滿足式。5.1.2. 謂詞公式由于謂詞公式的真值與個(gè)體域及解釋有關(guān)，考慮到個(gè)體域的數(shù)目和個(gè)體域中元素?cái)?shù)目無(wú)限的情形，所以要通過(guò)一個(gè)機(jī)械的執(zhí)行的方法（即算法），判斷一個(gè)謂詞公式的永真性一般是不可能的，所以一般稱一階謂詞邏輯是不可判定的。（但它是半可判定的。） 5.1.2. 謂詞公式作業(yè)：補(bǔ)充作業(yè)：1什么是項(xiàng)、什么是原子謂詞公式、什么是謂詞公式?2什么是謂詞公式的解釋？5.1.3. 謂詞邏輯中的形式演繹推理利用謂詞公式可以將自然語(yǔ)言中的陳述語(yǔ)句表示為一種形式化的符號(hào)表達(dá)式。那么，利用謂詞公式，我們同樣可以將形式邏輯中抽象出來(lái)的推理規(guī)則形

19、式化為一些符號(hào)變換公式。表5.1(P.99-100)和表5.2(P.100)就是形式邏輯中常用的一些邏輯等價(jià)式和邏輯蘊(yùn)含式，即推理規(guī)則的符號(hào)表示形式。表5.1 常用邏輯等價(jià)式5.1.3. 謂詞邏輯中的形式演繹推理利用謂詞公式可以將自然語(yǔ)言中的陳述語(yǔ)句表示為一種形式化的符號(hào)表達(dá)式。那么，利用謂詞公式，我們同樣可以將形式邏輯中抽象出來(lái)的推理規(guī)則形式化為一些符號(hào)變換公式。表5.1(P.99-100)和表5.2(P.100)就是形式邏輯中常用的一些邏輯等價(jià)式和邏輯蘊(yùn)含式，即推理規(guī)則的符號(hào)表示形式。表5.2 常用邏輯蘊(yùn)含式5.1.3. 謂詞邏輯中的形式演繹推理利用謂詞公式可以將自然語(yǔ)言中的陳述語(yǔ)句表示為

20、一種形式化的符號(hào)表達(dá)式。那么，利用謂詞公式，我們同樣可以將形式邏輯中抽象出來(lái)的推理規(guī)則形式化為一些符號(hào)變換公式。表5.1(P.99-100)和表5.2(P.100)就是形式邏輯中常用的一些邏輯等價(jià)式和邏輯蘊(yùn)含式，即推理規(guī)則的符號(hào)表示形式。表常用邏輯等價(jià)式(E1E40)（見P.99100）什么是邏輯等價(jià)式？定義：設(shè)P和Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域。若對(duì)D上的任何一個(gè)解釋，P與Q都有相同的真值，則稱公式P和Q在D上是等價(jià)的。如果D是任意域，則稱P和Q是等價(jià)的。記作： PQ。重要的邏輯等價(jià)式有：E1；E9；E12；E13；E14；E15；E20；E21；E24；E29；E30；5.1.3.

21、 謂詞邏輯中的形式演繹推理E1： A AE9： A(BC) (AB)(AC) E12： (AB) AB E13： (AB) AB E14：AB AB E15：AnB (AB)(BA) E20： AA F E21： AA T E24：AB BAE29： xA(x) xA(x)E30： xA(x) xA(x) 雙重否定律分配律 摩根定律蘊(yùn)含表達(dá)式等價(jià)表達(dá)式矛盾律排中律逆反律量詞轉(zhuǎn)換律5.1.3. 謂詞邏輯中的形式演繹推理表常用邏輯等價(jià)式(E1E40)（見P.99100）表5.2 常用邏輯蘊(yùn)含式(I1I20)（見）什么是永真蘊(yùn)含式？定義：對(duì)于謂詞公式P和Q，如果PQ永真，則稱P永真蘊(yùn)含Q，且稱Q為P

22、的邏輯結(jié)論，稱P為Q的前提，記作： PQ重要的邏輯蘊(yùn)含式有： I3； I4；I6；I11（簡(jiǎn)稱US）；I12（簡(jiǎn)稱ES）；I13（簡(jiǎn)稱UG）；I14（簡(jiǎn)稱EG）；5.1.3. 謂詞邏輯中的形式演繹推理表5.2 常用邏輯蘊(yùn)含式(I1I20)（見）I1：A ABI2：AB A， AB BI3：(AB)A BI4：(AB)B A I6：(AB)(BC) (AC) I11：xA(x) A(y) (簡(jiǎn)稱US)；I12：xA(x) A(y) (簡(jiǎn)稱ES)；I13：A(y) xA(x) (簡(jiǎn)稱UG)；I14：A(y) xA(x) (簡(jiǎn)稱EG)；附加律簡(jiǎn)化律假言推理拒取式假言三段論y是個(gè)體域中的任一確定的元素

23、y是個(gè)體域中的某一確定的元素y是個(gè)體域中的任一確定的元素y是個(gè)體域中的某一確定的元素5.1.3. 謂詞邏輯中的形式演繹推理5.1.3. 謂詞邏輯中的形式演繹推理利用謂詞公式可以將自然語(yǔ)言中的陳述語(yǔ)句表示為一種形式化的符號(hào)表達(dá)式。那么，利用謂詞公式，我們同樣可以將形式邏輯中抽象出來(lái)的推理規(guī)則形式化為一些符號(hào)變換公式。表5.1(P.99-100)和表5.2(P.100)就是形式邏輯中常用的一些邏輯等價(jià)式和邏輯蘊(yùn)含式，即推理規(guī)則的符號(hào)表示形式?？梢钥闯?，利用一階謂詞邏輯的這種形式語(yǔ)言，就可以把關(guān)于自然語(yǔ)言的邏輯推理問(wèn)題, 轉(zhuǎn)化為這種符號(hào)表達(dá)式的推演變換。下面就是幾個(gè)例子。 自然演繹推理：從一組已知為

24、真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過(guò)程稱為自然演繹推理。 (為什么書中要稱為：形式演繹推理？)邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由古希臘學(xué)者亞里士多德創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理、證明等問(wèn)題的學(xué)科就叫做數(shù)理邏輯。也叫做符號(hào)邏輯。數(shù)理邏輯是精確化、數(shù)學(xué)化的形式邏輯。下面就是幾個(gè)例子。例 設(shè)有前提：(1)凡是大學(xué)生都學(xué)過(guò)計(jì)算機(jī)；(2)小王是大學(xué)生。試問(wèn)：小王學(xué)過(guò)計(jì)算機(jī)嗎？解：令S(x): x是大學(xué)生； M(x): x學(xué)過(guò)計(jì)算機(jī)；a: 小王。則上面的兩個(gè)命題可用謂詞公式表示為 ：(1) x(S(x) M(x)(2) S(a)下面我們進(jìn)行形式推理： (1) x(S(x)

25、M(x) 前提(2) S(a) M(a) (1),US(I11)(3) S(a) 前提(4) M(a) (2), (3), I3得結(jié)果: M(a) , 即“小王學(xué)過(guò)計(jì)算機(jī)”。5.1.3. 謂詞邏輯中的形式演繹推理例 證明P(a,b)是xy(P(x,y)W(x,y)和W(a,b)的邏輯結(jié)果。證：說(shuō)明一下，本題也就是要證明： (xy(P(x,y)W(x,y)W(a,b) P(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), I45

26、.1.3. 謂詞邏輯中的形式演繹推理例 證明 x(P(x)Q(x)x(R(x)Q(x) x(R(x)P(x) 證： (P.101) （注意例5.6 的表達(dá)方式？）(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) (4)，US(6) R(y) P(y) (3)，(5)，I6(7)x(R(x)P(x) (6)，UG形式演繹推理的許多困難，推理規(guī)則太多(P.101P.102) 。因此，人們就開發(fā)了一些受限的自然演繹推理技術(shù)；或者另辟蹊徑，發(fā)明了所謂的歸結(jié)演繹推理技術(shù)。5.1.

27、3. 謂詞邏輯中的形式演繹推理5.2.1. 子句集定義1 原子謂詞公式及其否定稱為文字，若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句，由r個(gè)文字組成的子句叫r文字子句，1文字子句叫單元子句，不含任何文字的子句稱為空子句，記為或NIL。 例如下面的析取式都是子句PQ RP(x,y) Q(x) 如何求得一個(gè)謂詞公式G的子句集S？5.2 歸結(jié)演繹推理定義2 對(duì)一個(gè)謂詞公式G，通過(guò)以下步驟所得的子句集合S，稱為G的子句集。(1)消去蘊(yùn)含詞和等值詞n。(2)縮小否定詞的作用范圍，直到其僅作用于原子公式。(3)適當(dāng)改名，使量詞間不含同名指導(dǎo)變?cè)图s束變?cè)?4)消去存在量詞。(5)消去所有全稱量詞。(6)化公式為合

28、取范式。(7)適當(dāng)改名，使子句間無(wú)同名變?cè)?8)消去合取詞，以子句為元素組成一個(gè)集合S。 5.2.1. 子句集定義2 對(duì)一個(gè)謂詞公式G，通過(guò)以下步驟所得的子句集合S，稱為G的子句集。（續(xù)之一）(1)消去蘊(yùn)含詞和等值詞n。利用兩個(gè)邏輯等價(jià)式。a)AB A Bb)AnB (AB)(BA)(2)縮小否定詞的作用范圍, 直到其僅作用于原子公式。使用五個(gè)邏輯等價(jià)式。a) (A) A b) (AB) A Bc) (AB) A Bd) xP(x) xP(x)e) xP(x) xP(x) (2)縮小否定詞的作用范圍。a) A A b) ABc)AB5.2.1. 子句集定義2 對(duì)一個(gè)謂詞公式G，通過(guò)以下步驟所

29、得的子句集合S，稱為G的子句集。（續(xù)之二）5.2.1. 子句集(3)適當(dāng)改名，使量詞間不含同名指導(dǎo)變?cè)图s束變?cè)?。xA(x)xB(x) 改為 xA(x)yB(y)；xA(x)xB(x)xC(x) 改為 xA(x)yB(y)zC(z)。(4)消去存在量詞。消去存在量詞時(shí)，同時(shí)還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況：若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)@樣的函數(shù)稱為Skolem函數(shù)；x(A(x)yB(x, y)，用f(x)（函數(shù)）代y，x(A(x)B(x, f(x),xy(A(x)zB(x, y, z)，用f(x, y)（函數(shù)）代

30、z， xy(A(x)B(x, y, f(x, y),若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱為Skolem常量。xy(A(x, y)B(x)，用a（常量）代x， y(A(a, y)B(a)定義2 對(duì)一個(gè)謂詞公式G，通過(guò)以下步驟所得的子句集合S，稱為G的子句集。（續(xù)之三）(5)消去所有全稱量詞。(6)化公式為合取范式?？墒褂脙蓚€(gè)邏輯等價(jià)式。a) A(BC) (AB)(AC)b) (AB)C (AC)(BC) a) ABC (AB)(AC) b) ABC (AC)(BC)(7)適當(dāng)改名，使子句間無(wú)同名變?cè)?8)消去合取詞，以子句為

31、元素組成一個(gè)集合S。 5.2.1. 子句集定義2 對(duì)一個(gè)謂詞公式G，通過(guò)以下步驟所得的子句集合S，稱為G的子句集。(1)消去蘊(yùn)含詞和等值詞n。(2)縮小否定詞的作用范圍，直到其僅作用于原子公式。(3)適當(dāng)改名，使量詞間不含同名指導(dǎo)變?cè)图s束變?cè)?4)消去存在量詞。(5)消去所有全稱量詞。(6)化公式為合取范式。(7)適當(dāng)改名，使子句間無(wú)同名變?cè)?8)消去合取詞，以子句為元素組成一個(gè)集合S。 5.2.1. 子句集解：(1)消去蘊(yùn)含詞，得x( yP(x,y) y( Q(x,y) R(x,y)(2)縮小否定詞的作用范圍，直到其僅作用于原子公式。得x(yP(x,y) y (Q(x,y) R(x,y

32、)(3)適當(dāng)改名，使量詞間不含同名指導(dǎo)變?cè)图s束變?cè)５脁(yP(x,y) z(Q(x,z) R(x,z)(4)消去存在量詞。用f(x)代替y，用g(x)代替z，得 x(P(x,f(x) (Q(x,g(x) R(x,g(x)例5.7 求下面謂詞公式的子句集。 x(yP(x,y) y(Q(x,y) R(x,y)5.2.1. 子句集解（續(xù)） ：(5)消去所有全稱量詞。得 P(x,f(x) (Q(x,g(x) R(x,g(x)(6)化公式為合取范式。得 (P(x,f(x) Q(x,g(x) (P(x,f(x) R(x,g(x) )(7)適當(dāng)改名，使子句間無(wú)同名變?cè)?。?(P(x,f(x) Q(x,g

33、(x) (P(y,f(y) R(y,g(y) )(8)消去合取詞，以子句為元素組成一個(gè)集合S。得子句集S=P(x,f(x)Q(x,g(x), P(y,f(y)R(y,g(y)例5.7 求下面謂詞公式的子句集。 x(yP(x,y) y(Q(x,y) R(x,y)5.2.1. 子句集解：(1)消去存在量詞。說(shuō)明： (4)消去存在量詞。消去存在量詞時(shí)，同時(shí)還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況：若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的函數(shù)稱為Skolem函數(shù)；若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域

34、中的相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱為Skolem常量。存在量詞x、 u、 w；用a代替x，用f(y,z)代替u，用g(y,z,v)代替w，得 yzv (P(a,y,z) Q(f(y,z),v, g(y,z,v)(2)消去所有全稱量詞。得 P(a,y,z) Q(f(y,z),v, g(y,z,v)(3)適當(dāng)改名，使子句間無(wú)同名變?cè)５肞(a,x,y) Q(f(u,v),w, g(u,v,w)(4)消去合取詞，以子句為元素組成一個(gè)集合S。得子句集S = P(a,x,y) ， Q(f(u,v),w, g(u,v,w)例 求謂詞公式 G= xyzuvw (P(x,y,z) Q(u,v,w) 的子句集。

35、5.2.1. 子句集作業(yè)： (P.125) 第1大題的第(1)至(4)小題。(1) xy(P(x,y) Q(x,y)(2) xy(P(x,y) Q(x,y)(3) xy(P(x,y)Q(x,y) R(x,y)(4) x (P(x) yP(y) R(x,y)P.125 第1大題第（1）小題【參考答案】(1) xy(P(x,y) Q(x,y)解：第一步：消去存在量詞x和y，用a代x，用b代x，得：P(a，b) Q(a，b)第二步：消去合取詞，以子句為元素，組成子句集S，得：S=P(a，b)，Q(a，b)P.125 第1大題第（2）小題【參考答案】(2) xy(P(x,y) Q(x,y)解：第一步：

36、消去蘊(yùn)含詞，得： xy ( P(x,y) Q(x,y)第二步：消去全稱量詞x和y，得 ： P(x，y) Q(x，y)因?yàn)橹挥幸粋€(gè)子句，故子句集S為S= P(x，y) Q(x，y)P.125 第1大題第（3）小題【參考答案】(3) xy(P(x,y)Q(x,y) R(x,y)解：第一步：消去蘊(yùn)含詞，得：xy(P(x,y)Q(x,y)R(x,y)第二步：縮小否定詞 的作用范圍，直到其僅作用于原子公式，得： xy(P(x,y)Q(x,y)R(x,y)第三步：消去存在量詞y，用f(x)代y ，得：x(P(x, f(x)Q(x, f(x)R(x, f(x)第四步：消去全稱量詞x，得 ：P(x, f(x)

37、Q(x, f(x)R(x, f(x)第五步：化公式為合取范式，得 ： (P(x, f(x) R(x, f(x)(Q(x, f(x)R(x, f(x)第六步：適當(dāng)改名，使子句間無(wú)同名變?cè)?，得?P(x, f(x) R(x, f(x)(Q(y, f(y)R(y, f(y)第七步：消去合取詞，以子句為元素，組成子句集S，得：S=P(x, f(x) R(x, f(x)， Q(y, f(y)R(y, f(y)P.125 第1大題第（4）小題【參考答案】(4) x (P(x) yP(y) R(x,y)解：第一步：消去蘊(yùn)含詞，得： x ( P(x) yP(y)R(x,y)第二步：消去存在量詞y，用f(x)代

38、y ，得： x ( P(x) P(f(x)R(x, f(x)第三步：消去全稱量詞x，得： P(x) P(f(x)R(x, f(x)第四步：化公式為合取范式，得： (P(x) P(f(x)( P(x)R(x, f(x)第五步：適當(dāng)改名，使子句間無(wú)同名變?cè)?，得?(P(x) P(f(x)( P(y)R(y, f(y)第六步：消去合取詞，以子句為元素，組成子句集S，得：S=P(x) P(f(x) ， P(y)R(y, f(y)求謂詞公式的子句集，何用?由子句集的求法可以看出，一個(gè)子句集中的各子句間為合取關(guān)系。我們就可通過(guò)一個(gè)謂詞公式的子句集來(lái)判斷謂詞公式的不可滿足性。定理1 謂詞公式G不可滿足當(dāng)且僅

39、當(dāng)其子句集S不可滿足。定理1把證明一個(gè)謂詞公式G的不可滿足性，轉(zhuǎn)化為證明其子句集S的不可滿足性。定義3 子句集S是不可滿足的，當(dāng)且僅當(dāng)其子句集的合取式是不可滿足的。 G=B1B2Bn5.2.1. 子句集歸結(jié)原理的出現(xiàn)，被認(rèn)為是自動(dòng)推理，特別是定理機(jī)器證明領(lǐng)域的重大突破。定義4 設(shè)L為一個(gè)文字，則稱L與L為互補(bǔ)文字。(文字？原子謂詞公式及其否定稱為文字。)(定義1)定義5 設(shè)C1，C2是命題邏輯中的兩個(gè)子句，C1中有文字L1，C2中有文字L2，且L1與L2互補(bǔ)，從Cl，C2中分別刪除L1，L2，再將剩余部分析取起來(lái)，記構(gòu)成的新子句為C12，則稱C12為C1，C2的歸結(jié)式(或消解式)，C1，C2稱

40、為其歸結(jié)式的親本子句，L1，L2稱為消解基。 5.2.2. 命題邏輯中的歸結(jié)原理例 設(shè)于是 Cl = PQR ，C2 = QS ，于是Cl，C2的歸結(jié)式為： PR S 例5.9 設(shè)于是 Cl = PQR ，C2 = Q，于是Cl，C2的歸結(jié)式為： PR例5.9 設(shè)于是 Cl = PQ，C2 = Q，于是Cl，C2的歸結(jié)式為： P例5.9 設(shè)于是 Cl = PQR ，C2 = QR ，于是Cl，C2的歸結(jié)式為： PRR 或?yàn)椋?PQQ5.2.2. 命題邏輯中的歸結(jié)原理 定理2 歸結(jié)式是其親本子句的邏輯結(jié)果。 C1C2 C12證明：設(shè)L1=L，L2= L，則C1=C1 L ，C2= LC2，其中C

41、1和C2都是文字析取式，于是C1，C2的歸結(jié)式為： C1 C2 。C1 = C1 L = C1 L (根據(jù)E14)C2 = LC2 = L C2 (根據(jù)E14) C1C2 = ( C1L)(LC2) C1C2 根據(jù)I6(假言三段論)= C1C2 (根據(jù)E14) C1C2 C1C2 結(jié)論，歸結(jié)式是其親本子句的邏輯結(jié)果。證畢。5.2.2. 命題邏輯中的歸結(jié)原理由定理2即得推理規(guī)則：C1C2 (C1-L1)U(C2-L2)其中，Cl，C2是兩個(gè)子句，L1，L2分別是Cl，C2中的文字，且L1，L2互補(bǔ)。上式右端的寫法是把子句看作是文字的集合，此規(guī)則稱為命題邏輯中的歸結(jié)原理。 (歸結(jié)式是其親本子句的邏

42、輯結(jié)果。)例 用歸結(jié)原理驗(yàn)證：分離規(guī)則(I3)A(A B) B 和拒取式(I4)(A B)B A 。解：A(A B) A(AB) B(A B)B (AB) B A由歸結(jié)原理可知，如果兩個(gè)互否的單元子句進(jìn)行歸結(jié)，則歸結(jié)式為空子句，即LL (L和L的歸結(jié)式為) 。而另一方面，我們知道，LL = F（假）。所以，空子句就是恒假子句，即 F。5.2.2. 命題邏輯中的歸結(jié)原理歸結(jié)原理顯然是一個(gè)很好的推理規(guī)則。但我們一般不使用它直接從前提推導(dǎo)結(jié)論，而是通過(guò)推導(dǎo)空子句來(lái)作間接證明。具體來(lái)講，就是先求出要證的命題公式（謂詞公式也一樣）的否定式的子句集S，然后對(duì)子句集S（一次或多次）使用消解原理，若在某一步推

43、出了空子句，即推出了矛盾，則說(shuō)明子句集S是不可滿足的，從而原否定式也是不可滿足的，進(jìn)而說(shuō)明原公式是永真的。5.2.2. 命題邏輯中的歸結(jié)原理為什么說(shuō)，一旦推出了空子句，就說(shuō)明子句集S是不可滿足的呢？這是因?yàn)榭兆泳渚褪荈，推出了空子句就是推出了F。 但(因?yàn)?消解原理是推理規(guī)則，即正確的推理形式，那么由正確的推理形式推出了F，則說(shuō)明前提不真(前提是指F的前提)，即消解出空子句的兩個(gè)親本子句中至少有一個(gè)為假。那么(如果)這兩個(gè)親本子句(如果)都是原子句集S中的子句，即說(shuō)明原子句集S不可滿足(因?yàn)樽泳浼懈髯泳溟g為合取關(guān)系)。如果這兩個(gè)親本子句不是或不全是S中的子句，那么，它們必定是某次歸結(jié)的結(jié)果，

44、于是，用同樣的道理再向上追溯，這樣一定會(huì)推出原子句集S中至少有一個(gè)子句為假，從而說(shuō)明S不可滿足。實(shí)際上，上述分析也可作為定理2的推論。 5.2.2. 命題邏輯中的歸結(jié)原理證： (1) P Q (2) P S子句集 (3) Q（1）若用C12代替C1，C2得到新子句集S1，則由S1的不可滿足可推出原子句集S的不可滿足。即：S1不可滿足 S不可滿足（2）若把C12加入到S中，得到新子句集S2，則S2與原S的(是)同不可滿足。即：S2不可滿足 S不可滿足例5.11 證明子句集P Q， P，Q是不可滿足 (4) Q 由(1),(2) (5) 由(3),(4)所以，S是不可滿足。推論：設(shè)C1, C2是子

45、句集S的兩個(gè)子句, C12是它們的歸結(jié)式, 則5.2.2. 命題邏輯中的歸結(jié)原理例 用歸結(jié)原理證明R是P，(PQ)R，(SU)Q，U的邏輯結(jié)果。證： 對(duì)于這個(gè)問(wèn)題，可以先寫出謂詞公式：P(PQ)R)(SU) Q)U R，再求其否定式的子句集S；也可以先分別求前提中諸條件公式的子句，再求結(jié)論公式否定的子句，然后將這些子句合在一起，即得所求的子句集S。因?yàn)?(AB)=AB。我們采用后一種方法，（請(qǐng)同學(xué)們認(rèn)真思考證明過(guò)程，而不是看過(guò)場(chǎng)）有幾個(gè)前提？結(jié)論是什么？5.2.2. 命題邏輯中的歸結(jié)原理PQPQRRQPUQUU圖5-1 例5.12歸結(jié)演繹樹例 用歸結(jié)原理證明R是P，(PQ)R，(SU)Q，U的

46、邏輯結(jié)果。P(PQR)( S R)( UR)UR不可滿足，從而R是題設(shè)前提的邏輯結(jié)果。5.2.2. 命題邏輯中的歸結(jié)原理我們采用后一種方法，得子句集S = P，PQR，SR， UR，U，R，【該子句集S是怎么來(lái)的？】然后對(duì)該子句集施行歸結(jié)，歸結(jié)過(guò)程用下面的歸結(jié)演繹樹表示（見圖5-1）。由于最后推出了空子句，所以子句集S不可滿足，即命題公式：例5.12 用歸結(jié)原理證明R是P，(PQ)R，(SU)Q, U的邏輯結(jié)果。證 : 一、先對(duì)前提與結(jié)論否定式合取，得命題公式H，H= P(PQ)R)(SU)Q)U R二、將公式H化為子句集，其中a) (PQ)R= P Q R F2b) (SU)Q = (SU)

47、 R= S UR= (S R )( UR) F3從而得公式H的子句集S：S=P, PQR, S R, UR, U, R5.2.2. 命題邏輯中的歸結(jié)原理(7) PQ 由(2),(6) (8) Q 由(1),(7) (9) U 由(4),(8) (10) (NIL) 由(5),(9) 由此得出子句集S是不可滿足的，因而公式H也是不可滿足的，從而命題得證。 例（續(xù)）三、使用歸結(jié)原理，對(duì)子句集S進(jìn)行歸結(jié)(1) P F1(2) PQR F2 (3) SQ (4) UQ (5) U F4(6) R (G) F3SPQPQRRQPUQUU然后對(duì)該子句集施行歸結(jié)，歸結(jié)過(guò)程用下面的歸結(jié)演繹樹表示（見圖5-1）

48、。5.2.2. 命題邏輯中的歸結(jié)原理(2)(6)(7)(1)(8)(4)(9)(5)(10)定理（反證法定理）：G為F1，F(xiàn)2，F(xiàn)n的邏輯結(jié)果(結(jié)論) ，當(dāng)且僅當(dāng)F1F2FnG是不可滿足的。5.2.2. 命題邏輯中的歸結(jié)原理解釋如下：要證明G為F1，F(xiàn)2，F(xiàn)n的邏輯結(jié)果，只要證明 (F1F2Fn) G 為永真，及證明 ( (F1F2Fn) G )為永假。也就是證明下式： ( (F1F2Fn)G ) 為永假(不可滿足)。上式變成：F1F2FnG。只要能證明上式永假（不可滿足），就可得到證明。也就是說(shuō)，用歸結(jié)原理，可推出子句，也就可證明上式是不可滿足的。證 : 用反證法，即證明F1F2FnG是不可

49、滿足。其中：F1=P；F2=(PQ)R；F3=(SU)Q；F4=U；G=R。首先求得子句集S(1) P F1(2) PQR F2(5) U F4 (6) R (G)使用歸結(jié)原理，對(duì)子句集S進(jìn)行歸結(jié) (7) PQ 由(2),(6) (8) Q 由(1),(7) (9) U 由(4),(8) (10) (NIL) 由(5),(9) 由于子句集S是不可滿足的，從而得R是P，(PQ)R，(SU)Q，U的邏輯結(jié)果。 證畢。(3) SQ (4) UQ F3S（另一種證法）例 用歸結(jié)原理證明R是P，(PQ)R，(SU)Q，U的邏輯結(jié)果。5.2.2. 命題邏輯中的歸結(jié)原理(1) P F1(2) PQR F2(

50、5) U F4 (6) R (G)方式二：(7) PQ 由(2),(6) (8) Q 由(1),(7) (9) Q 由(4),(5) (10) 由(8),(9) (3) SQ (4) UQ F3S方式一：(7) PQ 由(2),(6) (8) Q 由(1),(7) (9) U 由(4),(8) (10) (NIL) 由(5),(9) 方式三:(7) QR 由(1),(2) (8) Q 由(4),(5) (9) R 由(7),(8) (10) 由(5),(9) 看一看例 有幾種歸結(jié)方式。5.2.2. 命題邏輯中的歸結(jié)原理作業(yè)：P. 125 第1大題第(5)至(6)小題P. 125 第4大題第(2

51、) 小題P.125 第1大題第（5）小題【參考答案】(5) x(P(x) y(P(y) R(x,y)解：第一步：消去蘊(yùn)含詞，得： x(P(x) y(P(y) R(x,y)第二步：消去存在量詞x，用a代x ，得： (P(a) y(P(y) R(a,y)第三步：消去全稱量詞y，得： (P(a) (P(y) R(a,y)第四步：消去合取詞，以子句為元素，組成子句集S，得：S=P(a) ， P(y) R(a,y)P.125 第1大題第（6）小題【參考答案】(6) xyzuvw(P(x,y,z,u,v,w) (Q(x,y,z,u,v,w) R(x,z,w)解：第一步：消去存在量詞x、y、u和w，用a代x

52、 , 用b代y , 用f(z)代u , 用g(z,v)代w ，得： zv(P(a, b, z, f(z), v, g(z,v)(Q(a, b, z, f(z), v, g(z,v) R(a, z, g(z,v)第二步：消去全稱量詞z和v，得： (P(a, b, z, f(z), v, g(z,v)(Q(a, b, z, f(z), v, g(z,v) R(a, z, g(z,v)第三步：適當(dāng)改名，使子句間無(wú)同名變?cè)茫?(P(a, b, x, f(x), v, g(x,y)(Q(a, b, u, f(u),v, g(u,v) R(a, u, g(u,v)第四步：消去合取詞，以子句為元素，組成

53、子句集S，得： S=P(a, b, x, f(x), v, g(x,y) ，Q(a, b, u, f(u), v, g(u,v) R(a, u, g(u,v)(2) F: (PQ) (PR) (QS) G: RS證 : 用反證法，即證明FG是不可滿足。首先求得子句集SF： (PQ) (PR) (QS)第一步：消去蘊(yùn)含詞，得： (PQ) (PR) (QS)第二步：消去合取詞，以子句為元素，組成子句集S1，得： S1= PQ， PR ， QS G ： (RS)第一步：縮小否定詞 的作用范圍，直到其僅作用于原子公式，得： R S 第二步：消去合取詞，以子句為元素，組成子句集S2，得： S2=R， S

54、 P.125 第4大題第(2)小題【參考答案】(2) F: (PQ) (PR) (QS) G: RS證 : 用反證法，即證明FG是不可滿足。首先求得子句集S使用歸結(jié)原理，對(duì)子句集S進(jìn)行歸結(jié) (7) P 由(2),(4)(8) Q 由(3),(5)(9) P 由(1),(8) (10) 由(7),(9)以上證得S是不可滿足的。由于子句集S是不可滿足的，從而得G是F的邏輯結(jié)果。證畢。F(G)S(1) PQ (2) PR (3) QS(4) R(5) S P.125 第4大題第(2)小題【參考答案】在一階謂詞邏輯中應(yīng)用消解原理，不像命題邏輯中那樣簡(jiǎn)單，因?yàn)橹^詞邏輯中的子句含有個(gè)體變?cè)?這就使得尋找

55、含互否文字的子句對(duì)的操作變得復(fù)雜。例如：C1=P(x)Q(x)C2= P(a)R(y)直接比較，兩者中不含互否文字，但是如果用a替換C1中的x，則得到，C1=P(a)Q(a)C2= P(a)R(y)于是根據(jù)命題邏輯中的消解原理，得C1和C2的消解式C3= Q(a) R(y)所以，要在謂詞邏輯中應(yīng)用消解原理，則一般需要對(duì)個(gè)體變?cè)鬟m當(dāng)?shù)奶鎿Q。5.2.3. 替換與合一替換：指對(duì)同名的謂詞中的個(gè)體變?cè)鬟m當(dāng)?shù)奶鎿Q，使互否的文字的形式結(jié)構(gòu)完全一致起來(lái)，進(jìn)而達(dá)到消解的目的。定義6 一個(gè)替換(Substitution)是形如t1/x1，t2/x2， ，tn/xn的有限集合，其中t1，t2，tn是項(xiàng)，稱為替

56、換的分子；x1，x2，xn是互不相同的個(gè)體變?cè)Q為替換的分母；ti不同于xi， xi也不循環(huán)地出現(xiàn)在tj(j1，2，n)中；ti/xi表示用ti替換xi。若t1，t2，tn都是不含變?cè)捻?xiàng)(稱為基項(xiàng))時(shí)，該替換稱為基替換；沒有元素的替換稱為空替換，記作e，它表示不作替換。5.2.3. 替換與合一5.2.3. 替換與合一對(duì)P(x1, x2, , xn)施行替換 t1/x1, t2/x2, , tn/xn，得P(t1, t2, , tn)。例如：a/x，g(y)/y，f(g(b)/z是一個(gè)替換，舉例：對(duì)P(x，y，z)施行替換a/x，g(y)/y，f(g(b)/z，得P(a, g(y), f(g

57、(b)。而g(y)/x, f(x)/y則不是一個(gè)替換，因?yàn)閤與y出現(xiàn)循環(huán)替換。舉例：Q(x, y)施行替換g(y)/x, f(x)/y，得Q(g(y), f(x)5.2.3. 替換與合一我們將項(xiàng)、原子公式、文字、子句等統(tǒng)稱為表達(dá)式，沒有變?cè)谋磉_(dá)式稱為基表達(dá)式，出現(xiàn)在表達(dá)式E中的表達(dá)式稱為E的子表達(dá)式。定義7 設(shè)q=t1/x1, t2/x2, , tn/xn是一個(gè)替換，E是一個(gè)表達(dá)式，即把對(duì)E施行替換，即把E中出現(xiàn)的個(gè)體變?cè)獂j (1jn)都用tj替換，記為Eq，所得的結(jié)果稱為E在q下的例(instance)。例如：若q=a/x, f(b)/y, c/z是一個(gè)替換，表達(dá)式為：G=P(x, y,

58、 z)，則G在q下的例記為：Gq=P(a, f(b), c)。5.2.3. 替換與合一兩個(gè)或兩個(gè)以上替換的復(fù)合組成一個(gè)替換。定義8 設(shè)q=t1/x1, t2/x2, , tn/xn, l=u1/y1, , um/ym是兩個(gè)替換，則將集合t1l/x1, , tnl/xn, u1/y1, , um/ym中凡符合下列條件的元素刪除：（1）til/xi 當(dāng)til=xi（2）ui/yi 當(dāng)yix1, , xn如此得到的集合仍然是一個(gè)替換，該替換稱為q與l的復(fù)合或乘積，記為ql 。例 設(shè)：q=f(y)/x, z/y，l=a/x, b/y, y/z, 于是，t1l/x1，t2l/x2，u1/y1，u2/y2

59、， u3/y3=f(b)/x，y/y，a/x，b/y，y/z，從而 ql=f(b)/x, y/z?？梢宰C明，替換的乘積滿足結(jié)合律，即 (ql)m= q(lm)。定義9 設(shè)S=F1, F2, ,Fn是一個(gè)原子謂詞公式集，若存在一個(gè)替換q，可使F1q = F2q =Fnq ，則稱q為S的一個(gè)合一(Unifier)，稱S為可合一的。一個(gè)公式的合一一般不(是)維一(的)。定義10 設(shè)s是原子公式集S的一個(gè)合一，如果對(duì)S的任何一個(gè)合一q，都存在一個(gè)替換l，使得 q=sl則稱s為S的最一般合一(Most General Unifier)，簡(jiǎn)稱MGU?？梢钥闯?，如果能找到一個(gè)公式集的合一，特別是最一般合一，

60、則可使互否的文字的形式結(jié)構(gòu)完全一致起來(lái)，進(jìn)而達(dá)到消解的目的。如何求一個(gè)公式集的最一般合一？有一個(gè)算法，可以求任何可合一公式集的最一般合一。為了介紹這個(gè)算法，我們先引入差異集的概念。S = P(a,b) P(a,b) P(a,b) = P(a,b) S = P(a,b) P(a,b) P(a,b) = P(a,b) 5.2.3. 替換與合一差異集定義11 設(shè)S是一個(gè)非空的具有相同謂詞名的原子公式集，從S中各公式的左邊第一個(gè)項(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