第16章謂詞演算中的歸結(jié)

1、第第1616章章 謂詞演算中的歸結(jié)謂詞演算中的歸結(jié) 第三部分第三部分 知識的表示和推理知識的表示和推理合一合一 合式公式合式公式( ( 1 1，2 2，n n)( )( 1 12 2k k) )，可縮寫為可縮寫為1 12 2k k，其中其中11，22，k k是可能是可能包含變量包含變量1 1，2 2，n n的文字。也就是說，僅僅去掉的文字。也就是說，僅僅去掉了全稱量詞，并假定了全稱量詞，并假定i i中任何變量全稱量化。這種縮寫形中任何變量全稱量化。這種縮寫形式的合式公式叫做式的合式公式叫做子句子句。有時，用集合符號。有時，用集合符號( (1 1，2 2，k k) )表達一個子句，并假定集合中的

2、元素是析取的。表達一個子句，并假定集合中的元素是析取的。 如果兩個子句的文字相匹配但是互補，我們能如果兩個子句的文字相匹配但是互補，我們能歸結(jié)歸結(jié)它它們們就像在命題演算中一樣。如果一個子句中有一個文就像在命題演算中一樣。如果一個子句中有一個文字字()( ()( 是一個變量是一個變量) )，而另一個子句中有一個互補文，而另一個子句中有一個互補文字字()()，是不包含是不包含的某個項的某個項，我們能把第一個子，我們能把第一個子句中的所有句中的所有用用代替；然后對互補文字進行命題歸結(jié)以代替；然后對互補文字進行命題歸結(jié)以產(chǎn)生那兩個子句的歸結(jié)式。產(chǎn)生那兩個子句的歸結(jié)式。 合一合一 舉例舉例：考慮兩個子句

3、：考慮兩個子句 : : P(f(y)P(f(y)， A) Q(B A) Q(B， C) C) P(xP(x， A) R(x A) R(x， C) S(A C) S(A， B) B)。 用用f(y)f(y)代替第二個子句中的代替第二個子句中的x x產(chǎn)生產(chǎn)生: : P( f(y)P( f(y)，A) R( f(y)A) R( f(y)，C) S(AC) S(A， B) B)。 現(xiàn)在，兩個子句中的第一個文字剛好互補，因此我們現(xiàn)在，兩個子句中的第一個文字剛好互補，因此我們能對文字能對文字( (f(y)f(y)，A)A)執(zhí)行一次歸結(jié)，產(chǎn)生歸結(jié)式執(zhí)行一次歸結(jié)，產(chǎn)生歸結(jié)式: : R(f(y) R(f(y)，

4、 C) S(A C) S(A， B) Q(B B) Q(B， C) C)。 用一個被稱為用一個被稱為合一合一的方法計算適當?shù)闹脫Q。合一在的方法計算適當?shù)闹脫Q。合一在AIAI中是一個極其重要的方法。中是一個極其重要的方法。 合一合一 為了描述合一，必須先討論一下置換為了描述合一，必須先討論一下置換: : 一個表達式項可能是變量符號、對象常量或者函數(shù)表達式，后者包一個表達式項可能是變量符號、對象常量或者函數(shù)表達式，后者包含函數(shù)常量和表達式項。一個表達式的置換實例通過置換那個表達式中含函數(shù)常量和表達式項。一個表達式的置換實例通過置換那個表達式中的變量項而得到。因此，的變量項而得到。因此， PxPx，

5、f(y)f(y)， B B的四個置換實例是：的四個置換實例是： PzPz，f(w)f(w)， B B Px Px，f(A)f(A)， B B Pg(z) Pg(z)，f(A)f(A)， B B PC PC，f(A)f(A)， B B 上面第一個實例稱為原始文字的上面第一個實例稱為原始文字的字母變種字母變種( ( alphabetic variant)alphabetic variant)，因為我們僅僅用另外的變量代替了因為我們僅僅用另外的變量代替了PxPx， f(y) f(y)， B B中出現(xiàn)的變量。第中出現(xiàn)的變量。第4 4個叫個叫基例基例( (ground instance)ground i

6、nstance)，因為文字中沒有一項包含變量因為文字中沒有一項包含變量( (一個基項一個基項是一個不包含任何變量的項是一個不包含任何變量的項) )。 合一合一 我們能通過一組有序?qū)ξ覀兡芡ㄟ^一組有序?qū)=s=1 1/1 1，2 2/2 2，n n/n n 來表達任何置換。來表達任何置換。i i/i i對意思是說對意思是說i i項替換在項替換在整個置換范圍內(nèi)的整個置換范圍內(nèi)的i i的每次出現(xiàn)的每次出現(xiàn)。而且，變量不能被一個。而且，變量不能被一個包含相同變量的項代替。使用前面包含相同變量的項代替。使用前面PxPx， f(y) f(y)， B B的四個的四個實例的置換是：實例的置換是： s1s1z/

7、xz/x， w/y w/y s2 s2A/yA/y s3 s3g(z)/xg(z)/x， A/y A/y s4 s4C/xC/x， A/y A/y 上面是用上面是用ss來指稱一個使用置換來指稱一個使用置換s s的表達式的表達式的一個置的一個置換實例。因此，換實例。因此，PzPz， f(w) f(w)， B= Px B= Px，f(y)f(y)，Bs1Bs1。 Pz Pz，f(w)f(w)， B B Px Px，f(A)f(A)， B B Pg(z) Pg(z)，f(A)f(A)， B B PC PC，f(A)f(A)， B B合一合一 兩個置換兩個置換s1s1和和s2s2的組合用的組合用s1s

8、2s1s2指稱，它指的是這個置指稱，它指的是這個置換通過先把換通過先把s2s2應用到應用到s1s1各項，再加上不含出現(xiàn)在各項，再加上不含出現(xiàn)在s1s1中變量中變量的所有的所有s2s2對而得到對而得到，因此；，因此； g(xg(x，y)/z y)/z A/x A/x，B/yB/y， C/w C/w， D/z D/z g(A g(A，B)/zB)/z，A/xA/x， B/y B/y， C/w C/w f(y)/x,z/y f(y)/x,z/y a/x,b/y,y/z= a/x,b/y,y/z= f(b)/x ,y/z f(b)/x ,y/z可以看出，可以看出，把把s1s1和和s2s2連續(xù)地應用到連

9、續(xù)地應用到表達式和把表達式和把s1s2s1s2應用應用到到是相同的，即：是相同的，即：( ( s1) s2 s1) s2(sls2)(sls2)。也能看出，也能看出，置換組合是符合結(jié)合律的。即：置換組合是符合結(jié)合律的。即：( (s1s2) s3s1s2) s3s1(s2s3)s1(s2s3)。 舉例舉例: :是是P(xP(x，y)y)， s1 s1是是 f(y)f(y)xx， s2 s2是是 A Ayy。那么那么 ( (s1)s2s1)s2p(f(y)p(f(y)，y) y) A Ayy P(f(A) P(f(A)，A)A)和和 (s1s2) (s1s2)P(xP(x，y) y) f(A) f

10、(A)x x，A Ayy P(f(A) P(f(A)，A) A) 合一合一 一般地講，置換不符合交換律，即一般地講，置換不符合交換律，即s1s2s1s2s2s1s2s1是不成是不成立的。因此，改變應用置換順序會產(chǎn)生差異。立的。因此，改變應用置換順序會產(chǎn)生差異。 例如：例如：是是P(xP(x，y)y)， s1 s1是是 f(y)f(y)xx， s2 s2是是A Ayy。那么那么 (s1s2) (s1s2)P(f(A)P(f(A)， A) A) (s2s1) (s2s1)P(xP(x， y) y) A Ay y，f(y)f(y)xx P(f(y) P(f(y)， A) A) 合一合一 當一個置換當

11、一個置換s s被應用到一個表達式集合被應用到一個表達式集合 i i 的每一個的每一個成員時，用成員時，用i iss表示置換實例集合。如果存在一個置換表示置換實例集合。如果存在一個置換s s，它使它使1 1s=s=2 2s=s=3 3s s，我們說表達式集合我們說表達式集合i i 是是可以可以合一的合一的( (unifiable)unifiable)。在這種情況下，在這種情況下，s s被稱為被稱為i i 的一個的一個合一式合一式( (unifier)unifier)，因為它的使用把集合壓縮成為因為它的使用把集合壓縮成為一個單元素集合。一個單元素集合。例如：例如： s s A Ax x，B Byy

12、把集合把集合pxpx，f(y)f(y)，BB， Px Px，f(B)f(B)，BB合一產(chǎn)生合一產(chǎn)生 pApA，f(B)f(B)，BB。 最一般最一般( (或最簡單或最簡單) )的合一式的合一式( (mgu)mgu)i i 的的g g有下面的有下面的特性：如果特性：如果s s是產(chǎn)生是產(chǎn)生i iss的的i i 的任意合一式，那么存的任意合一式，那么存在一個置換在一個置換ss以使以使i iss i igs gs 。而且，經(jīng)一個而且，經(jīng)一個最一般的合一式產(chǎn)生的通用實例除了字母變化外是惟一的。最一般的合一式產(chǎn)生的通用實例除了字母變化外是惟一的。 合一合一 有很多算法可以用來找到一個可以合一的表達式的有限

13、集合的有很多算法可以用來找到一個可以合一的表達式的有限集合的mgumgu，并且當那個集合不能被合一時能返回失敗。這里給出的算法并且當那個集合不能被合一時能返回失敗。這里給出的算法UNIFYUNIFY工作在一個列表結(jié)構(gòu)的表達式集合上，在這些表達式中，每個工作在一個列表結(jié)構(gòu)的表達式集合上，在這些表達式中，每個文字和項作為一個列表項。例如：文字和項作為一個列表項。例如：P(xP(x， f(A f(A， y) y)寫為寫為( (P x P x (f A y)(f A y)列表結(jié)構(gòu)形式，表達式列表結(jié)構(gòu)形式，表達式P P是列表中的第一個頂級表達式，是列表中的第一個頂級表達式，( (f A y)f A y)

14、是第三個頂級表達式。是第三個頂級表達式。 UNIFY UNIFY的基礎(chǔ)是的基礎(chǔ)是分歧集分歧集( (disagreement set)disagreement set)的思想。一個非空的的思想。一個非空的表達式集合表達式集合W W的分歧集由下面的方法得到：的分歧集由下面的方法得到： 首先定位第一個符號首先定位第一個符號( (從左邊計數(shù)從左邊計數(shù)) )，如果在這個位置不是，如果在這個位置不是W W中的中的所有表達式有完全相同的符號，那么從所有表達式有完全相同的符號，那么從W W的每個表達式中提取從占據(jù)的每個表達式中提取從占據(jù)那個位置的符號開始的子表達式，各個子表達式集合構(gòu)成那個位置的符號開始的子表

15、達式，各個子表達式集合構(gòu)成W W的分歧集。的分歧集。 例如，兩個列表例如，兩個列表(P x (f A y)P x (f A y)，( (P x (f z B)P x (f z B)集合的分集合的分歧集是歧集是 A A，zz。分歧集能用置換分歧集能用置換A Az z產(chǎn)生協(xié)調(diào)。產(chǎn)生協(xié)調(diào)。 合一合一 UNIFY()( UNIFY()( 是一個列表表達式集合是一個列表表達式集合) ) 1) 1)k0k0， k k，k k(初始化步驟；初始化步驟； 是空的置換是空的置換) )。 2) 2)如果如果k k是一個單元素集合，用是一個單元素集合，用的的mgu mgu k k退出；否則繼續(xù)。退出；否則繼續(xù)。 3

16、) 3)D Dk kk k的分歧集。的分歧集。 4) 4)如果在如果在 D Dk k中存在元素中存在元素 v vk k和和t tk k，v vk k 是一個不會出現(xiàn)在是一個不會出現(xiàn)在t tk k 中的變中的變量，則繼續(xù)；否則，失敗退出，量，則繼續(xù)；否則，失敗退出，是不可以合一的。是不可以合一的。 5) 5) k+1k+1k kttk k/v/vk k ，k+1k+1ttk kv vk k ( (注意注意k+1k+1=k kk+1k+1) )。 6)kk+1 6)kk+1 7) 7)轉(zhuǎn)到第轉(zhuǎn)到第2 2步。步。 合一合一 例：例： 設(shè)設(shè) F= P(a，x，f(g(y)，P(z，f(z)，f(u)，

17、求其合一。求其合一。 1）令令0 0= = ,F,F0 0=F,=F,因因F F0 0中含有兩個表達式，所以中含有兩個表達式，所以0 0不是最不是最一般合一。一般合一。 2 2）分歧集）分歧集D D0 0= = a a，z.z. 3) 3) 1 1= = 0 0 a/z = a/z = a/za/z F F1 1= = P(aP(a，x x，f(g(y)f(g(y)，P(aP(a，f(a)f(a)，f(u)f(u) 4) D1= 4) D1= x,f(a)x,f(a) 5) 5) 2 2= = 1 1 f(a)/x= f(a)/x= a/z,f(a)/xa/z,f(a)/x F F2 2=F=

18、F1 1 f(a)/x= f(a)/x= P(a,f(a),f(g(y),P(a,f(a),f(u)P(a,f(a),f(g(y),P(a,f(a),f(u) 6) D 6) D2 2= = g(y),ug(y),u 7) 7) 3 3 = = 2 2 g(y)/u= g(y)/u= a/z,f(a)/x,g(y)/ua/z,f(a)/x,g(y)/u合一合一 8) F 8) F3 3=F=F2 2 g(y)/u= g(y)/u= P(a,f(a),f(g(y).P(a,f(a),f(g(y). 因為因為F F3 3只含一個表達式，所以只含一個表達式，所以0 0就是最一般合一，就是最一般合一，

19、即即 a/z,f(a)/x,g(y)/ua/z,f(a)/x,g(y)/u是最一般合一。是最一般合一。謂詞演算歸結(jié)謂詞演算歸結(jié) 假如假如1 1和和2 2是兩個子句是兩個子句( (表示為文字集合表示為文字集合) )。如果如果1 1中有一個原子中有一個原子， 2 2中有一個文字中有一個文字，并使并使和和有一個最一般合一式有一個最一般合一式( (mgu)mgu)，那么這兩那么這兩個子句有一個歸結(jié)式個子句有一個歸結(jié)式，它通過把置換它通過把置換與與1 1和和2 2減去互補其文字的并集而得到。減去互補其文字的并集而得到。 即：即：=（ 1 1 - - ）（ 2 2 - - ） 謂詞演算歸結(jié)謂詞演算歸結(jié) 在

20、兩個子句被歸結(jié)前，為了避免變量混淆，我們對在兩個子句被歸結(jié)前，為了避免變量混淆，我們對每個子句中的變量重命名以使一個子句中的變量不會出每個子句中的變量重命名以使一個子句中的變量不會出現(xiàn)在另一個中。例如：假如我們正在歸結(jié)現(xiàn)在另一個中。例如：假如我們正在歸結(jié)P(x) Q(f(x)P(x) Q(f(x)與與R(g(x) R(g(x) Q(f(A)Q(f(A)，首先重寫第二個子句，比如說首先重寫第二個子句，比如說為為R(g(y) R(g(y) Q(f(A)Q(f(A)，然后執(zhí)行歸結(jié)獲得然后執(zhí)行歸結(jié)獲得P(A) P(A) R(g(y)R(g(y)。變量重命名被稱為變量重命名被稱為對變量進行標準化對變量進

21、行標準化( (standardizing the variables apart)standardizing the variables apart)。 下面是一些例子下面是一些例子: : P(x)P(x)，Q(xQ(x，y)y)和和P(A)P(A)，R(BR(B，z)z)歸結(jié)產(chǎn)生歸結(jié)產(chǎn)生: : Q(AQ(A，y)y)，R(BR(B，z)z)。 P(xP(x，x)x)，Q(x)Q(x)，R(x)R(x)和和P(AP(A，z)z)，Q(B)Q(B)可用兩可用兩種不同的方式歸結(jié)，分別產(chǎn)生種不同的方式歸結(jié)，分別產(chǎn)生Q(A)Q(A)，R(A)R(A)，Q(B)Q(B)和和P(BP(B，B)B)，R(B

22、)R(B)，P(AP(A，z)z)。 謂詞演算歸結(jié)謂詞演算歸結(jié) 有時需要對謂詞演算歸結(jié)有一個稍強的定義。例如，有時需要對謂詞演算歸結(jié)有一個稍強的定義。例如，考慮兩個子句考慮兩個子句P(u)P(u)，P(v)P(v)和和P(x)P(x)，P(y)P(y)。這兩個子這兩個子句各自有基例句各自有基例P(A)P(A)和和P(A)(P(A)(由置換由置換A Au u， A Av v， A Ax x， A Ay y獲得獲得) )。從這些基例中，能推斷出空子句，因此我們。從這些基例中，能推斷出空子句，因此我們應該能從初始子句推斷它，但是剛剛給定的歸結(jié)規(guī)則不能應該能從初始子句推斷它，但是剛剛給定的歸結(jié)規(guī)則不能

23、做到這些。做到這些。更強的規(guī)則更強的規(guī)則如下如下: : 假定假定1 1和和2 2是兩個子句是兩個子句( (再次表示為文字集合再次表示為文字集合) )。如。如果有果有1 1的一個子集的一個子集1 1和和2 2的一個子集的一個子集2 2，使得使得1 1的文字能與的文字能與2 2的文字的否定式用最一般合一式的文字的否定式用最一般合一式合一，合一，那么這兩個子句有一個歸結(jié)式那么這兩個子句有一個歸結(jié)式，它通過把置換它通過把置換與與1 1和和2 2減去其互補子集的并集而得到。即：減去其互補子集的并集而得到。即：=(=(1 1- -1 1)( )( 2 2- -2 2) ) 用這個歸結(jié)定義，歸結(jié)子句用這個歸

24、結(jié)定義，歸結(jié)子句P(u),P(v)P(u),P(v)和和P P（x x），），P(y)P(y)產(chǎn)生空子句。產(chǎn)生空子句。 完備性和合理性完備性和合理性 謂詞演算的歸結(jié)是合理的。也就是說，如果謂詞演算的歸結(jié)是合理的。也就是說，如果是兩個子句是兩個子句和和歸結(jié)式，那么歸結(jié)式，那么， 。這個事實的證明不比命題歸結(jié)的合理性證明難這個事實的證明不比命題歸結(jié)的合理性證明難。 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 就像在命題演算中一樣，任何合式公式能被轉(zhuǎn)化就像在命題演算中一樣，任何合式公式能被轉(zhuǎn)化為子句形式。步驟如下：為子句形式。步驟如下： 1)1)消除蘊含符號消除蘊含符號( (如在命

25、題演算中一樣如在命題演算中一樣) )。 2)2)減少否定符號的范圍減少否定符號的范圍( (如在命題演算中一樣如在命題演算中一樣) )。 3)3)變量標準化變量標準化，由于量詞范圍內(nèi)的變量像，由于量詞范圍內(nèi)的變量像“啞啞元元”，因此它們能被更名，以使每個量詞有它自己，因此它們能被更名，以使每個量詞有它自己的變量符號。的變量符號。 舉例：舉例：可以改寫為可以改寫為: : x x) )Q Q( (x x) ) ( (P P( (x x) )x x) ) ( ( y y) )Q Q( (y y) ) ( (P P( (x x) )x x) ) ( ( 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化

26、為子句形式 4) 4)取消存在量詞取消存在量詞。 舉例：在舉例：在 中，存在量詞中，存在量詞( ( y)y)在一個全稱量詞在一個全稱量詞( ( x)x)范圍內(nèi)，因此，范圍內(nèi)，因此，y y的的“存在存在”可能依可能依賴賴x x的值。例如，如果的意思是的值。例如，如果的意思是“每個人每個人x x有身高有身高y”y”，那那么很明顯身高與人有關(guān)。用么很明顯身高與人有關(guān)。用某個未知的函數(shù)某個未知的函數(shù)h(x)h(x)顯式定顯式定義這個依賴關(guān)系，義這個依賴關(guān)系，h(x)h(x)把把x x的每個值映射為存在的的每個值映射為存在的y y值值。這樣的一個函數(shù)叫做這樣的一個函數(shù)叫做 Skolem Skolem 函

27、數(shù)函數(shù)。如果我們把。如果我們把 Skolem Skolem 函數(shù)用在函數(shù)用在y y存在的位置，就能取消存在量詞，并寫為存在的位置，就能取消存在量詞，并寫為 h h( (x x) ) , ,x x) )H He ei ig gh ht t x x( (y y) ) , ,y y) )H He ei ig gh ht t( (x xx x) ) ( ( (把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 從一個合式公式中消除一個存在量詞的一般規(guī)則是用從一個合式公式中消除一個存在量詞的一般規(guī)則是用一個一個Skolem Skolem 函數(shù)代替函數(shù)代替存在量詞作用范圍內(nèi)變量的每一次存在量詞作

28、用范圍內(nèi)變量的每一次出現(xiàn)出現(xiàn)， Skolem Skolem 函數(shù)的參數(shù)是那些函數(shù)的參數(shù)是那些被全稱量詞約束被全稱量詞約束的變量，的變量，全稱量詞的范圍包括要被消除的存在量詞的范圍。用在全稱量詞的范圍包括要被消除的存在量詞的范圍。用在Skolem Skolem 函數(shù)中的函數(shù)符號必須是函數(shù)中的函數(shù)符號必須是“新的新的”，不能是已經(jīng)，不能是已經(jīng)出現(xiàn)在任何合式公式中被用在歸結(jié)反駁中的符號。出現(xiàn)在任何合式公式中被用在歸結(jié)反駁中的符號。因此，我們能從因此，我們能從 經(jīng)消除經(jīng)消除( ( z z) )，產(chǎn)生產(chǎn)生z z) ) u u, ,y y, ,u u) )R R( (x x, ,( (z z) )y y,

29、 ,z z) ) P P( (x x, ,y y) ) ( (x x) ) ( ( (w w) )Q Q( (w w) ) ( ( y y) ) ) g g( (x x, ,u u, ,y y, ,u u) )R R( (x x, ,( (y y) ) )g g( (x x, ,y y, ,y y) ) P P( (x x, ,x x) ) ( ( (w w) )Q Q( (w w) ) ( ( 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 我們能從我們能從 經(jīng)消除經(jīng)消除( ( w w) )，產(chǎn)生產(chǎn)生 其中其中g(shù)(Xg(X，y)y)和和h(x)h(x)都是都是Skolem Sk

30、olem 函數(shù)。函數(shù)。 如果要被消除的存在量詞不在任何全稱量詞的范圍內(nèi)，如果要被消除的存在量詞不在任何全稱量詞的范圍內(nèi)，那么我們使用一個那么我們使用一個沒有參數(shù)的沒有參數(shù)的Skolem Skolem 函數(shù)函數(shù)，它只是，它只是y y一個一個常量。因此，常量。因此，( ( x) P(x)x) P(x)成為成為P(Sk)P(Sk)，常量符號常量符號 Sk (Sk (用來指用來指向我們知道存在的那個項。另外，向我們知道存在的那個項。另外，Sk Sk 是一個新的符號常量是一個新的符號常量且沒有用在其他函數(shù)中，這是必要的。且沒有用在其他函數(shù)中，這是必要的。 P(w)P(w)w)w)w)Q(x,w)Q(x,

31、( (y)y)P(f(x,P(f(x,P(y)P(y)x)x)(P(x)P(x)x)x)( ( P P( (h h( (x x) ) ) h h( (x x) ) ) Q Q( (x x, ,y y) ) ) P P( (f f( (x x, ,P P( (y y) )y y P P( (x x) )x x) ) ( ( 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 為了從一個合式公式中消除所有的存在量化變量，依為了從一個合式公式中消除所有的存在量化變量，依次對每個子公式使用前述的過程。從一組合式公式中消除次對每個子公式使用前述的過程。從一組合式公式中消除存在量詞產(chǎn)生公式集合的

32、存在量詞產(chǎn)生公式集合的Skolem Skolem 范式。范式。 注意，一個合式公式的注意，一個合式公式的Skolem Skolem 范式并不等價于原始范式并不等價于原始的合式公式！公式的合式公式！公式( ( x) P(x)x) P(x)被它的被它的Skolem Skolem 范式范式P(Sk)P(Sk)邏邏輯涵蘊，但反過來就不行。輯涵蘊，但反過來就不行。 作為另一個例子，注意作為另一個例子，注意 P(A)P(B) P(A)P(B) ( ( x)P(x) x)P(x)，但是但是 P(A) P(B) P(A) P(B) P(Sk)P(Sk)。公式集合公式集合是可以滿足的，是可以滿足的，當且僅當當且

33、僅當?shù)牡腟kolem Skolem 范式是可以滿足的?；蛘撸瑢w結(jié)范式是可以滿足的。或者，對歸結(jié)反駁更有用的是，反駁更有用的是， 是不可滿足的，當且僅當是不可滿足的，當且僅當?shù)牡腟kolem Skolem 范式是不可滿足。范式是不可滿足。 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 5)5)轉(zhuǎn)化為前束范式轉(zhuǎn)化為前束范式。在這個階段，沒有任何殘留的。在這個階段，沒有任何殘留的存在量詞，每個全稱量詞有它自己的變量符號?，F(xiàn)在，存在量詞，每個全稱量詞有它自己的變量符號?，F(xiàn)在，我們可以把所有的全稱量詞移到合式公式的前面，并且我們可以把所有的全稱量詞移到合式公式的前面，并且讓每個量詞的范

34、圍包括跟隨它的合式公式的全部。這樣讓每個量詞的范圍包括跟隨它的合式公式的全部。這樣的合式公式被稱為是在前束范式中。前束范式的一個合的合式公式被稱為是在前束范式中。前束范式的一個合式公式包括一個稱為前束范式的量詞，它后面跟隨一個式公式包括一個稱為前束范式的量詞，它后面跟隨一個稱為稱為矩陣矩陣( (matrix)matrix)的沒有量詞的公式。的沒有量詞的公式。 合式公式：合式公式：的前束范式是：的前束范式是： P P( (h h( (x x) ) ) h h( (x x) ) ) Q Q( (x x, ,y y) ) ) P P( (f f( (x x, ,P P( (y y) ) P P( (

35、x x) )y y) ) x x) )( ( (P P( (h h( (x x) ) ) h h( (x x) ) ) Q Q( (x x, ,y y) ) ) P P( (f f( (x x, ,P P( (y y) )y y P P( (x x) )x x) ) ( ( 6 6) )將矩陣寫成一個合取范式將矩陣寫成一個合取范式。像命題演算一樣，我。像命題演算一樣，我們可以通過重復使用分配律，用們可以通過重復使用分配律，用 代替，代替， 把任何矩陣改寫成合取范式。把任何矩陣改寫成合取范式。 將前述合式公式例子的矩陣改寫成合取范式，它變將前述合式公式例子的矩陣改寫成合取范式，它變?yōu)闉?y y)

36、 ) ) P P( (f f( (x x, ,P P( (y y) )P P( (x x) )y y) ) x x) )( ( () )( () )( (3 31 12 21 1 ) )( (3 32 21 1 7)7)消除全稱量詞消除全稱量詞。由于用在合式公式中的所有變量。由于用在合式公式中的所有變量必須是在一個量詞范圍內(nèi)，保證在這一步保留的所有變必須是在一個量詞范圍內(nèi)，保證在這一步保留的所有變量都被全稱量化。而且，全稱量化的順序并不重要，因量都被全稱量化。而且，全稱量化的順序并不重要，因此可以刪去明確出現(xiàn)的全稱量詞，并且根據(jù)約定可以保此可以刪去明確出現(xiàn)的全稱量詞，并且根據(jù)約定可以保證矩陣中

37、的所有變量都被全稱量化。現(xiàn)在，只留下了一證矩陣中的所有變量都被全稱量化。現(xiàn)在，只留下了一個合取范式的矩陣。個合取范式的矩陣。 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 P P( (h h( (x x) ) ) P P( (x x) ) h h( (x x) ) ) Q Q( (x x, ,P P( (x x) ) 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 8)8)消除消除符號符號。可以用合式公式集合?？梢杂煤鲜焦郊? 1， 2 2 代代替表達式替表達式( (1 12 2) )，刪除顯式出現(xiàn)的刪除顯式出現(xiàn)的符號。重復代符號。重復代替的結(jié)果是獲得一個有限

38、的合式公式集合，合式公式替的結(jié)果是獲得一個有限的合式公式集合，合式公式中的每一項是一個文字析取項。只包含文字析取項的中的每一項是一個文字析取項。只包含文字析取項的任何合式公式被稱為一個子句，我們的合式公式例子任何合式公式被稱為一個子句，我們的合式公式例子被轉(zhuǎn)化為下面的子句集合：被轉(zhuǎn)化為下面的子句集合： P(x)P(x)P(y)Pf(x,y)P(y)Pf(x,y) P(x)Qx,h(x)P(x)Qx,h(x) P(x)P(x)Ph(x) Ph(x) 把任意的合式公式轉(zhuǎn)化為子句形式把任意的合式公式轉(zhuǎn)化為子句形式 9)9)變量更名變量更名。變量符號可以被更名，以使沒有任何。變量符號可以被更名，以使沒

39、有任何變 量 符 號 出 現(xiàn) 在 多 于 一 個 的 子 句 中 。 注 意 到變 量 符 號 出 現(xiàn) 在 多 于 一 個 的 子 句 中 。 注 意 到 ( ( x)P(x)Q(x)x)P(x)Q(x)等價于等價于( x)P(x) (x)P(x) ( y)Q(y)y)Q(y)。現(xiàn)在子句是：現(xiàn)在子句是： P(x1)P(x1)P(y) Pf(xlP(y) Pf(xl，y)y) P(x2)Qx2P(x2)Qx2，h(x2)h(x2) P(x3)Ph(x3)P(x3)Ph(x3) 一個子句的文字可以包含變量，但這些變量總是被一個子句的文字可以包含變量，但這些變量總是被理解為是全稱量化的。理解為是全稱

40、量化的。 用歸結(jié)證明定理用歸結(jié)證明定理 當歸結(jié)用作一個定理證明系統(tǒng)的推論規(guī)則時，可以當歸結(jié)用作一個定理證明系統(tǒng)的推論規(guī)則時，可以將要從中證明一個定理的合式公式集合首先轉(zhuǎn)化成子句。將要從中證明一個定理的合式公式集合首先轉(zhuǎn)化成子句?？梢宰C明如果合式公式可以證明如果合式公式從一個合式公式集合從一個合式公式集合中邏輯中邏輯地產(chǎn)生，那么同樣也從地產(chǎn)生，那么同樣也從中的合式公式轉(zhuǎn)換成的子句集中的合式公式轉(zhuǎn)換成的子句集合中邏輯地產(chǎn)生。反之亦然合中邏輯地產(chǎn)生。反之亦然。因此，子句是一個表達謂因此，子句是一個表達謂詞演算合式公式的完備的通用形式。詞演算合式公式的完備的通用形式。 假如機器人知道假如機器人知道27

41、27號房間中的所有箱子都比號房間中的所有箱子都比2828號房間中號房間中的小。即：的小。即： 1)( 1)( x x，y)y)Package(x)Package(y)Inroom(xPackage(x)Package(y)Inroom(x，27)Inroom(y27)Inroom(y，28) 28) Smaller(x Smaller(x，y )y ) 縮寫謂詞符號使公式緊湊。轉(zhuǎn)換為子句形式，產(chǎn)生：縮寫謂詞符號使公式緊湊。轉(zhuǎn)換為子句形式，產(chǎn)生： 2) 2)P(x) P(x) P(y) P(y)I(xI(x，27)27)I(yI(y，28)S(x28)S(x，y)y) 假定機器人知道箱子假定機器

42、人知道箱子A A在在2727號或號或2828號房間中號房間中( (但不知道是但不知道是哪一個哪一個) )。它知道箱子。它知道箱子B B在房間在房間2727中且中且B B不比不比A A小。小。 3) 3) P (A) P (A) 4) 4) P( B)P( B) 5) I( A 5) I( A，27) I(A27) I(A，28)28) 6) I( B 6) I( B，27)27) 7) 7) S( B S( B，A)A)用歸結(jié)反駁，機器人能證明箱子用歸結(jié)反駁，機器人能證明箱子A A在在2727號房間中。號房間中。 用歸結(jié)證明定理用歸結(jié)證明定理 用歸結(jié)證明定理用歸結(jié)證明定理 下圖是一棵證明樹。待

43、證明的合式公式的否定被標在左上下圖是一棵證明樹。待證明的合式公式的否定被標在左上角；和機器人明確知道的相對應的合式公式被標在圖中沿角；和機器人明確知道的相對應的合式公式被標在圖中沿右手方向。歸結(jié)期間的置換在圖中也已表示出來。右手方向。歸結(jié)期間的置換在圖中也已表示出來。 回答提取回答提取 為了用歸結(jié)回答由謂詞演算合式公式表示一個領(lǐng)域為了用歸結(jié)回答由謂詞演算合式公式表示一個領(lǐng)域知識的問題，通常要做的不只是證明一個定理。知識的問題，通常要做的不只是證明一個定理。 例如，假定必須證明形如例如，假定必須證明形如( ( ) () ()的一個定的一個定理。我們可能也想得到已經(jīng)證明存在的理。我們可能也想得到已

44、經(jīng)證明存在的。為了做到這為了做到這些，必須跟蹤在反駁過程中所做的置換，可以用一個回些，必須跟蹤在反駁過程中所做的置換，可以用一個回答文字策略跟蹤那個置換。將文字答文字策略跟蹤那個置換。將文字Ans (Ans (1 1，2 2，)加到要證明的定理的否定子句，執(zhí)行歸結(jié)直到只剩下一加到要證明的定理的否定子句，執(zhí)行歸結(jié)直到只剩下一個回答文字。在個回答文字。在Ans Ans 文字中的變量是出現(xiàn)在待證明定理文字中的變量是出現(xiàn)在待證明定理的否定子句形式中的所有變量。的否定子句形式中的所有變量。 在證明期間代替在證明期間代替Ans Ans 文字中變量的項，將成為被證文字中變量的項，將成為被證明合式公式中存在量

45、化變量的實例。明合式公式中存在量化變量的實例。 回答提取回答提取 在下圖中，給出了如何使用在下圖中，給出了如何使用Ans Ans 文字的一個例子，現(xiàn)在要文字的一個例子，現(xiàn)在要證明合式公式證明合式公式( u)I(A， u)，它可以看作是機器人問它自它可以看作是機器人問它自己：己：“A A究竟在哪個房間究竟在哪個房間?”?”。 等式謂詞等式謂詞 用在一個知識庫公式中的關(guān)系常量常常有用在一個知識庫公式中的關(guān)系常量常常有意向含意意向含意( (即關(guān)系即關(guān)系) )，但是這些關(guān)系僅僅被知識庫的模型集合所約束，但是這些關(guān)系僅僅被知識庫的模型集合所約束，根本不會被用在關(guān)系常量中的特殊符號所約束。歸結(jié)反駁根本不會被用在