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

3、Qx Q( (x x), ), 其中其中Q Q( (x x) )表示表示x x活到一百歲以上。活到一百歲以上。在個體域在個體域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

4、 Q( (x x) )表示表示x x活到一百歲以上。活到一百歲以上。 一階邏輯一階邏輯l公式及其解釋公式及其解釋l個體常量：個體常量：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 ）

5、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）消去量詞等值式：消去量詞等值式：設個體域為有窮集合（設個體域為有窮集合（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 ）謂詞邏輯基礎謂詞邏輯基礎量詞轄域收縮與擴張等值式：量詞轄域收縮與擴張等值式：

6、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） 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

7、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中中的一切量詞都位于該公式的最左邊（不含否的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的定詞），且這些量詞的轄域都延伸到公式的末端。末端。 謂詞邏輯歸結原理謂詞邏

8、輯歸結原理即：即： 把所有的量詞都提到前面去，然后消把所有的量詞都提到前面去，然后消掉所有量詞掉所有量詞(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 l l l l l l l l l l l l l l l ll量詞消去原則：量詞消去原則

9、：消去存在量詞消去存在量詞“ ”，略去全程量詞，略去全程量詞“ ”。注意：注意：左邊有全程量詞的存在量詞，消去左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數；如沒時該變量改寫成為全程量詞的函數；如沒有，改寫成為常量。有，改寫成為常量。 謂詞邏輯歸結原理謂詞邏輯歸結原理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標準形定義：標準

10、形定義：消去量詞后的謂詞公式。消去量詞后的謂詞公式。注意注意：謂詞公式：謂詞公式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(y, b)R(x)l第三

11、步，變元易名，得第三步，變元易名，得( 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

12、, f(x) Q(v, b)R(u)l消去消去( 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 G SKOLEM SKOLEM標準形標準形 消去存在變量消去

13、存在變量 以以“，”取代取代“”，并表示為集合形式，并表示為集合形式 。謂詞邏輯歸結原理謂詞邏輯歸結原理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 的子句

14、形的子句形lG G的字句集可以分解成幾個單獨處理。的字句集可以分解成幾個單獨處理。 l有有 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在不可滿足得意義在不可滿足得意義上是一致的。上是一致的。即即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的父親

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

16、一階邏輯表達式如下：，一階邏輯表達式如下：A1：( x)( y)( z)(P(x, y)P(y, z)Q(x, z)S A1：P(x ,y)P(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

17、A2，SB 謂詞邏輯歸結原理謂詞邏輯歸結原理l歸結原理正確性的根本在于，找到矛盾歸結原理正確性的根本在于，找到矛盾可以肯定不真。可以肯定不真。l方法：方法：l和命題邏輯一樣。和命題邏輯一樣。l但由于有函數，所以要考慮但由于有函數，所以要考慮合一合一和和置換置換。 謂詞邏輯歸結原理謂詞邏輯歸結原理l置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。量。l定義：定義：置換是形如置換是形如t1/x1, t2/x2, , tn/xn的有限集合。其中，的有限集合。其中，x1, x2, , xn是互不相同的變量，是互不相同的變量，t1, t

18、2, , tn是不同于是不同于xi的項（常量、變量、函的項（常量、變量、函數）；數）；ti/xi表示用表示用ti置換置換xi，并且要求，并且要求ti與與xi不能相同，而且不能相同，而且xi不能不能循環地出現在另一個循環地出現在另一個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，是兩個置換。，是兩個置換。 則則 與與 的合成也是一個置換，記作的合成也是一個置換

19、，記作 。它是從集合。它是從集合t1 /x1, t2 /x2, , tn /xn, u1/y1, u2/y2, , un/yn 中刪去以下兩種元素：中刪去以下兩種元素：li. 當當ti =xi時，刪去時，刪去ti /xi (i = 1, 2, , n);lIi. 當當yi x1,x2, , xn時，刪去時，刪去uj/yj (j = 1, 2, , m)最后剩下的元素所構成的集合。最后剩下的元素所構成的集合。 合成即是對合成即是對ti先做先做 置換然后再做置換然后再做 置換，置換置換，置換xi謂詞邏輯歸結原理謂詞邏輯歸結原理l例：例：設：設： f(y)/x, z/y， a/x, b/y, y/z

20、，求，求 與與 的合成。的合成。解：先求出集合解：先求出集合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的結果。在該集合中，的結果。在該集合中，y/y滿足定義中的條滿足定義中的條件件i，需要刪除；，需要刪除；a/x，b/y滿足定義中的條件滿足定義中的條件ii，也需要刪除。，也需要刪除。最后得最后得 f(b)/x，y/z謂詞邏輯歸結原理謂詞邏輯歸結原理合一合一l合一可以簡單地理解為合一可以簡單

21、地理解為“尋找相對變量的置換，使兩個謂詞尋找相對變量的置換，使兩個謂詞公式一致公式一致”。l定義：設有公式集定義：設有公式集FF1，F2，Fn，若存在一個置換，若存在一個置換 ，可使可使F1 F2 = Fn ，則稱，則稱 是是F的一個合一。同時稱的一個合一。同時稱F1，F2，. ，Fn是可合一的。是可合一的。l 例：例：設有公式集設有公式集FP(x, y, f(y), P(a,g(x),z)，則，則 a/x, g(a)/y, f(g(a)/z是它的一個合一。是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。注意：一般說來，一個公式集的合一不是唯一的。 謂詞邏輯歸結原理謂詞邏輯歸結原理

22、謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理謂詞邏輯歸結原理歸結原理歸結原理l歸結的注意事項：歸結的注意事項：1. 1.謂詞的一致性謂詞的一致性，P()P()與與Q()Q()， 不可以不可以2.2.常量的一致性，常量的一致性，P(a, P(a, ) )與與P(b,P(b,.).)， 不可以不可以 變量，變量，P(a, P(a, .).)與與P(x, P(x, ) )， 可以可以3.3.變量與函數，變量與函數，P(a, x, P(a, x, .).)與與P(x, f(x), P(x, f(x), ) )，不，不可以；可以；3.3.是不能同時消去兩個互補對，是不

23、能同時消去兩個互補對，PQPQ與與PPQ Q的空，的空，不可以不可以4.4.先進行內部簡化（置換、合并）先進行內部簡化（置換、合并） 謂詞邏輯歸結原理謂詞邏輯歸結原理l歸結的過程歸結的過程寫出謂詞關系公式寫出謂詞關系公式 用反演法寫出謂詞表達式用反演法寫出謂詞表達式 SKOLEMSKOLEM標準形標準形 子句集子句集S S 對對S S中可歸結的子句做歸結中可歸結的子句做歸結 歸結式仍放入歸結式仍放入S S中，反復歸結過程中，反復歸結過程 得到空子句得到空子句 得證得證謂詞邏輯歸結原理謂詞邏輯歸結原理例題例題“快樂學生快樂學生”問題問題l假設任何通過計算機考試并獲獎的人都是快樂的，任假設任何通過

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

25、ucky(x)Pass(x, y)lR3:“張不肯學習但他是幸運的張不肯學習但他是幸運的”Study(zhang)Lucky(zhang)lR4:“任何幸運的人都能獲獎任何幸運的人都能獲獎”( x)(Luck(x)Win(x,prize)l結論：結論：“張是快樂的張是快樂的”的否定的否定Happy(zhang)例題例題“快樂學生快樂學生”問題問題l由由R1及邏輯轉換公式及邏輯轉換公式: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

26、(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) Pass(zhang, computer) (9)(5)l(11) Lucky(zhang) (10)(3)，zhang/u, computer/vl(12) (11

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

28、制策略的原則控制策略的原則l給出控制策略，以使僅對選擇合適的子句給出控制策略，以使僅對選擇合適的子句間方可做歸結。避免多余的、不必要的歸間方可做歸結。避免多余的、不必要的歸結式出現。或者說，少做些歸結仍能導出結式出現。或者說，少做些歸結仍能導出空子句。空子句。謂詞邏輯歸結原理謂詞邏輯歸結原理刪除策略刪除策略=完備完備l名詞解釋：歸類：設有兩個子句名詞解釋：歸類：設有兩個子句C C和和D D，若有置換，若有置換 使得使得C C D D成立，則稱子句成立，則稱子句C C把子句把子句D D歸類。歸類。由于小的可以代表大的，所以小的吃掉大的了。由于小的可以代表大的，所以小的吃掉大的了。l若對若對S S

29、使用歸結推理過程中，當歸結式使用歸結推理過程中，當歸結式C Cj j是重言式是重言式（永真式）和（永真式）和C Cj j被被S S中子句和子句集的歸結式中子句和子句集的歸結式C Ci i(ij)(ij)所歸類時，便將所歸類時，便將C Cj j刪除。這樣的推理過程便稱做使刪除。這樣的推理過程便稱做使用了刪除策略的歸結過程。用了刪除策略的歸結過程。謂詞邏輯歸結原理謂詞邏輯歸結原理l主要思想：歸結過程在尋找可歸結子句時，子主要思想：歸結過程在尋找可歸結子句時，子句集中的子句越多，需要付出的代價就會越大。句集中的子句越多，需要付出的代價就會越大。如果在歸結時能把子句集中無用的子句刪除掉，如果在歸結時能

30、把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數，從而提高就會縮小搜索范圍，減少比較次數，從而提高歸結效率。刪除策略對阻止不必要的歸結式的歸結效率。刪除策略對阻止不必要的歸結式的產生來縮短歸結過程是有效的。然而要在歸結產生來縮短歸結過程是有效的。然而要在歸結式式C Cj j產生后方能判別它是否可被刪除，這部分產生后方能判別它是否可被刪除，這部分計算量是要花費的，只是節省了被刪除的子句計算量是要花費的，只是節省了被刪除的子句又生成的歸結式。盡管使用刪除策略的歸結，又生成的歸結式。盡管使用刪除策略的歸結，少做了歸結但不影響產生空子句，就是說刪除少做了歸結但不影響產生空子句，就是說刪除策略

31、的歸結推理是完備的。策略的歸結推理是完備的。謂詞邏輯歸結原理謂詞邏輯歸結原理采用支撐集采用支撐集 完備完備 支撐集：設有不可滿足子句集支撐集：設有不可滿足子句集S S的子集的子集T T，如，如果果S-TS-T是可滿足的，則是可滿足的，則T T是支持集。是支持集。 采用支撐集策略時，從開始到得到采用支撐集策略時，從開始到得到的整個的整個歸結過程中，只選取不同時屬于歸結過程中，只選取不同時屬于S-TS-T的子句，的子句，在其間進行歸結。就是說，至少有一個子在其間進行歸結。就是說，至少有一個子句來自于支撐集句來自于支撐集T T或由或由T T導出的歸結式。導出的歸結式。 謂詞邏輯歸結原理謂詞邏輯歸結原

32、理例如：例如：A A1 1AA2 2AA3 3B B中的中的B B可以作為支撐集使用。可以作為支撐集使用。要求每一次參加歸結的親本子句中，只要應該有一個是要求每一次參加歸結的親本子句中，只要應該有一個是有目標公式的否定（有目標公式的否定（B B）所得到的子句或者它們的后）所得到的子句或者它們的后裔。裔。l支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用支撐集策略達到加快歸結速度的目的。公式都可以用采用支撐集策略達到加快歸結速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標子句的非，即集是目標子句的非，即S SB B。謂詞邏輯歸結原理謂詞邏輯歸結原理ST可滿足支撐集示意圖謂詞邏輯歸結原理謂詞邏輯歸結原理 語義歸結語義歸結 完備完備 語義歸結策略是將子句語義歸結策略是將子句S S按照一定的語義按照一定的語義分成兩部分，約定每部分內的子句間不允許分成兩部分，約定每部分內的子句間不允許作歸結。同時還引入了文字次序，約定歸結作歸結。同時還引入了文字次序，約定歸結時其中的一個子句的被歸結文字只能是該子時其中的一個子句的被歸結文字只能是該子句中句中“最大最大”的文字。的文字。 語義歸結策略的歸結是完備的，同樣，語義歸結策略的歸結是完備的，同樣，所有可歸