人工智能導(dǎo)論-第3章

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

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

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

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

5、如果： G L1 L2 Ln 其中Li（i = 1, 2, , n）是原子或原子的非的合取式。 合取范式：公式G為合取范式，如果： G L1 L2 Ln 其中Li（i = 1, 2, , n）是原子或原子的非的惜取式。 任何一個(gè)公式在等價(jià)的意義下，都可轉(zhuǎn)化成析取范式或者合取范式。 文字（Literal）：一個(gè)原子或原子的非。 子句（Clause）：文字的析取式。 空子句：不含文字的空集合。,人工智能原理第三章 歸結(jié)推理方法,命題邏輯基礎(chǔ)：基本等值式,基本等值式24個(gè)(1) 交換率：pq q p ； p q q p 結(jié)合率： (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),人工智能原理第三章 歸結(jié)推理方法,命題邏輯基礎(chǔ)：基本等值式,基本等值式（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(恒假) 蘊(yùn)含等值式:p q pq 假言易位式: p q q p,人工智能原理第三章 歸結(jié)推理方法,命題例,命題：能判斷真假（不是既真又假）的陳述句。 簡(jiǎn)單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)。 例如：1 1+1=2 2 雪是黑色的

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

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

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

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

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

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

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

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

15、指定一個(gè)函數(shù)，即指定Dn到D的一個(gè)映射； 對(duì)每個(gè)m元謂詞符號(hào)，指定一個(gè)謂詞，即指定Dm到T, F的一個(gè)映射。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)原理基礎(chǔ)：解釋舉例,給出如下兩個(gè)公式： (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值。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)原理基礎(chǔ),例如：（1）所有的人都是要死的。 （

16、2） 有的人活到一百歲以上。 在個(gè)體域D為人類集合時(shí)，可符號(hào)化為： （1）xP(x)，其中P(x)表示x是要死的。 （2）x Q(x), 其中Q(x)表示x活到一百歲以上。 在個(gè)體域D是全總個(gè)體域時(shí)， 引入特殊謂詞R(x)表示x是人，可符號(hào)化為： （1）x（R(x) P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。 （2）x（R(x) Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)原理基礎(chǔ),量詞否定等值式： ( 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） 消去量詞等值式：設(shè)個(gè)體域?yàn)橛懈F集合（a1, a2, an） ( x ） P（x） P（ a1 ） P（ a2 ） P（ an ） ( x ）P（x） P（ a1 ） P（ a2 ） P（ an ）,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)原理基礎(chǔ),量詞轄域收縮與擴(kuò)張等值式： ( 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）,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形),SKOLEM標(biāo)準(zhǔn)形 前束范式 定義：說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形),即： 把

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

20、不唯一。 SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后的謂詞公式。 注意：謂詞公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形),例:將下式化為Skolem標(biāo)準(zhǔn)形： (x)(y)P(a, x, y) (x)(y)Q(y, b)R(x) 解：第一步，消去號(hào)，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) 第二步，深入到量詞內(nèi)部，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) 第三步，變?cè)酌?，?(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) 由此得到前述范式,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形),第五步，消去“”（存在量詞），略去“”全稱量詞 消去(y)，因?yàn)樗筮呏挥?x)，所以使用x的函數(shù)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標(biāo)準(zhǔn)形為： P(a, x, f(x

22、) Q(g(x), b)R(x),人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形,子句與子句集 文字：不含任何連接詞的謂詞公式。 子句：一些文字的析取（謂詞的和）。 子句集S的求取： G SKOLEM標(biāo)準(zhǔn)形 消去存在變量 以“，”取代“”，并表示為集合形式 。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形,G是不可滿足的 S是不可滿足的 G與S不等價(jià)，但在不可滿足的意義下是一致的。 定理： 若G是給定的公式，而S是相應(yīng)的子句集，則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(xiàn)弄假S。,人工智能原理第三章 歸結(jié)推理方法,謂詞歸結(jié)子句形,G = G1 G2 G3 Gn 的子句形 G的字句集可以分解成幾個(gè)單獨(dú)處理。 有 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不可滿足,人工智能原理第三章 歸結(jié)推理方法,求取子句集例(1),例：對(duì)所有的x,y,z來(lái)說(shuō)，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個(gè)人都有父親，試問(wèn)對(duì)某個(gè)人來(lái)說(shuō)誰(shuí)是它的祖父

24、？ 求：用一階邏輯表示這個(gè)問(wèn)題，并建立子句集。 解：這里我們首先引入謂詞： P(x, y) 表示x是y的父親 Q(x, y) 表示x是y的祖父 ANS(x) 表示問(wèn)題的解答,人工智能原理第三章 歸結(jié)推理方法,求取子句集例(2),對(duì)于第一個(gè)條件，“如果x是y 的父親， y又是z 的父親，則x是z 的祖父”，一階邏輯表達(dá)式如下： A1：(x)(y)(z)(P(x, y)P(y, z)Q(x, z) S A1：P(x ,y)P(y, z)Q(x, z) 對(duì)于第二個(gè)條件：“每個(gè)人都有父親”，一階邏輯表達(dá)式： A2：(y)(x)P(x, y) S A2：P(f(y), y) 對(duì)于結(jié)論：某個(gè)人是它的祖父

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

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

27、n， u1/y1, u2/y2, , um/ym，是兩個(gè)置換。 則與的合成也是一個(gè)置換，記作。它是從集合 t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , um/ym 中刪去以下兩種元素： 當(dāng)yix1,x2, , xn時(shí)，刪去ui/yi (i = 1, 2, , m) 當(dāng)ti=xi時(shí)，刪去ti/xi (i = 1, 2, , n); 最后剩下的元素所構(gòu)成的集合。 合成即是對(duì)ti先做置換然后再做置換，置換xi,人工智能原理第三章 歸結(jié)推理方法,置換的合成,例： 設(shè)：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)的結(jié)果；y/y中的y是置換作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件i，需要?jiǎng)h除；a/x，b/y滿足定義中的條件ii，也需要?jiǎng)h除。最后得 f(b)/x，y/z,人工智能原理第三章 歸結(jié)推理方法,合一,合一可以簡(jiǎn)單地理解為“尋找相對(duì)變量的置換，使兩個(gè)謂詞公式一致”。 定義：設(shè)有公式集FF1，F(xiàn)2，F(xiàn)n，若存在一個(gè)置換，可使F1F2= Fn，則稱是F的一個(gè)合一。同時(shí)稱F1，F(xiàn)2，. ，F(xiàn)n是可合一的。 例： 設(shè)有公式集FP(x, y, f(y),

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

30、空，不可以 先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并）,人工智能原理第三章 歸結(jié)推理方法,歸結(jié)原理,歸結(jié)的過(guò)程 寫(xiě)出謂詞關(guān)系公式 用反演法寫(xiě)出謂詞表達(dá)式 SKOLEM標(biāo)準(zhǔn)形 子句集S 對(duì)S中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程 得到空子句 得證,人工智能原理第三章 歸結(jié)推理方法,歸結(jié)原理的完備性：歸結(jié)式,定義：歸結(jié)式：設(shè)C1，C2是兩個(gè)無(wú)公共變量的兩個(gè)子句，L1、L2分別是C1、C2中的兩個(gè)文字。如果L1、L2有最一般合一，則子句 (C1 - L1 ) (C2 - L2 ) 稱為C1和C2的二元?dú)w結(jié)式， L1和L2稱為歸結(jié)文字。 例如： 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).,人工智能原理第三章 歸結(jié)推理方法,歸結(jié)原理的完備性,設(shè)S是子句集，從S推出子句C的一個(gè)演繹是如下一個(gè)有限子句序列： C1，C2，Ck 其中Ci或者是S中的子句，或者是Cj和Cr的歸結(jié)式(ji, ri)；并且Ck = C. 從S推出空子句的演繹稱為一個(gè)反駁，或稱為S的一個(gè)證明。 定理：如果子句集S是不可滿足的，則存在從S推出空子句的歸結(jié)演繹。,人工智能原理第三章 歸結(jié)推理方法,例題“快樂(lè)學(xué)生”問(wèn)題,假設(shè)任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的

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

33、原理第三章 歸結(jié)推理方法,例題“快樂(lè)學(xué)生”問(wèn)題,由R1及邏輯轉(zhuǎn)換公式: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) 由結(jié)論：(7)Happy(zhang)（結(jié)論的否定） (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),人工智能原理第三章 歸結(jié)推理方法,Schuberts Steamroller Problem,1978年Alberta大學(xué)的L. Schubert教授提出了以下具有挑戰(zhàn)性的、著名的人工智能問(wèn)題18： 狼（wolves）、狐貍（foxes）、鳥(niǎo)（birds）、毛蟲(chóng)（caterpillars）及蛇（snails）都是動(dòng)物（animals），且存在著這些動(dòng)

35、物。同時(shí)也存在著一些谷物（grains），且谷物是一種植物（plants）。每一種動(dòng)物喜歡吃所有的植物或所有那些比本身小且喜歡吃某些植物的動(dòng)物。毛蟲(chóng)和蛇比鳥(niǎo)小，鳥(niǎo)又比狐貍小，狐貍又比狼小。狼不喜歡吃狐貍和谷物，鳥(niǎo)喜歡吃毛蟲(chóng)而不喜歡吃蛇，毛蟲(chóng)與蛇喜歡吃某些植物。因此，有一種動(dòng)物喜歡吃某種喜歡吃谷物的動(dòng)物。,人工智能原理第三章 歸結(jié)推理方法,歸結(jié)原理,歸結(jié)法的實(shí)質(zhì)： 歸結(jié)法是僅有一條推理規(guī)則的推理方法。 歸結(jié)的過(guò)程是一個(gè)語(yǔ)義樹(shù)倒塌的過(guò)程。 歸結(jié)法的問(wèn)題 子句中有等號(hào)或不等號(hào)時(shí)，完備性不成立。 Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。,人工智能原理第三章 歸結(jié)推理方法,第三章 歸結(jié)推理方

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

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

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

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

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

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

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

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

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

45、解： H0 a, b為子句集中出現(xiàn)的常量 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域，簡(jiǎn)稱H域。,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理（H域）,幾個(gè)基本概念 f（tn）：f為子句集S中的所有函數(shù)變量。t1, t2, tn為S的H域的元素。通過(guò)它們來(lái)討論永真性。 原子集A：謂詞

47、套上H域的元素組成的集合。如 A = 所有形如 P(t1, t2, tn)的元素 即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。,人工智能原理第三章 歸結(jié)推理方法,原子集例題,上例題的原子集為： 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),) 一旦原子集內(nèi)真值確定好（規(guī)定好），則S在H上的真值可確定。成為可數(shù)問(wèn)題。,人工智能原理第三章

48、 歸結(jié)推理方法,Herbrand定理,H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理,H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理（H解釋）,解釋I：謂詞公式G在論域D上任何一組真值的指定稱為一個(gè)解釋。 H解釋：子句集S在的H域上的解釋稱為H解釋。 問(wèn)題： 對(duì)于所有的解釋，全是假才可判定。因?yàn)樗薪忉尨砹怂械那闆r，如可窮舉，問(wèn)題便可解決 。,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理：H解釋,定義：設(shè)S是子句集，H是S的H域，I是S在H上的一個(gè)解釋。稱I為S的一

49、個(gè)H解釋，如果I滿足以下條件： I映射S中的每個(gè)常量符號(hào)到自身； 若f是S中n元函數(shù)符號(hào)，h1， hn是H中元素，則I指定映射 (h1， hn)f (h1， hn); 由定義可以看出，S的H解釋對(duì)于S中n原謂詞符號(hào)的指定沒(méi)有約束。,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理：H解釋,設(shè)A=A1, Sn, 是S的原子集。于是S的一個(gè)H解釋I可方便地表示為如下一個(gè)集合： I=m1, m2, , mn, 其中,人工智能原理第三章 歸結(jié)推理方法,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), ,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理：H解釋,當(dāng)然，子句集S的一個(gè)解釋不是必須定義在H域上，即使定義在H域上，也不一定是一個(gè)H解釋： 例如SP(x), Q(y, f(y,a),令S的一個(gè)解釋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.,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理（H解釋）,如下三個(gè)定理保證了歸結(jié)法的正確性： 定理1： 設(shè)I是S的論域D上的解釋，存在對(duì)應(yīng)于I的H解釋I*，使得若有S|I = T，必有 S|I* = T。 定理2： 子句集S是不可滿足的，當(dāng)且僅當(dāng)S 在所有的H解釋下為假。 定理3： 子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理（H解釋）,基例 S中某子句中所有變?cè)?hào)均以S的

52、H域中的元素代入時(shí)，所得的基子句C稱為C的一個(gè)基例。 一般來(lái)說(shuō)，D是無(wú)窮不可列的，因此，子句集S也是無(wú)窮不可列的。但S確定后H是無(wú)窮可列的。不過(guò)在H上證明S的不可滿足性仍然是不可能的。 解決問(wèn)題的方法：語(yǔ)義樹(shù),人工智能原理第三章 歸結(jié)推理方法,Herbrand定理,H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理,H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理,人工智能原理第三章 歸結(jié)推理方法,Herbrand定理（語(yǔ)義樹(shù)）,構(gòu)成方法 原子集中所有元素逐層添加的一棵二叉樹(shù)。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫(huà)完） 。 特點(diǎn) 一般情況H是可數(shù)集，S的語(yǔ)義樹(shù)是無(wú)限樹(shù)。,人工智能原理第三章 歸結(jié)推理方法,H