【文章內(nèi)容簡介】 z,w ） 消解式 ： Q[f(f(a))]∨R[f(a),y]∨R[f(y),w] 置換 ： f(f(a))/x, f(y)/z 第四章 確定性推理 演繹推理 2/27/2023 33 消解反演 ? 消解反演 是利用 消解原理進行推理的過程。 ? 消解反演的推理過程 : ?給定公式集 S和目標(biāo)公式 L ?證明 公式 L的步驟如下： ?否定 L ，得～ L ?把～ L 添加到 S中去 ?把新產(chǎn)生的集合 {～ L ,S}化成子句集 ?應(yīng)用消解原理力圖推導(dǎo)出一個表示矛盾的空子句 第四章 確定性推理 演繹推理 2/27/2023 34 命題邏輯消解反演的例子 設(shè)公理集： P, (P?Q) ?R, (S?T) ?Q, T 求證： R 子句集： (1) P (2) ~P?~Q?R (3) ~S?Q (4) ~T?Q (5) T (6) ~R（目標(biāo)求反） 化子句集： (P?Q) ?R = ~(P?Q)?R = ~P?~Q?R (S?T) ?Q = ~ (S?T)?Q = (~S?~T)?Q = (~S?Q) ?(~T?Q) = {~S?Q, ~T?Q} 第四章 確定性推理 演繹推理 2/27/2023 35 命題邏輯消解反演的例子（續(xù)） 子句集： (1) P (2) ~P?~Q?R (3) ~S?Q (4) ~T?Q (5) T (6) ~R（目標(biāo)求反） 歸結(jié)： (7) ~P?~Q (2, 6) (8) ~Q (1, 7) (9) ~T (4, 8) (10) nil (5, 9) 第四章 確定性推理 演繹推理 2/27/2023 36 謂詞邏輯消解反演的例子 ? 例： 已知： If Fido goes wherever John goes and if John is at school, where is Fido ? (?x)[AT(John, x) ? AT(Fido, x)] AT(John, School) 求證： (?x)AT(Fido, x) 子句集： ~AT(John, y) ? AT(Fido, y) AT(John, School) ~AT(Fido, x) ( ~(?x)AT(Fido, x) = (? x) ~AT(Fido, x) ) 第四章 確定性推理 演繹推理 2/27/2023 37 ~AT(Fido, x) ~AT(John, y) ?AT(Fido, y) 子句集： ~AT(John, y) ? AT(Fido, y) AT(John, School) ~AT(Fido, x) ~AT(John, x) {x/y} AT(John, School) nil {School/x} AT(Fido, School) 謂詞邏輯消解反演的例子（續(xù)） 第四章 確定性推理 演繹推理 2/27/2023 38 基于消解原理的問答系統(tǒng) ? 消解原理主要用來解決證明的問題，但有時我們希望得到如 x=?時， W(x)為真的回答 ? 消解原理是將結(jié)論的否定作為前提進行歸結(jié)，而為了回答問題，用由結(jié)論的否定構(gòu)成的重言式作為前提進行歸結(jié)，得到的結(jié)論是問題的回答而不是空語句。這個過程稱為修改證明過程（或修改歸結(jié)過程）。 ? 下面以猴子摘香蕉問題為例來說明 第四章 確定性推理 演繹推理 2/27/2023 39 用消解原理解猴子摘香蕉問題 ? 為了把狀態(tài)空間的算符描述與謂詞演算結(jié)合起來，將狀態(tài)添到謂詞上； ? 將算符看成是把一種狀態(tài)映射成另一種狀態(tài)的函數(shù)； ? 問題簡化成沒有 goto()規(guī)則； c 第四章 確定性推理 演繹推理 2/27/2023 40 猴子摘香蕉問題的表示 問題可以描述如下 ： 1, ~ONBOX(s0) 2, (?x)(?s)(~ONBOX(s) ? AT(box, x, push(x, s))) 3, (?s)(ONBOX(climbbox(s))) 4, (?s)((ONBOX(s) ? AT(box, c, s)) ? HB(grasp(s))) 5, (?x)(?s)(AT(box, x, s) ? AT(box, x, climb(s))) 求解： (?s)HB(s) 第四章 確定性推理 演繹推理 2/27/2023 41 猴子摘香蕉問題的子句集 1, ~ON(s0) 2, ON(s1) ? AT(box, x1, push(x1, s1)) 3, ON(climb(s2)) 4, ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) 5, ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) 6, ~HB(s5) 第四章 確定性推理 演繹推理 2/27/2023 42 ~HB(s5) ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) ~ON(s3) ? ~AT(box, c, s3) {grasp(s3)/s5} ON(climb(s2)) {climb(s2)/s3} ~AT(box, c, climb(s2)) ~ON(s0) ON(s1) ? AT(box, x1, push(x1, s1)) {s0/s1} AT(box, x1, push(x1, s0)) ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) {x4/x1,push(x4,s0)/s4} AT(box, x4, climb(push(x4,s0))) NIL {c/x4,push(c,s0)/s2} HB(s5) ? HB(grasp(s3)) ? ? HB(grasp(climb(s2))) HB(grasp(climb(push(c,s0)))) 猴子摘香蕉問題的（修正）消解樹 第四章 確定性推理 演繹推理 2/27/2023 43 歸結(jié)反演的搜索策略 ? 歸結(jié)反演過程是“運用歸結(jié)規(guī)則直到產(chǎn)生空子句為止” ? 在對子句集進行歸結(jié)時，一個關(guān)鍵問題是如何選擇子句進行歸結(jié)。 ? 如果對任意一對可以歸結(jié)的子句都做歸結(jié)，這樣不僅消耗很多的時間，還會產(chǎn)生許多無用的歸結(jié)式，占用很多空間 ? 因此，需要研究有效的歸結(jié)控制（搜索）策略。 ? 歸結(jié)搜索策略一般包括：排序策略和限制策略 第四章 確定性推理 演繹推理 2/27/2023 44 排序策略 ? 歸結(jié)順序與狀態(tài)空間的擴展順序類似。 ? 狀態(tài)空間的搜索問題有多種搜索策略。 ? 把原始子句看成 0層歸結(jié)式。 ? （ i+1）層的歸結(jié)式是一個 i層歸結(jié)式和一個 j(j≤i)層歸結(jié)式進行歸結(jié)所得到的歸結(jié)式。 ? 寬度優(yōu)先： ? 先生成第 1層的所有歸結(jié)式．然后是第 2層所有的歸結(jié)式，依次類推，直到產(chǎn)生空子句或不能再進行歸結(jié)為止。 ? 深度優(yōu)先： ? 產(chǎn)生一個第 1層的歸結(jié)式，然后用第 1層的歸結(jié)式和第 0層的歸結(jié)式進行歸結(jié)，得到第 2層的歸結(jié)式，直到產(chǎn)生空子句結(jié)束，或者不能歸結(jié)，則回溯到其他的上層子句繼續(xù)歸結(jié) ? 單元優(yōu)先： ? 在歸結(jié)過程中優(yōu)先考慮僅由一個文字構(gòu)成的子句，這樣的子句稱為單元子句。 第四章 確定性推理 演繹推理