《人工智能》第三章知識(shí)演繹

《人工智能》第三章知識(shí)演繹第一頁(yè)，共55頁(yè)。2①

規(guī)則演繹系統(tǒng)②謂詞演繹的歸結(jié)方法③歸結(jié)反駁搜索策略④Hone子句的歸結(jié)

“知識(shí)演繹”核心內(nèi)容第二頁(yè)，共55頁(yè)。3規(guī)則演繹系統(tǒng)在基于規(guī)則系統(tǒng)中，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配；then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種系統(tǒng)叫做基于規(guī)則的演繹系統(tǒng)(rulebaseddeductionsystem)。在這種系統(tǒng)中，通常稱(chēng)規(guī)則的if部分為前項(xiàng)(antecedent)，稱(chēng)規(guī)則的then部分為后項(xiàng)(consequent)。第三頁(yè)，共55頁(yè)。4規(guī)則演繹系統(tǒng)基于規(guī)則的求解系統(tǒng)由if-then形式的規(guī)則建立的。例如：if(antecedent)then(consequent)

基于規(guī)則的系統(tǒng)稱(chēng)為規(guī)則演繹系統(tǒng)，若后件用于規(guī)定動(dòng)作，則稱(chēng)為產(chǎn)生式系統(tǒng)。規(guī)則演繹系統(tǒng)可以分為如下的3種：規(guī)則正向演繹系統(tǒng)、規(guī)則逆向演繹系統(tǒng)、規(guī)則雙向演繹系統(tǒng)。

前件

后件第四頁(yè)，共55頁(yè)。5

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)從if部分向then部分推理的過(guò)程稱(chēng)為正向推理，即從事實(shí)或狀態(tài)向目標(biāo)或行動(dòng)進(jìn)行操作。 規(guī)則正向演繹系統(tǒng)的步驟：事實(shí)表達(dá)命題式的與或形變換利用(W1→W2)和(W1∨W2)的等價(jià)關(guān)系，消去符號(hào)→(如果存在該符號(hào)的話)。實(shí)際上，在事實(shí)中間很少有符號(hào)→出現(xiàn)，因?yàn)榭砂烟N(yùn)涵式表示為規(guī)則。用狄·摩根(DeMorgan)定律把否定符號(hào)移進(jìn)括號(hào)內(nèi)，直到每個(gè)否定符號(hào)的轄域最多只含有一個(gè)謂詞為止。

第五頁(yè)，共55頁(yè)。6

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)從if部分向then部分推理的過(guò)程稱(chēng)為正向推理，即從事實(shí)或狀態(tài)向目標(biāo)或行動(dòng)進(jìn)行操作。 規(guī)則正向演繹系統(tǒng)的步驟：xyP(x,y)事實(shí)表達(dá)命題式的與或形變換xP(x,f(x))yxP(x,y)xP(x,a)~xP(x)x~P(x)對(duì)所得到的表達(dá)式進(jìn)行Skolem化和前束化。對(duì)全稱(chēng)量詞轄域內(nèi)的變量進(jìn)行改名和變量標(biāo)準(zhǔn)化，而存在量詞量化變量用Skolem函數(shù)代替。刪去全稱(chēng)量詞，而任何余下的變量都被認(rèn)為具有全稱(chēng)量化作用。第六頁(yè)，共55頁(yè)。7

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)從if部分向then部分推理的過(guò)程稱(chēng)為正向推理，即從事實(shí)或狀態(tài)向目標(biāo)或行動(dòng)進(jìn)行操作。 規(guī)則正向演繹系統(tǒng)的步驟：例1：我們有事實(shí)表達(dá)式(u)(v){Q(v，u)∧[(R(v)∨P(v))∧S(u，v)]}把它化為：Q(v,A)∧{[R(v)∧P(v)]∨S(A,v)}對(duì)變量更名標(biāo)準(zhǔn)化，使得同一變量不出現(xiàn)在事實(shí)表達(dá)式的不同主要合取式中。更名后得表達(dá)式：Q(w,A)∧{[R(v)∧P(v)]∨S(A,v)}必須注意到Q(v，A)中的變量v可用新變量w代替，而合取式[R(v)∧P(v)]中的變量v卻不可更名，因?yàn)楹笳咭渤霈F(xiàn)在析取式

S(A,v)中。第七頁(yè)，共55頁(yè)。8

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)從if部分向then部分推理的過(guò)程稱(chēng)為正向推理，即從事實(shí)或狀態(tài)向目標(biāo)或行動(dòng)進(jìn)行操作。 規(guī)則正向演繹系統(tǒng)的步驟：例2：我們有事實(shí)表達(dá)式(v)(u){Q(v，u)∧[(R(v)∨P(v))∧S(u，v)]}注意，這時(shí)變量u成為了變量v的函數(shù)f(v)，利用Skolem函數(shù)把這個(gè)表達(dá)式化為：Q(v,f(v))∧{[R(v)∧P(v)]∨S(f(v),v)}第八頁(yè)，共55頁(yè)。9

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 規(guī)則正向演繹系統(tǒng)的步驟：事實(shí)表達(dá)命題式的與或形變換R(V)P(V)

R(V)∧P(V)S(A,V)[R(V)∧

P(V)]∨S(A,V)Q(W,A)Q(W,A)∧{[R(V)∧P(V)]∨S(A,V)}

每個(gè)節(jié)點(diǎn)表示該事實(shí)表達(dá)式的一個(gè)子表達(dá)式。某個(gè)事實(shí)表達(dá)式(E1∧…∧En)的每個(gè)合取子表達(dá)式E1，…，En是用后繼節(jié)點(diǎn)表示的，并由一個(gè)k線連接符把它們連接到父輩節(jié)點(diǎn)上。某個(gè)事實(shí)表達(dá)式(E1∨…∨Ek)的析取關(guān)系子表達(dá)式E1，…，Ek是由單一的后繼節(jié)點(diǎn)表示的，并由一個(gè)單線連接符接到父輩結(jié)點(diǎn)。第九頁(yè)，共55頁(yè)。10

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 與或圖的正向推理：限制規(guī)則的公式類(lèi)型為：LW

其中：L為單文字；W為與或形的唯一公式。例如：考慮規(guī)則S(x∧y)∨z應(yīng)用到右面的事實(shí)表達(dá)式中。TS(T∨U)[S∧(T∨U)][(P∨Q)∧R]∨[S∧(T∨U)](P∨Q)RPQU[(P∨Q)∧R]表示某個(gè)事實(shí)表達(dá)式的與或圖的葉節(jié)點(diǎn)均由表達(dá)式中的文字來(lái)標(biāo)記。圖中標(biāo)記有整個(gè)事實(shí)表達(dá)式的節(jié)點(diǎn)，稱(chēng)為根節(jié)點(diǎn)，它在圖中沒(méi)有祖先。XYSX∧YZ當(dāng)目標(biāo)公式按正向規(guī)則應(yīng)用到事實(shí)表達(dá)式與或圖，產(chǎn)生的與或圖包含有終止在目標(biāo)節(jié)點(diǎn)的一個(gè)解圖時(shí)，證明目標(biāo)公式成立。第十頁(yè)，共55頁(yè)。11

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 與或圖的正向推理：公式的與或圖表示有個(gè)有趣的性質(zhì)，即由變換該公式得到的子句集可作為此與或圖的解圖的集合(終止于葉節(jié)點(diǎn))讀出；也就是說(shuō)，所得到的每個(gè)子句是作為解圖的各個(gè)葉節(jié)點(diǎn)上文字的析取。這樣，由表達(dá)式Q(w,A)∧{[R(v)∧P(v)]∨S(A,v)}得到的子句為：Q(w,A),S(A,v)∨R(v),S(A,v)∨P(v)我們一般把事實(shí)表達(dá)式的與或圖表示倒過(guò)來(lái)畫(huà)，即把根節(jié)點(diǎn)畫(huà)在最下面，而把其后繼節(jié)點(diǎn)往上畫(huà)。我們將要討論到目標(biāo)公式的與或圖表示，它是按通常方式畫(huà)出的，即目標(biāo)在上面。

第十一頁(yè)，共55頁(yè)。12

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 推理規(guī)則：消解(歸結(jié))把原子公式和原子公式的否定稱(chēng)為文字。任何文字的析取式稱(chēng)為子句。析取式P?Q??R可用子句表示為：{P，Q，?R}。不包含任何文字的子句稱(chēng)為空子句（NIL）?？兆泳涫怯兰俚?。由子句構(gòu)成的集合稱(chēng)為子句集。歸結(jié)定義為：從{}1和{

}2(1和2是文字集合，是一個(gè)文字)，可以歸結(jié)為12，它被稱(chēng)為兩個(gè)子句的歸結(jié)式。是被歸結(jié)的文字。這個(gè)過(guò)程稱(chēng)為歸結(jié)。第十二頁(yè)，共55頁(yè)。13

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 推理規(guī)則：消解(歸結(jié))歸結(jié)定義為：從{}1和{

}2(1和2是文字集合，是一個(gè)文字)，可以歸結(jié)為12，它被稱(chēng)為兩個(gè)子句的歸結(jié)式。是被歸結(jié)的文字。這個(gè)過(guò)程稱(chēng)為歸結(jié)。例：1、P?R和Q??R歸結(jié)R為P?Q。注意到P?R與Q??R的等價(jià)寫(xiě)法為?P?R、R?Q，利用蘊(yùn)涵“?”的傳遞性，則有?P?Q，而它的等價(jià)表示為P?Q。于是，可以看出，通過(guò)鏈?zhǔn)降耐评硪?guī)則產(chǎn)生的結(jié)果與歸結(jié)是一致的。2、

R和Q??R歸結(jié)R為Q。而Q??R等價(jià)于R?Q，這樣，此歸結(jié)與假言推理是一致的。第十三頁(yè)，共55頁(yè)。14

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 推理規(guī)則：消解(歸結(jié))歸結(jié)是合理的。證明：所謂合理的，就是說(shuō)，如果{}1和{

}2均是真的，那么12是真的。對(duì)的真假值討論就可以了。情形一：是真的，那么，

是假的，因此，{

}2為真，必須2為真，故12是真的。情形二：是假的，那么，{}1為真，必須1為真，故12是真的。綜合情形一和二，可知，1、2至少有一個(gè)必須為真，即12是真的。第十四頁(yè)，共55頁(yè)。15

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 與或圖的正向推理：應(yīng)用消解原理的結(jié)果:規(guī)則S→(X∧Y)∨Z化為子句：

S∨X∨Z；S∨Y∨Z；事實(shí)表達(dá)式[(P∨Q)∧R]∨[S∧(T∨U)]化為 子句：P∨Q∨S；R∨S；P∨Q∨T∨U；R∨T∨U歸結(jié)結(jié)果：X∨Z∨P∨Q；Y∨Z∨P∨Q； R∨X∨Z；R∨Y∨Z第十五頁(yè)，共55頁(yè)。16

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng) 與或圖的正向推理：應(yīng)用一條規(guī)則得到的與或圖繼續(xù)表示事實(shí)表達(dá)式和推得的表達(dá)式，這可利用匹配弧兩側(cè)有相同標(biāo)記的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)。對(duì)一個(gè)節(jié)點(diǎn)應(yīng)用一條規(guī)則之后，此節(jié)點(diǎn)就不再是該圖的葉節(jié)點(diǎn)。不過(guò)，它仍然由單一文字標(biāo)記而且可以繼續(xù)具有一些應(yīng)用于它的規(guī)則。我們把圖中標(biāo)有單文字的任一節(jié)點(diǎn)都稱(chēng)為文字節(jié)點(diǎn)，由一個(gè)與或圖表示的子句集就是對(duì)應(yīng)于該圖中以文字節(jié)點(diǎn)終止的解圖集。

第十六頁(yè)，共55頁(yè)。17

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)

作為終止條件的目標(biāo)公式

應(yīng)用規(guī)則推理的目的在于從某個(gè)事實(shí)公式和某個(gè)規(guī)則集出發(fā)來(lái)證明某個(gè)目標(biāo)公式。在正向推理系統(tǒng)中，這種目標(biāo)表達(dá)式只限于可證明的表達(dá)式，尤其是可證明的文字析取形的目標(biāo)公式表達(dá)式。我們用文字集表示此目標(biāo)公式，并設(shè)該集各元都為析取形式。目標(biāo)文字和規(guī)則可用來(lái)對(duì)與或圖添加后繼節(jié)點(diǎn)，當(dāng)一個(gè)目標(biāo)文字與該圖中文字節(jié)點(diǎn)n上的一個(gè)文字相匹配時(shí)，我們就對(duì)該圖添加這個(gè)節(jié)點(diǎn)n的新后裔，并標(biāo)記為匹配的目標(biāo)文字。這個(gè)后裔叫做目標(biāo)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)都用匹配弧分別接到它們的父輩節(jié)點(diǎn)上。第十七頁(yè)，共55頁(yè)。18

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)

作為終止條件的目標(biāo)公式例3：事實(shí)P∨Q；規(guī)則P→C，Q→G；目標(biāo)C∨G。把規(guī)則化為子句形，得子句集：P∨

C，Q

∨G

目標(biāo)的否定為:(C∨G)；其子句形為:C，GP∨

CP∨

QQ∨

CCQ

Q∨

G

G

Q

NIL第十八頁(yè)，共55頁(yè)。19

規(guī)則演繹系統(tǒng)(1)規(guī)則正向演繹系統(tǒng)

作為終止條件的目標(biāo)公式例3：事實(shí)P∨Q；規(guī)則P→C，Q→G；目標(biāo)C∨G。PQPR(P∨Q)[(P∨O)∧R][S∧(T∨U)]∨[(P∨Q)∧R](T∨U)STUQ[(T∨U)∧S]CDEGCG當(dāng)目標(biāo)公式按正向規(guī)則應(yīng)用到事實(shí)表達(dá)式與或圖，產(chǎn)生的與或圖包含有終止在目標(biāo)節(jié)點(diǎn)的一個(gè)解圖時(shí)，證明目標(biāo)公式成立。第十九頁(yè)，共55頁(yè)。20

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)基于規(guī)則的逆向演繹系統(tǒng)，其操作過(guò)程與正向演繹系統(tǒng)相反，即為從目標(biāo)到事實(shí)的操作過(guò)程，從then到if的推理過(guò)程。

目標(biāo)表達(dá)式的與或形式

采用與變換事實(shí)表達(dá)式同樣的過(guò)程，把目標(biāo)公式化成與或形，即消去蘊(yùn)涵符號(hào)，把否定符號(hào)移進(jìn)括號(hào)內(nèi)，對(duì)全稱(chēng)量詞Skolem化并刪去存在量詞。留在目標(biāo)表達(dá)式與或形中的變量假定都已存在量詞量化。例1：目標(biāo)表達(dá)式：(

y)(x){P(x)→[Ｑ(x,y)∧[P(x)∧S(y)]]}

被化成與或形：

P(f(y))∨{Q(f(y),y)∧[P(f(y))∨S(y)]}

式中，x=f(y)為一Skolem函數(shù)。第二十頁(yè)，共55頁(yè)。21

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)目標(biāo)表達(dá)式的與或形式

與或形的目標(biāo)公式也可以表示為與或圖。不過(guò)，與事實(shí)表達(dá)式的與或圖不同的是，對(duì)于目標(biāo)表達(dá)式，與或圖中的k線連接符用來(lái)分開(kāi)合取關(guān)系的子表達(dá)式。在目標(biāo)公式的與或圖中，我們把根節(jié)點(diǎn)的任一后裔叫做子目標(biāo)節(jié)點(diǎn)，而標(biāo)在這些后裔節(jié)點(diǎn)中的表達(dá)式叫做子目標(biāo)。例1：目標(biāo)表達(dá)式：

P(f(y))∨{Q(f(y),y)∧[P(f(y))∨S(y)]}P(f(y))∨{Q(f(y),y)∧[P(f(y))∨S(y)]}Q(f(y),y)

∧[P(f(y))∨S(y)]P(f(y))Q(f(y),y)S(y)P(f(y))P(f(y))∨S(y)第二十一頁(yè)，共55頁(yè)。22

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)與或圖的逆向推理規(guī)則變換

我們應(yīng)用逆向推理規(guī)則來(lái)變換逆向演繹系統(tǒng)的與或圖結(jié)構(gòu)，逆向推理規(guī)則是建立在確定的蘊(yùn)涵式基礎(chǔ)上的，現(xiàn)在把這些逆向推理規(guī)則限制為:

W→L其中：W為任一與或形公式，L為單文字。逆向系統(tǒng)中的事實(shí)表達(dá)式均限制為文字合取形，它可以表示為一個(gè)文字集。當(dāng)一個(gè)事實(shí)文字和標(biāo)在該圖文字節(jié)點(diǎn)上的文字相匹配時(shí)，就可把相應(yīng)的后裔事實(shí)節(jié)點(diǎn)添加到該與或圖中去。這個(gè)事實(shí)節(jié)點(diǎn)通過(guò)標(biāo)有mgu的匹配弧與匹配的子目標(biāo)文字節(jié)點(diǎn)連接起來(lái)。同一個(gè)事實(shí)文字可以多次重復(fù)使用(每次用不同變量)，以便建立多重事實(shí)節(jié)點(diǎn)。第二十二頁(yè)，共55頁(yè)。23

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)與或圖的逆向推理規(guī)則變換

事實(shí):

F1:DOG(FIDO);狗的名字叫Fido

F2:BARKS(FIDO);Fido是不叫的F3:WAGS-TAIL(FIDO);Fido搖尾巴

F4:MEOWS(MYRTLE);貓咪的名字叫Myrtle

規(guī)則:

R1:[WAGS-TAIL(x1)∧DOG(x1)]→FRIENDLY(x1)

搖尾巴的狗是溫順的狗第二十三頁(yè)，共55頁(yè)。24

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)與或圖的逆向推理規(guī)則變換

規(guī)則:

R2:FRIENDLY(x2)∧BARKS(x2)→AFRAID(y2,x2)

溫順而又不叫的東西是不值得害怕的R3:DOG(x3)→ANIMAL(x3)狗為動(dòng)物

R4:CAT(x4)→ANIMAL(x4)

貓為動(dòng)物R5:MEOWS(x5)→CAT(x5)貓咪是貓目標(biāo):(x)(

y)[CAT(x)∧DOG(y)∧

AFRAID(x,y)]是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?第二十四頁(yè)，共55頁(yè)。25

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)與或圖的逆向推理規(guī)則變換

CAT(x)∧DOG(y)∧AFRAID(x,y)CAT(x)DOG(y)AFRAID(x,y)CAT(x5)AFRAID(x2,y2)MEOWS(x)FRIENDLY(y)WAGS-TAIL(y)DOG(x1)FRIENDLY(x1)BARKS(y)DOG(FIDO)MEOWS(MYRTLE)BARKS(FIDO)WAGS-TAIL(FIDO)DOG(FIDO)R1R2R5x5/xMYRTLE/xFIDO/yFIDO/yx2/x，y2/yFIDO/yFIDO/yy/x1第二十五頁(yè)，共55頁(yè)。26

規(guī)則演繹系統(tǒng)(2)規(guī)則逆向演繹系統(tǒng)與或圖的逆向推理規(guī)則變換

正向演繹系統(tǒng)能夠處理任意形式的if表達(dá)式，但被限制在then表達(dá)式為由文字析取組成的一些表達(dá)式。逆向演繹系統(tǒng)能夠處理任意形式的then表達(dá)式，但被限制在if表達(dá)式為文字合取組成的一些表達(dá)式。

[CAT(MYRTLE)∧DOG(FIDO)∧AFRAID(MYRTLE,FIDO)]第二十六頁(yè)，共55頁(yè)。27

謂詞演繹的歸結(jié)方法謂詞、函數(shù)、量詞謂詞：表示個(gè)體對(duì)象之間的關(guān)系、屬性或狀態(tài)。其表示形式如下：

P(x1,x2,x3,...xn)

其中：P是謂詞符號(hào)，表示x1,x2,x3,...xn個(gè)體對(duì)象之間的屬性、狀態(tài)或關(guān)系。x1,x2,x3,...xn是謂詞的參量（或稱(chēng)項(xiàng)），一般表示個(gè)體，它可以是個(gè)體常量、個(gè)體變量或是個(gè)體函數(shù)。個(gè)體變?cè)淖兓秶Q(chēng)為個(gè)體域（或論域）例：

P(x):表示x是素?cái)?shù)

FRIEND(a,b)：表示a和b是朋友第二十七頁(yè)，共55頁(yè)。28謂詞演繹的歸結(jié)方法謂詞、函數(shù)、量詞個(gè)體函數(shù)：表示項(xiàng)之間的關(guān)系

有了個(gè)體函數(shù)之后，謂詞的表達(dá)能力更強(qiáng)。假如個(gè)體函數(shù)father(b)表示“個(gè)體b的父親”，則謂詞FRIEND(a,father(b))表示“a和b的父親是朋友”，顯然表達(dá)能力更強(qiáng)了。例：

E(x,y):表示x和y相等關(guān)系

個(gè)體函數(shù)square(x)：表示個(gè)體x的平方

則謂詞E(square(a),b)表示什么？第二十八頁(yè)，共55頁(yè)。29謂詞演繹的歸結(jié)方法謂詞、函數(shù)、量詞量詞

全稱(chēng)量詞：“所有”,“一切”,“任一”,“全體”,“凡是”等詞稱(chēng)為全稱(chēng)量詞，記為

存在量詞：“存在”、“有些”、“至少有一個(gè)”、“有的”等詞統(tǒng)稱(chēng)為存在量詞，記為例：謂詞M(x):表示x是人，謂詞N(x):表示x有名字，則x(M(x)→N(x))表示“凡是人都有名字”。

謂詞G(x):表示x是整數(shù)，E(x)：表示x是偶數(shù)，則x（G(x)∧E(x))表示“存在不是偶數(shù)的整數(shù)”

知識(shí)“不存在最大的整數(shù)”的表示：謂詞D(x,y)表示x大于y。則表示如下：x(G(x)∧y(G(y)→D(x,y)))第二十九頁(yè)，共55頁(yè)。30謂詞演繹的歸結(jié)方法命題邏輯中的歸結(jié)推理方法

若命題邏輯描述的命題A1,A2,...An和B,要證明在A1∧A2∧...∧An成立的條件下有B成立，或說(shuō)A1∧A2∧...∧An→B。很顯然A1∧A2∧...∧An→B等價(jià)于證明A1∧A2∧...∧An∧B是矛盾(永假)式。歸結(jié)推理的方法就是從A1∧A2∧...∧An∧B出發(fā)使用歸結(jié)推理規(guī)則來(lái)尋找矛盾，從而證明A1∧A2∧...∧An→B的成立。這種方法稱(chēng)為反演推理方法。第三十頁(yè)，共55頁(yè)。31謂詞演繹的歸結(jié)方法命題邏輯的歸結(jié)推理過(guò)程利用邏輯蘊(yùn)含式和邏輯等價(jià)式將命題公式化成合取范式(子句的合取)子句集：將若干個(gè)子句的合取式中的合取詞∧換成逗號(hào)，形成的集合稱(chēng)為子句集。從子句集S出發(fā)，僅只對(duì)S的子句間使用歸結(jié)推理規(guī)則（即求歸結(jié)式），并將所得歸結(jié)式仍放入S中，進(jìn)而再對(duì)新子句集使用歸結(jié)推理規(guī)則，重復(fù)這些步驟直到得到空子句□（說(shuō)明有矛盾）。也就是說(shuō)S是不可滿足的，從而與子句集S對(duì)應(yīng)的定理是成立的。第三十一頁(yè)，共55頁(yè)。32謂詞演繹的歸結(jié)方法謂詞公式的子句形

合取范式和析取范式

合取范式：若謂詞公式A有如下形式B1∧B2∧...∧Bn,其中Bi(i=1,2,...n)形如L1∨L2∨...∨Ln，并且L1,L2,...Ln都是文字。

析取范式：若謂詞公式A有如下形式B1∨B2∨...∨Bn,其中Bi(i=1,2,...n)形如L1∧L2∧...∧Ln，并且L1,L2,...Ln都是文字。

前束范式：將所有的量詞都放在謂詞公式的前面。前束范式可分成前束合取范式和前束析取范式。第三十二頁(yè)，共55頁(yè)。33謂詞演繹的歸結(jié)方法化成前束合取范式的步驟Step1：消去∧，∨，以外的連接詞

AB.............A∨B

AB............(A∨B)∧(B∨A)step2：將連接詞內(nèi)移，移到原子公式之前

(A)A

(A∧B)

A∨B

(A∨B)

A∧B

xA(x)

xA(x)

xA(x)

xA(x)第三十三頁(yè)，共55頁(yè)。34謂詞演繹的歸結(jié)方法化成前束合取范式的步驟Step3：將量詞盡可能向左推，推到前綴所在的位置，用下列公式：

xA(x)∨B............x（A(x)∨B），其中B中不含約束變?cè)?/p>

B∨xA(x)............x（B∨A(x)），其中B中不含約束變?cè)?/p>

xA(x)∨B............x（A(x)∨B），其中B中不含約束變?cè)?/p>

B∨xA(x)............x（B∨A(x)），其中B中不含約束變?cè)?/p>

同樣對(duì)上面式子中的∨改為∧可得到另一組關(guān)于的∧的替換式。第三十四頁(yè)，共55頁(yè)。35謂詞演繹的歸結(jié)方法化成前束合取范式的步驟step4：用下式進(jìn)行替換：

xA(x)∧xB(x)..................x（A(x)∧B(x)）

xA(x)∨xB(x)..................xy（A(x)∨B(y)）,采用更名規(guī)則

xA(x)∨xB(x)..................x（A(x)∨B(x)）

xA(x)∧xB(x)..................xy（A(x)∧B(y)）,采用更名規(guī)則Step5：使用∧，∨的分配律化成合取范式。第三十五頁(yè)，共55頁(yè)。36謂詞演繹的歸結(jié)方法將謂詞公式化成子句集的步驟按上述步驟化成前束合取范式；化成Skolem標(biāo)準(zhǔn)型，消去存在量詞；消取存在量詞時(shí)，還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況：

⑴若該存在量詞在某些全稱(chēng)量詞的轄域內(nèi)，則用這些全稱(chēng)量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)@樣的函數(shù)稱(chēng)為Skolem函數(shù)；

⑵若該存在量詞不在任何全稱(chēng)量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域中相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱(chēng)為Skolem常量。第三十六頁(yè)，共55頁(yè)。37謂詞演繹的歸結(jié)方法將謂詞公式化成子句集的步驟消去所有全稱(chēng)量詞

消去合取詞∧，用逗號(hào)代替，以子句為元素組成一個(gè)集合S，即是謂詞公式的子句集。第三十七頁(yè)，共55頁(yè)。38謂詞演繹的歸結(jié)方法引入控制策略從謂詞邏輯的歸結(jié)方法中我們可以看出，當(dāng)使用歸結(jié)法時(shí)，若從子句集S出發(fā)做所有可能的歸結(jié)，并將歸結(jié)式加入S中，再做第二層這樣的歸結(jié)，…直到產(chǎn)生空子句。這種盲目的歸結(jié)，會(huì)產(chǎn)生組合爆炸問(wèn)題。這種無(wú)控制的歸結(jié)導(dǎo)致大量的不必要的歸結(jié)式的產(chǎn)生。如何給出控制策略，以使系統(tǒng)僅選擇合式的子句對(duì)其做歸結(jié)來(lái)避免多余不必要的歸結(jié)式的出現(xiàn)，或者說(shuō)少做些歸結(jié)但仍然導(dǎo)出空子句來(lái)，這已經(jīng)成為一個(gè)重要的問(wèn)題。第三十八頁(yè)，共55頁(yè)。39謂詞演繹的歸結(jié)方法引入控制策略歸納起來(lái)，歸結(jié)過(guò)程策略控制的要點(diǎn)如下：要解決的問(wèn)題：歸結(jié)方法避免知識(shí)爆炸?？刂撇呗缘哪康模簹w結(jié)點(diǎn)盡量少。控制策略的原則：刪除不必要的子句，或?qū)⒓託w結(jié)的子句做限制。給出控制策略，以使僅選擇合式的子句對(duì)其做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)。第三十九頁(yè)，共55頁(yè)。40謂詞演繹的歸結(jié)方法引入控制策略置換與合一(含有變量的歸結(jié)式)在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定的合式公式或合式公式集，以產(chǎn)生新的合式公式。一個(gè)重要的推理規(guī)則是假言推理，這就是由合式公式W1和W1=>W2產(chǎn)生合式公式W2的運(yùn)算。另一個(gè)推理規(guī)則叫做全稱(chēng)化推理，它是由合式公式(x)W(x)產(chǎn)生合式公式W(A)，其中A為任意常量符號(hào)。第四十頁(yè)，共55頁(yè)。41謂詞演繹的歸結(jié)方法引入控制策略置換與合一(含有變量的歸結(jié)式)在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定的合式公式或合式公式集，以產(chǎn)生新的合式公式。一個(gè)重要的推理規(guī)則是假言推理，這就是由合式公式W1和W1=>W2產(chǎn)生合式公式W2的運(yùn)算。另一個(gè)推理規(guī)則叫做全稱(chēng)化推理，它是由合式公式(x)W(x)產(chǎn)生合式公式W(A)，其中A為任意常量符號(hào)。綜合推理：它是由合式公式(x)W1(x)=>W2(x)，W1(A)產(chǎn)生合式公式W2(A)，其中A為任意常量符號(hào)。第四十一頁(yè)，共55頁(yè)。42謂詞演繹的歸結(jié)方法引入控制策略置換與合一一個(gè)表達(dá)式的項(xiàng)可以是常量、變量和函數(shù)。合一就是尋找項(xiàng)對(duì)變量的置換而使表達(dá)式一致。置換可用有序?qū)Φ募蟬={t1/v1,t2/v2,…,tn/vn}表示，其中ti/vi表示每個(gè)變量vi用ti替換。ti可以是常量或變量或函數(shù)。但是f(vi)

/vi是不允許的，即在替換中不允許在項(xiàng)中出現(xiàn)被替換的變量。置換是可以結(jié)合的，換句話說(shuō)，如果s1和s2是合式公式E的置換，那么(E)s1s2=((E)s1)s2第四十二頁(yè)，共55頁(yè)。43謂詞演繹的歸結(jié)方法引入控制策略置換與合一把置換s作用于集合{Ei}中的每個(gè)公式得到的例的集合用{Ei}s表示。如果存在一個(gè)置換s，使得(E1)s=(E2)s=…=(En)s，那么稱(chēng)公式集合{Ei}為可合一的，置換s稱(chēng)為{Ei}的合一者。下面是遞歸合一算法UNIFY(E1,E2)；其中，E1,E2

是待合一的公式：1、如果E1或E2是原子公式，無(wú)妨設(shè)是E1則執(zhí)行22、如果E1和E2是相同的，returnNIL3、如果E1是一個(gè)變量則執(zhí)行4否則到64、如果E1出現(xiàn)在E2中則returnFAIL5、return{E2/E1}6、F1E1的第一個(gè)元素，T1E1的其余元素；F2E2的第一個(gè)元素，T2E2的其余元素；7、Z1UNIFY(F1,F2)8、如果Z1=FAIL則returnFAIL9、G1Z1作用于T1的結(jié)果；G2Z1作用于T2的結(jié)果；10、Z2UNIFY(G1,G2)11、如果Z2=FAIL則returnFAIL；否則returnZ1與Z2的合成。第四十三頁(yè)，共55頁(yè)。44謂詞演繹的歸結(jié)方法在謂詞邏輯中，子句含有變量。這時(shí)，尋找一個(gè)置換，作用于給定的兩個(gè)子句，使它們包括互補(bǔ)文字，即存在文字1和?1，然后進(jìn)行歸結(jié)。設(shè)C1和C2是兩個(gè)沒(méi)有相同變量的子句，并分別表示成兩個(gè)文字集合{Li}和{Mi}，li是{Li}的一個(gè)文字，?mi是{Mi}的一個(gè)子集。若存在s是文字li和mi的最小合一置換，則C12={{Li}-{li}}{{Mi}-{?mi}}s，為子句C1和C2的歸結(jié)。更一般定義為：設(shè)C1和C2是兩個(gè)沒(méi)有相同變量的子句，并分別表示成兩個(gè)文字集合{Li}和{Mi}，{li}是{Li}的一個(gè)子集，{mi}是的一個(gè)子集{Mi}。若s是集合{li}和{?mi}的并集的最小合一置換，則稱(chēng)C12={{Li}-{li}}{{Mi}-{mi}}s為C1和C2的歸結(jié)。第四十四頁(yè)，共55頁(yè)。45謂詞演繹的歸結(jié)方法等式謂詞在歸結(jié)的過(guò)程中，通常謂詞名的語(yǔ)義并不能真正獲取，因此，有時(shí)無(wú)法得到正確的結(jié)論。例如：假設(shè)有Equals(A,B)，但是，無(wú)法歸結(jié)：?P(A,B)和P(B,A)。因此，需要引入等式謂詞：自反性：(x)Equals(x,x)對(duì)稱(chēng)性：(x,y)[Equals(x,y)Equals(y,x)]傳遞性：(x,y,z)[Equals(x,y)Equals(y,z)Equals(x,z)]第四十五頁(yè)，共55頁(yè)。46謂詞演繹的歸結(jié)方法等式謂詞在歸結(jié)的過(guò)程中，通常謂詞名的語(yǔ)義并不能真正獲取，因此，有時(shí)無(wú)法得到正確的結(jié)論。即使有等式謂詞有了這些公理，但還是無(wú)法得到，例：{P(A)，Equals(A,B)}P(B)。于是，我們給出等價(jià)替換規(guī)則：假如有兩個(gè)子句：1，2。1={()1’}，2={Equals(,)2’}其中，，，是項(xiàng)。1’和2’子句。()是包含的文字。如果有一置換使得，能夠合一，那么有1’和2’的調(diào)解式：={[()]1’2’}該調(diào)解式實(shí)際上，是將中用替換，并且與1’和2’做析取。第四十六頁(yè)，共55頁(yè)。47歸結(jié)反駁搜索策略排序策略定義n層歸結(jié)項(xiàng)：1）把原子的子句稱(chēng)為0層歸結(jié)項(xiàng)；2）i+1層的歸結(jié)項(xiàng)是一個(gè)i層歸結(jié)項(xiàng)和一個(gè)j層歸結(jié)項(xiàng)歸結(jié)的結(jié)果。廣度優(yōu)先：按照歸結(jié)項(xiàng)的層數(shù)每次產(chǎn)生該層的所有歸結(jié)項(xiàng)，逐層生成，直到或者產(chǎn)生了空子句，或者不能再產(chǎn)生新的層次。深度優(yōu)先：首先產(chǎn)生一個(gè)第1層的歸結(jié)項(xiàng)，然后，用某些第1層的歸結(jié)項(xiàng)或0層歸結(jié)項(xiàng)產(chǎn)生第2層的歸結(jié)項(xiàng)，依次類(lèi)推。排序歸結(jié)的一個(gè)通用策略是單元優(yōu)先策略：這種歸結(jié)至少有一個(gè)子句有一個(gè)單一的文字構(gòu)成。這樣的子句稱(chēng)為單元子句。第四十七頁(yè)，共55頁(yè)。48歸結(jié)反駁搜索策略精確策略支持集的概念：子句2是另一個(gè)子句1的后裔，當(dāng)且僅當(dāng)：(a)2是1和另一些子句的一個(gè)歸結(jié)項(xiàng)；或(b)2是1的后裔與另一些子句的一個(gè)歸結(jié)項(xiàng)。2是1的后裔，那么1是2的祖先。支持集定義為由一些子句組成，這些子句或來(lái)源于待證定理的否定，或者是這些子句的后裔。支持集策略：只允許這樣一些歸結(jié)：在其中正在被歸結(jié)的子句中的一個(gè)在支持集中。支持集策略是反駁完備的。即，假如只對(duì)一個(gè)不可滿足的子句集合運(yùn)用支持集