【正文】 出現(xiàn)在公式的最前面 ，且它的轄域一直延伸到公式之末 ， 同時(shí)公式中不出現(xiàn)連接詞 → 及 ? ，這種形式的公式稱(chēng)作前束形范式 。 歸結(jié)推理方法 將謂詞公式 G化為 Skolem標(biāo)準(zhǔn)型的步驟如下： （ 1） 消去謂詞公式 G中的蘊(yùn)涵 （ → ） 和雙條件符號(hào)（ ? ） ， 以～ A∨ B代替 A→ B， 以 (A∧ B)∨ (～ A∧ ～ B)替換A?B。 這里分兩種情況 ， 一種情況是存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi) ， 此時(shí) ， 只要用一個(gè)新的個(gè)體常量替換該存在量詞約束的變?cè)?， 就可以消去存在量詞；另一種情況是 ， 存在量詞位于一個(gè)或多個(gè)全稱(chēng)量詞的轄域內(nèi) ， 這時(shí)需要用一個(gè) Skolem函數(shù)替換存在量詞而將其消去 。 歸結(jié)推理方法 2． 子句與子句集 定義 不含有任何連接詞的謂詞公式叫 原子公式 ， 簡(jiǎn)稱(chēng)原子 ， 而原子或原子的否定統(tǒng)稱(chēng) 文字 。 歸結(jié)推理方法 3． 不可滿(mǎn)足意義下的一致性 定理 設(shè)有謂詞公式 G， 而其相應(yīng)的子句集為 S，則 G是不可滿(mǎn)足的充分必要條件是 S是不可滿(mǎn)足的 。 稱(chēng)為公式 G或子句集 S的 Herbrand域 ， 簡(jiǎn)稱(chēng) H域 。i=0， 1， 2， … 。 定義 當(dāng)子句集 S中的某個(gè)子句 C中的所有變?cè)?hào)均以其 H域中的元素替換時(shí) ， 所得到的基子句稱(chēng)作 C的一個(gè) 基例 。 可以證明 ， 在給定域 D上的任一個(gè)解釋 I， 總能在 H域上構(gòu)造一個(gè)解釋 I*與之對(duì)應(yīng) ， 使得如果 D域上的解釋能滿(mǎn)足子句集S， 則在 H域的解釋 I*也能滿(mǎn)足 S（ 即若 S|I=T， 就有 S|I*=T） 。 必要性 ：若 S在任一 H解釋 I*下均為假 ， 必然會(huì)使 S在 D域上的每一個(gè)解釋為假 。 該定理稱(chēng)為 Herbrand定理 ， 下面給出它的簡(jiǎn)要證明 。 這樣 ， 就至少會(huì)存在一個(gè) S中的某子句Ci的基例 Ci′ 為假 。 1． 命題邏輯中的歸結(jié)原理 ? 歸結(jié)與歸結(jié)式 定義 設(shè) C1與 C2是子句集中的任意兩個(gè)子句 ， 如果 C1中的文字 L1與C2中的文字 L2互補(bǔ) ， 則從 C1和 C2中可以分別消去 L1和 L2， 并將二子句中余下的部分做析取構(gòu)成一個(gè)新的子句 C12， 稱(chēng)這一過(guò)程為 歸結(jié) ， 所得到的子句 C12稱(chēng)為 C1和 C2的 歸結(jié)式 ， 而稱(chēng) C1和 C2為 C12的 親本子句 。 即： S是不可滿(mǎn)足的 = S1是不可滿(mǎn)足的 歸結(jié)推理過(guò)程 子句集 S不可滿(mǎn)足性的推理過(guò)程如下： (1) 對(duì)子句集 S中的各子句間使用歸結(jié)推理規(guī)則 。 (4) 置 S=S′， 轉(zhuǎn)步驟 （ 1） 。 將 Ciσ和 Liσ寫(xiě)成集合 形式 ， 如 P(x)∨ ～ Q(y)改寫(xiě)為 {P(x),～ Q(y)}。 （ 2） 在求歸結(jié)式時(shí) ， 不能同時(shí)消去兩個(gè)互補(bǔ)文字對(duì) ， 消去兩個(gè)互補(bǔ)文字對(duì)所得的結(jié)果不是兩個(gè)親本子句的邏輯推論 。 （ 1） C1與 C2的二元?dú)w結(jié)式 。 歸結(jié)推理方法 例 設(shè) C1=～ P(a)∨ Q(x)∨ R(x)， C2 =P(y)∨ ～ Q(b)， 求其二元?dú)w結(jié)式 。 (3) 應(yīng)用歸結(jié)原理 ， 證明子句集 S的不可滿(mǎn)足性 ， 從而證明謂詞公式 G的不可滿(mǎn)足性 。 歸結(jié)推理方法 應(yīng)用歸結(jié)原理進(jìn)行問(wèn)題求解 下面是利用歸結(jié)原理求取問(wèn)題答案的步驟： （ 1） 把已知前提條件用謂詞公式表示出來(lái) ， 并化成相應(yīng)的子句集 ， 設(shè)該子句集的名字為 S1。 歸結(jié)推理方法 （ 4） 對(duì)子句集 S應(yīng)用謂詞歸結(jié)原理進(jìn)行歸結(jié) ， 在歸結(jié)的過(guò)程中 ， 通過(guò)合一置換 ， 改變 ANSWER中的變?cè)?。 Brother(x,y)表示 x和 y是兄弟 。 Brother(John,Peter) F3： John的父親是 David。 S2 ={～ Father(u,Peter)∨ ANSWER(u)} S= S1∪ S2 將 S中各子句列出如下： （ 1） ～ Brother(x,y)∨ ～ Father(z,x)∨ Father(z,y)。 歸結(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。 這是一種盲目全面的歸結(jié) ， 其結(jié)果是產(chǎn)生大量的不必要的歸結(jié)式 ， 況且這種不必要的歸結(jié)式在下一輪歸結(jié)時(shí) ， 會(huì)以?xún)绱畏降脑鲩L(zhǎng)速度快速增長(zhǎng) ， 從而產(chǎn)生組合爆炸 。另一類(lèi)是限制策略 ， 限制策略主要是通過(guò)對(duì)參加歸結(jié)的子句進(jìn)行種種限制 ， 盡可能地減小歸結(jié)的盲目性 ， 使其盡快歸結(jié)出空子句 。 歸結(jié)推理方法 ? 重言式刪除法 如果一個(gè)子句中同時(shí)包含互補(bǔ)文字時(shí) ， 則稱(chēng)該子句為 重言式 。 ? 包孕刪除法 設(shè)有子句 C1和 C2， 如果存在一個(gè)置換 σ， 使得 C1σ?C2， 則稱(chēng) C1包孕于C2。 歸結(jié)推理方法 3． 單文字 （ 單元 ） 歸結(jié)策略 如果一個(gè)子句只包含一個(gè)文字 ， 則稱(chēng)該子句為 單文字子句 或 單元子句 。 但是 ， 這種歸結(jié)策略是不完備的 。 演講完畢，謝謝觀(guān)看！ 。 歸結(jié)推理方法 4． 輸入歸結(jié)策略 輸入歸結(jié)策略對(duì)參加歸結(jié)的子句有如下限制：參加歸結(jié)的兩個(gè)子句中 ， 必須至少有一個(gè)子句是初始子句集中的子句 。 用單文字歸結(jié)策略時(shí) ， 歸結(jié)式將比親本子句含有較少的文字 。 可從子句集中刪去那些被包孕的子句 。 重言式是取值為永真的子句 。 歸結(jié)推理方法 歸結(jié)控制策略及其應(yīng)用舉例 1． 刪除策略 ? 純文字刪除法 如果文字 L出現(xiàn)在 S中 ， 而～ L不出現(xiàn)于 S中 ， 便說(shuō) L為 S的 純文字 。 在解決上述問(wèn)題的過(guò)程中 ， 人們研究出了許多歸結(jié)策略 。 歸結(jié)推理方法 歸結(jié)過(guò)程的控制策略 引入控制策略 1． 引入控制策略的原因 對(duì)子句集 S進(jìn)行歸結(jié)時(shí) ， 首先要從子句集中找出可進(jìn)行歸結(jié)的一對(duì)子句進(jìn)行歸結(jié) 。 （ 3） Father(David,John)。 設(shè) Peter的父親是 u， 則有： Father(u,Peter)。 F1 ：任何兄弟都有同一個(gè)父親 。 歸結(jié)推理方法 例 任何兄弟都有同一個(gè)父親 ， John和 Peter是兄弟 ， 且John的父親是 David， 問(wèn) Peter的父親是誰(shuí) ？ 解 第一步：將已知條件用謂詞公式表示出來(lái) ， 并化成子句集 ， 那么要先定義謂詞 。 謂詞 ANSWER是一個(gè)專(zhuān)為求解問(wèn)題而設(shè)置的謂詞 ， 其變量必須與問(wèn)題公式的變量完全一致 。 歸結(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é)論 。 即若子句集是不可滿(mǎn)足的 ， 則必存在一個(gè)從該子句集到空子句的歸結(jié)推理過(guò)程；反之 ， 若從子句集到空子句存在一個(gè)歸結(jié)推理過(guò)程 ， 則該子句集必是不可滿(mǎn)足的 。 （ 3） C1與 C2的因子 C2σ2的二元?dú)w結(jié)式 。 歸結(jié)推理方法 應(yīng)用因子的概念 ， 可對(duì)謂詞邏輯中的歸結(jié)原理定義如下 。 歸結(jié)推理方法 在謂詞邏輯中 ， 對(duì)子句進(jìn)行歸結(jié)推理時(shí) ， 要注意以下幾個(gè)問(wèn)題： （ 1） 若被歸結(jié)的子句 C1 和 C2中具有相同的變?cè)獣r(shí) ， 需要將其中一個(gè)子句的變?cè)?， 否則可能無(wú)法做合一置換 。 定義 設(shè) C1和 C2是兩個(gè)沒(méi)有相同變?cè)淖泳?， L1 和 L