人工智能第六章6.3-6.5.ppt_第1頁
人工智能第六章6.3-6.5.ppt_第2頁
人工智能第六章6.3-6.5.ppt_第3頁
人工智能第六章6.3-6.5.ppt_第4頁
人工智能第六章6.3-6.5.ppt_第5頁
已閱讀5頁,還剩35頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、8/7/2020,1,6.3 合一算法,8/7/2020,2,例: C1:P(x) Q(x) C2:P(f(x) R(x) 沒有互補(bǔ)對; C1:P(y) Q(y) y/x C1:P(f(x) Q(f(x) f(x)/y C3:R(x) Q(f(x) 替換和合一是為了處理謂詞邏輯中子句之間的模式匹配而引進(jìn).,8/7/2020,3,一、替換與最一般合一替換,定義(替換)一個替換是形如t1/v1, , tn/vn 的一個有限集合,其中vi是變量符號,ti是不同于vi的項(xiàng)。并且在此集合中沒有在斜線符號后面有相同變量符號的兩個元素,稱ti為替換的分子,vi為替換的分母。 例. a/x, g(y)/y,

2、f(g(b)/z是替換; x/x, y/f(x), a/x, g(y)/y, f(g(b)/y不是替換; 基替換:當(dāng)t1,tn是基項(xiàng)時,稱此替換為基替換。 空替換:沒有元素的替換稱為空替換,記為。,8/7/2020,4,替換,定義(改名) 設(shè)替換 = t1/x1, , tn/xn 如果t1, , tn是不同的變量符號,則稱為一個改名替換,簡稱改名。 替換作用對象:表達(dá)式(項(xiàng)、項(xiàng)集、原子、原子集、文字、子句、子句集)。 基表達(dá)式:沒有變量符號的表達(dá)式。 子表達(dá)式:出現(xiàn)在表達(dá)式E中的表達(dá)式稱為E的子表達(dá)式。,8/7/2020,5,E的例,定義(E的例) 設(shè) = t1/v1, , tn/vn 是一個

3、替換,E是一個表達(dá)式。將E中出現(xiàn)的每一個變量符號,vi (1 i n) ,都用項(xiàng)ti替換,這樣得到的表達(dá)式記為E。稱E 為E的例。 若E 不含變量,則E 為E的基例。 例. 令 = a/x, f(b)/y, c/z,E=P(x, y, z) 于是E的例(也是E的基例)為 E = P(a, f(b), c),8/7/2020,6,練習(xí): E=P(x, g(y), h(x,z), =a/x, f(b)/y, g(w)/z E=P(a, g(f(b), h(a,g(w) E=P(x, y, z), =y/x, z/y E=P(y, z, z). EP(z, z, z).,8/7/2020,7,替換的

4、乘積,定義(替換的乘積)設(shè) = t1/x1, , tn/xn , = u1/y1, , um/ym 是兩個替換。將下面集合 t1/x1, , tn/xn , u1/y1, , um/ym 中任意符合下面條件的元素刪除: 1)ui/yi,當(dāng)yix1, , xn 時; 2)ti/xi,當(dāng)ti = xi 時。 如此得到一個替換,稱為與的乘積,記為 。 例. 令 =f(y)/x, z/y =a/x, b/y, y/z 于是得集合 t1/x1, t2/x2 , u1/y1, u2/y2 , u3/y3 = f(b)/x, y/y, a/x, b/y, y/z 與的乘積為 = f(b)/x, y/z ,8

5、/7/2020,8,=a/x, =b/x =a/x =b/x 可見: ,8/7/2020,9,例子: E=P(x, y, z) =a/x, f(z)/y, w/z E=P(a, f(z), w) =t/z, g(b)/w (E)=P(a, f(t), g(b) =a/x, f(t)/y, g(b)/z,g(b)/w E=P(a, f(t), g(b),8/7/2020,10,引理 若E是表達(dá)式,是兩個替換, 則E ( ) = (E),證明: 設(shè)vi是E中任意一個變量符號,而 = t1/x1, , tn/xn , = u1/y1, , um/ym 若vi既不在 x1, , xn 中,也不在 y1

6、, , ym 中,則vi在E ( )中和在(E)中都不變。 若vi=xj (1jn),則E中的vi,在(E)中先變成tj,然后再變成tj;E中的vi在E()中立即就變成了tj。故E中vi在(E)中和在E()中有相同變化。 若vi=yj (1jm),且yj x1,xn ,則E中vi在(E)中變?yōu)閡j;E中vi在E()中也變?yōu)閡j(注意:yjx1, xn,所以uj/yj),故E中vi在(E)中和在E ()中有相同變化。 由于vi的任意性,故引理得證。,8/7/2020,11,引理 設(shè), 是三個替換, 于是()(),證明: 設(shè)E是任一表達(dá)式,由上面引理知 E() =(E() = (E) E() =(

7、E) () = (E) 所以 E() = E() 由于E的任意性,故 ()(),8/7/2020,12,定義(合一)稱替換是表達(dá)式集合E1,Ek的合一,當(dāng)且僅當(dāng)E1E2=Ek。 表達(dá)式集合E1, , Ek稱為可合一的,如果存在關(guān)于此集合的一個合一。 定義(最一般合一) 表達(dá)式集合E1, , Ek的合一 稱為是最一般合一(most general unifier, 簡寫為mgu),當(dāng)且僅當(dāng)對此集合的每一個合一,都存在替換,使得 ,8/7/2020,13,二、合一算法,定義(差異集合) 設(shè)W是非空表達(dá)式集合,W的差異集合是如下一個集合:首先找出W的所有表達(dá)式中不是都相同的第一個符號,然后從W的每一

8、個表達(dá)式中抽出占有這個符號位置的子表達(dá)式。所有這些子表達(dá)式組成的集合稱為這步找到的W的差異集合D。,8/7/2020,14,W不可合一的三種情況,(1)若D中無變量符號為元素,則W是不可合一的。 例. W=P(f(x), P(g(x) D=f(x), g(x) (2)若D中有奇異元素和非奇異元素,則W是不可合一的。 例. W=P(x), P(x, y) D=, y (3)若D中元素有變量符號x和項(xiàng)t,且x出現(xiàn)在t中,則W是不可合一的。 例. W=P(x), P(f(x) D=x, f(x),8/7/2020,15,換名: P(f(x), x), P(x, a); 如果不換名:D=f(x), x

9、. 換名: P(f(y), y), P(x, a); mgu: f(a)/x, a/y,8/7/2020,16,步驟1:置 k=0, Wk=W, k= 步驟2:若Wk只有一個元素,則停止,k是W的最一般合一; 否則,找出Wk的差異集合。 步驟3:若Dk非奇異,Dk中存在元素vk和tk,其中vk是變量符號,并且 不出現(xiàn)在tk中,則轉(zhuǎn)步驟4; 否則,算法停止,W是不可合一的。 步驟4:令 k+1=ktk/vk,Wk+1=Wk (注:Wk+1=W ) 步驟5:置 k=k+1,轉(zhuǎn)步驟2。,合一算法(Unification algorithm),8/7/2020,17,例. 令 W=Q(f(a), g(

10、x), Q(y, y), 求W的mgu。,步驟1: k=0, W0=W, 0=。 步驟2: D0 =f(a), y。 步驟3:有v0=y D0,v0不出現(xiàn)在t0f(a)中。 步驟4:令 1=0t0/v0=f(a)/y, W1=Q(f(a), g(x), Q(f(a), f(a) 步驟5:k=k+1=1 步驟2: D1 =g(x), f(a) 。 步驟3:D1中無變量符號,算法停止,W不可合一。,8/7/2020,18,例 令 W= P(a, x, f(g(y), P(z, f(z), f(u), 求出W的mgu。,步驟1:k=0,W0=W, 0= 。 步驟2: D0 =a, z。 步驟3:有v

11、0=z D0,v0不出現(xiàn)在t0a中。 步驟4:令 1=0t0/v0=a/z=a/z, W1=W0t0/v0=P(a,x,f(g(y),P(z,f(z),f(u)a/z=P(a,x,f(g(y),P(a,f(a),f(u) 步驟5:k=k+1=1 步驟2: D1 =x, f(a) 。 步驟3:有v1=x D1,且v1不出現(xiàn)在t1f(a)中。 步驟4:令 2=1t1/v1=a/z f(a)/x =a/z, f(a)/x , W2=W1t1/v1=P(a,x,f(g(y),P(a,f(a),f(u)f(a)/x =P(a,f(a),f(g(y),P(a,f(a),f(u),8/7/2020,19,例

12、.,步驟5:k=k+1=2 步驟2: D2 =g(y), u。 步驟3:有v2=u D2,且v2不出現(xiàn)在t2g(y)中。 步驟4:令 3=2t2/v2=a/z, f(a)/x g(y)/u =a/z, f(a)/x, g(y)/u , W3=W2t2/v2=P(a, f(a), f(g(y), P(a, f(a), f(u) g(y)/u =P(a, f(a), f(g(y) 步驟5:k=k+1=3 步驟2:W3只有一個元素。算法停止。 3=a/z, f(a)/x, g(y)/u 是W的最一般合一。,8/7/2020,20,定理 若W是關(guān)于表達(dá)式的有限非空可合一集合,則合一算法終將結(jié)束在步驟2

13、,并且最后的k是W的最一般合一。,證明: (1)終止性。 否則將產(chǎn)生一個無窮序列: W , W , W , 其中每一個直接后繼集合比它的前任都少一個變量符號(注意:W 包含vk,而W 不包含vk)。但這是不可能的,因?yàn)閃僅含有限個變量符號。 (2) k是W的合一。若算法停止在步驟2,則Wk=W只含有一個元素,所以k是W的合一。,8/7/2020,21,(3)用歸納法證明算法必不會停止在步驟3,并且對任意W的一個合一,任意k,都存在替換k,使得 =kk 亦即k是W的mgu。 當(dāng)k=0時,因0=,取0=,于是=00。,8/7/2020,22,假設(shè)對0kn,=kk成立 往證:存在n+1,使得=n+1

14、n+1。 若W 只含有一個元素,則合一算法結(jié)束在步驟2。因?yàn)?nn,且n是W的合一,故n是W的mgu。定理得證。 若W 不只含有一個元素,按照算法,將找出W的差異集合Dn。 因?yàn)?nn是W的合一,所以W中表達(dá)式經(jīng)替換作用后都變成同一個相同的表達(dá)式。而W中表達(dá)式經(jīng)n作用后,產(chǎn)生了差異集合Dn,所以Dn必須被n所統(tǒng)一,即n是D n的合一。,8/7/2020,23,因?yàn)镈n是可合一的(n就是Dn的合一),所以必有變量符號vnDn;Dn中至少有兩個不同元素。所以可設(shè)tnDn,且tnvn。顯然,變量符號vn不出現(xiàn)在tn中(否則,vnn tnn,這與n是Dn的合一矛盾)。 因此算法不能停止在步驟3,所以算

15、法必然停止在步驟2。,8/7/2020,24,令n+1=ntn/vn。因?yàn)関nn=tnn,所以tnn/vnn 令n+1=n -tnn/vn。因vn不出現(xiàn)在tn中,所以 于是 故 歸納法完成。即對所有k0,都存在替換k,使=kk。所以算法終止步驟2時,k是W的最一般合一。,8/7/2020,25,6.4 一階邏輯中的歸結(jié)原理,8/7/2020,26,定義(因子) 如果子句C中,兩個或兩個以上的文字有一個最一般合一,則C稱為C的因子; 如果C是單元子句,則C稱為C的單因子。 例. C=P(x) P(f(y) Q(x) 令 f(y)/x,于是 C= P(f(y) Q(f(y) 是C的因子。,8/7/

16、2020,27,二元?dú)w結(jié)式,定義 設(shè)C1, C2是兩個無公共變量的子句(稱為親本子句), L1, L2分別是C1, C2中的兩個文字。 如果L1和L2有最一般合一,則子句 (C1- L1) ( C2- L2) 稱為C1和C2的二元?dú)w結(jié)式,L1和L2稱為歸結(jié)文字。 例. 設(shè)C1=P(x) Q(x), C2=P(a) R(x) 將C2中x改名為y。取L1P(x), L2=P(a), =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) -C1和C2的二元?dú)w結(jié)式.,8/7/2020,28

17、,在謂詞邏輯中,對子句進(jìn)行歸結(jié)推理時,要注意以下幾個問題: (1)若被歸結(jié)的子句C1 和C2中具有相同的變元時,需要將其中一個子句的變元更名,否則可能無法合一,從而沒有辦法進(jìn)行歸結(jié)。 (2)在求歸結(jié)式時,不能同時消去兩個互補(bǔ)文字對,消去兩個互補(bǔ)文字對所得的結(jié)果不是兩個親本子句的邏輯推論。 (3)如果在參加歸結(jié)的子句內(nèi)含有可合一的文字,則在進(jìn)行歸結(jié)之前,應(yīng)對這些文字進(jìn)行合一,以實(shí)現(xiàn)這些子句內(nèi)部的化簡。,8/7/2020,29,歸結(jié)式,定義 子句C1, C2的一個歸結(jié)式是下列二元?dú)w結(jié)式之一: C1和C2的二元?dú)w結(jié)式。 C1和C2的因子的二元?dú)w結(jié)式。 C1的因子和C2的二元?dú)w結(jié)式。 C1的因子和C2

18、的因子的二元?dú)w結(jié)式。 例. 設(shè) C1=P(x) P(f(y) R(g(y) C2=P(f(g(a) Q(b) C1的因子C1= P(f(y) R(g(y)。于是C1和C2的二元?dú)w結(jié)式,從而也是C1和C2的歸結(jié)式為 R(g(g(a) Q(b),8/7/2020,30,一階邏輯歸結(jié)原理的完備性,提升引理 如果C1和C2分別是子句C1和C2的例,C是C1和C2的歸結(jié)式,則存在C1和C2的一個歸結(jié)式C,使C是C的例。,8/7/2020,31,一階邏輯歸結(jié)原理的完備性,定理 若子句集S是不可滿足的,則存在從S推出空子句的歸結(jié)演繹。 證明: 設(shè)子句集S是不可滿足的,由Herbrand定理II知,存在S的一

19、個基例集S也是不可滿足的。根據(jù)命題邏輯歸結(jié)原理的完備性,存在從S推出空子句的歸結(jié)演繹D。由提升引理知,可將D提升成一個從S推出空子句的歸結(jié)演繹D。定理得證。,8/7/2020,32,6.5 歸結(jié)原理的幾種改進(jìn),8/7/2020,33,一、支架集歸結(jié),定義子句集S的子集T稱為S的支架集,如果(S-T)是可滿足的。一個支架集歸結(jié)是一個不同時屬于(S-T)的兩個子句的歸結(jié)。 例. 設(shè)S是如下子句集: (1)PQ (2)PQ (3)PQ (4)PQ 令 T= PQ ,顯然 T 是支架集。如下的演繹是支架集歸結(jié)演繹: (5)P 由 (1)、(2) (6)Q 由(1)、(3) (7)Q 由(5)、(4)

20、(8) 由(6)、(7),8/7/2020,34,二、語義歸結(jié),定義(語義互撞) 設(shè)I是子句集S的一個解釋,P是S中謂詞符號的一個順序,有限子句序列 E1, , Eq, N (q1)稱為關(guān)于P和I的語義互撞(簡稱PI-互撞),當(dāng)且僅當(dāng)E1, , Eq, N 滿足下面條件: E1, , Eq在I下為假; 令R1=N,對每個 i=1, ,q,存在Ri和Ei的歸結(jié)式Ri+1。 Ei中的歸結(jié)文字是Ei中最大謂詞符號。 Rq+1在I下為假。 于是,Rq+1稱為此PI-互撞的PI-歸結(jié)式。,8/7/2020,35,例. 設(shè)S是如下子句集: (1)PQR (2)PR (3)QR (4)R 令 I=P, Q, R,PQR。于是在I下為假的子句只有兩個: Si =PR, QR 我們可得如下PI-演繹: (5)R 由(2)、(3) 、(1) (6) 由(5)、(4),8/7/2020,36,三、線性歸結(jié),定義(線性歸結(jié)演繹)設(shè)S是一個子句集,C0是S中的一個子句。以C0為頂子句,從S到Cn的線性歸結(jié)演繹是如下一個演繹: 對于 i=0, 1, ,n-1,Ci+1是Ci和Bi的歸結(jié)式。 每個Bi或者屬于S,或者是一個Cj,其中j i。,8/7/2020,37,四、鎖歸結(jié),定義(鎖歸結(jié)式) 設(shè)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論