子句和子句集

1、4.3 歸結(jié)演繹推理,歸結(jié)演繹推理是一種基于魯賓遜（robinson）歸結(jié)原理的機器推理技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫（herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法”。 在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)，就是要對前提p和結(jié)論q，證明pq永真。 要證明pq永真，就是要證明pq在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。 為此，人們進行了大量的探索，后來發(fā)現(xiàn)可以采用反證法的思想，把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。 即要證明pq永真，只要能夠證明pq是不可滿足的就可以了(原

2、因是 (pq) ( pq) p q 。 這方面最有成效的工作就是魯賓遜歸結(jié)原理。它使定理證明的機械化成為現(xiàn)實。,1,4.3.1 子句集及其化簡1. 子句和子句集,魯濱遜歸結(jié)原理是在子句集的基礎(chǔ)上討論問題的。因此，討論歸結(jié)演繹推理之前，需要先討論子句集的有關(guān)概念。 子句和子句集 定義1 原子謂詞公式及其否定統(tǒng)稱為文字。 例如，p(x)、q(x)、 p(x)、 q(x)等都是文字。 定義2 任何文字的析取式稱為子句。 例如，p(x)q(x)，p(x，f(x)q(x，g(x)都是子句。 定義3 不含任何文字的子句稱為空子句。 由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不

3、可滿足的。 空子句一般被記為nil。 定義4 由子句或空子句所構(gòu)成的集合稱為子句集。,2,4.3.1 子句集及其化簡2. 子句集的化簡（1/6）,在謂詞邏輯中，任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集。其化簡步驟如下： (1) 消去連接詞“”和“” 反復(fù)使用如下等價公式： pq pq pq (pq)(pq) 即可消去謂詞公式中的連接詞“”和“”。 例如公式 (x)(y)p(x,y) (y)(q(x,y)r(x,y) 經(jīng)等價變化后為 (x)(y)p(x,y) (y)(q(x,y)r(x,y),3,4.3.1 子句集及其化簡2. 子句集的化簡（2/6）,(2) 減少否定符號

4、的轄域 反復(fù)使用雙重否定率 (p) p 摩根定律 (pq) pq (pq) pq 量詞轉(zhuǎn)換率 (x)p(x) (x) p(x) (x)p(x) (x)p(x) 將每個否定符號“”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。 例如，上式經(jīng)等價變換后為 (x)(y)p(x，y)(y)( q(x，y) r(x，y),4,4.3.1 子句集及其化簡2. 子句集的化簡（3/6）,(3) 對變元標(biāo)準(zhǔn)化 在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。 例如，上式經(jīng)變換后為 (x)(y)p(x，y)(z)( q(x，

5、z) r(x，z) (4) 化為前束范式 化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進行了標(biāo)準(zhǔn)化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種移動是可行的。 例如，上式化為前束范式后為 (x)(y) (z)(p(x，y)( q(x，z) r(x，z),5,4.3.1 子句集及其化簡2. 子句集的化簡（4/6）,(5) 消去存在量詞 消去存在量詞時，需要區(qū)分以下兩種情況： 若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。 若存在量

6、詞位于一個或多個全稱量詞的轄域內(nèi)，例如 (x1)(xn) (y)p(x1，x2 , xn ,y) 則需要用skolem函數(shù)f(x1，x2 , xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。 例如，上步所得公式中存在量詞(y)和(z)都位于(x)的轄域內(nèi)，因此都需要用skolem函數(shù)來替換。設(shè)替換y和z的skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為 (x)(p(x,f(x)(q(x,g(x)r(x,g(x),6,4.3.1 子句集及其化簡2. 子句集的化簡（5/6）,(6) 化為skolem標(biāo)準(zhǔn)形 skolem標(biāo)準(zhǔn)形的一般形式為 (x1)(xn) m(x1,x2,xn)

7、 其中， m(x1,x2,xn)是skolem標(biāo)準(zhǔn)形的母式，它由子句的合取所構(gòu)成。 把謂詞公式化為skolem標(biāo)準(zhǔn)形需要使用以下等價關(guān)系 p(qr) (pq)(pr) 例如，前面的公式化為skolem標(biāo)準(zhǔn)形后為 (x)(p(x,f(x)q(x,g(x)(p(x,f(x)r(x,g(x) (7) 消去全稱量詞 由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。 例如，上式消去全稱量詞后為 (p(x,f(x)q(x,g(x) (p(x,f(x)r(x,g(x),7,4.3.1 子句集及其化簡2. 子句集的化簡（

8、6/6）,(8) 消去合取詞 在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。 例如，上式的子句集中包含以下兩個子句 p(x,f(x)q(x,g(x) p(x,f(x)r(x,g(x) (9) 更換變量名稱 對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關(guān)系。這樣，更換變量名是不會影響公式的真值的。 例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集 p(x,f(x)q(x,g(x) p

9、(y,f(y)r(y,g(y),8,4.3.1 子句集及其化簡3. 子句集的應(yīng)用（1/4）,在上述化簡過程中，由于在消去存在量詞時所用的skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不唯一的。 這樣，當(dāng)原謂詞公式為非永假時，它與其標(biāo)準(zhǔn)子句集并不等價。但當(dāng)原謂詞公式為永假（或不可滿足）時，其標(biāo)準(zhǔn)子句集則一定是永假的，即skolem化并不影響原謂詞公式的永假性。 這個結(jié)論很重要，是歸結(jié)原理的主要依據(jù)，可用定理的形式來描述。 定理4.1 設(shè)有謂詞公式f，其標(biāo)準(zhǔn)子句集為s，則f為不可滿足的充要條件是s為不可滿足的。 要證明一個謂詞公式是不可滿足的，只要證明其相應(yīng)的標(biāo)準(zhǔn)子句集是不可滿足的就可以了。至

10、于如何證明一個子句集的不可滿足性，由下面的海伯倫理論和魯賓遜歸結(jié)原理來解決。,9,4.3.2 魯濱遜歸結(jié)原理1. 基本思想,注意以下兩個關(guān)鍵 第一，子句集中的子句之間是合取關(guān)系。因此，子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的； 第二，空子句是不可滿足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。 魯濱遜歸結(jié)原理基本思想 首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴充的子句集s。然后設(shè)法檢驗子句集s是否含有空子句，若含有空子句，則表明s是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)

11、為止。 魯濱遜歸結(jié)原理包括 命題邏輯歸結(jié)原理 謂詞邏輯歸結(jié)原理,10,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（1/8）,歸結(jié)推理的核心是求兩個子句的歸結(jié)式 (1) 歸結(jié)式的定義及性質(zhì) 定義1 若p是原子謂詞公式，則稱p與p為互補文字。 定義2 設(shè)c1和c2是子句集中的任意兩個子句，如果c1中的文字l1與c2中的文字l2互補，那么可從c1和c2中分別消去l1和l2，并將c1和c2中余下的部分按析取關(guān)系構(gòu)成一個新的子句c12，則稱這一過程為歸結(jié)，稱c12為c1和c2的歸結(jié)式，稱c1和c2為c12的親本子句。 例4.7 設(shè)c1=pqr，c2=ps，求c1和c2的歸結(jié)式c12。 解：這里l1=

12、p，l2=p，通過歸結(jié)可以得到 c12= qrs 例4.8 設(shè)c1=q，c2=q，求c1和c2的歸結(jié)式c12。 解：這里l1=q，l2=q，通過歸結(jié)可以得到 c12= nil,11,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（2/8）,例4.9 設(shè)設(shè)c1 =p q ，c2=q，c3=p，求c1、c2、c3的歸結(jié)式c123。 解：若先對c1、c2歸結(jié)，可得到 c12=p 然后再對c12和c3歸結(jié)，得到 c123=nil 如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過程是不唯一的。 其歸結(jié)歸結(jié)過程可用右圖來表示，該樹稱為歸結(jié)樹。,12,p q,q,p,p,nil,p q,p,q,q,ni

13、l,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（3/8）,定理4.4 歸結(jié)式c12是其親本子句c1和c2的邏輯結(jié)論。 證明：（按定義）設(shè)c1=lc1 ，c2=lc2關(guān)于解釋i為真，則只需證明c12= c1 c2關(guān)于解釋i也為真。 對于解釋i，l和l中必有一個為假。 若l為假，則必有c1為真，不然就會使c1為假，這將與前提假設(shè)c1為真矛盾，因此只能有c1為真。 同理，若l為假，則必有c2為真。 因此，必有c12= c1c2關(guān)于解釋i也為真。即c12是c1和c2的邏輯結(jié)論。,13,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（4/8）,上述定理是歸結(jié)原理中的一個重要定理，由它可得到以下兩個推

14、論： 推論1：設(shè)c1和c2是子句集s中的兩個子句，c12是c1和c2的歸結(jié)式，若用c12代替c1和c2后得到新的子句集s1，則由s1的不可滿足性可以推出原子句集s的不可滿足性。即： s1的不可滿足性 s的不可滿足性 推論2：設(shè)c1和c2是子句集s中的兩個子句，c12是c1和c2的歸結(jié)式，若把c12加入s中得到新的子句集s2，則s與s2的不可滿足性是等價的。即： s2的不可滿足性s的不可滿足性,14,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（5/8）,上述兩個推論說明，為證明子句集s的不可滿足性，只要對其中可進行歸結(jié)得子句進行歸結(jié)，并把歸結(jié)式加入到子句集s中，或者用歸結(jié)式代替他的親本子句，

15、然后對新的子句集證明其不可滿足性就可以了。 如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集s是不可滿足的結(jié)論。 在命題邏輯中，對不可滿足的子句集s，其歸結(jié)原理是完備的。 這種不可滿足性可用如下定理描述： 不可滿足性： 子句集s是不可滿足的，當(dāng)且僅當(dāng)存在一個從s到空子句的歸結(jié)過程。,15,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（6/8）,(2) 命題邏輯的歸結(jié)反演 歸結(jié)原理：假設(shè)f為已知前提，g為欲證明的結(jié)論，歸結(jié)原理把證明g為f的邏輯結(jié)論轉(zhuǎn)化為證明fg為不可滿足。 再根據(jù)定理3.1，在不可滿足的意義上，公式集fg與其子句集是等價的，即把公式集上的不可滿足轉(zhuǎn)化為子句集上

16、的不可滿足。 應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。 在命題邏輯中，已知f，證明g為真的歸結(jié)反演過程如下： 否定目標(biāo)公式g，得g; 把g并入到公式集f中，得到f，g； 把f，g化為子句集s。 應(yīng)用歸結(jié)原理對子句集s中的子句進行歸結(jié)，并把每次得到的歸結(jié)式并入s中。如此反復(fù)進行，若出現(xiàn)空子句，則停止歸結(jié)，此時就證明了g為真。,16,4.3.2 魯濱遜歸結(jié)原理2. 命題邏輯的歸結(jié)（7/8）,例 ： 設(shè)已知的公式集為p, (pq)r, (st)q, t，求證結(jié)論r。 解：假設(shè)結(jié)論r為假, 將r加入公式集，并化為子句集 s=p,pqr, sq, tq, t, r 其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。該樹

17、根為空子句。 其含義為：先假設(shè)子句集s中的所有子句均為真，即原公式集為真,r也為真；然后利用歸結(jié)原理，對子句集進行歸結(jié)，并把所得的歸結(jié)式并入子句集中；重復(fù)這一過程，最后歸結(jié)出了空子句。 根據(jù)歸結(jié)原理的完備性，可知子句集s是不可滿足的，即開始時假設(shè)r為真是錯誤的，這就證明了r為真。,17,p qr, r,p q,p,q,t q,t,t,nil,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（1/16）,在謂詞邏輯中，由于子句集中的謂詞一般都含有變元，因此不能象命題邏輯那樣直接消去互補文字。而需要先用一個最一般合一對變元進行代換，然后才能進行歸結(jié)?？梢姡^詞邏輯的歸結(jié)要比命題邏輯的歸結(jié)麻煩一些。

18、謂詞邏輯的歸結(jié)原理 謂詞邏輯中的歸結(jié)式可用如下定義來描述： 定義4.11 設(shè)c1和c2是兩個沒有公共變元的子句，l1和l2分別是c1和c2中的文字。如果l1和l2存在最一般合一，則稱 c12=(c1- l1)( c2- l2) 為c1和c2的二元歸結(jié)式，而l1和l2為歸結(jié)式上的文字。,18,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（2/16）,例： 設(shè)c1=p(a)r(x)，c2=p(y)q(b)，求 c12 解：取l1= p(a), l2=p(y)，則l1和l2的最一般合一是=a/y。根據(jù)定義可得 c12=( c1-l1) (c2-l2) =(p(a), r(x)-p(a)(p(a),

19、 q(b)-p(a) =(r(x)(q(b)= r(x), q(b) =r(x)q(b) 例： 設(shè)c1=p(x)q(a)，c2=p(b)r(x) ，求 c12 解：由于c1和c2有相同的變元x，不符合定義4.11的要求。為了進行歸結(jié)，需要修改c2中變元x的名字為，令c2=p(b)r(y)。此時l1= p(x), l2 =p(b)，l1和l2的最一般合一是=b/x。則有 c12=( c1-l1) (c2-l2) =(p(b), q(a)-p(b) (p(b), r(y)-p(b) =(q(a) (r(y)= q(a), r(y) =q(a)r(y),19,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯

20、的歸結(jié)（4/16）,例： 設(shè)c1=p(x)q(b)，c2=p(a)q(y)r(z) 解：對c1和c2通過最一般合一（=a/x, b/y）的作用，可以得到兩個互補對。 注意：求歸結(jié)式不能同時消去兩個互補對，這樣的結(jié)果不是二元歸結(jié)式。如在=a/x, b/y下，若同時消去兩個互補對，所得的r(z)不是c1和c2的二元歸結(jié)式。 例： 設(shè)c1=p(x)p(f(a)q(x) ，c2=p(y)r(b)，求c12 解：對參加歸結(jié)的某個子句，若其內(nèi)部有可合一的文字，則在進行歸結(jié)之前應(yīng)先對這些文字進行合一。本例的c1中有可合一的文字p(x)與p(f(a)，若用它們的最一般合一=f(a)/x進行代換，可得到 c1=

21、p(f(a)q(f(a) 此時可對c1與c2進行歸結(jié)。選l1= p(f(a), l2 =p(y)，l1和l2的最一般合一是=f(a)/y，則可得到c1和c2的二元歸結(jié)式為 c12=r(b)q(f(a) 我們把c1稱為c1的因子。一般來說，若子句c中有兩個或兩個以上的文字具有最一般合一，則稱c為子句c的因子。如果c是一個單文字，則稱它為c的單元因子。 應(yīng)用因子概念，可對謂詞邏輯中的歸結(jié)原理給出如下定義：,20,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（5/16）,定義4.12若c1和c2是無公共變元的子句，則 c1和c2的二元歸結(jié)式; c1和c2的因子c22的二元歸結(jié)式； c1的因子c11

22、和c2的二元歸結(jié)式； c1的因子c11和c2的因子c22的二元歸結(jié)式。 這四種二元歸結(jié)式都是子句c1和c2的二元歸結(jié)式，記為c12。 例：設(shè)c1=p(y)p(f(x)q(g(x) ，c2=p(f(g(a)q(b)，求c12。 解：對c1 ，取最一般合一=f(x)/y，得c1的因子 c1=p(f(x)q(g(x) 對c1的因子和c2歸結(jié)（=g(a)/x ），可得到c1和c2的二元歸結(jié)式 c12=q(g(g(a)q(b),21,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（6/16）,謂詞邏輯的歸結(jié)反演 謂詞邏輯的歸結(jié)反演過程與命題邏輯的歸結(jié)反演過程相比，其步驟基本相同，但每步的處理對象不同。例

23、如，在步驟(3)化簡子句集時，謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集；在步驟(4)按歸結(jié)原理進行歸結(jié)時，謂詞邏輯的歸結(jié)原理需要考慮兩個親本子句的最一般合一。 例4.12 已知 f: (x)(y)(a(x, y)b(y)(y)(c(y)d(x, y) g: (x)c(x)(x)(y)(a(x, y)b(y) 求證g是f的邏輯結(jié)論。 證明：先把g否定，并放入f中，得到的f, g為 ( x)( y)(a(x,y)b(y)( y)(c(y)d(x,y), ( x)c(x)( x)( y)(a(x,y) b(y),22,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（7/16）,再把f,g化成子句集

24、，得到 (1) a(x,y) b(y) c(f(x) (2) a(u,v) b(v) d(u,f(u) (3) c(z) (4) a(m,n) (5) b(k) 其中，(1)、(2)是由f 化出的兩個子句，(3)、(4)、(5)是由g化出的3個子句。 最后應(yīng)用謂詞邏輯的歸結(jié)原理對上述子句集進行歸結(jié)，其過程為 (6) a(x,y) b(y) 由(1)和(3)歸結(jié)，取=f(x)/z (7) b(n) 由(4)和(6)歸結(jié)，取=m/x,n/y (8) nil 由(5)和(7)歸結(jié)，取=n/k 因此，g是f 的邏輯結(jié)論。 上述歸結(jié)過程可用如下歸結(jié)樹來表示,23,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯

25、的歸結(jié)（8/16）,24,a(x,y) b(y)c(f(x), c(z),a(x,y) b(y),a(m,n), b(n),b(k),nil,f(x)/z,m/x,n/y,n/k,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（13/16）,為了進一步加深對謂詞邏輯歸結(jié)的理解，下面再給出一個經(jīng)典的歸結(jié)問題 例：“激動人心的生活”問題 假設(shè)：所有不貧窮并且聰明的人都是快樂的，那些看書的人是聰明的。李明能看書且不貧窮，快樂的人過著激動人心的生活。 求證：李明過著激動人心的生活。 解：先定義謂詞： poor(x) x是貧窮的 smart(x) x是聰明的 happy(x) x是快樂的 read(x)

26、 x能看書 exciting(x) x過著激動人心的生活,25,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（14/16）,再將問題用謂詞表示如下： “所有不貧窮并且聰明的人都是快樂的” (x)(poor(x)smart(x)happy(x) “那些看書的人是聰明的” (y) (read(y) smart(y) “李明能看書且不貧窮” read(liming)poor(liming) “快樂的人過著激動人心的生活” (z) (happy(z)exciting(z) 目標(biāo)“李明過著激動人心的生活”的否定 exciting(liming),26,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（1

27、5/16）,將上述謂詞公式轉(zhuǎn)化為子句集如下： (1) poor(x)smart(x)happy(x) (2) read(y)smart(y) (3) read(liming) (4) poor(liming) (5) happy(z)exciting(z) (6) exciting(liming) (結(jié)論的否定),27,4.3.2 魯濱遜歸結(jié)原理3. 謂詞邏輯的歸結(jié)（16/16）,28,exciting(liming),happy(z)exciting(z),happy(liming),poor(x)smart(x)happy(x),poor(liming)smart(liming),read

28、(y)smart(y ),poor(liming)read(liming),poor(liming),read(liming),read(liming),nil,liming/z,liming/x,liming/y,4.3.3 歸結(jié)演繹推理的歸結(jié)策略,歸結(jié)演繹推理實際上就是從子句集中不斷尋找可進行歸結(jié)的子句對，并通過對這些子句對的歸結(jié)，最終得出一個空子句的過程。由于事先并不知道哪些子句對可進行歸結(jié)，更不知道通過對哪些子句對的歸結(jié)能盡快得到空子句，因此就需要對子句集中的所有子句逐對進行比較，直到得出空子句為止。這種盲目的全面進行歸結(jié)的方法，不僅會產(chǎn)生許多無用的歸結(jié)式，更嚴(yán)重的是會產(chǎn)生組核爆炸問題

29、。因此，需要研究有效的歸結(jié)策略來解決這些問題。 目前，常用的歸結(jié)策略可分為兩大類，一類是刪除策略，另一類是限制策略。刪除策略是通過刪除某些無用的子句來縮小歸結(jié)范圍；限制策略是通過對參加歸結(jié)的子句進行某些限制，來減少歸結(jié)的盲目性，以盡快得到空子句。為了說明選擇歸結(jié)策略的重要性，在討論各種常用的歸結(jié)策略之前，還是先提一下廣度優(yōu)先策略。,29,4.3.3 歸結(jié)演繹推理的歸結(jié)策略1. 廣度優(yōu)先策略（1/3）,廣度優(yōu)先是一種窮盡子句比較的復(fù)雜搜索方法。設(shè)初始子句集為s0，廣度優(yōu)先策略的歸結(jié)過程可描述如下： (1) 從s0出發(fā)，對s0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為s

30、1; (2) 用s0中的子句與s1中的子句進行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為s2; (3) 用s0和s1中的子句與s2中的子句進行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為s3; 如此繼續(xù)，知道得出空子句或不能再繼續(xù)歸結(jié)為止。 例： 設(shè)有如下子句集： s=i(x)r(x), i(a), r(y)l(y), l(a) 用寬度優(yōu)先策略證明s為不可滿足。 寬度優(yōu)先策略的歸結(jié)樹如下：,30,4.3.3 歸結(jié)演繹推理的歸結(jié)策略1. 廣度優(yōu)先策略（2/3）,31,i(x)r(x),i(a),r(y)l(y),l(a),r(a),i(x) l(x),r(a),l(a)

31、,l(a),i(a),i(a),nil,s,s1,s2,4.3.3 歸結(jié)演繹推理的歸結(jié)策略1. 廣度優(yōu)先策略（3/3）,從這個例子可以看出，寬度優(yōu)先策略歸結(jié)出了許多無用的子句，既浪費事間，又浪費空間。但是，這種策略由一個有趣的特性，就是當(dāng)問題有解時保證能找到最短歸結(jié)路徑。 因此，它是一種完備的歸結(jié)策略。寬度優(yōu)先對大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對小問題卻仍是一種比較好的歸結(jié)策略。,32,4.3.3 歸結(jié)演繹推理的歸結(jié)策略2. 支持集策略（1/3）,支持集策略是沃斯(wos)等人在1965年提出的一種歸結(jié)策略。它要求每一次參加歸結(jié)的兩個親本子句中，至少應(yīng)該有一個是由目標(biāo)公式的否定所得到的子句或它

32、們的后裔。可以證明支持集策略是完備的，即當(dāng)子句集為不可滿足時，則由支持集策略一定能夠歸結(jié)出一個空子句。也可以把支持集策略看成是在寬度優(yōu)先策略中引入了某種限制條件，這種限制條件代表一種啟發(fā)信息，因而有較高的效率 例：設(shè)有如下子句集： s=i(x)r(x), i(a), r(y)l(y), l(a) 其中，i(x)r(x)為目標(biāo)公式的否定。用支持集策略證明s為不可滿足。,33,4.3.3 歸結(jié)演繹推理的歸結(jié)策略2. 支持集策略（2/3）,34,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,4.3.3 歸結(jié)演繹推理的歸結(jié)策

33、略2. 支持集策略（3/3）,從上述歸結(jié)過程可以看出，各級歸結(jié)式數(shù)目要比寬度優(yōu)先策略生成的少，但在第二級還沒有空子句。就是說這種策略限制了子句集元素的劇增，但會增加空子句所在的深度。此外，支持集策略具有逆向推理的含義，由于進行歸結(jié)的親本子句中至少有一個與目標(biāo)子句有關(guān)，因此推理過程可以看作是沿目標(biāo)、子目標(biāo)的方向前進的。,35,4.3.5 歸結(jié)演繹推理的歸結(jié)策略3. 刪除策略（1/3）,主要想法是：歸結(jié)過程在尋找可歸結(jié)子句時，子句集中的子句越多，需要付出的代價就會越大。如果在歸結(jié)時能把子句集中無用的子句刪除掉，這就會縮小搜索范圍，減少比較次數(shù)，從而提高歸結(jié)效率。 常用的刪除方法有以下幾種（純文字、

34、重言式、包孕） 純文字刪除法 如果某文字l在子句集中不存在可與其互補的文字l，則稱該文字為純文字。 在歸結(jié)過程中，純文字不可能被消除，用包含純文字的子句進行歸結(jié)也不可能得到空子句，因此對包含純文字的子句進行歸結(jié)是沒有意義的，應(yīng)該把它從子句集中刪除。 對子句集而言，刪除包含純文字的子句，是不影響其不可滿足性的。例如，對子句集 s=pqr, qr, q, r 其中p是純文字，因此可以將子句pqr從子句集s中刪除。,36,4.3.3 歸結(jié)演繹推理的歸結(jié)策略3. 刪除策略（2/3）,重言式刪除法 如果一個子句中包含有互補的文字對，則稱該子句為重言式。例如 p(x)p(x), p(x)q(x)p(x)

35、都是重言式，不管p(x)的真值為真還是為假，p(x)p(x)和p(x)q(x)p(x)都均為真。 重言式是真值為真的子句。對一個子句集來說，不管是增加還是刪除一個真值為真的子句，都不會影響該子句集的不可滿足性。因此，可從子句集中刪去重言式。,37,4.3.3 歸結(jié)演繹推理的歸結(jié)策略3. 刪除策略（3/3）,包孕刪除法 設(shè)有子句c1和c2，如果存在一個置換，使得c1c2，則稱c1包孕于c2。例如 p(x) 包孕于 p(y)q(z) =y/x 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

36、 p(x) q(y) 包孕于 p(a)q(u)r(w) =a/x, u/y 對子句集來說，把其中包孕的子句刪去后，不會影響該子句集的不可滿足性。因此，可從子句集中刪除哪些包孕的子句。,38,4.3.3 歸結(jié)演繹推理的歸結(jié)策略4. 單文字子句策略（1/2）,如果一個子句只包含一個文字，則稱此子句為單文字子句。單文字子句策略是對支持集策略的進一步改進，它要求每次參加歸結(jié)的兩個親本子句中至少有一個子句是單文字子句。 例： 設(shè)有如下子句集： s=i(x)r(x), i(a), r(y)l(y), l(a) 用單文字子句策略證明s為不可滿足。 采用單文字子句策略，歸結(jié)式包含的文字?jǐn)?shù)將少于其親本子句中的文

37、字?jǐn)?shù)，這將有利于向空子句的方向發(fā)展，因此會有較高的歸結(jié)效率。但這種策略是不完備的，即當(dāng)子句集為不可滿足時，用這種策略不一定能歸結(jié)出空子句。,39,4.3.3 歸結(jié)演繹推理的歸結(jié)策略4. 單文字子句策略（2/2）,40,i(x)r(x),i(a),r(y)l(y),l(a),r(a),r(a),nil,4.3.3 歸結(jié)演繹推理的歸結(jié)策略5. 祖先過濾策略（1/2）,這種策略與線性輸入策略有點相似，但是，放寬了對子句的限制。每次參加歸結(jié)的兩個親本子句，只要滿足以下兩個條件中的任意一個就可進行歸結(jié)： (1) 兩個親本子句中至少有一個是初始子句集中的子句。 (2) 如果兩個親本子句都不是初始子句集中的

38、子句，則一個子句應(yīng)該是另一個子句的先輩子句。所謂一個子句(例如c1)是另一個子句(例如c2)的先輩子句是指c2是由c1與別的子句歸結(jié)后得到的歸結(jié)式。 例：設(shè)有如下子句集： s=q(x)p(x), q(y)p(y)，q(w)p(w) , q(a)p(a) 用祖先過濾策略證明s為不可滿足 證明：從s出發(fā)，按祖先過濾策略歸結(jié)過程如下圖所示。 可以證明祖先過濾策略也是完備的。 上面分別討論了幾種基本的歸結(jié)策略，但在實際應(yīng)用中，還可以把幾種策略結(jié)合起來使用。總之，在選擇歸結(jié)反演策略時，主要應(yīng)考慮其完備性和效率問題。,41,4.3.3 歸結(jié)演繹推理的歸結(jié)策略5. 祖先過濾策略（2/2）,42,q(x) p

39、(x),q(y)p(y), p(x), q(w)p(w), q(w),q(a)p(a),p(a),nil,4.3.4 用歸結(jié)反演求取問題的答案（1/4）,歸結(jié)原理出了可用于定理證明外，還可用來求取問題答案，其思想與定理證明相似。其一般步驟為： (1) 把問題的已知條件用謂詞公式表示出來，并化為相應(yīng)的子句集； (2) 把問題的目標(biāo)的否定用謂詞公式表示出來，并化為子句集； (3) 對目標(biāo)否定子句集中的每個子句，構(gòu)造該子句的重言式（即把該目標(biāo)否定子句和此目標(biāo)否定子句的否定之間再進行析取所得到的子句），用這些重言式代替相應(yīng)的目標(biāo)否定子句式，并把這些重言式加入到前提子句集中，得到一個新的子句集； (4)

40、 對這個新的子句集，應(yīng)用歸結(jié)原理求出其證明樹，這時證明樹的根子句不為空，稱這個證明樹為修改的證明樹； (5) 用修改證明樹的根子句作為回答語句，則答案就在此根子句中。,43,4.3.4 用歸結(jié)反演求取問題的答案（2/4）,下面再通過一個例子來說明如何求取問題的答案。 例： 已知：“張和李是同班同學(xué)，如果x和y是同班同學(xué)，則x的教室也是y的教室，現(xiàn)在張在302教室上課?！?問：“現(xiàn)在李在哪個教室上課？” 解：首先定義謂詞： c(x, y) x和y是同班同學(xué)； at(x, u) x在u教室上課。 把已知前提用謂詞公式表示如下： c(zhang, li) (x) (y) (u) (c(x, y)at

41、(x, u)at(y,u) at(zhang, 302) 把目標(biāo)的否定用謂詞公式表示如下： (v)at(li, v),44,4.3.4 用歸結(jié)反演求取問題的答案（3/4）,把上述公式化為子句集： c(zhang, li) c(x, y)at(x, u)at(y, u) at(zhang, 302) 把目標(biāo)的否定化成子句式，并用重言式 at(li,v) at(li,v) 代替之。 把此重言式加入前提子句集中，得到一個新的子句集，對這個新的子句集，應(yīng)用歸結(jié)原理求出其證明樹。其求解過程如下圖所示。 該證明樹的根子句就是所求的答案，即“李明在302教室”。,45,4.3.4 用歸結(jié)反演求取問題的答案（

42、4/4）,46,at(li,v)at(li,v),c(x, y)at(x, u)at(y, u),at(li,v) c(x, li)at(x, v),c(zhang, li), at(zhang,v)at(li, v),at(zhang, 302),at(li, 302),li/y,v/u,zhang/x,302/v,4.4 與/或形演繹推理,上一節(jié)討論了歸結(jié)演繹推理，它需要把謂詞公式化為子句形，盡管這種轉(zhuǎn)化在邏輯上是等價的，但是原來蘊含在謂詞公式中的一些重要信息卻會在求取子句形的過程中被丟失。例如，下面的幾個蘊含式 abc, acb, abc, bac, 都與子句 abc 等價。但在abc中

43、，是根本得不到原邏輯公式中所蘊含的哪些超邏輯的含義的。況且，在不少情況下人們多希望使用那種接近于問題原始描述的形式來進行求解，而不希望把問題描述化為子句集。 規(guī)則是一種比較接近于人們習(xí)慣的問題描述方式，按照這種問題描述方式進行求解的系統(tǒng)稱為基于規(guī)則的系統(tǒng)，或者叫做基于規(guī)則的演繹系統(tǒng)。 規(guī)則演繹系統(tǒng)的推理可分為正向演繹推理、逆向演繹推理三種形式。,47,4.4.1與/或形正向演繹推理,與/或形正向演繹和前面所討論過的正向推理相對應(yīng)。 它是從已知事實出發(fā)，正向使用規(guī)則，直接進行演繹，直至到達目標(biāo)為止的一種證明方法。一個直接演繹系統(tǒng)不一定比反演系統(tǒng)更有效，但其演繹過程容易被人們所理解。,48,4.4

44、.1 與/或形演繹推理1. 事實表達式的與/或形變換（1/2）,在一個基于規(guī)則的正向演繹系統(tǒng)中，其前提條件中的事實表達式是作為系統(tǒng)的初始綜合數(shù)據(jù)庫來描述的。對事實的化簡，只須轉(zhuǎn)換成不含蘊含符號“”的與/或形表示即可，而不必化成子句集。把事實表達式化為非蘊含形式的與/或形的主要步驟如下： (1) 利用連接詞化規(guī)律“pqpq”，消去蘊含符號。事實上，在事實表達式中很少有含蘊含符號“”出現(xiàn)，因為可把蘊含式表示成規(guī)則。 (2) 利用狄.摩根定律及量詞轉(zhuǎn)換率把“”移到緊靠謂詞的位置，直到每個否定符號的轄域最多只含一個謂詞為止。 (3) 對所得到的表達式進行前束化。 (4) 對全稱量詞轄域內(nèi)的變量進行改名

45、和標(biāo)準(zhǔn)化，對存在量詞量化的變量用skolem函數(shù)代替，使不同量詞約束的變元有不同的名字。 (5) 消去全稱量詞，而余下的變量都被認為是全程量詞量化的變量。 (6) 對變量進行換名，使主合取元具有不同的變量名。,49,4.4.1與/或形演繹推理1. 事實表達式的與/或形變換（2/2）,例如，有如下表達式 (x) (y)(q(y, x)(r(y)p(y)s(x, y) 可把它轉(zhuǎn)化為： q(z, a)(r(y)p(y)s(a, y) 這就是與/或形表示。,50,4.4.1與/或形演繹推理2. 事實表達式的與/或樹表示（1/3）,事實表達式的與/或形可用一棵與/或樹表示出來。例如，對上例所給出的與/或

46、式，可用如下與/或樹來表示。,51,q(z, a)(r(y)p(y)s(a, y),q(z, a),(r(y)p(y)s(a, y),r(y)p(y),s(a, y),r(y),p(y),4.4.1與/或形演繹推理2. 事實表達式的與/或樹表示（2/3）,在該圖中，每個節(jié)點表示該事實表達式的一個子表達式，子表達式之間的與、或關(guān)系規(guī)定如下： 當(dāng)某個表達式為k個子表達式的析取時，例如e1e2ek，其中的每個子表達式 ei 均被表示為 e1e2ek 的后繼節(jié)點，并由一個k線連接符將這些后繼節(jié)點都連接到其父節(jié)點，即表示成與的關(guān)系。 當(dāng)某個表達式為k個子表達式的合取時，例如e1e2ek，其中的每個子表達

47、式 ei 均被表示成 e1e2ek 的一個單一的后繼節(jié)點，并由一個單一連接符連接到其父節(jié)點，即表示成或的關(guān)系。 這樣，與/或樹的根節(jié)點就是整個事實表達式，端節(jié)點均為事實表達式中的一個文字。有了與/或樹的表示，就可以求出其解樹（結(jié)束于文字節(jié)點上的子樹）集。并且可以發(fā)現(xiàn)，事實表達式的子句集與解樹集之間存在著一一對應(yīng)關(guān)系，即解樹集中的每個解樹都對應(yīng)著子句集中的一個子句。其對應(yīng)方式為：解樹集中每個解樹的端節(jié)點上的文字的析取就是子句集中的一個子句。 例如，上圖所示的與/或樹有3個解樹，分別對應(yīng)這以下3個子句： q(z, a) r(y) s(a, y) p(y) s(a, y),52,4.4.1與/或形演

48、繹推理2. 事實表達式的與/或樹表示（3/3）,與/或樹的這個性質(zhì)很重要，它可以把與/或樹看作是對子句集的簡潔表示。不過，表達式的與/或樹表示要比子句集表示的通用性差一些，原因是與/或樹中的合取元沒有進一步展開，因此不能象在子句形中那樣對某些變量進行改名，這就限制了與/或樹表示的靈活性。例如，上面的最后一個子句，在子句集中其變量y可全部改名為x，但卻無法在與/或樹中加以表示，因而失去了通用性，并且可能帶來一些困難。,53,4.4.1與/或形演繹推理3. 規(guī)則的與/或形變換（1/2）,在與/或形正向演繹系統(tǒng)中，是以正向方式使用規(guī)則(f規(guī)則)對綜合數(shù)據(jù)庫中的與/或樹結(jié)構(gòu)進行變換的。為簡化這種演繹過

49、程，通常要求f規(guī)則應(yīng)具有如下形式： lw 其中，l為單文字，w為與/或形公式。假定出現(xiàn)在蘊含式中的任何變量全都受全稱量詞的約束，并且這些變量已經(jīng)被換名，使得他們與事實公式和其他規(guī)則中的變量不同。 如果領(lǐng)域知識的規(guī)則表示形式與上述要求不同，則應(yīng)將它轉(zhuǎn)換成要求的形式。其變換步驟如下：,54,4.4.1與/或形演繹推理3. 規(guī)則的與/或形變換（2/2）,(1) 暫時消去蘊含符號“”。設(shè)有如下公式： (x)(y) ( z)p(x, y,z)(u)q(x, u) 運用等價關(guān)系“pqpq”，可將上式變?yōu)椋?(x)( y) (z)p(x, y,z)(u)q(x, u) (2) 把否定符號“”移到緊靠謂詞的位

50、置上，使其作用域僅限于單個謂詞。通過使用狄.摩根定律及量詞轉(zhuǎn)換率可把上式轉(zhuǎn)換為： ( x)( (y) (z)p(x, y,z) (u)q(x, u) (3) 引入skolem函數(shù)，消去存在量詞。消去存在量詞后，上式可變?yōu)椋?( x)( (y) (p(x, y,f(x,y)(u)q(x, u) 化成前束式，消去全部全稱量詞。消去全稱量詞后，上式變?yōu)椋?p(x, y,f(x,y)q(x, u) 此公式中的變元都被視為受全稱量詞約束的變元。 (5) 恢復(fù)蘊含式表示。利用等價關(guān)系“pqpq”將上式變?yōu)椋?p(x, y,f(x,y)q(x, u) 在上述對f規(guī)則的要求中，之所以限制其前件為單文字，是因為

51、在進行正向演繹推理時要用f規(guī)則作用于表示事實的與/或樹，而該與/或樹的葉節(jié)點都是單文字，這樣就可用f規(guī)則的前件與葉節(jié)點進行簡單匹配。對非單文字情況，若形式為l1l2w，則可將其轉(zhuǎn)換成與之等價的兩個規(guī)則l1w與 l2w進行處理。,55,4.4.1與/或形演繹推理4. 目標(biāo)公式的表示形式,與/或樹正向演繹系統(tǒng)要求目標(biāo)公式用子句形表示。如果目標(biāo)公式不是子句形，則需要化成子句形。把一個目標(biāo)公式轉(zhuǎn)化為子句形的步驟與第3節(jié)所述的化簡子句形的步驟類似，但skolem化的過程不同。目標(biāo)公式的skolem化過程是化簡子句形的skolem過程的對偶形式，即把目標(biāo)公式中屬于存在量詞轄域內(nèi)的全稱變量用存在量詞量化變量

52、的skolem函數(shù)來代替，使經(jīng)skolem化目標(biāo)公式只剩下存在量詞，然后再對析取元作變量替換，最后把存在量詞消掉。 例如：設(shè)目標(biāo)公式為 (y) (x) (p(x, y)q(x, y) 用skolem函數(shù)消去全稱量詞后有 (y)(p(f(y), y)q(f(y), y) 進行變量換名，使每個析取元具有不同的變量符號，于是有 (y)p(f(y), y)(z)q(f(z), z) 最后，消去存在量詞得 p(f(y), y)q(f(z), z) 這樣，目標(biāo)公式中的變量都假定受存在量詞的約束,56,4.4.1與/或形演繹推理5. 規(guī)則正向演繹系統(tǒng)（1/5）,規(guī)則正向演繹推理過程是從已知事實出發(fā)，不斷運用

53、f規(guī)則，推出欲證明目標(biāo)公式的過程。即先用與/或樹把已知事實表示出來，然后再用f規(guī)則的前件和與或樹的葉節(jié)點進行匹配，并通過一個匹配弧把匹配成功的f規(guī)則加入到與/或樹中，依此使用f規(guī)則，直到產(chǎn)生一個含有以目標(biāo)節(jié)點為終止節(jié)點的解圖為止。 下面分命題邏輯和謂詞邏輯兩種情況來討論規(guī)則正向演繹過程。,57,4.4.1與/或形演繹推理5. 規(guī)則正向演繹系統(tǒng)（2/5）,命題邏輯的規(guī)則演繹過程 由于命題邏輯中的公式不含變元，因此其規(guī)則演繹過程比較簡單。 例： 設(shè)已知事實為：ab f規(guī)則為： r1: acd r2: beg 目標(biāo)公式為：cg 證明：先將已知事實用與/或樹表示出來，然后再用匹配弧把r1和r2分別連接

54、到事實與/或樹中與r1和r2前件匹配的兩個不同端節(jié)點，由于出現(xiàn)了以目標(biāo)節(jié)點為終節(jié)點的解樹，故推理過程結(jié)束。這一證明過程可用下圖表示。,58,4.4.1與/或形演繹推理5. 規(guī)則正向演繹系統(tǒng)（3/5）,在該圖中，雙箭頭表示匹配弧，它相當(dāng)于一個單線連接符。,59,c,g,c,d,e,g,a,b,a,b,ab,目標(biāo),匹配,匹配,f規(guī)則,已知事實,r1,r2,4.4.1與/或形演繹推理5. 規(guī)則正向演繹系統(tǒng)（4/5）,為了驗證上述推理的正確性，下面再用歸結(jié)演繹推理給于證明。由已知事實、規(guī)則及目標(biāo)的否定可得到如下子句集： ab, ac, ad, be, bg, c, g 其歸結(jié)過程如下圖所示。 可見，用

55、歸結(jié)演繹推理對已知事實、f規(guī)則集目標(biāo)的否定所過程的子句集進行歸結(jié)，得到了空子句nil，從而證明了目標(biāo)公式。它與正向演繹推理所得到的結(jié)果是一致的。,60,ac,c,bg,g,ab,a,b,b,nil,4.4.1與/或形演繹推理5. 規(guī)則正向演繹系統(tǒng)（5/5）,在謂詞邏輯情況下，由于事實、f規(guī)則及目標(biāo)中均含有變元，因此，其規(guī)則演繹過程還需要用最一般合一對變進行置換。 例：設(shè)已知事實的與/或形表示為：p(x, y)(q(x)r(v, y) f規(guī)則為： p(u, v)(s(u)n(v) 目標(biāo)公式為：s(a)n(b)q(c) 其推理過程如下圖所示。,61,s(a),n(b),q(c),s(u),n(v),p(u, v),p(x, y),q(x),r(v, y),q(x)r(v, y),p(x, y)(q(x)r(v, y),a/u,b/v,c/x,u/x,v/y,4.4.2與/或形演繹推理,與/或形逆向演繹推理過程是從目標(biāo)公式的與/或樹出發(fā)，反向使用規(guī)則（b規(guī)則），對目標(biāo)公式的與/或樹進行變換，直到得出含有事實節(jié)點一致解圖為止。包括： 目標(biāo)公式的與/或形變換 目標(biāo)公式的與/或樹表示 b規(guī)則的表示形式 規(guī)則逆向演繹推理過程,62,4.4.2與/或形逆向演繹推理1. 目標(biāo)公式的與/或形變換,逆向系統(tǒng)中的目標(biāo)公式采用與/或形表示，其化簡采用與正向系統(tǒng)中對事實表達式處理