人工智能,第三章2

1、精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形( Skolem ( Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) ) 為了能夠像命題邏輯那樣進(jìn)行歸結(jié)，首先必須解決謂詞邏輯中的量詞問(wèn)題。 前束范式：如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形( Skolem ( Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )Skolem標(biāo)準(zhǔn)形前束范式中消去所有的量詞。Skolem函數(shù) 如果某個(gè)存在量詞是在其他任意量詞的轄域內(nèi)

2、，就存在某種依賴關(guān)系，可以用一個(gè)函數(shù)描述這種依賴關(guān)系，叫做Skolem函數(shù)。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形( Skolem ( Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )量詞消去原則：存在量詞。將該量詞約束的變量用任意常量（a，b等）或任意變量的函數(shù)（f(x)，g(y)等）代替。左邊有任意量詞的存在量詞，消去時(shí)該變量改寫成為任意量詞的函數(shù)；如沒(méi)有，改寫成為常量。任意量詞。簡(jiǎn)單地省略掉該量詞。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形( Skolem ( Sk

3、olem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )例:將下式化為Skolem標(biāo)準(zhǔn)形：(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) 第二步，深入到量詞內(nèi)部，得：(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) (y)(Q(y, b) R(x)精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句

4、形( Skolem ( Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) ) 第四步，變量易名，存在量詞左移，直至所有的量詞移到前面，得： (x)(y)P(a, x, y) (y)(Q(y, b) R(x) (x)(y)P(a, x, y) (z)(Q(z, b) R(x) (x)(y) (z) (P(a, x, y) Q(z, b) R(x)由此得到前述范式精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形( Skolem ( Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )第五步，消去存在量詞，略去任意量詞消去(y)，因?yàn)樗筮呏挥?x)，所以使用x的函數(shù)f(x)代

5、替，這樣得到：(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) Q(g(x), b)R(x) 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形( Skolem ( Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) ) Skolem定理：謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。 注意：謂詞公式G的Skolem標(biāo)準(zhǔn)形同G并不等值。 精

6、選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形 子句與子句集 文字：不含任何連接詞的謂詞公式。 子句：一些文字的析?。ㄖ^詞的和）。 空子句：不含任何文字的子句。記作NIL或 子句集：所有子句的集合。 對(duì)于任何一個(gè)謂詞公式G，都可以通過(guò)Skolem標(biāo)準(zhǔn)形，建立起一個(gè)子句集與之對(duì)應(yīng)。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形 子句集S的求?。?將謂詞公式G轉(zhuǎn)換成前束范式； 生成Skolem標(biāo)準(zhǔn)形； 將各個(gè)子句提出，以“，”取代“”，并表示為集合形式 。精選課件精選課件人

7、工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形 定理3.1 謂詞公式G是不可滿足的，當(dāng)且僅當(dāng)其子句集 S是不可滿足的。 G與S不等價(jià)，但在不可滿足的意義下是一致的。 注意：G真不一定S真，而S真必有G真。即： S = G精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理謂詞歸結(jié)子句形謂詞歸結(jié)子句形 定理3.1的推廣對(duì)于形如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在不可滿足的意

8、義上是一致的。即SG 不可滿足 S1 U S2 U S3 U U Sn不可滿足?？梢詫?duì)一個(gè)復(fù)雜的謂詞公式分而治之。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理求取子句集例求取子句集例(1)例：對(duì)所有的x,y,z來(lái)說(shuō)，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個(gè)人都有父親，試問(wèn)對(duì)某個(gè)人來(lái)說(shuō)誰(shuí)是他的祖父？求：用一階邏輯表示這個(gè)問(wèn)題，并建立子句集。解：這里我們首先引入謂詞：P(x, y) 表示y是x 的父親Q(x, y) 表示y是x的祖父ANS(x) 表示問(wèn)題的解答精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理求

9、取子句集例求取子句集例(2)對(duì)于第一個(gè)條件，“如果y是x的父親， z又是y的父親，則z是x的祖父”，一階邏輯表達(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：(x)(y)P(x, y)S A2：P(x,f(x)對(duì)于結(jié)論：某個(gè)人是他的祖父B：(x)(y)Q(x, y)否定后得到子句： ( (x)(y)Q(x, y)ANS(y)SB：Q(x, y)ANS(y)則得到的相應(yīng)的子句集為： S A1，S A2，SB 精選課件精選課件人工智能人工智能第三章第三章 謂詞

10、邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理置換與合一置換與合一 一階謂詞邏輯得歸結(jié)比命題邏輯的歸結(jié)要復(fù)雜的多，其中一個(gè)原因就是謂詞邏輯公式中含有個(gè)體變量與函數(shù)。 如P(x) Q(y)與P(a) R(z) 所以要考慮置換與合一。即對(duì)變量作適當(dāng)?shù)奶鎿Q。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(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置換

11、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é)原理謂詞邏輯與歸結(jié)原理置換的合成置換的合成 設(shè)t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn，是兩個(gè)置換。 則與的合成也是一個(gè)置換，記作。它是從集合t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , un/yn 中刪去以下兩種元素： 當(dāng)ti=xi時(shí)，刪去ti/xi (i = 1, 2, , n); 當(dāng)yix1,

12、x2, , xn時(shí)，刪去uj/yj (j = 1, 2, , m)最后剩下的元素所構(gòu)成的集合。 合成即是對(duì)ti先做置換然后再做置換精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理置換的合成置換的合成 例：設(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(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滿足定義中

13、的條件ii，也需要?jiǎng)h除。最后得f(b)/x，y/z精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(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), P(a,g(x),z)，則a/x, g(a)/y, f(g(a)/z是它的一個(gè)合一。注意：一般說(shuō)來(lái)，一個(gè)公式集的合一不是唯一的。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理

14、最一般合一（最一般合一（mgu） 設(shè)是謂詞公式集F的一個(gè)合一，如果對(duì)F的任意一個(gè)合一都存在一個(gè)置換，使得=.，則稱是一個(gè)最一般合一。 最一般合一求取方法 令W=F1,F2 令k=0,W0=W, 0= 如果Wk已合一，停止， k=mgu,否則找Dk 若Dk中存在元素vk和tk，其中，vk不出現(xiàn)在tk中，轉(zhuǎn)下一步，否則，不可合一。 令k+1= k.tk/vk,Wk+1=Wktk/vk=W k+1 K=k+1轉(zhuǎn)第3步。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理最一般合一（最一般合一（mgu）例：W=P(a,x,f(g(y),P(z,f(a),f(u),其中，F(xiàn)

15、1 P(a,x,f(g(y)，F(xiàn)2 P(z,f(a),f(u)求F1和F2的mgu解：由mgu算法(1)W= P(a,x,f(g(y),P(z,f(a),f(u)(2)W0=W,0=(3) W0 未合一，從左到右找差異集，有D0=a,z(4)取V0=z,t0a精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理最一般合一（最一般合一（mgu）(5)令1= 0. t0/v0=a/z W1= W0 1=P(a,x,f(g(y),P(a,f(a),f(u)(3) W1 未合一，找差異集，有D1=x,f(a)(4)取v1=x,t1f(a)(5)令2=1. t1/v1= a

16、/z,f(a)/x W2= W12=P(a,f(a),f(g(y),P(a,f(a),f(u)(3) W2 未合一，找差異集，有D2=g(y),u(4)取v2=u,t2g(y)精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理最一般合一（最一般合一（mgu）(5)令3=2. t2/v2=a/z,f(a)/x,g(y)/u W3= W2 3=P(a,f(a),f(g(y),P(a,f(a),f(g(y)(3) W3 已合一 3= a/z,f(a)/x,g(y)/u便是F1和F2的mgu。算法的第(4)步，當(dāng)不存在vk或不存在tk或出現(xiàn)差異集為x,f(x),都會(huì)導(dǎo)致

17、不可合一。此時(shí)，算法返回失敗。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理最一般合一（最一般合一（mgu） 謂詞邏輯的歸結(jié)方法和命題邏輯基本相同，但在進(jìn)行歸結(jié)之前，應(yīng)采用最一般合一方法對(duì)待歸結(jié)的一對(duì)子句進(jìn)行置換。然后再判斷是否可以進(jìn)行歸結(jié)。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理歸結(jié)原理歸結(jié)原理歸結(jié)時(shí)的注意事項(xiàng)：n謂詞的一致性，P()與Q()， 不可以n常量的一致性，P(a, )與P(b,.)， 不可以。變量與函數(shù)，P(a, x, .)與P(x, f(x), )，不可以；n不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，PQ與PQ得空，不

18、可以1.先進(jìn)行內(nèi)部簡(jiǎn)化再進(jìn)行置換與合并。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理歸結(jié)原理歸結(jié)原理 歸結(jié)的過(guò)程寫出謂詞關(guān)系公式 用反演法寫出謂詞表達(dá)式 SKOLEM標(biāo)準(zhǔn)形 求子句集S 對(duì)S中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程 得到空子句 命題得證。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理例題例題“快樂(lè)學(xué)生快樂(lè)學(xué)生”問(wèn)題問(wèn)題例：假設(shè)任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。求證：張是快樂(lè)的。 解：先將問(wèn)題用謂詞表

19、示如下： 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)精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理例題例題“快樂(lè)學(xué)生快樂(lè)學(xué)生”問(wèn)題問(wèn)題 R3:“張不肯學(xué)習(xí)但他是幸運(yùn)的”Study(zhang)Lucky(zhang) R4:“任何幸運(yùn)的人都能獲獎(jiǎng)”(x)(Luck(x)Win(x,prize) 結(jié)論：“張是快樂(lè)的”的否定Happy(zhang)精選課件精選課件

20、人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理 由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(zh

21、ang, computer)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é)原理謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理 概述 命題邏輯 謂詞邏輯的歸結(jié)法 歸結(jié)過(guò)程的控制策略 Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸

22、結(jié)原理 概述 命題邏輯 謂詞邏輯的歸結(jié)法 歸結(jié)過(guò)程的控制策略 Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理歸結(jié)過(guò)程的控制策略歸結(jié)過(guò)程的控制策略 要解決的問(wèn)題： 歸結(jié)方法的知識(shí)爆炸。 控制策略的目的 歸結(jié)點(diǎn)盡量少 控制策略的原則 給出控制策略，以使僅對(duì)選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f(shuō)，少做些歸結(jié)仍能導(dǎo)出空子句。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(1)刪除策略 歸類：設(shè)有兩個(gè)子句C和D，若有置換使得C D成立，則稱子句C把子句D歸類

23、。 若對(duì)S使用歸結(jié)推理過(guò)程中，當(dāng)歸結(jié)式Cj是重言式和Cj被S中子句和子句集的歸結(jié)式Ci(ij)所歸類時(shí)，便將Cj刪除。這樣的推理過(guò)程便稱作使用了刪除策略的歸結(jié)過(guò)程。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(1)刪除策略 如P(x)P(x), P(x)Q(x)P(x) P(x)歸類P(y)Q(z) =y/x 純文字刪除。如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則稱該文字為純文字。如S=PQR,QR,Q,R 盡管使用刪除策略的歸結(jié)，少做了歸結(jié)但不影響產(chǎn)生空子句，就是說(shuō)刪除策略的歸結(jié)推理是完備的。精選課件精選課件人工智能人

24、工智能第三章第三章 謂詞邏輯與歸結(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é)式。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(2)支撐集策略 例如：A1A2A3B中的B可以作為支撐集使用。要求每一次參加歸結(jié)的親本子句中，至少應(yīng)該有一個(gè)是由目標(biāo)公式的否定（B）所得到的子句或者它們的

25、后裔。 支撐集策略的歸結(jié)是完備的。同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問(wèn)題是如何尋找合適的支撐集。一個(gè)最容易找到的支撐集是目標(biāo)子句的非，即SB。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理ST可滿足支撐集示意圖精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(2)支撐集策略 例如：S(1)I(X)R(X) 目標(biāo)公式的否定得到的子句(2)I(a)(3)R(Y)VL(Y)(4)L(a) S1：(5) R(a) (1)與(2)歸結(jié)(6) I(x)VL(x) (1)

26、與(3)歸結(jié)(7)L(a) (2)與(6)歸結(jié)(8)NIL (4)與(7)歸結(jié)精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(3)語(yǔ)義歸結(jié)策略 語(yǔ)義歸結(jié)策略是將子句S按照一定的語(yǔ)義分成兩部分，約定每部分內(nèi)的子句間不允許作歸結(jié)。同時(shí)還引入了文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中“最大”的文字。語(yǔ)義歸結(jié)策略的歸結(jié)是完備的。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(4)線性歸結(jié) 線性歸結(jié)策略首先從子句集中選取一個(gè)稱作頂子句的子句C0開(kāi)始作歸結(jié)。歸

27、結(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é)原理C0C1C2C3C4C5空線性歸結(jié)策略示意圖精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理控制策略的方法控制策略的方法(5)單元?dú)w結(jié)策略 單元?dú)w結(jié)策略要求在歸結(jié)過(guò)程中，每次歸結(jié)都有一個(gè)子句是單元子句（只含一個(gè)文字的子句）或單元因子。顯而易見(jiàn)，此種方法可以簡(jiǎn)單地削去另一個(gè)非單子句中的一個(gè)因子，使其長(zhǎng)度減少

28、，構(gòu)成簡(jiǎn)單化，歸結(jié)效率較高。 初始子句集中沒(méi)有單元子句時(shí)，單元?dú)w結(jié)策略無(wú)效。所以說(shuō)“反之不成立”，即此問(wèn)題不能采用單元?dú)w結(jié)策略。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(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é)原理謂詞邏輯與

29、歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理 概述 命題邏輯 謂詞邏輯的歸結(jié)法 歸結(jié)過(guò)程的控制策略 Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理第三章謂詞邏輯與歸結(jié)原理 概述 命題邏輯 謂詞邏輯的歸結(jié)法 歸結(jié)過(guò)程的控制策略 Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbrand定理定理問(wèn)題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸

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

31、所給定的公式的確是永假的，就沒(méi)有這樣的解釋存在，并且算法在有限步內(nèi)停止。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbrand定理定理 H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbrand定理定理 H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（H H域）域） 基本方法： 因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是任意的

32、，所以解釋的個(gè)數(shù)是無(wú)限、不可數(shù)的 。 簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上，該公式是不可滿足的。 此域稱為H域。 ),.,(11niittfHH精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理D域H域H域與D域關(guān)系示意圖精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理H H域例題域例題設(shè)子句集S = P(x), Q(y,f(z,b),R(a)，求H域解：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

33、,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,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

34、(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 = H1H2H3精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（H H域）域） 幾個(gè)基本概念f（tn）：f為子句集S中的所有函數(shù)變量。t1, t2, tn為S的H域的元素。通過(guò)它們來(lái)討論永真性。 原子集A：謂詞套上H域的元素組成的集合。如A = 所有形如 P(t1, t2, tn)的元素即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，

35、因此，A也是可數(shù)的。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(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)題。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbran

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

37、章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（H H解釋）解釋） 如下三個(gè)定理保證了歸結(jié)法的正確性： 定理定理1：設(shè)I是S的論域D上的解釋，存在對(duì)應(yīng)于I的H解釋I*，使得若有S|I = T，必有 S|I* = T。 定理定理2 2：子句集S是不可滿足的，當(dāng)且僅當(dāng)所有的S的H解釋下為假。 定理定理3 3：子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（H H解釋）解釋） 基例S中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所

38、得的基子句C稱為C的一個(gè)基例。 若一個(gè)子句為假，則此解釋為假。 一般來(lái)說(shuō)，D是無(wú)窮不可列的，因此，子句集S也是無(wú)窮不可列的。但S確定后H是無(wú)窮可列的。不過(guò)在H上證明S的不可滿足性仍然是不可能的。 解決問(wèn)題的方法：語(yǔ)義樹(shù)精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbrand定理定理 H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbrand定理定理 H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理精選課件精選課件人工智能人工智能第三章

39、第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（語(yǔ)義樹(shù)）（語(yǔ)義樹(shù)） 構(gòu)成方法原子集中所有元素逐層添加的一棵二叉樹(shù)。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完） 。 特點(diǎn)一般情況H是無(wú)限可數(shù)集，S的語(yǔ)義樹(shù)是無(wú)限樹(shù)。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理N0P(a)N12Q(a)P(f(a)N24N31N38無(wú)限語(yǔ)義樹(shù)N11P(a)Q(a)Q(a)Q(a)P(f(a)N21SP(x)Q(x)，P(f(y)，Q(f(y) 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定

40、理（語(yǔ)義樹(shù)）（語(yǔ)義樹(shù)） 意義 S H A 語(yǔ)義樹(shù)可以理解語(yǔ)義樹(shù)為H域的圖形解釋。 目的：把每個(gè)解釋都攤開(kāi)。語(yǔ)義樹(shù)中包含原子集的全部元素。因此，語(yǔ)義樹(shù)是完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng)S的一個(gè)解釋。可以通過(guò)對(duì)語(yǔ)義樹(shù)每一個(gè)分支來(lái)計(jì)算S的真值。如果每個(gè)基例都為假，則可認(rèn)為是不可滿足的。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（語(yǔ)義樹(shù)）（語(yǔ)義樹(shù)） 幾個(gè)概念 失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某子句的某基例為假。但N以前尚不能判斷這個(gè)事實(shí)。就稱N為失敗結(jié)點(diǎn)。 封閉語(yǔ)義樹(shù)：如果S的完全語(yǔ)義樹(shù)的每個(gè)分枝上都有一個(gè)失敗

41、結(jié)點(diǎn)，就稱它是一棵封閉語(yǔ)義樹(shù)。精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理N0P(a)N1,2Q(a)P(f(a)N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,14封閉語(yǔ)義樹(shù)Q(f(a)SP(x)Q(x)，P(f(y)，Q(f(y) 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理HerbrandHerbrand定理定理 H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Her

42、brandHerbrand定理定理 H域 H解釋 語(yǔ)義樹(shù) 結(jié)論：Herbrand定理精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（結(jié)論）（結(jié)論）Herbrand定理：n 子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義數(shù)是棵有限封閉樹(shù)。 1. 子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。 精選課件精選課件人工智能人工智能第三章第三章 謂詞邏輯與歸結(jié)原理謂詞邏輯與歸結(jié)原理Herbrand定理定理（結(jié)論）（結(jié)論） 定理的意義 Herbrand定理已將證明問(wèn)題轉(zhuǎn)化成了命題邏輯問(wèn)題。 由此定理保證，可以放心的用機(jī)器來(lái)實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理） 注意 Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。但是 精選課件精選課件人工智能人工