【正文】 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 60 對與或圖作變換例 ? 例： 事實： ((P ? Q) ? R) ? (S ? (T ? U)) 規(guī)則： S ? (X ? Y) ? Z ? 事實的 與或圖與 規(guī)則對其進行的變換過程如下圖： 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 61 ((P ? Q) ? R) ? (S ? (T ? U)) (P ? Q) ? R P ? Q R P Q S ? (T ? U) S T ? U T U S X ? Y Z X Y P? Q? S P? Q? T? U S? R R? T? U P? Q? X? Z P? Q? Y? Z R? X? Z R? Y? Z 規(guī)則的子句： S ? (X ? Y) ? Z = ~S?(X ? Y) ? Z = ~S ? X ? Z ~S ? Y ? Z 結論：加入規(guī)則后得到的解圖，是事實與規(guī)則對應子句的歸結式 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 62 目標公式作為終止條件 ? 應用規(guī)則進行推理的目的是為了證明某個目標公式 ? 在正向推理系統(tǒng)中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式 ? 在與或圖的產生過程中，目標文字或規(guī)則與圖中文字節(jié)點匹配時，產生新后裔節(jié)點，標記為匹配的目標文字。當產生的圖包含有終止在目標節(jié)點上的一個解圖時，系統(tǒng)便成功地結束。 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 63 例： 事實： A ? B 規(guī)則集： A ? C ? D B ? E ? G 目標公式： C ? G A? B A A C D B B E G C G 目標 目標公式作為終止條件例一 匹配弧 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 64 目標公式作為終止條件例二 例：事實： P(x, y) ? (Q(x, A) ? R(B, y)) 規(guī)則集 ： P(A, B) ? (S(A) ? X(B)) Q(B, A) ? U(A) R(B, B) ? V(B) 目標 ： S(A) ? X(B) ?(U(A) ? V(B)) 事實的 與或圖與 規(guī)則對其進行的變換過程如下圖： 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 65 P(x, y) ? (Q(x, A) ? R(B, y)) P(x, y) Q(x, A) ? R(B, y) Q(x, A) R(B, y) P(A, B) {A/x,B/y} S(A) X(B) Q(B, A) {B/x} U(A) R(B, B) {B/y} V(B) 例二的與或圖 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 66 基于規(guī)則的逆向演繹推理 ? 將目標表達式表示成與或形 ? 將規(guī)則限制為下列形式： W ? L 其中， L是單文字， W是與或形，變量受全稱量詞約束 如 規(guī)則 形為： W? L1 ?L2，則變換為： W? L1 和 W? L2 ? 事實表達式均限制為文字合取形，形如： ? F1 ?F2 ? … ? Fn Fi(i＝ 1,2…n) 為單文字．且都可單獨起作用 ? 推理過程：從目標公式的與／或樹出發(fā)，不斷用規(guī)則的后件和與／或樹的葉節(jié)點進行匹配，并將匹配成功的規(guī)則用匹配弧加入與／或樹中，直到產生某個終止在事實節(jié)點上的解圖為止。 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 67 化目標表達式為與或形 ? 消去蘊涵符號： ～ P∨Q 取代 P→Q ? 減少否定符號的管轄域 ? 對變量標準化 ? 消去全稱量詞 ： 引入 Skolem函數 ? 消去存在量詞 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 68 目標表達式化為與或形舉例 例： (?z) (?x)(?y){[(P(x) ?Q(x)) ?R(y)] ?U(z)} 前三步： 1, 消蘊涵符 2, 移動否定符 3, 變量標準化 等 3步與正向推理中化事實的表達式方法相同 4, 消全稱量詞 (skolem化 (對偶形 ) ） 原則：對于一個受全稱量詞約束的變量，如果他受存在量詞約束，則該變量用一個函數代替。 (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} = (?z) ) (?y){[(~P(f(z)) ?~Q(f(z))) ? R(y)] ?U(z)} 5, 消存在量 詞 [(~ P(f(z))?~Q(f(z))) ? R(y)] ?U(z) 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 69 目標表達式的與或圖表示 ? 用 K連線表示合取，無連線表示析取 例： Q(w, A) ? ((~R(v) ?~P(v)) ? ~S(A, v)) Q(w, A) ?((~R(v) ? ~P(v)) ? ~S(A, v)) Q(w, A) (~R(v) ? ~P(v)) ? ~S(A, v) ~R(v) ? ~P(v) ~S(A, v) ~R(v) ~P(v) 讀葉節(jié)點的與或關系，得子句： Q(w, A) ~R(v)?~S(A,v) ~P(v)?~S(A,v) 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 70 逆向演繹 例 ： 事實： D(F) ~B(F) W(F) M(N) 規(guī)則： R1: (W(x1) ? D(x1)) ? F(x1) R2: (F(x2) ? ~B(x2)) ? ~A(y2, x2) R3: D(X3) ? A(x3) R4: C(x4) ? A(x4) R5: M(x5) ? C(x5) 目標： C(x) ? D(y) ? ~A(x, y) C(x) ? D(y) ? ~A(x, y) C(x) D(y) ~A(x, y) C(x5) {x/x5} M(x) R5 M(N) {N/x} D(F) {F/y} ~A(y2, x2) {x/y2,y/x2} F(y) ~B(y) R2 ~B(F) {F/y} F(x1) {y/x1} W(y) D(y) R1 W(F) {F/y} D(F) {F/y} 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 71 正、逆向系統(tǒng)對比 ? 事實表達式任意形 ? 規(guī)則形式： 單文字 ? W ? 目標公式為文字析取 ? 對事實、規(guī)則消存在量詞，Skolem化 ? 消目標的全稱量詞，Skolem化 (對偶形 ) ? 事實表達式與或樹 ，“ ?”對“與”，“ ?”對應“或” ? 從事實出發(fā)，正向應用規(guī)則 ? 以目標為結束的一致解圖 ? 事實表達式是合取形 ? 規(guī)則形式： L ? 單文字 ? 目標公式任意形 ? 對事實、規(guī)則消存在量詞，Skolem化 ? 消目標的全稱量詞，Skolem化 (對偶形 ) ? 目標公式的與或樹 ，“ ?”對“與”，“ ?”對應“或” ? 從目標出發(fā)，逆向應用規(guī)則 ? 以事實為結束的一致解圖 第四章 確定性推理 規(guī)則的 演繹推理 2/27/2023 72 The End 第四章 確定性推理 2/27/2023 73 演講完畢，謝謝觀看！