文習(xí)明 方良達(dá) 余泉 常亮 王駒

隨著深度學(xué)習(xí)等一系列機(jī)器學(xué)習(xí)算法的不斷完善，計(jì)算機(jī)逐漸具備了學(xué)習(xí)知識(shí)的能力。對(duì)于人類來說，除了具備不斷學(xué)習(xí)知識(shí)的能力，還具備策略性遺忘知識(shí)的能力。遺忘不僅僅意味著記憶的遺失，也是一個(gè)幫助大腦吸收新知識(shí)并有效做出決策的積極過程。如何讓計(jì)算機(jī)像人一樣具備遺忘的能力，目前仍然是人工智能所面臨的最大挑戰(zhàn)之一。遺忘在基于符號(hào)邏輯的知識(shí)表示與推理（KR：Knowledge representation and reasoning）領(lǐng)域和基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)領(lǐng)域都有研究。特別是在KR領(lǐng)域，遺忘扮演著非常重要的角色。

在KR領(lǐng)域，遺忘（forgetting）的思想最早可以追溯到1854年Boole提出的“消去（elimination）”（[4]）。其直觀含義是：從當(dāng)前理論中刪除某些信息，得到一個(gè)比原理論更弱的新理論，但在保留下來的信息范圍內(nèi)，新理論和原理論能夠推導(dǎo)出一致的邏輯結(jié)論。在命題邏輯，一階謂詞邏輯、模態(tài)邏輯、描述邏輯、回答集邏輯程序設(shè)計(jì)（ASP：answer set programming）以及情景演算（situation calculus）等邏輯語言中都有關(guān)于遺忘的研究。其被廣泛應(yīng)用于最弱充分條件和最強(qiáng)必要條件的計(jì)算（[10,26]），溯因推理（[26]），相關(guān)性分析（[14,24,27]），知識(shí)和信念的推理（[14,35]），沖突解決（[25,45]），本體分析與重用（[5,19–22,31–33,37,41–43,47]），信息隱藏（[31,42,47]），邏輯差異的判定（[21,42]），知識(shí)庫更新（[13,28–30,34,46]），ASP中的非單調(diào)推理（[9,11,18,38–40]）等諸多領(lǐng)域。

關(guān)于遺忘的理論研究，主要集中在兩個(gè)方面：可定義性問題和遺忘結(jié)果的計(jì)算問題。前者主要研究當(dāng)前理論用某種邏輯語言表示時(shí)，遺忘結(jié)果是否依然能用該邏輯語言來表示；后者主要研究如何計(jì)算遺忘之后所得的新理論。

遺忘作為一個(gè)邏輯概念首次由Lin和Reiter于1994年（[27]）在命題邏輯中正式提出。其中，Lin和Reiter基于模型理論給出了命題邏輯中遺忘原子命題的定義，證明了其可定義性，且給出了遺忘結(jié)果的計(jì)算方法。Lang等人將其擴(kuò)展到遺忘命題文字（literal）。（[24]）方良達(dá)和萬海等（[14]），以及林作銓教授和徐岱（[44]）等分別進(jìn)一步將其擴(kuò)展到遺忘命題公式。

模態(tài)邏輯適用于智能體的知識(shí)表示與推理。按照對(duì)知識(shí)的不同理解和要求，提出了不同的模態(tài)邏輯公理系統(tǒng)，其中較常用的正規(guī)模態(tài)邏輯系統(tǒng)有K，T，KD45，S4和S5等。（[15]）模態(tài)邏輯中區(qū)分客觀事實(shí)與主觀知識(shí)，其知識(shí)遺忘比命題邏輯中的變量遺忘要復(fù)雜的多，因?yàn)槊}邏輯只要處理客觀事實(shí)的遺忘問題，模態(tài)邏輯要同時(shí)處理客觀事實(shí)與主觀知識(shí)的遺忘問題。（[16]）而且在不同的模態(tài)邏輯公理系統(tǒng)中，遺忘還表現(xiàn)出不同的特性。已有研究成果表明，在K（[2,36]），T（[2]），KD45（[13]）和S5（[6,46]）中，知識(shí)遺忘是可定義的，但在S4中是不可定義的（[7]）。

為了適應(yīng)多智能體場景下的知識(shí)表示與推理，多智能體模態(tài)邏輯被提出。與單智能體模態(tài)邏輯系統(tǒng)相對(duì)應(yīng)，多智能體模態(tài)邏輯也有一些常用的正規(guī)公理系統(tǒng)：Kn、Tn、KD45n、S4n和S5n。由于高階知識(shí)（關(guān)于智能體知識(shí)的知識(shí)）的引入，多智能體模態(tài)邏輯中的知識(shí)遺忘變得更加復(fù)雜。方良達(dá)和劉詠梅等將知識(shí)遺忘擴(kuò)展到多智能體模態(tài)邏輯，并證明了知識(shí)遺忘在Kn，Tn，KD45n，和S5n是可定義的，在S4n中是不可定義的。（[12]）同時(shí)，Cate等在描述邏輯ALC中證明了統(tǒng)一插值的可定義性（[5]），鑒于ALC與模態(tài)邏輯的對(duì)應(yīng)關(guān)系（[1]）以及統(tǒng)一插值與知識(shí)遺忘的對(duì)偶關(guān)系（[33]），他們實(shí)質(zhì)上也給出了Kn中知識(shí)遺忘可定義的結(jié)論。

到目前為止，多智能體模態(tài)邏輯系統(tǒng)中的知識(shí)遺忘還無法有效計(jì)算。文獻(xiàn)[12]中，雖然給出了常用正規(guī)模態(tài)邏輯系統(tǒng)中知識(shí)遺忘的可定義性結(jié)果，但其知識(shí)遺忘計(jì)算效率非常低——非初等時(shí)間復(fù)雜度。這嚴(yán)重影響了知識(shí)遺忘的實(shí)際應(yīng)用。本文重點(diǎn)探討多智能體模態(tài)邏輯系統(tǒng)Kn中知識(shí)遺忘的計(jì)算問題。我們采用知識(shí)編譯（[8]）的思想，先將一般公式等價(jià)轉(zhuǎn)換為一種特殊的范式公式——Kn-DNF公式，然后再計(jì)算知識(shí)遺忘。該算法的時(shí)間復(fù)雜度是Kn-DNF公式長度的多項(xiàng)式時(shí)間。Kn系統(tǒng)是最小的正規(guī)多智能體模態(tài)邏輯公理系統(tǒng)，其它正規(guī)多智能模態(tài)邏輯系統(tǒng)都從它擴(kuò)展而來。雖然不同模態(tài)邏輯系統(tǒng)中知識(shí)遺忘的性質(zhì)和計(jì)算方法都不盡相同，但Kn系統(tǒng)中知識(shí)遺忘的研究對(duì)其它多智能模態(tài)邏輯系統(tǒng)中知識(shí)遺忘的研究依然具有借鑒意義。

文章后續(xù)部分結(jié)構(gòu)如下：第一部分，介紹本文研究相關(guān)的基礎(chǔ)知識(shí)；第二部分，分析Kn中知識(shí)遺忘的重要性質(zhì)；第三部分，按知識(shí)編譯的思路，提出Kn中有利于知識(shí)遺忘計(jì)算的范式公式；第四部分，給出Kn中知識(shí)遺忘的計(jì)算算法，證明其正確性，分析時(shí)間復(fù)雜度，并比較相關(guān)工作；最后，總結(jié)全文并指出進(jìn)一步的研究方向。

1 基礎(chǔ)知識(shí)

本章介紹與本文研究相關(guān)的基礎(chǔ)知識(shí)和一些符號(hào)記法。

1.1 多智能體模態(tài)邏輯

模態(tài)邏輯適用于智能體的知識(shí)表示與推理，我們參考文獻(xiàn)[15]定義多智能體模態(tài)邏輯的語法和語義。

P表示原子命題集，A表示n個(gè)智能體的集合。通常用i,j∈{1,...,n}來指代不同的智能體。

定義1([15]).多智能體模態(tài)邏輯語言L可遞歸定義如下：

。Ki表示“智能體i知道?”，Li?表示“智能體i認(rèn)為?有可能”。

多智能體模態(tài)邏輯語言L中的元素，稱為公式。形如Ki?的公式稱為正模態(tài)文字，形如Li?的公式稱為負(fù)模態(tài)文字。不包含模態(tài)文字的公式稱為客觀公式。所有客觀公式的集合，即為命題邏輯語言，記為Lp。var(?)表示公式?中出現(xiàn)的原子命題的集合。

通常用長度或深度來刻畫模態(tài)邏輯公式的復(fù)雜程度，它們的定義分別如下。

定義2([15]).給定公式?∈L，?的長度為符號(hào)集P∪{?,∧,K1,...,Kn}中的符號(hào)在?中出現(xiàn)的次數(shù)，記為|?|。

定義3([15]).在模態(tài)邏輯語言L中，公式?的深度d(?)為公式中模態(tài)算子的嵌套層數(shù)，其可遞歸定義如下：

多智能體模態(tài)邏輯的語義采用克里普克的可能世界語義（[23]），通過克里普克模型與多智能體模態(tài)邏輯公式之間的滿足關(guān)系給出。

定義4([15]).n個(gè)智能體的克里普克結(jié)構(gòu)是一個(gè)多元組M=(W,V,R1,...,Rn)，其中

?W是一個(gè)非空的可能世界集合；

?V:W →2P是一個(gè)賦值函數(shù)，指定在每個(gè)可能世界中哪些原子命題成立；

?Ri?W×W是W上的二元關(guān)系。

(w1,w2)∈Ri表明智能體i處于世界w1時(shí)，認(rèn)為可能處于世界w2。如果用有向圖來表示克里普克結(jié)構(gòu)，那么(w1,w2)就表現(xiàn)為一條從結(jié)點(diǎn)w1到w2的標(biāo)識(shí)為的i邊，因此Ri常被稱為可達(dá)關(guān)系。R=∪ni=1Ri，即所有智能體可達(dá)關(guān)系的并集，R?表示R的自反傳遞閉包。令Ri(w)={w′|(w,w′)∈Ri}表示在世界w時(shí)，智能體i認(rèn)為其可能所處世界的集合。類似地，R?(w)表示從w出發(fā)，所有可達(dá)世界的集合。

定義5([15]).n個(gè)智能體的克里普克模型是一個(gè)二元組(M,w)，其中M=(W,V,R1,...,Rn)是克里普克結(jié)構(gòu)，w∈W是可能世界之一，被稱為當(dāng)前世界。

定義6([15]).克里普克模型(M,w)滿足公式?∈L，記為(M,w)??，可遞歸定義如下：

(M,w)?p 當(dāng)且僅當(dāng) p∈V(w)

(M,w)??? 當(dāng)且僅當(dāng) (M,w)/??

(M,w)??∧φ 當(dāng)且僅當(dāng) (M,w)??且(M,w)?φ

(M,w)?Ki? 當(dāng)且僅當(dāng) 對(duì)任意w′∈W，如果(w,w′)∈R，則(M,w′)??

智能體i知道?（Ki?），當(dāng)且僅當(dāng)，在當(dāng)前世界下，所有他認(rèn)為可能的世界中?都成立；智能體i認(rèn)為?可能（Li?），當(dāng)且僅當(dāng)，在當(dāng)前世界下，存在一個(gè)他認(rèn)為可能的世界中?成立。我們用??φ表示公式?的所有模型都滿足公式φ，?≡φ表示φ??且??φ。

正規(guī)的多智能體模態(tài)邏輯系統(tǒng)，都必須滿足如下公理和推理規(guī)則：

A1所有命題邏輯中的公理；

A2 Ki? ∧ Ki(? ? φ)? Kiφ,i=1,...,n；

R1由?α和?α?β，可推導(dǎo)出?β；

R2由?α，可推導(dǎo)出?Kiα,i=1,...,n。

僅滿足上述公理和推理規(guī)則的公理系統(tǒng)稱為Kn系統(tǒng)。在此基礎(chǔ)上，根據(jù)對(duì)知識(shí)性質(zhì)的不同要求，擴(kuò)展出各種不同的公理系統(tǒng)，如Tn，KD45n，S4n和S5n等。（[15]）本文重點(diǎn)關(guān)注Kn公理系統(tǒng)。

1.2 Σ-互模擬

在模態(tài)邏輯的研究中，互模擬（bisimulation）是一個(gè)非常重要的概念（[3]），模態(tài)邏輯中知識(shí)遺忘的定義大都基于互模擬的擴(kuò)展——Σ-互模擬。我們參考文獻(xiàn)[12]定義多智能體模態(tài)邏輯中的Σ-互模擬。

原子條件V(v)?ΣV′(v′)；

其中V(v)?ΣV′(v′)表示可能世界v和v′中除了Σ中的命題之外，其它命題的賦值一致。

(M,w)?Σ(M′,w′)，即模型(M,w)和(M′,w′)在除了Σ中命題之外的命題上相互模擬。當(dāng)Σ=?時(shí)，Σ-互模擬實(shí)質(zhì)上就是互模擬，簡寫成(M,w)?(M′,w′)。顯然，Σ-互模擬關(guān)系是一個(gè)等價(jià)關(guān)系，即具有自反性、傳遞性和對(duì)稱性。Σ-互模擬具有如下重要特性。

命題1([12]).如果(M,w)?Σ(M′,w′)，給定公式?∈ L，var(?)∩Σ = ?，則(M,w)? ?當(dāng)且僅當(dāng)(M′,w′)? ?。

命題1表明：兩個(gè)克里普克模型Σ-互模擬，則它們滿足相同的不包含Σ中原子命題的公式。

定義8([3]).給定模型 (M,w)，M=(W,V,R1,...,Rn)和(M′,w)，M′=(W′,V′,R′1,...,R′n)，(M′,w)為(M,w)的生成子模型，當(dāng)滿足下列條件時(shí)：

(1)W′=R?(w)；

(2)V′(u)=V(u)，如果 u ∈ W′；

(3)R′i=Ri∩(W′×W′)。

(M,w)的生成子模型中僅考慮從可能世界w出發(fā)可達(dá)的可能世界，并保留它們之間的可達(dá)關(guān)系。

命題2([3]).若(M′,w)為(M,w)的生成子模型，則兩者互模擬(M,w)?(M′,w)。

1.3 變量遺忘

Lin和Reiter基于模型理論定義了命題邏輯中的變量遺忘。（[27]）模態(tài)邏輯中的知識(shí)遺忘在此基礎(chǔ)上發(fā)展起來，因此有必要介紹一下變量遺忘。

定義9([27]).給定命題邏輯的公式?∈Lp和原子命題p∈P，公式?′是公式?遺忘p的結(jié)果，記為?′≡Forget(?,p)，如果任意命題邏輯模型M，M ??′當(dāng)且僅當(dāng)存在模型M′??且M′?{p}M。

其中，M′?{p}M表示模型M′和M在P{p}上的真值指派一致。

命題3([27]).在命題邏輯中，若?′≡ Forget(?,p)，則?′≡ ?(p/?)∨?(p/⊥)。其中，?(p/?)和?(p/⊥)分別表示將公式?中的命題p分別用?和⊥統(tǒng)一替換之后的結(jié)果。

2 多智能體模態(tài)邏輯中的知識(shí)遺忘

文獻(xiàn)[12]將文獻(xiàn)[46]中單智能體模態(tài)邏輯系統(tǒng)S5中知識(shí)遺忘的定義擴(kuò)展到多智能體模態(tài)邏輯。在此基礎(chǔ)上，我們定義修正版的多智能體模態(tài)邏輯知識(shí)遺忘。

定義10.給定公式?∈L和原子命題p∈P，公式?′是公式?遺忘p的結(jié)果，記為?′≡KForget(?,p)，如果任意的模型(M,w)，(M,w)??′當(dāng)且僅當(dāng)存在模型(M′,w′)滿足 (M′,w′)? ? 且 (M,w)?{p}(M′,w′)。

為與命題邏輯中的變量遺忘區(qū)分，模態(tài)邏輯中的變量遺忘，特稱為“知識(shí)遺忘”，記為KForget。為簡單起見，我們定義的是遺忘一個(gè)原子命題p∈P。易證，遺忘一個(gè)原子命題集可以通過依次遺忘該集合中的原子命題來實(shí)現(xiàn)，且與遺忘的次序無關(guān)。在文獻(xiàn)[12]的定義中要求var(?′)?var(?){p}。我們的定義放棄了這一限制條件，后面會(huì)證明這原本就是我們定義的知識(shí)遺忘的性質(zhì)之一。

接下來，我們將系統(tǒng)分析在智能體模態(tài)邏輯系統(tǒng)Kn中知識(shí)遺忘的重要性質(zhì)。

命題4([46]).若? ∈ Lp，即?是客觀公式，p∈ P，則KForget(?,p)≡ Forget(?,p)。

該命題表明：命題邏輯中的變量遺忘實(shí)質(zhì)上是模態(tài)邏輯中知識(shí)遺忘的特例。

命題5.給定 ? ∈ L和 p∈ P，則KForget(Ki?,p)≡ Ki(KForget(?,p))，i=1,...,n。

證明.根據(jù)知識(shí)遺忘的定義可證，具體證明如下：

假定 (M,w)|=Ki(KForget(?,p))，M=(W,V,R1,...,Rn)，需證 (M,w)|=KKForget(?,p)，僅需證存在模型滿足公式Ki?且與模型(M,w)在除了p之外的命題上互模擬。由(M,w)|=Ki(KForget(?,p))可知，任意(w,v)∈Ri，均滿足 (M,v)? KForget(?,p)，即存在 (Mv,wv)? ?且 (Mv,wv)?{p}(M,v)，Mv=(Wv,Vv,Rv1,...,Rvn)。對(duì)所有這樣的v，將(M,v)的生成子模型分別用(Mv,wv)進(jìn)行替換，并假定不同的Wv之間相互獨(dú)立（彼此不相交），得到模型(M′,w)。易證 (M′,w)?{p}(M,w)且 (M′,w)? Ki?。

注意：若? ∈ Lp，則KForget(Ki?,p)≡ Ki(Forget(?,p))。當(dāng)?是一般的模態(tài)邏輯公式時(shí)，我們僅證明了在Kn中命題5成立；在其它公理系統(tǒng)中，KForget(Ki?,p)?Ki(KForget(?,p))成立，但目前還無法證明其反向是否成立。因?yàn)槠渌硐到y(tǒng)的克里普克模型中可達(dá)關(guān)系需滿足一定的性質(zhì)，上述模型構(gòu)成過程無法保證保持其可達(dá)關(guān)系的性質(zhì)。

命題6([46]).給定?1,?2∈L和p∈P，則：

(1) 若 ?1≡ ?2，則 KForget(?1,p)≡ K(Forget(?2,p))；

(2) 若 ?1? ?2，則 KForget(?1,p)? K(Forget(?2,p))；

(3)KForget(?1∨ ?2,p)≡ KForget(?1,p)∨ KForget(?2,p)；

(4)KForget(?1∧ ?2,p)? KForget(?1,p)∧ KForget(?2,p)。

結(jié)論(1)表明知識(shí)遺忘的結(jié)果具有邏輯唯一性；結(jié)論(2)表明知識(shí)遺忘保持邏輯蘊(yùn)涵關(guān)系；結(jié)論(3)表明知識(shí)遺忘操作對(duì)析取運(yùn)算滿足分配率；結(jié)論(4)表明知識(shí)遺忘操作對(duì)合取運(yùn)算并不滿足分配率，這給知識(shí)遺忘的計(jì)算帶來困難。例如：KForget(K1(p?q)∧K1(q?r),q)≡K1(p?r)，KForget(K1(p?q),q)≡?，KForget(K1(q? r),q)≡ ?，顯然KForget(K1(p? q)∧K1(q? r),q)與KForget(K1(p?q),p)∧KForget(K1(q?r),q)不等價(jià)。

定義11.給定?∈L和p∈P，若存在?′∈L，?≡?′且var(?′)∩{p}=?，則稱?與p不相關(guān)，記為IR(?,p)。

命題 7.給定 ?1,?2∈ L 和 p ∈ P，若 IR(?1,p)，則 KForget(?1∧?2,p)≡ ?1∧KForget(?2,p)。

命題7表明：從一個(gè)理論（有限個(gè)公式的集合）中遺忘命題p，與p不相關(guān)的部分不受影響。

文獻(xiàn)[46]提出了四個(gè)公設(shè)：弱化公設(shè)（W）、正保持公設(shè)（PP）、負(fù)保持公設(shè)（NP）和不相關(guān)公設(shè)（IR），刻畫了S5中知識(shí)遺忘的語義特征。下面我們將證明在Kn中知識(shí)遺忘依然滿足這些公設(shè)。

定理1.在多智能體模態(tài)邏輯Kn中，給定?1,?2∈ L和p∈ P，?2≡ KForget(?1,p)，則滿足如下條件：

(W)?1??2，即?2在邏輯上要比?1弱；

(PP)任意公式φ∈L，IR(φ,p)，若?1?φ，則?2?φ；

(NP) 任意公式 φ ∈ L，IR(φ,p)，若 ?1/? φ，則?2/? φ；

(IR)IR(?2,p)，即 ?2與 p不相關(guān)。

證明.根據(jù)知識(shí)遺忘定義和不相關(guān)的定義可證，具體證明如下：

(W)任意模型(M,w)??1，有(M,w)?{p}(M,w)。由定義10可知，(M,w)?KForget(?1,p)，故有 ?1? ?2。

(PP) 由?2≡ KForget(?1,p)可知，任意模型(M,w)? ?2，必存在模型(M′,w′)??1且 (M,w)?{p}(M′,w′)。由 ?1? φ 可知，(M′,w′)? φ。由 IR(φ,p)和(M,w)?{p}(M′,w′)以及命題1可知，(M,w)?φ。故有?2?φ。

(NP)若 ?1/? φ，則存在模型 (M,w)? ?1但 (M,w)/? φ。由 (M,w)? ?1和?2≡ KForget(?1,p)可知，存在 (M′,w′)? ?2且 (M,w)?{p}(M′,w′)。由IR(φ,p)和命題 1 可知，(M′,w′)/? φ。故有 ?2/? φ。

(IR)根據(jù)不相關(guān)的定義可知，要證IR(?2,p)只需證存在公式?′∈L，var(?′)∩{p}=?且?′≡ KForget(?1,p)。文獻(xiàn)[12]和[5]中已證明確實(shí)存在這樣的公式。

推論1.給定?1,?2∈L和p∈P，若?2≡ KForget(?1,p)，則對(duì)任意φ∈L且IR(φ,p)，?1? φ當(dāng)且僅當(dāng)?2? φ。

推論1表明從一個(gè)理論遺忘一個(gè)命題，所得新理論與原理論在與被遺忘命題無關(guān)的結(jié)論中，保持邏輯一致。

推論2.給定公式?∈L和p∈P，φ≡KForget(?,p)，則存在公式?′∈L，?′≡φ且 var(?′)? var(?){p}。

證明. 對(duì)任意 p′∈ Pvar(?)，有 IR(?,p′)。由命題 7 可知 ? ≡ KForget(?,p′)。令?′≡ KForget(KForget(?,p′),p)，即由 ? 依次遺忘 {p}∩Pvar(?)中的原子命題得到 ?′。顯然，?′≡ φ 且 var(?′)? var(?){p}。

推論2，充分說明在定義知識(shí)遺忘時(shí)，不必如[12]中那樣顯式約束var(?′)?var(?){p}。

命題8([12]).在Kn中，對(duì)任意公式?∈L和原子命題p∈P，均存在公式?′∈L使得 ?′≡ KForget(?,p)。

命題8表明：在多智能體模態(tài)邏輯Kn中，知識(shí)遺忘是可定義的。

3 Kn析取范式

由命題3可知，命題邏輯中的變量遺忘可以通過簡單的語法替換來計(jì)算。但是，該方法無法推廣到模態(tài)邏輯?？匆粋€(gè)簡單的例子：給定?=K1p∧?K1q∧?K1?q，顯然?(q/?)≡ ⊥和?(p/⊥)≡ ⊥，故而?(p/⊥)∨?(p/⊥)≡ ⊥，顯然KForget(?,q)不應(yīng)該是⊥。由命題6可知，由于知識(shí)遺忘操作對(duì)合取運(yùn)算并不滿足分配率，因此盡管有命題4和命題5的性質(zhì)，依然無法直接將模態(tài)邏輯中知識(shí)遺忘的計(jì)算轉(zhuǎn)換為命題邏輯中的變量遺忘來計(jì)算。文獻(xiàn)[46]在單智能體模態(tài)邏輯S5中，提出了一種析取范式（S5-DNF），通過將一般公式轉(zhuǎn)換成與之等價(jià)的析取范式，該范式公式的知識(shí)遺忘可以轉(zhuǎn)換成命題邏輯的變量遺忘來計(jì)算。但是，S5-DNF充分利用了S5模態(tài)邏輯系統(tǒng)中可達(dá)關(guān)系是等價(jià)關(guān)系的特性，無法擴(kuò)展到Kn系統(tǒng)。本章從有效計(jì)算知識(shí)遺忘的角度，提出Kn系統(tǒng)中的析取范式（Kn-DNF）。

定義12.Kn–析取范式，遞歸定義如下：

其中，B?A，φ∈Lp，δi和ηij均為Kn-DNF，且滿足對(duì)任意ηij均有ηij?δi。

命題9.對(duì)于任意的α,β,γ∈L，在Kn中下列等價(jià)式成立：

式(1)和(2)是德?摩根定律，式(3)是雙重否定律，式(4)和(5)是模態(tài)算子Ki和Li之間的對(duì)偶關(guān)系，式(6)是合取對(duì)析取的分配律，式(7)是正模態(tài)文字的合并，式(8)是正負(fù)模態(tài)文字的結(jié)合。當(dāng)然，在Kn中也滿足其它的等價(jià)式，例如：吸收率，結(jié)合律和交換律等，這里只列出我們所需的主要等價(jià)式。借助這些等價(jià)式，可將一般多智能體模態(tài)邏輯公式轉(zhuǎn)換成與之等價(jià)的Kn-DNF公式，具體算法參見算法1。

算法1.transfer(?)//將公式?∈L轉(zhuǎn)換為等價(jià)的Kn-DNF公式

輸入：?∈L

2.利用等價(jià)式(1)–(5)將?等價(jià)轉(zhuǎn)換為僅由正（負(fù)）模態(tài)文字和命題公式通過聯(lián)結(jié)詞∧或∨組成的公式?′;

5.return ?′′′(δi/transfer(δi),ηij/transfer(ηij));//遞歸調(diào)用該算法將 ?′′′中的子公式δi和ηij分別轉(zhuǎn)換為等價(jià)的Kn-DNF公式，進(jìn)行等價(jià)替換后返回

注意：在算法1中，經(jīng)過步驟2之后，否定（?）僅允許出現(xiàn)在命題公式的前面，但并不嚴(yán)格要求只出現(xiàn)在原子命題的前面；步驟3中利用的（合取對(duì)析取的）分配律和步驟4中利用的（正負(fù)模態(tài)文字的）結(jié)合律均會(huì)導(dǎo)致公式長度的增長，但導(dǎo)致公式長度增長的主要原因在步驟3，它會(huì)導(dǎo)致公式長度指數(shù)倍的增長，就像在命題邏輯中DNF公式的轉(zhuǎn)換過程一樣。步驟4僅導(dǎo)致公式長度多項(xiàng)式倍的增長。步驟1和2均可在公式長度的多項(xiàng)式時(shí)間內(nèi)完成。因此整個(gè)轉(zhuǎn)換算法的時(shí)間復(fù)雜度是公式長度的指數(shù)時(shí)間。

定理2.給定任意?∈L，均可等價(jià)轉(zhuǎn)換為Kn-DNF公式，且公式長度在最壞情況下是原公式長度的指數(shù)倍。

例1.? = ?(p∧?q)∧?(K1p∧K2q)∧K1(K2p∨K2?p)∧K2p∧K1r∧L2r,p,q,r∈ P。將?轉(zhuǎn)換為Kn-DNF公式。

根據(jù)定理2，雖然一般多智能體模態(tài)邏輯公式都可轉(zhuǎn)換為與之等價(jià)的Kn-DNF公式，但是會(huì)導(dǎo)致公式長度的增長，在最壞情況下，Kn-DNF公式相對(duì)于原公式在長度上可能會(huì)有單指數(shù)倍的膨脹。但我們會(huì)證明，Kn-DNF公式非常適用于知識(shí)遺忘的計(jì)算。

4 Kn中知識(shí)遺忘的計(jì)算

我們采用了知識(shí)編譯（[2]）的思想來計(jì)算Kn中的知識(shí)遺忘。主要思路是：首先將一般模態(tài)邏輯公式等價(jià)轉(zhuǎn)換成Kn-DNF公式，然后利用Kn-DNF公式計(jì)算知識(shí)遺忘的便利性，有效地計(jì)算知識(shí)遺忘。

4.1 知識(shí)遺忘計(jì)算定理

知識(shí)編譯是解決知識(shí)推理難問題的方法之一，其主要思想是：將源知識(shí)庫轉(zhuǎn)換成特定形式的知識(shí)庫（目標(biāo)知識(shí)庫）；在目標(biāo)知識(shí)庫中，一些推理問題會(huì)變得簡單易實(shí)現(xiàn)。其關(guān)鍵在針對(duì)特定的推理問題，選擇適合的目標(biāo)知識(shí)庫表示形式。我們提出的Kn-DNF公式就是易于計(jì)算知識(shí)遺忘的目標(biāo)知識(shí)庫形式。

定理3.給定任意Kn-DNF公式ξ，其知識(shí)遺忘KForget(ξ,p)可遞歸計(jì)算如下：

其中φ∈Lp，F(xiàn)orget(φ,p)表示命題邏輯中的變量遺忘；δi和ηij均為Kn-DNF公式，且對(duì)任意ηij均有ηij?δi。

證明.定理中的(1)–(3)項(xiàng)顯然成立，這里僅對(duì)(4)加以證明，具體證明如下：

由定理3知，一個(gè)Kn-DNF公式知識(shí)遺忘的結(jié)果依然是一個(gè)Kn-DNF公式。這有利于后續(xù)知識(shí)遺忘的計(jì)算。

4.2 算法與復(fù)雜度分析

由定理3可知，Kn-DNF公式的知識(shí)遺忘可以高效計(jì)算。由定理2可知，任意多智能體模態(tài)邏輯公式均可等價(jià)轉(zhuǎn)換為Kn-DNF公式，又由命題6可知，若兩個(gè)公式等價(jià)，則其知識(shí)遺忘也等價(jià)。因此，不難給出Kn系統(tǒng)中一般公式的知識(shí)遺忘計(jì)算算法，具體參見算法2。

算法2.Kn系統(tǒng)中知識(shí)遺忘的計(jì)算

輸入：?∈L和p∈P

輸出：KForget(?,p)

1.將?等價(jià)轉(zhuǎn)換成Kn-DNF公式?′=transfer(?);

2.計(jì)算 KForget(?′,p);

3.return KForget(?′,p);

算法2即可實(shí)現(xiàn)Kn系統(tǒng)中一般公式知識(shí)遺忘的計(jì)算方法，其正確性由定理2，定理3以及命題6可證。步驟1（即知識(shí)編譯）時(shí)間復(fù)雜度為|?|的指數(shù)時(shí)間，步驟 2 時(shí)間復(fù)雜度為 |?′|的多項(xiàng)式時(shí)間，由于 |?′|=2O(|?|·log|?|)，因此整個(gè)算法的時(shí)間復(fù)雜度為2O(|?|·log|?|)，即原公式長度的指數(shù)時(shí)間。知識(shí)編譯僅需做一次，就可供多次知識(shí)遺忘計(jì)算使用。在多次計(jì)算知識(shí)遺忘時(shí)，知識(shí)編譯的時(shí)間開銷會(huì)得到一定的補(bǔ)償。

例2.在Kn系統(tǒng)中，給定公式?=(p?q)∧K1(q∧K2r∨?q∧K2?r)∧L1(q?r)，計(jì)算 KForget(?,q)。

首先，?≡(p?q)∧K1(q∧K2r∨?q∧K2?r)∧L1(q∧r∧K2r∨?q∧K2?r)；

接著，KForget(?,q)≡ K1(K2r∨K2?r)∧L1(r∧K2r∨K2?r)。

4.3 相關(guān)工作

文獻(xiàn)[12]中，證明了包括Kn在內(nèi)的一些常用正規(guī)模態(tài)邏輯系統(tǒng)中知識(shí)遺忘的可定義性，但其知識(shí)遺忘計(jì)算效率非常低——為非初等時(shí)間復(fù)雜度。

Janin和Walukiewicz提出了另一種多智能體模態(tài)邏輯析取范式公式，被稱為覆蓋析取范式公式（CDNF：cover disjunctive normal formula，[17]），研究結(jié)果表明該析取范式也適合知識(shí)遺忘的計(jì)算。（[5,17]）

定義13([17]).給定智能體集合A和公式Φ?L集合，覆蓋模態(tài)算子?，i∈A可定義為：

(M,w)??iΦ，當(dāng)且僅當(dāng)w在M 中的直接Ri后繼v滿足且僅滿足Φ中的公式，即Φ中覆蓋了w的直接Ri后繼可滿足的公式。故模態(tài)算子?i也被稱為“覆蓋模態(tài)算子”。顯然?i{?}≡?，?i{⊥}≡⊥，?i?≡Ki⊥。

定義14([17]).覆蓋析取公式，可遞歸定義如下：

其中，π是一致的命題文字合取，Φ1,...,Φn均為覆蓋析取公式的有限集合。

所有CDNF公式的集合記為LCDNF。已有研究結(jié)果表明：任意模態(tài)邏輯公式，均可等價(jià)轉(zhuǎn)換成CDNF公式，在最壞情況下，可能會(huì)導(dǎo)致公式長度單指數(shù)倍的膨脹。（[5]）

命題10([5]).給定任意CDNF公式ξ，其知識(shí)遺忘KForget(ξ,p)可遞歸計(jì)算如下：

(1)KForget(?,p)≡ ?；

(2)KForget(⊥,p)≡ ⊥；

從π中刪除與p相關(guān)文字（p或?p）之后的命題文字合取。

定義15.給定邏輯語言L和L′，如果對(duì)于任意的?′∈L′，均存在?∈L，滿足?≡?′且|?|≤f(|?′|)，其中f:N→N是多項(xiàng)式函數(shù)，則稱L至少和L′一樣簡潔（succinct），記為 L ≤ L′。

如果L≤L′且L′/≤L，則稱L比L′簡潔，記為L

例3.借助CDNF公式計(jì)算例2中的KForget(?,q)。

從例2和例3可知，將一般公式轉(zhuǎn)換成Kn-DNF或CDNF之后，均可計(jì)算其知識(shí)遺忘，且兩者所得結(jié)果邏輯等價(jià)（CDNF公式與一般公式之間的轉(zhuǎn)換參考文獻(xiàn) [5]）。不難看出，即使采用 ?iΦ 作為 ∧φ∈ΦLiφ∧Ki(Vφ∈Φφ)的縮寫，Kn-DNF公式比CDNF公式仍要簡潔得多。而且采用Kn-DNF公式可以避免部分子公式知識(shí)遺忘的重復(fù)計(jì)算。

5 結(jié)論與展望

本文在多智能體模態(tài)邏輯系統(tǒng)Kn中，對(duì)知識(shí)遺忘進(jìn)一步展開研究。系統(tǒng)分析了知識(shí)遺忘的重要性質(zhì)；基于知識(shí)編譯，提出一種Kn系統(tǒng)中知識(shí)遺忘計(jì)算的有效算法，與已有算法相比，我們的算法更高效。Kn是最小的正規(guī)多智能體模態(tài)邏輯系統(tǒng)，其它正規(guī)多智能模態(tài)邏輯系統(tǒng)都在其基礎(chǔ)上擴(kuò)展而來。盡管不同模態(tài)邏輯系統(tǒng)中知識(shí)遺忘的性質(zhì)和計(jì)算方法都不盡相同，但本文的研究對(duì)其它多智能模態(tài)邏輯系統(tǒng)中知識(shí)遺忘的研究依然具有借鑒意義。

下一步研究，一方面將考慮引入包括公共知識(shí)（common Knowledge）和分布知識(shí)（distributed Knowledge）在內(nèi)的群體知識(shí)之后，知識(shí)遺忘的計(jì)算問題。另一方面，將繼續(xù)探討在其他多智能體模態(tài)邏輯系統(tǒng)（如：KD45n，S5n）中的知識(shí)遺忘計(jì)算問題。