謂詞邏輯基礎(chǔ)(精)教學(xué)提綱

1、謂詞邏輯基礎(chǔ)(精)3.2 謂詞邏輯基礎(chǔ)謂詞邏輯基礎(chǔ)l例如：（例如：（1）所有的人都是要死的。）所有的人都是要死的。l （2） 有的人活到一百歲以上。有的人活到一百歲以上。在個體域在個體域D為人類集合時，可符號化為：為人類集合時，可符號化為：（1） xPxP( (x x) )，其中，其中P P( (x x) )表示表示x x是要死的。是要死的。（2） x Qx Q( (x x), ), 其中其中Q Q( (x x) )表示表示x x活到一百歲以上。活到一百歲以上。在個體域在個體域D是全總個體域時，是全總個體域時，引入特殊謂詞引入特殊謂詞R R( (x x) )表示表示x x是人，可符號化為：是人

2、，可符號化為：（1 1） x x（R R( (x x) ) P P( (x x) )）, , 其中，其中，R R( (x x) )表示表示x x是人；是人；P P( (x x) )表示表示x x是要死的。是要死的。（2 2） x x（R R( (x x) ) Q Q( (x x) )），），其中，其中，R R( (x x) )表示表示x x是人；是人；Q Q( (x x) )表示表示x x活到一百歲以上?；畹揭话贇q以上。 一階邏輯一階邏輯l公式及其解釋公式及其解釋l個體常量：個體常量：a,b,cl個體變量：個體變量：x,y,zl謂詞符號：謂詞符號：P,Q,Rl量詞符號：量詞符號： , , 3.

3、2 謂詞邏輯基礎(chǔ)謂詞邏輯基礎(chǔ)量詞否定等值式：量詞否定等值式：l( ( x x ） P P（x x） （ y y ） P P（y y） l( ( x x ） P P（x x） （ y y ） P P（y y）量詞分配等值式：量詞分配等值式：l( ( x x ）( ( P P（x x） Q Q（x x）) () ( x x ） P P（x x） ( ( x x ） Q Q（x x）l( ( x x ）( ( P P（x x） Q Q（x x）) () ( x x ） P P（x x） ( ( x x ） Q Q（x x）消去量詞等值式：消去量詞等值式：設(shè)個體域為有窮集合（設(shè)個體域為有窮集合（a a

4、1 1, a, a2 2, a, an n）l( ( x x ） P P（x x） P P（ a a1 1 ） P P（ a a2 2 ） P P（ a an n ）l( ( x x ）P P（x x） P P（ a a1 1 ） P P（ a a2 2 ） P P（ a an n ）3.2 謂詞邏輯基礎(chǔ)謂詞邏輯基礎(chǔ)量詞轄域收縮與擴張等值式：量詞轄域收縮與擴張等值式：l( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Ql( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q l( ( x x ）(

5、( P P（x x） Q Q) () ( x x ） P P（x x） Q Q l( ( x x ）( (Q Q P P（x x） ) ) Q Q ( ( x x ） P P（x x） l( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Ql( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q l( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q l( ( x x ）( (Q Q P P（x x） ) ) Q Q ( ( x x ） P P（x x）

6、3.2 謂詞邏輯基礎(chǔ)謂詞邏輯基礎(chǔ)3.2 謂詞邏輯基礎(chǔ)謂詞邏輯基礎(chǔ)SKOLEMSKOLEM標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形l前束范式前束范式定義定義：說公式：說公式A A是一個前束范式，如果是一個前束范式，如果A A中中的一切量詞都位于該公式的最左邊（不含否的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的定詞），且這些量詞的轄域都延伸到公式的末端。末端。 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理即：即： 把所有的量詞都提到前面去，然后消把所有的量詞都提到前面去，然后消掉所有量詞掉所有量詞(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)(Q)(Qn nx xn n)M(x)M(x

7、1 1,x ,x2 2,x,xn n) )約束變項換名規(guī)則：約束變項換名規(guī)則：l(Qx(Qx ） MM（x x） （QyQy ） MM（y y） l(Qx(Qx ） MM（x,zx,z） （QyQy ） MM（y,zy,z）3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l l l l l l l l l l l l l l l l l l l l l l l l l ll量詞消去原則：量詞消去原則：消去存在量詞消去存在量詞“ ”，略去全程量詞，略去全程量詞“ ”。注意：注意：左邊有全程量詞的存在量詞，消去左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒時該變量改寫成為全程量詞的函數(shù)

8、；如沒有，改寫成為常量。有，改寫成為常量。 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l l l l l l l l l l l l l l l l l l l l l l l l l llSkolemSkolem定理定理：謂詞邏輯的任意公式都可以化為與之等價謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。的前束范式，但其前束范式不唯一。 lSKOLEMSKOLEM標(biāo)準(zhǔn)形定義：標(biāo)準(zhǔn)形定義：消去量詞后的謂詞公式。消去量詞后的謂詞公式。注意注意：謂詞公式：謂詞公式G G的的SKOLEMSKOLEM標(biāo)準(zhǔn)形同標(biāo)準(zhǔn)形同G G并并不等值不等值。 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理例

9、：例：將下式化為將下式化為Skolem標(biāo)準(zhǔn)形：標(biāo)準(zhǔn)形： ( x)( y)P(a, x, y) ( x)( y)Q(y, b)R(x)l解：第一步，消去解：第一步，消去號，得：號，得： ( x)( y)P(a, x, y) ( x) ( y)Q(y, b)R(x)l第二步，深入到量詞內(nèi)部，得：第二步，深入到量詞內(nèi)部，得： ( x)( y)P(a, x, y) ( x)x) ( y)Q(y, b)R(x)l第三步，變元易名，得第三步，變元易名，得( x)( y)P(a, x, y) ( u) ( v)(Q(v, b) R(u)l第四步，存在量詞左移，直至所有的量詞移到前面，第四步，存在量詞左移，直

10、至所有的量詞移到前面，( x) ( y) ( u) ( v) (P(a, x, y) (Q(v, b) R(u)由此得到前述范式由此得到前述范式l第五步，消去第五步，消去“ ”（存在量詞），略去（存在量詞），略去“ ”全稱量詞全稱量詞l消去消去( y)，因為它左邊只有，因為它左邊只有( x)，所以使用，所以使用x的函數(shù)的函數(shù)f(x)代替之，這樣得到：代替之，這樣得到：( x)( u)( v) (P(a, x, f(x) Q(v, b)R(u)l消去消去( u)，同理使用，同理使用g(x)代替之，這樣得到：代替之，這樣得到：( x) ( v) ( P(a, x, f(x) Q(v, b) R(g

11、(x)l則，略去全稱變量，原式的則，略去全稱變量，原式的Skolem標(biāo)準(zhǔn)形為：標(biāo)準(zhǔn)形為： P(a, x, f(x) Q(v, b) R(g(x) l子句與子句集子句與子句集l文字：不含任何連接詞的謂詞公式。文字：不含任何連接詞的謂詞公式。l子句：一些文字的析?。ㄖ^詞的和）。子句：一些文字的析?。ㄖ^詞的和）。l子句集子句集S S的求?。旱那笕。?G G SKOLEM SKOLEM標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形 消去存在變量消去存在變量 以以“，”取代取代“”，并表示為集合形式，并表示為集合形式 。3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l G是不可滿足的是不可滿足的 S是不可滿足的是不可滿足的lG與與S不等價，但

12、在不可滿足得意義下是一致的。不等價，但在不可滿足得意義下是一致的。 l定理：定理：若若G是給定的公式，而是給定的公式，而S是相應(yīng)的子句集，則是相應(yīng)的子句集，則G是是不可滿足的不可滿足的 S是不可滿足的。是不可滿足的。 注意注意：G真不一定真不一定S真，而真，而S真必有真必有G真。真。即：即： S = = G3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理lG = GG = G1 1 G G2 2 G G3 3 G Gn n 的子句形的子句形lG G的字句集可以分解成幾個單獨處理。的字句集可以分解成幾個單獨處理。 l有有 S SG G = S = S1 1 U SU S2 2 U S U S3 3 U

13、U S U U Sn n則則S SG G 與與 S S1 1 U SU S2 2 U S U S3 3 U U S U U Sn n在不可滿足得意義在不可滿足得意義上是一致的。上是一致的。即即S SG G 不可滿足不可滿足 S S1 1 U SU S2 2 U S U S3 3 U U S U U Sn n不可滿足不可滿足3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理例：對所有的例：對所有的x,y,z來說，如果來說，如果y是是x的父親，的父親，z又是又是y的的父親，則父親，則z是是x的祖父。又知每個人都有父親，試問對的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？某個人來說誰是它的祖父？求

14、：用一階邏輯表示這個問題，并建立子句集。求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞：解：這里我們首先引入謂詞：lP(x, y) 表示表示x是是y的父親的父親lQ(x, y) 表示表示x是是y的祖父的祖父lANS(x) 表示問題的解答表示問題的解答3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理對于第一個條件，對于第一個條件，“如果如果x是是y 的父親，的父親， y又是又是z 的父親，則的父親，則x是是z 的祖父的祖父”，一階邏輯表達(dá)式如下：，一階邏輯表達(dá)式如下：A1：( x)( y)( z)(P(x, y)P(y, z)Q(x, z)S A1：P(x ,y)P(y, z)Q(x

15、, z)對于第二個條件：對于第二個條件：“每個人都有父親每個人都有父親”，一階邏輯表達(dá)式：，一階邏輯表達(dá)式：A2：( y)( x)P(x, y)S A2：P(f(y), y)對于結(jié)論：某個人是它的祖父對于結(jié)論：某個人是它的祖父B：( x)( y)Q(x, y)否定后得到子句：否定后得到子句： （ ( x)( y)Q(x, y)） ANS(x)SB：Q(x, y)ANS(x)則得到的相應(yīng)的子句集為：則得到的相應(yīng)的子句集為： S A1，S A2，SB 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l歸結(jié)原理正確性的根本在于，找到矛盾歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真?？梢钥隙ú徽?。l方法：方

16、法：l和命題邏輯一樣。和命題邏輯一樣。l但由于有函數(shù)，所以要考慮但由于有函數(shù)，所以要考慮合一合一和和置換置換。 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。量。l定義：定義：置換是形如置換是形如t1/x1, t2/x2, , tn/xn的有限集合。其中，的有限集合。其中，x1, x2, , xn是互不相同的變量，是互不相同的變量，t1, t2, , tn是不同于是不同于xi的項（常量、變量、函的項（常量、變量、函數(shù)）；數(shù)）；ti/xi表示用表示用ti置換置換xi，并且要求，并且要求

17、ti與與xi不能相同，而且不能相同，而且xi不能不能循環(huán)地出現(xiàn)在另一個循環(huán)地出現(xiàn)在另一個ti中。中。例如例如a/x，c/y，f(b)/z是一個置換。是一個置換。g(y)/x，f(x)/y不是一個置換，不是一個置換， 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理置換置換置換的合成置換的合成l設(shè)設(shè) t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn，是兩個置換。，是兩個置換。 則則 與與 的合成也是一個置換，記作的合成也是一個置換，記作 。它是從集合。它是從集合t1 /x1, t2 /x2, , tn /xn, u1/y1, u2/y2, , un/yn 中刪去以

18、下兩種元素：中刪去以下兩種元素：li. 當(dāng)當(dāng)ti =xi時，刪去時，刪去ti /xi (i = 1, 2, , n);lIi. 當(dāng)當(dāng)yi x1,x2, , xn時，刪去時，刪去uj/yj (j = 1, 2, , m)最后剩下的元素所構(gòu)成的集合。最后剩下的元素所構(gòu)成的集合。 合成即是對合成即是對ti先做先做 置換然后再做置換然后再做 置換，置換置換，置換xi3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l例：例：設(shè)：設(shè)： f(y)/x, z/y， a/x, b/y, y/z，求，求 與與 的合成。的合成。解：先求出集合解：先求出集合f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(

19、b)/x, y/y, a/x, b/y, y/z其中，其中，f(b)/x中的中的f(b)是置換是置換 作用于作用于f(y)的結(jié)果；的結(jié)果；y/y中的中的y是置換是置換 作用于作用于z的結(jié)果。在該集合中，的結(jié)果。在該集合中，y/y滿足定義中的條滿足定義中的條件件i，需要刪除；，需要刪除；a/x，b/y滿足定義中的條件滿足定義中的條件ii，也需要刪除。，也需要刪除。最后得最后得 f(b)/x，y/z3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理合一合一l合一可以簡單地理解為合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞尋找相對變量的置換，使兩個謂詞公式一致公式一致”。l定義：設(shè)有公式集定義：設(shè)有公

20、式集FF1，F(xiàn)2，F(xiàn)n，若存在一個置換，若存在一個置換 ，可使可使F1 F2 = Fn ，則稱，則稱 是是F的一個合一。同時稱的一個合一。同時稱F1，F(xiàn)2，. ，F(xiàn)n是可合一的。是可合一的。l 例：例：設(shè)有公式集設(shè)有公式集FP(x, y, f(y), P(a,g(x),z)，則，則 a/x, g(a)/y, f(g(a)/z是它的一個合一。是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。注意：一般說來，一個公式集的合一不是唯一的。 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理3.3 謂詞邏輯歸結(jié)原理謂詞邏輯

21、歸結(jié)原理歸結(jié)原理歸結(jié)原理l歸結(jié)的注意事項：歸結(jié)的注意事項：n謂詞的一致性謂詞的一致性，P()P()與與Q()Q()， 不可以不可以n常量的一致性，常量的一致性，P(a, )P(a, )與與P(b,.)P(b,.)， 不可以不可以 變量，變量，P(a, .)P(a, .)與與P(x, )P(x, )， 可以可以n變量與函數(shù)，變量與函數(shù)，P(a, x, .)P(a, x, .)與與P(x, f(x), )P(x, f(x), )，不，不可以；可以；n是不能同時消去兩個互補對，是不能同時消去兩個互補對，PQPQ與與PPQ Q的空，的空，不可以不可以1. 1.先進行內(nèi)部簡化（置換、合并）先進行內(nèi)部簡化

22、（置換、合并） 3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l歸結(jié)的過程歸結(jié)的過程寫出謂詞關(guān)系公式寫出謂詞關(guān)系公式 用反演法寫出謂詞表達(dá)式用反演法寫出謂詞表達(dá)式 SKOLEMSKOLEM標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形 子句集子句集S S 對對S S中可歸結(jié)的子句做歸結(jié)中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入歸結(jié)式仍放入S S中，反復(fù)歸結(jié)過程中，反復(fù)歸結(jié)過程 得到空子句得到空子句 得證得證3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理例題例題“快樂學(xué)生快樂學(xué)生”問題問題l假設(shè)任何通過計算機考試并獲獎的人都是快樂的，任假設(shè)任何通過計算機考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運的人都可以通過所有的考試，張不肯何肯學(xué)習(xí)或幸運的人都可

23、以通過所有的考試，張不肯學(xué)習(xí)但他是幸運的，任何幸運的人都能獲獎。求證：學(xué)習(xí)但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。張是快樂的。l 解：先將問題用謂詞表示如下：解：先將問題用謂詞表示如下：lR1:“任何通過計算機考試并獲獎的人都是快樂的任何通過計算機考試并獲獎的人都是快樂的”( x)(Pass(x, computer)Win(x, prize)Happy(x)lR2:“任何肯學(xué)習(xí)或幸運的人都可以通過所有考試任何肯學(xué)習(xí)或幸運的人都可以通過所有考試”( x)( y)(Study(x)Lucky(x)Pass(x, y)lR3:“張不肯學(xué)習(xí)但他是幸運的張不肯學(xué)習(xí)但他是幸運的”Study(

24、zhang)Lucky(zhang)lR4:“任何幸運的人都能獲獎任何幸運的人都能獲獎”( x)(Luck(x)Win(x,prize)l結(jié)論：結(jié)論：“張是快樂的張是快樂的”的否定的否定Happy(zhang)例題例題“快樂學(xué)生快樂學(xué)生”問題問題l由由R1及邏輯轉(zhuǎn)換公式及邏輯轉(zhuǎn)換公式:PWH = （PW） H ，可得，可得l (1)Pass(x, computer)Win(x, prize)Happy(x)l由由R2： (2)Study(y)Pass(y,z)l (3)Lucky(u)Pass(u,v)l由由R3： (4)Study(zhang)l (5)Lucky(zhang)l由由R4：

25、(6)Lucky(w)Win(w，prize)l由結(jié)論：由結(jié)論：(7)Happy(zhang)（結(jié)論的否定）（結(jié)論的否定）l(8)Pass(w, computer)Happy(w)Luck(w) (1)(6)，w/xl(9)Pass(zhang, computer)Lucky(zhang) (8)(7)，zhang/wl(10) Pass(zhang, computer) (9)(5)l(11) Lucky(zhang) (10)(3)，zhang/u, computer/vl(12) (11)(5) l歸結(jié)法的實質(zhì)：歸結(jié)法的實質(zhì)：l歸結(jié)法是僅有一條推理規(guī)則的推理方法。歸結(jié)法是僅有一條推理規(guī)則

26、的推理方法。 l歸結(jié)的過程是一個語義樹倒塌的過程。歸結(jié)的過程是一個語義樹倒塌的過程。 l歸結(jié)法的問題歸結(jié)法的問題l子句中有等號或不等號時，完備性不成立。子句中有等號或不等號時，完備性不成立。 Herbrand Herbrand定理的不實用性引出了可實用的定理的不實用性引出了可實用的歸結(jié)法。歸結(jié)法。3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理歸結(jié)過程的控制策略歸結(jié)過程的控制策略l要解決的問題：要解決的問題：l歸結(jié)方法的知識爆炸。歸結(jié)方法的知識爆炸。l控制策略的目的控制策略的目的l歸結(jié)點盡量少歸結(jié)點盡量少l控制策略的原則控制策略的原則l給出控制策略，以使僅對選擇合適的子句給出控制策略，以使僅對選擇合適

27、的子句間方可做歸結(jié)。避免多余的、不必要的歸間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f，少做些歸結(jié)仍能導(dǎo)出結(jié)式出現(xiàn)。或者說，少做些歸結(jié)仍能導(dǎo)出空子句?？兆泳?。3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理刪除策略刪除策略=完備完備l名詞解釋：歸類：設(shè)有兩個子句名詞解釋：歸類：設(shè)有兩個子句C C和和D D，若有置換，若有置換 使得使得C C D D成立，則稱子句成立，則稱子句C C把子句把子句D D歸類。歸類。由于小的可以代表大的，所以小的吃掉大的了。由于小的可以代表大的，所以小的吃掉大的了。l若對若對S S使用歸結(jié)推理過程中，當(dāng)歸結(jié)式使用歸結(jié)推理過程中，當(dāng)歸結(jié)式C Cj j是重言式是重言式（

28、永真式）和（永真式）和C Cj j被被S S中子句和子句集的歸結(jié)式中子句和子句集的歸結(jié)式C Ci i(ij)(ij)所歸類時，便將所歸類時，便將C Cj j刪除。這樣的推理過程便稱做使刪除。這樣的推理過程便稱做使用了刪除策略的歸結(jié)過程。用了刪除策略的歸結(jié)過程。3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理l主要思想：歸結(jié)過程在尋找可歸結(jié)子句時，子主要思想：歸結(jié)過程在尋找可歸結(jié)子句時，子句集中的子句越多，需要付出的代價就會越大。句集中的子句越多，需要付出的代價就會越大。如果在歸結(jié)時能把子句集中無用的子句刪除掉，如果在歸結(jié)時能把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數(shù)，從而提高就會縮小搜

29、索范圍，減少比較次數(shù)，從而提高歸結(jié)效率。刪除策略對阻止不必要的歸結(jié)式的歸結(jié)效率。刪除策略對阻止不必要的歸結(jié)式的產(chǎn)生來縮短歸結(jié)過程是有效的。然而要在歸結(jié)產(chǎn)生來縮短歸結(jié)過程是有效的。然而要在歸結(jié)式式C Cj j產(chǎn)生后方能判別它是否可被刪除，這部分產(chǎn)生后方能判別它是否可被刪除，這部分計算量是要花費的，只是節(jié)省了被刪除的子句計算量是要花費的，只是節(jié)省了被刪除的子句又生成的歸結(jié)式。盡管使用刪除策略的歸結(jié)，又生成的歸結(jié)式。盡管使用刪除策略的歸結(jié)，少做了歸結(jié)但不影響產(chǎn)生空子句，就是說刪除少做了歸結(jié)但不影響產(chǎn)生空子句，就是說刪除策略的歸結(jié)推理是完備的。策略的歸結(jié)推理是完備的。3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸

30、結(jié)原理采用支撐集采用支撐集 完備完備 支撐集：設(shè)有不可滿足子句集支撐集：設(shè)有不可滿足子句集S S的子集的子集T T，如，如果果S-TS-T是可滿足的，則是可滿足的，則T T是支持集。是支持集。 采用支撐集策略時，從開始到得到采用支撐集策略時，從開始到得到的整個的整個歸結(jié)過程中，只選取不同時屬于歸結(jié)過程中，只選取不同時屬于S-TS-T的子句，的子句，在其間進行歸結(jié)。就是說，至少有一個子在其間進行歸結(jié)。就是說，至少有一個子句來自于支撐集句來自于支撐集T T或由或由T T導(dǎo)出的歸結(jié)式。導(dǎo)出的歸結(jié)式。3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理例如：例如：A A1 1AA2 2AA3 3B B中的中的B

31、B可以作為支撐集使用?？梢宰鳛橹渭褂?。要求每一次參加歸結(jié)的親本子句中，只要應(yīng)該有一個是要求每一次參加歸結(jié)的親本子句中，只要應(yīng)該有一個是有目標(biāo)公式的否定（有目標(biāo)公式的否定（B B）所得到的子句或者它們的后）所得到的子句或者它們的后裔。裔。l支撐集策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞支撐集策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標(biāo)子句的非，即集是目標(biāo)子句的非，即S SB B。3.3 謂詞

32、邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理ST可滿足支撐集示意圖3.3 謂詞邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理 語義歸結(jié)語義歸結(jié) 完備完備 語義歸結(jié)策略是將子句語義歸結(jié)策略是將子句S S按照一定的語義按照一定的語義分成兩部分，約定每部分內(nèi)的子句間不允許分成兩部分，約定每部分內(nèi)的子句間不允許作歸結(jié)。同時還引入了文字次序，約定歸結(jié)作歸結(jié)。同時還引入了文字次序，約定歸結(jié)時其中的一個子句的被歸結(jié)文字只能是該子時其中的一個子句的被歸結(jié)文字只能是該子句中句中“最大最大”的文字。的文字。 語義歸結(jié)策略的歸結(jié)是完備的，同樣，語義歸結(jié)策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用語義歸所有可歸結(jié)的謂詞公式都可以用采用語義歸結(jié)策略達(dá)到加快歸結(jié)速度的目的。問題是如結(jié)策略達(dá)到加快歸結(jié)速度的目的。問題是如何尋找合適的語義分類方法，并根據(jù)其含義何尋找合適的語義分類方法，并根據(jù)其含義將子句集兩個部分中的子句進行排序。將子句集兩個部分中的子句進行排序。 3.3 謂詞邏輯歸結(jié)原