【正文】 81 82 演講完畢，謝謝觀看！ 。 80 歸結(jié)過程的控制策略 4． 輸入歸結(jié)策略 輸入歸結(jié)策略對(duì)參加歸結(jié)的子句有如下限制：參加歸結(jié)的兩個(gè)子句中 ， 必須至少有一個(gè)子句是初始子句集中的子句 。 但是 ， 這種歸結(jié)策略是不完備的 。 用單文字歸結(jié)策略時(shí) ， 歸結(jié)式將比親本子句含有較少的文字 。 79 歸結(jié)過程的控制策略 3． 單文字 （ 單元 ） 歸結(jié)策略 如果一個(gè)子句只包含一個(gè)文字 ， 則稱該子句為 單文字子句 或 單元子句 。 可從子句集中刪去那些被包孕的子句 。 ? 包孕刪除法 設(shè)有子句 C1和 C2， 如果存在一個(gè)置換 σ， 使得 C1σ?C2， 則稱 C1包孕于C2。 重言式是取值為永真的子句 。 77 歸結(jié)過程的控制策略 ? 重言式刪除法 如果一個(gè)子句中同時(shí)包含互補(bǔ)文字時(shí) ， 則稱該子句為 重言式 。 76 歸結(jié)過程的控制策略 歸結(jié)控制策略及其應(yīng)用舉例 1． 刪除策略 ? 純文字刪除法 如果文字 L出現(xiàn)在 S中 ， 而～ L不出現(xiàn)于 S中 ， 便說 L為 S的 純文字 。另一類是 限制策略 ， 限制策略主要是通過對(duì)參加歸結(jié)的子句進(jìn)行種種限制 ， 盡可能地減小歸結(jié)的盲目性 ， 使其盡快歸結(jié)出空子句 。 在解決上述問題的過程中 ， 人們研究出了許多 歸結(jié)策略 。 這是一種 盲目全面的歸結(jié) ， 其結(jié)果是產(chǎn)生大量的不必要的歸結(jié)式 ， 況且這種不必要的歸結(jié)式在下一輪歸結(jié)時(shí) ， 會(huì)以 冪次方的增長(zhǎng)速度快速增長(zhǎng) ， 從而產(chǎn)生 組合爆炸 。 73 歸結(jié)過程的控制策略 引入控制策略 1． 引入控制策略的原因 對(duì)子句集 S進(jìn)行歸結(jié)時(shí) ， 首先要從子句集中找出可進(jìn)行歸結(jié)的一對(duì)子句進(jìn)行歸結(jié) 。 72 歸結(jié)推理方法 第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié) （ 5） ～ Brother(John,y)∨ Father(David,y) （ 1） 與 （ 3） 歸結(jié) σ={David/z,John/x} （ 6） ～ Brother(John,Peter)∨ ANSWER(David) （ 4） 與 （ 5） 歸結(jié) σ={David/u,Peter/y} （ 7） ANSWER(David) （ 2） 與 （ 6） 歸結(jié) 第五步：得到了歸結(jié)式 ANSWER(David)， 答案即在其中 ， 所以u(píng)=David。 （ 3） Father(David,John)。 S2 ={～ Father(u,Peter)∨ ANSWER(u)} S= S1∪ S2 將 S中各子句列出如下： （ 1） ～ Brother(x,y)∨ ～ Father(z,x)∨ Father(z,y)。 設(shè) Peter的父親是 u， 則有： Father(u,Peter)。 Brother(John,Peter) F3： John的父親是 David。 F1 ：任何兄弟都有同一個(gè)父親 。 Brother(x,y)表示 x和 y是兄弟 。 68 歸結(jié)推理方法 例 任何兄弟都有同一個(gè)父親 ， John和 Peter是兄弟 ， 且John的父親是 David， 問 Peter的父親是誰 ？ 解 第一步：將已知條件用謂詞公式表示出來 ， 并化成子句集 ， 那么要先定義謂詞 。 67 歸結(jié)推理方法 （ 4） 對(duì)子句集 S應(yīng)用謂詞歸結(jié)原理進(jìn)行歸結(jié) ， 在歸結(jié)的過程中 ， 通過合一置換 ， 改變 ANSWER中的變?cè)?。 謂詞 ANSWER是一個(gè)專為求解問題而設(shè)置的謂詞 ， 其變量必須與問題公式的變量完全一致 。 66 歸結(jié)推理方法 應(yīng)用歸結(jié)原理進(jìn)行問題求解 下面是利用歸結(jié)原理求取問題答案的步驟： （ 1） 把已知前提條件用謂詞公式表示出來 ， 并化成相應(yīng)的子句集 ， 設(shè)該子句集的名字為 S1。 64 歸結(jié)推理方法 例 已知： A: (?x)((? y)(P(x,y)∧ Q(y))→ (? y)(R(y)∧ T(x,y))) B: ～ (? x)R(x)→ (? x)(? y)(P(x,y)→ ～ Q(y)) 求證： B是 A的邏輯結(jié)論 。 (3) 應(yīng)用歸結(jié)原理 ， 證明子句集 S的不可滿足性 ， 從而證明謂詞公式 G的不可滿足性 。 即若子句集是不可滿足的 ， 則必存在一個(gè)從該子句集到空子句的歸結(jié)推理過程；反之 ， 若從子句集到空子句存在一個(gè)歸結(jié)推理過程 ， 則該子句集必是不可滿足的 。 61 歸結(jié)推理方法 例 設(shè) C1=～ P(a)∨ Q(x)∨ R(x)， C2 =P(y)∨ ～ Q(b)， 求其二元?dú)w結(jié)式 。 （ 3） C1與 C2的因子 C2σ2的二元?dú)w結(jié)式 。 （ 1） C1與 C2的二元?dú)w結(jié)式 。 60 歸結(jié)推理方法 應(yīng)用因子的概念 ， 可對(duì)謂詞邏輯中的歸結(jié)原理定義如下 。 （ 2） 在求歸結(jié)式時(shí) ， 不能同時(shí)消去兩個(gè)互補(bǔ)文字對(duì) ， 消去兩個(gè)互補(bǔ)文字對(duì)所得的結(jié)果不是兩個(gè)親本子句的邏輯推論 。 59 歸結(jié)推理方法 在謂詞邏輯中 ， 對(duì)子句進(jìn)行歸結(jié)推理時(shí) ， 要注意以下幾個(gè)問題： （ 1） 若被歸結(jié)的子句 C1 和 C2中具有相同的變?cè)獣r(shí) ， 需要將其中一個(gè)子句的變?cè)?， 否則可能無法做合一置換 。 將 C iσ和 L iσ寫成集合 形式 ， 如 P(x)∨ ～Q(y)?{P(x),～ Q(y)}。 定義 設(shè) C1和 C2是兩個(gè)沒有相同變?cè)淖泳?， L1 和 L2分別是 C1 和 C2的文字 ， 如果 L1與～ L2有 mgu σ， 則把 C12 =( C1σ－ {L1σ})∪ (C2 σ－ {L2σ}) 稱作子句 C1 和 C2的一個(gè) 二元?dú)w結(jié)式 ， 而 L1 和 L2是被歸結(jié)的文字 。 (4) 置 S=S′， 轉(zhuǎn)步驟 （ 1） 。 (3) 檢查子句集 S′中是否有空子句 (NIL),若有則停止推理 。 即： S是不可滿足的 = S1是不可滿足的 歸結(jié)推理過程 子句集 S不可滿足性的推理過程如下： (1) 對(duì)子句集 S中的各子句間使用歸結(jié)推理規(guī)則 。 推論 設(shè) C1和 C2是子句集 S上的子句 ， C12是 C1和 C2的歸結(jié)式 。 1． 命題邏輯中的歸結(jié)原理 ? 歸結(jié)與歸結(jié)式 定義 設(shè) C1與 C2是子句集中的任意兩個(gè)子句 ， 如果 C1中的文字 L1與C2中的文字 L2互補(bǔ) ， 則從 C1和 C2中可以分別消去 L1和 L2， 并將二子句中余下的部分做析取構(gòu)成一個(gè)新的子句 C12， 稱這一過程為 歸結(jié) ， 所得到的子句 C12稱為 C1和 C2的 歸結(jié)式 ， 而稱 C1和 C2為 C12的 親本子句 。 另外 ， 由于 S中的子句是有限的 ， 而每個(gè)子句又由有限的文字組成 ， 因而 S的不可滿足的基例集也是有限的 。 這樣 ， 就至少會(huì)存在一個(gè) S中的某子句Ci的基例 Ci′ 為假 。 根據(jù)H域上的解釋與 D域上的解釋的對(duì)應(yīng)關(guān)系 ， 可知在 D域上一定存在一個(gè)解釋使 S不可滿足 ， 從而證明了子句集 S是不可滿足的 。 該定理稱為 Herbrand定理 ， 下面給出它的簡(jiǎn)要證明 。 這與 S在所有 H解釋下均為假矛盾 。 必要性 ：若 S在任一 H解釋 I*下均為假 ， 必然會(huì)使 S在 D域上的每一個(gè)解釋為假 。 定理 子句集 S不可滿足的充要條件是 S對(duì) H域上的一切解釋都為假 。 可以證明 ， 在給定域 D上的任一個(gè)解釋 I， 總能在 H域上構(gòu)造一個(gè)解釋 I*與之對(duì)應(yīng) ， 使得如果 D域上的解釋能滿足子句集S， 則在 H域的解釋 I*也能滿足 S（ 即若 S|I=T， 就有 S|I*=T） 。 對(duì)于子句 P(a)， 因?yàn)槠渲胁缓凶冊(cè)?， 所以它已是基子句 ， 而且 a?H， 所以它也是基例 。 定義 當(dāng)子句集 S中的某個(gè)子句 C中的所有變?cè)?hào)均以其 H域中的元素替換時(shí) ， 所得到的基子句稱作 C的一個(gè) 基例 。 解 此例中沒有個(gè)體常量 ， 任意指定一個(gè)常量 a作為個(gè)體常量；只有一個(gè)函數(shù) f(y)， 有： H0={a} H1={a,f(a)} H2={a,f(a),f(f(a))} …… H∞={a,f(