1、5/1/20221第七章第七章 基于規(guī)則的演繹系統(tǒng)基于規(guī)則的演繹系統(tǒng)5/1/20222l歸結(jié)方法 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單（僅使用一條推理規(guī)則） 完備 缺點(diǎn)：低效（不使用領(lǐng)域知識） 轉(zhuǎn)換成子句形式過程中失去了控制信息 l基于規(guī)則的演繹系統(tǒng) 優(yōu)點(diǎn)：易于理解（推理過程與人的推理過程相近） 高效（盡量使用與領(lǐng)域有關(guān)的知識） 缺點(diǎn)：不完備5/1/20223基于規(guī)則的演繹系統(tǒng)基于規(guī)則的演繹系統(tǒng)l描述領(lǐng)域知識的邏輯語句分為兩類： 描述該領(lǐng)域的一般性規(guī)律-轉(zhuǎn)換成產(chǎn)生式規(guī)則 描述該領(lǐng)域的具體情況或狀態(tài)-轉(zhuǎn)換成產(chǎn)生式系統(tǒng)的狀態(tài)描述l工作過程 選可用的產(chǎn)生式規(guī)則用于狀態(tài)描述、產(chǎn)生新的狀態(tài)描述，當(dāng)產(chǎn)生的狀態(tài)描述滿足終止條件時

2、，推導(dǎo)任務(wù)完成。l工作方式正向系統(tǒng)：以事實(shí)作為初始狀態(tài)描述，以結(jié)論為終止條件的演繹系統(tǒng)反向系統(tǒng)：以結(jié)論作為初始狀態(tài)描述，以事實(shí)為終止條件的演繹系統(tǒng)5/1/202247.1 正向演繹系統(tǒng)正向演繹系統(tǒng)一、初始狀態(tài)描述一、初始狀態(tài)描述 先把描述事實(shí)的邏輯公式轉(zhuǎn)換成不含蘊(yùn)涵符號的先把描述事實(shí)的邏輯公式轉(zhuǎn)換成不含蘊(yùn)涵符號的AND/OR形式，再用形式，再用AND/OR圖表示。圖表示。l事實(shí)表達(dá)式的事實(shí)表達(dá)式的AND/OR形轉(zhuǎn)換形轉(zhuǎn)換 與化與化Skolem范式過程類似范式過程類似 不同：不要求母式是合取范式不同：不要求母式是合取范式 要求：不同的主合取項里變量使用不同的名字。要求：不同的主合取項里變量使用不

3、同的名字。5/1/20225例例表示事實(shí)的邏輯公式G= u v (Q (v,u) (R(v)P(v) S(u,v) = u v (Q (v,u)( (R(v) P(v) S(u,v)用常量符號A代替u得 v(Q(v,A)(R(v)P(v)S(A,v)對變量改名,使得不同的主合取項里變量使用不同的名字: wQ(w,A) v(R(v)P(v)S(A,v)Q(w,A) (R(v)P(v)S(A,v)5/1/20226l 事實(shí)表達(dá)式的事實(shí)表達(dá)式的AND/OR圖表示圖表示 節(jié)點(diǎn)：表示事實(shí)節(jié)點(diǎn)：表示事實(shí)AND/OR形式的子表達(dá)式形式的子表達(dá)式如 果 子 表 達(dá) 式如 果 子 表 達(dá) 式 E1, , Ek的

4、 父 親 節(jié) 點(diǎn) 是的 父 親 節(jié) 點(diǎn) 是（E1Ek）,則用則用k-連接符把這些子節(jié)點(diǎn)與連接符把這些子節(jié)點(diǎn)與父節(jié)點(diǎn)連接起來；父節(jié)點(diǎn)連接起來；如 果 子 表 達(dá) 式如 果 子 表 達(dá) 式 E1, , Ek的 父 親 節(jié) 點(diǎn) 是的 父 親 節(jié) 點(diǎn) 是（E1Ek），則用），則用1-連接符分別把這些子節(jié)連接符分別把這些子節(jié)點(diǎn)與父節(jié)點(diǎn)連接起來。點(diǎn)與父節(jié)點(diǎn)連接起來。 5/1/20227l表示邏輯公式的表示邏輯公式的AND/OR圖的性質(zhì)：圖的性質(zhì)：該公式對應(yīng)的所有子句可以從終止在葉節(jié)點(diǎn)的解圖集合中該公式對應(yīng)的所有子句可以從終止在葉節(jié)點(diǎn)的解圖集合中讀出讀出- AND/OR圖是子句形式的一種緊湊表示方式圖是子句

5、形式的一種緊湊表示方式例例.Q(w,A) (R(v)P(v)S(A,v)對應(yīng)的所有子句對應(yīng)的所有子句 Q(w,A) S(A,v)R(v) S(A,v)P(v) 都可從解圖讀出來。都可從解圖讀出來。Note:其一般性要比子句形式稍差一點(diǎn)。其一般性要比子句形式稍差一點(diǎn)。 原因：原因： 在子句形式中，不同子句之間變量允許任意改名；在子句形式中，不同子句之間變量允許任意改名； 在在AND/OR圖表示中，改名有時會受到限制圖表示中，改名有時會受到限制-僅允許最僅允許最外層合取項間經(jīng)改名無公共變量。外層合取項間經(jīng)改名無公共變量。5/1/20228 二、正向演繹系統(tǒng)的規(guī)則二、正向演繹系統(tǒng)的規(guī)則lF規(guī)則的形式

6、：規(guī)則的形式：LW 是正常是正常Skolem化后恢復(fù)成蘊(yùn)涵式，且要求：化后恢復(fù)成蘊(yùn)涵式，且要求： L是單文字；是單文字； W是是AND/OR形公式；形公式； 出現(xiàn)在蘊(yùn)涵式中的所有變量假定是對整個蘊(yùn)涵式全稱定量的；出現(xiàn)在蘊(yùn)涵式中的所有變量假定是對整個蘊(yùn)涵式全稱定量的； 不同規(guī)則使用的變量名互不相同；不同規(guī)則使用的變量名互不相同； 規(guī)則與事實(shí)規(guī)則與事實(shí)AND/OR圖中的變量名也不相同。圖中的變量名也不相同。 Note:正向演繹系統(tǒng)的規(guī)則的前提必須是單文字，看起來似乎限制正向演繹系統(tǒng)的規(guī)則的前提必須是單文字，看起來似乎限制很強(qiáng)。但是，很多邏輯公式可以轉(zhuǎn)換成滿足這種限制的規(guī)則很強(qiáng)。但是，很多邏輯公式可

7、以轉(zhuǎn)換成滿足這種限制的規(guī)則. 例如，形式為（例如，形式為（L1L2）W的蘊(yùn)涵式等價于兩條規(guī)則的蘊(yùn)涵式等價于兩條規(guī)則 L1W和和L2W。5/1/20229例例 對于公式對于公式 x( y zP(x,y,z) uQ(x,u)可以通過如下步驟實(shí)現(xiàn)其轉(zhuǎn)換：可以通過如下步驟實(shí)現(xiàn)其轉(zhuǎn)換：(1)暫時刪除蘊(yùn)涵符號：暫時刪除蘊(yùn)涵符號： x( y zP(x,y,z) uQ(x,u)(2)把否定符移到原子前：把否定符移到原子前： x( y zP(x,y,z) uQ(x,u)(3)化前束范式：化前束范式： x y z u（P(x,y,z) Q(x,u)(4)Skolem化：用化：用f(x,y)代代z，得，得P(x,y

8、,f(x,y) Q(x,u)(5)恢復(fù)成蘊(yùn)涵形式：恢復(fù)成蘊(yùn)涵形式：P(x,y,f(x,y)Q(x,u)5/1/202210lF規(guī)則的使用規(guī)則的使用 規(guī)則規(guī)則LW中的中的L同同AND/OR圖葉節(jié)點(diǎn)圖葉節(jié)點(diǎn)n匹配匹配( 合一下合一下)成功時成功時,稱為使用該規(guī)則的一次推理。稱為使用該規(guī)則的一次推理。 應(yīng)用規(guī)則的結(jié)果：把表示應(yīng)用規(guī)則的結(jié)果：把表示W(wǎng) 的的AND/OR圖通過圖通過L連到連到AND/OR圖的節(jié)點(diǎn)圖的節(jié)點(diǎn)n上，上，n和它的后繼節(jié)和它的后繼節(jié)點(diǎn)點(diǎn)L以以1-連接符（稱為匹配弧，用連接符（稱為匹配弧，用 標(biāo)記）連接。標(biāo)記）連接。 5/1/202211例. 已知：事實(shí)：(PQ)R)(S(TU) 帶

9、有文字S的子句是：PQS和RS 規(guī)則：S(XY)Z 子句形式是：SXZ和SYZPQUT(TU)RS(PQ)RS(TU)(PQ)R)(S(TU)(PQ)圖7.2 一個沒有變量的AND/OR圖5/1/202212圖7.3 應(yīng)用一條規(guī)則后所得到的AND/OR圖XZPQ，YZPQ，RYZ，RXZ都包含在解圖所表示的子句中 PQUT(TU)RS(PQ)RS(TU)(PQ)R)(S(TU)(PQ)SZXYYX匹配弧5/1/202213l結(jié)論：對AND/OR圖應(yīng)用一條規(guī)則的過程，以十分簡便高效的方式達(dá)到了使用歸結(jié)方法經(jīng)過多次歸結(jié)才能達(dá)到的目的。 l當(dāng)對一個節(jié)點(diǎn)應(yīng)用規(guī)則后，這個節(jié)點(diǎn)已經(jīng)不再是葉節(jié)點(diǎn)了，但它仍然

10、用單文字標(biāo)記。l把單文字標(biāo)記的節(jié)點(diǎn)叫文字節(jié)點(diǎn)，并且規(guī)定對文字節(jié)點(diǎn)可以繼續(xù)使用規(guī)則。 這樣應(yīng)用規(guī)則后的AND/OR圖既能表示原來的事實(shí)公式又能表示推理結(jié)果。l終止于文字節(jié)點(diǎn)的解圖對應(yīng)于AND/OR圖所表示的子句。5/1/202214包含變量的正向演繹系統(tǒng)例包含變量的正向演繹系統(tǒng)例事實(shí)事實(shí):P(x,y)(Q(x,A)R(B,y) 子句：子句： P(x,y)Q(x,A) P(x,y)R(B,y)規(guī)則規(guī)則:P(A,B)(S(A)X(B)P(x,y) (Q(x,A)R(B,y)P(x,y)Q(x,A)R(B,y)Q(x,A)R(B,y)圖7.5 一個事實(shí)中包含變量的AND/OR圖5/1/202215新增

11、加的葉節(jié)點(diǎn)與原圖的葉節(jié)點(diǎn)構(gòu)成兩個新的解新增加的葉節(jié)點(diǎn)與原圖的葉節(jié)點(diǎn)構(gòu)成兩個新的解圖，與這兩個解圖對應(yīng)的子句是：圖，與這兩個解圖對應(yīng)的子句是：S(A)X(B)Q(A,A)和和S(A)X(B)R(B,B)S(A)X(B)P(A,B)P(x,y)Q(x,A)R(B,y)Q(x,A) R(B,y)P(x,y)Q(x,A) R(B,y)A/x,B/y圖7.6 應(yīng)用了一條包含變量的規(guī)則后的AND/OR圖5/1/202216三、三、正向演繹系統(tǒng)的目標(biāo)正向演繹系統(tǒng)的目標(biāo)l目標(biāo)公式形式：目標(biāo)公式形式：文字的析取形式文字的析取形式。 當(dāng)目標(biāo)公式包含存在定量和全稱定量的變量時，是經(jīng)當(dāng)目標(biāo)公式包含存在定量和全稱定量的

12、變量時，是經(jīng)對偶對偶Skolem化后的文字的析取形式化后的文字的析取形式； 對公式中的變量進(jìn)行改名，使得不同的析取項中沒有對公式中的變量進(jìn)行改名，使得不同的析取項中沒有相同的變量。相同的變量。 Note:對偶對偶Skolem化：全稱量詞用存在量詞的化：全稱量詞用存在量詞的Skolem函函數(shù)所代替，然后把存在量詞刪去，出現(xiàn)的變量假定都是數(shù)所代替，然后把存在量詞刪去，出現(xiàn)的變量假定都是存在定量的。存在定量的。 改名依據(jù)改名依據(jù): x(W1(x) W2(x)= xW1(x) yW2(y)5/1/202217l目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn) 基情形：當(dāng)目標(biāo)公式中的一個文字與基情形：當(dāng)目標(biāo)公式中的一個文字與AND/O

13、R圖中的一個文字圖中的一個文字n相匹配相匹配時，我們把匹配的目標(biāo)文字作為節(jié)點(diǎn)時，我們把匹配的目標(biāo)文字作為節(jié)點(diǎn)n的后繼加到的后繼加到AND/OR圖上，這個圖上，這個節(jié)點(diǎn)稱作節(jié)點(diǎn)稱作目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)。 含變量情形：含變量情形：當(dāng)目標(biāo)公式中的一個文字與當(dāng)目標(biāo)公式中的一個文字與AND/OR圖中的一個文字圖中的一個文字n可可合一時，我們把匹配的目標(biāo)文字作為節(jié)點(diǎn)合一時，我們把匹配的目標(biāo)文字作為節(jié)點(diǎn)n的后繼加到的后繼加到AND/OR圖上，圖上，其間以匹配弧相接，用最一般合一標(biāo)記，這個節(jié)點(diǎn)稱作其間以匹配弧相接，用最一般合一標(biāo)記，這個節(jié)點(diǎn)稱作目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)。l產(chǎn)生式系統(tǒng)成功終止條件產(chǎn)生式系統(tǒng)成功終止條件基情形

14、：當(dāng)基情形：當(dāng)AND/OR圖包含一個終止在目標(biāo)節(jié)點(diǎn)的解圖時，產(chǎn)生式系統(tǒng)圖包含一個終止在目標(biāo)節(jié)點(diǎn)的解圖時，產(chǎn)生式系統(tǒng)成功地終止。成功地終止。含變量情形：對含變量情形：對AND/OR圖不斷地應(yīng)用規(guī)則，當(dāng)圖不斷地應(yīng)用規(guī)則，當(dāng)AND/OR圖包含一個終圖包含一個終止于目標(biāo)節(jié)點(diǎn)的相容解圖時，系統(tǒng)成功地終止。把合一復(fù)合用于相容解止于目標(biāo)節(jié)點(diǎn)的相容解圖時，系統(tǒng)成功地終止。把合一復(fù)合用于相容解圖，就得到從事實(shí)到目標(biāo)的證明。圖，就得到從事實(shí)到目標(biāo)的證明。5/1/202218例例 事實(shí)：事實(shí)：AB 規(guī)則：規(guī)則：ACD BEG 目標(biāo)：目標(biāo)： CG 目標(biāo)節(jié)點(diǎn)AA(AB)規(guī)則ACDBEGBBGGCCDE事實(shí)圖7.4 滿足

15、終止條件的AND/OR圖5/1/202219 Note:對于對于AB，因為不知道，因為不知道A是真的還是是真的還是B是是真的，必須分情況加以證明，先假定真的，必須分情況加以證明，先假定A是真的是真的去證明目標(biāo)，再假定去證明目標(biāo)，再假定B是真的去證明目標(biāo)。只是真的去證明目標(biāo)。只有當(dāng)這兩個證明都成功時，才能算做是證明了有當(dāng)這兩個證明都成功時，才能算做是證明了目標(biāo)。因此在圖目標(biāo)。因此在圖7.4中，節(jié)點(diǎn)（中，節(jié)點(diǎn)（AB）的兩個）的兩個后繼用后繼用2-連接符號（連接符號（AB）連接，這就是為什）連接，這就是為什么在么在AND/OR圖中要使用圖中要使用k-連接符連接析取節(jié)連接符連接析取節(jié)點(diǎn)與其后繼的理由。

16、點(diǎn)與其后繼的理由。 5/1/202220四、四、 正向演繹系統(tǒng)的相容解圖正向演繹系統(tǒng)的相容解圖l定義（定義（替換的相容性集合、合一復(fù)合替換替換的相容性集合、合一復(fù)合替換）設(shè)有替換集合設(shè)有替換集合1 ，2 ，n，每一，每一i 具有如下形式：具有如下形式：i = ti1/vi1 ，tim(i)/vim(i)其中其中ti1，tim(i) 是項，是項，vi1，vim(i)是變量；是變量；我們用這些替換構(gòu)造兩個表達(dá)式我們用這些替換構(gòu)造兩個表達(dá)式U1和和U2如下：如下：U1 =v11，v1m(1)，vn1，vnm(n) U2 =t11，t1m(1)，tn1，tnm(n)）如果如果U1 和和U2是可合一的，

17、則替換集合是可合一的，則替換集合1 ，2 ，n稱作是相容稱作是相容的，否則稱作是不相容的，的，否則稱作是不相容的，U1 和和U2的最一般合一替換也叫做的最一般合一替換也叫做1 ，2 ，n的合一復(fù)合替換。的合一復(fù)合替換。5/1/202221l例：例：問如下問如下1,2是否相容？是否相容？ 若相容，給出合一復(fù)合替換。若相容，給出合一復(fù)合替換。設(shè)設(shè)(1)1,2=A/x,B/x (2)1,2=x/y,y/z (3) 1,2=f(z)/x,f(A)/x (4) 1,2=g(y)/x,f(x)/y5/1/202222Note:只有對具有相容匹配替換的解圖才考慮它只有對具有相容匹配替換的解圖才考慮它對應(yīng)的子

18、句集是合理的對應(yīng)的子句集是合理的. 例例.事實(shí)事實(shí):P(x)Q(x) 規(guī)則規(guī)則:P(A)R(A) Q(B)R(B)(R(A)R(B)不是該不是該AND/OR圖的一個子句表示。圖的一個子句表示。P(x) Q(x)P(x)P(A)R(A)Q(x)Q(B)R(B)A/xB/x圖7.7 一個具有不相容替換的AND/OR圖5/1/202223例例. 事實(shí)事實(shí)DOG(FIDO)(BARKS(FIDO)BITES(FIDO) 規(guī)則：規(guī)則：R1: DOG(x)TERRIER(x) R2: BARKS(y)NOISY(y)目標(biāo)：目標(biāo)： TERRIER(z)NOISY(z)目標(biāo)節(jié)點(diǎn)TERRIER(z)NOISY(z)TERRIER(FIDO)DOG(x)DOG(FIDO)NOISY(FIDO)BARKS(y)BARKS(FIDO)BITE