多智能体模态逻辑系统Kn中的知识遗忘论文

多智能体模态逻辑系统K_n中的知识遗忘

文习明 方良达 余泉 常亮 王驹

摘 要： 如何让智能体像人一样具备遗忘的能力，目前仍然是人工智能所面临的最大挑战之一。遗忘在基于符号逻辑的知识表示与推理领域和基于统计的机器学习领域都有研究。特别在知识表示与推理领域，遗忘扮演着非常重要的角色。在命题逻辑、一阶谓词逻辑、模态逻辑、描述逻辑、回答集逻辑程序设计，以及情景演算等逻辑语言中都有大量的研究。模态逻辑适用于智能体的知识表示与推理。在模态逻辑中，知识遗忘首先在单智能体场景中被提出。随着多智能体系统研究的发展，多智能体模态逻辑中知识遗忘的研究也开始被关注。到目前为止，多智能体模态逻辑系统中的知识遗忘还无法有效计算。本文在多智能体模态逻辑系统K_n中对知识遗忘进一步展开研究。采用知识编译的思想，提出一种新的多智能体模态逻辑范式K_n-DNF。基于K_n-DNF，我们给出K_n中计算知识遗忘的有效算法，其时间复杂度是K_n-DNF公式长度的多项式时间。

关键词： 多智能体模态逻辑；知识推理；知识编译；知识遗忘

随着深度学习等一系列机器学习算法的不断完善，计算机逐渐具备了学习知识的能力。对于人类来说，除了具备不断学习知识的能力，还具备策略性遗忘知识的能力。遗忘不仅仅意味着记忆的遗失，也是一个帮助大脑吸收新知识并有效做出决策的积极过程。如何让计算机像人一样具备遗忘的能力，目前仍然是人工智能所面临的最大挑战之一。遗忘在基于符号逻辑的知识表示与推理（KR：Knowledge representation and reasoning）领域和基于统计的机器学习领域都有研究。特别是在KR领域，遗忘扮演着非常重要的角色。

在KR领域，遗忘（forgetting）的思想最早可以追溯到1854年Boole提出的“消去（elimination）”（[4]）。其直观含义是：从当前理论中删除某些信息，得到一个比原理论更弱的新理论，但在保留下来的信息范围内，新理论和原理论能够推导出一致的逻辑结论。在命题逻辑，一阶谓词逻辑、模态逻辑、描述逻辑、回答集逻辑程序设计（ASP：answer set programming）以及情景演算（situation calculus）等逻辑语言中都有关于遗忘的研究。其被广泛应用于最弱充分条件和最强必要条件的计算（[10,26]），溯因推理（[26]），相关性分析（[14,24,27]），知识和信念的推理（[14,35]），冲突解决（[25,45]），本体分析与重用（[5,19–22,31–33,37,41–43,47]），信息隐藏（[31,42,47]），逻辑差异的判定（[21,42]），知识库更新（[13,28–30,34,46]），ASP中的非单调推理（[9,11,18,38–40]）等诸多领域。

关于遗忘的理论研究，主要集中在两个方面：可定义性问题和遗忘结果的计算问题。前者主要研究当前理论用某种逻辑语言表示时，遗忘结果是否依然能用该逻辑语言来表示；后者主要研究如何计算遗忘之后所得的新理论。

遗忘作为一个逻辑概念首次由Lin和Reiter于1994年（[27]）在命题逻辑中正式提出。其中，Lin和Reiter基于模型理论给出了命题逻辑中遗忘原子命题的定义，证明了其可定义性，且给出了遗忘结果的计算方法。Lang等人将其扩展到遗忘命题文字（literal）。（[24]）方良达和万海等（[14]），以及林作铨教授和徐岱（[44]）等分别进一步将其扩展到遗忘命题公式。

模态逻辑适用于智能体的知识表示与推理。按照对知识的不同理解和要求，提出了不同的模态逻辑公理系统，其中较常用的正规模态逻辑系统有K，T，KD45，S4和S5等。（[15]）模态逻辑中区分客观事实与主观知识，其知识遗忘比命题逻辑中的变量遗忘要复杂的多，因为命题逻辑只要处理客观事实的遗忘问题，模态逻辑要同时处理客观事实与主观知识的遗忘问题。（[16]）而且在不同的模态逻辑公理系统中，遗忘还表现出不同的特性。已有研究成果表明，在K（[2,36]），T（[2]），KD45（[13]）和S5（[6,46]）中，知识遗忘是可定义的，但在S4中是不可定义的（[7]）。

前向条件 对于任意u∈W 和i∈A，如果(v,u)∈R_i，则存在u^′∈W^′满足且(u,u^′)∈ρ；

到目前为止，多智能体模态逻辑系统中的知识遗忘还无法有效计算。文献[12]中，虽然给出了常用正规模态逻辑系统中知识遗忘的可定义性结果，但其知识遗忘计算效率非常低——非初等时间复杂度。这严重影响了知识遗忘的实际应用。本文重点探讨多智能体模态逻辑系统K_n中知识遗忘的计算问题。我们采用知识编译（[8]）的思想，先将一般公式等价转换为一种特殊的范式公式——K_n-DNF公式，然后再计算知识遗忘。该算法的时间复杂度是K_n-DNF公式长度的多项式时间。K_n系统是最小的正规多智能体模态逻辑公理系统，其它正规多智能模态逻辑系统都从它扩展而来。虽然不同模态逻辑系统中知识遗忘的性质和计算方法都不尽相同，但K_n系统中知识遗忘的研究对其它多智能模态逻辑系统中知识遗忘的研究依然具有借鉴意义。

文章后续部分结构如下：第一部分，介绍本文研究相关的基础知识；第二部分，分析K_n中知识遗忘的重要性质；第三部分，按知识编译的思路，提出K_n中有利于知识遗忘计算的范式公式；第四部分，给出K_n中知识遗忘的计算算法，证明其正确性，分析时间复杂度，并比较相关工作；最后，总结全文并指出进一步的研究方向。

1 基础知识

本章介绍与本文研究相关的基础知识和一些符号记法。

1.1 多智能体模态逻辑

模态逻辑适用于智能体的知识表示与推理，我们参考文献[15]定义多智能体模态逻辑的语法和语义。

P表示原子命题集，A表示n个智能体的集合。通常用i,j∈{1,...,n}来指代不同的智能体。

定义1 ([15]).多智能体模态逻辑语言L可递归定义如下：

其中，p∈P，i∈A，⊥表示逻辑“假”。逻辑“真”（⊤），“析取”（∨）和“蕴涵”（⊃）分别可定义如下：。

多智能体模态逻辑是在命题逻辑的基础上引入多个模态算子 K_i（i∈A）扩展而成。此外，还有一类与K_i对偶的模态算子L_i，其定义如下：

。K_i表示“智能体i知道ϕ”，L_iϕ表示“智能体i认为ϕ有可能”。

多智能体模态逻辑语言L中的元素，称为公式。形如K_iϕ的公式称为正模态文字 ，形如L_iϕ的公式称为负模态文字 。不包含模态文字的公式称为客观公式 。所有客观公式的集合，即为命题逻辑语言，记为L^p。var(ϕ)表示公式ϕ中出现的原子命题的集合。

通常用长度 或深度 来刻画模态逻辑公式的复杂程度，它们的定义分别如下。

定义2 ([15]).给定公式ϕ∈L，ϕ的长度为符号集P∪{¬,∧,K₁,...,K_n}中的符号在ϕ中出现的次数，记为|ϕ|。

第二天一大早，我还没有醒，就听到妈妈在嚷：“死丫头！看来今天我不收拾你一顿，你就不知道你姓啥了！”骂谁呢？我赶紧穿上衣服，睡眼惺忪地走了出去，看到眼前的一幕，我完全醒了：那一排吊死鬼，竟然是一衣架的新衣服，那画中鬼，竟是妈妈新挂上的画《蒙娜丽莎》。我愣住了。不好，赶紧跑！这时，妈妈已经拿着鸡毛掸子气势汹汹地追了，不一会儿，我就被捉住了，狠狠地被收拾了一顿。这时，我才埋怨起自己的“傻大胆”来。心里想，回学校后，一定找说世界上有鬼的人算账去。

定义3 ([15]).在模态逻辑语言L中，公式ϕ的深度d(ϕ)为公式中模态算子的嵌套层数，其可递归定义如下：

多智能体模态逻辑的语义采用克里普克的可能世界语义（[23]），通过克里普克模型与多智能体模态逻辑公式之间的满足关系给出。

定义4 ([15]).n个智能体的克里普克结构是一个多元组M=(W,V,R₁,...,R_n)，其中

•W是一个非空的可能世界集合；

•V:W →2^P是一个赋值函数，指定在每个可能世界中哪些原子命题成立；

* Correspondence: J Lin, E-mail: Jiao.Lin@osamember.org; X C Yuan, E-mail: xcyuan@szu.edu.cn

•R_i⊆W×W是W上的二元关系。

(w₁,w₂)∈R_i表明智能体i处于世界w₁时，认为可能处于世界w₂。如果用有向图来表示克里普克结构，那么(w₁,w₂)就表现为一条从结点w₁到w₂的标识为的i边，因此R_i常被称为可达关系。R=∪_ni=1R_i，即所有智能体可达关系的并集，R^∗表示R的自反传递闭包。令R_i(w)={w^′|(w,w^′)∈R_i}表示在世界w时，智能体i认为其可能所处世界的集合。类似地，R^∗(w)表示从w出发，所有可达世界的集合。

定义5 ([15]).n个智能体的克里普克模型是一个二元组(M,w)，其中M=(W,V,R₁,...,R_n)是克里普克结构，w∈W是可能世界之一，被称为当前世界。

定义6 ([15]).克里普克模型(M,w)满足公式ϕ∈L，记为(M,w)⊨ϕ，可递归定义如下：

(M,w)⊨p 当且仅当 p∈V(w)

(M,w)⊨¬ϕ 当且仅当 (M,w)/⊨ϕ

(M,w)⊨ϕ∧φ 当且仅当 (M,w)⊨ϕ且(M,w)⊨φ

(M,w)⊨K_iϕ 当且仅当 对任意w^′∈W，如果(w,w^′)∈R，则(M,w^′)⊨ϕ

智能体i知道ϕ（K_iϕ），当且仅当，在当前世界下，所有他认为可能的世界中ϕ都成立；智能体i认为ϕ可能（L_iϕ），当且仅当，在当前世界下，存在一个他认为可能的世界中ϕ成立。我们用ϕ⊨φ表示公式ϕ的所有模型都满足公式φ，ϕ≡φ表示φ⊨ϕ且ϕ⊨φ。

笔者在广泛调研国内外掘进机工作特点的基础上，设计了用于掘进机模拟试验平台且可对掘进机所有状态与参数进行动态显示的监控系统，另外搭建了可对各种掘进机位姿检测方法进行验证与对比的高精度掘进机位姿测量精度验证系统。选取了具有代表性的位姿测量方法开展掘进机位姿测量试验，对系统的功能进行验证，并分析了位姿测量精度验证系统的实用性。

R2由⊢α，可推导出⊢K_iα,i=1,...,n。

A2 K_iϕ ∧ K_i(ϕ ⊃ φ)⊃ K_iφ,i=1,...,n；

R1由⊢α和⊢α⊃β，可推导出⊢β；

正规的多智能体模态逻辑系统，都必须满足如下公理和推理规则：

A1所有命题逻辑中的公理；

仅满足上述公理和推理规则的公理系统称为K_n系统。在此基础上，根据对知识性质的不同要求，扩展出各种不同的公理系统，如T_n，KD45_n，S4_n和S5_n等。（[15]）本文重点关注K_n公理系统。

1.2 Σ-互模拟

在模态逻辑的研究中，互模拟（bisimulation）是一个非常重要的概念（[3]），模态逻辑中知识遗忘的定义大都基于互模拟的扩展——Σ-互模拟。我们参考文献[12]定义多智能体模态逻辑中的Σ-互模拟。

按照“放管服”改革的统一部署，本规定对船载危险货物所涉及的行政许可事项进行了必要的调整。一是将船舶载运危险货物进出港口许可中的危险货物安全适运申报，由许可制调整为报告制；二是按照上位法的规定，将船舶载运危险货物过驳作业许可的适用范围，调整为船舶在港口水域外从事内河危险货物过驳作业或者海上散装液体污染危害性货物过驳作业。同时，本规定进一步明确了负有安全生产主体责任的托运人和承运人的安全责任，对海事管理机构事中、事后监督管理作出了规定。

定义7 ([12]).给定克里普克模型(M,w),M=(W,V,R₁,...,R_n)和(M^′,w^′),M^′=，原子命题集Σ⊆P。(M,w)和(M^′,w^′)之间Σ-互模拟，记为 (M,w)↔_Σ(M^′,w^′)，当存在二元关系 ρ ⊆ W ×W^′，(w,w^′)∈ ρ，且任意(v,v^′)∈ρ满足如下条件：

结论(1)表明知识遗忘的结果具有逻辑唯一性；结论(2)表明知识遗忘保持逻辑蕴涵关系；结论(3)表明知识遗忘操作对析取运算满足分配率；结论(4)表明知识遗忘操作对合取运算并不满足分配率，这给知识遗忘的计算带来困难。例如：KForget(K₁(p⊃q)∧K₁(q⊃r),q)≡K₁(p⊃r)，KForget(K₁(p⊃q),q)≡⊤，KForget(K₁(q⊃ r),q)≡ ⊤，显然KForget(K₁(p⊃ q)∧K₁(q⊃ r),q)与KForget(K₁(p⊃q),p)∧KForget(K₁(q⊃r),q)不等价。

安娜对待爱情就很真诚很纯粹，当然，也很极端。没有爱情的时候，她的生命里就只有她的儿子谢廖沙和无休无止的社交活动，遭遇爱情之后，就只剩下爱情了。随着安娜陷入越来越深地偏执和沉迷，她的情郎渥伦斯基开始渐渐感到疲倦，因此安娜的焦虑也就与日俱增。安娜选择卧轨自杀之前，精神曾一度处于崩溃的边缘，但同时她的潜意识就更加清晰地浮现出来了：“我的爱情越来越强烈，越来越自私，而他的却越来越减退，这就是使我们分离的原因③”“在我，一切都以他为中心，我要求他越来越完完全全地献身于我，但他却越来越想疏远我……我不是嫉妒，而是不满足④。”尽管安娜也有过片刻地理智和清醒，但爱情之火烧到尽头，死亡在所难免。

原子条件 V(v)≃_ΣV^′(v^′)；

为了适应多智能体场景下的知识表示与推理，多智能体模态逻辑被提出。与单智能体模态逻辑系统相对应，多智能体模态逻辑也有一些常用的正规公理系统：K_n、T_n、KD45_n、S4_n和S5_n。由于高阶知识（关于智能体知识的知识）的引入，多智能体模态逻辑中的知识遗忘变得更加复杂。方良达和刘咏梅等将知识遗忘扩展到多智能体模态逻辑，并证明了知识遗忘在K_n，T_n，KD45_n，和S5_n是可定义的，在S4_n中是不可定义的。（[12]）同时，Cate等在描述逻辑ALC中证明了统一插值的可定义性（[5]），鉴于ALC与模态逻辑的对应关系（[1]）以及统一插值与知识遗忘的对偶关系（[33]），他们实质上也给出了K_n中知识遗忘可定义的结论。

反向条件 对于任意u^′∈W^′和i∈A，如果，则存在u∈W 满足(v,u)∈ R_i且 (u,u^′)∈ ρ；

其中V(v)≃_ΣV^′(v^′)表示可能世界v和v^′中除了Σ中的命题之外，其它命题的赋值一致。

(M,w)↔_Σ(M^′,w^′)，即模型(M,w)和(M^′,w^′)在除了Σ中命题之外的命题上相互模拟。当Σ=∅时，Σ-互模拟实质上就是互模拟，简写成(M,w)↔(M^′,w^′)。显然，Σ-互模拟关系是一个等价关系，即具有自反性、传递性和对称性。Σ-互模拟具有如下重要特性。

命题1 ([12]).如果(M,w)↔_Σ(M^′,w^′)，给定公式ϕ∈ L，var(ϕ)∩Σ = ∅，则(M,w)⊨ ϕ当且仅当(M^′,w^′)⊨ ϕ。

命题1表明：两个克里普克模型Σ-互模拟，则它们满足相同的不包含Σ中原子命题的公式。

定义8 ([3]).给定模型 (M,w)，M=(W,V,R₁,...,R_n)和(M^′,w)，M^′=(W^′,V^′,R^′₁,...,R^′_n)，(M^′,w)为(M,w)的生成子模型，当满足下列条件时：

(1)W^′=R^∗(w)；

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

(3)R^′_i=R_i∩(W^′×W^′)。

(M,w)的生成子模型中仅考虑从可能世界w出发可达的可能世界，并保留它们之间的可达关系。

命题2 ([3]).若(M^′,w)为(M,w)的生成子模型，则两者互模拟(M,w)↔(M^′,w)。

1.3 变量遗忘

Lin和Reiter基于模型理论定义了命题逻辑中的变量遗忘。（[27]）模态逻辑中的知识遗忘在此基础上发展起来，因此有必要介绍一下变量遗忘。

区内岩浆活动强烈，北部以幕阜山燕山早期花岗岩为主，其岩性主要为粗中粒斑状黑云母二长花岗岩、片麻状粗中粒斑状黑云母二长花岗岩。幕阜山燕山早期花岗岩与冷家溪群片岩的接触带呈东西向曲折延伸，接触面倾向南，倾角 25° –35°，接触面与流面产状大致平行，呈波浪式起伏，向南部凸起。矿区东南部出露有雪峰期花岗岩体，出露面积较小，岩性为中细粒-细粒斑状黑云母花岗岩，包括梅仙岩体、三墩岩体、钟洞岩体及传梓源岩体（如图2)。

定义9 ([27]).给定命题逻辑的公式ϕ∈L^p和原子命题p∈P，公式ϕ^′是公式ϕ遗忘p的结果，记为ϕ^′≡Forget(ϕ,p)，如果任意命题逻辑模型M，M ⊨ϕ^′当且仅当存在模型M^′⊨ϕ且M^′≃_{p}M。

Similarly to the first round, significantly more female participants completed both first and second FIT rounds in comparison to male participants (16 of 95 or 16.8%vs 8 of 116 or 6.8%, P = 0.05).

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

命题3 ([27]).在命题逻辑中，若ϕ^′≡ Forget(ϕ,p)，则ϕ^′≡ ϕ(p/⊤)∨ϕ(p/⊥)。其中，ϕ(p/⊤)和ϕ(p/⊥)分别表示将公式ϕ中的命题p分别用⊤和⊥统一替换之后的结果。

2 多智能体模态逻辑中的知识遗忘

文献[12]将文献[46]中单智能体模态逻辑系统S5中知识遗忘的定义扩展到多智能体模态逻辑。在此基础上，我们定义修正版的多智能体模态逻辑知识遗忘。

定义10. 给定公式ϕ∈L和原子命题p∈P，公式ϕ^′是公式ϕ遗忘p的结果，记为ϕ^′≡KForget(ϕ,p)，如果任意的模型(M,w)，(M,w)⊨ϕ^′当且仅当存在模型(M^′,w^′)满足 (M^′,w^′)⊨ ϕ 且 (M,w)↔_{p}(M^′,w^′)。

为与命题逻辑中的变量遗忘区分，模态逻辑中的变量遗忘，特称为“知识遗忘”，记为KForget。为简单起见，我们定义的是遗忘一个原子命题p∈P。易证，遗忘一个原子命题集可以通过依次遗忘该集合中的原子命题来实现，且与遗忘的次序无关。在文献[12]的定义中要求var(ϕ^′)⊆var(ϕ)\{p}。我们的定义放弃了这一限制条件，后面会证明这原本就是我们定义的知识遗忘的性质之一。

接下来，我们将系统分析在智能体模态逻辑系统K_n中知识遗忘的重要性质。

命题4 ([46]).若ϕ ∈ L^p，即ϕ是客观公式，p∈ P，则KForget(ϕ,p)≡ Forget(ϕ,p)。

该命题表明：命题逻辑中的变量遗忘实质上是模态逻辑中知识遗忘的特例。

对比各个省市，可以发现，各省市的ZX值差距略微明显。2014-2016年间，天津、西藏、上海、山东、浙江、广东、江苏、北京的ZX值均大于0.500，效率处于中等以上水平。其余省份ZX值均小于0.500，效率值处于较低水平，另外，云南、内蒙古、甘肃省、新疆、黑龙江三年间排名均在后六位，效率水平处于最后位。可见，各个省市的效率水平存在明显区域差距，效率处于不同水平的省市发展较为稳定。

命题5 .给定 ϕ ∈ L和 p∈ P，则KForget(K_iϕ,p)≡ K_i(KForget(ϕ,p))，i=1,...,n。

证明.根据知识遗忘的定义可证，具体证明如下：

任意(M,w)⊨ KForget(K_iϕ,p)，M=(W,V,R₁,...,R_n)，均存在 (M^′,w^′)⊨ K_iϕ且 (M,w) ↔_{p}(M^′,w^′)，其中。对任意，均有(M^′,v^′)⊨ ϕ。由Σ-互模拟的定义可知，任意(w,v)∈ R_i，均存在且 (M^′,v^′) ↔_{p}(M,v)。由 (M^′,v^′) ⊨ ϕ 和 (M^′,v^′) ↔_{p}(M,v)可知 (M,v) ⊨KForget(ϕ,p)，从而 (M,w)|=K_i(KForget(ϕ,p))。故有 KForget(K_iϕ,p)|=K_i(K Forget(ϕ,p))。

假定 (M,w)|=K_i(KForget(ϕ,p))，M=(W,V,R₁,...,R_n)，需证 (M,w)|=KKForget(ϕ,p)，仅需证存在模型满足公式K_iϕ且与模型(M,w)在除了p之外的命题上互模拟。由(M,w)|=K_i(KForget(ϕ,p))可知，任意(w,v)∈R_i，均满足 (M,v)⊨ KForget(ϕ,p)，即存在 (M^v,w^v)⊨ ϕ且 (M^v,w^v)↔_{p}(M,v)，M^v=(W^v,V^v,R^v₁,...,R^v_n)。对所有这样的v，将(M,v)的生成子模型分别用(M^v,w^v)进行替换，并假定不同的W^v之间相互独立（彼此不相交），得到模型(M^′,w)。易证 (M^′,w)↔_{p}(M,w)且 (M^′,w)⊨ K_iϕ。

(2) 若 ϕ₁⊨ ϕ₂，则 KForget(ϕ₁,p)⊨ K(Forget(ϕ₂,p))；

注意：若ϕ ∈ L^p，则KForget(K_iϕ,p)≡ K_i(Forget(ϕ,p))。当ϕ是一般的模态逻辑公式时，我们仅证明了在K_n中命题5成立；在其它公理系统中，KForget(K_iϕ,p)⊨K_i(KForget(ϕ,p))成立，但目前还无法证明其反向是否成立。因为其他公理系统的克里普克模型中可达关系需满足一定的性质，上述模型构成过程无法保证保持其可达关系的性质。

命题6 ([46]).给定ϕ₁,ϕ₂∈L和p∈P，则：

(1) 若 ϕ₁≡ ϕ₂，则 KForget(ϕ₁,p)≡ K(Forget(ϕ₂,p))；

三是群体利益诉求的延伸。网络中有一类群体是以讨伐个人或集体利益为目标而集中的一个群体，这样的群体往往以知识型成员为主导者，通过有理有据的说明方式使群众信服，号召更多人参与进来。声势浩大的群体容易加剧社会问题，发酵微小的社会事件，引起全社会的关注。

(3)KForget(ϕ₁∨ ϕ₂,p)≡ KForget(ϕ₁,p)∨ KForget(ϕ₂,p)；

到了火车站，我们看见那个女孩儿正和她的家人在一起说着话。舒曼一个人拿着吉他和行李站在离她稍远些的地方。他的行李很简单，不像一个远行的人，孤凄地看着周围一家家送行的场面。

(4)KForget(ϕ₁∧ ϕ₂,p)⊨ KForget(ϕ₁,p)∧ KForget(ϕ₂,p)。

进一步使用10 μmol/L OHT刺激干扰PGRN表达的耐药细胞MCF-7R和T47DR 48 h，FCM法检测结果（图4C～D）显示，与阴性对照组相比，敲低PGRN表达后，再用OHT处理，原本耐药的MCF-7R和T47DR细胞的凋亡率明显升高（t值分别为5.212和7.023，P值均＜0.01）。

古代:① 过去距离现代较远的时代,在我国历史分期上多指19世纪中叶以前;② 特指奴隶社会时代(有时也包括原始公社时代)。

定义11. 给定ϕ∈L和p∈P，若存在ϕ^′∈L，ϕ≡ϕ^′且var(ϕ^′)∩{p}=∅，则称ϕ与p不相关，记为IR(ϕ,p)。

命题 7. 给定 ϕ₁,ϕ₂∈ L 和 p ∈ P，若 IR(ϕ₁,p)，则 KForget(ϕ₁∧ϕ₂,p)≡ ϕ₁∧KForget(ϕ₂,p)。

临沭地瓜生产区域为山东省临沭县境内(118°26′～118°48′E，34°40′～35°06′N)，包括临沭街道、郑山街道、青云镇、玉山镇、蛟龙镇、石门镇、大兴镇、店头镇、曹庄镇，共计9个镇(街道办事处)的地瓜生产村。生产规模10 000 hm2，年产量45万t。

命题7表明：从一个理论（有限个公式的集合）中遗忘命题p，与p不相关的部分不受影响。

文献[46]提出了四个公设：弱化公设（W）、正保持公设（PP）、负保持公设（NP）和不相关公设（IR），刻画了S5中知识遗忘的语义特征。下面我们将证明在K_n中知识遗忘依然满足这些公设。

定理1. 在多智能体模态逻辑K_n中，给定ϕ₁,ϕ₂∈ L和p∈ P，ϕ₂≡ KForget(ϕ₁,p)，则满足如下条件：

(W)ϕ₁⊨ϕ₂，即ϕ₂在逻辑上要比ϕ₁弱；

(PP)任意公式φ∈L，IR(φ,p)，若ϕ₁⊨φ，则ϕ₂⊨φ；

(NP) 任意公式 φ ∈ L，IR(φ,p)，若 ϕ₁/⊨ φ，则ϕ₂/⊨ φ；

(IR)IR(ϕ₂,p)，即 ϕ₂与 p不相关。

证明.根据知识遗忘定义和不相关的定义可证，具体证明如下：

(W)任意模型(M,w)⊨ϕ₁，有(M,w)↔_{p}(M,w)。由定义10可知，(M,w)⊨KForget(ϕ₁,p)，故有 ϕ₁ ⊨ ϕ₂。

(PP) 由ϕ₂≡ KForget(ϕ₁,p)可知，任意模型(M,w)⊨ ϕ₂，必存在模型(M^′,w^′)⊨ϕ₁且 (M,w)↔_{p}(M^′,w^′)。由 ϕ₁⊨ φ 可知，(M^′,w^′)⊨ φ。由 IR(φ,p)和(M,w)↔_{p}(M^′,w^′)以及命题1可知，(M,w)⊨φ。故有ϕ₂⊨φ。

(NP)若 ϕ₁/⊨ φ，则存在模型 (M,w)⊨ ϕ₁但 (M,w)/⊨ φ。由 (M,w)⊨ ϕ₁和ϕ₂≡ KForget(ϕ₁,p)可知，存在 (M^′,w^′)⊨ ϕ₂且 (M,w)↔_{p}(M^′,w^′)。由IR(φ,p)和命题 1 可知，(M^′,w^′)/⊨ φ。故有 ϕ₂/⊨ φ。

(IR)根据不相关的定义可知，要证IR(ϕ₂,p)只需证存在公式ϕ^′∈L，var(ϕ^′)∩{p}=∅且ϕ^′≡ KForget(ϕ₁,p)。文献[12]和[5]中已证明确实存在这样的公式。

推论1. 给定ϕ₁,ϕ₂∈L和p∈P，若ϕ₂≡ KForget(ϕ₁,p)，则对任意φ∈L且IR(φ,p)，ϕ₁⊨ φ当且仅当ϕ₂⊨ φ。

推论1表明从一个理论遗忘一个命题，所得新理论与原理论在与被遗忘命题无关的结论中，保持逻辑一致。

推论2. 给定公式ϕ∈L和p∈P，φ≡KForget(ϕ,p)，则存在公式ϕ^′∈L，ϕ^′≡φ且 var(ϕ^′)⊆ var(ϕ)\{p}。

证明. 对任意 p^′∈ P\var(ϕ)，有 IR(ϕ,p^′)。由命题 7 可知 ϕ ≡ KForget(ϕ,p^′)。令ϕ^′≡ KForget(KForget(ϕ,p^′),p)，即由 ϕ 依次遗忘 {p}∩P\var(ϕ)中的原子命题得到 ϕ^′。显然，ϕ^′≡ φ 且 var(ϕ^′)⊆ var(ϕ)\{p}。

推论2，充分说明在定义知识遗忘时，不必如[12]中那样显式约束var(ϕ^′)⊆var(ϕ)\{p}。

命题8 ([12]).在K_n中，对任意公式ϕ∈L和原子命题p∈P，均存在公式ϕ^′∈L使得 ϕ^′≡ KForget(ϕ,p)。

命题8表明：在多智能体模态逻辑K_n中，知识遗忘是可定义的。

3 K_n析取范式

由命题3可知，命题逻辑中的变量遗忘可以通过简单的语法替换来计算。但是，该方法无法推广到模态逻辑。看一个简单的例子：给定ϕ=K₁p∧¬K₁q∧¬K₁¬q，显然ϕ(q/⊤)≡ ⊥和ϕ(p/⊥)≡ ⊥，故而ϕ(p/⊥)∨ϕ(p/⊥)≡ ⊥，显然KForget(ϕ,q)不应该是⊥。由命题6可知，由于知识遗忘操作对合取运算并不满足分配率，因此尽管有命题4和命题5的性质，依然无法直接将模态逻辑中知识遗忘的计算转换为命题逻辑中的变量遗忘来计算。文献[46]在单智能体模态逻辑S5中，提出了一种析取范式（S5-DNF），通过将一般公式转换成与之等价的析取范式，该范式公式的知识遗忘可以转换成命题逻辑的变量遗忘来计算。但是，S5-DNF充分利用了S5模态逻辑系统中可达关系是等价关系的特性，无法扩展到K_n系统。本章从有效计算知识遗忘的角度，提出K_n系统中的析取范式（K_n-DNF）。

定义12. K_n–析取范式，递归定义如下：

其中，B⊆A，φ∈L^p，δ_i和η_ij均为K_n-DNF，且满足对任意η_ij均有η_ij⊨δ_i。

φ∧∧_i∈B(K_iδ_i∧^∧_jL_iη_ij)表示：在合取式中，合取项分为三类：命题公式φ∈L^p，正模态文字K_iδ_i，负模态文字L_iη_ij。若在合取式中包含与智能体i∈A相关的模态文字合取项，则i∈B；否则，i/∈B。当i∈B时，最多包含一个与i相关的正模态文字合取项，可包含若干与之相关的负模态文字合取项，用∧_jLiηij表示与i相关的若干负模态文字的合取。当合取式中仅包含与i相关的负模态文字合取项，不包含与之相关的正模态文字合取项时，可看作K_i⊤作为正模态文字合取项。所有K_n-DNF公式的集合记为，显然。

命题9. 对于任意的α,β,γ∈L，在K_n中下列等价式成立：

式(1)和(2)是德•摩根定律，式(3)是双重否定律，式(4)和(5)是模态算子K_i和L_i之间的对偶关系，式(6)是合取对析取的分配律，式(7)是正模态文字的合并，式(8)是正负模态文字的结合。当然，在K_n中也满足其它的等价式，例如：吸收率，结合律和交换律等，这里只列出我们所需的主要等价式。借助这些等价式，可将一般多智能体模态逻辑公式转换成与之等价的K_n-DNF公式，具体算法参见算法1。

算法1. transfer(ϕ)//将公式ϕ∈L转换为等价的K_n-DNF公式

输入：ϕ∈L

输出：

1.return ϕ;//如果ϕ是K_n-DNF公式，就直接返回

2.利用等价式(1)–(5)将ϕ等价转换为仅由正（负）模态文字和命题公式通过联结词∧或∨组成的公式ϕ^′;

3.利用等价式(6)，将ϕ^′等价转换为由形如ψ的析取项构成的析取式ϕ^′′;//ϕ^′′中的析取项由命题公式，正（负）模态文字的合取构成

4.利用等价式(7)和(8)，将ϕ^′′等价转换为由形如的析取项构成的析取式ϕ^′′′;//ϕ^′′′中的析取项最多包含一个与i相关的正模态文字，可包含若干与之相关的负模态文字，且η_ij⊨δ_i

5.return ϕ^′′′(δ_i/transfer(δ_i),η_ij/transfer(η_ij));//递归调用该算法将 ϕ^′′′中的子公式δ_i和η_ij分别转换为等价的K_n-DNF公式，进行等价替换后返回

注意：在算法1中，经过步骤2之后，否定（¬）仅允许出现在命题公式的前面，但并不严格要求只出现在原子命题的前面；步骤3中利用的（合取对析取的）分配律和步骤4中利用的（正负模态文字的）结合律均会导致公式长度的增长，但导致公式长度增长的主要原因在步骤3，它会导致公式长度指数倍的增长，就像在命题逻辑中DNF公式的转换过程一样。步骤4仅导致公式长度多项式倍的增长。步骤1和2均可在公式长度的多项式时间内完成。因此整个转换算法的时间复杂度是公式长度的指数时间。

定理2.给定任意ϕ∈L，均可等价转换为K_n-DNF公式，且公式长度在最坏情况下是原公式长度的指数倍。

证明.由命题9可知，算法1中采用的均为等价转换或等价替换，故ϕ=transfer(ϕ)。由算法 1可知 。根据模态逻辑公式ϕ的定义，可递归证明|transfer(ϕ)=2^{O(|ϕ|·log|ϕ|)}|。定理得证。

例1. ϕ = ¬(p∧¬q)∧¬(K₁p∧K₂q)∧K₁(K₂p∨K₂¬p)∧K₂p∧K₁r∧L₂r,p,q,r∈ P。将ϕ转换为K_n-DNF公式。

根据定理2，虽然一般多智能体模态逻辑公式都可转换为与之等价的K_n-DNF公式，但是会导致公式长度的增长，在最坏情况下，K_n-DNF公式相对于原公式在长度上可能会有单指数倍的膨胀。但我们会证明，K_n-DNF公式非常适用于知识遗忘的计算。

4 K_n中知识遗忘的计算

我们采用了知识编译（[2]）的思想来计算K_n中的知识遗忘。主要思路是：首先将一般模态逻辑公式等价转换成K_n-DNF公式，然后利用K_n-DNF公式计算知识遗忘的便利性，有效地计算知识遗忘。

4.1 知识遗忘计算定理

知识编译是解决知识推理难问题的方法之一，其主要思想是：将源知识库转换成特定形式的知识库（目标知识库）；在目标知识库中，一些推理问题会变得简单易实现。其关键在针对特定的推理问题，选择适合的目标知识库表示形式。我们提出的K_n-DNF公式就是易于计算知识遗忘的目标知识库形式。

定理3. 给定任意K_n-DNF公式ξ，其知识遗忘KForget(ξ,p)可递归计算如下：

其中φ∈L^p，Forget(φ,p)表示命题逻辑中的变量遗忘；δ_i和η_ij均为K_n-DNF公式，且对任意η_ij均有η_ij⊨δ_i。

证明.定理中的(1)–(3)项显然成立，这里仅对(4)加以证明，具体证明如下：

令(1)假定(M,w)⊨ ξ，则存在且(M^′,w^′)↔_{p}(M,w)。由(M^′,w^′)⊨ φ知，(M,w)⊨ Forget(φ,p)。由(M^′,w^′)⊨ K_iδ_i知，(M,w)⊨KForget(K_iδ_i,p)。由命题 5 知，(M,w) ⊨ K_iKForget(δ_i,p)。由 (M^′,w^′) ⊨ L_iη_ij知，(M,w)⊨ KForget(L_iη_ij,p)，进而 (M,w)⊨ L_iKForget(η_ij,p)。故 (M,w)⊨ ζ，从而ξ⊨ζ。

(2)假定 (M,w)⊨ ζ，M=(W,V,R₁,...,R_n)，要证 (M,w)⊨ ξ，只需证存在模型 且 (M^′,w^′) ↔_{p}(M,w)。由(M,w)⊨ Forget(φ,p)可知，w ⊨ Forget(φ,p)，存在 w^′⊨ φ 且 V(w)≃_ΣV^′(w^′)。由(M,w)⊨L_iKForget(η_ij,p)可知，存在v_ij∈W 使得(w,v_ij)∈R_i且(M,v_ij)⊨KForget(η_ij,p)，故存在模型 (M^ij,u^ij)⊨ η_ij且 (M,v^ij)↔_{p}(M^ij,u^ij)。令Q是所有这样v_ij的集合。若R_i(w)\Q/= ∅，则对任意 a∈R_i(w)\Q，均有(M,a) ⊨ KForget(δ_i,p)，则存在模型 (M^ia,u^ia) ⊨ δ_i且 (M,a) ↔_{p}(M^ia,u^ia)。由上述w^′，(M^ij,u^ij)和(M^ia,u^ia)可构造出模型(M^′,w^′)，其在w^′和(M^ij,u^ij)及(M^ia,u^ia)不相交合并（disjoint unions）（[7]）的基础上添加(w^′,u^ij)与(w^′,u^ia)这些 i边构成。由构造过程可知，(M^′,w^′)↔_{p}(M,w)，且由 η_ij⊨ δ_i可知。

由定理3知，一个K_n-DNF公式知识遗忘的结果依然是一个K_n-DNF公式。这有利于后续知识遗忘的计算。

4.2 算法与复杂度分析

由定理3可知，K_n-DNF公式的知识遗忘可以高效计算。由定理2可知，任意多智能体模态逻辑公式均可等价转换为K_n-DNF公式，又由命题6可知，若两个公式等价，则其知识遗忘也等价。因此，不难给出K_n系统中一般公式的知识遗忘计算算法，具体参见算法2。

算法2. K_n系统中知识遗忘的计算

输入：ϕ∈L和p∈P

输出：KForget(ϕ,p)

1.将ϕ等价转换成K_n-DNF公式ϕ^′=transfer(ϕ);

2.计算 KForget(ϕ^′,p);

3.return KForget(ϕ^′,p);

算法2即可实现K_n系统中一般公式知识遗忘的计算方法，其正确性由定理2，定理3以及命题6可证。步骤1（即知识编译）时间复杂度为|ϕ|的指数时间，步骤 2 时间复杂度为 |ϕ^′|的多项式时间，由于 |ϕ^′|=2^{O(|ϕ|·log|ϕ|)}，因此整个算法的时间复杂度为2^{O(|ϕ|·log|ϕ|)}，即原公式长度的指数时间。知识编译仅需做一次，就可供多次知识遗忘计算使用。在多次计算知识遗忘时，知识编译的时间开销会得到一定的补偿。

例2. 在K_n系统中，给定公式ϕ=(p⊃q)∧K₁(q∧K₂r∨¬q∧K₂¬r)∧L₁(q⊃r)，计算 KForget(ϕ,q)。

首先，ϕ≡(p⊃q)∧K₁(q∧K₂r∨¬q∧K₂¬r)∧L₁(q∧r∧K₂r∨¬q∧K₂¬r)；

接着，KForget(ϕ,q)≡ K₁(K₂r∨K₂¬r)∧L₁(r∧K₂r∨K₂¬r)。

4.3 相关工作

文献[12]中，证明了包括K_n在内的一些常用正规模态逻辑系统中知识遗忘的可定义性，但其知识遗忘计算效率非常低——为非初等时间复杂度。

Janin和Walukiewicz提出了另一种多智能体模态逻辑析取范式公式，被称为覆盖析取范式公式（CDNF：cover disjunctive normal formula，[17]），研究结果表明该析取范式也适合知识遗忘的计算。（[5,17]）

定义13 ([17]).给定智能体集合A和公式Φ⊆L集合，覆盖模态算子∇，i∈A可定义为：

(M,w)⊨∇_iΦ，当且仅当w在M 中的直接R_i后继v满足且仅满足Φ中的公式，即Φ中覆盖了w的直接R_i后继可满足的公式。故模态算子∇_i也被称为“覆盖模态算子”。显然∇_i{⊤}≡⊤，∇_i{⊥}≡⊥，∇_i∅≡K_i⊥。

定义14 ([17]).覆盖析取公式，可递归定义如下：

其中，π是一致的命题文字合取，Φ₁,...,Φ_n均为覆盖析取公式的有限集合。

所有CDNF公式的集合记为L_CDNF。已有研究结果表明：任意模态逻辑公式，均可等价转换成CDNF公式，在最坏情况下，可能会导致公式长度单指数倍的膨胀。（[5]）

命题10 ([5]).给定任意CDNF公式ξ，其知识遗忘KForget(ξ,p)可递归计算如下：

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

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

(3)KForget(ϕ ∨φ,p)≡ KForget(ϕ,p)∨ KForget(φ,p)；(4)，其中 π^′为

从π中删除与p相关文字（p或¬p）之后的命题文字合取。

定义15. 给定逻辑语言L和L^′，如果对于任意的ϕ^′∈L^′，均存在ϕ∈L，满足ϕ≡ϕ^′且|ϕ|≤f(|ϕ^′|)，其中f:N→N是多项式函数，则称L至少和L^′一样简洁（succinct），记为 L ≤ L^′。

如果L≤L^′且L^′/≤L，则称L比L^′简洁，记为L<L^′。

命题11. 且。

命题11表明L_CDNF是的子片段，或者换句话说，与CDNF相比，K_n-DNF放松了析取项的约束条件。CDNF中析取项的命题部分要求是命题文字的合取，而K_n-DNF中析取项的命题部分仅要求是命题公式即可。通过放松对析取项的约束条件，使得比L_CDNF更加简洁。由于命题公式的变量遗忘可以简单计算，因此，这样处理并不会给知识遗忘的计算带来负面影响。虽然，通过转换成K_n-DNF或CDNF计算知识遗忘，其算法时间复杂度均为原公式长度的指数时间；但是，由于比L_CDNF更加简洁且可以避免部分子公式知识遗忘的重复计算，转换成K_n-DNF计算知识遗忘的效率往往更高。

例3. 借助CDNF公式计算例2中的KForget(ϕ,q)。

从例2和例3可知，将一般公式转换成K_n-DNF或CDNF之后，均可计算其知识遗忘，且两者所得结果逻辑等价（CDNF公式与一般公式之间的转换参考文献 [5]）。不难看出，即使采用 ∇_iΦ 作为 ∧_φ∈ΦL_iφ∧K_i(V_φ∈Φφ)的缩写，K_n-DNF公式比CDNF公式仍要简洁得多。而且采用K_n-DNF公式可以避免部分子公式知识遗忘的重复计算。

5 结论与展望

本文在多智能体模态逻辑系统K_n中，对知识遗忘进一步展开研究。系统分析了知识遗忘的重要性质；基于知识编译，提出一种K_n系统中知识遗忘计算的有效算法，与已有算法相比，我们的算法更高效。K_n是最小的正规多智能体模态逻辑系统，其它正规多智能模态逻辑系统都在其基础上扩展而来。尽管不同模态逻辑系统中知识遗忘的性质和计算方法都不尽相同，但本文的研究对其它多智能模态逻辑系统中知识遗忘的研究依然具有借鉴意义。

下一步研究，一方面将考虑引入包括公共知识（common Knowledge）和分布知识（distributed Knowledge）在内的群体知识之后，知识遗忘的计算问题。另一方面，将继续探讨在其他多智能体模态逻辑系统（如：KD45_n，S5_n）中的知识遗忘计算问题。

参考文献

[1] F.Baader,D.Calvanese,D.L.McGuinness et al.,2003,The Description Logic Handbook:Theory,Implementation,and Applications,New York:Cambridge University Press.

[2] M.Bilkova,2007,“Uniform interpolation and propositional quantifiers in modal logics”,Studia Logica,85(1):1–31.

[3] P.Blackburn,M.de Rijke and Y.Venema,2001,Modal Logic,Cambridge:Cambridge University Press.

[4] G.Boole,1854,The Laws of Thought,London:Walton and Maberley.

[5] B.T.Cate,W.Conradie,M.Marxetal.,2006,“Definitorially complete description logics”,Proc of the 10th International Conference on Principles of Knowledge Representation and Reasoning(KR-2006),pp.79–89,Menlo Park:AAAI Press.

[6] S.Chilardi,C.Lutz,F.Wolter et al.,2006,“Conservative extensions in modal logic”,Papers from the Sixth Conference on “Advances in Modal Logic”,Advances in Modal Logic,vol.6,pp.187–207,London:College Publications.

[7] S.Chilardi and M.Zawadowski,1995,“Undefinability of propositional quantifiers in the modal system S4”,Studia Logica,55(2):259–271.

[8] A.Darwiche and P.Marquis,2002,“A knowledge compilation map”,Journal of Artificial Intelligence Research,17:229–264.

[9] J.DelgrandeandK.W.Wang,2015,“A syntax-independent approach to forgetting in disjunctive logic programs”,Proc of the 29th AAAI Conference on Artificial Intelligence(AAAI-2015),pp.1482–1488,Menlo Park:AAAI Press.

[10] P.Doherty,W.Lukaszewicz and A.Szalas,2001,“Computing strongest necessary and weakest sufficient conditions of first-order formulas”,Proc of the 17th International Joint Conference on Artificial Intelligence(IJCAI-2001),pp.145–154,San Francisco:Morgan Kaufmann Publishers.

[11] T.Eiter and K.W.Wang,2008,“Semantic forgetting in answer set programming”,Artificial Intelligence,172(14):1644–1672.

[12] L.D.Fang,Y.M.Liu and H.van Ditmarsch,2016,“Forgetting in multi-agent modal logics”,Proc of the 25 International Joint Conference on Artificial Intelligence(IJCAI-2016),pp.1066–1073,Menlo Park:AAAI Press.

[13] L.D.Fang,Y.M.Liu and X.M.Wen,2015,“On the progression of knowledge and belief for nondeterministic actions in the situation calculus”,Proc of the 29th International Conference on Artificial Intelligence.pp.2955–2963,Menlo Park:AAAI Press.

[14] L.D.Fang,H.Wan,X.Q.Liu et al.,2018,“Dependence in propositional logic:formula-formula dependence and formula forgetting — Application to belief update and conservative extension”,Procofthe 32th AAAI Conferenceon Artificial Intelligence(AAAI-2018),pp.1835–1844,Menlo Park:AAAI Press.

[15] J.Y.Halpern and Y.A.Moses,1992,“A guide to completeness and complexity for modal logics of knowledge and belief”,Artificial Intelligence,54(3):319–379.

[16] A.Herzig and J.Mengin,2008,“Uniform interpolation by resolution in modal logic”,Proc of the 11th European Conference on Logics in Artificial Intelligence(JELIA-2008),pp.219–231,Berlin:Springer.

[17] D.Janin and I.Walukiewicz,1995,“Automata for the modalµ-calculus and related results”,Mathematical Foundations of Computer Science,pp.552–562,Berlin:Springer.

[18] M.J.Ji,J.H.You and Y.S.Wang,2015,“On forgetting postulates in answer set programming”,Proc of the 24th International Joint Conference on Artificial Intelligence(IJCAI-2015),pp.3076–3083,Menlo Park:AAAI Press.

[19] B.Konev,D.Walther and F.Wolter,2009,“Forgetting and uniform interpolation in large-scale description logic terminologies”,Proc of the 21st International Joint Conference on Artificial Intelligence(IJCAI-2009),pp.830–835,Menlo Park:AAAI Press.

[20] R.Kontchakov,F.Wolter and M.Zakharyaschev,2010,“Logic-based ontology comparison and module extraction,with an application to DL-lite”,Artificial Intelligence,174(15):1093–1141.

[21] P.Koopmann and R.A.Schmidt,2014,“Count and forget:Uniform interpolation of SHQ-ontologies”,Proc of the 7th International Joint Conference on Automated Reasoning(IJCAR-2014),pp.434–448,Cham:Springer.

[22] P.Koopmann and R.A.Schmidt,2015,“Uniform interpolation and forgetting for ALC ontologies with ABoxes”,Proc of the 29th AAAI Conference on Artificial Intelligence(AAAI-2015),pp.175–181,Menlo Park:AAAI Press.

[23] S.Kripke,1963,“Semantic analysis of modal logic”,Zeitschrift fur mathematische Logik und Grundlagen der Mathematik,9(5–6):67–96.

[24] J.Lang,P.Liberatore and P.Marquis,2003,“Propositional independence:Formula-variable independence and forgetting”,Journal of Artificial Intelligence Research,18:391–443.

[25] J.Lang and P.Marquis,2010,“Reasoning under inconsistency:A forgetting-based approach”,Artificial Intelligence,174(12–13):799–823.

[26] F.Z.Lin,2001,“On strongest necessary and weakest sufficient conditions”,Artificial Intelligence,128(1–2):143–159.

[27] F.Z.Lin and R.Reiter,1994,“Forget it!”,Proc of AAAI Fall Symposium on Relevance,pp.141–146,Menlo Park:AAAI Press.

[28] F.Z.Lin and R.Reiter,1997,“How to progress a database”,Artificial Intelligence,92(1–2):131–167.

[29] Y.M.LiuandG.Lakemeyer,2009,“On first-order definability and computability of progression for local-effect actions and beyond”,Proc of the 21st International Joint Conference on Artificial Intelligence(IJCAI-2009),pp.860–866,Menlo Park:AAAI Press.

[30] Y.M.Liu and X.M.Wen,2009,“On the progression of knowledge in the situation calculus”,Proc of the 22nd International Joint Conference on Artificial Intelligenc(IJCAI-2011),pp.976–982,Menlo Park:AAAI Press.

[31] M.Ludwig and B.Konev,2014,“Practical uniform interpolation and forgetting for ALC TBoxes with applications to logical difference”,Proc of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2014), pp. 318–327, Menlo Park: AAAI Press.

[32] C. Lutz, I. Seylan and F. Wolter, 2012, “An automata-theoretic approach to uniform interpolation and approximation in the description logic EL”,Proc of the 14th International Conference on Principles of Knowledge Representation and Reasoning(KR-2012),pp.286–296,Menlo Park:AAAI Press.

[33] C.Lutz and F.Wolter,2011,“Foundations for uniform interpolation and forgetting in expressive description logics”,Proc of the 22nd International Joint Conference on Artificial Intelligence(IJCAI-2011),pp.989–995,Menlo Park:AAAI Press.

[34] A.Nayak,Y.Chen and F.Z.Lin,2006,“Forgetting and knowledge update”,Proc of 19th Australian Joint Conference on Artificial Intelligence(AI-2006),pp.131–140,Berlin:Springer.

[35] K.L.Su,A.Sattar and G.F.Lv,2009,“Variable forgetting in reasoning about knowledge”,Journal of Artificial Intelligence Research,35:677–716.

[36] A.Visser,1996,“Uniform interpolation and layered bisimulation”,Gödel’96:Logical Foundations of Mathematics,Computer Science and Physics,pp.139–164,Berlin:Springer.

[37] K. W. Wang, Z. Wang, R. W. Topor et al., 2014, “Eliminating concepts and roles from ontologies in expressive descriptive logics”,Computational Intelligence,30(2):205–232.

[38] Y.S.Wang,K.W.Wang,Z.Wang et al.,2015,“Knowledge forgetting in circumscription:A preliminary report”,Proc of the 29th AAAI Conference on Artificial Intelligence(AAAI-2015),pp.1649–1655,Menlo Park:AAAI Press.

[39] Y.S.Wang,K.W.Wang and M.Y.Zhang,2013,“Forgetting for answer set programs revisited”,Proc of the 23rd International Joint Conference on Artificial Intelligence(IJCAI-2013),pp.1162–1168,Menlo Park:AAAI Press.

[40] Y.S.Wang,Y.Zhang,Y.Zhou et al.,2014,“Knowledge forgetting in answer set programming”,Journal of Artificial Intelligence Research,50(1):31–70.

[41] Z.Wang,K.W.Wang,R.W.Topor et al.,2009,“Uniform interpolation for ALC revisited”,Australasian Joint Conference on Advances in Artificial Intelligence(ACAI-2009),pp.528–537,Berlin:Springer.

[42] Z.Wang,K.W.Wang,R.W.Topor et al.,2010,“Forgetting for knowledge bases in DL-Lite”,Annals of Mathematics and Artificial Intelligence,58(1–2):117–151.

[43] Z.Wang,K.W.Wang,R.W.Topor et al.,2010,“Tableau-based forgetting in ALC ontologies”,Proc of the 19th European Conference on Artificial Intelligence(ECAI-2010),pp.47–52,Ohmsha:IOS Press.

[44] D.Xu and Z.Q.Lin,2011,“A prime implicates-based formulae forgetting”,Proc of IEEE International Conference on Computer Science and Automation Engineering(CSAE-2011),pp.128–132,Piscataway:IEEE.

[45] N.F.Y.Zhang,2006,“Solving logic program conflict through strong and weak forgettings”,Artificial Intelligence,170(8–9):739–778.

[46] Y.Zhang and Y.Zhou,2009,“Knowledge forgetting:Properties and applications”,Artificial Intelligence,173(16–17):1525–1537.

[47] Y. Zhao and R. A. Schmidt, 2015, “Concept forgetting in ALCOI-ontologies using an ackermann approach”,Proceedings of the 14th International Semantic Web Conference(ISWC-2015),pp.587–602,New York:Springer.

Knowledge Forgetting in Multi-Agent Modal Logic System K_n

Ximing Wen Liangda Fang Quan Yu Liang Chang Ju Wang

Abstract For humans,forgetting is more than just a failure to remember;it is an active process that helps the brain take in new information and make decisions more effectively.Endowing computers the ability to forget like humans is one of the great challenges of artificial intelligence.Forgetting has been studied not only in the field of knowledge representation and reasoning based on symbol logic,but also in the field of machine learning based on statistics.In particular,forgetting plays an important role in knowledge representation and reasoning.It has been extensively studied in many logics such as propositional logic,first-order predicate logic,modal logics,description logics,answer set programming,situation calculus,and so on.Modal logic is suitable for representing and reasoning about the knowledge of agents.Knowledge forgetting in modal logics has been firstly proposed in single-agent scenarios.With the development of the research on multi-agent systems,the investigation on knowledge forgetting in multi-agent modal logics begins to attract attention.However,to the best of our knowledge,knowledge forgetting cannot be effectively computed up to now.In the present paper,we make further investigation on the knowledge forgetting in the multi-agent modal logic system K_n.By adopting the idea of knowledge compilation,we introduce a novel normal form named K_n-DNF.Based on K_n-DNF,an effective algorithm to compute the knowledge forgetting in Kn is provided.The time complexity of our algorithm is polynomial in the length of the K_n-DNF formula.

中图分类号： B81

文献标识码： A

收稿日期： 2018-10-30

作者信息：

文习明 广东行政学院信息技术教研部，广西可信软件重点实验室（桂林电子科技大学）

wenxim@mail2.sysu.edu.cn

方良达 暨南大学计算机科学系，广西可信软件重点实验室（桂林电子科技大学）

fangld@jnu.edu.cn

余泉 黔南民族师范学院数学与统计学院

yuquanlogic@126.com

常亮 广西可信软件重点实验室（桂林电子科技大学）

changl@guet.edu.cn

王驹 广西可信软件重点实验室（桂林电子科技大学）

juwang500909@163.com

基金项目： 国家自然科学基金（61603152、61463044、61363030、61862051）；广西可信软件重点实验室开放课题（KX201604、KX201606、KX201419）；广西自然科学基金（No.2015GXNSFAA139285）。

（责任编辑：罗心澄）

Ximing Wen Department of Information Science,Guangdong Institute of Public Administration,

Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology wenxim@mail2.sysu.edu.cn

Liangda Fang Department of Computer Science,Jinan University,

Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology fangld@jnu.edu.cn

Quan Yu School of Mathematics and Statistics,Qiannan Normal College for Nationalities

yuquanlogic@126.com

Liang Chang Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology

changl@guet.edu.cn

Ju Wang Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology juwang500909@163.com

标签：多智能体模态逻辑论文;  知识推理论文;  知识编译论文;  知识遗忘论文;  广东行政学院信息技术教研部论文;  广西可信软件重点实验室(桂林电子科技大学)论文;  暨南大学计算机科学系论文;  黔南民族师范学院数学与统计学院论文;