1、人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制,人工智能原理第三章 歸結推理方法,概述,歸結原理由J.A.Robinson由1965年提出。 與演繹法(deductive inference)完全不同，新的邏輯演算(inductive inference)算法。 一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使

2、用歸結原理，總可以在有限步內給以判定。 語義網絡、框架表示、產生式規則等等都是以推理方法為前提的。即，有了規則已知條件，順藤摸瓜找到結果。 而歸結方法是自動推理、自動推導證明用的。（“數學定理機器證明”） 本課程只討論一階謂詞邏輯描述下的歸結推理方法，不涉及高階謂詞邏輯問題。,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推

3、理方法,命題邏輯的歸結法,命題邏輯（Propositional Logic）基礎： 定義：對于命題p，q 命題的非： p 命題與（合取式）：p與q，記做p q 命題或（析取式）： p或q，記做p q 蘊含式： 如果p則q，記做p q 等價式：p當且僅當q，記做p q,人工智能原理第三章 歸結推理方法,命題邏輯基礎：公式,在命題邏輯中，我們將命題成為原子公式（Atomic Formula），簡稱原子。 定義：公式 原子是公式； 若G，H是公式，則(G)、(GH )、 (G H )、 (G H )、 (G H )是公式； 所有公式都是有限次使用(1)、(2)得到的符號串。,人工智能原理第三章 歸結

4、推理方法,命題邏輯基礎：真值表（解釋）,人工智能原理第三章 歸結推理方法,命題邏輯基礎,定義：對于公式A 若A在它的所有解釋I（Interpretation）下，其真值都為T（真），則稱A為重言式或恒真式； 若A在它的所有解釋I下，其真值都為F（假），則稱A為不可滿足的（Unsatisfiable，或永假式）； 若至少存在一個解釋I，使得A為真，則稱A為可滿足的（Satisfiable）； 邏輯蘊涵：公式G，H，如果（G H）是恒真的，記為G H 。 邏輯等價：公式G，H，如果（G H）是恒真的，記為G H 。,人工智能原理第三章 歸結推理方法,命題邏輯基礎：范式,析取范式：公式G為析取范式，

5、如果： G L1 L2 Ln 其中Li（i = 1, 2, , n）是原子或原子的非的合取式。 合取范式：公式G為合取范式，如果： G L1 L2 Ln 其中Li（i = 1, 2, , n）是原子或原子的非的惜取式。 任何一個公式在等價的意義下，都可轉化成析取范式或者合取范式。 文字（Literal）：一個原子或原子的非。 子句（Clause）：文字的析取式。 空子句：不含文字的空集合。,人工智能原理第三章 歸結推理方法,命題邏輯基礎：基本等值式,基本等值式24個(1) 交換率：pq q p ； p q q p 結合率： (pq) r p(q r); (p q) r p (q r) 分配率：

6、 p(q r) (pq)(p r) ； p (q r) (p q) (p r),人工智能原理第三章 歸結推理方法,命題邏輯基礎：基本等值式,基本等值式（1） 摩根率: (pq) p q ； (p q) p q 吸收率: p(pq ) p， p (pq ) p ； 泛界律: pF p ， pT p， p F F ， pT T 互余律：G G T(恒真)， G G F(恒假) 蘊含等值式:p q pq 假言易位式: p q q p,人工智能原理第三章 歸結推理方法,命題例,命題：能判斷真假（不是既真又假）的陳述句。 簡單陳述句描述事實、事物的狀態、關系等性質。 例如：1 1+1=2 2 雪是黑色的

7、。 3 北京是中國的首都。 4 到冥王星去渡假。 判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現在是假，隨著人類科學的發展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。 而例如：1 快點走吧！ 2 到那去？ 3 x+y10 等等句子，都不是命題。,人工智能原理第三章 歸結推理方法,命題表示公式（1）,將陳述句轉化成命題公式。 如：設“下雨”為p，“騎車上班”為q， 1“只要不下雨，我騎自行車上班”。p 是 q的充分條件， 因而，可得命題公式： p q 2“只有不下雨，我才騎自行車上班”。p 是 q的必要條件，

8、 因而，可得命題公式：q p,人工智能原理第三章 歸結推理方法,命題表示公式（2）,例如： 1 “如果我進城我就去看你，除非我很累。” 設：p，我進城，q，去看你，r，我很累。則有命題公式：r (p q)。 2“應屆高中生，得過數學或物理競賽的一等 獎， 保送上北京大學。” 設：p，應屆高中生，q，保送上北京大學上學， r，是得過數學一等獎。t，是得過物理一等獎。 則有命題公式公式：p ( r t ) q。,人工智能原理第三章 歸結推理方法,命題邏輯的歸結法,基本單元：簡單命題（陳述句） 例： 命題： A1、A2、A3 和 B 求證： A1A2A3成立，則B成立， 即：A1A2A3 B 反證法

9、：證明A1A2A3B 是矛盾式 （永假式）,人工智能原理第三章 歸結推理方法,命題邏輯的歸結法,建立子句集 合取范式：命題、命題和的與， 如： P（ PQ）（ PQ） 子句集S：合取范式形式下的子命題（元素）的集合 例：命題公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ,人工智能原理第三章 歸結推理方法,命題邏輯的歸結法,歸結式 消除互補對，求新子句得到歸結式。 如子句：C1, C2， 歸結式：R(C1, C2) = C1C2 注意：C1C2 R(C1, C2) ， 反之不一定成立。,人工智能原理第三章 歸結推理方法,命題邏輯的歸結法,歸結過程 將命題寫成合取范式 求出子

10、句集 對子句集使用歸結推理規則 歸結式作為新子句參加歸結 歸結式為空子句 ，S是不可滿足的（矛盾），原命題成立。 （證明完畢） 謂詞的歸結：除了有量詞和函數以外，其余和命題歸結過程一樣。,人工智能原理第三章 歸結推理方法,命題邏輯歸結例題（1）,例題，證明公式：(P Q) (Q P) 證明： （1）根據歸結原理，將待證明公式轉化成待歸結命題公式： 欲證結論的否： (P Q) (Q P) ( (P Q) (Q P) = (P Q) (Q P) （2）分別將公式前項化為合取范式： P Q P Q 結論求后的后項化為合取范式： (Q P) (QP) Q P 兩項合并后化為合取范式： （P Q）Q P

11、 （3）則子句集為： PQ，Q，P,人工智能原理第三章 歸結推理方法,命題邏輯歸結例題（2）,子句集為： PQ，Q，P （4）對子句集中的子句進行歸結可得： 1. PQ 2. Q 3. P 4. Q，（1，3歸結） 5. ，（2，4歸結） 由上可得原公式成立。,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,謂詞歸結

12、原理基礎,一階邏輯（First-Order Logic ) 為什么需要一階邏輯？ 命題A：人都是要死的。命題B：秦始皇是人。 命題C：秦始皇是要死的。 如何有A、B推出C呢？ 基本概念 個體詞：表示主語的詞 謂詞：刻畫個體性質或個體之間關系的詞 量詞：表示數量的詞,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎,小王是個工程師。 8是個自然數。 我去買花。 小麗和小華是朋友。 其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質，第三個謂詞“去買”表示的一個動作也表

13、示了主、賓兩個個體詞的關系，最后一個謂詞“是朋友”表示兩個個體詞之間的關系。,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎,一階邏輯 公式及其解釋 個體常量：a,b,c 個體變量：x,y,z 謂詞符號：P,Q,R 函數符號：f, g, h 量詞符號： ,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎：項與原子,定義：謂詞邏輯中的項（term）： 常量符號是項； 變量符號是項； 若f是n元函數符號，t1, t2, , tn是項, 則f(t1, t2, , tn)是項； 所有項都是有限次使用(1)-(3)生成的符號串。 定義：謂詞邏輯中的原子： 若P(x1, x2, , xn)是n元謂詞

14、符號， t1, t2, , tn是項，則P (t1, t2, , tn)是原子。,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎：公式,定義：謂詞邏輯中的公式 原子是公式； 若G，H是公式，則(G)、(GH )、 (G H )、 (G H )、 (G H )是公式； 若G是公式，x 是G中的自由變量，則(x)G，(x)G是公式； 所有公式都是有限次使用(1)(3)得到的符號串。,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎：解釋,定義：公式G的一個解釋I，是由非空區域D和下列對G中的常量符號、謂詞符號、函數符號的一組指定組成： 對每個常量符號，指定D中一個元素； 對每個n元函數符號，

15、指定一個函數，即指定Dn到D的一個映射； 對每個m元謂詞符號，指定一個謂詞，即指定Dm到T, F的一個映射。,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎：解釋舉例,給出如下兩個公式： (x)(P(f(x) Q(x, f(a). (x)(P(x) Q(x, a). 給出如下的解釋I： D=1, 2 a/1, f(1)/2, f(2)/1 P(1)/F, P(2)/T, Q(1, 1)/T, Q(1,2)/T, Q(2,1)/F, Q(2,2)/T 于是公式（1）在I下取T值，公式（2）在I下取F值。,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎,例如：（1）所有的人都是要死的。 （

16、2） 有的人活到一百歲以上。 在個體域D為人類集合時，可符號化為： （1）xP(x)，其中P(x)表示x是要死的。 （2）x Q(x), 其中Q(x)表示x活到一百歲以上。 在個體域D是全總個體域時， 引入特殊謂詞R(x)表示x是人，可符號化為： （1）x（R(x) P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。 （2）x（R(x) Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎,量詞否定等值式： ( x ） M（x） （ y ） M（y） ( x ） M（x） （ y ） M（y） 量詞分配等值式：

17、 ( x ）( P（x） Q（x）) ( x ） P（x） ( x ） Q（x） ( x ）( P（x） Q（x）) ( x ） P（x） ( x ） Q（x） 消去量詞等值式：設個體域為有窮集合（a1, a2, an） ( x ） P（x） P（ a1 ） P（ a2 ） P（ an ） ( x ）P（x） P（ a1 ） P（ a2 ） P（ an ）,人工智能原理第三章 歸結推理方法,謂詞歸結原理基礎,量詞轄域收縮與擴張等值式： ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x

18、） Q ( x ）(Q P（x） ) Q ( x ） P（x） ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）(Q P（x） ) Q ( x ） P（x）,人工智能原理第三章 歸結推理方法,謂詞歸結子句形( Skolem 標準形),SKOLEM標準形 前束范式 定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。,人工智能原理第三章 歸結推理方法,謂詞歸結子句形( Skolem 標準形),即： 把

19、所有的量詞都提到前面去，然后消掉所有量詞 (Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn) 約束變項換名規則： (Qx ） M（x） （Qy ） M（y） (Qx ） M（x,z） （Qy ） M（y,z）,人工智能原理第三章 歸結推理方法,謂詞歸結子句形( Skolem 標準形), 量詞消去原則： 消去存在量詞“”，略去全程量詞“”。 注意：左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數；如沒有，改寫成為常量。,人工智能原理第三章 歸結推理方法,謂詞歸結子句形( Skolem 標準形), Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式

20、不唯一。 SKOLEM標準形定義： 消去量詞后的謂詞公式。 注意：謂詞公式G的SKOLEM標準形同G并不等值。,人工智能原理第三章 歸結推理方法,謂詞歸結子句形( Skolem 標準形),例:將下式化為Skolem標準形： (x)(y)P(a, x, y) (x)(y)Q(y, b)R(x) 解：第一步，消去號，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) 第二步，深入到量詞內部，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) 第三步，變元易名，得 (x)(y)P(a, x, y) (u) ( v)(Q(v, b) R(u) 第四步

21、，存在量詞左移，直至所有的量詞移到前面，得： (x) (y) (u) ( v)P(a, x, y) (Q(v, b) R(u) 由此得到前述范式,人工智能原理第三章 歸結推理方法,謂詞歸結子句形( Skolem 標準形),第五步，消去“”（存在量詞），略去“”全稱量詞 消去(y)，因為它左邊只有(x)，所以使用x的函數f(x)代替之，這樣得到： (x)(z)( P(a, x, f(x) Q(z, b)R(x) 消去(z)，同理使用g(x)代替之，這樣得到： (x) ( P(a, x, f(x) Q(g(x), b)R(x) 則，略去全稱變量，原式的Skolem標準形為： P(a, x, f(x

22、) Q(g(x), b)R(x),人工智能原理第三章 歸結推理方法,謂詞歸結子句形,子句與子句集 文字：不含任何連接詞的謂詞公式。 子句：一些文字的析取（謂詞的和）。 子句集S的求取： G SKOLEM標準形 消去存在變量 以“，”取代“”，并表示為集合形式 。,人工智能原理第三章 歸結推理方法,謂詞歸結子句形,G是不可滿足的 S是不可滿足的 G與S不等價，但在不可滿足的意義下是一致的。 定理： 若G是給定的公式，而S是相應的子句集，則G是不可滿足的 S是不可滿足的。 注意：G真不一定S真，而S真必有G真。 即： S G 例：G = ( x)P(x), S = P(a). 令G和S 的解釋I如

23、下：D=1, 2 a: 1, P(1): F, P(2): T 顯然I滿足G，但I弄假S。,人工智能原理第三章 歸結推理方法,謂詞歸結子句形,G = G1 G2 G3 Gn 的子句形 G的字句集可以分解成幾個單獨處理。 有 SG = S1 U S2 U S3 U U Sn 則SG 與 S1 U S2 U S3 U U Sn在不可滿足的意義上是一致的。 即SG 不可滿足 S1 U S2 U S3 U U Sn不可滿足,人工智能原理第三章 歸結推理方法,求取子句集例(1),例：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父

24、？ 求：用一階邏輯表示這個問題，并建立子句集。 解：這里我們首先引入謂詞： P(x, y) 表示x是y的父親 Q(x, y) 表示x是y的祖父 ANS(x) 表示問題的解答,人工智能原理第三章 歸結推理方法,求取子句集例(2),對于第一個條件，“如果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(y, z)Q(x, z) 對于第二個條件：“每個人都有父親”，一階邏輯表達式： A2：(y)(x)P(x, y) S A2：P(f(y), y) 對于結論：某個人是它的祖父

25、B：(x)(y)Q(x, y) 否定后得到子句： （ (x)(y)Q(x, y)） ANS(x) SB：Q(x, y)ANS(x) 則得到的相應的子句集為： S A1，S A2，SB ,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,歸結原理,歸結原理正確性的根本在于，找到矛盾可以肯定不真。 方法： 和命題邏輯一樣。

26、 但由于有函數，所以要考慮合一和置換。,人工智能原理第三章 歸結推理方法,置換,置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。 定義： 置換是形如t1/x1, t2/x2, , tn/xn的有限集合。其中，x1, x2, , xn是互不相同的變量，t1, t2, , tn是不同于xi的項（常量、變量、函數）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環地出現在另一個ti中。 例如 a/x，c/y，f(b)/z是一個置換。 g(y)/x，f(x)/y不是一個置換，,人工智能原理第三章 歸結推理方法,置換的合成,設t1/x1, t2/x2, , tn/x

27、n， u1/y1, u2/y2, , um/ym，是兩個置換。 則與的合成也是一個置換，記作。它是從集合 t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , um/ym 中刪去以下兩種元素： 當yix1,x2, , xn時，刪去ui/yi (i = 1, 2, , m) 當ti=xi時，刪去ti/xi (i = 1, 2, , n); 最后剩下的元素所構成的集合。 合成即是對ti先做置換然后再做置換，置換xi,人工智能原理第三章 歸結推理方法,置換的合成,例： 設：f(y)/x, z/y，a/x, b/y, y/z，求與的合成。 解：先求出集合 f(b/y)/x, (

28、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,人工智能原理第三章 歸結推理方法,合一,合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式一致”。 定義：設有公式集FF1，F2，Fn，若存在一個置換，可使F1F2= Fn，則稱是F的一個合一。同時稱F1，F2，. ，Fn是可合一的。 例： 設有公式集FP(x, y, f(y),

29、 P(a,g(x),z)，則a/x, g(a)/y, f(g(a)/z是它的一個合一。 注意：一般說來，一個公式集的合一不是唯一的。 表達式集合 F1，F2，Fn的合一稱為是最一般合一（most general unigier， mgu)當且僅當對此集合的每一個合一，都存在置換：使得 = 。,人工智能原理第三章 歸結推理方法,歸結原理,歸結的注意事項： 謂詞的一致性，P()與Q()， 不可以 常量的一致性，P(a, )與P(b,.)， 不可以 變量，P(a, .)與P(x, )， 可以 變量與函數，P(a, x, .)與P(x, f(x), )，不可以； 是不能同時消去兩個互補對，PQ與PQ的

30、空，不可以 先進行內部簡化（置換、合并）,人工智能原理第三章 歸結推理方法,歸結原理,歸結的過程 寫出謂詞關系公式 用反演法寫出謂詞表達式 SKOLEM標準形 子句集S 對S中可歸結的子句做歸結 歸結式仍放入S中，反復歸結過程 得到空子句 得證,人工智能原理第三章 歸結推理方法,歸結原理的完備性：歸結式,定義：歸結式：設C1，C2是兩個無公共變量的兩個子句，L1、L2分別是C1、C2中的兩個文字。如果L1、L2有最一般合一，則子句 (C1 - L1 ) (C2 - L2 ) 稱為C1和C2的二元歸結式， L1和L2稱為歸結文字。 例如： C1P(x) Q(x), C2 = P(a) R(x)。

31、將C2中的x改為y。取L1=P(x)，L2=P(a), = a/x，于是(C1 - L1 ) (C2 - L2 ) Q(a) R(y).,人工智能原理第三章 歸結推理方法,歸結原理的完備性,設S是子句集，從S推出子句C的一個演繹是如下一個有限子句序列： C1，C2，Ck 其中Ci或者是S中的子句，或者是Cj和Cr的歸結式(ji, ri)；并且Ck = C. 從S推出空子句的演繹稱為一個反駁，或稱為S的一個證明。 定理：如果子句集S是不可滿足的，則存在從S推出空子句的歸結演繹。,人工智能原理第三章 歸結推理方法,例題“快樂學生”問題,假設任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的

32、人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。 解：先將問題用謂詞表示如下： R1:“任何通過計算機考試并獲獎的人都是快樂的” (x)(Pass(x, computer)Win(x, prize)Happy(x) R2:“任何肯學習或幸運的人都可以通過所有考試” (x)(y)(Study(x)Lucky(x)Pass(x, y) R3:“張不肯學習但他是幸運的” Study(zhang)Lucky(zhang) R4:“任何幸運的人都能獲獎” (x)(Luck(x)Win(x,prize) 結論：“張是快樂的”的否定 Happy(zhang),人工智能

33、原理第三章 歸結推理方法,例題“快樂學生”問題,由R1及邏輯轉換公式:PWH = （PW） H ，可得 (1)Pass(x, computer)Win(x, prize)Happy(x) 由R2： (2)Study(y)Pass(y,z) (3)Lucky(u)Pass(u,v) 由R3： (4)Study(zhang) (5)Lucky(zhang) 由R4： (6)Lucky(w)Win(w，prize) 由結論：(7)Happy(zhang)（結論的否定） (8)Pass(w, computer)Happy(w)Luck(w) (1)(6)，w/x (9)Pass(zhang, comp

34、uter)Lucky(zhang) (8)(7)，zhang/w (10)Pass(zhang, computer) (9)(5) (11)Lucky(zhang) (10)(3)，zhang/u, computer/v (12) (11)(5),人工智能原理第三章 歸結推理方法,Schuberts Steamroller Problem,1978年Alberta大學的L. Schubert教授提出了以下具有挑戰性的、著名的人工智能問題18： 狼（wolves）、狐貍（foxes）、鳥（birds）、毛蟲（caterpillars）及蛇（snails）都是動物（animals），且存在著這些動

35、物。同時也存在著一些谷物（grains），且谷物是一種植物（plants）。每一種動物喜歡吃所有的植物或所有那些比本身小且喜歡吃某些植物的動物。毛蟲和蛇比鳥小，鳥又比狐貍小，狐貍又比狼小。狼不喜歡吃狐貍和谷物，鳥喜歡吃毛蟲而不喜歡吃蛇，毛蟲與蛇喜歡吃某些植物。因此，有一種動物喜歡吃某種喜歡吃谷物的動物。,人工智能原理第三章 歸結推理方法,歸結原理,歸結法的實質： 歸結法是僅有一條推理規則的推理方法。 歸結的過程是一個語義樹倒塌的過程。 歸結法的問題 子句中有等號或不等號時，完備性不成立。 Herbrand定理的不實用性引出了可實用的歸結法。,人工智能原理第三章 歸結推理方法,第三章 歸結推理方

36、法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,歸結過程的控制策略,要解決的問題： 歸結方法的知識爆炸。 控制策略的目的 歸結點盡量少 控制策略的原則 給出控制策略，以使僅對選擇合適的子句間方可做歸結。避免多余的、不必要的歸結式出現。或者說，少做些歸結仍能導出空子句。,人工智能原理第三章 歸結推理方法,控制策略的方法(1),刪除策略=完備 名詞解釋：歸類：設有兩個子句

37、C和D，若有置換使得C D成立，則稱子句C把子句D歸類。 由于小的可以代表大的，所以小的吃掉大的了。 若對S使用歸結推理過程中，當歸結式Cj是重言式（永真式）和Cj被S中子句和子句集的歸結式Ci(ij)所歸類時，便將Cj刪除。這樣的推理過程便稱做使用了刪除策略的歸結過程。 主要思想：歸結過程在尋找可歸結子句時，子句集中的子句越多，需要付出的代價就會越大。如果在歸結時能把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數，從而提高歸結效率。刪除策略對阻止不必要的歸結式的產生來縮短歸結過程是有效的。然而要在歸結式Cj產生后方能判別它是否可被刪除，這部分計算量是要花費的，只是節省了被刪除的子句

38、又生成的歸結式。盡管使用刪除策略的歸結，少做了歸結但不影響產生空子句，就是說刪除策略的歸結推理是完備的。,人工智能原理第三章 歸結推理方法,控制策略的方法(2),采用支撐集完備 支撐集：設有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支持集。 采用支撐集策略時，從開始到得到的整個歸結過程中，只選取不同時屬于S-T的子句，在其間進行歸結。就是說，至少有一個子句來自于支撐集T或由T導出的歸結式。 例如：A1A2A3B中的B可以作為支撐集使用。要求每一次參加歸結的親本子句中，只要應該有一個是有目標公式的否定（B）所得到的子句或者它們的后裔。 支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞

39、公式都可以用采用支撐集策略達到加快歸結速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標子句的非，即SB。,人工智能原理第三章 歸結推理方法,人工智能原理第三章 歸結推理方法,控制策略的方法(3),語義歸結完備 語義歸結策略是將子句S按照一定的語義分成兩部分，約定每部分內的子句間不允許作歸結。同時還引入了文字次序，約定歸結時其中的一個子句的被歸結文字只能是該子句中“最大”的文字。 語義歸結策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用語義歸結策略達到加快歸結速度的目的。問題是如何尋找合適的語義分類方法，并根據其含義將子句集兩個部分中的子句進行排序。,人工智能原理第

40、三章 歸結推理方法,控制策略的方法(4),線性歸結 完備 線性歸結策略首先從子句集中選取一個稱作頂子句的子句C0開始作歸結。歸結過程中所得到的歸結式Ci立即同另一子句Bi進行歸結得歸結式Ci+1。而Bi屬于S或是已出現的歸結式Cj(ji)。即，如下圖所示歸結得到的新子句立即參加歸結。 線性歸結是完備的，同樣，所有可歸結的謂詞公式都可以采用線性歸結策略達到加快歸結速度的目的。如果能搞找到一個較好的頂子句，可以使歸結順利進行。否則也可能事與愿違。,人工智能原理第三章 歸結推理方法,人工智能原理第三章 歸結推理方法,控制策略的方法(5),單元歸結=完備 單元歸結策略要求在歸結過程中，每次歸結都有一個

41、子句是單元子句（只含一個文字的子句）或單元因子。顯而易見，詞中方法可以簡單地削去另一個非單子句中的一個因子，使其長度減少，構成簡單化，歸結效率較高。 初始子句集中沒有單元子句時，單元歸結策略無效。所以說“反之不成立”，即此問題不能采用單元歸結策略。,人工智能原理第三章 歸結推理方法,控制策略的方法(6),輸入歸結 =完備 與單元歸結策略相似，輸入歸結策略要求在歸結過程中，每一次歸結的兩個子句中必須有一個是S的原始子句。這樣可以避免歸結出的不必要的新子句加入歸結，造成惡性循環。可以減少不必要的歸結次數。 如同單元歸結策略，不是所有的可歸結謂詞公式的最后結論都是可以從原始子句集中的得到的。簡單的例

42、子，歸結結束時，即最后一個歸結式為空子句的條件是，參加歸結的雙方必須是兩個單元子句。原始子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結策略。,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,第三章 歸結推理方法,概述 命題邏輯的歸結法 謂詞歸結子句形 歸結原理 歸結過程的策略控制 Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理,問題： 一階邏輯公式的永真性（永假性）的判定是否能在有限步內完成？,人工智能原理第三章 歸結推理方法,

43、Herbrand定理,1936年圖靈(Turing)和邱吉(Church)互相獨立地證明了：,“沒有一般的方法使得在有限步內判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內得到結論。判定的過程將可能是不停止的。”,人工智能原理第三章 歸結推理方法,Herbrand定理,Herbrand的思想 定義： 公式G永真：對于G的所有解釋，G都為真。 思想： 尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內停止。,人工智能原理第三章

44、 歸結推理方法,Herbrand定理,H域 H解釋 語義樹 結論：Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理,H域 H解釋 語義樹 結論：Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理（H域）,基本方法： 因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數是無限、不可數的 。 簡化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。 此域稱為H域。,人工智能原理第三章 歸結推理方法,人工智能原理第三章 歸結推理方法,H域例題,設子句集S = P(x), Q(y,f(z,b),R(a)，求H域

45、解： H0 a, b為子句集中出現的常量 H1 a, b, f(a,b), f(a,a), f(b,a), f(b,b) H2 a, b, f(a,b), f(a,a), f(b,a), f(b,b)， f(a,f(a,b), f(a,f(a,a), f(a, f(b,a), f(a, f(b,b), f(b,f(a,b), f(b,f(a,a), f(b, f(b,a), f(b,f(b,b), f(f(a,b),f(a,b), f(f(a,b),f(a,a), f(f(a,b), f(b,a), f(f(a,b), f(b,b), f(f(a,a),f(a,b), f(f(a,a),f(a

46、,a), f(f(a,a), f(b,a), f(f(a,a), f(b,b), f(f(b,a),f(a,b), f(f(b,a),f(a,a), f(f(b,a), f(b,a), f(f(b,a), f(b,b), f(f(b,b),f(a,b), f(f(b,b),f(a,a), f(f(b,b), f(b,a), f(f(b,b), f(b,b) H 稱為S的Herbrand域，簡稱H域。,人工智能原理第三章 歸結推理方法,Herbrand定理（H域）,幾個基本概念 f（tn）：f為子句集S中的所有函數變量。t1, t2, tn為S的H域的元素。通過它們來討論永真性。 原子集A：謂詞

47、套上H域的元素組成的集合。如 A = 所有形如 P(t1, t2, tn)的元素 即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數的，因此，A也是可數的。,人工智能原理第三章 歸結推理方法,原子集例題,上例題的原子集為： A = P(a), Q(a, a), R(a), P(b), Q(b, a), Q(b, b), Q(a, b), R(b), P( f(a,b), Q(f(a, b), f(a, b), R(f(a, b), P(f(a,a), P(f(b,a), P(f(b,b),) 一旦原子集內真值確定好（規定好），則S在H上的真值可確定。成為可數問題。,人工智能原理第三章

48、 歸結推理方法,Herbrand定理,H域 H解釋 語義樹 結論：Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理,H域 H解釋 語義樹 結論：Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理（H解釋）,解釋I：謂詞公式G在論域D上任何一組真值的指定稱為一個解釋。 H解釋：子句集S在的H域上的解釋稱為H解釋。 問題： 對于所有的解釋，全是假才可判定。因為所有解釋代表了所有的情況，如可窮舉，問題便可解決 。,人工智能原理第三章 歸結推理方法,Herbrand定理：H解釋,定義：設S是子句集，H是S的H域，I是S在H上的一個解釋。稱I為S的一

49、個H解釋，如果I滿足以下條件： I映射S中的每個常量符號到自身； 若f是S中n元函數符號，h1， hn是H中元素，則I指定映射 (h1， hn)f (h1， hn); 由定義可以看出，S的H解釋對于S中n原謂詞符號的指定沒有約束。,人工智能原理第三章 歸結推理方法,Herbrand定理：H解釋,設A=A1, Sn, 是S的原子集。于是S的一個H解釋I可方便地表示為如下一個集合： I=m1, m2, , mn, 其中,人工智能原理第三章 歸結推理方法,Herbrand定理：H解釋,例 S=P(x) Q(x), R(f(y),于是， S的H域=a, f(a), f(f(a), S的原子集A=P(a

50、), Q(a), R(a), P(f(a), Q(f(a), R(f(a), 下面的解釋就是S的H解釋： I1=P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), I1=P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), ,人工智能原理第三章 歸結推理方法,Herbrand定理：H解釋,當然，子句集S的一個解釋不是必須定義在H域上，即使定義在H域上，也不一定是一個H解釋： 例如SP(x), Q(y, f(y,a),令S的一個解釋I如下： D 1，2,a/2, f(1,1)/1, f(1,2)/2, f(2,1)/2, f(2,2)

51、/1, P(1)/T, P(2)/F, Q(1,1)/F, Q(1,2)/F, Q(2,1)/F, Q(2,2)/T.,人工智能原理第三章 歸結推理方法,Herbrand定理（H解釋）,如下三個定理保證了歸結法的正確性： 定理1： 設I是S的論域D上的解釋，存在對應于I的H解釋I*，使得若有S|I = T，必有 S|I* = T。 定理2： 子句集S是不可滿足的，當且僅當S 在所有的H解釋下為假。 定理3： 子句集S是不可滿足的，當且僅當對每一個解釋I下，至少有S的某個子句的某個基例為假。,人工智能原理第三章 歸結推理方法,Herbrand定理（H解釋）,基例 S中某子句中所有變元符號均以S的

52、H域中的元素代入時，所得的基子句C稱為C的一個基例。 一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不過在H上證明S的不可滿足性仍然是不可能的。 解決問題的方法：語義樹,人工智能原理第三章 歸結推理方法,Herbrand定理,H域 H解釋 語義樹 結論：Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理,H域 H解釋 語義樹 結論：Herbrand定理,人工智能原理第三章 歸結推理方法,Herbrand定理（語義樹）,構成方法 原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標記在兩側的分枝上（可不完全畫完） 。 特點 一般情況H是可數集，S的語義樹是無限樹。,人工智能原理第三章 歸結推理方法,H