AI05-4歸結推理.ppt

1、第5章 知識與推理,5.5.1 子句集 5.5.2 命題邏輯的歸結原理 5.5.3 替換與合一 5.5.4 謂詞邏輯的歸結原理 5.5.5 歸結策略,第5章 知識與推理,5.5.1 子句集 謂詞邏輯有量詞、變量和函數(shù)，轉換步驟： 前束范式 Skolem標準形,第5章 知識與推理,子句集 文字 不含任何連接詞的謂詞公式 原子謂詞公式及其否定 子句 一些文字的析?。ㄖ^詞的和） 空子句 不含任何文字的子句 /NIL 子句集 所有子句的集合,第5章 知識與推理,例子 子句集 P(a，x，f(x)， Q(g(x)，b)， R(x) Q(y，b)R(x)， P(x) 非子句集 P(a，x，y)Q(y，b)

2、， P(x) P(x，y)P(y，z)， Q(x, z),第5章 知識與推理,例子 子句集 P(a，x，f(x)， Q(g(x)，b)， R(x) Q(y，b)R(x)， P(x) 非子句集 P(a，x，y)Q(y，b)， P(x) P(x，y)P(y，z)， Q(x, z),第5章 知識與推理,前束范式 如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端 (Q1x1)(Q2x2)(Qnxn) P(x1,x2,xn) A是一個前束范式 任何謂詞公式P的前束范式都是存在的 前束范式是不唯一的 可利用換名規(guī)則和替代規(guī)則求前束范式 指導變量應互不相同 原公式的自

3、由變量在前束范式中還是自由變量 原公式的約束變量在前束范式中還是約束變量,第5章 知識與推理,例子 (xP(x,y)yQ(y)xR(x,y) (xP(x,z)yQ(y)xR(x,z)替換原則 (xP(x, z)yQ(y)tR(t,z)換名原則 x(P(x, z)yQ(y)tR(t,z)量詞轄域收縮與擴張 xy(P(x,z)Q(y)tR(t,z)量詞轄域收縮與擴張 xy(P(x,z)Q(y)tR(t,z)量詞轄域收縮與擴張 xyt(P(x,z)Q(y)R(t,z)量詞轄域收縮與擴張,第5章 知識與推理,Skolem標準形 前束范式中消去所有的存在量詞 任何一個謂詞公式都有與之對應的Skolem標

4、準形 Skolem標準形不唯一 算法 依據(jù)約束變量換名規(guī)則，把公式變型為前束范式 依照量詞消去原則，消去或略去所有量詞 Skolem標準型滿足合取范式,第5章 知識與推理,量詞消去原則 消去存在量詞“ ” 如果左邊沒有任何全稱量詞，則只將其改寫成為常量(a, b等)，該常量稱為skolem常量 如果左邊有全稱量詞，消去時該變量改寫成為任意量詞的函數(shù)(f(x), g(y)等)，該函數(shù)稱為skolem函數(shù) 消去全稱量詞 “ 簡單地省略掉該量詞 例子 (x)(y)P(x，y)可以表示為“每一個人x都有自己的y年齡”，則年齡y與人x有關，可用一個函數(shù)f(x)描述這種依賴關系， f(x)把每一個x值映射

5、為存在的y值； (x)(y)P(x，y) (x)P(x，f(x) (y) P(y) P(a),第5章 知識與推理,定理 公式G的Skolem標準形同G并不等值 例子 謂詞公式G=(x)P(x) Skolem標準型為：G=P(a) 解釋I： 個體域D=0,1 常數(shù)a=0 謂詞P(0)=F, P(1)=T 在解釋I下： G=T， G=F,第5章 知識與推理,例子 (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

6、, y)(x)(y)Q(y,b)R(x) 縮小否定詞作用范圍 =(x)(y)P(a, x, y)(z)(t)Q(t,b)R(z) 換名原則 =(x)P(a, x, f(x)(z)(Q(g(z),b)R(z) 消去原則 =(x)(z)(P(a, x, f(x)Q(g(z),b)R(z) 前束范式 = P(a, x, f(x)Q(g(z),b)R(z) Skolem,第5章 知識與推理,子句集S求取 謂詞公式G轉換成前束范式 消去前束范式中的存在變量，略去其中的任意變量，生成Skolem標準形 將Skolem標準形中的各個子句提出，表示為集合形式 例子 Skolem: P(a,x,f(x)Q(g(

7、x),b)R(x) 子句集S：P(a,x,f(x), Q(g(x),b), R(x),第5章 知識與推理,子句集S求取 算法 消去蘊含詞和等值詞 縮小否定詞的作用范圍，直到其僅作用于原子公式 換名/替換原則，使量詞不含同名指導變元和約束變元 消去存在量詞 消去所有全稱量詞 化公式為合取范式 消去合取詞，以子句為元素組成集合S,第5章 知識與推理,例子1 (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

8、)(x)(y)Q(y,b)R(x) 縮小否定詞作用范圍 =(x)(y)P(a, x, y)(z)(t)Q(t,b)R(z) 換名原則 =(x)P(a, x, f(x)(z)(Q(g(z),b)R(z) 消去原則 =(x)(z)(P(a, x, f(x)Q(g(z),b)R(z) 前束范式 = P(a, x, f(x)Q(g(z),b)R(z) Skolem = S=P(a, x, f(x),Q(g(z),b),R(z)子句集S,第5章 知識與推理,例子2 xyP(x,y)yQ(x,y)R(x,y) = xyP(x,y)yQ(x,y)R(x,y) 消去 = xyP(x,y)yQ(x,y) R(x

9、,y) 縮小否定詞作用范圍 = xyP(x,y)zQ(x,z) R(x,z) 換名原則 = xP(x,f(x)Q(x,g(x) R(x,g(x) 消去原則 = P(x,f(x)Q(x,g(x) R(x,g(x)消去原則 = P(x,f(x)Q(x,g(x)P(x,f(x)R(x,g(x) Skolem = S=P(x,f(x)Q(x,g(x), P(x,f(x)R(x,g(x)子句集S,第5章 知識與推理,例子3 xyzuvw(P(x,y,z)Q(u,v,w) wf(y,z,v) u g(y,z) xa Skolem: P(a,y,z)Q(g(y,z),v,f(y,z,v) S:P(a,y,z

10、),Q(g(y,z),v,f(y,z,v),第5章 知識與推理,子句集與謂詞公式的不可滿足性 歸結原理將謂詞公式的正確性證明問題轉化為謂詞公式的不可滿足性問題的證明 可以通過一個謂詞公式的子句集來判斷該公式的不可滿足性,第5章 知識與推理,定理 謂詞公式G是不可滿足當且僅當其子句集S是不可滿足 公式G與其子句集S并不等值，但它們在不可滿足的意義下是一致的 證明命題A1A2A3B，只需證明G= A1A2A3B的子句集是不可滿足的，這也正是引入子句集的目的 公式G和子句集S之間邏輯關系 G真不一定S真 S真必有G真，即，S = G 在生成SKOLEM標準形時將存在量詞用常量或其他變量的函數(shù)代替，使

11、得變量討論的論域發(fā)生了變化，即論域變小了。所以G不能保證S真 子句集S是不可滿足的，當且僅當其全部子句的合取式是不可滿足的,第5章 知識與推理,定理推廣 謂詞公式G，G = G1 G2 G3 Gn G子句集SG，Gi的子句集為Si S= S1 S2 S3 Sn 雖然G的子句集不為S，但是可以證明SG與S在不可滿足的意義上是一致的,即SG不可滿足 S不可滿足 G的子句集的求取過程可以分解成幾個部分單獨處理,第5章 知識與推理,例子 對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？用一階邏輯表示這個問題，并建立子句集 解：

12、 首先引入謂詞：F(x, y) 表示x是y的父親G(x, y) 表示x是y的祖父ANS(x) 表示問題的解答 如果y是x的父親，z又是y的父親，則z是x的祖父 A1：(x)(y)(z)(F(x, y)F(y, z)G(x, z) A1化為合取范式，求Skolem標準形：SA1：F(x ,y)F(y, z)G(x, z),第5章 知識與推理,每個人都有父親 A2：( x)( y)F(x, y) Skolem標準形：SA2：F(x, f(x) ) 結論：某個人是它的祖父 B：(x)(y)G(x, y) 否定后得到子句：SB：G(x, y)ANS(x) 子句集： S A1，S A2，SB =F(x

13、,y)F(y, z)G(x, z)， F(x, f(x) )， G(x, y)ANS(x),第5章 知識與推理,5.5.2 命題邏輯中的歸結原理 歸結演繹推理是基于一種稱為歸結原理(亦稱消解原理principle of resolution)的推理規(guī)則的推理方法 歸結原理是由魯濱遜(J.A.Robinson)于1965年首先提出 它是謂詞邏輯中一個相當有效的機械化推理方法 歸結原理的出現(xiàn)，被認為是自動推理，特別是定理機器證明領域的重大突破,第5章 知識與推理,歸結式 設C1和C2是子句集中的任意兩個子句 如果C1中的文字L1與C2中的文字L2互補 可從C1和C2中分別消去L1和L2，并將C1和

14、C2中余下的部分按析取關系構成一個新子句C12 C12為C1和C2的歸結式，C1和C2為C12的親本子句 例子 子句：C1 PQR ， C2= QS 存在互補對 Q和Q 歸結式：C12 = PRS,第5章 知識與推理,定理 歸結式是其親本子句的邏輯結果 證明：設C1=LC1, C2=LC2 C1 = LC1 = C1L C2 = LC2 = LC2 C1C2= (C1L) (LC2) = C1C2= C1C2,第5章 知識與推理,定理 歸結式是其親本子句的邏輯結果 由定理即得推理規(guī)則： C1C2 (C1-L1)(C2-L2) C1,C2是兩個子句 L1,L2分別是C1,C2中的文字，且L1,L

15、2互補 此規(guī)則即命題邏輯中的歸結原理,第5章 知識與推理,例子 用歸結原理驗證分離規(guī)則和拒取式 A(AB) B (AB) B A 解： A(AB)A(AB) = B (AB)B(AB)(B)= A,第5章 知識與推理,推論 設C1、C2是子句集S的兩個字句，C12是它們的歸結式 若用C12代替C1、C2 ，得到新子句集S1，則 S1不可滿足 = S不可滿足 若把C12加入到S中，得到新子句集S2，則 S2不可滿足 = S不可滿足,第5章 知識與推理,例子 證明子句集 PQ,P,Q 是不可滿足的 證明： PQ P Q Q 由(1),(2) 由(3),(4),第5章 知識與推理,例子 用歸結原理證

16、明R是P,(PQ)R,(SU)Q,U的邏輯結果 證明： 將證明公式轉化為命題公式 P (PQ)R) (SU)Q) U R 合取范式 P(PQR)(SQ)(UQ) U R 子句集S S=P,PQR,SQ,UQ,U,R 歸結,第5章 知識與推理,推出空子句，所以子句集S不滿足 原命題公式P (PQ)R) (SU)Q) U R不滿足 原命題得證,歸結樹,第5章 知識與推理,5.5.3 替換與合一 謂詞邏輯公式中含有個體變量與函數(shù)。因此，尋找互補子句的過程比較復雜： P(x )Q(y) 與 P(a)Q(z) 不易從直接比較中發(fā)現(xiàn)這兩個子句中含有互補對 將x取a值，則很顯然這兩個子句為互補對 替換/置換

17、,第5章 知識與推理,置換 在一個謂詞公式中用置換項去置換變量 置換是形如t1/x1, t2/x2, , tn/xn的有限集合 x1, x2, , xn是互不相同的變量，即置換變量 t1, t2, , tn是不同于xi的項（常量、變量、函數(shù)），即置換項 ti/xi 用ti置換xi ti與xi不能相同 xi不能循環(huán)出現(xiàn)在另一個ti中。,第5章 知識與推理,作用 將某些變量用另外的變量、常量或函數(shù)取代，使其不在公式中出現(xiàn) 置換對所有變量進行操作 例子 a/x，c/y，f(b)/z 置換 a/x, c/y, f(x)/z 置換 a/x, f(y)/y, f(x)/z 不是置換 g(y)/x，f(x)

18、/y 不是置換,第5章 知識與推理,例(instance) 設=t1/x1,tn/xn是一個替換，E是一個表達式 對E施行替換，即把E中出現(xiàn)的個體變元xj(1jn)都用tj替換，記為E 所得的結果稱為E在下的例(instance) 例子 =a/x,f(b)/y,c/z G=P(x,y,z) G= P(a,f(b),c),第5章 知識與推理,置換合成 設t1/x1, t2/x2, , tn/xn，u1/y1, u2/y2, , un/yn 則與的合成也是一個置換，記作 算法 集合t1/x1,t2/x2,tn/xn, u1/y1, u2/y2, un/yn即對ti先做置換，然后再做置換，置換xi

19、刪去以下元素： 當tixi時，刪去ti/xi (i = 1, 2, , n); 當yix1,x2, , xn時，刪去uj/yj (j = 1, 2, , m) 最后剩下的元素所構成的集合,第5章 知識與推理,例子 設f(y)/x, z/y，a/x, b/y, y/z，求與的合成 解： 先求出集合 f(b/y)/x, (y/z)/y, a/x, b/y, y/z =f(b)/x, y/y, a/x, b/y, y/z 在該集合中 y/y滿足條件1，刪除 a/x，a/y滿足條件2，刪除 最后得=f(b)/x，y/z,第5章 知識與推理,合一 尋找相對變量的置換，使兩個謂詞公式一致 設有公式集SF1

20、，F(xiàn)2，F(xiàn)n，若存在一個置換，可使F1F2= Fn，則稱是F的一個合一。同時稱F1，F(xiàn)2，. ，F(xiàn)n是可合一的 一般說來，一個公式集的合一不是唯一的,第5章 知識與推理,例子 公式集SP(x, y, f(y), P(a,g(x),z) 置換a/x, g(a)/y, f(g(a)/z F1=F2=P(a, g(a), f(g(a) 是F的一個合一,第5章 知識與推理,最一般合一 設是公式集S的一個合一 如果對S的任意一個合一都存在一個置換，使得 是一個最一般合一（Most General Unifier，mgu） 一個公式集的最一般合一是不唯一的,第5章 知識與推理,算法 令k=0，Sk=S，k

21、=(代表空置換) 若Sk只含有一個表達式，則算法停止，k是mgu 找出Sk的差異集Dk 若Dk中存在元素xk 和tk ，其中xk是變元， tk是項，且xk不在tk中出現(xiàn)，則 k1= k tk / xk Fk1= Fk tk / xk k=k+1 轉step2; 若不存在變元xk或項tk ，則轉step5 算法終止，F(xiàn)的mgu不存在,第5章 知識與推理,差異集 將兩個謂詞公式的項從左到右進行比較，那些不相同的項所構成的集合 例子： 設公式集F1，F(xiàn)2中有公式F1=P(x，y，z)和F1=P(x，f(a)，h(b)，求差異集。 解： 比較兩個公式的第一個元素，相同 比較第二個元素，不同，構成差異集

22、： D1=y， f(a) 比較第二個元素，不同，構成差異集： D2=z， h(b),第5章 知識與推理,例子 設S= P(f(x)，y)，P(y，f(b)，求mgu 解： 令0 =, S0=S, k=0 差異集：D0=f(x)，y 1=0 f(x)/ y=f(x)/ y S1=S0 f(x)/ y=P(f(x)， f(x)，P(f(x)，f(b) k=1 差異集： D1=x，b 2=1 b/x=f(b)/y，b/x S2=S1 b/x=P(f(b)， f(b)，P(f(b)，f(b) =P(f(b)， f(b) 所以，公式集是可合一的，mgu=2=f(b)/ y，b/x,第5章 知識與推理,例

23、子 設S= P(x，x)，P(y，f(y)，求mgu 解： 令0 =, S0=S, k=0 差異集：D0=x，y 1=0 x/y=x/y S1=S0 x/y=P(x，x)，P(x，f(x) k=1 差異集： D1=f(x)，x 由于變元x在項f(x)中出現(xiàn)，不存在置換，算法結束 所以，公式集是不可合一的,第5章 知識與推理,5.5.4謂詞邏輯中的歸結原理 歸結原理需將謂詞公式轉化為子句集 由于謂詞邏輯與命題邏輯不同，有量詞、變量和函數(shù)，所以在生成子句集之前要對邏輯公式做處理：Skolem標準型 歸結原理方法與命題邏輯基本相同。但由于有變量與函數(shù)，所以要考慮合一和置換,第5章 知識與推理,歸結式

24、 設C1，C2是兩個無公共變量的子句 L1，L2分別是C1，C2的文字 如果L1，L2有mgu,則(C1-L1)(C2-L2)稱作子句C1、C2的一個二元歸結式，而L1，L2為被歸結的文字,第5章 知識與推理,例子1 設C1=P(x)Q(x),C2=P(a)R(y)，求C1,C2的歸結式 解： 取L1=P(x),L2=P(a),則L1與L2的mgu=a/x (C1-L1)(C2-L2) =(P(a),Q(a)-P(a) (P(a),R(y)-P(a) =Q(a),R(y) = Q(a)R(y) 所以，Q(a)R(y)是C1和C2的二元歸結式,第5章 知識與推理,例子2 設C1=P(x,y)Q(

25、a),C2=Q(x)R(y),求C1,C2的歸結式 解： 由于C1、C2中含有公共變量x，y，所以歸結前進行改名 C1=P(x,y)Q(a),C2=Q(s)R(t) 取L1= Q(a),L2=Q(s),則L1與L2的mgu=a/s 歸結式為 P(x,y)R(t),第5章 知識與推理,注意事項 謂詞的一致性 P()與Q()， 不可以歸結 常量的一致性 P(a, )與P(b,.)， 不可以歸結 P(a, .)與P(x, )， 可以歸結 變量與函數(shù) P(a, x, .)與P(x, f(x), )，不可以歸結 P(x, x, )與P(x, f(y), )，可以歸結 不能同時消去兩個互補對 PQ與PQ歸

26、結為空，是不正確的 對內部可合一的子句先進行簡化，再進行置換合一,因子 如果子句C中，兩個或兩個以上的文字有一個最一般合一，則C稱為C的因子 如果C是單元子句，則C稱為C的單因子 子句C1,C2的歸結式 C1和C2的二元歸結式 C1和C2的因子的二元歸結式 C1的因子和C2的二元歸結式 C1的因子和C2的因子的二元歸結式,第5章 知識與推理,例子3 P(x)Q(x，y) 與P(a)R(b，z) 的歸結式為 Q(a，y) R(b，z) P(x，y)Q(x)R(x)與P(a，z)Q(b)的歸結式為 Q(a)R(a)Q(b) 或 P(b，y) R(b) P(a，z),第5章 知識與推理,例子4 設C

27、1=P(x)P(f(a)Q(x)，C2=P(y)R(b), 求C1,C2的歸結式 解： 對C1進行簡化，取置換=f(a)/x,即P(x),P(f(a)的最一般合一，則得 C1= P(f(a)Q(f(a) 對C1、C2歸結，得： Q(f(a)R(b),第5章 知識與推理,例子5 設C1P(y)P(f(x)Q(g(x)，C2P(f(g(a)Q(b)，求C1和C2的歸結式 解： 對C1，取最一般合一=f(x)/y，得C1的因子C1P(f(x)Q(g(x) 對C1和C2進行歸結g(a)/x，可歸結式：Q(g(g(a)Q(b),第5章 知識與推理,定理 謂詞邏輯中的消解式是它的親本子句的邏輯結果 謂詞邏

28、輯中的推理規(guī)則： C1C2(C1-L1)(C2-L2) C1,C2是兩個無相同變元的子句 L1,L2分別是C1,C2中的文字 為L1與L2的最一般合一。 此規(guī)則稱為謂詞邏輯中的消解原理（或歸結原理）,第5章 知識與推理,定理 如果子句集S是不可滿足的，那么必存在一個由S推出空子句的歸結序列 稱為歸結原理的完備性定理,第5章 知識與推理,歸結過程 謂詞邏輯 vs 命題邏輯 基本步驟相同 每步的處理對象不同 謂詞邏輯 謂詞公式集化為子句集 歸結前進行置換和合一,第5章 知識與推理,歸結步驟 寫出謂詞關系公式 用反演法寫出謂詞表達式 化為SKOLEM標準形 變量換名，字句間無同名變量，求取子句集S

29、對S中可歸結的子句做歸結 歸結式仍放入S中，反復歸結過程 得到空子句 命題得證,第5章 知識與推理,例子1 求證G是A1和A2的邏輯結果 A1: x(P(x)(Q(x)R(x) A2: x(P(x)S(x) G: x(S(x)R(x) 證明： 用反證法，即證明A1A2G不可滿足 求子句集S 對A1， P(x)Q(x)， P(y)R(y) 對A2， P(a)， S(a) 對G，S(z)R(z),G=x(s(x)R(x),第5章 知識與推理,歸結 P(x)Q(x) P(y)R(y) P(a) S(a) S(z)R(z) R(a)2,3 a/y R(a)4,5 a/z 6,7 子句集不滿足，從而原命

30、題得證,第5章 知識與推理,例子2 設已知 能閱讀者是識字的 海豚不識字 有些海豚是很聰明的 試證明：有些聰明者并不能閱讀 證明： 定義謂詞 R(x)：x能閱讀 L(x)：x識字 I(x)：x是聰明的 D(x)：x是海豚,第5章 知識與推理,謂詞公式 x(R(x)L(x) x(D(x) L(x) x(D(x)I(x) x(I(x)R(x) 子句集 R(x)L(x) D(y) L(y) D(a) I(a) I(z)R(z),第5章 知識與推理,歸結 R(x)L(x) D(y) L(y) D(a) I(a) I(z)R(z) R(a)4,5 a/z L(a)1,6 a/x D(a)2,7 a/y

31、3,8 子句集不滿足，從而原命題得證,第5章 知識與推理,例子3 假設任何通過計算機考試并獲獎的人都是快樂的 任何肯學習或幸運的人都可以通過所有的考試 張不肯學習但他是幸運的 任何幸運的人都能獲獎 求證：張是快樂的,第5章 知識與推理,解： 定義謂詞 Pass(x,y): x通過y考試 Win(x,y): x獲得y Study(x): x肯學習 Lucky(x): x是幸運的 Happy(x): x是快樂的,第5章 知識與推理,將問題用謂詞公式表示 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),第5章 知識與推理,謂詞公式轉化為Skolem標準形,求取子句集 由R1及轉換公式:PWH =(PW) H，可得 (1) Pass