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

主講：夏幼明《人工智能》示范課程2①規(guī)章演繹系統(tǒng)②謂詞演繹的歸結(jié)方法③歸結(jié)反對(duì)搜尋策略④Hone子句的歸結(jié)“學(xué)問(wèn)演繹”核心內(nèi)容3規(guī)章演繹系統(tǒng)在基于規(guī)章系統(tǒng)中，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配；then局部用于規(guī)定放入工作內(nèi)存的新斷言。這種系統(tǒng)叫做基于規(guī)章的演繹系統(tǒng)(rulebaseddeductionsystem)。在這種系統(tǒng)中，通常稱規(guī)章的if局部為前項(xiàng)(antecedent)，稱規(guī)章的then局部為后項(xiàng)(consequent)。4規(guī)章演繹系統(tǒng)基于規(guī)章的求解系統(tǒng)由if-then形式的規(guī)章建立的。例如：if(antecedent)then(consequent)

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

前件

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

6規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng)從if局部向then局部推理的過(guò)程稱為正向推理，即從事實(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ì)全稱量詞轄域內(nèi)的變量進(jìn)展改名和變量標(biāo)準(zhǔn)化，而存在量詞量化變量用Skolem函數(shù)代替。刪去全稱量詞，而任何余下的變量都被認(rèn)為具有全稱量化作用。7規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng)從if局部向then局部推理的過(guò)程稱為正向推理，即從事實(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)化，使得同一變量不消失在事實(shí)表達(dá)式的不同主要合取式中。更名后得表達(dá)式：Q(w,A)∧{[R(v)∧P(v)]∨S(A,v)}必需留意到Q(v，A)中的變量v可用新變量w代替，而合取式[R(v)∧P(v)]中的變量v卻不行更名，由于后者也消失在析取式S(A,v)中。8規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng)從if局部向then局部推理的過(guò)程稱為正向推理，即從事實(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)}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)。10規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng) 與或圖的正向推理：限制規(guī)章的公式類型為：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)，稱為根節(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)公式成立。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)畫，即把根節(jié)點(diǎn)畫在最下面，而把其后繼節(jié)點(diǎn)往上畫。我們將要爭(zhēng)論到目標(biāo)公式的與或圖表示，它是按通常方式畫出的，即目標(biāo)在上面。

12規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng) 推理規(guī)章：消解(歸結(jié))把原子公式和原子公式的否認(rèn)稱為文字。任何文字的析取式稱為子句。析取式P?Q??R可用子句表示為：{P，Q，?R}。不包含任何文字的子句稱為空子句〔NIL〕?？兆泳涫怯兰俚?。由子句構(gòu)成的集合稱為子句集。歸結(jié)定義為：從{}1和{}2(1和2是文字集合，是一個(gè)文字)，可以歸結(jié)為12，它被稱為兩個(gè)子句的歸結(jié)式。是被歸結(jié)的文字。這個(gè)過(guò)程稱為歸結(jié)。13規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng) 推理規(guī)章：消解(歸結(jié))歸結(jié)定義為：從{}1和{}2(1和2是文字集合，是一個(gè)文字)，可以歸結(jié)為12，它被稱為兩個(gè)子句的歸結(jié)式。是被歸結(jié)的文字。這個(gè)過(guò)程稱為歸結(jié)。例：1、P?R和Q??R歸結(jié)R為P?Q。留意到P?R與Q??R的等價(jià)寫法為?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é)與假言推理是全都的。14規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng) 推理規(guī)章：消解(歸結(jié))歸結(jié)是合理的。證明：所謂合理的，就是說(shuō)，假設(shè){}1和{}2均是真的，那么12是真的。對(duì)的真假值爭(zhēng)論就可以了。情形一：是真的，那么，是假的，因此，{}2為真，必需2為真，故12是真的。情形二：是假的，那么，{}1為真，必需1為真，故12是真的。綜合情形一和二，可知，1、2至少有一個(gè)必需為真，即12是真的。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∨Z16規(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)都稱為文字節(jié)點(diǎn)，由一個(gè)與或圖表示的子句集就是對(duì)應(yīng)于該圖中以文字節(jié)點(diǎn)終止的解圖集。17規(guī)章演繹系統(tǒng)(1)規(guī)章正向演繹系統(tǒng) 作為終止條件的目標(biāo)公式應(yīng)用規(guī)章推理的目的在于從某個(gè)事實(shí)公式和某個(gè)規(guī)章集動(dòng)身來(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)上。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)的否認(rèn)為:(C∨G)；其子句形為:C，GP∨

CP∨

QQ∨

CCQ

Q∨

G

G

Q

NIL19規(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)公式成立。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)，把否認(rèn)符號(hào)移進(jìn)括號(hào)內(nèi)，對(duì)全稱量詞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ù)。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)22規(guī)章演繹系統(tǒng)(2)規(guī)章逆向演繹系統(tǒng)與或圖的逆向推理規(guī)章變換我們應(yīng)用逆向推理規(guī)章來(lái)變換逆向演繹系統(tǒng)的與或圖構(gòu)造，逆向推理規(guī)章是建立在確定的蘊(yùn)涵式根底上的，現(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)。23規(guī)章演繹系統(tǒng)(2)規(guī)章逆向演繹系統(tǒng)與或圖的逆向推理規(guī)章變換事實(shí):F1:DOG(FIDO);狗的名字叫FidoF2:BARKS(FIDO);Fido是不叫的F3:WAGS-TAIL(FIDO);Fido搖尾巴

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

規(guī)章:R1:[WAGS-TAIL(x1)∧DOG(x1)]→FRIENDLY(x1)搖尾巴的狗是溫存的狗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)]是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?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/x126規(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)]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是謂詞的參量〔或稱項(xiàng)〕，一般表示個(gè)體，它可以是個(gè)體常量、個(gè)體變量或是個(gè)體函數(shù)。個(gè)體變?cè)淖兓秶Q為個(gè)體域〔或論域〕例：

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

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

有了個(gè)體函數(shù)之后，謂詞的表達(dá)力量更強(qiáng)。假設(shè)個(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)表示什么？29謂詞演繹的歸結(jié)方法謂詞、函數(shù)、量詞量詞

全稱量詞：“全部”,“一切”,“任一”,“全體”,“但凡”等詞稱為全稱量詞，記為

存在量詞：“存在”、“有些”、“至少有一個(gè)”、“有的”等詞統(tǒ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ù)”

學(xué)問(wèn)“不存在最大的整數(shù)”的表示：謂詞D(x,y)表示x大于y。則表示如下：x(G(x)∧y(G(y)→D(x,y)))30謂詞演繹的歸結(jié)方法命題規(guī)律中的歸結(jié)推理方法假設(shè)命題規(guī)律描述的命題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動(dòng)身使用歸結(jié)推理規(guī)章來(lái)查找沖突，從而證明A1∧A2∧...∧An→B的成立。這種方法稱為反演推理方法。31謂詞演繹的歸結(jié)方法命題規(guī)律的歸結(jié)推理過(guò)程利用規(guī)律蘊(yùn)含式和規(guī)律等價(jià)式將命題公式化成合取范式(子句的合取)子句集：將假設(shè)干個(gè)子句的合取式中的合取詞∧換成逗號(hào)，形成的集合稱為子句集。從子句集S動(dòng)身，僅只對(duì)S的子句間使用歸結(jié)推理規(guī)章〔即求歸結(jié)式〕，并將所得歸結(jié)式仍放入S中，進(jìn)而再對(duì)新子句集使用歸結(jié)推理規(guī)章，重復(fù)這些步驟直到得到空子句□〔說(shuō)明有沖突〕。也就是說(shuō)S是不行滿足的，從而與子句集S對(duì)應(yīng)的定理是成立的。32謂詞演繹的歸結(jié)方法謂詞公式的子句形合取范式和析取范式

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

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

前束范式：將全部的量詞都放在謂詞公式的前面。前束范式可分成前束合取范式和前束析取范式。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)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)于的∧的替換式。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：使用∧，∨的安排律化成合取范式。36謂詞演繹的歸結(jié)方法將謂詞公式化成子句集的步驟按上述步驟化成前束合取范式；化成Skolem標(biāo)準(zhǔn)型，消去存在量詞；消取存在量詞時(shí)，還要進(jìn)展變?cè)鎿Q。變?cè)鎿Q分兩種狀況：

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

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

消去合取詞∧，用逗號(hào)代替，以子句為元素組成一個(gè)集合S，即是謂詞公式的子句集。38謂詞演繹的歸結(jié)方法引入掌握策略從謂詞規(guī)律的歸結(jié)方法中我們可以看出，當(dāng)使用歸結(jié)法時(shí)，假設(shè)從子句集S動(dòng)身做全部可能的歸結(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)避開(kāi)多余不必要的歸結(jié)式的消失，或者說(shuō)少做些歸結(jié)但仍舊導(dǎo)出空子句來(lái)，這已經(jīng)成為一個(gè)重要的問(wèn)題。39謂詞演繹的歸結(jié)方法引入掌握策略歸納起來(lái)，歸結(jié)過(guò)程策略掌握的要點(diǎn)如下：要解決的問(wèn)題：歸結(jié)方法避開(kāi)學(xué)問(wèn)爆炸。掌握策略的目的：歸結(jié)點(diǎn)盡量少。掌握策略的原則：刪除不必要的子句，或?qū)⑴c歸結(jié)的子句做限制。給出掌握策略，以使僅選擇合式的子句對(duì)其做歸結(jié)。避開(kāi)多余的、不必要的歸結(jié)式消失。40謂詞演繹的歸結(jié)方法引入掌握策略置換與合一(含有變量的歸結(jié)式)在謂詞規(guī)律中，有些推理規(guī)章可應(yīng)用于肯定的合式公式或合式公式集，以產(chǎn)生新的合式公式。一個(gè)重要的推理規(guī)章是假言推理，這就是由合式公式W1和W1=>W2產(chǎn)生合式公式W2的運(yùn)算。另一個(gè)推理規(guī)章叫做全稱化推理，它是由合式公式(x)W(x)產(chǎn)生合式公式W(A)，其中A為任意常量符號(hào)。41謂詞演繹的歸結(jié)方法引入掌握策略置換與合一(含有變量的歸結(jié)式)在謂詞規(guī)律中，有些推理規(guī)章可應(yīng)用于肯定的合式公式或合式公式集，以產(chǎn)生新的合式公式。一個(gè)重要的推理規(guī)章是假言推理，這就是由合式公式W1和W1=>W2產(chǎn)生合式公式W2的運(yùn)算。另一個(gè)推理規(guī)章叫做全稱化推理，它是由合式公式(x)W(x)產(chǎn)生合式公式W(A)，其中A為任意常量符號(hào)。綜合推理：它是由合式公式(x)W1(x)=>W2(x)，W1(A)產(chǎn)生合式公式W2(A)，其中A為任意常量符號(hào)。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)中消失被替換的變量。置換是可以結(jié)合的，換句話說(shuō)，假設(shè)s1和s2是合式公式E的置換，那么(E)s1s2=((E)s1)s243謂詞演繹的歸結(jié)方法引入掌握策略置換與合一把置換s作用于集合{Ei}中的每個(gè)公式得到的例的集合用{Ei}s表示。假設(shè)存在一個(gè)置換s，使得(E1)s=(E2)s=…=(En)s，那么稱公式集合{Ei}為可合一的，置換s稱為{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的合成。44謂詞演繹的歸結(jié)方法在謂詞規(guī)律中，子句含有變量。這時(shí)，查找一個(gè)置換，作用于給定的兩個(gè)子句，使它們包括互補(bǔ)文字，即存在文字1和?1，然后進(jìn)展歸結(jié)。設(shè)C1和C2是兩個(gè)沒(méi)有一樣變量的子句，并分別表示成兩個(gè)文字集合{Li}和{Mi}，li是{Li}的一個(gè)文字，?mi是{Mi}的一個(gè)子集。假設(shè)存在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}。假設(shè)s是集合{li}和{?mi}的并集的最小合一置換，則稱C12={{Li}-{li}}{{Mi}-{mi}}s為C1和C2的歸結(jié)。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ì)稱性：(x,y)[Equals(x,y)Equals(y,x)]傳遞性：(x,y,z)[Equals(x,y)Equals(y,z)Equals(x,z)]46謂詞演繹的歸結(jié)方法等式謂詞在歸結(jié)的過(guò)程中，通常謂詞名的語(yǔ)義并不能真正獵取，因此，有時(shí)無(wú)法得到正確的結(jié)論。即使有等式謂詞有了這些公理，但還是無(wú)法得到，例：{P(A)，Equals(A,B)}P(B)。于是，我們給出等價(jià)替換規(guī)章：假設(shè)有兩個(gè)子句：1，2。1={()1’}，2={Equals(,)2’}其中，，，是項(xiàng)。1’和2’子句。()是包含的文字。假設(shè)有一置換使得，能夠合一，那么有1’和2’的調(diào)解式：={[()]1’2’}該調(diào)解式實(shí)際上，是將中用替換，并且與1’和2’做析取。47歸結(jié)反對(duì)搜尋策略排序策略定義n層歸結(jié)項(xiàng)：1〕把原子的子句稱為0層歸結(jié)項(xiàng)；2〕i+1層的歸結(jié)項(xiàng)是一個(gè)i層歸結(jié)項(xiàng)和一個(gè)j層歸結(jié)項(xiàng)歸結(jié)的結(jié)果。廣度優(yōu)先：依據(jù)歸結(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)，依次類推。排序歸結(jié)的一個(gè)通用策略是單元優(yōu)先策略：這種歸結(jié)至少有一個(gè)子句有一個(gè)單一的文字構(gòu)成。這樣的子句稱為單元子句。48歸結(jié)反對(duì)搜尋策略準(zhǔn)確策略支持集的概念：子句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)源于待證定理的否認(rèn)，或者是這些子句的后裔。支持集策略：只允許這樣一些歸結(jié)：在其中正在被歸結(jié)的子句中的一個(gè)在支持集中。支持集策略是反對(duì)完備的。即，假設(shè)只對(duì)一個(gè)不行滿足的子句集合運(yùn)用支持集歸