謂詞演算與消解歸結(jié)原理

1、第三章 謂詞演算與消解(歸結(jié))原理,命題演算 謂詞演算 推理規(guī)則產(chǎn)生謂詞演算表達式 應(yīng)用 歸結(jié)原理,3.1 命題演算,3.1.1 符號和命題,命題演算的符號：是命題符號,命題符號代表命題，是關(guān)于現(xiàn)實世界的能分辨真假值的陳述句。 命題符號：P，Q，R，S，T,命題演算的符號：真值符號：True, false 聯(lián)結(jié)詞：∨，∧，~，=>，＝通過聯(lián)結(jié)詞可把多個命題組成合成的命題，也稱為合式公式。,

2、3.1.2 命題演算的語義,3.1 命題演算,—如兩個命題表達式 在任何真值指派下都有相同的值，則稱為是等價的（P 29 ）表2.2所示的真值表證明： P=>Q 與 ~P ∨Q 等價。—對于命題表達式 P，Q，R ~ (~P)=P ; (P∨Q) ＝ (~P=>Q),否定律：~ (P∨Q) ＝ (~P∧~Q) ~ (P∧Q) ＝ (~P∨~Q)分配律

3、：P∨(Q∧R) ＝ (P∨Q)∧(P∨R) 分配律：P∧(Q∨R)＝(P∧Q)∨(P∧R) 交換律：(P∧Q) ＝ (Q∧P) 交換律：(P∨Q) ＝ (Q∨P) 結(jié)合律：((P∧Q)∧R) ＝ (P∧(Q∧R)) 結(jié)合律：((P∨Q)∨R) ＝(P∨(Q∨R)) 置換律：(P=>Q) ＝ (~Q=>~P),3.1 命題演算,3.2 謂詞演算,命題演算中，P，Q代表一定的命題，如：P：星期四下雨而謂詞：W

4、eather（X，Y）代表日期與天氣的關(guān)系Weather（Tuesday，Rain）,可以操縱命題演算表達式 允許包含變元 Weather（X，Rain）,3.2.1 謂詞的語法和命題,3.2 謂詞演算,謂詞演算的字母表組成：（1）英文字母組合，包括大寫與小寫（2）數(shù)字集合0,1,…,9（3）下劃線如：George fires bill xxxx,謂詞演算符號包括： 1.真值符號 true 和 false

5、。 2.常元符號,第一個字符為小寫字母的符號表達式。 3.變元符號,第一個字符為大寫字母的符號表達式。 4.函詞符號,第一個字符為小寫字母的符號表達式, 函詞有一個元數(shù), 指出從定義域中映射到值域中的每個元素。,3.2 謂詞演算,例： likes (george, kate). likes (X, george). likes (george, susie). likes (X, X). likes (georg

6、e, sarah, tuesday). friends (bill, richard). friends (bill, george). friends (father (david), father (andrew)) helps (bill, george). helps (richard, bill).,3.2 謂詞演算,原子命題：是一個n元謂詞，后跟n個項，用括號括起來并用逗號分開。,常元符號

7、,項,3.2.1 謂詞的語法和命題,與謂詞相關(guān)的一個正整數(shù)稱為元數(shù)或“參數(shù)數(shù)目”，具有相同的名但元數(shù)不同的謂詞是不同的。真值true和false也是原子命題。任何原子命題都能夠用邏輯操作符將其變成謂詞演算的命題。用的聯(lián)結(jié)詞也和命題演算一樣: ∨,∧, ~, => 和＝。 當一個變元在一個命題中作為參數(shù)出現(xiàn)時,它代表的是域中不特定的對象。謂詞演算包括兩個符號, 量詞?（全稱量詞）和彐（存在量詞）, 用于限定包含變元的命題的含義

8、。,3.2.1 謂詞的語法和命題,一個量詞后面緊跟著一個變元和一個命題。例如： ? X likes (X, ice_cream).彐Y friends (Y, peter).,全稱量詞? , 表明命題對于變元的變域中的所有的值都為真。存在量詞彐, 表明該命題對于變元的變域中的一些值為真。,例：命題,3.2.1 謂詞的語法和命題,plus(two,three)equal(plus(two,three))彐xfoo(x,two,

9、plus(two,three)) ∧equal(plus(two,three),five),3.2.2 謂詞演算的語義,謂詞演算的語義提供了確定合式表達式真值的形式基礎(chǔ)。表達式的真值依賴于常元、變元、謂詞、函詞到論域中的映射，在論域中的關(guān)系的真假決定了相應(yīng)表達式的真假。例如：,friends ( george, susie )friends ( george, kate ),3.2.2 謂詞演算的語義,一個論域D上的解釋：假設(shè)論域

10、D是一個非空集合，在D上的一個解釋把論域D的實體指派給一個謂詞演算表達式的每一個常元、變元、謂詞及函詞符號，于是有：1）每一個常元指派了D的一個元素。2）對每一個變元，指派D的一個非空集合，這是該變元的變域。3）每個n元謂詞P定義在論域D中的n個參數(shù)上，并定義了從Dn到{T，F(xiàn)}的一個映射。4) 每個m元函詞f定義在論域D的m個參數(shù)上，并定義了從Dm到{T，F(xiàn)}的一個映射。在一種解釋下，一個表達式的意義是在該解釋下的一個真值

11、指派。,3.2.2 謂詞演算的語義,謂詞演算表達式的真值設(shè)有表達式E和在非空論域D上對E的一個解釋I，E的真值按以下規(guī)律決定：1）一個常元的值是根據(jù)I指派給它的D的一個元素。2）一個變元的值是根據(jù)I指派給它的D的一個元素集合。3）一個函詞的值是根據(jù)由I指派給它的參數(shù)值計算得到的D的元素。4）真值符號true的值是T，false的值是F。5）原子命題的值或者為T，或者為F，取決于解釋I。6）如果一個命題的值為F，則其否定式為

12、T，否則為F。7）如果…11)如果對于在解釋I下的X的每一個指派，S的值為T，則? X S為T，否則為F。12）如果在解釋I下存在X的一個指派使得S的值為T，則彐X S為T，否則為F。,3.2.2 謂詞演算的語義,變元：likes(george,X) 這個變元名可以由任何其他變元名代替，不會改變表達式的意思。,變元的量詞約束是謂詞演算語義的重要部分 在謂詞演算中,變元有兩種約束使用的方法:在特定解釋下,命題對變元的變域中的所

13、有常元指派為真,則稱該變元是全稱性變元。代表全稱量詞的符號是? ,括號常常用于表示量詞的約束范圍 存在性變元。至少存在變元的變域中的一個值使包含變元的表達式為真時，表達式才為真。代表存在量詞的符號是彐,3.2.2 謂詞演算的語義,否定與全稱量詞、存在量詞之間的關(guān)系 。對于謂詞 P, Q, 變元 X, Y有： ~彐X P(X) ＝ ? X ~P(X) ~ ?X P(X) ＝ 彐X ~P(X) 彐X P(X) ＝ 彐Y P(

14、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)生謂詞演算表達式,3.3.1 推理規(guī)則 推理規(guī)則：實際上是一個從其他謂詞演算命題產(chǎn)生新的謂詞演算命題的機械方法。亦即推理規(guī)則產(chǎn)生基于給定邏輯斷言的句法形式的新命題。當每個由邏輯表達式集S上的推理規(guī)則產(chǎn)生的命題X都是S的邏輯

15、結(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). hu

16、man(Socrates). X: mortal (Socrates).,human(Socrates) => mortal(Socrates),合一算法,3.3.2 合一,偽代碼寫的函數(shù) Unify 用于計算兩個謂詞表達式的最一般合一,是判斷兩個謂詞表達式匹配所需的一種代入算法合一表明了兩個或多個表達式在什么條件下可以稱為等價的。,以兩個謂詞演算表達式為參數(shù),若這兩個表達式可以合一, 則返回最

17、一般合一代入,否則返回 FAIL。,3.3.2 合一,function unify (E1, E2) ;begincase …end %end caseend,首先,它遞歸地試圖對表達式的初始成分合一。如果成功, 這次合一返回的任何代入式被用到兩個表達式的剩下部分, 然后以這兩個表達式為參數(shù)。終止條件是兩個參數(shù)之一為一個符號 (謂詞名, 函詞名, 變元, 常元 ), 或兩個表達式的每一元素都已匹配了。,3.3.2 合

18、一,caseE1, E2 或者是常元或者是空表: %遞歸終止。 If E1 ＝ E2 then return { } else return FAIL; E1是一個變元: if E1在E2中出現(xiàn) then return FAIL else return {E2/E1};E2是一個變元:

19、if E2在E1中出現(xiàn) then return FAIL else return {E1/E2}; 其他情況: % E1和E2都是表,3.3.2 合一,begin HE1:= E1的第一個元素; HE2:= E2的第一個元素; SUBS1:= unify (HE1, HE2); if SUBS1 ＝ FAI

20、L then return FAIL TE1:= apply (SUBS1, E1的后半部) TE2:= apply (SUBS1, E2的后半部) SUBS2:= unify (TE1, TE2 ), if SUBS2 ＝ FAIL then return FAIL else return SUBS1與SUBS2 的合成 end,3.3.3 合一的一個例子,通過以下調(diào)用來跟蹤算

21、法的運行過程： unify ((parents X (father X) (mother bill)), (parents bill (father bill) Y )) 第一次調(diào)用: unify (parents, parents) 這次調(diào)用成功, 返回代入集 { }。 第二次調(diào)用: unify (X, bill) 這次

22、調(diào)用成功,返回代入 {bill / X }。,3.3.3 合一的一個例子,在此基礎(chǔ)上又調(diào)用: unify (((father bill) (mother bill)), ((father bill) Y )) 導致調(diào)用: (1) unify((father bill),(father bill)) unify (father, father) unify (bill, bill) unify (( )

23、, ( )) 所有的調(diào)用都成功,返回空代入集 { }。(2) unify ((mother bill), Y),3.4 應(yīng)用 :一個基于邏輯的金融投資輔助決策程序,一位有三個人需贍養(yǎng),有$22000存款,每年有$25000的穩(wěn)定收入的投資者的情況,可產(chǎn)生一個由下列命題組成的邏輯系統(tǒng): 1.savings (inadequate) => investment (savings). 2.savings (adequat

24、e)∧income (adequate ) => investment (stocks). 3. Savings (adequate)∧income (inadequate) => investment (combination). 4. ? X amountsaved (X)∧彐Y(dependents (Y)∧ greater (X, minsavings (Y))) => savings (adequat

25、e).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).

26、7. ? X earnings (X, steady)∧彐Y (dependents (Y) ∧ ~greater (X, minincome (Y))) => income (inadequate). 8. ? X earnings (X, unsteady) => income (inadequate). 9. amountsaved (22000).10. earnings (25000, steady)

27、.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的前提合一,得: 13. savings (adequate),將第12、13條命題檢驗第3條命題得到其前

28、提為真。于是運用假言推理后得到結(jié)論: investment (combination), 這就是給投資者的建議。,(存款的人應(yīng)該把他們多余的錢分別用于存款和買股票，在增加存款做保險的同時試圖通過做股票以增加收入。),3.5 消解定理證明,消解是一種應(yīng)用于謂詞演算中的定理證明技術(shù)，是人工智能問題求解的一個組成部分。消解描述了如何用最少的合一次數(shù)在一個子句數(shù)據(jù)庫中發(fā)現(xiàn)矛盾的方法。,具體方法如下：對所要證明的命題取反，把它加到已知為真的公理

29、集中，然后用消解推理規(guī)則證明這將導致一個矛盾，一旦證明了否定目標與已知公理集不一致，就能推導出原來的目標與已知公理集是一致的，從而定理得證。,3.5 消解定理證明,3.5.1 引言消解否證包含以下步驟：把前提或公理轉(zhuǎn)換成子句形式。把求證目標的否定的子句形式加到公理集合中。 對所有這些子句進行消解，產(chǎn)生它們的邏輯結(jié)果子句。 用產(chǎn)生空子句的方法來得出矛盾。 否定目標的否證在用于產(chǎn)生空子句的代換下為真。,3.5.1 引言,消解否

30、證需要所有公理和否定目標為子句形式,子句形式把一個邏輯數(shù)據(jù)庫表示為一個文字析取式的集合。一個文字是一個原子表達式或原子表達式的否定。,消解作用于兩個子句, 其中一個包含某文字,另一個包含該文字的否定,如果這些文字包含變元,必須用合一使它們相等。一個新的子句就此產(chǎn)生了,它包含兩個子句中所有謂詞的析取,除了該文字和它的否定以外。,3.5.1 引言,用消解所做的等價的推理把以下謂詞演算公式變換成子句形式 ： 謂詞形式

31、 子句形式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) (ani

32、mal (Y)→ die (Y)) ~ animal (Y) ∨die (Y),證明：fido will die,對目標“取反” ：,~ die ( fido ),~dog(X) ∨ animal(X). ~animal(Y) ∨ die(Y).  ｛Y/X｝ dog(fido). ~dog(Y) ∨ die(Y). { fido/Y｝

33、  die(fido). ~die(fido).     圖 “死狗”問題消解證明,3.5.1 引言,,,,,,,,3.5.2 為消解否證產(chǎn)生子句形式,本節(jié)提出一個由一系列變換組成的算法，這些變換可以把任何謂詞演算表達式歸約為子句形式，在此過程中保持其真值、一般性和不可滿足性不變。,即如果在原謂詞演算表達式中存在一個矛盾，則其子句形式

34、中也存在一個矛盾，變換不犧牲消解否證的完備性。,3.5.2 為消解否證產(chǎn)生子句形式,設(shè)X,Y,Z,W表示變元；l,m,n表示常元；a,b,c,d,e表示謂詞名。要歸納為子句的表達式：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)

35、］∨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)∨

36、 ~ b(X)］∨[c(X,l)∧[~ c(Y,Z)]∨d(X,Y))])∨e(W),3.5.2 為消解否證產(chǎn)生子句形式,斯柯倫標準化：去掉所有的存在量詞,彐Z（foo(Y，Z)),foo(Y，k),斯柯倫常元,如果謂詞中含有多個參數(shù)，而彐約束變元在?約束變元的約束范圍內(nèi)，則彐約束變元必須是那些其他變元的函數(shù)。,如： （?X）(彐Y)(mother(X,Y)),3.5.2 為消解否證產(chǎn)生子句形式,6. (? X)(? Z)(? W)

37、([ ~ 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)∧[~ c(Y,Z)]∨d(X,Y))])∨e(W),,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

38、,l)∨e(W)］∧ [~ a(X) ∨ ~ b(X)∨ ~ c(f(X), Z)∨d(X, f(X))∨e(W)］,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),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)

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

40、通過了歷史考試并中了彩票的人是快樂的。任何肯學習或幸運的人可以通過所有考試, John不學習但很幸運,任何人只要是幸運的就能中彩。John快樂嗎?",? X (pass (X, history)∧win (X, lottery) →happy (X) ) ? X ?Y ( study (X)∨lucky (X) → pass (X,Y) )~study (john) ∧ lucky (john) ? X (l

41、ucky (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,

42、 history)∧win (X, lottery) →happy (X) ) ? X ?Y ( study (X)∨lucky (X) → pass (X,Y) )~study (john) ∧ lucky (john) ? X (lucky (X)→win (X, lottery) ),將這四個謂詞演算命題轉(zhuǎn)換成子句形式:,3.5.3 消解證明過程,~ pass(X,history)∨ ~ win(U,lott

43、ery)∨ ~ lucky(U)win(X,lottery)∨happy(X)  ｛U/X｝  ~ pass(U,history)∨ ~ happy(john). happy(U)∨ ~ lucky(U).  ｛john/U｝  lucky(john). ~ pass(john,history)∨

44、 ~ lucky(john).   ~ pass(john,history). ~ lucky(∨)∨pass(V,W).  ｛john/V,history/W｝ lucky(john). ~ lucky(john).    圖 “快樂學生”問題的消解否證,,,,,,,,

45、,,,,子句 1,子句 6,子句 7,,子句 5,子句 3,子句 5,,子句集及其化簡,子句和子句集： 定義3.14 原子謂詞公式及其否定統(tǒng)稱為文字。 定義3.15 任何文字的析取式稱為子句。 定義3.16 不含任何文字的子句稱為空子句。 由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的。 空子句一般被記為□或NIL。

46、定義3.17 由子句或空子句所構(gòu)成的集合稱為子句集。,在謂詞邏輯中，任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集。,(? X) (［a(X)∧b(X)］→ ［c(X, l )∧(彐Y) ((彐Z)［c(Y，Z)］→d(X,Y) ) ］)∨ (? X) (e(X)),其化簡步驟如下：消去連接詞“→”和“?” 減少否定符號的轄域?qū)ψ冊獦藴驶?化為前束范式消去存在量詞 化為Skolem標準形 消去全稱量詞

47、消去合取詞 更換變量名稱,在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標準子句集是 不唯一的。 這樣，當原謂詞公式為非永假時，它與其標準子句集并不等價。但當原謂詞公式為永假（或不可滿足）時，其標準子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。 這個結(jié)論很重要，是歸結(jié)原理的主要依據(jù)，可用定理的形式來描述。,歸結(jié)原理基本思想: 首先把欲證明問題的結(jié)論否定，并加入子句集，

48、得到一個擴充的子句集S'。然后設(shè)法檢驗子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進行歸結(jié)，直至導出空子句或不能繼續(xù)歸結(jié)為止。 歸結(jié)原理包括: 命題邏輯歸結(jié)原理 謂詞邏輯歸結(jié)原理,例3.9 設(shè)C1 =﹁P ∨ Q ，C2=﹁Q，C3=P，求C1、C2、C3的歸結(jié)式C123。,簡單的例子：,解：（1）若先對

49、C1、C2歸結(jié),（2）若先對C1、C3歸結(jié),歸結(jié)樹,如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果：即其歸結(jié)過程是不唯一的。,3.5.3 歸結(jié)證明過程,例2： 假設(shè): “所有不貧窮并且聰明的人是快樂的。那些看書的人是不笨的。John能看書并且富有。快樂的人過著激動人心的生活。你能發(fā)現(xiàn)誰過著激動人心的生活嗎?",把上述故事翻譯成謂詞演算表達式:?X((~ poor(X)∧smart(X))→happy(X)?Y( read

50、(Y)→smart(Y))read(john)∧ ~ poor(john)?Z( happy(Z)→exciting(Z)),否定目標是：~ 彐 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.~ excit

51、ing(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) ~ happy(Z)∨exciting(Z)  ｛Z/W｝  ~ happy(Z)

52、 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,這個例子的消解否證如圖所示：,｛john/Y｝,~ read(jo

53、hn),read(john),,,,,,子句 4,子句 3,3.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(Y)∨smart(Y) ｛Y/X｝&

54、#160; poor(Y)∨ ~ read(Y) ~ poor(john) ｛john/Y｝,,,,,,,,~ read(john),read(john),,,,,,~ exciting(W) ~ happy(Z)∨exciting(Z)  ｛Z/W｝  ~ happy(Z) poor(X)∨ ~ smar

55、t(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é)法求更為復雜問題例子,例1：某記者到一孤島采訪，遇到了一個難題，即島上有許多人說假話，因而難以保證新

56、聞報道的正確性，不過有一點他是清楚的，這個島上的人有一特點：說假話的人從來不說真話，說真話的人也從來不說假話。一次記者遇到了孤島上的三個人，為了弄清楚誰說真話，誰說假話，他向這三個人中的每一個都提了一個同樣的問題，即 “誰是說謊者？” 結(jié)果A答“B和C都是說謊者”， B答“A和C都是說謊者”， C答“A和B中至少有一個 是說謊者”， 試問記者如何從回答中理出頭緒。,3.6 用歸結(jié)

57、法求更為復雜問題例子,以A，B，C三個命題來表示A，B，C三個是老實人（不說謊）,A答“B和C都是說謊者”B答“A和C都是說謊者”C答“A和B中至少有一個 是說謊者”,如果A說真話，則B和C一定說謊，因此有：A → ~ B ∧ ~ C 如果A說假話，則B和C中至少有一人說真話,因此有:~ A → B ∨ C以同樣的推理方式可得到：如果B說真話, 如果B說假話

58、 B → ~ A ∧ ~ C ~ B → A ∨ C如果C說真話, 如果C說假話 C → ~ A ∨ ~ B ~ C → A ∧ B,3.6 用歸結(jié)法求更為復雜問題例子,對以上蘊含式加以推理,并化成子句形式,可得： ~ A ∨ ~ B

59、 （1） ~ A ∨ ~ C （2） A ∨ B ∨ C （3） ~ B ∨ ~ C （4）

60、 ~ A ∨ ~ B ∨ ~ C （5） A ∨ C （6） B ∨ C （7）,3.6 用歸結(jié)法求更為復雜問題例子,（1）和（7）歸結(jié)，得： ~ A ∨ C （8

61、）（2）和（8）歸結(jié)，得： ~ A （9）（6）和（9）歸結(jié)，得： C （10）（4）和（10）歸結(jié)，得： ~ B （11）,說明？ 誰是說謊者？,A和B都是說謊者，而C是老實人,3.6 用歸結(jié)法求更為復雜問題例子,例2: 四對夫婦中，王結(jié)婚時，周送了禮；周和錢是同一排球隊的隊員；李的愛人是陳的愛人的表哥；陳夫婦與鄰居吵架，徐、周、吳的愛人都去助戰(zhàn)；李、徐、周結(jié)婚前住一間宿舍，試用歸結(jié)法求王、

62、周、錢、陳、李、徐、吳、孫八人誰是男？誰是女？誰和誰是夫婦？,（1）女（李）（2）女（李） → 女（徐）即：NOT 女（李）∨ 女（徐）（3）女（李） → 女（周）即：NOT 女（李）∨ 女（周）（4）女（周） → 女（錢）即：NOT 女（周）∨ 女（錢）（5）女（李）∧ 女（徐）∧ 女（周） ∧ 女（錢）→ 男（王） ∧男（陳） ∧男（吳） ∧男（孫）,則可解得男的是：王、陳、吳、孫則可解得女的是：李、徐、周、錢,（ 6）

63、~couple（王，周）（ 7） ~couple （陳，李）（ 8） ~ couple （陳，徐）（ 9） ~ couple （陳，周）（10） ~ couple （吳，周）（11） ~ couple （吳，徐）（12） couple （X，Y）→男（X）∧女(Y）（13） couple （陳，李）∨夫妻（陳，徐） ∨夫妻（陳，周）∨夫妻（陳，錢）,例2: 四對夫婦中，王結(jié)婚時，周送了禮；周和錢是同一排球隊的隊員；李的愛人

64、是陳的愛人的表哥；陳夫婦與鄰居吵架，徐、周、吳的愛人都去助戰(zhàn)；李、徐、周結(jié)婚前住一間宿舍，試用消解法求王、周、錢、陳、李、徐、吳、孫八人誰是男？誰是女？誰和誰是夫婦？,男：王、陳、吳、孫女：李、徐、周、錢,（14）couple（陳，錢） (13)(7)(8)(9)歸結(jié);（15）couple(吳,周)∨ couple(吳,徐)∨ couple(吳,李)（16）couple (吳,李) （15）（10）（11）進行歸結(jié);

65、（17） couple （王，周）∨ couple （王，徐）（18） couple （王，徐） （17）與（6）歸結(jié)（19） couple （孫，周）,3.6 用歸結(jié)法求更為復雜問題例子,例3: 某村農(nóng)民王某被害，有四個嫌疑犯A，B，C，D，公安局派出五個偵察員，他們帶回的信息各不一樣，甲說A，B中至少有一人作案，乙說B ，C中至少有一人作案，丙說C，D中至少有一人作案，丁說A，C中至少有一人與此案無關(guān)，戊說B ，D中至少有

66、一人與此案無關(guān)，如果這五個偵察員的話都是可靠的，試用消解法求出誰是罪犯。,3.6 用歸結(jié)法求更為復雜問題例子,（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

67、） C是罪犯。 （3）、（8）歸結(jié)。,3.7 歸結(jié)演繹推理的歸結(jié)策略-廣度優(yōu)先策略,廣度優(yōu)先是一種窮盡子句比較的復雜搜索方法。設(shè)初始子句集為S0，廣度優(yōu)先策略的歸結(jié)過程可描述如下： (1) 從S0出發(fā)，對S0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1; (2) 用S0中的子句與S1中的子句進行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2; (

68、3) 用S0和S1中的子句與S2中的子句進行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3; 如此繼續(xù)，知道得出空子句或不能再繼續(xù)歸結(jié)為止。,例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é)出了許多無用的子句，既浪費時間，又浪費空間。但是

69、，這種策略有一個有趣的特性，就是當問題有解時保證能找到最短歸結(jié)路徑。它是一種完備的歸結(jié)策略。寬度優(yōu)先對大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對小問題卻仍是一種比較好的歸結(jié)策略。,3.7 歸結(jié)演繹推理的歸結(jié)策略-廣度優(yōu)先策略,支持集策略是沃斯(Wos)等人在1965年提出的一種歸結(jié)策略。它要求每一次參加歸結(jié)的兩個親本子句中，至少應(yīng)該有一個是由目標公式的否定所得到的子句或它們的后裔。可以證明支持集策略是完備的，即當子句集為不可滿足時，則