第3章(搜索推理技術(shù)5-消解原理).pptx

1、人 工 智 能 Artificial Intelligence (AI),劉 靜 理工學院 2009年春季,第3章 搜索推理技術(shù),3.1 圖的搜索策略 3.2 盲目搜索 3.3 啟發(fā)式搜索 3.4 與或樹搜索（補充） 3.5 博弈樹搜索（補充） 3.6 消解原理,3.6 消解原理 3.6.1 子句集的求取 3.6.2 消解原理（補充） 3.6.3 消解推理規(guī)則 3.6.4 含有變量的消解式 3.6.5 消解反演求解過程 3.6.6 Horn子句集消解（補充） 3.6.7 Prolog 語言簡介 （補充）,3.6 消解原理,第2章中介紹： 謂詞邏輯的基本知識 合一算法（求最一般的一致置換或合一者

2、mgu） 本節(jié)： 消解原理（或者歸結(jié)原理）,3.6.1 子句集的求取 如何將謂詞公式轉(zhuǎn)化為子句集，作為合一算法的輸入（公式集） 3.6.1.1 若干基本概念 3.6.1.2 子句集的求取,3.6.1.1 若干基本概念 1 自由變元與約束變元 2 前束范式與前束合取范式 3 斯科倫（Skolem）范式 4 子句集,設(shè)，是一個謂詞公式，將量詞記作（即 或 ）,1 自由變元與約束變元,如果中包含部分公式 (x)，則中變元 x 的一切出現(xiàn)都稱為 x 在 中的約束出現(xiàn)，相應地稱 x 為約束變元（啞元、虛構(gòu)變量、約束變量）,約束變元,中不在任何量詞作用域內(nèi)的變元 x ，稱為變元 x 在 中的自由出現(xiàn)，相應

3、地稱 x 為自由變元（自由變量）,自由變元：,量詞的作用域（轄域）是直接跟在它后面的公式 如果有括號，則是括號里的公式 如果沒有括號，則是最短的完整公式,說明：,例1： x ( P(x) y (R(x, y) ) x , y 都是約束變元 例2： x ( P(x) (R(x, y) ) x 是約束變量，y 是自由變元,改名：將謂詞公式中一個變元名改成另一個變元名，但是要求改名后的公式與原公式意義相同（真假值相同） 原則：改成的新的變元名一定是量詞作用域中沒有出現(xiàn)過的變元名（包括約束變元和自由變元）,約束變元的改名或變量的標準化,例3： x ( P(x) (R(x, y) 除了 y 外，可以將

4、x 改成任何變元名 例4： x P(x) Q(y) 可以改成任何變元名，包括 y（建議不要用）,2 前束范式與前束合取范式,定義：設(shè)謂詞公式具有形式： (1x1)(nxn) M 其中：i ( i = 1 , , n ) 是 或 M 是不包含量詞的謂詞公式 則，稱是前束范式 稱 (1x1)(nxn ) 為前束 稱 M 為母式,定義：設(shè)謂詞公式是一個前束范式，如果的母式具有形式： （M11M12M1 n1） （M21M22M2 n2） (Mm1Mm2Mm nm） 其中，M i j 是原子公式或其非，則稱是前束合取范式。相應地有前束析取范式,前束范式： (x) (y) (z)(P(x)Q(y)R(z

5、) 前束合取范式（交換律、分配律，p.33） (x) (y) (z)(R(z)P(x)(R(z)Q(y),例：,3 斯柯倫范式,定義：前束中不含存在量詞的前束范式稱為斯柯倫范式,若xk (1kn )左邊沒有全稱量詞，則取不在母式中出現(xiàn)的常量替代母式中的所有 xk ，并刪除前束中的 xk,消去存在量詞的規(guī)則 或 前束范式化成斯柯倫的步驟是：,若 xk (1 kn )左邊有全稱量詞 (xs1) (xs2)(xsr) ( 1r，1s1s2srk) 則，取不在母式中出現(xiàn)的 r 階函數(shù) fr (xs1, xs2,xsr)替代母式中的所有xk ，并刪除前束中的 xk,反復使用上述兩條規(guī)則，消除前束中的所有

6、存在量詞，即得到斯柯倫范式 其中，引入的函數(shù)稱為斯柯倫函數(shù),x y z u v w A(x,y,z,u,v,w) (用a替代x，刪除x) = y z u v w A(a,y,z,u,v,w) （用f(y,z)代替u，刪除u） = y z v w A(a,y,z, f(y,z),v,w) （用h(y,z,v)代替w，刪除w） = y z v A(a,y,z, f(y,z),v,h(y,z,v),例：求斯柯倫范式,說明： 一個謂詞公式的斯科倫范式不是唯一的，盡可能將斯科倫函數(shù)取得簡單一點,化成前束范式 化成前束合取范式 化成斯科倫范式（斯科倫函數(shù)的變元較多）,對于謂詞公式：=12,正常的做法：,將

7、1、2 分別化成前束范式 對1、2 分別求出斯柯倫范式1、2 將12 的量詞左移得到的斯柯倫范式（即前束范式）,簡化的做法：,好處：簡化斯科倫函數(shù),=12, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = y1 x1 x2 y2 (P( x1 , y1 ) Q( x2 , y2 ) （前束合取范式） = x1 x2 (P( x1 , a1 ) Q( x2 , f(x1,x2) ),例：正?；? = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = x1 P( x1 , a1 ) x2 Q( x2 , f(x2) ) （先分別化

8、成斯科倫范式） = x1 x2 (P( x1 , a1 ) Q( x2 , f(x2) ) (前束合取范式）,簡化化法,4 子句集,原子命題是原子公式 如果t1,tn(n1)是項，P是謂詞，則P(t1,tn)是原子公式 其它表達式都不是原子公式,原子公式的定義：, 文字（或基本式）：“原子公式”或者“原子公式的非” 子句：一個或多個基本式的 析取,子句的定義：,一個謂詞公式具有形式： ( x1 )( xn )( c1c2cm ) 其中，ci ( i = 1, , m )為子句 x1, , xn 是子句中出現(xiàn)的約束變元 則，稱謂詞公式具有子句形式,子句形式的定義：,閉公式：不含自由變量的謂詞公式

9、 謂詞公式的子句形式是閉公式 母式為子句的合取范式 前束中只有全稱量詞，無存在量詞,說明：,若謂詞公式 具有子句形式，記 S = ( c1 , c2 , , cm ) 則，稱 S 為謂詞公式的子句集,( x1 )( xn )( c1c2cm ),子句集的定義：,為了便于消解推理，要通過改名使得一個變量符號不出現(xiàn)在一個以上的子句中，即每一個子句具有不同的變量,說明：,子句形式： (x) (y) (z)(R(z)P(x)(R(z)Q(y) 子句集： R(z)P(x) , R(z)Q(y) R(z1)P(x1) , R(z2)Q(y1) （改名）,例：,3.6.1.2 子句集的求取,子句集的求取（將

10、謂詞公式化成子句集）有兩種方法，其形式上會有差別，但是其邏輯意義是相同,1、將謂詞合適公式轉(zhuǎn)化為前束合取范式 消去“蘊含”和“等價”連結(jié)詞 將“”連結(jié)詞直接作用到原子公式前 約束變元改名，使所有的約束變元名都不相同 將量詞移到謂詞公式的左邊，得到前束范式 將前束范式化成前束合取范式,方法1（離散數(shù)學、數(shù)理邏輯采用的方法）：,2、將前束范式轉(zhuǎn)化為斯柯倫（Skolem）范式 得到斯科倫范式 3、將斯柯倫范式轉(zhuǎn)化為子句集 消去前束（全稱量詞） 消去合取連詞 變量改名，得到子句集,為了使斯科倫函數(shù)更簡單一些，可以將合取關(guān)系的各個謂詞公式分別先分成前束范式、斯科倫范式，再綜合起來化成前束范式、前束合取范

11、式（后面的定理證明部分就采用了這一種化法）,說明：, 消去“蘊含”和“等價”連結(jié)詞 減少“非”連結(jié)詞的轄域（將“”連結(jié)詞直接作用到原子公式前） 對變量標準化（約束變元改名）,方法2 （教材采用的方法）：,消去存在量詞（引入斯科倫函數(shù)） 化成前束范式 將母式化成合取范式 消去全稱量詞 消去合取連結(jié)詞 更改變量名，得到子句集,兩者的差別：在于三步 方法 1 是先得到前束合取范式，再化成斯科倫范式 方法 2 是先引入斯科倫函數(shù)消去存在量詞，再化成前束合取范式,三步的結(jié)果： 得到不含存在量詞的前束合取范式,謂詞公式 = 全稱量詞串 + 合取范式的母式,注：母式中的斯科倫函數(shù)變元個數(shù)可能不相同,求取子句

12、集的步驟(教材)：,使用的公式： AB = AB AB = (AB)(B A), 消去“蘊含”和“等價”連結(jié)詞,將“”連結(jié)詞直接作用到原子公式前，使得每一個“非”聯(lián)結(jié)詞最多只能作用于一個原子公式（謂詞符號）, 減少“非”連結(jié)詞的轄域,(A) A (AB) = AB (AB) = AB (x)A(x) = (x)(A(x) (x)A(x) = (x)(A(x),使用的公式是：,說明： 到現(xiàn)在為止，謂詞公式只包含三種連結(jié)詞 “合取”： “析取” “非” ,對約束變元改名，使得所有的約束變元名都不相同，保證每一個量詞都有自己唯一的約束變元, 對變量標準化,以一個斯科倫函數(shù)代替每一個帶存在量詞的約束變

13、元，斯科倫函數(shù)的變元是（左邊）帶全稱量詞的約束變元，而且這些全稱量詞的轄域必須包括被消去的存在量詞的轄域, 消去存在量詞,消去存在量詞的規(guī)則：,如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，則用常量來代替 斯科倫函數(shù)和常量的符號必須是未在謂詞公式出現(xiàn)過的符號, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = x1 P( x1 , a1 ) x2 Q( x2 , f(x2) ) （引入斯科倫函數(shù)，消去存在量詞， x1 的轄域不包含y2 的轄域）,例：,將全稱量詞移到謂詞公式的左邊，使得每一個量詞的轄域包括該量詞后面的整個謂詞公式, 化成前束范式,(x)A(

14、x)R = (x) (A(x)R) (x)A(x)R = (x) (A(x)R) (1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z) (1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z) 說明：A(x), B(z), R中允許含有與x，z不同的自由變量,使用的規(guī)則：,前束范式 （前束） （母式）,全稱量詞串,無量詞公式, 將母式化成合取范式,利用分配律將前束范式化成前束合取范式： P(QR) = (PQ)(PR) （析取 合?。?謂詞公式已經(jīng)化成了前束合取范式，且只包含全稱量詞，此時全稱量詞的次序也不重要了，所以可以消去全部量詞（即前束、前綴）,

15、消去全稱量詞, 消去合取連結(jié)詞 ,母式為合取范式： A1 A2 An 消去合取連結(jié)詞，得到子句集： A1 , A2, , An 子句：基本式（文字）的析取（只含）,更改變元名，使得一個變量符號不出現(xiàn)在一個以上的子句中，即不同的子句包含不同的約束變元名, 更換變元名,(x)A(x) (x)B(x) = (x)A(x)(x)B(x) （消去“蘊含”） = (x) (A(x)(x)B(x) （“非”直接作用謂詞符號） = ( x) (A(x) ) (z) B(z) (改名) = A(a)B(b) （消去存在量詞） 子句集= A(a)B(b) 注：兩種方法的結(jié)果相同,例1：,仔細分析量詞的轄域,(x)

16、 (y)( (z)(A(x,z)A(y,z) (u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z)(u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z) )(u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z) )B(x,y,f(x,y) = (x) (y) (z)(A(x,z)A(y,z) B(x,y,f(x,y),使用方法1，函數(shù)將為f(x,y,z),子句,例2：,(x)P(x)(y)Q(y) (x)R(x) =(x)P(x)(y)Q(y) (x)R(x) =(x)P(x)(y)Q(y) (x)R(x) =( (x)(P(

17、x)(y)(Q(y) (x)R(x) =( (x)(P(x)(y)(Q(y) (z)R(z) (改名),例3：, ( (P(a)(y)(Q(y) (z)R(z) （消去存在量詞） (y) (z)( P(a) Q(y) R(z) ) （化成前束范式） (y) (z)( (P(a) R(z)(Q(y) R(z) ) (化成前束合取范式) 子句集= P(a) R(z) , Q(y) R(x) ,兩者化法結(jié)果相同,=( (x)(P(x)(y)(Q(y) (z)R(z),例4：將謂詞公式化成子句集, 消去“蘊含”符號, “非”直接作用到謂詞符號, 約束變量改名,后面的 y 改成 w, 引入斯科倫函數(shù)消去

18、存在量詞,斯科倫函數(shù) w = g ( x ), 化成前束范式, 化成前束合取范式,分配律： P(QR) = (PQ)(PR),注：使用分配律兩次, 消去全稱量詞或者前束, 消去合取符號，得到子句, 變量改名，使得變量不相同，得到子句集,如果使用方法1，函數(shù)g將會有兩個變量g(x,y),設(shè)c1 , c2是兩個無公共變元的子句，令 c1= P(t11,t1n)P(tk1,tkn)c1 c2= P(t11,t1n)P(tm1,tmn)c2,3.6.2 消解原理,說明：謂詞符號相同，變元不同,消解式定義：,若 P(t11,t1n), , P(tk1,tkn), P(t11,t1n), , P(tm1,

19、tmn) 有最一般的合一者（或一致置換）（mgu）,說明：用合一算法求取mgu,則稱 c = ( c1 c2) 為c1 , c2的消解式 稱 P(t11,t1n), ., P(tk1,tkn), P(t11,t1n), , P(tm1,tmn) 為被消解式,設(shè)c1 , c2為無變量子句，c1=Lc1，c2=Lc2 其中 L 是基本式 則c = c1 c2 為c1 , c2 的消解式 當c1c2時，c= (空句子),對于子句中無變量的特殊情況（即命題情況）：,例1：c1=PQ，c2=PQ c1=P c2=P c = c 1 c 2= P （消解式）,L= Q,設(shè)c1 = P(x) Q(x), c

20、2 = P(a) R(y) P(x), P(a)的最一般的合一者為 a/x c1= Q(x) c2= R(y) 則c1, c2的消解式為 c=Q(a)R(y),例2：,設(shè)S是子句集，c是子句。若存在一個子句序列c1,cn滿足 cn = c 任意一個 ci 或者屬于 S 或者它前面的子句 ck, cl ( ik , il )的消解式,消解演繹和反演的定義：,則稱 c1, , cn 是從子句集 S 到子句 c 的一個消解演繹 當 c= 時的消解演繹稱為（消解）反演,把謂詞公式轉(zhuǎn)化為子句集S（所有子句的變量名不同） 如空子句成為子句集的子句，則算法結(jié)束 在子句集中選取兩個不同的可以消解的子句ci ,

21、 cj,注：子句的個數(shù)限制,反演的基本算法：,計算 ci , cj 的消解式 rij 把 rij 加到子句集中，形成新的子句集S 轉(zhuǎn)到,反演的流程圖,將謂詞公式化成子句集,有空子句？,成功結(jié)束,取兩個子句,有消解式？,無解結(jié)束,將消解式送到子句集,有,無,例1：設(shè)子句集為S= PQ, PQ, PQ, PQ 求S的一個反演,S的一個反演為：,PQ (S) PQ (S) PQ (S) PQ (S) Q Q ,P P ,S的另一個反演為：,例2：設(shè)S= P(z1,a)P(z1,x1)P(x1,z1), P(z2,f(z2)P(a, z2), P(f(z3),z3)P(a, z3) 求S的一個反演,

22、P(z1,a)P(z1,x1)P(x1,z1) （S） P(z2,f(z2)P(a ,z2) （S） P(f(z3),z3)P(a ,z3) （S）,S的一個反演為：, 取c1=，c1= P(z2,f(z2) 取c2=，c2= 公式集為： P(z1,a), P(z1,x1), P(x1,z1), P(a,z2) 最一般的合一者為=a/x1, a/z1, a/z2 對應的消解式：P(a, f(a), P(z1,a)P(z1,x1)P(x1,z1) P(z2,f(z2)P(a ,z2), 取c1=，c1= P(f(z3),z3) 取c2=，c2= 公式集為 P(z1,a), P(z1,x1), P

23、(x1,z1), P(a, z3) 最一般的合一者為=a/x1,a/z1,a/z3 對應的消解式為：P(f(a), a), P(z1,a)P(z1,x1)P(x1,z1) P(f(z3),z3)P(a ,z3),取c1=，c1= 取c2=，c2=P(z1,a)P(z1,x1) 公式集 P(x1,z1), P(a, f(a) 最一般的合一者為=a/x1,f(a)/z1 對應的消解式為：P(f(a),a), P(z1,a)P(z1,x1)P(x1,z1) P(a, f(a),取c1= ，c1= 取c2= ，c2= 公式集: P(f(a) , a) 最一般的合一者為= 對應的消解式為： , P(f(

24、a), a) P(f(a),a), P(z1,a)P(z1,x1)P(x1,z1) （S） P(z2,f(z2)P(a ,z2) （S） P(f(z3),z3)P(a ,z3) （S） P(a, f(a) ( ) P(f(a), a) ( ) P(f(a),a) ( ) ( ),反演過程：,3.6.3 消解推理規(guī)則 （命題的特殊情況）,從父子句求消解式的若干例子,1、假言推理,2、合并,3、重言式,4、空子句（矛盾）,5、鏈式（三段論）,3.6.4 含有變量的消解式（謂詞情況）,先求最一般的合一者mgu，再求消解式,例1,置換,例2,例3,1 消解反演（數(shù)學定理的證明，論斷是否成立，即反演）

25、2 反演求解過程（回答問題，即消解演繹）,3.6.5 消解反演求解過程,1 消解反演 消解反演證明定理的思路非常類似于數(shù)學中的反證法,給定一個公式集 S（前提條件）和目標公式 L（結(jié)論），通過反演來求證目標公式 L，其證明過程為： 否定 L ，得到 L 把 L 加到 S 中 把新形成的集合 S ， L 化為子句集（簡化化法） 應用消解原理，試圖導出一個表示矛盾的空子句,設(shè)SF1,Fn 是前提條件，L是欲求證的結(jié)論 則，從前提條件推出結(jié)論的問題，可以表示成： F1Fn L （F1Fn ）L 并證明其永真（永遠成立）,反演證明過程的正確性：,先將公式取“非” ： （F1Fn ）L） （F1Fn ）

26、 L F1Fn L 利用消解原理來證明它是永假的（即，構(gòu)造一個反演）,實際中，我們可以將 F1Fn L 中的每一個部分化成子句集（化法任選），合并后得到完整的子句集，然后利用消解原理導出空子句（反演）,設(shè)有公式集： F1: (x)(C(x)(W(x)R(x) F2: (x)(C(x)O(x) L: (x)(O(x)R(x) 試證：L是F1，F(xiàn)2的邏輯結(jié)果，即F1F2L,例1：,利用消解原理來構(gòu)造F1F2L的一個反演 首先分別求出F1，F(xiàn)2和 L 的子句集,證明：,(x)(C(x)(W(x)R(x) = (x)(C(x)(W(x)R(x) = (x)(C(x)W(x) )(C(x)R(x) 子句

27、集= C(x)W(x) , C(x)R(x) (未改名),F1的前束合取范式與子句集：,(x)(C(x)O(x) = (C(a)O(a) 子句集= C(a), O(a) ,F2的前束合取范式和子句集：,(x)(O(x)R(x) = (x)(O(x)R(x) 子句集=O(x)R(x),L 的前束范式和子句集：,構(gòu)成子句集（注意改名） C(x)W(x), C(y)R(y), C(a)， O(a), O(z)R(z) , C(x)W(x) C(y)R(y) C(a) O(a) O(z)R(z),證明過程：, R(a) ，mgu=a/y R(a) mgu=a/z , C(y)R(y) C(a), O(

28、a) O(z)R(z),前提：每一個儲蓄錢的人都獲得利息 結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢,例2：用消解反演證明,S ( x , y )：某人 x 儲蓄 y（數(shù)量） M ( x )：x（數(shù)量） 是錢 I( x )：x （數(shù)量）是利息 E( x , y )：某人 x 獲得 y （數(shù)量）,證明： 設(shè),前提：每一個儲蓄錢的人都獲得利息,結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢,任何人 x 將 y 數(shù)量的錢存入銀行,任何人 x 得到 y 數(shù)量的利息,沒有 x 數(shù)量的利息,任何人 x 就不會將任何數(shù)量 y 的錢存入銀行,將前提條件化成子句集,前束范式,前束合取范式,前提條件的子句集,結(jié)論取非：,

29、化成子句集,改名、消除,“結(jié)論非”的子句集,完整的子句集,反演過程,儲蓄問題的反演樹（簡單情況下使用）,2 反演求解過程,從反演樹求取某一個問題的答案，其過程為： 將前提條件用謂詞表示出來，并化成子句集 S,將目標公式（問題）用謂詞表示出來，把由目標公式的否定所產(chǎn)生的子句及其非（目標公式否定之否定）用析取連接詞相連組成一個新子句（重言式），加到 S 構(gòu)成新的子句集 S,對子句集 S ，進行消解演繹，直到得到某一個子句為止 將此子句作為問題的答案,例： 已知三個前提條件 F1:：王(Wang)先生是小李(Li)的老師 F2：小李與小張(Zhang)是同班同學 F3：如果x與y是同班同學，則x的老

30、師就是y的老師 問題：小張的老師是誰？,解： 定義謂詞 T(x , y) : x 是 y 的老師 C(x , y) : x 與 y 是同班同學,前提： F1：T(Wang , Li) F2：C(Li , Zhang) F3： (x) (y) (z) (C(x,y)T(z,x) T(z,y) 目標： G： (x)T(x,Zhang) G： (x)T(x,Zhang)=(x) ( T(x,Zhang),用謂詞表示前提條件與目標（問題）：,前提的子句集： (1) T(Wang, Li) (2) C(Li, Zhang) (3) C(x,y) T(z,x) T(z,y) 目標的否定的子句及其非組成重言

31、式： (4) T(x,Zhang) T(x,Zhang),完整的子句集： (1) T(Wang, Li) (2) C(Li, Zhang) (3) C(x,y) T(z,x) T(z,y) (4) T(u,Zhang) T(u,Zhang),(1) T(Wang, Li) (2) C(Li, Zhang) (3) C(x,y) T(z,x) T(z,y) (4) T(u,Zhang) T(u,Zhang) (5) C(Li ,y) T(Wang,y) (1)(3) mgu=Wang/z, Li/x),消解演繹過程,(6) C(Li ,Zhang) T(Wang, Zhang) (4)(5) mgu=Wang/u, Zhang/y (7) T(Wang, Zhang) (6)(2),問題的答案,(4) T(u,Zhang) T(u,Zhang) (5) C(Li ,y) T(Wang,y),(2) C(Li, Zhang),mgu= ,例：如果無論約