【正文】 用與變換事實表達式同樣的過程，把目標公式化成與或形。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 56/101 規(guī)則演繹系統(tǒng) 逆向規(guī)則演繹系統(tǒng) 基于規(guī)則的逆向演繹系統(tǒng)，其操作過程與正向演繹系統(tǒng)相反，即為從目標到事實的操作過程，從 then到 if的推理過程。用文字集表示此目標公式，并設該集各元都為析取關系。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 55/101 規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng) 4. 作為終止條件的目標公式 應用 F規(guī)則的目的在于從某個事實公式和某個規(guī)則集出發(fā)來證明某個目標公式。這個子句集包括在 F(L)的子句形和 L=W的子句形間對 L進行所有可能的消解而得到的整集。 F(W)是用 W代替 F中的所有 L而得到的。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 54/101 規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng) 3. 與或圖的 F規(guī)則變換 將這類規(guī)則應用于與或圖進行推演。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 51/101 規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng) 例：有事實表達式 (彐 u)(? v)｛ Q(v, u)∧ ～ [(R(v)∨ P(v))∧ S(u, v)]｝ 把它化為 Q(v,A)∧ ｛［～ R(v)∧ ～ P(v)］ ∨ ～ S(A,v)｝ 對變量更名標準化，使得同一變量不出現(xiàn)在事實表達式的不同主要合取式中，得： Q(w,A)∧ ｛［～ R(v)∧ ～ P(v)］ ∨ ～ S(A,v)｝ 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 52/101 規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng) 2. 事實表達式的與或圖表示 將上例與或形的事實表達式用與或圖來表示 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) 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 53/101 規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng) 3. 與或圖的 F規(guī)則變換 這些規(guī)則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。具體變換步驟與前述化為子句形類似。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 50/101 規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng) 正向規(guī)則演繹系統(tǒng)是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從 if到 then的方向進行推理的。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng) (rule based deduction system)。有時把該斷言集稱為工作內(nèi)存。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 46/101 消解原理 消解反演求解過程 例 如果無論約翰 (John)到哪里去，菲多 (Fido)也就去那里，那么如果約翰在學校里，菲多在哪里呢 ? 事實公式集： S={(?x)[AT(JOHN, x)=AT(FIDO, x)], AT(JOHN, SCHOOL)} 目標公式 L： (彐 x)AT(FIDO,x) 首先證明 ~ L在邏輯上遵循公式集 S ~L=~{(彐 x)AT(FIDO,x)}= (?x){~AT(FIDO,x)} 其子句為 ~AT(FIDO,x) 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 47/101 消解原理 消解反演求解過程 例 的反演樹 ~AT(FIDO,x) ~ AT(JOHN, y) ∨ AT(FIDO, y)], ~ AT(JOHN, x) σ ={ x/y} NIL AT(JOHN, SCHOOL)} σ ={ SCHOOL/x} 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 48/101 消解原理 消解反演求解過程 例 ~AT(FIDO,x) ∨ AT(FIDO,y) ~ AT(JOHN, y) ∨ AT(FIDO, y)], ~ AT(JOHN, x )∨ AT(FIDO,x) σ ={ x/y} AT(FIDO,SCHOOL) AT(JOHN, SCHOOL)} σ ={ SCHOOL/x} 目標公式的重言式 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 49/101 規(guī)則演繹系統(tǒng) 規(guī)則演繹系統(tǒng)的定義： 基于規(guī)則的問題求解系統(tǒng)運用下述規(guī)則來建立： If→Then 其中， If部分可能由幾個 if組成，而 Then部分可能由一個或一個以上的 then組成。由于變換關系涉及到把由目標公式的否定產(chǎn)生的每個子句變換為一個重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨地遵循公理。 (3)用根部的子句作為一個回答語句。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 43/101 消解原理 消解反演求解過程 ~S(x,y)∨ ~M(y) ∨ I(f(x)) ~I(z) ~S(x,y)∨ ~M(y) σ ={ f(x)/z} ~M(b) S(a,b) σ ={ a/x, b/y} NIL M(b) 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 44/101 消解原理 消解反演求解過程 反演求解過程 步驟： (1)把由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定之否定的子句中去。39。={~L, S39。中去 ,即 S39。={~S(x,y))∨ ~M(y)∨ I(f(x)), ~S(x,y)∨ ~M(y)∨ E(x,f(x))} 其中， y=f(x)為 Skolem函數(shù)。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 40/101 消解原理 消解反演求解過程 反演求解舉例 例：儲蓄問題 前提：每個儲蓄錢的人都獲得利息?？梢宰C明，如果消解反演反復應用到不可滿足的子句集，那么最終將要產(chǎn)生空子句 NIL。如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 39/101 消解原理 消解反演求解過程 反演求解的正確性 設公式 L在邏輯上遵循公式集 S，那么按照定義滿足 S的每個解釋也滿足 L。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 32/101 消解原理 含有變量的消解式 例 ：考慮兩個子句： P[x,f(A)] ∨ P[x,f(y)] ∨ Q(y) ~p[z,f(A)] ∨ ~Q(z) 取 {li}= {P[x,f(A)]}， {mi}= {~p[z,f(A)]} 可得消解式 P[z,f(y)] ∨ Q(y) ∨ ~Q(z) σ ={z/x} 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 33/101 消解原理 含有變量的消解式 如果取 {li}= {Q(y) } ， {mi}= {~Q(z) 則可得消解式 P[x,f(A)] ∨ P[x,f(y)] ∨ ~p[y,f(A)] 進一步消解的消解式 P[y,f(y)] σ ={y/z} 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 34/101 消解原理 含有變量的消解式 幾個含有變量的子句使用消解的例子： B(x) ~B(x) ∨ C(x) C(x) 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 35/101 消解原理 含有變量的消解式 幾個含有變量的子句使用消解的例子： P(x) ∨ Q(x) ~Q[f(y) P[f(y)] σ ={f(y)/x} 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 36/101 消解原理 含有變量的消解式 幾個含有變量的子句使用消解的例子： P[(x,f(y)] ∨ Q(x) ∨ R[f(a),y] ~P[f(f(a)),z] ∨ R(z,w) Q(f(f(a) ∨ R[f(a),y] ∨ R(f(y),w) σ ={f(f(a)/x, f(y)/z} 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 37/101 消解原理 消解反演求解過程 1. 基本思想 把要解決的問題作為一個要證明的命題，其目標公式被否定并化成子句形，然后添加到命題公式集中去，把消解反演系統(tǒng)應用于聯(lián)合集，并推導出一個空子句 (NIL)，產(chǎn)生一個矛盾，這說明目標公式的否定式不成立，即有目標公式成立，定理得證，問題得到解決，與數(shù)學中反證法的思想十分相似。設 {li}是 {Li}的一個子集， {mi}是 {Mi}的一個子集，若 σ是 {li}和 {~mi}的最一般的合一，消解兩個子句 {Li}和 {Mi}，得到新子句 {{Li} {li}} σ ∨ {{Mi} {mi}} σ 就是這兩個子句的消解式。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 25/101 消解原理 消解推理規(guī)則 常用消解規(guī)則 (1) 假言推理 父輩子句 P ～ P∨ Q(即 P→Q) 消解式 Q 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 26/101 消解原理 消解推理規(guī)則 常用消解規(guī)則 (2) 合并 父輩子句 P∨ Q ～ P∨ Q 消解式 Q∨ Q=Q 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 27/101 消解原理 消解推理規(guī)則 常用消解規(guī)則 (3) 重言式 P ∨ Q ～ P ∨ ～ Q P ∨ Q ～ P ∨ ～ Q 消解式 Q ∨ ～ Q P ∨ ～ P 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 28/101 消解原理 消解推理規(guī)則 常用消解規(guī)則 (4) 空子句 (矛盾 ) ～ P P 消解式 NIL 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 29/101 消解原理 消解推理規(guī)則 常用消解規(guī)則 (5) 鏈式 (三段論 ) ～ P ∨ Q ～ Q ∨ R 消解式 ～ P ∨ R 合肥工業(yè)大學