模態(tài)邏輯及其應(yīng)用

1、3-1模態(tài)邏輯及其應(yīng)用本節(jié)主要涉及以下內(nèi)容：1. 經(jīng)典邏輯的局限性2. 模態(tài)邏輯3. 時(shí)序邏輯4. 基于區(qū)間的時(shí)間推理3-1-1經(jīng)典邏輯的局限性一階謂詞邏輯的局限：任何命題必須知道真、偽，否則，不能處理。Aristotle例子：“明天波斯和雅典將發(fā)生海戰(zhàn)”Aristotle工具論指出了傳統(tǒng)邏輯的這一局限性，并論述了其解決辦法(后 被冷落)。直到20世紀(jì)初，Lewis(劉易斯)研究實(shí)質(zhì)蘊(yùn)涵悖論時(shí)重新提出。實(shí)質(zhì)蘊(yùn)涵悖論： (qp)， (pr q)， (pq) (qr p) = p q p， p p q， ( p q) ( q p)即有：(1)若某命題為真，則它可從任何命題推出；(2) 若某命題為假

2、，則它可推出任何命題；(3) 任意兩個(gè)命題p和q，不是p推出q，就是q推出p。則有如下悖論：(1) 若布什在7086年當(dāng)選皇帝，則1+仁2;(2) 若太陽(yáng)從西邊出來(lái)，則公司經(jīng)理不要效益；(3) 要么從黎曼猜想為真能夠推導(dǎo)出費(fèi)馬大定理為真，要么從費(fèi)馬大定 理為真能推出黎曼猜想為真，兩者必居其一。根源：Russel對(duì)p- q經(jīng)典定義，即 p q改進(jìn)：Lewis提出以嚴(yán)格蘊(yùn)涵代替 Russel的實(shí)質(zhì)蘊(yùn)涵，即p. q=不可能(p q)。(Lewis定義實(shí)際上也有悖論存在)發(fā)展簡(jiǎn)況：Aristotle提出四種模態(tài)，即可能、偶然、不可能、必然；后來(lái)，Kant分為三種，即或然、實(shí)然、必然；Wunt歸結(jié)為或然

3、和必然，將實(shí)然看作非模態(tài)判斷；現(xiàn)代模態(tài)邏輯一般以 可能和必然為基本標(biāo)準(zhǔn)。3-1-2模態(tài)邏輯基本思想：在普通邏輯中引入 可能和必然模態(tài)詞。定義3-1-2-1模態(tài)邏輯的合適公式:(1) 任何一個(gè)一階謂詞演算的合適公式都是模態(tài)邏輯的合適公式。(2) 若A是模態(tài)邏輯的合適公式，則口 A也是合適公式。(3) 若A是模態(tài)邏輯合適公式則 A也是合適公式。(4) 若A是模態(tài)邏輯合適公式則A也是合適公式。(5) 若A、B是合適公式，貝U A B, A B,A > B,A=B都是合適公式(6) 除此以外，沒(méi)有別的合適公式是必然算子，是可能算子。注：口 (A > B)表示A不一定推出B; (A >

4、 B)表示A必然推不出B定義3-1-2-2命題模態(tài)邏輯系統(tǒng)：(1) 一組命題(模態(tài))合適公式，稱為公理；(2) 一組推導(dǎo)規(guī)則，每個(gè)規(guī)則采取如下形式：A1 A2 幾。其中，A和AA都是模態(tài)邏輯合適公式；(3) 規(guī)則組的推導(dǎo)是封閉的則稱(1)和(2)構(gòu)成一個(gè)命題模態(tài)邏輯系統(tǒng)T系統(tǒng)及其性質(zhì)討論等參見(jiàn)人工智能(下)P424-437 (陸汝鈐)定義3-1-2-3模態(tài)邏輯的一個(gè)模型 用一個(gè)三元組表示，即M =(W,R,V)。其中，W是可能世界的非空集合，V是對(duì)W中可能世界的真值指派，即對(duì)每個(gè)合 適公式，指明它在每個(gè)可能世界中取真值還是假值， R是附加于此模型之上的其 它關(guān)系，可以為空。注：有各種模型，如L

5、eibnitz模型，標(biāo)準(zhǔn)模型(當(dāng)R為W W上的一個(gè)二元 關(guān)系時(shí))。3-1-3時(shí)序邏輯定義3-1-3-1時(shí)序邏輯或時(shí)態(tài)邏輯 對(duì)模型M的R解釋為時(shí)間先后關(guān)系時(shí)，該 模型即成為時(shí)序邏輯。詳細(xì)討論及例舉等參見(jiàn)人工智能(下)P437-453 (陸汝鈐)3-1-4基于區(qū)間的時(shí)間推理(時(shí)序推理)3-1-4-1基本表示方法及推理算法由Allen提出，用于表示時(shí)間關(guān)系知識(shí)，并進(jìn)行時(shí)間順序推理。假設(shè)：區(qū)間是時(shí)間表示的基本單位，一般不為0,時(shí)間區(qū)間由兩個(gè)時(shí)間點(diǎn)表 示，即t-和t ,其中。半開(kāi)半閉區(qū)間概念。定義3-1-4-1 Allen的時(shí)間關(guān)系表示體系：設(shè)A和B表示時(shí)間區(qū)間，t(A)、t(A) 分別表示A的左端和A

6、的右端。則有：(1) A B或B A表示A在B之前發(fā)生，也即t(A) ：t(B)-(2) A=B或B=A表示A和B發(fā)生的時(shí)間區(qū)間相同，即t(A)=：t(B廠且t(A) “(B)(3) AmB或 BmiA 表示 A遇到 B，即 t(A-t(B)(4) AoB 或 BoiA 表示 A交叉 B，即 t(A) - ： t(B) = t(A) : t(B)(5) AdB 或 BdiA 表示 A 在 B 中，即 t(B廠:t(A)_ : t(A) < t(B)或者 t(B)飛t(A) 一 ：t(A) ：t(B)(6) AbB 或 BbiA 表示 A開(kāi)始于 B，即 t(A)=t(B)一 ： t(A)

7、： t(B)(7) AeB或 BeiA表示 A結(jié)束于 B，即 t(B) ：t(A) : t(A) =t(B)表3-1-4-1時(shí)間區(qū)間之間的組合關(guān)系R=<>ddiooimmibbieei(等于)=<>ddiooimmibbieei<(在之前)<<?< o m d b<<< o m d b<< o m d b<<< o m d b<>(在之后)>?>> oi mi d e>> oi mi d e>> oi mi d e>>oi mide&

8、gt;>>d(在之中)d<>d?< o m>oi mi<>d> oi mid<o md bd eded bdi（包含）di< o m di ei> oi mi di eio oi du codiodieioidibio di eioidibidieiodioi di bidio（交叉）o<> oi mi di bio d b< o m di ei< o mo oi du co<oidibiodi ei oo d b<o moi（被交叉）oi< o m di ei>oi d e

9、> oi mi di bio oi du co>oi mio di ei>oi d e> oi mioioidibim（遇上）m<> oi mi di bio d b<<o d b<e eimmo d b<mi（被遇上）mi< o m di ei>oi d e>oide>b bi>oi d e>mimib（開(kāi)始）b<>d< o m di ei< o moide<mibb bid<mobi（被開(kāi)始）bi< o m di ei>oi d ediodieio

10、io di eimib bibioidie（結(jié)束）e<>d> oi mi di bio d b>oi mim>d> oi mieeei表示實(shí)例：包龍圖為了弄清(A1)新科狀元陳世美 不認(rèn)(A2)發(fā)妻的原因，請(qǐng)(A3)御史大夫寇準(zhǔn)偵察(A4)陳世美的宅院。助手狄仁杰 配合(A5)寇準(zhǔn)工作。他在監(jiān)視 (A6)陳時(shí)，遭人攻擊(A7)，被打(A8)致傷(A9)，尚方寶劍被搶(A10)。根據(jù)定義3-1-4-1,從文字描述中可以直接獲得如下關(guān)系 (其有向圖網(wǎng)絡(luò)表示 如圖 3-1-4-1)：AdA即區(qū)間A4在區(qū)間A1中(“偵察”行為區(qū)間包含在“弄清”活動(dòng)中)；A ； A即

11、“不認(rèn)”在“弄清”之前，t(A2)t(A)；AmA即“請(qǐng)”和“偵察”之間是 meet關(guān)系，上(人)兒耳(代)-即“偵察”和“配合”同期進(jìn)行，t(A5)、t(A4)，t(As/ =t(A4)AdA即“監(jiān)視”在“配合”期間發(fā)生，上(人廠譏(代廠：譏(乓)mt(A5)A8bA7 即“打”是“攻擊”的開(kāi)始點(diǎn)，t(As) 一 二 t(A7r : t(A8/ : t(A7)'A8OA9即“打”和“受傷”之間交叉的，"乓)一譏(乓廠：t(A8)：t(A9)AeA 即“受傷”后“配合”結(jié)束，t(AsP < t(A9P <t(A9f =t(As)AmAo即“受傷”過(guò)后尚方寶劍“被搶

12、” ，t(A9)+ = t(Ao) 注：以上關(guān)系的獲取必須借助于某種知識(shí)(如常識(shí))：關(guān)系之間的組 合可以形成新的關(guān)系； 這種時(shí)間關(guān)系可看成是對(duì)事件之間的一種約束，而關(guān) 系的組合看成是約束的延伸；這種基于時(shí)間區(qū)間的關(guān)系約束常用有向圖表示(如圖3-1-4-1),其方法是用A -(R)T Aj表示關(guān)系A(chǔ)RAj : 任何兩個(gè)時(shí)間區(qū)間關(guān)系的表示都有兩種方法，如 A9mAo= AiomiA9，AdAu AQA4A3 ： (mi) A4 (d) r A ： ( A2(=)IAs (d)r A5 ： (e) Ag： (mi)A。(o)IM (b)-As圖3-1-4-1時(shí)間區(qū)間關(guān)系的網(wǎng)絡(luò)表示實(shí)例定義3-1-4-

13、2重復(fù)關(guān)系如果一對(duì)關(guān)系滿足以下條件，則稱之 為重復(fù)關(guān)系：(1) ARB和ARB ,R是任意關(guān) 系1 1(2) ARB 和 BR- A，R- 是 R 的逆關(guān)系定義3-1-4-3包含關(guān)系下列 關(guān)系稱為包含關(guān)系：(1) AdB 包含 AbBAdB包含AeB(3) AdB，B =C時(shí)，AdC。即“關(guān)系甲”包含“關(guān)系乙”，“關(guān)系乙”和“關(guān) 系丙”重復(fù)，則“關(guān)系甲”包含“關(guān)系丙”時(shí)間區(qū)間網(wǎng)絡(luò)的建立過(guò)程及在網(wǎng)絡(luò)上的推理過(guò)程(即傳播時(shí)間約束關(guān)系的過(guò)程):(1) 根據(jù)獲得的約束關(guān)系繪制約束關(guān)系有向圖(2) 對(duì)兩個(gè)區(qū)間之間的關(guān)系沒(méi)有確定的，將所有可能關(guān)系都標(biāo)注上去(3) 通過(guò)推理或其它途徑獲得有用信息后，逐步減少

14、區(qū)間之間的不唯一約束關(guān)系直到完全確定為止算法描述：假設(shè)：G :已知的時(shí)間區(qū)間關(guān)系網(wǎng)絡(luò)圖；n :表示一組時(shí)間區(qū)間事件；N(i,j):表示時(shí)間區(qū)間對(duì)(A,AJ之間的非重復(fù)約束關(guān)系集合； S :初始(時(shí)間 區(qū)間對(duì))對(duì)偶集合；T :結(jié)果或中間結(jié)果(時(shí)間區(qū)間對(duì))對(duì)偶集合； N(i,k,j): 表示i和j之間有一個(gè)中間約束區(qū)間k的約束關(guān)系集合；：表示累加約束是否 改變區(qū)間對(duì)之間的非重復(fù)約束關(guān)系集合內(nèi)容。(1)總體控制算法 給定一組(時(shí)間區(qū)間)事件 A ,1 乞n 給定區(qū)間對(duì)(A，Aj)的非重復(fù)約束關(guān)系集合N(i,j)，其中，i :： j 令 S 二和 T = , ： =0 S = d, j .h：i,j

15、G，其中仁 i ：上 n -d.j . S，令 T =T 一: i,j .，計(jì)算:i, j .的累加約束 NAdd(i, j)。IFN(i, j) = NAdd(i,j) THEN : =1 IF S = THEN轉(zhuǎn) IF : =0 THEN end. S=T，T =，: =0，轉(zhuǎn)(2) 計(jì)算兩個(gè)節(jié)點(diǎn)之間的累加約束 -k , IF (N(i,k)= )(N(k,j)=N(i,k)=， N(j,k)= N(k,i)-N(k, j) = THEN 計(jì)算 N '(min( i, j),k,max(i, j)完成合成約束 IF k THEN end. 設(shè)i ： j，構(gòu)造新的約束關(guān)系集合N

16、9;'(i,j)二N'(i,k, j)。其中，求交集時(shí)k要注意：若關(guān)系甲 N'(i,a,j)，關(guān)系乙 N'(i,b,j)，關(guān)系甲包關(guān)系含乙，則關(guān)系乙 N'(i,a, j) N'(i,b,j)，關(guān)系甲 N'(i,a,j)N'(i,b,j)。 IF N''(i, jH THEN出現(xiàn)矛盾，結(jié)束整個(gè)算法，退出推理過(guò)程。 IF N(i,j)二 THEN N(i, jHN''(i,j)，結(jié)束算法，返回。 令 N(i, j)二 N(i,j) N''(i, j) IF N(i,j)二'THE

17、N出現(xiàn)矛盾，結(jié)束整個(gè)算法，退出推理過(guò)程。 結(jié)束算法，返回。(3) 計(jì)算合成約束設(shè)任務(wù)為求解N'(i,k, j) N'(i,k, j)二，通過(guò)必要的逆關(guān)系替換(原關(guān)系)，將兩個(gè)輸入集合(見(jiàn)累加約束算法)變換成N(i,k)和N(k,j)的形式 IF N(i,k)THEN轉(zhuǎn)ELSE通過(guò)必要的逆關(guān)系把輸出集 N'(i,k,j) 改為N'(min(i, j), k,max(i, j)的形式，結(jié)束算法，返回。 自N(i,k)中取一個(gè)約束R (即時(shí)間區(qū)間關(guān)系) 對(duì)N(k, j)的每個(gè)約束R'，按照Allen關(guān)系表構(gòu)造合成約束R R'，并置入N'(i,k

18、, j)中 轉(zhuǎn)算法說(shuō)明(1):從非形式化故事情節(jié)總結(jié)出的時(shí)間關(guān)系，往往不是唯一的。因?yàn)椋行┘?xì)節(jié)可能沒(méi)有交代。所以，一條弧線上可能標(biāo)注多個(gè)關(guān)系。約束累加的目的就是通過(guò)多方約束剔除弧線上的不合適關(guān)系。例如：對(duì)“包龍圖請(qǐng)寇準(zhǔn)”，如果寇準(zhǔn)馬上答應(yīng)，則有關(guān)系 AmA，如果寇準(zhǔn) 需要考慮后才能回答，則有關(guān)系 人：代，另外，如果寇準(zhǔn)已經(jīng)察覺(jué)陳世美的不 法行為，因此，未等到包龍圖來(lái)請(qǐng)他，他就開(kāi)始偵察，則又有關(guān)系A(chǔ)3 A,?？梢?jiàn)，一條弧線上可能有多個(gè)關(guān)系存在。算法說(shuō)明(2)：交集為空表明約束出現(xiàn)矛盾。例如：A疳A2，A2 ： A3，A3疳A，則 N'(1,2,3) = ，N(1,3) = ，則 N&#

19、39;(1,2,3)N(1,3)='，即表示時(shí)間是不能循環(huán)的。算法說(shuō)明(3)：任何一個(gè)時(shí)間關(guān)系都有一個(gè)逆關(guān)系存在，因此，在表示中，往往并不需要把兩種關(guān)系都羅列出來(lái)。3-1-4-2 Allen方法的不足(1)考察如下情節(jié)“當(dāng)?shù)胰式芴M(jìn)陳世美的宅院時(shí)正好陳世美不在家”?？捎萌齻€(gè)事件表示之：A :狄仁杰跳進(jìn)陳世美宅院；(<,m, mi,>) - A1-(0, m)T AA，:陳世美在自己的宅院里；A :狄仁杰在陳世美的宅院里；其網(wǎng)絡(luò)關(guān)系如右圖所示?？梢?jiàn)， A和A2之間，A和A之間的可能關(guān)系不是唯一的。設(shè)T為合成約束，則合成約束集合 N'(3,1,2)的運(yùn)算如下：T(oi,

20、 ：)二：,o,m,di,ei，T(oi,m) =o,di ,ei，T(oi,mi)二 ，T(oi, )= T(mi, ：)= ：,o,m,di ,ei， T(mi,m) = b,bi, =， T(mi,mi)= ，T(mi, )= 由合成算法得N'(3,1,2) =,o,m,di,b,bi,ei, =，即A和A之間的關(guān)系通過(guò)A 連接起來(lái)時(shí)，可能有9種情形！如： 狄仁杰在陳世美家時(shí)，陳世美還沒(méi)有回家，等了一會(huì)兒，他就走了； 陳世美一直在家，剛好狄仁杰要來(lái)時(shí)陳世美就走了； 狄仁杰在陳世美家，等了一會(huì)，陳世美回來(lái)了，兩人爭(zhēng)執(zhí)了一會(huì)兒，狄仁 杰走了； 狄仁杰在陳世美家時(shí)，陳世美不在，但，他剛

21、離開(kāi)陳世美就回來(lái)了； 狄仁杰來(lái)陳世美家時(shí)，陳世美已經(jīng)在家，兩人爭(zhēng)執(zhí)了一會(huì)兒，狄仁杰走了； 狄仁杰剛到陳世美家，陳世美就回來(lái)了，兩人爭(zhēng)執(zhí)了一會(huì)兒，狄仁杰走了； 陳世美剛回來(lái)，狄仁杰就來(lái)了，兩人爭(zhēng)執(zhí)起來(lái)，一會(huì)，陳世美跑了； 狄仁杰到陳世美家時(shí)，陳世美正好在家，兩人爭(zhēng)執(zhí)起來(lái)，最后，他們一起 到皇帝那里評(píng)理去了； 狄仁杰到陳世美家時(shí)，陳世美也正好回來(lái)，兩人爭(zhēng)執(zhí)起來(lái)，最后，他們一 起到皇帝那里評(píng)理去了。(2)增加一個(gè)情節(jié)后的結(jié)果“陳世美回到了自己的宅院”則有如下幾種可能: 狄仁杰跳進(jìn)宅院地上，陳世美就回來(lái)了，兩人爭(zhēng)執(zhí)起來(lái)，狄隨后離去 狄仁杰等了一會(huì)，陳世美來(lái)了。陳責(zé)怪狄不該私闖他人宅院，狄隨后離去 狄仁

22、杰等了一會(huì)，陳世美來(lái)了。陳見(jiàn)狄私自進(jìn)自己的宅院大怒，揚(yáng)言要面 君告狀，轉(zhuǎn)身進(jìn)宮去了。此時(shí)，A和A之間增加了新的約束b,o,di。取其和原來(lái)的合成約束集合N(2,3)(二 N'(2,1,3)的交集，得新的 N(2,3) =bi,oi,d注：N(2,3)為 N(3,2)之逆關(guān)系集人-(o,m)T 民-(o,b,di)T A合?？紤]右圖的約束傳遞關(guān)系，其合成約束N'(1,3,2)的計(jì)算如下：T(o,o) = ：,o,m , T(o,b)=o , T(o,di) = ：,o, m,diT(m,o) =： , T(m,b)=m , T(m,di) = ：所以，N'(1,3,2)

23、= ：,o,m,di。與原來(lái)的 N(1,2) = ：,m,mi, .之交集為：N(1,2) =N'(1,3,2)N(1,2) = :,m可見(jiàn)，另外兩種可能mi, 被排除了！即不是：并非陳世美先在自己的宅院， 然后狄仁杰跳進(jìn)去；也不是陳世美一離開(kāi)宅院，狄仁杰馬上就跳進(jìn)去。分析：常識(shí)推斷可知，排除mi, 是沒(méi)有道理的，因?yàn)椋愂烂揽隙ㄔ诩彝?留過(guò)。原因在于：他假定每個(gè)事件只能位于一個(gè)時(shí)間區(qū)間，而不能位于多個(gè)時(shí)間區(qū)間。女口： Allen沒(méi)有考慮到陳世美經(jīng)常(每天晚上)在宅院里，又經(jīng)常(白天) 不在宅院里的情形。3-1-4-3 Allen 方法的改進(jìn)1. 改進(jìn)1定義3-1-4-2對(duì)事件增加一元

24、關(guān)系f。令A(yù)為時(shí)間區(qū)間所代表的事件，則fA表 示A可以多次出現(xiàn)。由此，可導(dǎo)出如下 語(yǔ)義擴(kuò)充：1) 若fA2成立，fA1不成立，則A1RA2表示A和A2的某個(gè)出現(xiàn)有R關(guān)系。2) 若R是這樣一個(gè)關(guān)系，R和Rn是其子關(guān)系，則 ARA?表示A和A2的 第一個(gè)出現(xiàn)之間有R關(guān)系，ARnA2表示A和A2的最后一個(gè)出現(xiàn)之間有 R關(guān)系。3) 若fA和fA2都成立，則ARA表示A的某個(gè)出現(xiàn)和A?的某個(gè)出現(xiàn)之間 有R關(guān)系。4) 若R是這樣一個(gè)關(guān)系，Rj,i,j =0,1,n為其子關(guān)系。其中，下標(biāo) 0代表 某一個(gè)，1代表第一個(gè)，n代表最后一個(gè)。例如：A,R01A2表示A|的某個(gè)出現(xiàn)與A2的第一個(gè)出現(xiàn)之間有關(guān)系R， A

25、,R1n A2表示A 的第一個(gè)出現(xiàn)與A2的最后一個(gè)出現(xiàn)之間有關(guān)系 R，ARooA二ARA2。在一元關(guān)系f擴(kuò)充下，事件A2 (陳世美在自己的宅院里) 表示為f2，在網(wǎng) 絡(luò)關(guān)系外觀上沒(méi)有變化，但語(yǔ)義將發(fā)生變化。如： N(1,2)中的JA2表 示該集合之某種關(guān)系的某次出現(xiàn)。而 N(1,2)可以擴(kuò)展為如下形式表達(dá)所有情形：N (1,2) :-1 ,., n , mii,min , mi ,., mn , 1' n 。增加新事實(shí)“陳世美回到了自己的宅院”，經(jīng)類似推理計(jì)算可得N'(1,3,2) =：n,On,mn。顯然，該事實(shí)是 A的最后一次出現(xiàn)！同理，N(1,2) =N'(1,3

26、,2)N(1,2)。問(wèn)題：原來(lái)的2n種可能 1 ., n ,mi1 ,.,min依然被排除了。原因：定義3-1-2-2并沒(méi)有考慮到語(yǔ)義擴(kuò)充后交集運(yùn)算的不合理性，不能反映事件多次出現(xiàn)時(shí)關(guān)系的多樣性。2. 改進(jìn)2定義3-1-4-3如果兩個(gè)事件A和A2之間任何一個(gè)都不排斥另一個(gè)，則稱其為關(guān)系矛盾關(guān)系<An，min，mn，On，Oin，bn，bin，en，ein，dn，din，=n>向1,0,0,03, bi1,G,ei1,d1,di1,=1=<i,>n,min, mi,o,oi,b,bi,e,ei,d,di致的，否則，稱其為不一致的表3-1-4-2部分矛盾關(guān)系3.算法的修改對(duì)

27、時(shí)間區(qū)間多次出現(xiàn)時(shí)法的修改:的約束計(jì)算算法描述：(1)對(duì)計(jì)算累加約束算假設(shè):假定：為任意的關(guān)系集合，則-定義為:- - -x|xw：；, y,x和y不矛盾，或 x，：,Ty三用，x和y不矛盾對(duì)任意的關(guān)系集組f k，k定義為：k二x|x ,-j, y. >j,x和y不矛盾，其中,i = j,仁 i, j 乞 n k M 構(gòu)造 N''(i, j) N'(i,k, j)k M 令 N(i,j) =N(i, j)N'(i,j)(2)對(duì)計(jì)算合成約束算法的修改 M對(duì)N(k, j)中的每個(gè)約束R'，構(gòu)造合成約束R R'，并將它們置入N'(i,k,

28、 j) 中。注：無(wú)論fA成立與否，以上對(duì)累加約束和合成約束的計(jì)算算法改進(jìn)都是有效的。當(dāng)其不成立時(shí)，運(yùn)算相當(dāng)于求交集運(yùn)算。計(jì)算實(shí)例：對(duì) N(1,2)工 ：!，., ：n，mi1,.,min，mi,.,mn，n和 N'(1,3,2) = ：n,On,mn的 約束合成。N'(1,3,2)中的：<n 與 N(1,2)中的：i,., ：n,mii,.,mi n J > mi>.> min，1,., n不矛盾；On 與mii,.,min“ 1,., n不矛盾；mn與mii,.,min4, 1,., n不矛盾；由前面改進(jìn)算法的定義知，N'(1,3,2)的所有成

29、員都可以保留下來(lái)(-都有不 矛盾的約束關(guān)系存在)。又，N(1,2)中與N'(1,3,2)所有成員都有矛盾的關(guān)系只有 min, n。所以，最后的新N(1,2)為：N(1,2) = ：1,., ：n,mii,.,min4,mi,.,mn, 1,., nJ或簡(jiǎn)寫(xiě)為：N(1,2)門(mén):,mi -min, m, - n結(jié)論：弓I入以上改進(jìn)后，加入事實(shí)“陳世美回到了自己的宅院”，不是排除整 個(gè)關(guān)系，而只是排除了其中的最后一次出現(xiàn) n,min。顯然，這樣的表達(dá)能力更 強(qiáng)，也更能有效地表示相應(yīng)的故事情節(jié)。4. Freksa改進(jìn)(粗粒知識(shí)表示方法)定義3-1-4-3只有起點(diǎn)或終點(diǎn)的時(shí)間區(qū)間，稱之為 半?yún)^(qū)間

30、。例如：“陳世美離家以后杳無(wú)音信”（只有起點(diǎn)），“秦香蓮歷盡千辛萬(wàn)苦，找 到了陳世美”（只有終點(diǎn)）。注：起點(diǎn)和終點(diǎn)是一個(gè)長(zhǎng)度區(qū)間為零的事實(shí)。如“陳世美離家”，“秦香蓮找 到陳世美”。表3-1-4-1的半?yún)^(qū)間表示結(jié)果（Freksa關(guān)系表示）如圖 3-1-4-2。其中，主要 利用了 Allen區(qū)間關(guān)系的兩個(gè)性質(zhì)： Allen區(qū)間的終點(diǎn)始終大于起點(diǎn)。 ：,=關(guān)系具有傳遞性。注：教材圖3.3與陸汝鈐教材互相有沖突！定義3-1-4-4給定事件A和A2之間的任意兩個(gè)關(guān)系R和R2，如果其中一個(gè)可 以（通過(guò)縮短、拉長(zhǎng)和移動(dòng)）連續(xù)地變化為另一個(gè)而不通過(guò)第三個(gè)關(guān)系R3，則稱R和是相鄰的。例如：:和m是相鄰的，而:

31、和o不是相鄰的，因?yàn)?只需將A逐近向右移動(dòng) 就可達(dá)到m，而：:必須經(jīng)過(guò)m才能到達(dá)o。定義3-1-4-5 一組關(guān)系A(chǔ)，- A，An，人,，代，使得i，A和A彳相鄰。其中，1 豈n -1。則稱關(guān)系組A是鄰居。例如：:，m和o是鄰居，但：:和o不構(gòu)成鄰居。注：?jiǎn)蝹€(gè)關(guān)系和所有13種關(guān)系是鄰居的特例。定義3-1-4-6若鄰居中成員不只一個(gè)，則稱其為粗粒知識(shí)。注：Allen表示為細(xì)粒知識(shí)，F(xiàn)reksa表示為粗粒知識(shí)。單個(gè)關(guān)系不能構(gòu)成粗粒 知識(shí)。表3-1-4-2用半?yún)^(qū)間關(guān)系表示整區(qū)間關(guān)系t(A)+ <t(B) +t(A)+ = t(B)*t(Af>t(B) +t(A)+<t(B)-<

32、t(A) J(B) mt(A)<t(B) oeidi Jt(A) J(B) b=bit(A)F(B) deoit(A)"(B) mi>t(A)<t(B) +t(A)-=t(B) +t(A)ft(B) +定義3-1-4-7(Freksa粗粒知識(shí)關(guān)系)(1) AolB表示A比B老，或Byo A表示B比A年輕。其時(shí)間區(qū)間特征為t(A)- ：t(B)-。(2) AhhB表示A和B同日生，或BhhA表示B和A同日生。特征為t(A)-=t(B) -0(3) AsvB表示A比B后死，或BsbA表示B比A先死。特征為t(A) ' t(B) ' o(4) AttB表示

33、A和B同日死，或BttA表示B和A同日死。特征為t( A) = t(B)。(5) AprB表示A死在B出生之前，或BsdA表示B生在A死去之后。特征為t(A)譏-。(6) ActB表示A和B同時(shí)代，或BctA表示B和A同時(shí)代。特征為A B，。(7) AbdB表示A出生在B死去之前，或BbdA表示B死在A出生之后，特征 為 t(A)- <t(B)。利用以上關(guān)系，可推論出：(8) AobB表示A比B老，且比B先死，或BysA表示B比A年輕，且比A后死。特征為 t(A) ：t(B) t(A) ：t(B)。(9) AscB表示A和B同時(shí)代，且比B后死，BbcA表示B和A同時(shí)代，且比A先死。特征為

34、t(A)t(B/ A B- - o(10) AocB表示A比B老，且和B同時(shí)代，BycA表示B比A年輕，且和A同時(shí)代。特征為 t(A)、t(B) A B= - oAllen時(shí)間表示與Freksa時(shí)間表示之間的對(duì)應(yīng)關(guān)系分析：首先，對(duì)定義3-1-4-7作如下修改：(1)刪除定義中的第6、9、10類關(guān)系，即ct,sc,bc,oc, yc等五項(xiàng)。增加下列關(guān)系：AtoB表示A死時(shí)B正好出生，或BfrA表示B出生時(shí)A正好死去。其特征為t(A)'t(B)-則，F(xiàn)reksa時(shí)間關(guān)系和Allen時(shí)間關(guān)系的對(duì)應(yīng)關(guān)系如表 3-1-4-3所示sbttsvpr<oltomdboeidiJb=bihhdeoiyomi>bdfrsd表3-1-4-3 Freksa與Allen時(shí)間關(guān)系的對(duì)應(yīng)關(guān)系表定義3-1-4-8 F類關(guān)系f和A類關(guān)系a對(duì)應(yīng)的兩個(gè)矩 形