人工智能-謂詞邏輯43

《人工智能-謂詞邏輯43》由會員分享，可在線閱讀，更多相關《人工智能-謂詞邏輯43（44頁珍藏版）》請在裝配圖網上搜索。

1、謂詞邏輯基礎謂詞邏輯基礎一階邏輯一階邏輯l基本概念基本概念l個體詞：表示主語的詞個體詞：表示主語的詞l謂詞：刻畫個體性質或個體之間關系的詞謂詞：刻畫個體性質或個體之間關系的詞l量詞：表示數量的詞量詞：表示數量的詞l小王是個工程師。小王是個工程師。l8是個自然數。是個自然數。l我去買花。我去買花。l小麗和小華是朋友。小麗和小華是朋友。其中，其中，“小王小王”、“工程師工程師”、“我我”、“花花”、“8”、“小麗小麗”、“小華小華”都是個體詞，而都是個體詞，而“是個工程師是個工程師”、“是個自然數是個自然數”、“去買去買”、“是朋友是朋友”都是謂詞。顯然前兩個謂詞表示的是事物都是謂詞。顯然前兩個謂

2、詞表示的是事物的性質，第三個謂詞的性質，第三個謂詞“去買去買”表示的一個動作也表示了主、賓兩表示的一個動作也表示了主、賓兩個個體詞的關系，最后一個謂詞個個體詞的關系，最后一個謂詞“是朋友是朋友”表示兩個個體詞之間表示兩個個體詞之間的關系。的關系。謂詞邏輯基礎謂詞邏輯基礎謂詞邏輯基礎謂詞邏輯基礎l例如：（例如：（1）所有的人都是要死的。）所有的人都是要死的。l （2）有的人活到一百歲以上。有的人活到一百歲以上。在個體域在個體域D為人類集合時，可符號化為：為人類集合時，可符號化為：（1）xPxP(x x)，其中，其中P P(x x)表示表示x x是要死的。是要死的。（2）x Qx Q(x x),)

3、,其中其中Q Q(x x)表示表示x x活到一百歲以上?；畹揭话贇q以上。在個體域在個體域D是全總個體域時，是全總個體域時，引入特殊謂詞引入特殊謂詞R R(x x)表示表示x x是人，可符號化為：是人，可符號化為：（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個體常量：個

4、體常量：a,b,cl個體變量：個體變量：x,y,zl謂詞符號：謂詞符號：P,Q,Rl量詞符號：量詞符號：,謂詞邏輯基礎謂詞邏輯基礎量詞否定等值式：量詞否定等值式：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）消去量詞等值式：消去量詞等值式：設個體域為有窮集合（設個體域為有窮集合

5、（a a1 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 ）謂詞邏輯基礎謂詞邏輯基礎量詞轄域收縮與擴張等值式：量詞轄域收縮與擴張等值式：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

6、）)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）謂詞邏輯基礎謂詞邏輯基礎謂詞邏輯基礎謂詞邏輯基礎SKOLEMSKOLEM標準形標準形l前束范式前束范式定義定義：說公式：說公式A A是一個前束范式，如果是一個前束范式，如果A A中中的一切量詞都位于該公式的最左邊（不含否的一切量詞都位于該公式的

7、最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的定詞），且這些量詞的轄域都延伸到公式的末端。末端。謂詞邏輯歸結原理謂詞邏輯歸結原理即：即：把所有的量詞都提到前面去，然后消把所有的量詞都提到前面去，然后消掉所有量詞掉所有量詞(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)(Q(Qn nx xn n)M(x)M(x1 1,x,x2 2,x,xn n)約束變項換名規則：約束變項換名規則：l(Qx(Qx ）MM（x x）（QyQy ）MM（y y）l(Qx(Qx ）MM（x,zx,z）（QyQy ）MM（y,zy,z）謂詞邏輯歸結原理謂詞邏輯歸結原理l l l l l l l l l l

8、 l l l l l l l l l l l l l l l ll量詞消去原則：量詞消去原則：消去存在量詞消去存在量詞“”，略去全程量詞，略去全程量詞“”。注意：注意：左邊有全程量詞的存在量詞，消去左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數；如沒時該變量改寫成為全程量詞的函數；如沒有，改寫成為常量。有，改寫成為常量。謂詞邏輯歸結原理謂詞邏輯歸結原理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定理定理：謂詞邏輯的任意公式都可以化為與之等價謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范

9、式不唯一。的前束范式，但其前束范式不唯一。lSKOLEMSKOLEM標準形定義：標準形定義：消去量詞后的謂詞公式。消去量詞后的謂詞公式。注意注意：謂詞公式：謂詞公式G G的的SKOLEMSKOLEM標準形同標準形同G G并并不等值不等值。謂詞邏輯歸結原理謂詞邏輯歸結原理例：例：將下式化為將下式化為Skolem標準形：標準形：(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第二步，深入到量詞內部，得：第二步，深入到量詞內部，得：(x)(y)P(a,x,y)(x)x)(y)Q

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

11、(u)，同理使用，同理使用g(x)代替之，這樣得到：代替之，這樣得到：(x)(v)(P(a,x,f(x)Q(v,b)R(g(x)l則，略去全稱變量，原式的則，略去全稱變量，原式的Skolem標準形為：標準形為：P(a,x,f(x)Q(v,b)R(g(x)l子句與子句集子句與子句集l文字：不含任何連接詞的謂詞公式。文字：不含任何連接詞的謂詞公式。l子句：一些文字的析?。ㄖ^詞的和）。子句：一些文字的析?。ㄖ^詞的和）。l子句集子句集S S的求?。旱那笕。篏 G SKOLEM SKOLEM標準形標準形 消去存在變量消去存在變量 以以“，”取代取代“”，并表示為集合形式，并表示為集合形式 。謂詞邏輯歸結

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

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

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

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

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

17、出現在另一個循環地出現在另一個ti中。中。例如例如a/x，c/y，f(b)/z是一個置換。是一個置換。g(y)/x，f(x)/y不是一個置換，不是一個置換，謂詞邏輯歸結原理謂詞邏輯歸結原理置換置換置換的合成置換的合成l設設 t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是兩個置換。，是兩個置換。則則 與與 的合成也是一個置換，記作的合成也是一個置換，記作 。它是從集合。它是從集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn 中刪去以下兩種元素：中刪去以下兩種元素：li.當當ti=xi時，刪去時，刪去ti/xi(i=1,2,n);lIi.當當y

18、i x1,x2,xn時，刪去時，刪去uj/yj(j=1,2,m)最后剩下的元素所構成的集合。最后剩下的元素所構成的集合。合成即是對合成即是對ti先做先做 置換然后再做置換然后再做 置換，置換置換，置換xi謂詞邏輯歸結原理謂詞邏輯歸結原理l例：例：設：設：f(y)/x,z/y，a/x,b/y,y/z，求，求 與與 的合成。的合成。解：先求出集合解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其中，其中，f(b)/x中的中的f(b)是置換是置換 作用于作用于f(y)的結果；的結果；y/y中的中的y是置換是置換 作用于作用于z的結果。

19、在該集合中，的結果。在該集合中，y/y滿足定義中的條滿足定義中的條件件i，需要刪除；，需要刪除；a/x，b/y滿足定義中的條件滿足定義中的條件ii，也需要刪除。，也需要刪除。最后得最后得 f(b)/x，y/z謂詞邏輯歸結原理謂詞邏輯歸結原理合一合一l合一可以簡單地理解為合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞尋找相對變量的置換，使兩個謂詞公式一致公式一致”。l定義：設有公式集定義：設有公式集FF1，F2，Fn，若存在一個置換，若存在一個置換，可使可使F1 F2=Fn，則稱，則稱 是是F的一個合一。同時稱的一個合一。同時稱F1，F2，.，Fn是可合一的。是可合一的。l 例：例：設有公

20、式集設有公式集FP(x,y,f(y),P(a,g(x),z)，則，則 a/x,g(a)/y,f(g(a)/z是它的一個合一。是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。注意：一般說來，一個公式集的合一不是唯一的。謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理歸結原理歸結原理l歸結的注意事項：歸結的注意事項：1.1.謂詞的一致性謂詞的一致性，P()P()與與Q()Q()，不可以不可以2.2.常量的一致性，常量的一致性，P(a,P(a,)與與P(b,P(b,.).)，不可以不可以 變量，變量，P(a,

21、P(a,.).)與與P(x,P(x,)，可以可以3.3.變量與函數，變量與函數，P(a,x,P(a,x,.).)與與P(x,f(x),P(x,f(x),)，不，不可以；可以；3.3.是不能同時消去兩個互補對，是不能同時消去兩個互補對，PQPQ與與PPQ Q的空，的空，不可以不可以4.4.先進行內部簡化（置換、合并）先進行內部簡化（置換、合并）謂詞邏輯歸結原理謂詞邏輯歸結原理l歸結的過程歸結的過程寫出謂詞關系公式寫出謂詞關系公式 用反演法寫出謂詞表達式用反演法寫出謂詞表達式 SKOLEMSKOLEM標準形標準形 子句集子句集S S 對對S S中可歸結的子句做歸結中可歸結的子句做歸結 歸結式仍放入

22、歸結式仍放入S S中，反復歸結過程中，反復歸結過程 得到空子句得到空子句 得證得證謂詞邏輯歸結原理謂詞邏輯歸結原理例題例題“快樂學生快樂學生”問題問題l假設任何通過計算機考試并獲獎的人都是快樂的，任假設任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的人都可以通過所有的考試，張不肯何肯學習或幸運的人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。張是快樂的。l 解：先將問題用謂詞表示如下：解：先將問題用謂詞表示如下：lR1:“任何通過計算機考試并獲獎的人都是快樂的任何通過計算機考試并獲獎的人都是快樂的”

23、(x)(Pass(x,computer)Win(x,prize)Happy(x)lR2:“任何肯學習或幸運的人都可以通過所有考試任何肯學習或幸運的人都可以通過所有考試”(x)(y)(Study(x)Lucky(x)Pass(x,y)lR3:“張不肯學習但他是幸運的張不肯學習但他是幸運的”Study(zhang)Lucky(zhang)lR4:“任何幸運的人都能獲獎任何幸運的人都能獲獎”(x)(Luck(x)Win(x,prize)l結論：結論：“張是快樂的張是快樂的”的否定的否定Happy(zhang)例題例題“快樂學生快樂學生”問題問題l由由R1及邏輯轉換公式及邏輯轉換公式:PWH=（PW）

24、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：(6)Lucky(w)Win(w，prize)l由結論：由結論：(7)Happy(zhang)（結論的否定）（結論的否定）l(8)Pass(w,computer)Happy(w)Luck(w)(1)(6)，w/xl(9)Pass(zhang,computer)Lucky(zhang)(8)(7)，zhang/wl(10

25、)Pass(zhang,computer)(9)(5)l(11)Lucky(zhang)(10)(3)，zhang/u,computer/vl(12)(11)(5)l歸結法的實質：歸結法的實質：l歸結法是僅有一條推理規則的推理方法。歸結法是僅有一條推理規則的推理方法。l歸結的過程是一個語義樹倒塌的過程。歸結的過程是一個語義樹倒塌的過程。l歸結法的問題歸結法的問題l子句中有等號或不等號時，完備性不成立。子句中有等號或不等號時，完備性不成立。Herbrand Herbrand定理的不實用性引出了可實用的定理的不實用性引出了可實用的歸結法。歸結法。謂詞邏輯歸結原理謂詞邏輯歸結原理歸結過程的控制策略歸

26、結過程的控制策略l要解決的問題：要解決的問題：l歸結方法的知識爆炸。歸結方法的知識爆炸。l控制策略的目的控制策略的目的l歸結點盡量少歸結點盡量少l控制策略的原則控制策略的原則l給出控制策略，以使僅對選擇合適的子句給出控制策略，以使僅對選擇合適的子句間方可做歸結。避免多余的、不必要的歸間方可做歸結。避免多余的、不必要的歸結式出現?；蛘哒f，少做些歸結仍能導出結式出現?；蛘哒f，少做些歸結仍能導出空子句?？兆泳?。謂詞邏輯歸結原理謂詞邏輯歸結原理刪除策略刪除策略=完備完備l名詞解釋：歸類：設有兩個子句名詞解釋：歸類：設有兩個子句C C和和D D，若有置換，若有置換 使得使得C C D D成立，則稱子句成

27、立，則稱子句C C把子句把子句D D歸類。歸類。由于小的可以代表大的，所以小的吃掉大的了。由于小的可以代表大的，所以小的吃掉大的了。l若對若對S S使用歸結推理過程中，當歸結式使用歸結推理過程中，當歸結式C Cj j是重言式是重言式（永真式）和（永真式）和C Cj j被被S S中子句和子句集的歸結式中子句和子句集的歸結式C Ci i(ij)(ij)所歸類時，便將所歸類時，便將C Cj j刪除。這樣的推理過程便稱做使刪除。這樣的推理過程便稱做使用了刪除策略的歸結過程。用了刪除策略的歸結過程。謂詞邏輯歸結原理謂詞邏輯歸結原理l主要思想：歸結過程在尋找可歸結子句時，子主要思想：歸結過程在尋找可歸結子

28、句時，子句集中的子句越多，需要付出的代價就會越大。句集中的子句越多，需要付出的代價就會越大。如果在歸結時能把子句集中無用的子句刪除掉，如果在歸結時能把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數，從而提高就會縮小搜索范圍，減少比較次數，從而提高歸結效率。刪除策略對阻止不必要的歸結式的歸結效率。刪除策略對阻止不必要的歸結式的產生來縮短歸結過程是有效的。然而要在歸結產生來縮短歸結過程是有效的。然而要在歸結式式C Cj j產生后方能判別它是否可被刪除，這部分產生后方能判別它是否可被刪除，這部分計算量是要花費的，只是節省了被刪除的子句計算量是要花費的，只是節省了被刪除的子句又生成的歸結式。

29、盡管使用刪除策略的歸結，又生成的歸結式。盡管使用刪除策略的歸結，少做了歸結但不影響產生空子句，就是說刪除少做了歸結但不影響產生空子句，就是說刪除策略的歸結推理是完備的。策略的歸結推理是完備的。謂詞邏輯歸結原理謂詞邏輯歸結原理采用支撐集采用支撐集 完備完備 支撐集：設有不可滿足子句集支撐集：設有不可滿足子句集S S的子集的子集T T，如，如果果S-TS-T是可滿足的，則是可滿足的，則T T是支持集。是支持集。采用支撐集策略時，從開始到得到采用支撐集策略時，從開始到得到的整個的整個歸結過程中，只選取不同時屬于歸結過程中，只選取不同時屬于S-TS-T的子句，的子句，在其間進行歸結。就是說，至少有一個

30、子在其間進行歸結。就是說，至少有一個子句來自于支撐集句來自于支撐集T T或由或由T T導出的歸結式。導出的歸結式。謂詞邏輯歸結原理謂詞邏輯歸結原理例如：例如：A A1 1AA2 2AA3 3B B中的中的B B可以作為支撐集使用?？梢宰鳛橹渭褂?。要求每一次參加歸結的親本子句中，只要應該有一個是要求每一次參加歸結的親本子句中，只要應該有一個是有目標公式的否定（有目標公式的否定（B B）所得到的子句或者它們的后）所得到的子句或者它們的后裔。裔。l支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用支撐集策略達到加快歸結速度的目的。公式

31、都可以用采用支撐集策略達到加快歸結速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標子句的非，即集是目標子句的非，即S SB B。謂詞邏輯歸結原理謂詞邏輯歸結原理ST可滿足支撐集示意圖謂詞邏輯歸結原理謂詞邏輯歸結原理 語義歸結語義歸結 完備完備 語義歸結策略是將子句語義歸結策略是將子句S S按照一定的語義按照一定的語義分成兩部分，約定每部分內的子句間不允許分成兩部分，約定每部分內的子句間不允許作歸結。同時還引入了文字次序，約定歸結作歸結。同時還引入了文字次序，約定歸結時其中的一個子句的被歸結文字只能是該子時其中的一個子句的被歸結

32、文字只能是該子句中句中“最大最大”的文字。的文字。語義歸結策略的歸結是完備的，同樣，語義歸結策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用語義歸所有可歸結的謂詞公式都可以用采用語義歸結策略達到加快歸結速度的目的。問題是如結策略達到加快歸結速度的目的。問題是如何尋找合適的語義分類方法，并根據其含義何尋找合適的語義分類方法，并根據其含義將子句集兩個部分中的子句進行排序。將子句集兩個部分中的子句進行排序。謂詞邏輯歸結原理謂詞邏輯歸結原理線性歸結線性歸結 完備完備 線性歸結策略首先從子句集中選取一個稱作頂線性歸結策略首先從子句集中選取一個稱作頂子句的子句子句的子句C C0 0開始作歸結。歸

33、結過程中所得到的歸開始作歸結。歸結過程中所得到的歸結式結式C Ci i立即同另一子句立即同另一子句B Bi i進行歸結得歸結式進行歸結得歸結式C Ci+1i+1。而。而B Bi i屬于屬于S S或是已出現的歸結式或是已出現的歸結式C Cj j(ji)(j=完備完備 單元歸結策略要求在歸結過程中，每次歸結都單元歸結策略要求在歸結過程中，每次歸結都有一個子句是單元子句（只含一個文字的子句）有一個子句是單元子句（只含一個文字的子句）或單元因子。顯而易見，詞中方法可以簡單地削或單元因子。顯而易見，詞中方法可以簡單地削去另一個非單子句中的一個因子，使其長度減少，去另一個非單子句中的一個因子，使其長度減少

34、，構成簡單化，歸結效率較高。構成簡單化，歸結效率較高。初始子句集中沒有單元子句時，單元歸結策略初始子句集中沒有單元子句時，單元歸結策略無效。所以說無效。所以說“反之不成立反之不成立”，即此問題不能采，即此問題不能采用單元歸結策略用單元歸結策略。輸入歸結輸入歸結 =完備完備 與單元歸結策略相似，輸入歸結策略要求在歸結與單元歸結策略相似，輸入歸結策略要求在歸結過程中，每一次歸結的兩個子句中必須有一個是過程中，每一次歸結的兩個子句中必須有一個是S S的的原始子句。這樣可以避免歸結出的不必要的新子句原始子句。這樣可以避免歸結出的不必要的新子句加入歸結，造成惡性循環?？梢詼p少不必要的歸結加入歸結，造成惡性循環?？梢詼p少不必要的歸結次數。次數。如同單元歸結策略，不是所有的可歸結謂如同單元歸結策略，不是所有的可歸結謂詞公式的最后結論都是可以從原始子句集詞公式的最后結論都是可以從原始子句集中的得到的。簡單的例子，歸結結束時，中的得到的。簡單的例子，歸結結束時，即最后一個歸結式為空子句的條件是，參即最后一個歸結式為空子句的條件是，參加歸結的雙方必須是兩個單元子句。原始加歸結的雙方必須是兩個單元子句。原始子句集中沒有單元子句的謂詞公式一定不子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結策略。能采用輸入歸結策略。演講完畢，謝謝觀看！