人工智能經(jīng)典邏輯推理

1、人工智能經(jīng)典邏輯推理第三章經(jīng)典邏輯推理3.1 根本概念3.2 自然演繹推理3.3 歸結(jié)演繹推理3.4 與或形演繹推理3.1 根本概念3.1.1 什么是推理所謂推理就是按某種策略由判斷推出另一個(gè)判斷的思維過(guò)程。在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。3.1.2 推理方式及其分類1. 演繹推理、歸納推理、默認(rèn)推理演繹推理：從一般到特殊。例如三段論。歸納推理：從個(gè)體到一般。默認(rèn)推理：缺省推理，在知識(shí)不完全情況下假設(shè)某些條件已經(jīng)具備所進(jìn)展的推理。2. 確定性、不確定性推理3.1.2 推理方式及其分類3. 單調(diào)推理、非單調(diào)推理推出的結(jié)論是否單調(diào)增加 5. 基于知識(shí)的推理專家系統(tǒng) 、統(tǒng)計(jì)推理、直覺(jué)推

2、理常識(shí)性推理4. 啟發(fā)式、非啟發(fā)式推理 所謂啟發(fā)性知識(shí)是指與問(wèn)題有關(guān)且能加快推理進(jìn)程、求得問(wèn)題最優(yōu)解的知識(shí)。3.1.3 推理的控制策略推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制策略。1. 正向推理數(shù)據(jù)驅(qū)動(dòng)推理根本思想：從用戶提供的初始事實(shí)出發(fā)，在知識(shí)庫(kù)KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用的知識(shí)集KS，然后按某種沖突消解策略從KS中選出一條知識(shí)進(jìn)展推理，并將推出的新事實(shí)參加到數(shù)據(jù)庫(kù)DB中，作為下一步推理的事實(shí)。在此之后，再在知識(shí)庫(kù)中選取可適用的知識(shí)進(jìn)展推理。如此重復(fù)進(jìn)展這一過(guò)程，直到求得所要求的解。正向推理示意圖2 逆向推理根本思想 首先選定一個(gè)假設(shè)目的，然后尋找

3、支持該假設(shè)的證據(jù)，假設(shè)所需的證據(jù)都能找到，那么說(shuō)明原假設(shè)是成立的；假設(shè)找不到所需要的證據(jù)，那么說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的假設(shè)。逆向推理示意圖 動(dòng)物識(shí)別的例子(正向推理)事實(shí)：一動(dòng)物有毛，吃草，黑條紋R1：動(dòng)物有毛 哺乳類 R2：動(dòng)物產(chǎn)奶 哺乳類 R3：哺乳類 吃肉 食肉類 R4：哺乳類 吃草 有蹄類 R5：食肉類 黃褐色 有斑點(diǎn) 獵狗 R6：食肉類 黃褐色 黑條紋 虎 R7：有蹄類 長(zhǎng)脖 長(zhǎng)頸鹿 R8：有蹄類 黑條紋 斑馬3.1.3 推理的控制策略3. 混合推理先正向推理后逆向推理先逆向推理后正向推理4. 雙向推理正向推理與逆向推理同時(shí)進(jìn)展，且在推理過(guò)程中的某一步上“碰頭。5. 求解策

4、略只求一個(gè)解，還是求所有解以及最優(yōu)解。6. 限制策略限制搜索的深度、寬度、時(shí)間、空間等等。形式匹配是指對(duì)兩個(gè)知識(shí)形式(例如兩個(gè)謂詞公式、框架片斷、語(yǔ)義網(wǎng)絡(luò)片斷)進(jìn)展比較，檢查這兩個(gè)知識(shí)形式是否完全一致或者近似一致。3.1.4 形式匹配形式匹配可分為確定性匹配與不確定性匹配。3.1.4 形式匹配確定性匹配是指兩個(gè)知識(shí)形式完全一致，或者經(jīng)過(guò)變量代換后變得完全一致。 知識(shí)：IF father(x,y) and man(y) THEN son(y,x) 事實(shí)：father(李四，李小四) and man(李小四)不確定性匹配是指兩個(gè)知識(shí)形式不完全一致，但是它們的相似程度又在規(guī)定的限度內(nèi)。變量代換置換定

5、義 代換是一個(gè)形如t1/x1,t2/x2,tn/xn的有限集合。 其中t1,t2,tn是項(xiàng)常量、變量、函數(shù)； x1,x2,xn是某一公式中互不一樣的變?cè)?ti/xi表示用ti代換xi 不允許ti與xi一樣，也不允許變?cè)獂i循環(huán)地出如今另一個(gè)tj中。例如：a/x,f(b)/y,w/z是一個(gè)代換g(y)/x,f(x)/y不是代換g(a)/x,f(x)/y是代換令= t1/x1,t2/x2,tn/xn為一個(gè)代換，F(xiàn)為表達(dá)式，那么F表示對(duì)F用ti代換xi后得到的表達(dá)式。F稱為F的特例。 規(guī)那么: IF father(x,y) and man(y) THEN son(y,x)事實(shí): father(李四

6、，李小四) and man(李小四) F=father(x,y) man(y) = 李四/X,李小四/Y F= father(李四，李小四) man(李小四) 結(jié)論: son(李小四,李四)代換的復(fù)合定義 設(shè)= t1/x1,t2/x2,tn/xn= u1/y1,u2/y2,um/ym是兩個(gè)代換，那么這兩個(gè)代換的復(fù)合也是一個(gè)代換，它是從t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym中刪去如下兩種元素：ti/xi當(dāng)ti=xiui/yi當(dāng)yix1,x2,xn后剩下的元素所構(gòu)成的集合，記為 。注 (1) ti表示對(duì)ti運(yùn)用進(jìn)展代換。 (2)就是對(duì)一個(gè)公式F先運(yùn)用進(jìn)展代換，然后再

7、運(yùn)用進(jìn)展代換：F =F 代換復(fù)合的例子例如，設(shè)有代換= f(y)/x,z/y= a/x,b/y,y/z那么=? =f(y)/x, z/y, a/x, b/y, y/z =f(b)/x, y/y, a/x, b/y, y/z =f(b)/x,y/z公式集的合一定義 設(shè)有公式集F=F1,F2,Fn，假設(shè)存在一個(gè)代換使得F1=F2=Fn那么稱為公式集F的一個(gè)合一，且稱F1,F2,Fn是可合一的。例如，設(shè)有公式集F=P(x,y,f(y),P(a,g(x),z)那么下式是它的一個(gè)合一：=a/x,g(a)/y,f(g(a)/z一個(gè)公式集的合一一般不唯一。 最一般合一定義 設(shè)是公式集F的一個(gè)合一，假設(shè)對(duì)任一

8、個(gè)合一都存在一個(gè)代換，使得=那么稱是一個(gè)最一般的合一。最一般合一是唯一的。求取最一般合一差異集：兩個(gè)公式中一樣位置處不同符號(hào)的集合。例如：F=F1:P(x,y,z), F2:P(x,f(a),h(b)那么D1=y,f(a), D2=z,h(b)求取最一般合一的算法：令k=0,Fk=F, k=，是空代換。假設(shè)Fk只含一個(gè)表達(dá)式，那么算法停頓，k就是最一般合一。找出Fk的差異集Dk。假設(shè)Dk中存在元素xk和tk，其中xk是變?cè)?，tk是項(xiàng)，且xk不在tk中出現(xiàn)，那么置：Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后轉(zhuǎn)(2)。假設(shè)不存在這樣的xk和tk那么算法停頓。算法終止，F(xiàn)的最一般合一

9、不存在。求取最一般合一的例子求公式集 F=P(a,x,f(g(y),P(z,f(z),f(u)的最一般合一。求取最一般合一的例子F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一的過(guò)程：令F0=F, 0=。 F0中有兩個(gè)表達(dá)式，所以0不是最一般合一。差異集：D0=a,z。代換： a/zF1= F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u) 。 1=0a/z=a/zD1=x,f(a) 。代換： f(a)/xF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u) 。 2=1f(a)/x=a/z,f(a)/x D2=g(y),u 。

10、代換： g(y)/uF3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y) 。 3=2g(y)/u=a/z,f(a)/x,g(y)/u 至此，求得最一般合一 a/z,f(a)/x,g(y)/u 3.1.5 沖突消解策略沖突：多個(gè)知識(shí)都匹配成功。正向推理：多條產(chǎn)生式前件都與事實(shí)匹配成功逆向推理：多條規(guī)那么后件都和同一個(gè)假設(shè)匹配成功沖突消解的根本思想都是對(duì)知識(shí)進(jìn)展排序。幾種沖突消解策略按針對(duì)性排序優(yōu)先選用針對(duì)性強(qiáng)的產(chǎn)生式規(guī)那么。按事實(shí)的新穎性排序優(yōu)先選用與較多新事實(shí)匹配的規(guī)那么。按匹配度排序在不確定性匹配中，計(jì)算兩個(gè)知識(shí)形式的相似度(匹配度)，并對(duì)其排序，相似度高的

11、規(guī)那么先推。按領(lǐng)域問(wèn)題特點(diǎn)排序按上下文限制排序把規(guī)那么按照下上文分組，并只能選取組中的規(guī)那么。按冗余限制排序冗余知識(shí)越少的規(guī)那么先推。按條件個(gè)數(shù)排序條件少的規(guī)那么先推。3.2 自然演繹推理從一組為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯的推理規(guī)那么推出結(jié)論的過(guò)程，稱為自然演繹推理。其中，根本的推理規(guī)那么是P規(guī)那么、T規(guī)那么、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式P規(guī)那么：在推理的任何步驟都可以引入前提。T規(guī)那么：推理時(shí)，假設(shè)前面步驟中有一個(gè)或者多個(gè)公式永真蘊(yùn)含公式S，那么可把S引入推理過(guò)程中。3.2 自然演繹推理3.3 歸結(jié)演繹推理定理證明：要證明PQ(PQ)的永真性。根據(jù)反證法

12、，只要證明其否認(rèn)(PQ) 不可滿足性即可。歸結(jié)：Resolution，也稱為消解，消解原理海伯倫(Herbrand)定理為自動(dòng)定理證明奠定了理論根底；魯濱遜(Robinson)提出的歸結(jié)原理使機(jī)器定理證明成為現(xiàn)實(shí)。3.3.1 子句在謂詞邏輯中，把原子謂詞公式及其否認(rèn)統(tǒng)稱為文字。 如：P(x)， P(x,f(x)， Q(x,g(x)定義： 不包含任何文字的子句稱為空子句。定義： 任何文字的析取式稱為子句。 例如： P(x)Q(x), P(x,f(x)Q(x,g(x) 子句集(1) 合取范式：C1 C2 C3 Cn(2) 子句集: S= C1 ,C2 ,C3 ,Cn(3)任何謂詞公式F都可通過(guò)等價(jià)

13、關(guān)系及推理規(guī)那么化為相應(yīng)的子句集S把謂詞公式化成子句集的步驟(1)1. 利用等價(jià)關(guān)系消去“和“例如公式可等價(jià)變換成2. 利用等價(jià)關(guān)系把“移到緊靠謂詞的位置上上式經(jīng)等價(jià)變換后3. 重新命名變?cè)?，使不同量詞約束的變?cè)胁煌拿稚鲜浇?jīng)變換后把謂詞公式化成子句集的步驟(2)4. 消去存在量詞a.存在量詞前面沒(méi)有全稱量詞時(shí)，那么只要用一個(gè)新的個(gè)體常量交換受該量詞約束的變?cè)?。b.存在量詞前面有一個(gè)或者多個(gè)全稱量詞時(shí)，要用函數(shù)f(x1,x2,xn)交換受該存在量詞約束的變?cè)?。上式中存在量詞(y)及(z)都位于(x)的后面，所以需要用函數(shù)交換，設(shè)交換y和z的函數(shù)分別是f(x)和g(x)，那么交換后得到5.

14、把全稱量詞全部移到公式的左邊把謂詞公式化成子句集的步驟(3)6. 利用等價(jià)關(guān)系把公式化為Skolem標(biāo)準(zhǔn)形Skolem標(biāo)準(zhǔn)形的一般形式是其中，M是子句的合取式，稱為Skolem標(biāo)準(zhǔn)形的母式。上式化為Skolem標(biāo)準(zhǔn)形后得到7. 消去全稱量詞8. 對(duì)變?cè)?，使不同子句中的變?cè)煌鲜交癁?. 消去合取詞，就得到子句集 子句集的性質(zhì)1子句集中子句之間是合取關(guān)系。2子句集中的變?cè)苋Q量詞的約束。 子句集的意義子句集S的不可滿足性：對(duì)于任意論域中的任意一個(gè)解釋，S中的子句不能同時(shí)獲得真值T。定理 設(shè)有謂詞公式F，其子句集為S，那么F不可滿足的充要條件是S不可滿足。要證明PQ永真，只需證明公式F=

15、(PQ)永假，即S P , Q不可滿足。3.3.2 海伯倫理論Herbrand為了判斷子句集的不可滿足性，需要對(duì)所有可能論域上的所有解釋進(jìn)展斷定。只有當(dāng)子句集對(duì)任何非空個(gè)體域上的任何一個(gè)解釋都是不可滿足的時(shí)候，才可斷定該子句集是不可滿足的。海伯倫構(gòu)造了一個(gè)特殊的論域(海伯倫域)，并證明只要對(duì)這個(gè)特殊域上的一切解釋進(jìn)展斷定，就可知子句集是否不可滿足。海伯倫域定義 設(shè)S為子句集，那么按下述方法構(gòu)造的域H稱為海伯倫域，記為H域：(1)令H0是S中所有個(gè)體常量的集合，假設(shè)S中不包含個(gè)體常量，那么令H0a，其中a為任意指定的一個(gè)個(gè)體常量。(2)令Hi+1=HiS中所有n元函數(shù)f(x1,xn)|xj(j=

16、1,n)是Hi中的元素，其中i=0,1,2,。海伯倫域的例子例 求子句集S=P(x)Q(x),R(f(y)的H域。解：此例中沒(méi)有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量，得到H0=aH1=a,f(a)H2=a,f(a),f(f(a)H3=a,f(a),f(f(a),f(f(f(a)H=a,f(a),f(f(a),f(f(f(a), 子句集S在H域上的解釋就是對(duì)S中出現(xiàn)的常量、函數(shù)及謂詞進(jìn)展指派。子句集在H域上的解釋定義 子句集S在H域上的一個(gè)解釋I滿足以下條件：(1)在解釋I下，常量映射到自身；(2)S中的任一個(gè)n元函數(shù)是HnH的映射。即設(shè) h1,h2,H，那么f(h1,h2,hn)H;(3)

17、S中的任一個(gè)n元謂詞是HnT,F的映射。謂詞的真值可以指派為T，也可為F。在H域上進(jìn)展解釋的意義意義：對(duì)于S任意可能論域D上的任意一個(gè)解釋I，總存在H域上的一個(gè)解釋I與它對(duì)應(yīng)，且子句集在這兩個(gè)解釋下具有一樣的真值。定理 子句集S不可滿足的充要條件是S對(duì)H域上一 切解釋都為假?；泳浼母拍罨印⒒淖?、基子句、基子句集沒(méi)有變量出現(xiàn)的原子、文字、子句、子句集，分別稱作基原子、基文字、基子句、基子句集如： P(a), P(f(a) 都稱作子句CP(x)的基例Herbrand 定理 子句集S不可滿足的充要條件是存在一個(gè)有限的不可滿足的基子句集S 。注： Herbrand 定理給出了一階邏輯的半可斷

18、定算法。即，僅當(dāng)被證明定理成立時(shí)，使用該算法可以得證，而當(dāng)被證明定理不成立時(shí)，使用該算法得不出任何結(jié)果。3.3.3 魯濱遜歸結(jié)原理子句集S的不可滿足性：對(duì)于任意論域中的任意一個(gè)解釋，S中的子句不能同時(shí)獲得真值T。一旦S中包含空子句，那么S必不可滿足。 魯濱遜歸結(jié)原理的根本思想：檢查子句集S中是否包含空子句。假設(shè)包含，那么S不可滿足；假設(shè)不包含，就在子句集中選擇適宜的子句進(jìn)展歸結(jié)，一旦通過(guò)歸結(jié)能推出空子句，就說(shuō)明子句集S是不可滿足的。命題邏輯中的歸結(jié)原理定義 假設(shè)P是原子謂詞公式，那么稱P與P為互補(bǔ)文字。在命題邏輯中，P為命題。定義 設(shè)C1與C2是子句集中的任意兩個(gè)子句。假設(shè)C1中的文字L1與C

19、2中文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的局部析取，構(gòu)成一個(gè)新子句C12，那么稱這一過(guò)程為歸結(jié)。稱C12為C1和C2的歸結(jié)式，C1和C2為C12的親本子句。例 設(shè)C1=PQ, C2=QR, C3=PC1與C2歸結(jié)得到：C12=PRC12與C3歸結(jié)得到：C123=R歸結(jié)原理中的重要定理定理 C12是其親本子句C1與C2的邏輯結(jié)論。證明：設(shè)C1=LC1, C2=LC2, 那么C12=C1C2兩個(gè)推論推論1 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式。假設(shè)用C12代替C1和C2后得到新子句集S1，那么由S1的不可滿足性可推出原子句集S的不可滿足性，即S

20、1的不可滿足性S的不可滿足性推論2 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們 的歸結(jié)式。假設(shè)把C12參加S中得到新子句集S2，那么S與S2在不可滿足的意義上是等價(jià)的，即S2的不可滿足性S的不可滿足性在命題邏輯中應(yīng)用歸結(jié)原理推論1及推論2保證了我們可以用歸結(jié)的方法來(lái)證明子句集S的不可滿足性。為了要證明子句集S的不可滿足性，只要對(duì)其中可進(jìn)展歸結(jié)的子句進(jìn)展歸結(jié)，并把歸結(jié)式參加子句集S，或者用歸結(jié)式交換它的親本子句，然后對(duì)新子句集(S1或者S2)證明不可滿足性就可以了。假設(shè)經(jīng)過(guò)歸結(jié)能得到空子句，那么立即可得原子句集S是不可滿足的結(jié)論。在命題邏輯中，對(duì)不可滿足的子句集S，歸結(jié)原理是完備的。即，假

21、設(shè)子句集不可滿足，那么必然存在一個(gè)從S到空子句的歸結(jié)演繹；假設(shè)存在一個(gè)從S到空子句的歸結(jié)演繹，那么S一定是不可滿足的。謂詞邏輯中的歸結(jié)原理在謂詞邏輯中，由于子句中含有變?cè)?，所以不能像命題邏輯那樣直接消去互補(bǔ)文字，而需要先用最一般合一對(duì)變?cè)M(jìn)展代換，然后才能進(jìn)展歸結(jié)。例如,設(shè)有兩個(gè)子句C1=P(x)Q(x), C2= P(a)R(y)由于P(x)與P(a)不同，所以C1與C2不能直接進(jìn)展歸結(jié)。但是假設(shè)用最一般合一 =a/x 對(duì)兩個(gè)子句分別進(jìn)展代換：C1 =P(a)Q(a)C2 = P(a)R(y)就可對(duì)它們進(jìn)展歸結(jié)，得到歸結(jié)式：Q(a)R(y)二元?dú)w結(jié)式的定義定義 設(shè)C1與C2是兩個(gè)沒(méi)有一樣變?cè)?/p>

22、的子句，L1和L2分別是C1和C2中的文字。假設(shè)是L1和L2的最一般合一，那么稱C12=(C1-L1)(C2-L2) 為C1和C2的二元?dú)w結(jié)式，L1和L2稱為歸結(jié)式上的文字。例 設(shè)C1=P(a)Q(x)R(x), C2=P(y)Q(b)假設(shè)選L1=P(a),L2=P(y)，那么有：L1=P(a), L2=P(y)，=a/y就是L1與L2的最一般合一。可得： C12=(C1-L1)(C2-L2)= Q(x)R(x)Q(b)假設(shè)參加歸結(jié)的子句內(nèi)部含有可合一的文字，那么在進(jìn)展歸結(jié)之前應(yīng)先對(duì)這些文字進(jìn)展合一。一般來(lái)說(shuō)，假設(shè)子句C中有兩個(gè)或者兩個(gè)以上的文字具有最一般合一，那么稱C是子句C的因子。假設(shè)C為

23、一個(gè)單文字，那么稱它為C的單元因子。例子： C1=P(x)VP(f(a)VQ(x) C2= P(y) VR(b) = f(a)/x C1=P(f(a) VQ(f(a) C12 = Q(f(a) VR(b)定義 子句C1和C2的歸結(jié)式是以下二元?dú)w結(jié)式之一：C1與C2的二元?dú)w結(jié)式；C1與C2的因子C22的二元?dú)w結(jié)式；C1的因子C11與C2的二元?dú)w結(jié)式；C1的因子C11與C2的因子C22的二元?dú)w結(jié)式。對(duì)于一階謂詞邏輯，歸結(jié)原理也是完備的。即，假設(shè)子句集S不可滿足，那么必然存在一個(gè)從S到空子句的歸結(jié)演繹；假設(shè)存在一個(gè)從S到空子句的歸結(jié)演繹，那么S一定是不可滿足的。特別注意求歸結(jié)式時(shí)不能同時(shí)消去兩個(gè)互補(bǔ)

24、對(duì)一個(gè)簡(jiǎn)單的例子 C1=P V Q C2= P V Q3.3.4 歸結(jié)反演如欲證明Q為P1,P2,Pn的邏輯結(jié)論，只需證(P1P2Pn)Q是不可滿足的，或證明其子句集是不可滿足的。而子句集的不可滿足性可用歸結(jié)原理來(lái)證明。應(yīng)用歸結(jié)原理證明定理的過(guò)程稱為歸結(jié)反演。歸結(jié)反演的步驟設(shè)F為前提的公式集，Q為目的公式(結(jié)論)，用歸結(jié)反演證明Q為真的步驟是：否認(rèn)Q，得到Q；把Q并入到公式集F中，得到F, Q;把公式集F, Q化為子句集S；應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)展歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)展，假設(shè)出現(xiàn)了空子句，那么停頓歸結(jié)，此時(shí)就證明了Q為真。 求證：G是F的邏輯結(jié)論。A(

25、x,y)B(y)C(f(x)A(x,y)B(y)B(b)NILC(z)A(a,b)B(b)證明：首先把F和G化為子句集：然后進(jìn)展歸結(jié)：(6)A(x,y)B(y)由(1)與(3)歸結(jié)，f(x)/z(7)B(b)由(4)與(6)歸結(jié)，a/x,b/y(8)NIL由(5)與(7)歸結(jié)所以G是F的邏輯結(jié)論。上述歸結(jié)過(guò)程如右圖歸結(jié)樹(shù)所示:自動(dòng)定理證明舉例證明：梯形的對(duì)角線與上下底構(gòu)成的內(nèi)錯(cuò)角相等證明過(guò)程： 1定義謂詞 2建立子句集 3運(yùn)用歸結(jié)原理進(jìn)展推理1定義謂詞設(shè)梯形的頂點(diǎn)為a、b、c、d，定義謂詞如下：T(x,y,u,v): 表示以x,y為上底、u,v為下底的梯形P(x,y,u,v): 表示邊xy平行

26、于邊uvT(x,y,z,u,v,w): 表示xyz= uvw2建立子句集3運(yùn)用歸結(jié)原理進(jìn)展推理3.3.5 應(yīng)用歸結(jié)原理求取問(wèn)題的答案把前提用謂詞公式表示出來(lái)，并且化為相應(yīng)的子句集。設(shè)該子句集的名字為S。把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它否認(rèn)并與謂詞Answer構(gòu)成析取式。Answer是一個(gè)為了求解問(wèn)題而專設(shè)的謂詞，其變?cè)毰c問(wèn)題公式的變?cè)耆恢?。把此析取式化為子句集，并且把該子句集并入到子句集S中，得到子句集S。對(duì)S應(yīng)用歸結(jié)原理進(jìn)展歸結(jié)。假設(shè)得到歸結(jié)式Answer，那么答案就在Answer中。求解的步驟：用歸結(jié)原理求解問(wèn)題的例子 設(shè)A,B,C三人中有人從不說(shuō)真話，也有人從不說(shuō)假話。

27、某人向這三人分別提出同一個(gè)問(wèn)題：誰(shuí)是說(shuō)謊者？A答：“B和C都是說(shuō)謊者；B答：“A和C都是說(shuō)謊者；C答：“A和B中至少有一個(gè)是說(shuō)謊者。求誰(shuí)是老實(shí)人，誰(shuí)是說(shuō)謊者？解：設(shè)用T(x)表示x說(shuō)真話, T(C)T(A)T(B)T(C)T(A)T(B) T(A)T(B)T(C) T(A)T(B)T(C) T(B)T(A)T(C) T(B)T(A)T(C) T(C)T(A)T(B) T(C)T(A)T(B)把上述公式化成子句集，得到S：(1)T(A)T(B)(2)T(A)T(C)(3)T(C)T(A)T(B)(4)T(B)T(C)(5)T(C)T(A)T(B)(6) T(A)T(C)(7)T(B)T(C)把T

28、(x)Ansewer(x)并入S得到S1。即多一個(gè)子句：(8)T(x)Ansewer(x)應(yīng)用歸結(jié)原理對(duì)S1進(jìn)展歸結(jié)：(9)T(A)T(C)(1)和(7)歸結(jié)(10)T(C) (6)和(9)歸結(jié)(11)Ansewer(C) (8)和(10)歸結(jié)所以C是老實(shí)人，即C從不說(shuō)假話。下面先求誰(shuí)是老實(shí)人。(1) T(A)T(B) (2) T(A)T(C)(3) T(C)T(A)T(B) (4) T(B)T(C)(5) T(C)T(A)T(B) (6) T(A)T(C)(7) T(B)T(C)對(duì)T(A)進(jìn)展否認(rèn)，并入S中，得到子句集S2，即S2比S多如下子句：(8)(T(A), 即T(A)應(yīng)用歸結(jié)原理對(duì)S

29、2進(jìn)展歸結(jié)：(9)T(A)T(C) (1)和(7)歸結(jié)(10)T(A) (2)和(9)歸結(jié)(11)NIL (8)和(10)歸結(jié)所以A不是老實(shí)人。同樣可以證明B也不是老實(shí)人。在上面的歸結(jié)中，歸結(jié)不出Ansewer(A)和Ansewer(B)。下面證明A不是老實(shí)人，即證明T(A)。兩點(diǎn)注意歸結(jié)時(shí)，并不要求把子句集中所有的子句都用到。在歸結(jié)過(guò)程中，一個(gè)子句可以屢次被用來(lái)進(jìn)展歸結(jié)。3.3.6 歸結(jié)策略歸結(jié)策略可分為兩大類：(1) 刪除策略刪除某些無(wú)用的子句來(lái)縮小歸結(jié)的范圍。(2) 限制策略通過(guò)對(duì)參加歸結(jié)的子句進(jìn)展種種限制，盡可能減小歸結(jié)的盲目性，使其盡快地歸結(jié)出空子句。歸結(jié)的一般過(guò)程設(shè)有子句集S=C1

30、,C2,C3,C4，那么對(duì)此子句集歸結(jié)的一般過(guò)程：S內(nèi)任意子句兩兩逐一進(jìn)展歸結(jié)，得到一組歸結(jié)式，稱為第一級(jí)歸結(jié)式，記為S1。把S與S1內(nèi)的任意子句兩兩逐一進(jìn)展歸結(jié)，得到一組歸結(jié)式，稱為第二級(jí)歸結(jié)式，記為S2。S和S1內(nèi)的子句與S2內(nèi)的任意子句兩兩逐一進(jìn)展歸結(jié)，得到一組歸結(jié)式，稱為第三級(jí)歸結(jié)式，記為S3。如此繼續(xù)，直到出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)為止。一個(gè)歸結(jié)的例子例 設(shè)有子句集S=P, R,PQ,QR。歸結(jié)過(guò)程為：S: (1)P(2)R(3)PQ(4)QRS1: (5)Q (1)與(3)歸結(jié)(6)Q (2)與(4)歸結(jié)(7)PR (3)與(4)歸結(jié)S2: (8)R (1)與(7)歸結(jié)(9)P

31、 (2)與(7)歸結(jié)(10)P (3)與(6)歸結(jié)(11)R (4)與(5)歸結(jié)S3: (12) NIL (1)與(9)歸結(jié)刪除策略純文字刪除法假設(shè)某文字L在子句集中不存在可與之互補(bǔ)的文字L，那么稱該文字為純文字。包含純文字的子句可以刪除。重言式刪除法假設(shè)一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，那么該字句稱為重言式。重言式是永遠(yuǎn)為真的子句，可以刪除。包孕刪除法設(shè)有子句C1和C2，假設(shè)存在一個(gè)代換，使得 ，那么稱C1包孕于C2。C2可刪除。支持集策略對(duì)參加歸結(jié)的子句提出如下限制：每一次歸結(jié)時(shí)，親本子句中至少有一個(gè)是由目的公式的否認(rèn)所得到的子句，或者是它的后裔?？梢宰C明，支持集策略是完備的。支持集策略用支持

32、集策略進(jìn)展歸結(jié)的過(guò)程是：S:(1) I(x)R(x)(2) I(a)(3) R(y)L(y)(4) L(a)S1: (5) R(a) (1)與(2)歸結(jié)(6) I(x)L(x) (1)與(3)歸結(jié)S2: (7) L(a) (2)與(6)歸結(jié)(8) L(a) (3)與(5)歸結(jié)(9) I(a) (4)與(6)歸結(jié)S3: (10)NIL (2)與(9)歸結(jié)例 設(shè)有子句集S=I(x)R(x),I(a),R(y)L(y),L(a)其中I(x)R(x)是目的公式否認(rèn)后得到的子句。支持集策略例如I(x)R(x)I(a)R(y)L(y)L(a)R(a)L(a)I(x)L(x)L(a)I(a)NIL12345

33、678910線性輸入策略限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是初始子句集中的子句。I(x)R(x)I(a)R(y)L(y)L(a)R(a)L(a)I(x)L(x)L(a)I(a)NIL123456981112R(a)I(a)710線性輸入策略可限制生成歸結(jié)式的數(shù)量，具有簡(jiǎn)單、高效的優(yōu)點(diǎn)。但是它是不完備的。單文字子句策略假設(shè)一個(gè)子句只包含一個(gè)文字，稱它為單文字子句。用單文字子句策略歸結(jié)時(shí)，歸結(jié)式比親本子句含有較少的文字，這有利于朝著空子句的方向前進(jìn)，因此它有較高的歸結(jié)效率。但是，這種歸結(jié)策略是不完備的。當(dāng)初始子句集中不包含單文字子句時(shí)，歸結(jié)就無(wú)法進(jìn)展。限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)

34、是單文字子句。祖先過(guò)濾策略該策略與線性策略比較相似，但放寬了限制。當(dāng)對(duì)兩個(gè)子句C1和C2進(jìn)展歸結(jié)時(shí)，只要它們滿足下述任一個(gè)條件就可以歸結(jié):C1和C2中至少有一個(gè)是初始子句集中的子句。C1和C2中一個(gè)是另外一個(gè)的祖先子句。祖先過(guò)濾策略是完備的。Q(x)P(x)Q(y)P(y)Q(w)P(w)Q(w)Q(u)P(A)P(A)NILP(x)*祖先過(guò)濾策略的搜索過(guò)程例：設(shè)有子句集 Q(x)P(x), Q(y)P(y),Q(w)P(w), Q(u)P(A) ，用祖先過(guò)濾形策略進(jìn)展歸結(jié)優(yōu)點(diǎn)：缺點(diǎn)：歸結(jié)演繹推理的特點(diǎn)簡(jiǎn)單，便于在計(jì)算機(jī)上實(shí)現(xiàn)。必須把邏輯公式化成子句集。不便于閱讀與理解。P(x)Q(x)沒(méi)有P

35、(x)Q(x)直觀?？赡軉适Э刂菩畔ⅰ＠缫韵逻壿嫻剑?AB)C A(BC)(AC)B B(AC)(CB)A C(BA)化成子句后都是: ABC3.4 與/或形演繹推理歸結(jié)演繹推理要求把有關(guān)問(wèn)題的知識(shí)及目的的否認(rèn)都化成子句形式，然后通過(guò)歸結(jié)進(jìn)展演繹推理，其推理規(guī)那么只有一條，即歸結(jié)規(guī)那么.與/或形演繹推理不再把有關(guān)知識(shí)轉(zhuǎn)化成子句集，而把領(lǐng)域知識(shí)及事實(shí)分別用蘊(yùn)含式及與/或形表示出來(lái)，然后通過(guò)運(yùn)用蘊(yùn)含式進(jìn)展演繹推理，從而證明某個(gè)目的公式。與/或形演繹推理的分類正向演繹 從事實(shí)出發(fā)，正向地使用蘊(yùn)含式F規(guī)那么進(jìn)展推理，直至得到某個(gè)目的公式的一個(gè)終止條件為止。逆向演繹 從待證明的目的出發(fā)，通過(guò)逆向地使

36、用蘊(yùn)含式B規(guī)那么進(jìn)展演繹推理，直至得到包含事實(shí)的終止條件為止。雙向演繹 同時(shí)運(yùn)用F規(guī)那么和B規(guī)那么4.4.1 正向與/或形演繹推理正向與/或形演繹推理對(duì)事實(shí)、F規(guī)那么和目的公式地表示形式都有一定要求。假設(shè)不符合要求，就需要先進(jìn)展變換。1 事實(shí)表達(dá)式的與/或形變換及其樹(shù)形表示 正向與/或形演繹推理要求事實(shí)用不含蘊(yùn)含符號(hào)的與/或形表示。把一個(gè)公式轉(zhuǎn)換為與/或形的步驟類似于子句集的轉(zhuǎn)換過(guò)程：1利用PQ 等價(jià)于PQ，消去公式中的“；2利用德摩根律及量詞轉(zhuǎn)換律把“轉(zhuǎn)移到緊靠謂詞的位置上；3重新命名變?cè)?，使得不同量詞約束的變?cè)哂胁煌拿郑?引入Skolem函數(shù)消去存在量詞；5消去全稱量詞，且使各主要合

37、取式中的變?cè)煌? 事實(shí)表達(dá)式的與/或形變換及其樹(shù)形表示事實(shí)表示式的與/或形可用一顆與/或樹(shù)表示。與/或樹(shù)的一個(gè)節(jié)點(diǎn)表示事實(shí)表達(dá)式的一個(gè)子表達(dá)式，葉節(jié)點(diǎn)為謂詞公式中的文字。對(duì)于用析取符號(hào)連接而成的表達(dá)式，用一個(gè)N連接符半圓弧把它們連接起來(lái)。對(duì)于用合取符號(hào)連接而成的表達(dá)式，無(wú)需用連接符半圓弧連接。事實(shí)的與或樹(shù)表示例： Q(w, A)(R(v) P(v) S(A, v)Q(w, A)(R(v) P(v) S(A, v)Q(w, A)(R(v) P(v) S(A, v)R(v) P(v) S(A, v)R(v)P(v)解圖集：Q(w, A), R(v)S(A, v), P(v)S(A, v) 2

38、 F規(guī)那么的表示形式在正向與/或形演繹推理中，通常要求F規(guī)那么具有如下形式：L W其中，L為單文字，W為與/或形。限制F規(guī)那么左部為單文字的原因：要用F規(guī)那么作用于表示事實(shí)的與/或樹(shù)，而與/或樹(shù)的葉節(jié)點(diǎn)都是單文字。2 F規(guī)那么的表示形式 假設(shè)領(lǐng)域知識(shí)不是所要求的表示形式，那么需要通過(guò)變換將它變成規(guī)定的形式，步驟如下王：P144例子：1暫時(shí)消去蘊(yùn)含符號(hào)“；2利用德摩根律及量詞轉(zhuǎn)換律把“轉(zhuǎn)移到緊靠謂詞的位置上；3引入Skolem函數(shù)消去存在量詞；4消去全稱量詞；5恢復(fù)為蘊(yùn)含式。3 目的公式的表示形式在正向與/或形演繹推理中，要求目的公式用子句表示，否那么就要化成子句形式。轉(zhuǎn)換方法同前4 推理過(guò)程1

39、用與/或樹(shù)把事實(shí)表示出來(lái)；2用F規(guī)那么的左部和與/或樹(shù)的節(jié)點(diǎn)進(jìn)展匹配，并將匹配成功的F規(guī)那么參加到與/或樹(shù)中；3重復(fù)第2步，直到產(chǎn)生一個(gè)含有以目的節(jié) 點(diǎn)作為終止節(jié)點(diǎn)的解圖為止。例：事實(shí)：A B規(guī)那么集： A C D B E G目的公式： C GA BABACDBEGCG目的正向與/或形演繹推理舉例命題邏輯例：設(shè)事實(shí)和規(guī)那么分別為事實(shí)：(P Q) R) (S (T U)規(guī)那么：S (X Y) Z 用正向演繹推理推出所有可能的目的子句。正向與/或形演繹推理舉例命題邏輯(P Q) R) (S (T U)(P Q) R S (T U)P Q R ST UPQTUSX YZX YP Q SP Q T U

40、S RR T UP Q X ZP Q Y ZR X ZR Y Z規(guī)那么的子句： S (X Y) Z= S(X Y) Z= S X Z S Y Z結(jié)論：參加規(guī)那么后得到的解圖，是事實(shí)與規(guī)那么對(duì)應(yīng)子句的歸結(jié)式例：事實(shí)：P(x, y) (Q(x, A) R(B, y) 規(guī)那么集： P(A, B) (S(A) X(B) Q(B, A) U(A) R(B, B) V(B) 目的：S(A) X(B) U(A)P(x, y) (Q(x, A) R(B, y)P(x, y)Q(x, A) R(B, y)Q(x, A) R(B, y)P(A, B)A/x,B/yS(A)X(B)Q(B, A) B/xU(A) R

41、(B, B)B/yV(B) 正向與/或形演繹推理舉例謂詞邏輯4.4.2 逆向與/或形演繹推理與/或形逆向演繹推理從待證明的目的出發(fā)，通過(guò)逆向地使用蘊(yùn)含式B規(guī)那么進(jìn)展演繹推理，直至得到包含事實(shí)地終止條件為止。與/或形逆向演繹推理對(duì)目的公式、B規(guī)那么和事實(shí)的表示形式也有詳細(xì)要求，假設(shè)不符合要求，就需要進(jìn)展變換。1 目的公式的與/或形變換及其樹(shù)形表示把一個(gè)目的公式轉(zhuǎn)換為與/或形的步驟類似于子句集的轉(zhuǎn)換過(guò)程：1利用PQ 等價(jià)于PQ，消去公式中的“；2利用德摩根律及量詞轉(zhuǎn)換律把“轉(zhuǎn)移到緊靠謂詞的位置上；3重新命名變?cè)?，使得不同量詞約束的變?cè)哂胁煌拿郑?引入Skolem函數(shù)消去全稱量詞；5消去存在量

42、詞，且使各主要析取式中的變?cè)煌Ｗ⒁猓荷鲜黾t字標(biāo)出的局部是與前面與/或形正向演繹推理中把事實(shí)變換為與/或形表示不同的地方。1 目的公式的與/或形變換及其樹(shù)形表示目的表示式的與/或形可用一顆與/或樹(shù)表示。把與/或樹(shù)的葉節(jié)點(diǎn)用它們之間的合取及析取關(guān)系連接起來(lái)，就可得到目的公式的子目的。對(duì)于用合取符號(hào)連接而成的表達(dá)式，用一個(gè)N連接符半圓弧把它們連接起來(lái)。對(duì)于用析取符號(hào)連接而成的表達(dá)式，無(wú)需用連接符半圓弧連接。這點(diǎn)也和正向與/或形演繹推理不同2 B規(guī)那么的表示形式在逆向與/或形演繹推理中，要求B規(guī)那么具有如下形式：W L 其中，W為任一與/或形公式， L為文字。限制B規(guī)那么右部為文字的原因：要用B規(guī)那么的右部和目的與/或樹(shù)的葉節(jié)點(diǎn)進(jìn)展匹配，而目的與/或樹(shù)的葉節(jié)點(diǎn)都是文字。3 事實(shí)的表示形式逆向與/或形演繹推理要求事實(shí)是文字的合取式，即形如F1 F2 Fn因?yàn)槊總€(gè)事實(shí)都可以單獨(dú)使用，因此上式也可表示為如下集合：F1,F2,Fn4 推理過(guò)程1用與/或樹(shù)把目的公式表示出來(lái)；2用B規(guī)那么的右部和與/或樹(shù)的葉子節(jié)點(diǎn)進(jìn)展匹配，將匹配成功的B規(guī)那么參加到與/或樹(shù)中；3重復(fù)第2步，直到產(chǎn)生某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖為止。注：一致解圖是指在推理