1、精選優(yōu)質(zhì)文檔-傾情為你奉上第三章歸結(jié)演繹推理摘要：本文對(duì)歸結(jié)對(duì)歸結(jié)演繹推理進(jìn)行了較為詳細(xì)的介紹，描述了歸結(jié)演繹推理的基本思路、使用步驟、并指明了其過程是完備的，還給出了運(yùn)用歸結(jié)原理進(jìn)行歸歸結(jié)的具體例子，最后簡單總結(jié)了其優(yōu)缺點(diǎn)。關(guān)鍵詞：歸結(jié)，演繹，推理1 知識(shí)背景人工智能是一門新興的學(xué)科，推理技術(shù)是實(shí)現(xiàn)人工智能的基本技術(shù)之一，其中自然演繹推理是基于常用邏輯等價(jià)式以及常用邏輯蘊(yùn)含式(統(tǒng)稱推理規(guī)則)的推理技術(shù)，即從已知事實(shí)出發(fā)，利用推理規(guī)則進(jìn)行推出結(jié)論的過程。這種推理過程與人類的思維過程極其相似，但其缺點(diǎn)是極易產(chǎn)生知識(shí)爆炸，推理過程中得到的中間結(jié)論按指數(shù)規(guī)律遞增，對(duì)于復(fù)雜問題的推理不利，在計(jì)算機(jī)上實(shí)

2、現(xiàn)起來存在諸多困難。而歸結(jié)演繹推理是基于歸結(jié)原理的在計(jì)算機(jī)上得到了較好實(shí)現(xiàn)的一種推理技術(shù)，是一種有效的機(jī)器推理方法。歸結(jié)原理的出現(xiàn), 使得自動(dòng)定理證明成為了可能，同時(shí)也使得人工智能技術(shù)向前邁進(jìn)了一大步。2 基本思路歸結(jié)演繹方法是一種基于魯濱遜（Robinson）歸結(jié)原理的機(jī)器推理技術(shù)【1】。魯濱遜歸結(jié)原理也稱作消解原理，是魯濱遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法”。在人工智能中基本上幾乎所有的問題都可以轉(zhuǎn)化為一個(gè)定理證明問題。而定理證明的實(shí)質(zhì)就是要從公式集出發(fā)推出結(jié)論G，即需要證明永真。要證明永真，若按定義來，需要證明在任何一個(gè)非空的個(gè)體域上都是永

3、真的。這將是非常困難的，甚至是不可實(shí)現(xiàn)的。為此人們進(jìn)行了大量的探索，后來發(fā)現(xiàn)可以采用反證法的思想，把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。即要證明永真，只要能夠證明是不可滿足的就可以了。在這一方面最有成效的的工作就是海伯倫理論和魯濱遜歸結(jié)原理。魯濱遜歸結(jié)原理使定理證明的機(jī)械化成為了現(xiàn)實(shí)。他們這些研究成果，在人工智能的發(fā)展史上都占有很重要的歷史地位。(1)我們首先需證明式成立，永真性的證明可以化為不可滿足性的證明。由命題邏輯的基本知識(shí)可得下表1-1：表1-1PGFFTTFTTTTFFFTTTT從上表可知：，從而永真性的證明可以化為的不可滿足性的證明。(2)要驗(yàn)證即不可滿足，只需要驗(yàn)證以上公

4、式中的任意一個(gè)子式不可滿足即可。我們定義不包含任意文字的子句為空子句，空子句是永假的，不可滿足的，一般記為NIL或。由子句和空子句組成的集合稱為子句集。在謂詞邏輯中，任何一個(gè)謂詞公式都可以通過應(yīng)用等價(jià)關(guān)系及推理規(guī)則化成相應(yīng)的子句集，且子句集無量詞約束、元素只是文字的析取、否定符只作用于單個(gè)文字，元素間默認(rèn)為和取。（3）歸結(jié)：我們定義命題P為文字，和P為互補(bǔ)文字。設(shè)C1和C2是子句集S中的任意兩個(gè)子句，如果子句C1中的文字L1與C2中的文字L2互補(bǔ)，則可從C1和C2中分別消去L1和L2，并將兩個(gè)子句余下的部分析取構(gòu)成一個(gè)新子句C12。我們稱這一過程為歸結(jié)，C12為C1和C2的歸結(jié)式，C1和C2為

5、C12的親本子句。即魯濱遜歸結(jié)原理的基本思路是：已知P，證明G，首先把欲證明的結(jié)論否定()，并加入前件知識(shí)構(gòu)成子句集S（），化子句集S；設(shè)法檢驗(yàn)子句集S中是否有空子句，若含有空子句，則S是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)運(yùn)算，對(duì)S中的子句進(jìn)行歸結(jié)至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。3 使用步驟運(yùn)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。已知F，證明G的歸結(jié)反演過程及步驟如下：（1）首先把欲證明的結(jié)論（目標(biāo)公式）G否定得到：（2）并把加入公式集F中，得F，；（3）把F，化成子句集S；（4）運(yùn)用歸結(jié)原理對(duì)S中的子句進(jìn)行歸結(jié)，并將歸結(jié)式加入S，反復(fù)進(jìn)行，直到歸結(jié)至導(dǎo)出空子句為止。4 完備性歸結(jié)原理

6、的歸結(jié)過程是完備的：因?yàn)樽泳浼疭是不可滿足的，充要條件是存在一個(gè)從S到空子句的歸結(jié)過程。我們知道：設(shè)C1和C2是子句集S中的任意兩個(gè)子句，C12是C1和C2的歸結(jié)式，若用C12代替C1和C2后，構(gòu)成新的子句集S1，則由S1的不可滿足性可以推出S的不可滿足性，即：S1不可滿足 S不可滿足。設(shè)C1和C2是子句集S中的任意兩個(gè)子句，C12是C1和C2的歸結(jié)式，若將C12添加到S中構(gòu)成新的子句集S2，則由S2的不可滿足性與S的不可滿足性等價(jià)，即：S2不可滿足 S不可滿足。進(jìn)而我們可以利用新子句集S1和S2不可滿足推出S不可滿足。從而只要能從S歸結(jié)出空子句，子句集S就是不可滿足的；子句集S是不可滿足的，

7、就一定存在一個(gè)從S到空子句的歸結(jié)過程。此歸結(jié)具有完備性。5 舉例說明在謂詞邏輯下求兩個(gè)子句的歸結(jié)式，和命題邏輯一樣是消互補(bǔ)對(duì)，但需考慮變量的合一與置換。簡單討論一階謂詞邏輯描述下的歸結(jié)推理方法，謂詞邏輯的歸結(jié)過程與命題邏輯的歸結(jié)過程相比，其基本步驟相同，但每步的處理對(duì)象不同。謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集，必要時(shí)在得到歸結(jié)式前要進(jìn)行置換和合一。 具體的謂詞邏輯歸結(jié)過程如下：(1)寫出謂詞關(guān)系公式 (2)用反演法寫出謂詞表達(dá)式(3)化為Skolem標(biāo)準(zhǔn)形 (4)求取子句集S (5)對(duì)S中可歸結(jié)的子句做歸結(jié)(6)歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程 (7)得到空子句(8)命題得證例如用歸結(jié)原

8、理求解“樂學(xué)生”問題：假設(shè)任何通過計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。求證：張是快樂的。 解：先將問題用謂詞表示如下：R1:"任何通過計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂的" (x)(Pass(x, computer)Win(x, prize)Happy(x)R2:"任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試" (x)(y)(Study(x)Lucky(x)Pass(x, y)R3:"張不肯學(xué)習(xí)但他是幸運(yùn)的" Study(zhang)Lucky(zhang)R4:

9、"任何幸運(yùn)的人都能獲獎(jiǎng)" (x)(Luck(x)Win(x,prize)結(jié)論"張是快樂的"的否定 Happy(zhang)將上述謂詞公式轉(zhuǎn)化為子句集并進(jìn)行歸結(jié)如下：首先將每一個(gè)表示邏輯條件的謂詞子句轉(zhuǎn)換為子句集可以接受的Skolem標(biāo)準(zhǔn)形。由R1及邏輯轉(zhuǎn)換公式PWH =(PW)H ,可得(1)Pass(x, computer)Win(x, prize)Happy(x)由R2可得 (2) Study(y) Pass(y,z) (3) Lucky(u) Pass(u,v)由R3可得 (4) Study(zhang) (5) Lucky(zhang) 由R4可

10、得 (6) Lucky(w) Win(w，prize) 由結(jié)論可得 (7) Happy(zhang) 結(jié)論的否定 根據(jù)以上7條子句，歸結(jié)如下： (8) Pass(w, computer) Happy(w) Luck(w) (1)，(6)歸結(jié)，w/x (9) Pass(zhang, computer) Lucky(zhang) (8)，(7)歸結(jié)，zhang/w (10) Pass(zhang, computer) (9)，(5)歸結(jié) (11) Lucky(zhang) (10),(3)歸結(jié),zhang/u, computer/v (12) (11),(5)歸結(jié) 6 優(yōu)缺點(diǎn)總結(jié)定理證明的實(shí)質(zhì)就是

11、要對(duì)給出的（已知的）前提和結(jié)論，證明此前提推導(dǎo)出該結(jié)論這一事實(shí)是永恒的真理。這是非常困難的，幾乎是不可實(shí)現(xiàn)的。要證明在一個(gè)論域上一個(gè)事件是永真的，就要證明在該域中的每一個(gè)點(diǎn)上該事實(shí)都成立。很顯然，論域是不可數(shù)時(shí)，該問題不可能解決。即使可數(shù)，如果該輪域是無限的，問題也無法簡單地解決。海伯倫采用了反證法的思想，將永真性的證明問題轉(zhuǎn)化成為不可滿足性的證明問題。海伯倫理論為自動(dòng)定理證明奠定了理論基礎(chǔ)，而魯濱遜的歸結(jié)原理使得自動(dòng)定理證明得以實(shí)現(xiàn)。因此，歸結(jié)推理方法在人工智能推理方法中有著很重要的歷史地位。從某種意義上講大部分人工智能問題都可以轉(zhuǎn)化為一個(gè)定理證明問題。歸結(jié)原理使定理證明的機(jī)械化成為了現(xiàn)實(shí)。當(dāng)子句集很大時(shí)，歸結(jié)過程會(huì)很復(fù)雜，一般的歸結(jié)過程會(huì)很盲目，產(chǎn)生許多無用的歸結(jié)式，更嚴(yán)重的是產(chǎn)生組合爆炸問題，所以還必須使用歸結(jié)策略來進(jìn)行控制，比如說刪除策略或限制策略。參考文獻(xiàn)：1 尚富華.李軍.人工智能及其運(yùn)用M.北京:石油工業(yè)出版社,2005.