【正文】 ○﹁ Q ○ P ∨ Q ○ Q ○ □73 動態(tài)支持集消解 ? 判斷 S―S’ 是否可滿足，需要花費時間，所以要尋找更好的策略。支持集消解的進一步改進就得到了動態(tài)支持集消解 ? [定義 ]動態(tài)支持集消解：設 S是子句集， S0=S，Sn=Sn1 ∪ {Cn}，其中 Cn是 Sn中兩個子句的消解式，如果有一種根據(jù)子句的語法結構劃分子句集的統(tǒng)一方法，使每個 Sn都劃分為 Sn1和 Sn2兩部分，且在消解時限定雙方不能都取自 Sn1 ，則稱 Sn2是 Sn的一個動態(tài)支持集，此消解稱為動態(tài)支持集消解。同時亦定義動態(tài)支持集推導、動態(tài)支持集否證。 第 4章 消解法 74 常用動態(tài)支持集消解策略 ? 常用的動態(tài)支持集消解有下列幾種策略： (1)線性消解 (2)輸入消解 (3)單元消解 ? [線性消解定義 ]在動態(tài)支持集消解定義中令Sn2={Cn }，則此策略稱為線性消解策略。 Cn稱為消解時的中心子句，另一方稱為邊子句 ? 線性消解是完備的 第 4章 消解法 75 線性消解 ? 注意：在現(xiàn)行消解過程中 ， 初始中心句的選取很重要 ， 不能任意選擇 。 ? 例 2： S={ P∨ Q,﹁ P∨ Q, P∨ ﹁ Q, ﹁ P∨ ﹁ Q }，其線性消解過程可由下圖說明 。 ★ 第 4章 消解法 S2 ○ P ∨ Q ○ ﹁ P ∨ Q Q ○ ○ P ∨﹁ Q P ○ ○ ﹁ P ∨﹁ Q ﹁ Q ○ ○ Q □ ○76 輸入消解 ? [輸入消解定義 ]在動態(tài)支持集消解定義中令Sn2=S，則此策略稱為輸入消解策略。因為每次消解必須有原子句集 S中的子句參加 (即輸入子句 )由此得名 ? 例 3 ： S={﹁ P, P∨ ﹁ Q, Q∨ ﹁ R, R }， 其消解過程如圖所示 。 ★ 第 4章 消解法 S2 ﹁ P ○ ○ P ∨﹁ Q ﹁ Q ○ ○ Q ∨﹁ R ﹁ R ○ ○ R □ ○77 單元消解 ? [單元消解定義 ]在動態(tài)支持集消解定義中令Sn2={Sn 中所有單子句和單因子 }，則此策略稱為單元消解策略 (也叫單項消解 ) / 這樣，每次參加消解的一方總有一個是單項 ? 例 4： S={P∨ Q,﹁ P∨ R,﹁ Q∨ R,﹁ R}， 其消解過程如圖所示 。 ★ 第 4章 消解法 S2 ﹁ R ○ ○﹁ Q ∨ R ﹁ Q ○ ○ P ∨ Q P ○ ○﹁ P ∨ R R ○ ○﹁ R □ ○78 輸入消解和單元消解的關系 ? 可以證明如下定理：輸入消解和單元消解是等價的，即一個子句集 S可以用輸入消解來否證，當且僅當 S可以用單元消解來否證。 ? 輸入消解和單元消解都不是完備的。但是，如果把子句集加以限制，就可以使這兩種消解成為完備的。 ? 只含 Horn子句的集合稱為 Horn子句集。 ? [定理 ]輸入消解和單元消解對于 Horn子句集都是完備的 第 4章 消解法 79 有序消解策略 ? 有序消解策略：對子句中被消解的文字加以限制 (第 2種策略 )，通常要對子句中的文字進行排序。這就是有序消解策略。 ? 有序消解一般和其他消解策略連用，以提高效率。這里只介紹一種有序謂詞消解和簡單語義消解連用的策略 第 4章 消解法 80 有關定義 (1) ? [兩分法消解定義 ]設 S是子句集 ， S0=S， Sn=Sn1{Cn}， 其中 Cn是 Sn中兩個子句的消解式 ， 如果有一種統(tǒng)一劃分子句集的方法 ， 使每個 Sn都劃分為 Sn1和 Sn2兩部分 ， 且在消解時限定雙方從Sn1和 Sn2中各出一個父子句 ， 則此消解稱為兩分法消解 。 ? [簡單語義消解定義 ]設 HI是子句集 S的一個 H解釋， Sn(n=0, 1, …) 定義如前， Sn1和 Sn2分別為 HI解釋中取真值和假值的子句集。按此規(guī)定劃分的兩分法消解稱為簡單語義消解 (因為由 HI解釋控制 ) 第 4章 消解法 81 有關定義 (2) ? 簡單語義消解是不完備的 ? [有序謂詞消解定義 ]把子句集 S中出現(xiàn)的謂詞按照名字排成全序 (即按字母排序 )，并規(guī)定在消解時只有父子句中排序最大 (即按字母序最前 )的謂詞文字被消解，則此策略稱為有序謂詞消解。 ? [有序謂詞語義消解定義 ]如果規(guī)定每次消解時必須同時滿足有序謂詞消解和簡單語義消解的定義，且規(guī)定中的子句 (HI解釋取假值 )以排序最大的謂詞進行消解，則此消解稱為有序謂詞語義消解 第 4章 消解法 82 有序謂詞語義消解例子 ? 例 5：設 S={P, Q,﹁ P∨﹁ Q∨ R, M,﹁ R∨ ﹁M∨ ﹁ P}， 規(guī)定 HI解釋為使正原子為真 ， 則 ? S01 ={ P, Q,﹁ P∨ ﹁Q∨ R, M }， S02 ={﹁R∨ ﹁ M∨ ﹁ P } ? 謂詞排序為 MPQR ? 其消解過程如圖所示 第 4章 消解法 S1 S2 ○ M ○﹁ R ∨﹁ M ∨﹁ P ○ P ○﹁ R ∨﹁ P ○﹁ P ∨﹁ Q ∨ R ○﹁ R ○ P ○﹁ P ∨﹁ Q ○ Q ○﹁ Q ○□83 消解法舉例 ? 例 “ 快樂學生 ” 問題 ? 假設：任何通過計算機考試并獲獎的人都是快樂的 ， 任何肯學習或幸運的人都可以通過所有考試 ， 張不肯學習但他是幸運的 ， 任何幸運的人都能獲獎 。 求證：張是快樂的 。 第 4章 消解法 84 第 4章 消解法 解 ：先將問題謂詞表示如下： “任何通過計算機考試并獲獎的人都是快樂的” ?( )(x ),( c o m p u te rxP a ss ))()),( xH a p p yp rizexW in ?? “任何肯學習或幸運的人 都可以通過所有考試” ?( ?)(x )()( xS tu d yy ? )),()() yxP a ssxLu c ky ? “張不肯學習但他是幸運的” ￢ )( zh a n gS tu sy )( zh a n gLu c ky? “張不肯學習但他是幸運的” ?( )(x L uck y )( x )),( p rizexW in? 結論“張是快樂的”的否定 ￢ )( zh a n gH a p p y 85 第 4章 消解法 將上述謂詞公式轉化為子句集如下： (1) ￢ ?),( c o m p u terxP a ss ￢ )(),( xHa p p yp r izexW in ? (2) ￢ ),()( zyP a ssyS tu d y ? (3) ￢ ),()( vuP a ssuLu c ky ? (4) ￢ )( zh a n gS tu d y (5) )( zh a n gLu c ky (6) ￢ ),()( p r izewW inwLu c k y ? (7) ￢ )( zh a n gH a p p y ( 本子句為結論的否定 ) 按謂詞邏輯的歸結原理對此子句進行歸結，其歸結反演過程如 下 圖 所示。由于歸結出了子句，這就證明了張是快樂的。 86 第 4章 消解法 {w/x} {zhang /w} {zhang /u,c ompu ter/ v} “快樂學生”問題的歸結反演樹 ￢?),( c om put e rxP as s￢)(),( xH appypr i z exW i n ? )( z h a n gL uc k y ￢),()( vuP as suL uc k y ? N I L ￢?),( c om put e rz hangP as s￢)( z h a n gL uc k y )( z h a n gL uc k y ￢),( c om pu t e rz ha ngP as s ￢)( z han gH ap py ￢?),( c om put e rwP as s ?)( wH appy￢)( wL u c k y ),()( pr i z ewW i nwL uc k y ? ￢)( z h a n gL uc k y 用的是什么消解策略？ 87 參考書目 ? Stuart Russell / Peter Norvig: AIMA 第 9章 ? 陸汝鈐 編著 : 人工智能 (下冊 ) 第 17章 ? 石純一、黃昌寧、王家 [廣欽 ]，人工智能原理，清華大學出版社， 1993年 10月第 1版 ? 田盛豐、黃厚寬，人工智能與知識工程，中國鐵道出版社， 1999年 8月第 1版 ,第 5章 第 4章 消解法 88 演講完畢，謝謝觀看！