歸結(jié)推理方法-課件

1、第三章 歸結(jié)原理（第二部分） (Chapter 3 Resolution Reasoning)(Part B)徐從富浙江大學(xué)人工智能研究所2002年第一稿2004年9月修改1本章的主要參考文獻(xiàn)：1 石純一 等. 人工智能原理. 清華大學(xué)出版社, 1993. pp11-81. （【注意】：本課件以該書中的這部分內(nèi)容為主而制作，若想更加全面地了解歸結(jié)原理及其應(yīng)用，請(qǐng)參見如下文獻(xiàn)2和3）2 陸汝鈐. 人工智能（下冊(cè)）. 科學(xué)出版社, 2000. pp681-728. 3 王永慶. 人工智能原理與方法. 西安交通大學(xué)出版社, 1998. pp111-155. 【注】：若對(duì)定理的機(jī)械化證明的更多內(nèi)容感興

2、趣者，可參考陸汝鈐. 人工智能（下冊(cè)）. 科學(xué)出版社, 2000. pp729-788. 其最新進(jìn)展可參考我國(guó)數(shù)學(xué)家吳文俊院士的相關(guān)論文，不過，他的研究工作對(duì)數(shù)學(xué)要求很高！2前言命題邏輯的歸結(jié)法子句型Herbrand定理歸結(jié)原理3歸結(jié)（resolution)(也稱消解）推理方法： 這是一種機(jī)械化的可在計(jì)算機(jī)上加以實(shí)現(xiàn)的推理方法。AI程序設(shè)計(jì)語(yǔ)言Prolog就是基于歸結(jié)原理的一種邏輯程序設(shè)計(jì)語(yǔ)言。4 歸結(jié)法（也稱消解法）的本質(zhì)是一種反 證法。 為了證明一個(gè)命題A恒真，要證明其反命題A恒假。所謂恒假就是不存在模型，即在所有的可能解釋中，A均取假值。但一命題的解釋通常有無窮多種，不可能一一測(cè)試。為此

3、，Herbrand建議使用一種方法：從眾多的解釋中，選擇一種代表性的解釋，并嚴(yán)格證明：任何命題，一旦證明為在這種解釋中取假值，即在所有的解釋中取假值，這就是Herbrand解釋。53.4 命題邏輯的歸結(jié)法要證明： A1A2A3B 是定理（重言式） A1A2A3 B 是矛盾(永假)式歸結(jié)推理方法就是從A1A2A3 B 出發(fā)，使用歸結(jié)推理規(guī)則來尋找矛盾，最后證明定理成立。歸結(jié)法（消解法）的本質(zhì)是數(shù)學(xué)中的反證法，稱為“反演推理方法”。等價(jià)于63.4.1 建立子句集首先，把A1A2A3 B化成一種稱作子句形的標(biāo)準(zhǔn)形式。如： P(QR)(PQ)(PQR)然后將合取范式寫成集合的表示形式，得 S = P,

4、 QR, PQ, PQR, 以“,”代 替“”。子句集一個(gè)子句73.4.2 歸結(jié)式設(shè)C1=PC1 C2=PC2 消去互補(bǔ)對(duì)，新子句 R(C1,C2) = C1 C2沒有互補(bǔ)對(duì)的兩子句沒有歸結(jié)式，歸結(jié)推理即對(duì)兩子句做歸結(jié)證明 C1C2R(C1,C2)任一使C1，C2為真的解釋I下必有R(C1,C2)也是真?？兆泳洚?dāng)C1=P C2=P兩個(gè)子句的歸結(jié)式為空，記作，稱為空子句，體現(xiàn)了矛盾。為兩個(gè)子句子句C1、C2的歸結(jié)式83.4.3歸結(jié)推理過程子句集S歸結(jié)推理規(guī)則S空子句S=所得歸結(jié)式說明S是不可滿足的與S對(duì)應(yīng)的定理成立推理結(jié)束是否9例：證明(PQ)QP先將(PQ)Q(P)化成合取范式，得 (PQ)Q

5、P建立子句集 S=PQ, Q, P)對(duì)S作歸結(jié)PQQPP 1), 2) 歸結(jié) 3), 4) 歸結(jié) 證畢注：一階謂詞邏輯的歸結(jié)方法比命題邏輯的歸結(jié)法要復(fù)雜得多，原因是要對(duì)量詞和變量做專門的處理。103.5 子句形設(shè)有由一階謂詞邏輯描述的公式A1，A2，A3和B，證明在A1A2A3成立的條件下有B成立。仍然采用反演法來證明。 A1A2A3B (3.2.1) 是不可滿足的。與命題邏輯不同，首先遇到了量詞問題，為此要將(3.2.1)式化成SKOLEM標(biāo)準(zhǔn)形。113.5.1 SKOLEM標(biāo)準(zhǔn)形（即與或句）對(duì)給定的一階謂詞邏輯公式G=A1A2A3B第一步，化成與其等值的前束范式 方法：參見2.3節(jié)“與或句

6、演繹系統(tǒng)”第二步，化成合取范式第三步，將所有存在量詞（ ）消去123.5.2子句與子句集概念原子公式：不含有任何聯(lián)結(jié)詞的謂詞公式文字：原子或原子的否定子句：一些文字的析取如，P(x) Q(x,y), P(x,c) R(x,y,f(x)都是子句由于G的SKOLEM標(biāo)準(zhǔn)形的母式已為合取范式，從而母式的每一個(gè)合取項(xiàng)都是一個(gè)子句，可以說，母式是由一些子句的合取組成的。子句集S：將G的已消去存在量詞的SKOLEM標(biāo)準(zhǔn)形，再略去全稱量詞，最后以“,”代替合取符號(hào)“”，便得子句集S。13例：解：將G化成SKOLEM標(biāo)準(zhǔn)形G的子句集子句集S中的變量，都認(rèn)為是由全稱量詞約束著，子句間是合取關(guān)系。14第一類：代數(shù)

7、、幾何證明（定理證明）例1.證明梯形的對(duì)角線與上下底構(gòu)成的內(nèi)錯(cuò)角相等3.5.3 建立子句集舉例a(x)d(v)b(y)c(u)15證明：設(shè)梯形的頂點(diǎn)依次為a,b,c,d.引入謂詞：T(x,y,u,v)表示以xy為上底，uv為下底的梯形P(x,y,u,v)表示xy/uvE(x,y,z,u,v,w)表示xyz = uvw問題的邏輯描述和相應(yīng)的子句集為梯形上下底平行：平形內(nèi)錯(cuò)角相等已知條件要證明的結(jié)論：B: E(a,b,d,c,d,b) 結(jié)論的“非”：SB:E(a,b,d,c,d,b)從而 S = SA1, SA2, SA3, SB 16第二類 機(jī)器人動(dòng)作問題例2.猴子香蕉問題已知一串香蕉掛在天花板

8、上，猴子直接去拿是夠不到的，但猴子可以走動(dòng)，也可以爬上梯子來達(dá)到吃香蕉的目的。分析：?jiǎn)栴}描述，不能忽視動(dòng)作的先后次序，體現(xiàn)時(shí)間概念。常用方法是引入狀態(tài)S來區(qū)分動(dòng)作的先后，以不同的狀態(tài)表現(xiàn)不同的時(shí)間，而狀態(tài)間的轉(zhuǎn)換由一些算子（函數(shù)）來實(shí)現(xiàn)。(b)y(a)x(c)z初始狀態(tài)S017解：引入謂詞P(x,y,z,s): 表示猴子位于x處，香蕉位于y處，梯子位于z處，狀態(tài)為sR(s): 表示s狀態(tài)下猴子吃到香蕉ANS(s): 表示形式謂詞，只是為求得回答的動(dòng)作序列而虛設(shè)的。引入狀態(tài)轉(zhuǎn)移函數(shù)Walk(y, z, s): 表示原狀態(tài)s下，在walk作用下，猴子從y走到z處所建立的新狀態(tài)。Carry(y,z,

9、s): 表示原狀態(tài)s下，在Carry作用下，猴子從y搬梯子到z處所建立的新狀態(tài)。Climb(s): 表示原狀態(tài)s下，在Climb作用下，猴子爬上梯子所建立的新狀態(tài)。18初始狀態(tài)為S0，猴子位于a，香蕉位于b,梯子位于c，問題描述如下：猴子走到梯子處（從x z）猴子搬著梯子到y(tǒng)處猴子爬上梯子吃到香蕉初始條件結(jié)論walk19第三類 程序設(shè)計(jì)自動(dòng)化問題例3：簡(jiǎn)單的程序集合問題若一臺(tái)計(jì)算機(jī)有寄存器a,b,c和累加器A，要求自動(dòng)設(shè)計(jì)實(shí)現(xiàn)+ (b) c的程序。20解:先引入謂詞P(u,x,y,z,s):表示累加器A,寄存器a,b,c分別放入u,x,y,z時(shí)的狀態(tài)為sLoad(x,s):表示狀態(tài)s下,對(duì)任一

10、寄存器x來說,實(shí)現(xiàn)(x)A后的新狀態(tài)Add(x,s):表示狀態(tài)s下,對(duì)任一寄存器x來說,實(shí)現(xiàn)(x)+(A)A后的新狀態(tài)Store(x,s):表示狀態(tài)s下,對(duì)任一寄存器x來說,實(shí)現(xiàn) (A)x后的新狀態(tài)問題描述(a)A):寄存器a中的值放入寄存器A中(b)+(A)A)21(A)C)初始狀態(tài)D下，累加器A與寄存器a,b,c中的數(shù)值結(jié)論子句集 S=SA1,SA2,SA3,SA4,SB223.6 Herbrand定理 雖然公式G與其子句集S并不等值，但它們?cè)诓豢蓾M足的意義下又是一致的。亦即，G是不可滿足的當(dāng)且僅當(dāng)S是不可滿足的。（證明從略，石純一AI原理P1720). 由于個(gè)體變量論域D的任意性，以及解

11、釋的個(gè)數(shù)的無限性，對(duì)一個(gè)謂詞公式來說，不可滿足性的證明是困難的。 如果對(duì)一個(gè)具體的謂詞公式能找到一個(gè)較簡(jiǎn)單的特殊的論域，使得只要在該論域上該公式是不可滿足的，便能保證在任何論域上也是不可滿足的，Herbrand域（簡(jiǎn)稱H域）具有這樣的性質(zhì)。233.6.1 H域設(shè)G是已給的公式，定義在論域D上，令H0是G中所出現(xiàn)的常量的集合，若G中沒有常量出現(xiàn)，就任取常量aD，而規(guī)定H0=a即 H0= 若G中有常量，為G中常量的集合 若無常量，則為aHi = Hi-1 U 所有形如f(t1,tn)的元素其中， f(t1,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而t1, t2, ,tn是Hi-1的元素，I=1,2,H為

12、G的H域。（或說是相應(yīng)子句集S的H域） “可數(shù)集合”H是直接依賴于G的最多共有可數(shù)個(gè)元素的集合24例1. S=P(a),P(x) P(f(x)25例2. S=P(x), Q(f(x,a) R(b)【注】：在S中出現(xiàn)函數(shù)f(x,a),仍視為f(x1,x2)的形式26概念基原子 原子基文字 文字基子句 子句基子句集 子句集基例：對(duì)： 基子句： 基例：:沒有變量出現(xiàn)的273.6.2 H解釋思想：由子句集S建立H域、原子集A，使任一論域D上S為真的問題，化成了僅有可數(shù)個(gè)元素的H域上S為真的問題。子句集S在D上不滿足問題成了H上不滿足問題，這是很有意義的結(jié)果。28定理3.3.2(1)設(shè)I是S的論域D上的

13、解釋，存在對(duì)應(yīng)于I的H解釋I*，使得S|I=T，必有S|I*=T。定理3.3.2(2)子句集S是不可滿足的，當(dāng)且僅當(dāng)在所有的S的H解釋下為假。（注：該定理將S在一般論域上的不可滿足問題化成了可數(shù)集上H上的不可滿足問題，以上只需討論在S的H上即可。）定理3.3.2(3)子句集S是不可滿足的當(dāng)且僅當(dāng)對(duì)每個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。29例1：設(shè)子句集S的原子集A=P,Q,R圖 語(yǔ)義樹（二叉樹）N0N11N12N21N22N23N24N31N32N33N34N35N36N37N38PPQQQRRRRR3.6.3 語(yǔ)義樹I(N)表示：從根結(jié)點(diǎn)到結(jié)點(diǎn)N分枝上所標(biāo)記的所有文字的并集。I(N

14、34)=P,Q,R30例2：解：H=a,f(a),f(f(a), A=P(a),Q(a),P(f(a),Q(f(a),N38圖 無限語(yǔ)義樹N0N11N12N21N22N23N24N31N32N33N34N35N36N37P(a)P(a)Q(a)Q(a)P(f(a)31完全語(yǔ)義樹：對(duì)所有結(jié)點(diǎn)N,（ ）,I(N)包含了A=A1,A2,中的 或Ai，i=1,2,n。失敗結(jié)點(diǎn)：如果結(jié)點(diǎn)N的I(N)使S的某一子句有某一基例為假，而N的父輩結(jié)點(diǎn)不能判斷這個(gè)事實(shí)，就說N是失敗結(jié)點(diǎn)。封閉樹：如果S的完全語(yǔ)義樹的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn)，即為封閉樹。32例2中的完全語(yǔ)義樹即為封閉樹。圖 封閉語(yǔ)義樹N0N11N

15、12N21N22N24N31N32N4,13N4,14N36P(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) ,P(f(a),使得S中的P(f(a)為假。 I(N4,1)=P(a),Q(a),使得Q(f(y)為假。N38N41N42N49N4,10333.6.4 Herbrand定理一階謂詞描述A1A2 A3B化成不滿足問題G= A1A2 A3 BG化成SKOLEM形S= , , ,一般論域D簡(jiǎn)化成H域上的討論引入語(yǔ)義樹34Herbrand給出的兩個(gè)定理定理3.3.4(1)子句集S是不可

16、滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義樹都是一棵有限的封閉語(yǔ)義樹。（注：證明從略）定理3.3.4(2)S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。（注：證明從略）35應(yīng)當(dāng)指出：Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證定理是成立的，使用該算法可得證，否則，得不出任何結(jié)果。Herbrand定理已將證明問題化成了命題邏輯問題，所以只需在命題邏輯范圍內(nèi)簡(jiǎn)化。36補(bǔ)充：石純一編著：人工智能原理P3940重言式子句可刪除規(guī)則 S=PP,C1,C2S=C1,C2.單文字刪除規(guī)則 S=L，LC1，L C2，C3，C4S=L C2，C3，C4，刪除含L的子句 S =C2，C3，C4，刪

17、除文字L純文字刪除規(guī)則 當(dāng)文字L出現(xiàn)于S中，而L不出現(xiàn)于S中，便說L為S的純文字。 S中刪除LS=，S可滿足 S中刪除LS，S,S同時(shí)不可滿足分離規(guī)則S=LA1) (LAm)(LB1) (LBn)R（不含L和L的子句等） S=A1,Am,R S=B1,Bn,R S不可滿足 S、 S同時(shí)不可滿足373.7 歸結(jié)原理 雖然Herbrandp定理給出了推理算法，但需逐次生成基例集 ，再檢驗(yàn) 的不可滿足性，常常難以實(shí)現(xiàn)。 1965年，Robinson提出了歸結(jié)原理，是對(duì)自動(dòng)推理的重大突破。383.7.1 置換與合一置換：是形為t1/v1,tn/vn的一個(gè)有限集。其中，vi是變量，而ti是不同于vi的項(xiàng)

18、（常量、變量、函數(shù)）且vivj，（ij),i,j=1,2,n例如，a/x,b/y,f(x)/z,f(z)/x,y/z都是置換。空置換：不含任何元素的置換。令置換=t1/v1,t2/v2,tn/vn E是一階謂詞 作用于E，就是將E中出現(xiàn)的變量vi均以ti代入（i=1,2,n)，以E表示結(jié)果，并稱為E的一個(gè)例。 作用于項(xiàng)t，是將t中出現(xiàn)的變量vi以ti代入(i=1,n)，結(jié)果以t表示。39例：=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)40常使用的置換的運(yùn)算是置換乘法（合成）若 =t1/x1,

19、tn/xn =u1/y1,um/ym置換乘積是新的置換，作用于E相當(dāng)于先后對(duì)E的作用。定義如下：先作置換：t1 /x1 , tn /xn , u1 /y1,um/ym 若yix1, xn時(shí)，先從中刪除ui/yi；ti = xi時(shí)，再?gòu)闹袆h除ti / xi；所設(shè)的置換稱作與的乘積，記作41例： =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 先刪除a/x,b/y,再刪y/y，得 = f(b)/x,y/z 當(dāng) E = P(x,y,z)時(shí)， E = P(f(y),

20、z, z), (E) = P(f(b), y, y) E() = P(f(b), y, y) (E) = E() 42概念：合一設(shè)有公式集E1,Ek和置換，使E1 = E2 =Ek 稱E1,Ek是可合一的，且稱為合一置換（union replacement）。若E1,Ek有合一置換，且對(duì)E1,Ek的任一合一置換都有置換存在，使得= 便說是E1,Ek的最一般置換，記作mgu（most general replacement)43例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

21、(a)/x, a/y并不是E1、 E2的mgu，而= f(y)/x才是E1、 E2的mgu，也可以說，是E1、 E2的最簡(jiǎn)單合一置換。44例3 E1=P(x), E2=P(y)。顯然y/x和x/y都是E1 、E2的mgu，說明mgu不唯一。45求mgu的算法（最一般合一置換mgu)令w=E1,E2。令k=0,w0=w,0=(空置換）。如果wk已合一，停止，k=mgu。否則找不一致集。若Dk中存在元素vk,tk,其中vk不出現(xiàn)于tk中做 5 ，否則不可合一。令k+1= ktk/vkwk+1=wktk/vk = wk+1。k+1k 轉(zhuǎn) 3。46例 w=P(a,x,f(g(y),P(z,f(a),f

22、(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. (4)取v0=z,t0=a. (5)令1= 0，t0/v0= a/z = a/z. w1=w01=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= 1f(a)/x=a/z,f(a)/x=a.z,f(a)/x w2=w12=P(a),f(

23、a),f(g(y),p(a,f(a),f(u).47(3) w2未合一，不一致集D2 = g(y),u.(4) 取v2 = u,t2=g(y).(5) 令3= 2g(y)/u = a/z,f(a)/xg(y)/u = a/z,f(a)/x,g(y)/u . w3 = w23=P(a),f(a),f(g(y),P(a),f(a),f(g(y)(3) w3已合一，這時(shí)3=a/z,f(a)/x,g(y)/u ，即為E1，E2的mgu.注：不可合一的情況 不存在vk變量，如w=P(a,b,c),P(d,b,c) 不存在tk變量，如w=P(a,b),P(x,y,z)出現(xiàn)不一致集為x,f(x)形483.7

24、.2 歸結(jié)式 在謂詞邏輯下求兩個(gè)子句的歸結(jié)式，和命題邏輯一樣是消去互補(bǔ)對(duì)，但需考慮變量的合一和置換。二元?dú)w結(jié)式：設(shè)C1, C2是兩個(gè)無公共 變量的子句， L1, L2分別是C1, C2的文字，若L1與 L2有mgu ，則(C1 - L1 ) (C2 - L2 )稱作子句C1, C2的一個(gè)二元?dú)w結(jié)式，而L1, L2為被歸結(jié)的文字?！咀⒁狻浚和}邏輯下的歸結(jié)式不同的是，先需對(duì)C1, C2有關(guān)變量作mgu，再消去互補(bǔ)對(duì)。同樣有： C1 C2 R(C1, C2)49例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) Q(x) C2 = P(g(y) Q(b) R(x)【解】：可知有兩個(gè)合一置換，故有兩個(gè)二元?dú)w結(jié)式。（1）當(dāng)取 = g(y)/x時(shí)，得R(C1, C2) = Q(g(y) Q(b) R(x)（2）當(dāng)取 = b/x時(shí)，得R(C1, C2) = P(b) P(g(y) R(x)50例3 C1 = P(x) Q(b) C2 = P(a) Q(y) R(z)【解】：這時(shí)