* * 第七章 基于規(guī)則的演繹系統(tǒng) * * 歸結(jié)方法優(yōu)點：實現(xiàn)簡單（僅使用一條推理規(guī)則）完備缺點：低效（不使用領(lǐng)域知識）轉(zhuǎn)換成子句形式過程中失去了控制信息 基于規(guī)則的演繹系統(tǒng)優(yōu)點：易于理解（推理過程與人的推理過程相近）高效（盡量使用與領(lǐng)域有關(guān)的知識）缺點：不完備 * * 基于規(guī)則的演繹系統(tǒng) 描述領(lǐng)域知識的邏輯語句分為兩類：描述該領(lǐng)域的一般性規(guī)律-----轉(zhuǎn)換成產(chǎn)生式規(guī)則描述該領(lǐng)域的具體情況或狀態(tài)----轉(zhuǎn)換成產(chǎn)生式系統(tǒng)的狀態(tài)描述 工作過程選可用的產(chǎn)生式規(guī)則用于狀態(tài)描述、產(chǎn)生新的狀態(tài)描述，當(dāng)產(chǎn)生的狀態(tài)描述滿足終止條件時，推導(dǎo)任務(wù)完成。 工作方式 正向系統(tǒng)：以事實作為初始狀態(tài)描述，以結(jié)論為終止條件的演繹系統(tǒng) 反向系統(tǒng)：以結(jié)論作為初始狀態(tài)描述，以事實為終止條件的演繹系統(tǒng) * * 7.1 正向演繹系統(tǒng) 一、初始狀態(tài)描述 先把描述事實的邏輯公式轉(zhuǎn)換成不含蘊涵符號的AND/OR形式，再用AND/OR圖表示。 事實表達式的AND/OR形轉(zhuǎn)換與化范式過程類似不同：不要求母式是合取范式要求：不同的主合取項里變量使用不同的名字。 * * 例 表示事實的邏輯公式 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)) * * 事實表達式的AND/OR圖表示 節(jié)點：表示事實AND/OR形式的子表達式 如果子表達式E1,…,Ek的父親節(jié)點是（E1∨…∨Ek）,則用k-連接符把這些子節(jié)點與父節(jié)點連接起來； 如果子表達式E1,…,Ek的父親節(jié)點是（E1∧…∧Ek），則用1-連接符分別把這些子節(jié)點與父節(jié)點連接起來。
* * 表示邏輯公式的AND/OR圖的性質(zhì)： 該公式對應(yīng)的所有子句可以從終止在葉節(jié)點的解圖集合中 讀出---- AND/OR圖是子句形式的一種緊湊表示方式 例.Q(w,A)∧ ((~R(v)∧~P(v))∨~S(A,v))對應(yīng)的所有子句 Q(w,A)~S(A,v)∨~R(v)~S(A,v)∨~P(v)都可從解圖讀出來。 Note:其一般性要比子句形式稍差一點。 原因： 在子句形式中，不同子句之間變量允許任意改名； 在AND/OR圖表示中，改名有時會受到限制----僅允許最外層合取項間經(jīng)改名無公共變量。 * * 二、正向演繹系統(tǒng)的規(guī)則 F規(guī)則的形式：L→W是正?；蠡謴?fù)成蘊涵式，且要求：L是單文字；W是AND/OR形公式；出現(xiàn)在蘊涵式中的所有變量假定是對整個蘊涵式全稱定量的；不同規(guī)則使用的變量名互不相同；規(guī)則與事實AND/OR圖中的變量名也不相同。Note:正向演繹系統(tǒng)的規(guī)則的前提必須是單文字，看起來似乎限制很強。但是，很多邏輯公式可以轉(zhuǎn)換成滿足這種限制的規(guī)則.例如，形式為（L1∨L2）→W的蘊涵式等價于兩條規(guī)則L1→W和L2→W。 * * 例 對于公式 ?x((?y ?zP(x,y,z)) ? ?uQ(x,u)) 可以通過如下步驟實現(xiàn)其轉(zhuǎn)換： (1)暫時刪除蘊涵符號： ?x(~?y ?zP(x,y,z)) ∨ ?uQ(x,u)) (2)把否定符移到原子前： ?x(?y? z~P(x,y,z)) ∨ ?uQ(x,u)) (3)化前束范式：?x?y? z ?u（~P(x,y,z))∨ Q(x,u)) (4)化：用f(x,y)代z，得 ~P(x,y,f(x,y)) ∨ Q(x,u) (5)恢復(fù)成蘊涵形式： P(x,y,f(x,y))→Q(x,u) * * F規(guī)則的使用規(guī)則L→W中的L同AND/OR圖葉節(jié)點n匹配(?合一下)成功時,稱為使用該規(guī)則的一次推理。
應(yīng)用規(guī)則的結(jié)果：把表示W(wǎng)?的AND/OR圖通過L連到AND/OR圖的節(jié)點n上，n和它的后繼節(jié)點L以1-連接符（稱為匹配弧，用? 標(biāo)記）連接。 * * 例. 已知：事實：((P∨Q)∧R)∨(S∧(T∨U))帶有文字S的子句是：P∨Q∨S和R∨S規(guī)則：S→(X∧Y)∨Z子句形式是：~S∨X∨Z和~S∨Y∨Z P Q U T (T∨U) R S (P∨Q)∧R S∧(T∨U) ((P∨Q)∧R)∨(S∧(T∨U)) (P∨Q) 圖7.2 一個沒有變量的AND/OR圖 * * 圖7.3 應(yīng)用一條規(guī)則后所得到的AND/OR圖X∨Z∨P∨Q，Y∨Z∨P∨Q，R∨Y∨Z，R∨X∨Z都包含在解圖所表示的子句中 P Q U T (T∨U) R S (P∨Q)∧R S∧(T∨U) ((P∨Q)∧R)∨(S∧(T∨U)) (P∨Q) S Z X∧Y Y X 匹配弧 * * 結(jié)論：對AND/OR圖應(yīng)用一條規(guī)則的過程，以十分簡便高效的方式達到了使用歸結(jié)方法經(jīng)過多次歸結(jié)才能達到的目的。 當(dāng)對一個節(jié)點應(yīng)用規(guī)則后，這個節(jié)點已經(jīng)不再是葉節(jié)點了，但它仍然用單文字標(biāo)記。 把單文字標(biāo)記的節(jié)點叫文字節(jié)點，并且規(guī)定對文字節(jié)點可以繼續(xù)使用規(guī)則。
這樣應(yīng)用規(guī)則后的AND/OR圖既能表示原來的事實公式又能表示推理結(jié)果。 終止于文字節(jié)點的解圖對應(yīng)于AND/OR圖所表示的子句。 * * 包含變量的正向演繹系統(tǒng)例事實:P(x,y)∨(Q(x,A)∧R(B,y))子句： P(x,y)∨Q(x,A)P(x,y)∨R(B,y)規(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 一個事實中包含變量的AND/OR圖 * * 新增加的葉節(jié)點與原圖的葉節(jié)點構(gòu)成兩個新的解圖，與這兩個解圖對應(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圖 * * 三、正向演繹系統(tǒng)的目標(biāo) 目標(biāo)公式形式：文字的析取形式。當(dāng)目標(biāo)公式包含存在定量和全稱定量的變量時，是經(jīng)對偶化后的文字的析取形式；對公式中的變量進行改名，使得不同的析取項中沒有相同的變量。
Note:對偶化：全稱量詞用存在量詞的函數(shù)所代替，然后把存在量詞刪去，出現(xiàn)的變量假定都是存在定量的。改名依據(jù):?x(W1(x) ∨W2(x))=?xW1(x)∨ ?yW2(y) * * 目標(biāo)節(jié)點 基情形：當(dāng)目標(biāo)公式中的一個文字與AND/OR圖中的一個文字n相匹配時，我們把匹配的目標(biāo)文字作為節(jié)點n的后繼加到AND/OR圖上，這個節(jié)點稱作目標(biāo)節(jié)點。 含變量情形：當(dāng)目標(biāo)公式中的一個文字與AND/OR圖中的一個文字n可合一時，我們把匹配的目標(biāo)文字作為節(jié)點n的后繼加到AND/OR圖上，其間以匹配弧相接，用最一般合一標(biāo)記，這個節(jié)點稱作目標(biāo)節(jié)點。 產(chǎn)生式系統(tǒng)成功終止條件 基情形：當(dāng)AND/OR圖包含一個終止在目標(biāo)節(jié)點的解圖時，產(chǎn)生式系統(tǒng)成功地終止。 含變量情形：對AND/OR圖不斷地應(yīng)用規(guī)則，當(dāng)AND/OR圖包含一個終止于目標(biāo)節(jié)點的相容解圖時，系統(tǒng)成功地終止。把合一復(fù)合用于相容解圖，就得到從事實到目標(biāo)的證明。 * * 例 事實：A∨B 規(guī)則：A→C∧D B→E∧G目標(biāo)： C∨G 目標(biāo)節(jié)點 A A (A∨B) 規(guī)則 A→C∧D B→E∧G B B G G C C D E 事實 圖7.4 滿足終止條件的AND/OR圖 * * Note:對于A∨B，因為不知道A是真的還是B是真的，必須分情況加以證明，先假定A是真的去證明目標(biāo)，再假定B是真的去證明目標(biāo)。
只有當(dāng)這兩個證明都成功時，才能算做是證明了目標(biāo)。因此在圖7.4中，節(jié)點（A∨B）的兩個后繼用2-連接符號（A∨B）連接，這就是為什么在AND/OR圖中要使用k-連接符連接析取節(jié)點與其后繼的理由。 * * 四、 正向演繹系統(tǒng)的相容解圖 定義（替換的相容性集合、合一復(fù)合替換） 設(shè)有替換集合{σ1 ，σ2 ，……，σn}，每一σi 具有如下形式： σi = {ti1/vi1 ，……，tim(i)/vim(i)} 其中ti1，……，tim(i) 是項產(chǎn)生式系統(tǒng)b規(guī)則演繹，vi1，……，vim(i)是變量； 我們用這些替換構(gòu)造兩個表達式U1和U2如下： U1 ={v11，……，v1m(1)，……，vn1，……，vnm(n) } U2 ={t11，……，t1m(1)，……，tn1，……，tnm(n)）} 如果U1 和U2是可合一的，則替換集合{σ1 ，σ2 ，……產(chǎn)生式系統(tǒng)b規(guī)則演繹，σn}稱作是相容 的，否則稱作是不相容的， U1 和U2的最一般合一替換也叫做{σ1 ，σ2 ，……，σn}的合一復(fù)合替換。 * * 例：問如下{σ1,σ2}是否相容？若相容，給出合一復(fù)合替換。設(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)/y}} * * Note:只有對具有相容匹配替換的解圖才考慮它對應(yīng)的子句集是合理的. 例.事實:P(x)∨Q(x)規(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/x} {B/x} 圖7.7 一個具有不相容替換的AND/OR圖 * * 例. 事實~DOG(FIDO)∨(BARKS(FIDO)∧BITES(FIDO)) 規(guī)則：R1: ~DOG(x)→~(x)R2: BARKS(y)→NOISY(y)目標(biāo)： ~(z)∨NOISY(z) 目標(biāo)節(jié)點 ~(z) NOISY(z) ~(FIDO) ~DOG(x) ~DOG(FIDO) NOISY(FIDO) BARKS(y) BARKS(FIDO) BITES(FIDO) BARKS(FIDO)∧ BITES(FIDO) ~DOG(FIDO)∨(BARKS(FIDO)∧ BITES(FIDO)) {FIDO/z} {FIDO/x} R1 R2 {FIDO/y} {FIDO/z} 圖7.8 “”問題的AND/OR圖 相容解圖, 合一復(fù)合替換: {FIDO/x，F(xiàn)IDO/y，F(xiàn)IDO/z}， 把該替換用于解圖的葉節(jié) 點，得到： ~(FIDO)∨NOISY(FIDO) * * 正向演繹系統(tǒng)不完備 原因 目標(biāo)形式單一 改名不徹底，導(dǎo)致AND/OR圖的一般性比子句差，有些推理問題通過使用子句的歸結(jié)演繹能推出來，但用正向演繹系統(tǒng)推不出來。
