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