謂詞演算和消解歸結(jié)基本原理

1、第三章 謂詞演算與消解()原理命題演算 謂詞演算 推理規(guī)則產(chǎn)生謂詞演算表達(dá)式3.1 命題演算 3.1.1 符號(hào)和命題命題演算的符號(hào)：是命題符號(hào),命題符號(hào)代表命題，是關(guān)于現(xiàn)實(shí)世界的能分辨真假值的陳述句。 命題符號(hào)：P，Q，R，S，T命題演算的符號(hào)：真值符號(hào)：True, false 聯(lián)結(jié)詞：，=，通過聯(lián)結(jié)詞可把多個(gè)命題組成合成的命題，也稱為合式公式。3.1.2 命題演算的語義3.1 命題演算 如兩個(gè)命題表達(dá)式 在任何真值指派下都有相同的值，則稱為是等價(jià)的（P 29 ）表所示的真值表證明： P=Q 與 P Q 等價(jià)。對(duì)于命題表達(dá)式 P，Q，R (P)=P ; (PQ) (P=Q)否定律： (PQ)

2、(PQ) (PQ) (PQ)分配律：P(QR) (PQ)(PR) 分配律：P(QR)(PQ)(PR) 交換律：(PQ) (QP) 交換律：(PQ) (QP) 結(jié)合律：(PQ)R) (P(QR) 結(jié)合律：(PQ)R) (P(QR) 置換律：(P=Q) (Q=P) 3.1 命題演算 3.2 謂詞演算命題演算中，P，Q代表一定的命題，如：P：星期四下雨而謂詞：Weather（X，Y）代表日期與天氣的關(guān)系Weather（Tuesday，Rain） 可以操縱命題演算表達(dá)式 允許包含變?cè)?Weather（X，Rain） 3.2.1 謂詞的語法和命題 3.2 謂詞演算謂詞演算的字母表組成：（1）英文字母組合

3、，包括大寫與小寫（2）數(shù)字集合0,1,9（3）下劃線如：George fires bill xxxx 謂詞演算符號(hào)包括： 1.真值符號(hào) true 和 false。 2.常元符號(hào),第一個(gè)字符為小寫字母的符號(hào)表達(dá)式。 3.變?cè)?hào),第一個(gè)字符為大寫字母的符號(hào)表達(dá)式。 4.函詞符號(hào),第一個(gè)字符為小寫字母的符號(hào)表達(dá)式, 函詞有一個(gè)元數(shù), 指出從定義域中映射到值域中的每個(gè)元素。 3.2 謂詞演算例： likes (george, kate). likes (X, george). likes (george, susie). likes (X, X). likes (george, sarah, tue

4、sday). friends (bill, richard). friends (bill, george). friends (father (david), father (andrew) helps (bill, george). helps (richard, bill). 3.2 謂詞演算原子命題：是一個(gè)n元謂詞，后跟n個(gè)項(xiàng)，用括號(hào)括起來并用逗號(hào)分開。謂詞符號(hào)常元符號(hào)項(xiàng)3.2.1 謂詞的語法和命題與謂詞相關(guān)的一個(gè)正整數(shù)稱為元數(shù)或“參數(shù)數(shù)目”，具有相同的名但元數(shù)不同的謂詞是不同的。真值true和false也是原子命題。任何原子命題都能夠用邏輯操作符將其變成謂詞演算的命題。用的聯(lián)結(jié)詞也和

5、命題演算一樣: , , = 和。 當(dāng)一個(gè)變?cè)谝粋€(gè)命題中作為參數(shù)出現(xiàn)時(shí),它代表的是域中不特定的對(duì)象。謂詞演算包括兩個(gè)符號(hào), 量詞（全稱量詞）和彐（存在量詞）, 用于限定包含變?cè)拿}的含義。 3.2.1 謂詞的語法和命題一個(gè)量詞后面緊跟著一個(gè)變?cè)鸵粋€(gè)命題。例如： X likes (X, ice_cream).彐Y friends (Y, peter). 全稱量詞 , 表明命題對(duì)于變?cè)淖冇蛑械乃械闹刀紴檎?。存在量詞彐, 表明該命題對(duì)于變?cè)淖冇蛑械囊恍┲禐檎?。例：命題3.2.1 謂詞的語法和命題plus(two,three)equal(plus(two,three)彐xfoo(x,two,

6、plus(two,three) equal(plus(two,three),five)3.2.2 謂詞演算的語義謂詞演算的語義提供了確定合式表達(dá)式真值的形式基礎(chǔ)。表達(dá)式的真值依賴于常元、變?cè)?、謂詞、函詞到論域中的映射，在論域中的關(guān)系的真假?zèng)Q定了相應(yīng)表達(dá)式的真假。例如：friends ( george, susie )friends ( george, kate )3.2.2 謂詞演算的語義一個(gè)論域D上的解釋：假設(shè)論域D是一個(gè)非空集合，在D上的一個(gè)解釋把論域D的實(shí)體指派給一個(gè)謂詞演算表達(dá)式的每一個(gè)常元、變?cè)?、謂詞及函詞符號(hào)，于是有：1）每一個(gè)常元指派了D的一個(gè)元素。2）對(duì)每一個(gè)變?cè)?，指派D的一個(gè)

7、非空集合，這是該變?cè)淖冇颉?）每個(gè)n元謂詞P定義在論域D中的n個(gè)參數(shù)上，并定義了從Dn到T，F(xiàn)的一個(gè)映射。4) 每個(gè)m元函詞f定義在論域D的m個(gè)參數(shù)上，并定義了從Dm到T，F(xiàn)的一個(gè)映射。在一種解釋下，一個(gè)表達(dá)式的意義是在該解釋下的一個(gè)真值指派。3.2.2 謂詞演算的語義謂詞演算表達(dá)式的真值設(shè)有表達(dá)式E和在非空論域D上對(duì)E的一個(gè)解釋I，E的真值按以下規(guī)律決定：1）一個(gè)常元的值是根據(jù)I指派給它的D的一個(gè)元素。2）一個(gè)變?cè)闹凳歉鶕?jù)I指派給它的D的一個(gè)元素集合。3）一個(gè)函詞的值是根據(jù)由I指派給它的參數(shù)值計(jì)算得到的D的元素。4）真值符號(hào)true的值是T，false的值是F。5）原子命題的值或者為T，

8、或者為F，取決于解釋I。6）如果一個(gè)命題的值為F，則其否定式為T，否則為F。7）如果11)如果對(duì)于在解釋I下的X的每一個(gè)指派，S的值為T，則 X S為T，否則為F。12）如果在解釋I下存在X的一個(gè)指派使得S的值為T，則彐X S為T，否則為F。3.2.2 謂詞演算的語義 變?cè)簂ikes(george,X) 這個(gè)變?cè)梢杂扇魏纹渌冊(cè)?，不?huì)改變表達(dá)式的意思。變?cè)牧吭~約束是謂詞演算語義的重要部分 在謂詞演算中,變?cè)袃煞N約束使用的方法:在特定解釋下,命題對(duì)變?cè)淖冇蛑械乃谐Ｔ概蔀檎?則稱該變?cè)侨Q性變?cè)?。代表全稱量詞的符號(hào)是 ,括號(hào)常常用于表示量詞的約束范圍 存在性變?cè)?。至少存在?/p>

9、元的變域中的一個(gè)值使包含變?cè)谋磉_(dá)式為真時(shí)，表達(dá)式才為真。代表存在量詞的符號(hào)是彐3.2.2 謂詞演算的語義否定與全稱量詞、存在量詞之間的關(guān)系 。對(duì)于謂詞 P, Q, 變?cè)?X, Y有： 彐X P(X) X P(X) X P(X) 彐X P(X) 彐X P(X) 彐Y P(Y) X Q(X) Y Q(Y) X (P(X)Q(X) ) X P(X) Y Q(Y) 彐X (P(X)Q(X) ) 彐X P(X)彐Y Q(Y) 3.3 推理規(guī)則產(chǎn)生謂詞演算表達(dá)式 3.3.1 推理規(guī)則 推理規(guī)則：實(shí)際上是一個(gè)從其他謂詞演算命題產(chǎn)生新的謂詞演算命題的機(jī)械方法。亦即推理規(guī)則產(chǎn)生基于給定邏輯斷言的句法形式的新命

10、題。當(dāng)每個(gè)由邏輯表達(dá)式集S上的推理規(guī)則產(chǎn)生的命題X都是S的邏輯結(jié)果,則稱該邏輯規(guī)則是合理的。S: X human(X) = mortal(X). human(Socrates). X: mortal (Socrates).假言推理和消解原理都是合理的推理規(guī)則的例子。假言推理：如果命題P，P = Q為真，應(yīng)用假言推理得出Q為真。S: X human(X) = mortal(X). human(Socrates). X: mortal (Socrates).human(Socrates) = mortal(Socrates)？ human(X) Socrates合一算法3.3.2 合一 偽代碼寫的

11、函數(shù) Unify 用于計(jì)算兩個(gè)謂詞表達(dá)式的最一般合一是判斷兩個(gè)謂詞表達(dá)式匹配所需的一種代入算法合一表明了兩個(gè)或多個(gè)表達(dá)式在什么條件下可以稱為等價(jià)的。以兩個(gè)謂詞演算表達(dá)式為參數(shù),若這兩個(gè)表達(dá)式可以合一, 則返回最一般合一代入,否則返回 FAIL。3.3.2 合一 function unify (E1, E2) ;begincase end %end caseend首先,它遞歸地試圖對(duì)表達(dá)式的初始成分合一。如果成功, 這次合一返回的任何代入式被用到兩個(gè)表達(dá)式的剩下部分, 然后以這兩個(gè)表達(dá)式為參數(shù)。終止條件是兩個(gè)參數(shù)之一為一個(gè)符號(hào) (謂詞名, 函詞名, 變?cè)? 常元 ), 或兩個(gè)表達(dá)式的每一元素都已

12、匹配了。3.3.2 合一caseE1, E2 或者是常元或者是空表: %遞歸終止。 If E1 E2 then return else return FAIL; E1是一個(gè)變?cè)? if E1在E2中出現(xiàn) then return FAIL else return E2/E1;E2是一個(gè)變?cè)? if E2在E1中出現(xiàn) then return FAIL else return E1/E2; 其他情況: % E1和E2都是表 3.3.2 合一begin HE1:= E1的第一個(gè)元素; HE2:= E2的第一個(gè)元素; SUBS1:= unify (HE1, HE2); if SUBS1 FAIL the

13、n return FAIL TE1:= apply (SUBS1, E1的后半部) TE2:= apply (SUBS1, E2的后半部) SUBS2:= unify (TE1, TE2 ), if SUBS2 FAIL then return FAIL else return SUBS1與SUBS2 的合成 end3.3.3 合一的一個(gè)例子通過以下調(diào)用來跟蹤算法的運(yùn)行過程： unify (parents X (father X) (mother bill), (parents bill (father bill) Y ) 第一次調(diào)用: unify (parents, parents) 這次調(diào)

14、用成功, 返回代入集 。 第二次調(diào)用: unify (X, bill) 這次調(diào)用成功,返回代入 bill / X 。 3.3.3 合一的一個(gè)例子在此基礎(chǔ)上又調(diào)用: unify (father bill) (mother bill), (father bill) Y ) 導(dǎo)致調(diào)用: (1) unify(father bill),(father bill) unify (father, father) unify (bill, bill) unify ( ), ( ) 所有的調(diào)用都成功,返回空代入集 。(2) unify (mother bill), Y)bill/X, (mother bill)

15、/Y3.4 應(yīng)用 :一個(gè)基于邏輯的金融投資輔助決策程序一位有三個(gè)人需贍養(yǎng),有$22000存款,每年有$25000的穩(wěn)定收入的投資者的情況,可產(chǎn)生一個(gè)由下列命題組成的邏輯系統(tǒng): 1.savings (inadequate) = investment (savings). 2.savings (adequate)income (adequate ) = investment (stocks). 3. Savings (adequate)income (inadequate) = investment (combination). 4. X amountsaved (X)彐Y(dependents

16、(Y) greater (X, minsavings (Y) = savings (adequate).5. X amountsaved (X) 彐Y (dependents (Y) greater (X, minsavings (Y) = savings (inadequate). 3.4 應(yīng)用 6. X earnings (X, steady) 彐Y (dependents (Y) greater (X, minincome(Y) = income (adequate). 7. X earnings (X, steady)彐Y (dependents (Y) greater (X, min

17、income (Y) = income (inadequate). 8. X earnings (X, unsteady) = income (inadequate). 9. amountsaved (22000).10. earnings (25000, steady).11. dependents (3).其中: minsavings (X) = 5000 * X; minincome (X) = 15000 + (4000 * X) 3.4 應(yīng)用 第一步把第10、11與第7的前提合一, 得: 12. Income (inadequate) . 第二步把第9、11與第4的前提合一,得: 1

18、3. savings (adequate)將第12、13條命題檢驗(yàn)第3條命題得到其前提為真。于是運(yùn)用假言推理后得到結(jié)論: investment (combination), 這就是給投資者的建議。(存款的人應(yīng)該把他們多余的錢分別用于存款和買股票，在增加存款做保險(xiǎn)的同時(shí)試圖通過做股票以增加收入。) 3.5 消解定理證明 消解是一種應(yīng)用于謂詞演算中的定理證明技術(shù)，是人工智能問題求解的一個(gè)組成部分。消解描述了如何用最少的合一次數(shù)在一個(gè)子句數(shù)據(jù)庫中發(fā)現(xiàn)矛盾的方法。具體方法如下：對(duì)所要證明的命題取反，把它加到已知為真的公理集中，然后用消解推理規(guī)則證明這將導(dǎo)致一個(gè)矛盾，一旦證明了否定目標(biāo)與已知公理集不一致

19、，就能推導(dǎo)出原來的目標(biāo)與已知公理集是一致的，從而定理得證。3.5 消解定理證明 3.5.1 引言消解否證包含以下步驟：把前提或公理轉(zhuǎn)換成子句形式。把求證目標(biāo)的否定的子句形式加到公理集合中。 對(duì)所有這些子句進(jìn)行消解，產(chǎn)生它們的邏輯結(jié)果子句。 用產(chǎn)生空子句的方法來得出矛盾。 否定目標(biāo)的否證在用于產(chǎn)生空子句的代換下為真。3.5.1 引言 消解否證需要所有公理和否定目標(biāo)為子句形式 子句形式把一個(gè)邏輯數(shù)據(jù)庫表示為一個(gè)文字析取式的集合。一個(gè)文字是一個(gè)原子表達(dá)式或原子表達(dá)式的否定。消解作用于兩個(gè)子句, 其中一個(gè)包含某文字,另一個(gè)包含該文字的否定,如果這些文字包含變?cè)?必須用合一使它們相等。一個(gè)新的子句就此產(chǎn)

20、生了,它包含兩個(gè)子句中所有謂詞的析取,除了該文字和它的否定以外。3.5.1 引言 用消解所做的等價(jià)的推理把以下謂詞演算公式變換成子句形式 ： 謂詞形式 子句形式1.All dogs are animals (X) (dog (X) animal (X) dog (X) animal (X)2.Fido is a dog dog ( fido ) dog ( fido )3.all animals will die (Y) (animal (Y) die (Y) animal (Y) die (Y) 證明：fido will die對(duì)目標(biāo)“取反” ： die ( fido ) dog(X) an

21、imal(X). animal(Y) die(Y). Y/X dog(fido). dog(Y) die(Y). fido/Y die(fido). die(fido). 圖 “死狗”問題消解證明 3.5.1 引言3.5.2 為消解否證產(chǎn)生子句形式本節(jié)提出一個(gè)由一系列變換組成的算法，這些變換可以把任何謂詞演算表達(dá)式歸約為子句形式，在此過程中保持其真值、一般性和不可滿足性不變。即如果在原謂詞演算表達(dá)式中存在一個(gè)矛盾，則其子句形式中也存在一個(gè)矛盾，變換不犧牲消解否證的完備性。3.5.2 為消解否證產(chǎn)生子句形式設(shè)X,Y,Z,W表示變?cè)?；l,m,n表示常元；a,b,c,d,e表示謂詞名。要?dú)w納為子句的

22、表達(dá)式：1.( X) (a(X)b(X) c(X, l )(彐Y) (彐Z)c(Y，Z)d(X,Y) ) ) ( X) (e(X) 2.( X) ( a(X) b(X)c(X，l)(彐y) (彐Z)c(Y,Z)d(X,Y)( ）(e(X)）3.( X) ( a(X) b(X)c(X, l)(彐Y) ( Z) c(Y,Z)d(X,Y)( X)(e(X)4.( X) ( a(X) b(X)c(X, l ) (彐Y) ( Z) c(Y,Z)d(X,Y)( W) (e(W) 所有量詞移到最左邊而不改變其次序 5.( X)(彐Y)( Z)( W) ( a(X) b(X)c(X,l) c(Y,Z)d(X,

23、Y)e(W)前束范式斯柯倫標(biāo)準(zhǔn)化去掉所有的存在量詞3.5.2 為消解否證產(chǎn)生子句形式斯柯倫標(biāo)準(zhǔn)化：去掉所有的存在量詞彐Z（foo(Y，Z)foo(Y，k)彐X（dog(X)dog(fido)斯柯倫常元如果謂詞中含有多個(gè)參數(shù)，而彐約束變?cè)诩s束變?cè)募s束范圍內(nèi)，則彐約束變?cè)仨毷悄切┢渌冊(cè)暮瘮?shù)。如： （X）(彐Y)(mother(X,Y)（X） (mother(X,m(X)3.5.2 為消解否證產(chǎn)生子句形式6. ( X)( Z)( W) ( a(X) b(X)c(X,l) c (f(X),Z)d(X,f(X)e(W) 5.( X)(彐Y)( Z)( W) ( a(X) b(X)c(X,l)

24、c(Y,Z)d(X,Y)e(W)斯柯倫標(biāo)準(zhǔn)化后去掉全稱量詞7.( a(X) b(X)c(X, l)( c(f(X), Z)d(X, f(X)e(W)8. a(X) b(X)c(X,l)e(W) a(X) b(X) c(f(X), Z)d(X, f(X)e(W)轉(zhuǎn)換成析取式的合取每個(gè)合取式為一個(gè)分離的子句9a: a(X) b(X)c(X,l)e(W)9b: a(X) b(X) c(f(X), Z)d(X, f(X)e(W)把分離的變?cè)獨(dú)w一化10a: a(X) b(X)c(X,l)e(W)10b: a(U) b(U) c(f(U), Z) d(U, f(U)e(V) 3.5.3 消解證明過程例1:

25、 “幸運(yùn)學(xué)生”的故事: “任何通過了歷史考試并中了彩票的人是快樂的。任何肯學(xué)習(xí)或幸運(yùn)的人可以通過所有考試, John不學(xué)習(xí)但很幸運(yùn),任何人只要是幸運(yùn)的就能中彩。John快樂嗎? 1. 第一步把這些句子變成謂詞形式:定義一些函詞：pass(x,y) , win(x, lottery) , happy(x) , study(X), lucky(x)3.5.3 消解證明過程“任何通過了歷史考試并中了彩票的人是快樂的。任何肯學(xué)習(xí)或幸運(yùn)的人可以通過所有考試, John不學(xué)習(xí)但很幸運(yùn),任何人只要是幸運(yùn)的就能中彩。John快樂嗎? X (pass (X, history)win (X, lottery) h

26、appy (X) ) X Y ( study (X)lucky (X) pass (X,Y) )study (john) lucky (john) X (lucky (X)win (X, lottery) ) 3.5.3 消解證明過程1. pass (X, history)win (X, lottery)happy (X)2. study (Y)pass (Y, Z)3. lucky (V)pass (V,W) 4. study (john)5.lucky (john)6. lucky (U)win (U, lottery) X (pass (X, history)win (X, lotter

27、y) happy (X) ) X Y ( study (X)lucky (X) pass (X,Y) )study (john) lucky (john) X (lucky (X)win (X, lottery) ) 將這四個(gè)謂詞演算命題轉(zhuǎn)換成子句形式:加入子句形式的否定目標(biāo):7. happy (john)3.5.3 消解證明過程 pass(X,history) win(U,lottery) lucky(U)win(X,lottery)happy(X) U/X pass(U,history) happy(john). happy(U) lucky(U). john/U lucky(john).

28、 pass(john,history) lucky(john). pass(john,history). lucky()pass(V,W). john/V,history/W lucky(john). lucky(john). 圖 “快樂學(xué)生”問題的消解否證子句 1子句 6子句 7子句 5子句 3子句 5John是快樂的子句集及其化簡子句和子句集： 定義3.14 原子謂詞公式及其否定統(tǒng)稱為文字。 定義3.15 任何文字的析取式稱為子句。 定義3.16 不含任何文字的子句稱為空子句。 由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的。 空子句一般被記為或NIL。

29、 定義3.17 由子句或空子句所構(gòu)成的集合稱為子句集。 在謂詞邏輯中，任何一個(gè)謂詞公式都可以通過應(yīng)用等價(jià)關(guān)系及推理規(guī)則化成相應(yīng)的子句集。( X) (a(X)b(X) c(X, l )(彐Y) (彐Z)c(Y，Z)d(X,Y) ) ) ( X) (e(X)a. a(X) b(X)c(X,l)e(W)b.a(U) b(U) c(f(U), Z) d(U, f(U)e(V)其化簡步驟如下：消去連接詞“”和“” 減少否定符號(hào)的轄域?qū)ψ冊(cè)獦?biāo)準(zhǔn)化 化為前束范式消去存在量詞 化為Skolem標(biāo)準(zhǔn)形 消去全稱量詞 消去合取詞 更換變量名稱 在上述化簡過程中，由于在消去存在量詞時(shí)所用的Skolem函數(shù)可以不同，

30、因此化簡后的標(biāo)準(zhǔn)子句集是 不唯一的。 這樣，當(dāng)原謂詞公式為非永假時(shí)，它與其標(biāo)準(zhǔn)子句集并不等價(jià)。但當(dāng)原謂詞公式為永假（或不可滿足）時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。 這個(gè)結(jié)論很重要，是歸結(jié)原理的主要依據(jù)，可用定理的形式來描述。歸結(jié)原理基本思想: 首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個(gè)擴(kuò)充的子句集S。然后設(shè)法檢驗(yàn)子句集S是否含有空子句，若含有空子句，則表明S是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。 歸結(jié)原理包括: 命題邏輯歸結(jié)原理 謂詞邏輯歸結(jié)原理 例3.9 設(shè)C1 =

31、P Q ，C2=Q，C3=P，求C1、C2、C3的歸結(jié)式C123。P QQP P NILP Q P QQ NIL簡單的例子： 解：（1）若先對(duì)C1、C2歸結(jié)（2）若先對(duì)C1、C3歸結(jié)歸結(jié)樹如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果：即其歸結(jié)過程是不唯一的。3.5.3 歸結(jié)證明過程例2： 假設(shè): “所有不貧窮并且聰明的人是快樂的。那些看書的人是不笨的。John能看書并且富有。快樂的人過著激動(dòng)人心的生活。你能發(fā)現(xiàn)誰過著激動(dòng)人心的生活嗎? 把上述故事翻譯成謂詞演算表達(dá)式:X( poor(X)smart(X)happy(X)Y( read(Y)smart(Y)read(john) poor(john)Z

32、( happy(Z)exciting(Z)否定目標(biāo)是： 彐 W(exciting(W) 3.5.3 歸結(jié)證明過程1.poor(X) smart(X)happy(X) 2. read(Y)smart(Y)3.read(john)4. poor(john) 5. happy(Z)exciting(Z)6. exciting(W)X( poor(X)smart(X)happy(X)Y( read(Y)smart(Y)read(john) poor(john)Z( happy(Z)exciting(Z) 彐 W(exciting(W) 變換成如下的子句:3.5.3 歸結(jié)證明過程 exciting(W)

33、 happy(Z)exciting(Z) Z/W happy(Z) poor(X) smart(X)happy(X) X/Z poor(X)smart(X) read(Y)smart(Y) Y/X poor(Y) read(Y) poor(john) 子句 6子句 5子句 1子句 2這個(gè)例子的消解否證如圖所示： john/Y read(john)read(john)子句 4子句 33.5.3 歸結(jié)證明過程 exciting(W) happy(Z)exciting(Z) Z/W happy(Z) poor(X) smart(X)happy(X) X/Z poor(X)smart(X) read(

34、Y)smart(Y) Y/X poor(Y) read(Y) poor(john) john/Y read(john)read(john) exciting(W) happy(Z)exciting(Z) Z/W happy(Z) poor(X) smart(X)happy(X) X/Z poor(X)smart(X) read(Y)smart(Y) Y/X poor(Y) read(Y) poor(john)john/Y 從歸結(jié)否證中提取答案3.6 用歸結(jié)法求更為復(fù)雜問題例子例1：某記者到一孤島采訪，遇到了一個(gè)難題，即島上有許多人說假話，因而難以保證新聞報(bào)道的正確性，不過有一點(diǎn)他是清楚的，這個(gè)

35、島上的人有一特點(diǎn)：說假話的人從來不說真話，說真話的人也從來不說假話。一次記者遇到了孤島上的三個(gè)人，為了弄清楚誰說真話，誰說假話，他向這三個(gè)人中的每一個(gè)都提了一個(gè)同樣的問題，即 “誰是說謊者？” 結(jié)果A答“B和C都是說謊者”， B答“A和C都是說謊者”， C答“A和B中至少有一個(gè) 是說謊者”， 試問記者如何從回答中理出頭緒。3.6 用歸結(jié)法求更為復(fù)雜問題例子以A，B，C三個(gè)命題來表示A，B，C三個(gè)是老實(shí)人（不說謊）A答“B和C都是說謊者”B答“A和C都是說謊者”C答“A和B中至少有一個(gè) 是說謊者”如果A說真話，則B和C一定說謊，因此有：A B C 如果A說假話，則B和C中至少有一人說真話,因此有

36、: A B C以同樣的推理方式可得到：如果B說真話, 如果B說假話 B A C B A C如果C說真話, 如果C說假話 C A B C A B3.6 用歸結(jié)法求更為復(fù)雜問題例子對(duì)以上蘊(yùn)含式加以推理,并化成子句形式,可得： A B （1） A C （2） A B C （3） B C （4） A B C （5） A C （6） B C （7）3.6 用歸結(jié)法求更為復(fù)雜問題例子（1）和（7）歸結(jié)，得： A C （8）（2）和（8）歸結(jié)，得： A （9）（6）和（9）歸結(jié)，得： C （10）（4）和（10）歸結(jié)，得： B （11）說明？ 誰是說謊者？A和B都是說謊者，而C是老實(shí)人3.6 用歸結(jié)法求更為

37、復(fù)雜問題例子例2: 四對(duì)夫婦中，王結(jié)婚時(shí)，周送了禮；周和錢是同一排球隊(duì)的隊(duì)員；李的愛人是陳的愛人的表哥；陳夫婦與鄰居吵架，徐、周、吳的愛人都去助戰(zhàn)；李、徐、周結(jié)婚前住一間宿舍，試用歸結(jié)法求王、周、錢、陳、李、徐、吳、孫八人誰是男？誰是女？誰和誰是夫婦？（1）女（李）（2）女（李） 女（徐）即：NOT 女（李） 女（徐）（3）女（李） 女（周）即：NOT 女（李） 女（周）（4）女（周） 女（錢）即：NOT 女（周） 女（錢）（5）女（李） 女（徐） 女（周） 女（錢） 男（王） 男（陳） 男（吳） 男（孫）則可解得男的是：王、陳、吳、孫則可解得女的是：李、徐、周、錢（ 6） couple（王，

38、周）（ 7） couple （陳，李）（ 8） couple （陳，徐）（ 9） couple （陳，周）（10） couple （吳，周）（11） couple （吳，徐）（12） couple （X，Y）男（X）女(Y）（13） couple （陳，李）夫妻（陳，徐） 夫妻（陳，周）夫妻（陳，錢）例2: 四對(duì)夫婦中，王結(jié)婚時(shí)，周送了禮；周和錢是同一排球隊(duì)的隊(duì)員；李的愛人是陳的愛人的表哥；陳夫婦與鄰居吵架，徐、周、吳的愛人都去助戰(zhàn)；李、徐、周結(jié)婚前住一間宿舍，試用消解法求王、周、錢、陳、李、徐、吳、孫八人誰是男？誰是女？誰和誰是夫婦？男：王、陳、吳、孫女：李、徐、周、錢（14）couple（

39、陳，錢） (13)(7)(8)(9)歸結(jié);（15）couple(吳,周) couple(吳,徐) couple(吳,李)（16）couple (吳,李) （15）（10）（11）進(jìn)行歸結(jié);（17） couple （王，周） couple （王，徐）（18） couple （王，徐） （17）與（6）歸結(jié)（19） couple （孫，周）3.6 用歸結(jié)法求更為復(fù)雜問題例子例3: 某村農(nóng)民王某被害，有四個(gè)嫌疑犯A，B，C，D，公安局派出五個(gè)偵察員，他們帶回的信息各不一樣，甲說A，B中至少有一人作案，乙說B ，C中至少有一人作案，丙說C，D中至少有一人作案，丁說A，C中至少有一人與此案無關(guān)，戊說B

40、，D中至少有一人與此案無關(guān)，如果這五個(gè)偵察員的話都是可靠的，試用消解法求出誰是罪犯。3.6 用歸結(jié)法求更為復(fù)雜問題例子（1） A B （2） B C （3）C D （4） A C （5） B D（6） B C （1）、（4）歸結(jié)；（7） B是罪犯。 （2）、（6）歸結(jié)； （8）C D （2）、（5）歸結(jié)；（9） C是罪犯。 （3）、（8）歸結(jié)。3.7 歸結(jié)演繹推理的歸結(jié)策略-廣度優(yōu)先策略廣度優(yōu)先是一種窮盡子句比較的復(fù)雜搜索方法。設(shè)初始子句集為S0，廣度優(yōu)先策略的歸結(jié)過程可描述如下： (1) 從S0出發(fā)，對(duì)S0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1; (2)

41、用S0中的子句與S1中的子句進(jìn)行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2; (3) 用S0和S1中的子句與S2中的子句進(jìn)行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3; 如此繼續(xù)，知道得出空子句或不能再繼續(xù)歸結(jié)為止。I(x)R(x)I(a)R(y)L(y)L(a)R(a)I(x) L(x)R(a)L(a)L(a)I(a)I(a)NILSS1S2例3.19 設(shè)有如下子句集： S=I(x)R(x), I(a), R(y)L(y), L(a) 用寬度優(yōu)先策略證明S為不可滿足。 寬度優(yōu)先策略的歸結(jié)樹如下：寬度優(yōu)先策略歸結(jié)出了許多無用的子句，既浪費(fèi)時(shí)間，又浪費(fèi)空間。但

42、是，這種策略有一個(gè)有趣的特性，就是當(dāng)問題有解時(shí)保證能找到最短歸結(jié)路徑。它是一種完備的歸結(jié)策略。寬度優(yōu)先對(duì)大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對(duì)小問題卻仍是一種比較好的歸結(jié)策略。3.7 歸結(jié)演繹推理的歸結(jié)策略-廣度優(yōu)先策略支持集策略是沃斯(Wos)等人在1965年提出的一種歸結(jié)策略。它要求每一次參加歸結(jié)的兩個(gè)親本子句中，至少應(yīng)該有一個(gè)是由目標(biāo)公式的否定所得到的子句或它們的后裔。可以證明支持集策略是完備的，即當(dāng)子句集為不可滿足時(shí)，則由支持集策略一定能夠歸結(jié)出一個(gè)空子句。也可以把支持集策略看成是在寬度優(yōu)先策略中引入了某種限制條件，這種限制條件代表一種啟發(fā)信息，因而有較高的效率 3.7 歸結(jié)演繹推理的歸結(jié)

43、策略-支持集策略I(x)R(x)I(a) R(y)L(y)L(a)R(a)I(x)L(x)L(a)L(a)I(a)NIL例3.20 設(shè)有如下子句集： S=I(x)R(x), I(a), R(y)L(y), L(a) 其中，I(x)R(x)為目標(biāo)公式的否定。用支持集策略證明S為不可滿足。各級(jí)歸結(jié)式數(shù)目要比寬度優(yōu)先策略生成的少但在第二級(jí)還沒有空子句。就是說這種策略限制了子句集元素的劇增，但會(huì)增加空子句所在的深度。支持集策略具有逆向推理的含義，由于進(jìn)行歸結(jié)的親本子句中至少有一個(gè)與目標(biāo)子句有關(guān)，因此推理過程可以看作是沿目標(biāo)、子目標(biāo)的方向前進(jìn)的。 3.7 歸結(jié)演繹推理的歸結(jié)策略-支持集策略主要想法是：歸

44、結(jié)過程在尋找可歸結(jié)子句時(shí)，子句集中的子句越多，需要付出的代價(jià)就會(huì)越大。如果在歸結(jié)時(shí)能把子句集中無用的子句刪除掉，這就會(huì)縮小搜索范圍，減少比較次數(shù)，從而提高歸結(jié)效率。 常用的刪除方法有以下幾種： 純文字 重言式 包孕 3.7 歸結(jié)演繹推理的歸結(jié)策略-刪除策略純文字刪除法： 如果某文字L在子句集中不存在可與其互補(bǔ)的文字L，則稱該文字為純文字。 在歸結(jié)過程中，純文字不可能被消除，用包含純文字的子句進(jìn)行歸結(jié)也不可能得到空子句，因此對(duì)包含純文字的子句進(jìn)行歸結(jié)是沒有意義的，應(yīng)該把它從子句集中刪除。 對(duì)子句集而言，刪除包含純文字的子句，是不影響其不可滿足性的。例如，對(duì)子句集 S=PQR, QR, Q, R其

45、中P是純文字，因此可以將子句PQR從子句集S中刪除。 3.7 歸結(jié)演繹推理的歸結(jié)策略-刪除策略重言式刪除法 如果一個(gè)子句中包含有互補(bǔ)的文字對(duì)，則稱該子句為重言式。例如 P(x)P(x), P(x)Q(x)P(x) 都是重言式，不管P(x)的真值為真還是為假，P(x)P(x)和P(x)Q(x)P(x)都均為真。 重言式是真值為真的子句。對(duì)一個(gè)子句集來說，不管是增加還是刪除一個(gè)真值為真的子句，都不會(huì)影響該子句集的不可滿足性。因此，可從子句集中刪去重言式。3.7 歸結(jié)演繹推理的歸結(jié)策略-刪除策略包孕刪除法 設(shè)有子句C1和C2，如果存在一個(gè)置換，使得C1C2，則稱C1包孕于C2。例如 P(x) 包孕于 P(y)Q(z) =x/y P(x) 包孕于 P(a) =a/x P(x) 包孕于 P(a)Q(z) =a/x P(x) Q(a) 包孕于 P(f(a)Q(a)R(y) =f(a)/x P(x) Q(y) 包孕于 P(a)Q(u)R(w) =a/x, u/y 對(duì)子句集來說，把其中包孕的子句刪去后，不會(huì)影