人工智能導(dǎo)論課件：第四章 謂詞邏輯與歸結(jié)原理

1、1,第四章 謂詞邏輯與歸結(jié)原理,2,命題邏輯 經(jīng)典邏輯 邏輯 謂詞邏輯 缺省邏輯 非經(jīng)典邏輯 非單調(diào)邏輯 模糊邏輯等等 歸結(jié)原理是一種主要基于謂詞邏輯知識表示的推理方法。,3,謂詞邏輯,命題邏輯有一定的局限性. 例如: 不能表達(dá)這樣的事實”當(dāng)移動木塊B時,說它就是on_B_C所斷言的木塊C上的木塊. 命題演算中,原子是沒有內(nèi)部結(jié)構(gòu)的串. 而謂詞演算提供了這種能力,例如, 不再讓一個命題符號P表示整個句子”星期二下雨了”,而是創(chuàng)建一個謂詞Weather來描述日期和天氣的關(guān)系.,4,一階謂詞邏輯的語法,一階謂詞邏輯的符號組成 常量, 變量,函數(shù)符號,謂詞符號, 聯(lián)結(jié)詞: , , , , 量詞: ,

2、 分隔符號: 逗號,括號 項的定義: 1) 常量,變量是項 2) 若f是n元函數(shù),t1,tn是項,則 f(t1,tn)是項,5,合式公式,合式公式(wff)的定義: 1) 若p是n元謂詞, t1,tn是項, 則 p(t1,tn)是合式公式. (稱為原子) 2) 若F ,G是合式公式,則F, FG, FG, FG, FG 都是合式公式. 3) 若X是一個變量,F是合式公式,則xF, xF 也是合式公式. 舉例: xp(X)y(p(Y)q(Y,X,f(a)）,6,謂詞邏輯,是一種形式語言，具有嚴(yán)密的理論體系 是一種常用的知識表示方法, 例： City（北京） City（上海） Age（張三，23）

3、 (X)(Y)(Z)(father(X, Y)father(Y, Z)gf(X, Z),7,歸結(jié)原理,歸結(jié)原理是一種定理證明方法，1965年由J.A.Robinson提出，從理論上解決了定理證明問題。當(dāng)時被認(rèn)為是人工智能領(lǐng)域的重大突破。 該方法簡單，易實現(xiàn)，因此一經(jīng)提出，就得到了人們的廣泛關(guān)注，對機器定理證明的研究起到了很大的推動作用。 但歸結(jié)原理也不是無所不能, 例如:“連續(xù)函數(shù)之和仍連續(xù)”是微積分中的簡單事實,可用歸結(jié)原理證明時,推了十萬步(歸結(jié)出幾十萬個子句)仍無結(jié)果.,8,子句,歸結(jié)原理是在謂詞邏輯公式的子句集合上進行歸結(jié)的。 定義:子句是如下形式的合式公式(wff): (L1 Ls

4、) 每個Li是文字(原子或原子的非),9,子句集,不包含任何文字的子句稱為空子句。 子句集：所有子句的合取，且每個合取子句不包括相同的變量。 I(z)R(z), I(A), R(x) L(x), D(y) 例如： I(z)R(z), I(A), (R(x)L(x), D(y) 不是子句集。,10,一般的wff與子句之間的關(guān)系？,任一合式公式都可以轉(zhuǎn)化成子句集,11,化子句集的方法,舉例說明 例：x( p(X)y(p(Y) q(Y,X,f(a) x(p(X)y (p(Y)q(Y,X,f(a) （1） 去掉蘊涵 理論根據(jù)：ab a b x(p(X)y(q(Y,X,f(a)p(Y) x(p(X)y(

5、q(Y,X,f(a)p(Y),12,(2) 移動否定符，將內(nèi)移到原子公式前: 理論根據(jù)：(a b) a b (a b) a b (x)P(x) (x)P(x) (x)P(x) (x)P(x) x (p(X)y(q(Y,X,f(a) p(Y) x( p(X) y(q(Y,X,f(a) p(Y) (3) 變量標(biāo)準(zhǔn)化，將各約束變量換名, 以避免混淆，即：不同的 約束，對應(yīng)于不同的變量 (x)A(x) (x)B(x) (x)A(x) (y)B(y) x(p(X)y(q(Y,X,f(a) p(Y) u (p(U) v(q(V,U,f(a) p(V),化子句集的方法（續(xù)）,13,化子句集的方法（續(xù)）,去掉

6、 (skolem變換) 原式為：x(p(X)y(q(Y,X,f(a) p(Y) u (p(U) v(q(V,U,f(a) p(V) 去掉后： (p(c)y(q(Y,c,f(a) p(Y) u ( p(U) (q(h(U),U,f(a) p(h(U) (5) 將全稱量詞提到最前面: 所用公式：(ByA(X)y(BA(X) y u (p(c)(q(Y,c,f(a) p(Y) (p(U) (q(h(U),U,f(a) p(h(U),skolem變換: 將謂詞公式中所有存在量詞消去,得到該謂詞公式的skolem標(biāo)準(zhǔn)型. 在消去存在量詞時, 有兩種情況: a. 存在量詞不在任何全稱量詞的轄域內(nèi), 例如:

7、 x (X) 變?yōu)?c), (注: c必須是一個新的常量,稱為skolem常數(shù),不能在原來的中) b. 存在量詞在某些全稱量詞的轄域內(nèi), 例如: xy height(X,Y)(公式中X依賴于Y) 變?yōu)?x height (X, h(X)） 這里h(X)稱為Skolem函數(shù).,略去全稱量詞為: (p(c)(q(Y,c,f(a) p(Y) ( p(U) (q(h(U),U,f(a) p(h(U) (6) 將上式化為合取范式 (p(c)(q(Y,c,f(a) p(Y) ( p(U)(q(h(U),U,f(a)( p(U) p(h(U) （7）表示為子句的形式 p(c)，q(Y,c,f(a) p(Y)

8、，p(U) q(h(U),U,f(a)， p(U) p(h(U) 注意：轉(zhuǎn)化，保證不可滿足性,16,說明：,轉(zhuǎn)化不意味著等價性,但可保證其保持“不可滿足性”. 一個合式公式或者一個子句集“不可滿足”, 是指在任何解釋下都有矛盾. 原式有矛盾，變換后的式子也有矛盾。,17,第11次課 11月28日,18,上次課程回顧,一階謂詞邏輯 子句，子句集 任一合式公式都可以轉(zhuǎn)化成子句集, 不等價，但滿足“不可滿足性”,19,練習(xí),求下面合式公式的子句集 x(yp(X,Y)y(q(X,Y)r(X,Y) 注: 按下面的步驟: 去掉蘊涵 將內(nèi)移到原子公式前: 將各約束變量換名, 以避免混淆 去掉 (skolem

9、變換) 將全稱量詞提到最前面: 化為合取范式 化為子句集的形式,20,作業(yè)解答,求下面合式公式的子句集 x(yp(X,Y)y(q(X,Y)r(X,Y) 解答： 1)(去蘊涵)x(yp(X,Y)y(q(X,Y)r(X,Y) 2)(移否定)x(yp(X,Y) y(q(X,Y)r(X,Y) x(yp(X,Y) y (q(X,Y)r(X,Y) 3）(換名)x(yp(X,Y) z (q(X,Z)r(X,Z),21,定理,定理： 一個合式公式不可滿足,當(dāng)且僅當(dāng)它所轉(zhuǎn)化的子句集不可滿足.,22,歸結(jié)原理,在定理證明系統(tǒng)中，已知一公式集F1，F(xiàn)2，F(xiàn)n，問公式W是否成立？ 方法一：證明F1F2FnW是永真式。

10、如果直接應(yīng)用推理規(guī)則進行推導(dǎo)，不容易建立機器證明系統(tǒng)。 方法二：間接法（反證法），證明F1F2FnW為永假，可以通過證明F所對應(yīng)的子句集S=S0W是不可滿足的。,23,命題： P|=F PF是不可滿足的。 證明: 若P F是不可滿足的，則 P|= F 若P|=F 則 P F是不可 滿足的。（反證法）,24,x(yp(X,Y) z (q(X,Z)r(X,Z) 5) (Skolem標(biāo)準(zhǔn)化) x(p(X,f(Y) (q(X,f(Z)r(X,f(Z) 6）（去全稱量詞）(p(X,f(X)(q(X,G(X)r(X,H(X) 7) (p(X,f(X)(q(X,G(Z) (p(X,f(X)r(X,H(X),

11、25,歸結(jié)原理,基本思想 將待證明的邏輯公式的結(jié)論（F），通過等值公式轉(zhuǎn)換成附加前提，再證明該邏輯公式是不可滿足的。 F （已證） P|=F PF是不可滿足的,26,使用歸結(jié)原理證明的思路,目標(biāo)（G）的否定連同已知條件（）一起，化為子句集 （ G化為子句集）， 并給出一種變換的方法，使得S S1 S2 . Sn同時保證當(dāng)Sn不可滿足時，有S不可滿足。,27,使用歸結(jié)原理證明的思路,目標(biāo)（G）的否定連同已知條件（）一起，化為子句集 （ G化為子句集）， 并給出一種變換的方法，使得S S1 S2 . Sn同時保證當(dāng)Sn不可滿足時，有S不可滿足。,空子句出現(xiàn),給出一種轉(zhuǎn)化方法，若原公式是永假的， 則

12、轉(zhuǎn)化的子句集也是不可滿足的。,把目標(biāo)的否定化為子句集,28,歸結(jié)方法（命題邏輯）,設(shè)子句集中的任意兩個子句：C1=LC1C2=(L)C2 (消去互補）構(gòu)成一個新的子句C=C1C2 則稱這一過程為歸結(jié)。C是C1和C2的歸結(jié)式. 例1：設(shè)C1=PQR, C2=Q S， 例2：設(shè) C1=P， C2=P 例3：設(shè)C1=PQ，C2=QR，C3=P， 兩次歸結(jié)：首先C1和C2 ，得C12=PR，再對C12，C3歸結(jié)，得 C123=R。,29,歸結(jié)方法（命題邏輯）,定理：歸結(jié)式是兩原子句的邏輯推論?；蛘哒f，任一使C1 ，C2為真的解釋I下，必有歸結(jié)式C12也為真。 證明:假設(shè)I是使C1 ，C2為真的任一解釋

13、。,歸結(jié)的例子,設(shè)集合： P, (PQ) R, (ST) Q, T 求證：R 子句集： (1) P (2) PQR (3) SQ (4) TQ (5) T (6) R（目標(biāo)求反）,化子句集： (PQ) R = (PQ)R = PQR (ST) Q = (ST)Q = (ST)Q = (SQ) (TQ) = SQ, TQ,31,子句集： (1) P (2) PQR (3) SQ (4) TQ (5) T (6) R（目標(biāo)求反）,歸結(jié)： (7) PQ (2, 6) (8) Q (1, 7) (9) T (4, 8) (10) nil (5, 9),歸結(jié)的例子,32,謂詞邏輯的歸結(jié)原理,謂詞邏輯中，

14、由于子句中包含有變元，所以不能直接消去互補文字（L和L），故需要考慮變量的約束問題，即在應(yīng)用歸結(jié)法時，往往要對公式作變量置換和合一等處理，才能得到互補的基本式，然后進行歸結(jié)。 問題：如何找歸結(jié)對 例：P(x)Q(y), P(f(y)R(y),33,置換,定義: 置換是形如t1/x1,tn/xn的有限集,其中xi是互不相同的變量,ti是不等于xi的項,且xi與ti互不循環(huán)出現(xiàn). 如果ti都是不含變量的項(基項),稱該置換為基置換. 若= ,則稱為空置換(表示不做置換),記為. 例如:1) a/x,g(y)/y,f(g(b)/z是一個置換? (是, 但不是基置換). 2) y/x, x/y是置換么

15、? (不是, 因為x,y循環(huán)出現(xiàn)).,34,置換（續(xù)）,定義 令 =t1/x1,tn/xn,E為表達(dá)式,E經(jīng)所得的實例E也是一個表達(dá)式,它是把在E中出現(xiàn)的xi同時置換為ti而得到. (項,文字,文字的合取,析取均稱為表達(dá)式) 若E是不含變量的表達(dá)式,則稱其為E的一個基實例. 例如:令E為p(x,y,f(a) =b/x,f(x)/y,則 E= ? E=p(b,f(x),f(a) 此例顯示了同時置換的含義. 可以看到E是在E上的作用,也就是將E中的(i=1, ,n)同時換成相應(yīng)的ti所得到的公式.,35,置換乘法,定義 令 =s1/y1,sm/ym, =t1/x1,tn/xn,則與的復(fù)合是一個置換

16、,定義為: =s1 /y1,sm /ym, t1/x1,tn/xn -(si /yi| si= yiti/xi |xiy1 , ym) 注意: 乘法的直觀含義是先做,在做.上述乘法的意思是從 s1 /y1,sm /ym, t1/x1,tn/xn中刪除: (1) 若s1= yi,則刪除si /yi項. (2) 若xiy1 , ym,則刪除ti/xi . 所得到的新的置換.,例1. =f(y)/x,z/y, =a/x, b/y, y/z 則=f(y)/x,z/y, a/x, b/y, y/z -(si /yi| s1= yit1/x1 |x1y1 , ym) = f(b)/x,y/y, a/x,

17、b/y, y/z -(si /yi| s1= yit1/x1 |x1y1 , ym) =f(b)/x, y/z =a/x, b/y, y/z, f(y)/x,z/y -(si /yi| s1= yit1/x1 |x1y1 , ym) =a/x, b/y, z/z, f(y)/x, z/y -(si /yi| s1= yit1/x1 |x1y1 , ym) =a/x,b/y 可以看到: ,即乘法是不可交換的.,例2. 公式E=p(x,f(y),z),置換 =f(x,y)/z, z/w =a/x,b/y,w/z 求 (1) (E) (2) E() (3) E() 解:(1) E= p(x,f(y)

18、,z)f(x,y)/z, z/w = p(x,f(y),f(x,y) (E)=p(x,f(y),f(x,y)a/x,b/y,w/z =p(a,f(b),f(a,b) (2) =f(x,y)/z, z/w, a/x,b/y,w/z -(si /yi| s1= yit1/x1 |x1y1 , ym) =f(a,b)/z, w/w, a/x,b/y,w/z -(si /yi| s1= yit1/x1 |x1y1 , ym) =f(a,b)/z,a/x,b/y,E()= p(x,f(y),z)f(a,b)/z, a/x,b/y = p(a,f(b),f(a,b) (3) =a/x,b/y,w/z, f

19、(x,y)/z, z/w -(si /yi| s1= yit1/x1 |x1y1 , ym) =a/x, b/y, z/w E()= p(x,f(y),z)a/x, b/y, z/w =p(a,f(b),z) 明顯的: E()E() 雖然置換乘法不滿足交換律,但是滿足下列性質(zhì): = (E)=E(), 其中E為任意公式. ()=() (即滿足結(jié)合律),39,合一(unifier),最廣合一(mgu),定義: 令S是一個簡單表達(dá)式的非空有限集 S=E1,En, S=E1 ,En 若S是單元素集,即E1= =En,則稱為S的一個合一(unifier), S稱為是可合一的. 如果對S的任意一個合一,存

20、在一個置換,使的=,則稱是S的一個最廣合一(most general unifier),記為mgu. 可以看到,若S有合一,則稱S是可合一的;否則,稱S是不可合一的; 注意到合一不唯一.,前面介紹了合一和最廣合一的概念. 為什么要求出最廣合一? 求最廣合一mgu的目的是: 使子句集中子句的文字形式結(jié)構(gòu)完全一致,從而達(dá)到取消互補文字的目的。 例1. S=p(x), p(a) =a/x是一個mgu. 例2. S=p(x), p(f(y), =f(y)/x是一個mgu. 對于=f(a)/x,a/y也是一個合一 (因為S是一個單元素集). 可求得=a/y使得=.,41,例3. S=p(x), p(y)

21、, 1=x/y和 2=y/x均為S的mgu. 1= 2x/y= 21, 2= 1y/x=22, 由此例可知: 最廣合一mgu不唯一. 若一個S有兩個mgu,則經(jīng)兩個mgu變換后,所得到的結(jié)果只有變量不同. (S1 =p(x), S2 =p(y).,合一,42,第12次課 11月4日,43,上次課程回顧,歸結(jié): 1）兩個子句：C1=LC1, C2=(L)C2 歸結(jié)式為 C=C1C2 2）P(x)Q(y), P(f(y)R(y) 置換： t1/x1,tn/xn的有限集 置換乘法 合一，mgu,44,合一算法,在介紹合一算法前,首先了解差異集的概念. 差異集: 設(shè)S是一個非空的具有相同謂詞名的原子公

22、式集,從S中各公式的左邊第一項開始,同時向右比較,直到發(fā)現(xiàn)第一個不都相同的項為止,用這些項的差異部分組成一個集合,這個集合就是原子公式子句集的一個差異集. 例如: S=p(x,y,z),p(x,f(a),h(b), 則S的差異集D1=y,f(a),合一算法: 輸入:簡單表達(dá)式的非空有限集S. 輸出: 判斷S是否可合一; 若S可合一,則輸出一個mgu. 若S不可合一,則報告S不可合一. 分析思路： 算法如下: 令k=0,Sk=S, k= 若Sk是單元素集,則算法停止,mgu=k 否則,求Skk的差異集Dk 若Dk中存在元素xk和tk,其中xk是變量, tk是項,且xk不出現(xiàn)在tk中,則置 k=k

23、+1,Sk+1= Sktk/xk,K+1=k tk/xk,轉(zhuǎn)步驟2. 否則,算法停止,報告S不可合一. 說明:若S可合一,算法總是在步驟2停止. (也可畫出框圖),46,k=0,Sk=S0=S,k= Sk是單元素集么? Y S可合一,mgu=k 尋找Sk的差異集Dk Dk中元素xk和tk,其中xk是變量, Y 算法停止, tk是項,判斷xk是否出現(xiàn)在tk中, S不可合一. N 置 k=k+1, Sk+1= Sktk/xk, K+1 =k tk/xk,Occur檢查,47,舉例,例1.求公式集S=p(a,x,f(g(y),p(z,h(z,u),f(u)的mgu. 解: 1) k=0, Sk=S0

24、=S, k=0=, 明顯的, S0=S不是單元素集. 2) 求得其差異集D0=a,z,其中z為變量,a為項,且z不 在a中出現(xiàn). 令k=k+1,有 1= 0 a/z= a/z= a/z S1=S0a/z=p(a,x,f(g(y),p(z,h(z,u),f(u)a/z =p(a,x,f(g(y), p(a,h(a,u),f(u) S1不是單元素集.,48,求得其差異集D1=x,h(a,u),其中x為變量,h(a,u)為項,且x不在h(a,u)中出現(xiàn). 令k=k+1,有 2= 1h(a,u)/x=a/zh(a,u)/x = a/z,h(a,u)/x S2=S1 h(a,u)/x=p(a,x,f(g

25、(y), p(a,h(a,u),f(u)h(a,u)/x =p(a,h(a,u),f(g(y),p(a,h(a,u),f(u) S2不是單元素集. 求得其差異集D2=g(y),u,其中u為變量, g(y)為項,且u不在g(y)中出現(xiàn).,舉例（續(xù)）,49,令k=k+1,有 3=2g(y)/u=a/z,h(a,u)/xg(y)/u =a/z,h(a,g(y)/x S3=S2g(y)/u =p(a,h(a,u),f(g(y),p(a,h(a,u),f(u)g(y)/u =p(a,h(a,g(y),f(g(y),p(a,h(a,g(y),f(g(y) 明顯的, S3是單元素集. 3) Mgu = 3=

26、a/z,h(a,g(y)/x,舉例（續(xù)）,50,練習(xí),1.令公式集S=p(a,x,h(g(z), p(z,h(y),h(y)使用合一算法,求S的mgu. 2. 判斷S=p(x,x),p(y,f(y)是否可合一.,51,謂詞邏輯的歸結(jié)方法,對于子句C1L1和C2 L2，如果L1與L2可合一，且是其合一，則(C1C2)是其歸結(jié)式。 例： P(x)Q(y), P(f(z)R(z) 判斷（P(x)， P(f(z)）是否有合一 ? 若可以合一，則歸結(jié)式為 (Q(y)R(z) ,52,謂詞邏輯的歸結(jié)舉例,設(shè)集合： （1）(x)(R(x)L(x) （2）(x)(D(x)L(x) （3）(x)(D(x)I(x

27、) 求證： (x)(I(x)R(x) 化子句集： (x)(R(x)L(x) = (x)(R(x)L(x) 去全稱量詞：R(x)L(x),（2） (x)(D(x)L(x) = (x)(D(x)L(x) 去全稱量詞：D(x)L(x) （3）(x)(D(x)I(x) Skolem標(biāo)準(zhǔn)化 D(A)I(A) 即得：D(A) I(A),53,目標(biāo)求反： (x)(I(x)R(x) 得 (x)(I(x)R(x) 得 (x)(I(x)R(x) 得 I(x)R(x),換名后的子句集： R(x1)L(x1) D(x2)L(x2) D(A) I(A) I(x5)R(x5),歸結(jié)舉例（續(xù)）,54,上例的歸結(jié)樹,子句集：

28、 R(x1)L(x1) D(x2)L(x2) D(A) I(A) I(x5)R(x5),I(A),I(x5)R(x5),R(A), A/x5,R(x1)L(x1),L(A), A/x1,D(x2)L(x2),D(A), A/x2,D(A),nil,55,基于歸結(jié)的問答系統(tǒng),例： 已知：(x)AT(John, x) AT(Fido, x) AT(John, School) 求證：(x)AT(Fido, x) 子句集： AT(John, x1) AT(Fido, x1) AT(John, School) AT(Fido, x2),指John在什么地方，F(xiàn)ido在什么地方,Fido在一個地方，找這個

29、地方,56,AT(Fido, x2),AT(John, x1) AT(Fido, x1),子句集：AT(John, x1) AT(Fido, x1) AT(John, School) AT(Fido, x2),x2/x1,AT(John, School),School/x2,AT(Fido, School),57,一個家族關(guān)系的例子,設(shè)有某家庭成員的集合 a, b, c1, c2, c3, d1, d2, d3, d4 并且知道它們之間的關(guān)系為: 1) b 是 c1, c2, c3的母親. 2) c3 是 d4 的母親. 3) c1是 d1, d2, d3的父親. 4) a是 b的丈夫. 問題

30、：a的孫輩是誰?,58,問題分析,家庭的關(guān)系圖. (1) mother(b, c1) (2) mother(b, c2) (3) mother(b, c3) (4) mother(c3, d4) (5) father(c1, d1) (6) father(c1, d2) (7) father(c1, d3) (8) husband(a, b),家庭中有三個二元關(guān)系: 母子關(guān)系,父子關(guān)系,夫妻關(guān)系.可表示為: mother (X,Y) : X是Y 的母親. father (X,Y): X是Y 的父親. huaband (X,Y): X是Y 的丈夫.句的形式,59,問題分析（續(xù)）,問題是: a的孫

31、輩是誰? 定義如下, 對任給 X, Y, Z a) 若X 是Y的母親且Y是Z的母親, 則X是Z的外祖母. b) 若X 是Y的母親且Y是Z的父親, 則X是Z的祖母. c) 若X 是Y的丈夫且Y是Z的(外)祖母, X是Z的(外)祖父. 形式的表示如下: (9) mother(X,Z) mother(Z,Y) grandmother(X,Y) (10) mother(X,Z) father(Z,Y) grandmother(X,Y) (11) husband(X,Z)grandmother(Z,Y) grandfather(X,Y),60,問題表示,已知：(1) mother(b, c1) (2)

32、mother(b, c2) (3) mother(b, c3) (4) mother(c3, d4) (5) father(c1, d1) (6) father(c1, d2) (7) father(c1, d3) (8) husband(a, b) (9) mother(X,Z) mother(Z,Y) grandmother(X,Y) (10) mother(X,Z) father(Z,Y) grandmother(X,Y) (11) husband(X,Z) grandmother(Z,Y) grandfather(X,Y) 求：(X) grandfather(a,X),(9) moth

33、er(X1,Z1) mother(Z1,Y1) grandmother(X1,Y1) (10) mother(X2,Z2) father(Z2,Y2) grandmother(X2,Y2) (11) husband(X3,Z3) grandmother(Z3,Y3) grandfather(X3,Y3),目標(biāo)求反 grandfather(a,X4),61,歸結(jié), grandfather(a,X4), husband(X3,Z3) grandmother(Z3,Y3) grandfather(X3,Y3), husband(a,Z3) grandmother(Z3,Y3),a/X3，Y3/X4,

34、62,第13次課 11月11日,63,上次課程回顧,合一算法 謂詞邏輯的歸結(jié),64,Herbrand定理,Herbrand定理是歸結(jié)原理的理論基礎(chǔ)。,Jacques Herbrand ： (1908.2.121931.7.27) 法國數(shù)學(xué)家, 生于法國巴黎, 死于一次登山事故. Herbrand定理的提出者。 Herbrand定理是歸結(jié)原理的理論基礎(chǔ)，歸結(jié)原理的正確性是通過Herbrand定理證明的。,65,預(yù)備知識,謂詞邏輯合式公式的真值： 1）原子公式的值要么為T, 要么為F. 2）若A,B為合式公式, 那么A, AB, AB, AB, AB的值由真值表決定. 3) 如果在解釋I下,A對X

35、的所有賦值都是 T，那么XA的值是T，否則為F。 4）如果在解釋中存在一個賦值使A的值是T， 那么XA的值是T，否則為F。 簡單的說: 對謂詞公式中的各種變量指定特定的常量去代替, 就構(gòu)成了謂詞的解釋.,66,舉例,例： 給定解釋I如下: 論域 D=2,3; 函數(shù)f(x)為f(2)=3,f(3)=2； 謂詞p(x)為p(2)=0，p(3)=1； q(x,y)為q(i,j)=1, i, j=2,3 r(x,y)為r(2,2)=r(3,3)=1, r(2,3)=r(3,2)=0 求（1）在解釋I下，x(p(f(x)q(x,f(x)的 真值。 （2）在解釋I下，xy r(x,y)的真值。 (3) 在

36、解釋I下， xy r(x,y)的真值。,67,模型,對于公式F，公式集S和解釋I： （1）若在I下，F(xiàn)為真，則I是F的一個模型。 （2）若在I下，S中各公式均為真，則I是S的 一個模型。 （3）如果S有模型，則稱S是可滿足的。 （4）如果S無模型，則稱S是不可滿足的。 （5）如果S的任一模型都是F的模型,則稱F是 S的邏輯推論,記為 S|= F. 公式F永真：對于F的所有解釋，F(xiàn)都為真。 公式F永假：對于F的所有解釋，F(xiàn)都為假。,S= F1, F2, F3 ,68,Herbrand定理思想,為了證明一個謂詞公式A永真, 需要證明其反命題A永假. 所謂“永假”就是不存在模型,即在所有可能的解釋中

37、, A均取假值. 由于量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數(shù)是無限的, 不可數(shù)的，要找到所有的解釋是不可能的。 Herbrand定理的基本思想是簡化討論域，建立一個比較簡單的，特殊的論域（Herbrand域），使得只要在此論域上，原謂詞公式是不可滿足的，即保證不可滿足的性質(zhì)不變。,69,Herbrand域和D域的關(guān)系如圖：,D 域,H 域,70,Herbrand域,定義1：設(shè)S是一個子句集，U0是S中子句所含的全體常量集。若S中子句皆不含常量，則任擇一常量a, 并令 U0 =a, 對i1, 令 Ui = Ui-1fn(t1,tn)| n1,fn是S中出現(xiàn)的所有函數(shù)符號的集合函數(shù); t1,tnUi-1 Us= i0 Ui 則稱Ui為S的i階常量集, Us稱為S的Herbrand論域. Us的元素稱為基項.,71,舉例,例1：令S=p(X),q(Y)r(Z)，求：H-域 解 在題目中設(shè)有常量a U0=a U1=U0=a Us=U0U1U3= a 例2: 令S=p(a),q(X)r(f