1、第四章經(jīng)典邏輯推理,4.1 基本概念 4.2 自然演繹推理 4.3 歸結(jié)演繹推理 4.4 與或形演繹推理,4.1 基本概念,4.1.1 什么是推理 所謂推理就是按某種策略由已知判斷推出另一個(gè)判斷的思維過(guò)程。 在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱(chēng)為推理機(jī)。,4.1.2 推理方式及其分類(lèi),1. 演繹推理、歸納推理、默認(rèn)推理 演繹推理：從一般到特殊。例如三段論。 歸納推理：從個(gè)體到一般。 默認(rèn)推理：缺省推理，在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。 2. 確定性、不確定性推理 3. 單調(diào)推理、非單調(diào)推理 推出的結(jié)論是否單調(diào)增加 4. 啟發(fā)式、非啟發(fā)式推理 所謂啟發(fā)性知識(shí)是指與問(wèn)題有關(guān)且

2、能加快推理進(jìn)程、求得問(wèn)題最優(yōu)解的知識(shí)。 5. 基于知識(shí)的推理（專(zhuān)家系統(tǒng)） 、統(tǒng)計(jì)推理、直覺(jué)推理（常識(shí)性推理）,4.1.3 推理的控制策略,推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制策略。 1. 正向推理（數(shù)據(jù)驅(qū)動(dòng)推理） 正向推理的基本思想是：從用戶(hù)提供的初始已知事實(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 逆向推理,逆

3、向推理的基本思想是：首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明原假設(shè)是成立的；若找不到所需要的證據(jù)，則說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的假設(shè)。,逆向推理示意圖,動(dòng)物識(shí)別的例子,已知事實(shí)：一動(dòng)物有毛，吃草，黑條紋 R1：動(dòng)物有毛 哺乳類(lèi) R2：動(dòng)物產(chǎn)奶 哺乳類(lèi) R3：哺乳類(lèi) 吃肉 食肉類(lèi) R4：哺乳類(lèi) 吃草 有蹄類(lèi) R5：食肉類(lèi) 黃褐色 有斑點(diǎn) 獵狗 R6：食肉類(lèi) 黃褐色 黑條紋 虎 R7：有蹄類(lèi) 長(zhǎng)脖 長(zhǎng)頸鹿 R8：有蹄類(lèi) 黑條紋 斑馬,3. 混合推理 先正向推理后逆向推理 先逆向推理后正向推理 4. 雙向推理 正向推理與逆向推理同時(shí)進(jìn)行，且在推理過(guò)程中的某一

4、步上“碰頭”。 5. 求解策略 只求一個(gè)解，還是求所有解以及最優(yōu)解。 6. 限制策略 限制搜索的深度、寬度、時(shí)間、空間等等。,所謂模式匹配是指對(duì)兩個(gè)知識(shí)模式(例如兩個(gè)謂詞公式、框架片斷、語(yǔ)義網(wǎng)絡(luò)片斷)進(jìn)行比較，檢查這兩個(gè)知識(shí)模式是否完全一致或者近似一致。 模式匹配可分為確定性匹配與不確定性匹配。 確定性匹配是指兩個(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)。,4.1

5、.4 模式匹配,變量代換,定義4.1 代換是一個(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)地出現(xià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稱(chēng)為F的特例。 規(guī)則: IF father(x,y) and man(y

6、) THEN son(y,x) 事實(shí): father(李四，李小四) and man(李小四) F=father(x,y) man(y) = 李四/X,李小四/Y F= father(李四，李小四) man(李小四) 結(jié)論: son(李小四,李四),代換的復(fù)合,定義4.2 設(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=xi ui/yi當(dāng)yix1,x2,xn 后剩下的元素所構(gòu)成的集合，記為 。 注

7、： ti表示對(duì)ti運(yùn)用進(jìn)行代換。 就是對(duì)一個(gè)公式F先運(yùn)用進(jìn)行代換，然后再運(yùn)用進(jìn)行代換：F（ ）=（F ）,代換的例子,例如，設(shè)有代換 = f(y)/x,z/w = a/x,b/y,w/z 則 =f(y)/x, z/w, a/x, b/y, w/z =f(b)/x, w/w, a/x, b/y, w/z =f(b)/x,w/z,公式集的合一,定義4.3 設(shè)有公式集F=F1,F2,Fn，若存在一個(gè)代換使得 F1=F2=Fn 則稱(chēng)為公式集F的一個(gè)合一，且稱(chēng)F1,F2,Fn是可合一的。 例如，設(shè)有公式集 F=P(x,y,f(y),P(a,g(x),z) 則下式是它的一個(gè)合一： =a/x,g(a)/y,

8、f(g(a)/z 一個(gè)公式集的合一一般不唯一。,最一般的合一,定義4.4 設(shè)是公式集F的一個(gè)合一，如果對(duì)任一個(gè)合一都存在一個(gè)置換，使得= 則稱(chēng)是一個(gè)最一般的合一。 （1）置換過(guò)程是一個(gè)用項(xiàng)代替變?cè)倪^(guò)程，因此是一 個(gè)從一般到特殊的過(guò)程。 （2） 最一般合一是唯一的。,求取最一般合一,差異集：兩個(gè)公式中相同位置處不同符號(hào)的集合。 例：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=。 是空代換。 若Fk只含一個(gè)表達(dá)式，則算法停止，k就是最一般合一。 找出Fk的差異集Dk。 若Dk中

9、存在元素xk和tk，其中xk是變?cè)瑃k是項(xiàng)，且xk不在tk中出現(xiàn)，則置： Fk+1=Fktk/xk K+1=ktk/xk k=k+1 然后轉(zhuǎn)(2)。若不存在這樣的xk和tk則算法停止。 算法終止，F(xiàn)的最一般合一不存在。,求取最一般合一的例子,例如，設(shè) F=P(a,x,f(g(y),P(z,f(z),f(u) 求其最一般合一。 令F0=F, 0=。F0中有兩個(gè)表達(dá)式，所以0不是最一般合一。 差異集：D0=a,z。代換： a/z F1= F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u) 。 1=0a/z=a/z D1=x,f(a) 。代換： f(a)/x F2=F1f(a)/x

10、=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 。代換： g(y)/u F3=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,4.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í)匹

11、配的規(guī)則。 按匹配度排序 在不確定性匹配中，計(jì)算兩個(gè)知識(shí)模式的相似度(匹配度)，并對(duì)其排序，相似度高的規(guī)則先推。 按領(lǐng)域問(wèn)題特點(diǎn)排序 按上下文限制排序 把規(guī)則按照下上文分組，并只能選取組中的規(guī)則。 按冗余限制排序 冗余知識(shí)越少的規(guī)則先推。 按條件個(gè)數(shù)排序 條件少的規(guī)則先推。,4.2 自然演繹推理,從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過(guò)程，稱(chēng)為自然演繹推理。其中，基本的推理規(guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。 假言推理的一般形式 拒取式推理的一般形式,P規(guī)則：在推理的任何步驟都可以引入前提。 T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或者多個(gè)公式永真蘊(yùn)含公式S，則可

12、把S引入推理過(guò)程中。,4.3 歸結(jié)演繹推理,定理證明即證明PQ(PQ)的永真性。根據(jù)反證法，只要證明其否定(PQ) 不可滿(mǎn)足性即可。 海伯倫(Herbrand)定理為自動(dòng)定理證明奠定了理論基礎(chǔ)；魯濱遜(Robinson)提出的歸結(jié)原理使機(jī)器定理證明成為現(xiàn)實(shí)。,4.3.1 子句,在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱(chēng)為文字。如：P(x)， P(x,f(x)， Q(x,g(x) 定義4.5： 任何文字的析取式稱(chēng)為子句。 例如： P(x)Q(x), P(x,f(x)Q(x,g(x) 定義4.6： 不包含任何文字的子句稱(chēng)為空子句。,子句集,(1) 合取范式：C1 C2 C3 Cn (2) 子句集:

13、S= C1 ,C2 ,C3 ,Cn (3)任何謂詞公式F都可通過(guò)等價(jià)關(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.存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi)，則只要用一個(gè)新的個(gè)體常量替換受該量詞約束的變?cè)?b.存在量詞位于一個(gè)或者多個(gè)全稱(chēng)量詞的轄域內(nèi)，此時(shí)要用Skolem函數(shù)f(x1,x2,xn)替換受該存在量詞約束的變?cè)?上式中存

14、在量詞(y)及(z)都位于(x)的轄域內(nèi)，所以需要用Skolem函數(shù)替換，設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后得到 5. 把全稱(chēng)量詞全部移到公式的左邊,把謂詞公式化成子句集的步驟(3),6. 利用等價(jià)關(guān)系把公式化為Skolem標(biāo)準(zhǔn)形 Skolem標(biāo)準(zhǔn)形的一般形式是 其中，M是子句的合取式，稱(chēng)為Skolem標(biāo)準(zhǔn)形的母式。 上式化為Skolem標(biāo)準(zhǔn)形后得到 7. 消去全稱(chēng)量詞 8. 對(duì)變?cè)共煌泳渲械淖冊(cè)煌?上式化為 9. 消去合取詞，就得到子句集,子句集的性質(zhì),（1）子句集中子句之間是合取關(guān)系。 （2）子句集中的變?cè)苋Q(chēng)量詞的約束。,子句集的意義,子句集

15、S的不可滿(mǎn)足性：對(duì)于任意論域中的任意 一個(gè)解釋?zhuān)琒中的子句不能同時(shí)取得真值T。 定理4.1 設(shè)有謂詞公式F，其子句集為S，則F不可滿(mǎn)足的充要條件是S不可滿(mǎn)足。 要證明PQ永真，只需證明公式F=(PQ)永假，即S不可滿(mǎn)足。,4.3.2 Herbrand理論,為了判斷子句集的不可滿(mǎn)足性，需要對(duì)所有可能論域上的所有解釋進(jìn)行判定。只有當(dāng)子句集對(duì)任何非空個(gè)體域上的任何一個(gè)解釋都是不可滿(mǎn)足的，才可斷定該子句集是不可滿(mǎn)足的。 海伯倫構(gòu)造了一個(gè)特殊的論域(海伯倫域)，并證明只要對(duì)這個(gè)特殊域上的一切解釋進(jìn)行判定，就可知子句集是否不可滿(mǎn)足。,海伯倫域,定義4.7 設(shè)S為子句集，則按下述方法構(gòu)造的域H稱(chēng)為海伯倫域，

16、記為H域。 (1)令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則令H0a，其中a為任意指定的一個(gè)個(gè)體常量。 (2)令Hi+1=HiS中所有n元函數(shù)f(x1,xn)|xj(j=1,n)是Hi中的元素，其中i=0,1,2,。 例4.3 求子句集S=P(x)Q(x),R(f(y)的H域。 解：此例中沒(méi)有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量，得到 H0=a H1=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)行指派。 定義4.8

17、 子句集S在H域上的一個(gè)解釋I滿(mǎn)足下列條 件： (1)在解釋I下，常量映射到自身； (2)S中的任一個(gè)n元函數(shù)是HnH的映射。即設(shè) h1,h2,H，則f(h1,h2,hn)H; (3)S中的任一個(gè)n元謂詞是HnT,F的映射。謂 詞的真值可以指派為T(mén)，也可為F。,在H域上進(jìn)行解釋的意義,意義：對(duì)于S任意可能論域D上的任意一個(gè)解釋I，總存 在H域上的一個(gè)解釋I與它對(duì)應(yīng)，且子句集在這兩個(gè)解 釋下具有相同的真值。 定理4.2 子句集S不可滿(mǎn)足的充要條件是S對(duì)H域上一切 解釋都為假。,4.3.3 魯濱遜歸結(jié)原理,魯濱遜歸結(jié)原理的基本思想：檢查子句集S中是否包含空子句。若包含，則S不可滿(mǎn)足；若不包含，就在

18、子句集中選擇合適的子句進(jìn)行歸結(jié)，一旦通過(guò)歸結(jié)能推出空子句，就說(shuō)明子句集S是不可滿(mǎn)足的。 子句集S的不可滿(mǎn)足性：對(duì)于任意論域中的任意一個(gè)解釋?zhuān)琒中的子句不能同時(shí)取得真值T。一旦S中包含空子句，則S必不可滿(mǎn)足。,命題邏輯中的歸結(jié)原理,定義4.9 若P是原子謂詞公式，則稱(chēng)P與P為互補(bǔ)文字。 在命題邏輯中，P為命題。 定義4.10 設(shè)C1與C2是子句集中的任意兩個(gè)子句。如果C1中的文字L1與C2中文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱(chēng)這一過(guò)程為歸結(jié)。稱(chēng)C12為C1和C2的歸結(jié)式，C1和C2為C12的親本子句。 例4.9 設(shè) C1=P

19、Q, C2=QR, C3=P C1與C2歸結(jié)得到：C12=PR C12與C3歸結(jié)得到：C123=R,定理4.4 C12是其親本子句C1與C2的邏輯結(jié)論。 證明：設(shè) C1=LC1, C2=LC2, 則C12=C1C2,推論1 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式。若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿(mǎn)足性可推出原子句集S的不可滿(mǎn)足性，即 S1的不可滿(mǎn)足性S的不可滿(mǎn)足性 推論2 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式。若把C12加入S中得到新子句集S2，則S與S2在不可滿(mǎn)足的意義上是等價(jià)的，即 S2的不可滿(mǎn)足性S的不可滿(mǎn)足性,推論1及推論

20、2保證了我們可以用歸結(jié)的方法來(lái)證明子句集S的不可滿(mǎn)足性。 為了要證明子句集S的不可滿(mǎn)足性，只要對(duì)其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或者用歸結(jié)式替換它的親本子句，然后對(duì)新子句集(S1或者S2)證明不可滿(mǎn)足性就可以了。如果經(jīng)過(guò)歸結(jié)能得到空子句，則立即可得原子句集S是不可滿(mǎn)足的結(jié)論。 在命題邏輯中，對(duì)不可滿(mǎn)足的子句集S，歸結(jié)原理是完備的。即，若子句集不可滿(mǎn)足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S到空子句的歸結(jié)演繹，則S一定是不可滿(mǎn)足的。,謂詞邏輯中的歸結(jié)原理,在謂詞邏輯中，由于子句中含有變?cè)圆荒芟衩}邏輯那樣直接消去互補(bǔ)文字，而需要先用最一般合一對(duì)變?cè)M(jìn)行代

21、換，然后才能進(jìn)行歸結(jié)。 例如,設(shè)有兩個(gè)子句 C1=P(x)Q(x), C2= P(a)R(y) 由于P(x)與P(a)不同，所以C1與C2不能直接進(jìn)行歸結(jié)。但是若用最一般合一 =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é)式的定義,定義4.11 設(shè)C1與C2是兩個(gè)沒(méi)有相同變?cè)淖泳?，L1和L2分別是C1和C2中的文字。若是L1和L2的最一般合一，則稱(chēng) C12=(C1-L1)(C2-L2) 為C1和C2的二元?dú)w結(jié)式，L1和L2稱(chēng)為歸結(jié)式上的文字。 例4.10 設(shè) C1=P(a)Q(x)R(x)

22、, C2=P(y)Q(b) 若選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),若子句C含有可合一的文字，則在進(jìn)行歸結(jié)之前應(yīng)先對(duì)這些文字進(jìn)行合一。記其最一般的合一為，稱(chēng)C子句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),定義4.12 子句C1和C2的歸結(jié)式是下列二元?dú)w結(jié)式之一： C1與C2的二元?dú)w結(jié)式； C1與C2的因子C22的二

23、元?dú)w結(jié)式； C1的因子C11與C2的二元?dú)w結(jié)式； C1的因子C11與C2的因子C22的二元?dú)w結(jié)式。 對(duì)于一階謂詞邏輯歸結(jié)原理也是完備的。即，若子句集S不可滿(mǎn)足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S到空子句的歸結(jié)演繹，則S一定是不可滿(mǎn)足的。,4.3.4 歸結(jié)反演,如欲證明Q為P1,P2,Pn的邏輯結(jié)論，只需證 (P1P2Pn)Q 是不可滿(mǎn)足的，或證明其子句集是不可滿(mǎn)足的。而子句集的 不可滿(mǎn)足性可用歸結(jié)原理來(lái)證明。 應(yīng)用歸結(jié)原理證明定理的過(guò)程稱(chēng)為歸結(jié)反演。 設(shè)F為已知前提的公式集，Q為目標(biāo)公式(結(jié)論)，用歸結(jié)反演證明Q為真的步驟是： 否定Q，得到Q； 把Q并入到公式集F中，得到F,

24、 Q; 把公式集F, Q化為子句集S； 應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。,歸結(jié)反演的例子,例4.12 已知 求證：G是F的邏輯結(jié)論。 證明：首先把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ù)所示。,4.3.5 應(yīng)用歸結(jié)原理求取問(wèn)題的答案,求解的步驟： 把已知前提用謂詞公式表示出來(lái)，并且化為相應(yīng)的子句集。設(shè)

25、該子句集的名字為S。 把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它否定并與謂詞Answer構(gòu)成析取式。Answer是一個(gè)為了求解問(wèn)題而專(zhuān)設(shè)的謂詞。 把此析取式化為子句集，并且把該子句集并入到子句集S中，得到子句集S。 對(duì)S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。 若得到歸結(jié)式Answer，則答案就在Answer中。,用歸結(jié)原理求解問(wèn)題的例子(1),例4.16 設(shè)A,B,C三人中有人從不說(shuō)真話(huà)，也有人從不說(shuō)假話(huà)。某人向這三人分別提出同一個(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ō)真話(huà)。 T(C

26、)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),用歸結(jié)原理求解問(wèn)題的例子(2),把上述公式化成子句集，得到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) 下面先求誰(shuí)是老實(shí)人。把T(x)Ansewer(x)并入S得到S1。即多一個(gè)子句： (8)T(x)Ansewer(x) 應(yīng)用歸結(jié)原理對(duì)S1進(jìn)行歸結(jié)：

27、(9)T(A)T(C)(1)和(7)歸結(jié) (10)T(C) (6)和(9)歸結(jié) (11)Ansewer(C) (8)和(10)歸結(jié) 所以C是老實(shí)人，即C從不說(shuō)假話(huà)。,(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) 下面證明A不是老實(shí)人，即證明T(A)。 對(duì)T(A)進(jìn)行否定，并入S中，得到子句集S2，即S2比S多如下子句： (8)(T(A), 即T(A) 應(yīng)用歸結(jié)原理對(duì)S2進(jìn)行歸結(jié)： (9)T(A)T(C) (1)和(7)歸結(jié) (10)T(A) (2)和(9)

28、歸結(jié) (11)NIL (8)和(10)歸結(jié) 所以A不是老實(shí)人。同樣可以證明B也不是老實(shí)人。,歸結(jié)時(shí)，并不要求把子句集中所有的子句都用到。 在歸結(jié)過(guò)程中，一個(gè)子句可以多次被用來(lái)進(jìn)行歸結(jié)。,4.3.6 歸結(jié)策略,歸結(jié)策略可分為兩大類(lèi)： 一類(lèi)是刪除策略； 刪除某些無(wú)用的子句來(lái)縮小歸結(jié)的范圍。 一類(lèi)是限制策略。 通過(guò)對(duì)參加歸結(jié)的子句進(jìn)行種種限制，盡可能減小歸結(jié)的盲目性，使其盡快地歸結(jié)出空子句。 歸結(jié)的一般過(guò)程 設(shè)有子句集S=C1,C2,C3,C4，則對(duì)此子句集歸結(jié)的一般過(guò)程是： S內(nèi)任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第一級(jí)歸結(jié)式，記為S1。 把S與S1內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組

29、歸結(jié)式，稱(chēng)為第二級(jí)歸結(jié)式，記為S2。 S和S1內(nèi)的子句與S2內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第三級(jí)歸結(jié)式，記為S3。 如此繼續(xù)，直到出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)為止。,一個(gè)歸結(jié)的例子,例4.17 設(shè)有子句集S=P, R,PQ,QR。歸結(jié)過(guò)程為： S: (1)P (2)R (3)PQ (4)QR S1: (5)Q (1)與(3)歸結(jié) (6)Q (2)與(4)歸結(jié) (7)PR (3)與(4)歸結(jié) S2: (8)R (1)與(7)歸結(jié) (9)P (2)與(7)歸結(jié) (10)P (3)與(6)歸結(jié) (11)R (4)與(5)歸結(jié) S3: (12) NIL (1)與(9)歸結(jié),刪除策

30、略,純文字刪除法 如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則稱(chēng)該文字為純文字。包含純文字的子句可以刪除。 重言式刪除法 如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，則該字句稱(chēng)為重言式。重言式是永遠(yuǎn)為真的子句，可以刪除。 包孕刪除法 設(shè)有子句C1和C2，如果存在一個(gè)代換，使得 ，則稱(chēng)C1包孕于C2。C2可刪除。,支持集策略,對(duì)參加歸結(jié)的子句提出如下限制：每一次歸結(jié)時(shí)，親本子句中至少有一個(gè)是由目標(biāo)公式的否定所得到的子句，或者是它的后裔?？梢宰C明，支持集策略是完備的。 例4.18 設(shè)有子句集S=I(x)R(x),I(a),R(y)L(y),L(a)其中I(x)R(x)是目標(biāo)公式否定后得到的子句。 用支持