第四章歸結(jié)推理方法-浙江大學(xué)計算機學(xué)院

1、1,第三章 歸結(jié)原理（第二部分） (Chapter 3 Resolution Reasoning)(Part B),徐從富浙江大學(xué)人工智能研究所2002年第一稿2004年9月修改,2,本章的主要參考文獻：[1] 石純一 等. 《人工智能原理》. 清華大學(xué)出版社, 1993. pp11-81. （【注意】：本課件以該書中的這部分內(nèi)容為主而制作，若想更加全面地了解歸結(jié)原理及其應(yīng)用，請參見如下文獻[2]和[3]）[2]

2、陸汝鈐. 《人工智能》（下冊）. 科學(xué)出版社, 2000. pp681-728. [3] 王永慶. 《人工智能原理與方法》. 西安交通大學(xué)出版社, 1998. pp111-155. 【注】：若對定理的機械化證明的更多內(nèi)容感興趣者，可參考陸汝鈐. 《人工智能》（下冊）. 科學(xué)出版社, 2000. pp729-788. 其最新進展可參考我國數(shù)學(xué)家吳文俊院士的相關(guān)論文，不過，他的研究工作對數(shù)學(xué)要求很高！,3,前言命題邏輯的歸結(jié)法子句

3、型Herbrand定理歸結(jié)原理,4,歸結(jié)（resolution)(也稱消解）推理方法：,這是一種機械化的可在計算機上加以實現(xiàn)的推理方法。AI程序設(shè)計語言Prolog就是基于歸結(jié)原理的一種邏輯程序設(shè)計語言。,,5,歸結(jié)法（也稱消解法）的本質(zhì)是一種反 證法。 為了證明一個命題A恒真，要證明其反命題~A恒假。所謂恒假就是不存在模型，即在所有的可能解釋中，~A均取假值。但一命題的解釋通常

4、有無窮多種，不可能一一測試。為此，Herbrand建議使用一種方法：從眾多的解釋中，選擇一種代表性的解釋，并嚴(yán)格證明：任何命題，一旦證明為在這種解釋中取假值，即在所有的解釋中取假值，這就是Herbrand解釋。,6,3.4 命題邏輯的歸結(jié)法,要證明： A1∧A2∧A3?B 是定理（重言式） ? A1∧A2∧A3 ∧ ~B 是矛盾(永假)式歸結(jié)推理方法就是從A1∧A2∧A3 ∧ ~B 出發(fā)，使用歸結(jié)推理規(guī)則來尋

5、找矛盾，最后證明定理成立。歸結(jié)法（消解法）的本質(zhì)是數(shù)學(xué)中的反證法，稱為“反演推理方法”。,等價于,,7,3.4.1 建立子句集,首先，把A1∧A2∧A3 ∧ ~B化成一種稱作子句形的標(biāo)準(zhǔn)形式。如： P∧(Q∨R)∧(~P∨~Q)∧(P∨~Q∨R)然后將合取范式寫成集合的表示形式，得 S = {P, Q∨R, ~P∨~Q, P∨~Q∨R}, 以“,”代 替“∧”。,,,子

6、句集,,,一個子句,8,3.4.2 歸結(jié)式,設(shè)C1=P∨C1′ C2=~P∨C2′ 消去互補對，新子句 R(C1,C2) = C1′∨ C2′沒有互補對的兩子句沒有歸結(jié)式，歸結(jié)推理即對兩子句做歸結(jié)證明 C1∧C2?R(C1,C2)任一使C1，C2為真的解釋I下必有R(C1,C2)也是真?？兆泳洹醍?dāng)C1=P C2=~P兩個子句的歸結(jié)式為空，記作□，稱為空子句，體現(xiàn)

7、了矛盾。,,為兩個子句,,,子句C1、C2的歸結(jié)式,9,3.4.3歸結(jié)推理過程,子句集S,歸結(jié)推理規(guī)則,S′＝空子句□,S′=所得歸結(jié)式,說明S是不可滿足的,與S對應(yīng)的定理成立,推理結(jié)束,,,,,,,,,,是,否,10,例：證明(P?Q)∧~Q?~P,先將(P?Q)∧~Q∧~(~P)化成合取范式，得 (~P∨Q)∧~Q∧P建立子句集 S={~P∨Q, ~Q, P)對S作歸結(jié)~P

8、∨Q~QP~P 1), 2) 歸結(jié)□ 3), 4) 歸結(jié) 證畢注：一階謂詞邏輯的歸結(jié)方法比命題邏輯的歸結(jié)法要復(fù)雜得多，原因是要對量詞和變量做專門的處理。,11,3.5 子句形,設(shè)有由一階謂詞邏輯描述的公式A1，A2，A3和B，證明在A1∧A2∧A3成立的條件下有B成立。仍然

9、采用反演法來證明。 A1∧A2∧A3∧~B (3.2.1) 是不可滿足的。與命題邏輯不同，首先遇到了量詞問題，為此要將(3.2.1)式化成SKOLEM標(biāo)準(zhǔn)形。,,12,3.5.1 SKOLEM標(biāo)準(zhǔn)形（即與或句）,對給定的一階謂詞邏輯公式G=A1∧A2∧A3∧~B第一步，化成與其等值的前束范式 [方法：參見2.3節(jié)“與或句演繹系統(tǒng)”]第二步，化成合取范式第三步

10、，將所有存在量詞（ ? ）消去,13,3.5.2子句與子句集,概念原子公式：不含有任何聯(lián)結(jié)詞的謂詞公式文字：原子或原子的否定子句：一些文字的析取如，P(x) ∨~Q(x,y), ~P(x,c) ∨R(x,y,f(x))都是子句由于G的SKOLEM標(biāo)準(zhǔn)形的母式已為合取范式，從而母式的每一個合取項都是一個子句，可以說，母式是由一些子句的合取組成的。子句集S：將G的已消去存在量詞的SKOLEM標(biāo)準(zhǔn)形，再略去全稱量詞，最后以

11、“,”代替合取符號“∧”，便得子句集S。,14,例：,解：①將G化成SKOLEM標(biāo)準(zhǔn)形G的子句集子句集S中的變量，都認為是由全稱量詞約束著，子句間是合取關(guān)系。,15,第一類：代數(shù)、幾何證明（定理證明）例1.證明梯形的對角線與上下底構(gòu)成的內(nèi)錯角相等,3.5.3 建立子句集舉例,16,證明：①設(shè)梯形的頂點依次為a,b,c,d.引入謂詞：T(x,y,u,v)表示以xy為上底，uv為下底的梯形P(x,y,u,v)表示xy//u

12、vE(x,y,z,u,v,w)表示∠xyz = ∠uvw②問題的邏輯描述和相應(yīng)的子句集為梯形上下底平行：平形內(nèi)錯角相等已知條件要證明的結(jié)論：B: E(a,b,d,c,d,b) 結(jié)論的“非”：S~B:~E(a,b,d,c,d,b)}從而 S = {SA1, SA2, SA3, S~B },17,第二類 機器人動作問題,例2.猴子香蕉問題已知一串香蕉掛在天花板上，猴子直接去拿是夠不到

13、的，但猴子可以走動，也可以爬上梯子來達到吃香蕉的目的。,分析：問題描述，不能忽視動作的先后次序，體現(xiàn)時間概念。常用方法是引入狀態(tài)S來區(qū)分動作的先后，以不同的狀態(tài)表現(xiàn)不同的時間，而狀態(tài)間的轉(zhuǎn)換由一些算子（函數(shù)）來實現(xiàn)。,初始狀態(tài)S0,18,解：引入謂詞P(x,y,z,s): 表示猴子位于x處，香蕉位于y處，梯子位于z處，狀態(tài)為sR(s): 表示s狀態(tài)下猴子吃到香蕉ANS(s): 表示形式謂詞，只是為求得回答的動作序列而虛設(shè)的。引

14、入狀態(tài)轉(zhuǎn)移函數(shù)Walk(y, z, s): 表示原狀態(tài)s下，在walk作用下，猴子從y走到z處所建立的新狀態(tài)。Carry(y,z,s): 表示原狀態(tài)s下，在Carry作用下，猴子從y搬梯子到z處所建立的新狀態(tài)。Climb(s): 表示原狀態(tài)s下，在Climb作用下，猴子爬上梯子所建立的新狀態(tài)。,19,初始狀態(tài)為S0，猴子位于a，香蕉位于b,梯子位于c，問題描述如下：猴子走到梯子處（從x ? z）猴子搬著梯子到y(tǒng)處

15、猴子爬上梯子吃到香蕉初始條件結(jié)論,walk,20,第三類 程序設(shè)計自動化問題,例3：簡單的程序集合問題若一臺計算機有寄存器a,b,c和累加器A，要求自動設(shè)計實現(xiàn)+ (b) ? c的程序。,21,解:先引入謂詞P(u,x,y,z,s):表示累加器A,寄存器a,b,c分別放入u,x,y,z時的狀態(tài)為sLoad(x,s):表示狀態(tài)s下,對任一寄存器x來說,實現(xiàn)(x)?A后的新狀態(tài)Add(x,s):表示狀態(tài)s下,

16、對任一寄存器x來說,實現(xiàn)(x)+(A)?A后的新狀態(tài)Store(x,s):表示狀態(tài)s下,對任一寄存器x來說,實現(xiàn) (A)?x后的新狀態(tài)問題描述((a)?A):寄存器a中的值放入寄存器A中((b)+(A)?A),22,((A)?C)初始狀態(tài)D下，累加器A與寄存器a,b,c中的數(shù)值結(jié)論子句集 S={SA1,SA2,SA3,SA4,S~B},?,23,3.6 Herbrand定理,雖然公式G與其子句集S并

17、不等值，但它們在不可滿足的意義下又是一致的。亦即，G是不可滿足的當(dāng)且僅當(dāng)S是不可滿足的。（證明從略，石純一《AI原理》P17~20). 由于個體變量論域D的任意性，以及解釋的個數(shù)的無限性，對一個謂詞公式來說，不可滿足性的證明是困難的。 如果對一個具體的謂詞公式能找到一個較簡單的特殊的論域，使得只要在該論域上該公式是不可滿足的，便能保證在任何論域上也是不可滿足的，Herbrand域（簡稱H域）具

18、有這樣的性質(zhì)。,,24,3.6.1 H域,設(shè)G是已給的公式，定義在論域D上，令H0是G中所出現(xiàn)的常量的集合，若G中沒有常量出現(xiàn)，就任取常量a?D，而規(guī)定H0={a}即 H0= 若G中有常量，為G中常量的集合 若無常量，則為{a}Hi = Hi-1 U {所有形如f(t1,…,tn)的元素}其中， f(t1,…,tn)是出現(xiàn)于G中的任一函數(shù)符號，而t1, t2, …,tn是Hi-1的元素，I

19、=1,2,…H∞為G的H域。（或說是相應(yīng)子句集S的H域） “可數(shù)集合”H∞是直接依賴于G的最多共有可數(shù)個元素的集合,,,25,例1. S={P(a),~P(x) ∨P(f(x))},26,例2. S={P(x), Q(f(x,a)) ∨R(b)}

20、【注】：在S中出現(xiàn)函數(shù)f(x,a),仍視為f(x1,x2)的形式,27,概念基原子 原子基文字 文字基子句 子句基子句集 子句集基例：

21、對： ① 基子句： ② 基例：,,,,:沒有變量出現(xiàn)的,,28,3.6.2 H解釋,思想：由子句集S建立H域、原子集A，使任一論域D上S為真的問題，化成了僅有可數(shù)個元素的H域上S為真的問題。子句集S在D上不滿足問題成了H上不滿足問題，這是很有意義的結(jié)果。,29,定理3.3.2(1)設(shè)I是S的論域D上的解釋，存在對應(yīng)于I的H解釋I*，使得S|I=T，必有S|I*=T。定理3.3.2(2)子句集S是不可滿足的，當(dāng)且

22、僅當(dāng)在所有的S的H解釋下為假。（注：該定理將S在一般論域上的不可滿足問題化成了可數(shù)集上H上的不可滿足問題，以上只需討論在S的H∞上即可。）定理3.3.2(3)子句集S是不可滿足的當(dāng)且僅當(dāng)對每個解釋I下，至少有S的某個子句的某個基例為假。,30,例1：設(shè)子句集S的原子集A={P,Q,R},圖 語義樹（二叉樹）,3.6.3 語義樹,I(N)表示：從根結(jié)點到結(jié)點N分枝上所標(biāo)記的所有文字的并集。I(N34)={P,~Q,~R}

23、,31,例2：解：H={a,f(a),f(f(a)),…} A={P(a),Q(a),P(f(a)),Q(f(a)),…},N38,32,完全語義樹：對所有結(jié)點N,（ ）,I(N)包含了A={A1,A2,…}中的 或~Ai，i=1,2,…,n。失敗結(jié)點：如果結(jié)點N的I(N)使S的某一子句有某一基例為假，而N的父輩結(jié)點不能判斷這個事實，就說N是失敗結(jié)點。封閉樹：如果S的完全語義樹的每個分枝上

24、都有一個失敗結(jié)點，即為封閉樹。,33,例2中的完全語義樹即為封閉樹。,圖 封閉語義樹,N0,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,N11,N12,N21,N22,N24,N31,N32,N4,13,N4,14,N36,P(a),~P(a),Q(a),~Q(a),P(f(a)),如，I(N2,2)={P(a),~Q(a)},使得S中，~P(a) ∨Q(a)為假。 I(N3,6)={~P(a), Q(a)

25、 ,~P(f(a))},使得S中的P(f(a))為假。 …… I(N4,1)={P(a),~Q(a)},使得~Q(f(y))為假。,,,,,N38,,,N41,N42,N49,,,N4,10,34,3.6.4 Herbrand定理,一階謂詞描述A1∧A2 ∧A3→B化成不滿足問題G= A1∧A2 ∧A3 ∧ ~BG化成SKOLEM形S={ , , ,……}一般論域D簡化成H∞域上的討論引入語

26、義樹,35,★Herbrand給出的兩個定理,定理3.3.4(1)子句集S是不可滿足的，當(dāng)且僅當(dāng)對應(yīng)于S的完全語義樹都是一棵有限的封閉語義樹。（注：證明從略）定理3.3.4(2)S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。（注：證明從略）,36,▲應(yīng)當(dāng)指出：,Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證定理是成立的，使用該算法可得證，否則，得不出任何結(jié)果。Herbrand定理已將證明問題化成了命題

27、邏輯問題，所以只需在命題邏輯范圍內(nèi)簡化。,37,補充：石純一編著：《人工智能原理》P39~40重言式子句可刪除規(guī)則 S={P∨~P,C1,C2}?S={C1,C2}.單文字刪除規(guī)則 S={L，L∨C1，~L ∨C2，C3，C4}?S′={~L ∨C2，C3，C4}，刪除含L的子句 ?

28、 S ={C2，C3，C4}，刪除文字~L純文字刪除規(guī)則 當(dāng)文字L出現(xiàn)于S中，而~L不出現(xiàn)于S中，便說L為S的純文字。 S中刪除L?S′=Ø，S可滿足 S中刪除L?S′≠Ø，S′,S同時不可滿足分離規(guī)則S={L∨A1)∧… ∧(L∨Am)∧(~L∨B1)∧ …∧(~L∨Bn)∧R（不含L和~L的子句等） S′={A1,…,Am,R} S′={B1,…,Bn,R}

29、 S不可滿足? S′、 S′同時不可滿足,′,′,,,′,′,38,3.7 歸結(jié)原理,雖然Herbrandp定理給出了推理算法，但需逐次生成基例集 ，再檢驗 的不可滿足性，常常難以實現(xiàn)。 1965年，Robinson提出了歸結(jié)原理，是對自動推理的重大突破。,,39,3.7.1 置換與合一,置換：是形為{t1/v1,…,tn/vn}的一個有限集。

30、其中，vi是變量，而ti是不同于vi的項（常量、變量、函數(shù)）且vi≠vj，（i≠j),i,j=1,2,…,n例如，{a/x,b/y,f(x)/z},{f(z)/x,y/z}都是置換?？罩脫Q?：不含任何元素的置換。令置換?={t1/v1,t2/v2,…,tn/vn} E是一階謂詞① ?作用于E，就是將E中出現(xiàn)的變量vi均以ti代入（i=1,2,…,n)，以E?表示結(jié)果，并稱為E的一個例。② ?作用于項t，是將t中出現(xiàn)的變

31、量vi以ti代入(i=1,…,n)，結(jié)果以t·?表示。,40,例：?={a/x, f(b)/y, u/z} E=P(x, y, z) t = g(x, y)那么 E? = P(a, f(b), u) t?=g(a, f(b)),41,常使用的置換的運算是置換乘法（合成）若 ?={t1/x1,…,tn/xn} ?={u1/y1,…,um/ym}置換乘積?

32、3;?是新的置換，作用于E相當(dāng)于先?后?對E的作用。定義如下：先作置換：{t1 ·? /x1 ,…, tn ·? /xn , u1 /y1,…,um/ym }若yi?{x1,…, xn}時，先從中刪除ui/yi；ti·? = xi時，再從中刪除ti ·?/ xi；所設(shè)的置換稱作?與?的乘積，記作?·?,42,例： ?={f(y)/x, z/y} ?={a/x

33、, 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} 先刪除a/x,b/y,再刪y/y，得 ?·? = {f(b)/x,y/z} 當(dāng) E = P(x,y,z)時， E? = P(f(y), z, z), (

34、E?)? = P(f(b), y, y) E(?·?) = P(f(b), y, y),,(E?)? = E(?·?),43,概念：合一,設(shè)有公式集{E1,…,Ek}和置換?，使E1 ? = E2 ?=…Ek ?稱E1,…,Ek是可合一的，且?稱為合一置換（union replacement）。若E1,…,Ek有合一置換?，且對E1,…,Ek的任一合一置換?都有置換?存在，使得?= ?·

35、;?便說?是E1,…,Ek的最一般置換，記作mgu（most general replacement),44,例1 E1=P(a,y),E2=P(x,f(b)),E1,E2可合一， ?={a/x, f(b)/y},且?是E1，E2的mgu.例2 E1=P(x), E2=P(f(y))置換?={f(a)/x, a/y}并不是E1、 E2的mgu，而?= {f(y)/x}才是E1、 E2的mgu，也可以說，是E1、 E2的最簡單合

36、一置換。,45,例3 E1=P(x), E2=P(y)。顯然{y/x}和{x/y}都是E1 、E2的mgu，說明mgu不唯一。,46,求mgu的算法（最一般合一置換mgu),令w={E1,E2}。令k=0,w0=w,?0=?(空置換）。如果wk已合一，停止，?k=mgu。否則找不一致集。若Dk中存在元素vk,tk,其中vk不出現(xiàn)于tk中做 5 ，否則不可合一。令?k+1= ?k·{tk/vk}wk+1=wk{tk/

37、vk} = w?k+1。k+1?k 轉(zhuǎn) 3。,47,例 w={P(a,x,f(g(y))),P(z,f(a),f(u))}其中，E1=P(a,x,f(g(y))),E2=P(z,f(a),f(u))求 E1,E2的mug解：(1) w={P(a,x,f(g(y))),P(z,f(a),f(u))}. (2) ?0=?,w0=w. (3) w0未合一，自左至右找不一致集，有D0={a,z}.

38、 (4)取v0=z,t0=a. (5)令?1= ?0，{t0/v0}= ?· {a/z} = {a/z}. w1=w0?1={P(a,x,f(g(y))),P(a,f(a),f(u))}. (3) ′w1未合一，不一致集D1={x,f(a)}. (4) ′取v1=x,t1=f(a). (5) ′令?2= ?1·{f(a)

39、/x}={a·?/z,f(a)/x}={a.z,f(a)/x} w2=w1?2={P(a),f(a),f(g(y)),p(a,f(a),f(u))}.,48,(3) ′w2未合一，不一致集D2 = {g(y),u}.(4) ′取v2 = u,t2=g(y).(5) ′令?3= ?2·{g(y)/u} = {a/z,f(a)/x}·{g(y)/u}

40、 = { a/z,f(a)/x,g(y)/u} . w3 = w2?3={P(a),f(a),f(g(y)),P(a),f(a),f(g(y)))}(3) ′w3已合一，這時?3={a/z,f(a)/x,g(y)/u} ，即為E1，E2的mgu.注：不可合一的情況 ①不存在vk變量，如w={P(a,b,c),P(d,b,c)} ②不存在tk變

41、量，如w={P(a,b),P(x,y,z)}③出現(xiàn)不一致集為{x,f(x)}形,′,′,′,′,′,49,3.7.2 歸結(jié)式,在謂詞邏輯下求兩個子句的歸結(jié)式，和命題邏輯一樣是消去互補對，但需考慮變量的合一和置換。二元歸結(jié)式：設(shè)C1, C2是兩個無公共 變量的子句， L1, L2分別是C1, C2的文字，若L1與~ L2有mgu ?，則(C1 ? - {L1 ?}) ? (C2 ? - {L2 ?})稱作子句C1, C2的一

42、個二元歸結(jié)式，而L1, L2為被歸結(jié)的文字?！咀⒁狻浚和}邏輯下的歸結(jié)式不同的是，先需對C1, C2有關(guān)變量作mgu，再消去互補對。同樣有： C1 ? C2 ? R(C1, C2),50,例1 C1 = ~A(x) ? B(x) C2 = A(g(x))【解】：先將C1的變量x改寫為y，可得mgu = {g(x)/y}，作歸結(jié)得R(C1, C2) = B(g(x))。例2 C1 = P(x)

43、 ? Q(x) C2 = ~P(g(y)) ? ~Q(b) ? R(x)【解】：可知有兩個合一置換，故有兩個二元歸結(jié)式。（1）當(dāng)取 ? = {g(y)/x}時，得R(C1, C2) = Q(g(y)) ? ~Q(b) ? R(x)（2）當(dāng)取 ? = {b/x}時，得R(C1, C2) = P(b) ? ~P(g(y)) ? R(x),51,例3 C1 = P(x) ? ~Q(b)

44、C2 = ~P(a) ? Q(y) ? R(z)【解】：這時要注意，求歸結(jié)式不能同時消去兩個互補對。如在 ? = {a/x, b/y}下，得R(z)。這不是C1, C2的二元歸結(jié)式。最簡單的例子是：C1 = P ? Q， C2 = ~P ? ～Q若消去上述兩個互補對便得空子句。但是C1, C2并無矛盾。這說明消去兩個互補對的結(jié)果并不是C1, C2的邏輯推論了。因此，消去兩個互補對結(jié)果不是二元歸結(jié)式。,

45、52,在對子句作歸結(jié)前，可先考慮子句內(nèi)部的化簡，這便提出了子句因子的概念。設(shè) C = P(x) ? P(f(y)) ? ~Q(x)令 ? = {f(y)/x}，將置換?使用于C，可使P(x), P(f(y))合一。顯然C?比C簡單得多。子句因子：若一個子句C的幾個文字有mgu ?，那么C的C?稱作子句C的因子。定義：若C1, C2是無公共變量的子句，作（1） C1, C2的二元歸結(jié)式（2） C1的因子和C2的二元

46、歸結(jié)式（3） C1,和C2的因子的二元歸結(jié)式（4） C1的因子和C2的因子的二元歸結(jié)式這四種二元歸結(jié)式都叫子句C1, C2的歸結(jié)式，記作R(C1, C2),53,例4 C1 = P(x) ? P(f(y)) ? Q(g(y)) C2 = ~P(f(g(a))) ? Q(b)【解】：先作C1的因子，取 ? = {f(y)/x}，得C1的因子C1? = P(f(y)) ? Q(g(y)) 于是C1,

47、C2歸結(jié)式為R(C1, C2) = Q(g(g(a))) ? Q(b)【說明】：上述推理過程的正確性能得到保證。,54,3.7.3 歸結(jié)推理過程,為證明A?B成立，其中A, B是謂詞公式，使用反演過程，先建立G = A ? ~B 進而做出相應(yīng)的子句集S，只需證明S是不可滿足的。 歸結(jié)法是僅有一條推理規(guī)則的推理方法。對S中的可歸結(jié)的子句作歸結(jié)，求得歸結(jié)式，并將這歸結(jié)式（新子句）仍放入S中，反復(fù)進行這