【正文】 ,b/y} （ 8） NIL（ 空子句 ） （ 5） 與 （ 7） 歸結(jié) 所以 B是 A的邏輯結(jié)論 。 66 歸結(jié)推理方法 應(yīng)用歸結(jié)原理進(jìn)行問題求解 下面是利用歸結(jié)原理求取問題答案的步驟： （ 1） 把已知前提條件用謂詞公式表示出來 ， 并化成相應(yīng)的子句集 ， 設(shè)該子句集的名字為 S1。 （ 2） 把待求解的問題也用謂詞公式表示出來 ， 然后將其否定 ， 并與一謂詞 ANSWER構(gòu)成析取式 。 謂詞 ANSWER是一個(gè)專為求解問題而設(shè)置的謂詞 ， 其變量必須與問題公式的變量完全一致 。 （ 3） 把問題公式與謂詞 ANSWER構(gòu)成的析取式化為子句集 ， 并把該子句集與 S1合并構(gòu)成子句集 S。 67 歸結(jié)推理方法 （ 4） 對(duì)子句集 S應(yīng)用謂詞歸結(jié)原理進(jìn)行歸結(jié) ， 在歸結(jié)的過程中 ， 通過合一置換 ， 改變 ANSWER中的變?cè)?。 （ 5） 如果得到歸結(jié)式 ANSWER ， 則問題的答案即在ANSWER謂詞中 。 68 歸結(jié)推理方法 例 任何兄弟都有同一個(gè)父親 ， John和 Peter是兄弟 ， 且John的父親是 David， 問 Peter的父親是誰(shuí) ？ 解 第一步：將已知條件用謂詞公式表示出來 ， 并化成子句集 ， 那么要先定義謂詞 。 （ 1） 定義謂詞： 設(shè) Father(x,y)表示 x是 y的父親 。 Brother(x,y)表示 x和 y是兄弟 。 69 歸結(jié)推理方法 （ 2） 將已知事實(shí)用謂詞公式表示出來 。 F1 ：任何兄弟都有同一個(gè)父親 。 (x)(y)(z)(Brother(x,y)∧ Father(z,x)→ Father(z,y)) F2： John和 Peter是兄弟 。 Brother(John,Peter) F3： John的父親是 David。 Father(David, John) （ 3） 將它們化成子句集得： S1={~Brother(x,y)∨ ~Father(z,x)∨ Father(z,y), Brother(John,Peter), Father(David,John)} 70 歸結(jié)推理方法 第二步：把問題用謂詞公式表示出來 ， 并將其否定與謂詞ANSWER作析取 。 設(shè) Peter的父親是 u， 則有： Father(u,Peter)。 將其否定與 ANSWER作析取 ， 得： G：～ Father(u,Peter)∨ ANSWER(u) 71 歸結(jié)推理方法 第三步：將上述公式 G化為子句集 S2， 并將 S1和 S2合并到 S。 S2 ={～ Father(u,Peter)∨ ANSWER(u)} S= S1∪ S2 將 S中各子句列出如下： （ 1） ～ Brother(x,y)∨ ～ Father(z,x)∨ Father(z,y)。 （ 2） Brother(John,Peter)。 （ 3） Father(David,John)。 （ 4） ～ Father(u,Peter)∨ ANSWER(u)。 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。 即 Peter的父親是 David。 73 歸結(jié)過程的控制策略 引入控制策略 1． 引入控制策略的原因 對(duì)子句集 S進(jìn)行歸結(jié)時(shí) ， 首先要從子句集中找出可進(jìn)行歸結(jié)的一對(duì)子句進(jìn)行歸結(jié) 。 由于事先 并不知道子句集中的哪兩個(gè)子句可以進(jìn)行歸結(jié) ， 也不知道通過對(duì)哪些子句的歸結(jié)可盡快得到空子句 ， 所以就必須對(duì)子句集中的所有子句逐一進(jìn)行比較 ， 以對(duì)所有可能歸結(jié)的子句對(duì)進(jìn)行歸結(jié) ， 并將歸結(jié)式加入 S中 ， 再做第二層這樣的歸結(jié) ?? ， 直到產(chǎn)生空子句 （ NIL） 為止 。 這是一種 盲目全面的歸結(jié) ， 其結(jié)果是產(chǎn)生大量的不必要的歸結(jié)式 ， 況且這種不必要的歸結(jié)式在下一輪歸結(jié)時(shí) ， 會(huì)以 冪次方的增長(zhǎng)速度快速增長(zhǎng) ， 從而產(chǎn)生 組合爆炸 。 74 歸結(jié)過程的控制策略 為了解決這一問題 ， 研究如何 選擇合適的子句進(jìn)行歸結(jié) ， 以避免多余的 、 不必要的歸結(jié)式的出現(xiàn) ， 已顯得非常重要 。 在解決上述問題的過程中 ， 人們研究出了許多 歸結(jié)策略 。 75 歸結(jié)過程的控制策略 2． 控制策略的分類 歸結(jié)策略大致可分為 兩大類 ：一類是 刪除策略 ， 刪除策略包括：純文字刪除法 、 重言式刪除法 、 包孕刪除法 。另一類是 限制策略 ， 限制策略主要是通過對(duì)參加歸結(jié)的子句進(jìn)行種種限制 ， 盡可能地減小歸結(jié)的盲目性 ， 使其盡快歸結(jié)出空子句 。 包括：線性歸結(jié)策略 、 單元 （ 單文字 ） 歸結(jié)策略 、 輸入歸結(jié)策略 、 支持集策略等 。 76 歸結(jié)過程的控制策略 歸結(jié)控制策略及其應(yīng)用舉例 1． 刪除策略 ? 純文字刪除法 如果文字 L出現(xiàn)在 S中 ， 而～ L不出現(xiàn)于 S中 ， 便說 L為 S的 純文字 。 例如 ， 設(shè)有子句集 ， S={T∨ Q∨ R,～ R,Q,R∨ ～ Q} 其中 T是純文字 ， 因此可將子句 T∨ Q∨ R刪去 ， 只用剩余的子句集進(jìn)行歸結(jié) ， 不會(huì)影響 S的不可滿足性 。 77 歸結(jié)過程的控制策略 ? 重言式刪除法 如果一個(gè)子句中同時(shí)包含互補(bǔ)文字時(shí) ， 則稱該子句為 重言式 。 例如 ， Q(x)∨ ～ Q(x)， P(x)∨ ～ Q(x)∨ ～ P(x)都是重言式 。 重言式是取值為永真的子句 。 可以從子句集中刪去重言式 。 ? 包孕刪除法 設(shè)有子句 C1和 C2， 如果存在一個(gè)置換 σ， 使得 C1σ?C2， 則稱 C1包孕于C2。 例如 ， P(x)∨ Q(a)包孕于 P(f(a))∨ Q(a)∨ R(y) ， σ={f(a)/x} T(x)∨ S(y)包孕于 T(b)∨ S(v)∨ R(x) ， σ={b/x， v/y}。 可從子句集中刪去那些被包孕的子句 。 78 歸結(jié)過程的控制策略 2． 線性歸結(jié)策略 線性歸結(jié)策略對(duì)參加歸結(jié)的子句提出如下限制：首先從子句集 S中先取一個(gè)稱作 頂子句 的子句 C0開始作歸結(jié)；其次是將歸結(jié)過程中所得到的歸結(jié)式 Ci立即同另一子句 Bi進(jìn)行歸結(jié) ， 得歸結(jié)式 Ci+1， 而 Bi是原子句集 S中的一個(gè)子句或是已經(jīng)歸結(jié)出的某個(gè)歸結(jié)式 Cj（ ji） 。 79 歸結(jié)過程的控制策略 3． 單文字 （ 單元 ） 歸結(jié)策略 如果一個(gè)子句只包含一個(gè)文字 ， 則稱該子句為 單文字子句 或 單元子句 。 如果在歸結(jié)過程中 ， 每次歸結(jié)都有一個(gè)子句是單文字子句 ， 則稱這種歸結(jié)就是 單文字歸結(jié) 。 用單文字歸結(jié)策略時(shí) ， 歸結(jié)式將比親本子句含有較少的文字 。 這有利于朝著空子句的方向前進(jìn) ， 因此它有較高的歸結(jié)效率 。 但是 ， 這種歸結(jié)策略是不完備的 。 因?yàn)榧僭O(shè)子句集 S是不可滿足的 ， 但其中卻不含有單文字子句 ， 則單元?dú)w結(jié)就無(wú)法進(jìn)行 。 80 歸結(jié)過程的控制策略 4． 輸入歸結(jié)策略 輸入歸結(jié)策略對(duì)參加歸結(jié)的子句有如下限制：參加歸結(jié)的兩個(gè)子句中 ， 必須至少有一個(gè)子句是初始子句集中的子句 。 5． 支持集策略 支持集策略對(duì)參加歸結(jié)的子句提出如下限制：每一次歸結(jié)時(shí) ， 參加歸結(jié)的兩個(gè)子句中至少應(yīng)有一個(gè)是由目標(biāo)公式的否定所得到的子句 ， 或者是它們的后裔 。 81 82 演講完畢，謝謝觀看！