（逻辑学专业论文）信念修正逻辑初探.pdf

西南大学硕士学位论文 摘要 信念修正逻辑初探 逻辑学专业硕士研究生萧瑶 指导老师何向东教授 摘要 经典的信念逻辑系统s 舢只能表达主体某个静止状态的信念及推理，事实上，在收到新信 息后，主体的信念将发生变化。动态认知逻辑是动态逻辑和认知逻辑相结合的结果，它为信 息变化提供了一种形式化的处理方法。本文旨在建立一个能处理信念变化的信念修正逻辑系 统s 哪。 第一部分：首先介绍经典的信念逻辑系统s x 矾s ，该系统能较好地刻画相信算子的性质：无 矛盾性、正内省性、负内省性，同时指出它的不足不能描述动作所产生的变化，也不能 刻画多主体间的相互作用。接着介绍传统的信念修正理论a g m 理论，它虽然能反映主体信 念变化的过程，但并不是一个形式化的系统。 第二部分：为了将信念排序，首先介绍顺序条件函数，它可以处理当主体收到带一定牢固 度的命题后信念是如何变化的。在此基础上，引入静态的信念逻辑系统s 瓣，给出语言、语义 以及证明系统，最后给出完备性的证明。 第三部分：在静态的信念逻辑系统s 潮的基础上，将行动模型在认知逻辑中的执行作为动 态模态算子引入逻辑语言中，建立动态的信念修正逻辑系统s 嘲。由于s 啉可以归约到s 锄，所 以可以证明s 呻n 也是完备的。 第四部分：对s 啉做出评价，指出不足之处，并指明在未来需要进一步研究的问题。 关键词：信念a g m 理论顺序条件函数信念修正 动态信念修正逻辑 艏南人学硕十学位论文a b s 仃a c t a p r e l i m i n a r ys t u d y o nl o g i co fb e h e fr e v i s i o n m a jo r ：l o g i c a u t h o r ：x i a oy a o s u p e r v i s o r ： p r o f e s s o rh ex i a n g d o n g a bs t r a c t t h ec l a s s i c a ls y s t e mo fd o x a s t i cl o 百c s k d 4 5 ，c a nm o d e la g e m sb e l i e fa n dr e a s o n m g o n l yi ns o m es t a t i cs t a t e s i nf a c t ，a f t e rr e c e i v i n gan e wp i e c eo fi n f o m l a t i o nt ot i l eb e l i e fs e t ， t h ee p i s t e m i ca g e n tw i l lc h a i l g eo l db e l i e fs e t d ) ，1 1 啪i ce p i s t e m i cl o g i c ( d e l ) ，w h i c hm e r g e s d y l l a n l i c1 0 百ca n de p i s t e m i cl o g i c ，p r o v i d e sf o 珊a 1m e 锄so fa 1 1 a l y s i so fi n f o 彻a t j o nc h a n g e i nt h i s m e s i s ， a l o g i cs y s t e mw i l lb ep r o p o s e d 一一d y l l a l l l i cl o g i co fb e l i e fr e v i s i o n ( d b r ) ，w h i c hc a nm o d e lb e l i e fc h a n g e p a r to n e ：a sac l a s s i c “s y s t e m s k d 4 5 ，i ti ss u c c e s s 凡lt 0e x p f e s ss t f o n g l yt h ep f o p e n i e s o fb e l i e w e a k e rk n o w l e d g e ；p o s i t i v ei n t r o s p e c t i o n ；n e g a t i v ep o s i t i v ei n 仃o s p e c t i o n a tm e s a m et i m e ，i t sf a l s et o 仃e a tt h ec h a n g ea i l di n t e m c t i o no fm u l t i a g e n t s e q u e n t i a l l y ，a l t h o u g h b e l i e fr e v i s i o nt h e o d ，c o n c e i v e db yc a l c h o u r r o n ，p g a r d e n f o r sa n dd m a c k i n s o n ( a g m ) 仃c a t t h ec h a n g es u c c e s s 如l l y i ti sn o ty e taf o m a ls y s t e m p a n 似o ：a no r d i n a lc o n d i t i o n a lf u n c t i o n ( o c f ) e x p r e s s e sar 锄k i n go fp r o p o s i t i o n s ，锄d i tr 印r e s e n t sa g e n t sr e v i s e db e l i e fa r e rr e c e i v i n gap i e c eo fi n f o 加a t i o nw i t hf i m m e s s 仅0 n m eb a s eo fo c f t l l i sp a p e ri n t r o d u c e sas t a t i cl o g i co fb e l i e fr e v i s i o n ( s b r ) ，i n c l u d i i l gs y n t a x ， s e m a n t i c sa n dp r o o fs y s t e m f i n a l l y t h el o g i cs y s t e mi sp r o v e dc o r r l p l e t e p a r tt h r e e ：a r e re x t e n d i n gm es b r ，b yi n t r o d u c i n gt h ee x e c u t i o no ft h ea c t i o nm o d e li n 印i s t e m i cm o d e la sad y n a m i co p e r a t o ri n t ot h e1 0 9 i c a l l a n g u a g e ，t l l i sp 印e rs e t su pad ”a n l i c l o g i co fb e l i e fr e v i s i o n ( d b r ) ni sc a nb ep r o v e dt h a tn l ed b r a l s oi sr e d u c e dt ot 1 1 es b r ，s o d b rs y s t e mi sc o m p l e t et 0 0 p a r tf o u r ：ic o m m e n to nn l ed b r ，a n dg i v es o m ep r o b l e n 琏f o rf h r 廿l e rr c s e a r c hi nn l e f u t u r e k e yw o r d s ：b e l i e f a g m t h e o 巧 o r d i n a lc o n d i t i o n a l 胁c t i o n b e l i e fr e v i s i o n d y n a m i cl o g i co f b e l i e f r e v i s i o n i i 独创性声明 学位论文题目一一 焦盒堡垂翌堑塑拯 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中己加 了标注。 学位论文作者：萧睦 签字日期：。2 。眸午月2 。日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：囹不保密， 口保密期限至年月止) 。 学位论文作孝签名：萧矗 签字日期：2 0 吗午午月2 0 日 导师签名： 签字日期：删年午月2 五日 西南人! 学硕+ 学位论文 文献综述 文献综述 认知逻辑是研究知识和信念的形式推理的逻辑。早在古代，哲学家就开始关 注知识和信念的表示与推理问题。在著作曼诺篇( m e m o ) 、泰阿泰德篇 ( t h t e a e t e t u s ) 等文中，柏拉图( p l a t o ) 认为认识可以分成不同的等级：知识、 谬误、信念、意见、怀疑和假设等等，其中最重要的就是知识和信念。康德( k a n t ) 也深入地研究了知识和信念的本质，他认为“知识是指在主观和客观上都能充分 地承认其为真的判断，而信念只指在主观上有充足的依据，而在客观上依据不足 的判断。 1 1 9 4 8 年，波兰逻辑学家洛斯( j l o s ) 最早提出了包括七条公理的信念逻辑系 统2 ，从而成为信念逻辑的创始人。1 9 5 7 年，帕普( a p a p ) 也提出了包括六条规 则的信念逻辑体系3 。虽然他们建立了自己的信念逻辑系统，但都没有给出完整的 语义解释。直到克里普克( s k n p k e ) 、欣迪卡( j h i n t i k k a ) 建立了完整的模态逻辑 语义理论可能世界语义学，信念逻辑才真正诞生，其标志性的著作为知识 与信念一书4 。 上述系统只能对信念及推理作静态的形式化处理，而实际上世界充满着变化， 人们的知识和信念也在不断地改变。在逻辑学中处理信念“变化”的代表性方法 是动态认知逻辑( d e l ；d y i l a i i l i ce p i s t e m i cl o g i c ) 和信念修正( b r ；b e l i e fr e v i s i o n ) 理论。 在上世纪八十年代，随着人工智能、博弈论、决策论等学科的发展，动态逻 辑( d y l l 锄i cl 0 9 i c ) 得以迅速地形成，并在多个学科中都得到了应用。动态认知逻辑 是认知逻辑和动态逻辑相结合的结果，第一个动态认知逻辑体系是由j a nap l a z a 建立的公开宣告逻辑( p a l ；p u b l i ca n n o u n c e m e n tl o g i c ) 5 。动态认知逻辑是形 式化的认知系统，其模型通常是建立在可能世界语义学基础上的克里普克模型6 ， 对于动作或程序产生的变化，也给出了相应的语义解释。 信念修正理论也产生于上世纪八十年代，是当前人工智能界和哲学界研究的 热门主题之一。在现实生活中，人们不断地接受新知识，从而导致认知状态也随 之改变。新知识通常会与原来的信念发生冲突，如何修正已有的信念状态，以获 1 i k a n t 纯粹理性批判( 中文版) 三联书店，1 9 5 7 2 l o s ，j e r zy i o g j l iw i e l o w a n o c j o w eaf o m a l i c a c j af u n k e j ii n t e n s j o n a l n y c h m 胁懈肋加请，口z 彻，1 7 ( 1 9 4 8 ) 5 7 7 8 3a p 印b e l i e f 绷dp r o p o s i t i o n 【j 】m f ，叫p 砂& 砌c p ，2 4 ( 1 9 5 7 ) ，1 2 3 一1 3 6 4j h i n t i k k 8 k 玎d w f 啦e 口露d b e 以妒爿，l 扬f m 幽c 加以f o 珐e 三p 爵c 可f 妇7 w o b f 如雄s 【m 】c o m e l lu n i v e r s 时 p r e s s 1 9 6 2 5ja p l a z a l o 画c so fp u b i i cc o m m u n i c a t i o n s 【a 】mle m r i c h ，msp 颇f e r mh a d z i k a d f c ，zw r a l s ( c d s ) p m c e e d i n g s 西t h e4 t hi n t e m a t i o n ms y 唧o s t u mo nm e t h o d o l o g i e s 如ri n t e l l i g e n ls y s t e m 武q 、9 鹋0 q 、翻6 ， 6v c l t m a l l 提出了另一种语义更新语义学，参见：f v e l n m n d e f ；m l t si nu p d a t es e m a i l t i c s a 】c d 础f f d ，l 口西， 。d i e 如“凰口，l d 尺p v 括f o ，l s 【c 】，e d i n b u r g h ，19 9 6 1 西南人学硕十学位论文 文献综述 得一个一致的新信念状态，这是信念修正的主要内容。信念修正的理论及其具体 的操作方法很多，具有代表性的是a l c h o u r r 6 n 、g a r d e n f o r s 和m a k i n s o n 提出的 a g m 理论。 经典的信念修正理论并不是一个形式化的逻辑系统。实际上，将行动模型在 认知逻辑中的执行作为动态模态算子引入到逻辑语言中，我们也可以建立动态认 知逻辑系统来刻画信念变化。目前，国际上的一个趋势是“建立动态认知逻辑来 处理信念修正”，代表性人物有h a i l sv a nd i t m a r s c h 8 、j v 姐b e n t h e m 9 及g a u c h e r m 等。 7c e a l c h o u r r 6 n ，p g a r d e n f o r sa n dd ，m a k i n s o n o nn l el o g i co ft h e o r yc h 黼g e ：p a m a lm e c tc o n 仃t i o n 龃d r e v i s j o nf u n c t i o n s j 】b “，w 口，可跏6 d ，耙p g f c ，5 0 ：5 1 0 - 5 3 0 ，1 9 8 5 8h a n s v a nd i t m a r s c h b e l i e fc h a n g ea n dd y n a r n i cl o g i c 【a 】i n ：j d e l g f 锄d e 醐dj l a n g 蠲dh r o t ta n dj - m 1 a 1 、o nt e d s ，b e t 耐c h 口n g ei nr 口l i o n 4 la g e n t s ：p e r s p e c t i v e sj r o ma 嘎o c i 口ti n t e t l i g e n c e p h i t o s o p bn 耐 历d 以。忉f c s c 】，2 0 0 5 9j v a nb e n t h e m d y i l a m i cl o g i c f o rb e l i e f r e v i s j o n 【j 】肋“m 口，删即矗耐d 疗纰豁f 儿唧c ，2 0 0 7 ( 1 7 ) ，l 2 7 1 0 ga u c h er 爿国肌6 伽耐跏f 绷力，印出倌工d g f c 口以d 曰p ，f r p 协咖m 硒t e r st h e s i s ，i l l c ，u n i v e r s 时o f a m s t e r d a m 2 0 0 3 2 西南大学硕士学位论文第1 章经典的信念逻辑 第1 章经典的信念逻辑 信念，从某种意义上讲，是另一种形式的知识。正如莱维斯克( l e v e s q u e ) 所讲 的“在知识库中的知识不必是必然为真”1 1 。我们将这种不必为真的知识称为信 念1 2 。本章将首先介绍经典的信念逻辑系统s k d 4 5 ，该系统能较好地刻画相信算子 的基本性质：无矛盾性、正内省性、负内省性；接着介绍传统的信念修正理论 a g m 理论，它虽然能反映主体信念变化的过程，但并不是一个形式化的系统。 1 1 信念逻辑系统s 麟， 要建立关于信念的逻辑系统，首先需要理解信念的涵义。信念与知识有着本 质上的区别：知识是与真假有联系的，知道的事物都是真的，也只有真的事物才 能被知道；而信念却与真假没有必然的联系，因为我们完全可以相信一个实际上 为假的命题。 基于可能世界语义学，我们可建立标准的信念逻辑系统s k ，。 定义1 1 ( 语言z k d 。，) 给定一个有限的命题变元集p ，信念逻辑系统s k d 4 ， 语言中的语句归纳定义如下： ( p ：= p i _ 1 平i ( ( p 人v ) i b ( p ，在这里p p 。 其中b 是相信算子，b ( p 读作“相信q ”。 定义1 2 ( 认知模型) 给定一个有限的命题变元集p ，信念逻辑系统s k d 4 ，的 认知模型定义为m = ( w ，r ，v ) ，其中： 1 w g ，w 是一个有限非空的可能世界集； 2 r ：p 一2 w ，r 对每个主体指派w 上的一个二元关系； 3 v ：p j 2 w ，v 是对每个命题变元在每个可能世界上进行赋值。 模型中的二元关系由相信算子的逻辑性质决定，在这里关系r 对应的性质有： 持续性( s 嘶1 i t y ) 、传递性( t 啪s i t i v i t y ) 、欧性( e u c l i e a r c ) ，所以它并不是一个等价关 系。 定义1 3 ( 语义) 给定一个认知模型m 和一个可能世界w w ，公式q 在认知 模型m 中是真的，记作( m ，w ) q ，归纳定义如下： 1 ( m ，w ) 唧当且仅当w v ( p ) ； 2 ( m ，w ) - 1 ( p 当且仅当并非( m w ) ( p ： 3 ( m ，w ) ( p v 当且仅当( m ，w ) 叩且( m ，w ) v ： h j l e v e s q u e al o g i co f i m p l i c t 鲫de x p l i c i tb e l i e f 【a 】尸胁卯耐胁伊矿珐p 4 f 加口，c d 吧励搠d 一彳一归耐 砌据， 弦，l c p c ，19 8 4 ，l9 8 2 0 2 1 2 周昌乐认知逻辑导论【m 】清华大学出版社，广西科学技术出版社出版，2 0 0 l ，p 1 2 1 3 西南人学硕十学位论文第1 章经典的信念逻辑 4 ( m ，w ) | 一b ( p 当且仅当对所有v ，如果( w v ) r ，那么( m ，v ) j _ ( p 。 定义1 4 ( 证明系统) 信念逻辑系统s l ( d 4 5 由以下公理和推演规则组成： 一、公理： l 、所有的命题重言式 2 、b ( q 争v ) ( b ( p b v ) 3 、，( b ( p b 、q )( 弱知道公理) 4 、b ( p _ b b ( p( 正内省公理) 5 、- 1 b ( p b - 1 b q ( 负内省公理) 二、推演规则： 1 、从 ( p ，( p v ) ，可以得到v ( 分离规则) 2 、从( p ，可以得到b ( p ( 必然化规则) 公理2 对应k 公理；公理3 、4 、5 分别对应d 公理、4 公理、5 ( e ) 公理。公理 3 是知道公理k ( p _ ( p 的弱化，它刻画了信念的无矛盾性，即不会同时相信两个矛 盾的命题。公理4 刻画了信念的正内省性( i i l t r o s p e c t i o n ) ，断定了“如果主体相信 什么，则他相信他相信什么”。公理5 刻画了信念的负内省性( n e g a t i v ei n t r o s p e c t i o n ) ， 断定了“如果主体不相信什么，则他相信他不相信什么”。公理3 、4 、5 能较好地反 映“信念”的内涵。 系统s 。；能较好地刻画相信算子的性质，是一种较为理想的信念逻辑系统。 但系统s 删，没有引入群体信念( g r o u pb e l i e f ) 1 3 的概念，也没有考虑多主体之间的相 互影响与互动，所以语言有待进一步丰富，语言的表达力有待进一步增强。同时 该系统也存在逻辑全知( 1 0 9 i c a lo 咖i s c i e n c e ) 1 4 问题，所以是个过于理想化的系 统。 1 2 信念修正的a g m 理论 在一些有实际意义的智能系统中( 如知识库系统或学习系统) ，都需要解决在保 证一致性的前提下，如何将新知识综合到系统已有的知识库中去。在过去二十多 年中，计算机科学家和逻辑学家一直在关注这个问题。在a g m 理论中，知识库被 表示为一个一致的、演绎封闭1 5 的语句集k ，也称为信念集。一个理想的知识体系 首先应遵循三条基本原则： 1 一致性原则( c o n s i s t e n c y ) ： 2 最小改变原则( m i n i m a lc h a n g e ) ：当新旧知识发生冲突时，尽可能不改变已 1 3 类似于群体知识，群体信念也可分为普遍信念( g e n c r a l b e 】i e f ) 、公共信念( c o m m o nb e l i e f ) 等。群体知识的定义 可参考r o n a l df a g i n ，j o s e p hy h a l p e m ，y o r a mm o s e s ，m o s h ey v a 柑i 月刀加g 口6 d 讲砌d w 跆如【m 】t h em i t p r e s s c a m b r i d g e ，m a s s a c h u s e t t s ，l o n d o n ，e n g l a n d ，2 0 0 3 ，p 2 3 - 2 5 ， 1 4 可参考：刘虎，鞠实儿信念逻辑的逻辑全知问题 j 】求是学刊，2 0 0 7 ( 6 ) ，3 l 3 4 1 5 演绎封闭指语句集k = c n ( 幻。其中c n 称为逻辑后承算子，c n ( a ) = ( a la 卜8 ) 。 4 西南大学硕士学位论文 第1 章经典的信念逻辑 有的知识，又称经济原则； 3 新消息优先原则( p r i o r i t yt ot h ei n c o m i n gh l f o m a t i o n ) ： a g m 考查了三种不同类型的信念变化：扩充( e x p a n s i o n ) 、修正( r e v i s i o n ) 与收 缩( c o n t r a c t i o n ) 。 扩充：将新语句p 加入到已有的信念集k 中，并利用逻辑演绎的方法，扩充 形成一个新的信念集，不考虑结果的一致性，这种变化称为p 扩充k ，记为k + p 。 修正：将新语句p 加入到与其不一致的信念集k 中，考虑到结果的一致性， 应先k 中部分语句删除，这种变化称为p 修正k ，记为p 。 收缩：信念集k 中的语句p 被删除，考虑到结果在演绎推理下封闭，故在必 要时将k 中其它的某些语句删除，这种变化称为p 收缩k ，记为k p 。 对于扩充，其变化过程较为简单，可定义为：k + p = c n u ( p ) ) 。容易看出， 由这种方法定义的k + p 在演绎推理下也是封闭的，而且当p 与k 一致时，k + p 也是一致的。 对于修正和收缩，用现有的逻辑和集合的知识难以处理。下面先看两个例子： 例子1 1 假设已有的信念集k 包含如下四个命题： 仅： 所有亚洲的天鹅都是白色的。 d ： 陷井中捕获的鸟是天鹅。 丫： 陷井中捕获的鸟来自中国。 6 ：中国是亚洲的一部分。 由上面的信念集，我们易得出如下结论： p ： 陷井中捕获的鸟是白色的。 而实际上我们捕获的鸟是黑色的，即新语句- 1 p 与原有的信念集k 不一致。考 虑到新消息优先原则，我们要接受1 p ，所以信念集k 中的某些语句将删除。考虑 到最小改变原则，我们没必要将所有有价值的信念都放弃，如只删除0 【1 6 。 例子1 2 假设已有的信念集k 包含仅、仪一p 、p 。如果我们执行收缩操作，将 d 删除，考虑到仪、仪寸p 在演绎推理下又能得出p ，所以仪、a d 至少还得删除一个。 a g m 先分别为修正和收缩给出八条理性的假设( r a t i o n a lp o s t u l a t e s ) ，再提出具 体的处理方法。下面先给出修正应满足的八条假设： ( r 1 ) 石p = c n ( 舻p ) ； ( r 2 ) p 5 p p ； ( r 3 ) 鼻p p 必印； ( r 4 ) 如果一p 仨k ，则j 帅量j 【聿p ； 1 6 这只是按修正最初的定义执行操作的，而后来在实际操作中，我们可以用a 来代替a ，a 为：除了中国某些 天鹅是黑色的以外，所有亚洲的灭鹅都是白色的。 5 两南火学硕士学位论文第l 章经典的信念逻辑 ( r 5 ) ，p = 尺- 上1 7 当且仅当i 一，p ； ( r 6 ) 女果i p q ，贝0 p p = = - ，q ； 假设( r 1 ) 表明信念集经过修正后仍然是一个信念集。 假设( r 2 ) 表明新知识应包含在新信念集中。 假设( r 3 ) 、( r 4 ) 表明当新知识与已有的信念一致时，修正实质上就是扩充。 假设( r 5 ) 表明p 应该是致的，除非p 本身不一致。 假设( r 6 ) 表明修正操作与新知识的语形并没有关系。 上面六条假设称为信念修正操作的基本假设，下面两条假设则称为信念修正 操作的附加假设： ( r 7 ) 舻( p q ) p ) + q ； ( r 8 ) 如果一q 芒舻p ，贝0 ( 舻p ) + q 三j p ( p q ) 。 假设( r 7 ) 和假设( r 8 ) 描述了知识体系被两条语句同时修正时的特性。这两条假 设表明：如果q 与p 一致，则p q 修正k 与先用p 修正k 再用q 扩充p 的效 果一样。 a g m 理论还给出了下面两条恒等式： l e v i 恒等式：舻p = 一 p ) + p ； h a r p e r 恒等式：k p = ( - p l p ) 广、k l e v i 恒等式表明：修正操作k 卑p 可以看成先用 p 收缩k ，从而将k 中与p 相 矛盾的知识去除，然后用p 扩充所得的结果，而h a 印e r 恒等式则表明收缩操作也 可用修正操作表示。 在给出了假设之后，人们提出了各种构造性的方法，其中a g m 提出的方法有： 极大一致子集( m a x i m “c o n s i s t 钮ts u b s e t s ) 修正；部分交0 a r t i a lm e e t ) 修正；全部交 ( f u l lm e e t ) 修正( 前三种修正参考1 8 ) ；认知牢固度( e p i s t e m i ce n t r e n c h m e n t ) 的方法1 9 。 源于a g m 理论，有不少的改进与进一步深化的方法，如基于理论基( t h e o 巧b a s e ) 的方法2 0 ，基于模型的方法2 1 等等。a g m 假设为各种信念修正方法提供了比较的尺 度，无论是哪一种方法，都尽可能地满足上述的八条修正假设。 由于经典的信念修正理论在描述知识的动态特征具有独特的优势，因而近年 来得到了广泛地研究，并且在形式化以及近似计算等方面得到了进一步发展2 2 。同 疋l 表示信念集不一致。 c 。e a i c h o u 九西n ，p g a r d e n f o r sa n dd 。m a k i n s o n o nt h el o g i co f t h e o r yc h 姐g c ：p a r t i a lm e e tc o n t r a c t i o n 锄d r e v i s i o nf u n c t i o n s j ，o “，疗口，q 厂s r ，”6 0 “c 己( 1 鲥c ，5 0 ：5 l o - 5 3 0 ，1 9 8 5 1 9p g a r d e n f o r s ，d m a k i n s o n r e v i s i o no fk n o w l e d g e s y s t e m s ：u s i n ge p i s t e m i ce n 仃e n c h m e n t a 】尸r d c 卯历川f 矿咖e & 材c 0 ，咖旭行c pd ，l 砌阳旭f f c 口，爿印p c 佃尺p 口舳行f 仃g 爿6 0 w 再锄d w ，啦p 【q 8 3 9 5 ，1 9 8 8 2 0 b n e b e l b a s er e v i s i o no p e r a t i o n sa n ds c h e m e s ：s e m a n t i c s ，r e p r e s e n t a t i o n ，a n dc o m p l e x i t y 【a i n ：c o h na g c d s ， p r o c e e d i n g s 可| it he u r o p e 4 nc on 寤r e n c eo na r t 啦c i q lj n t e l l i g e n c e 吼、9 9 4 2 1 m ，d a l a l 1 n v e s t i g a t i o n si n t oat h e o r yo f k n o w l e d g eb a s er e v i s i o n ：p r e l i m i n a 哆r e p o r t 【a 】i n ：跏翮，罾，矿舫e 肭 口f f d 以口fc b 咖m d 疗爿c 】1 9 8 8 ，4 7 5 - 4 7 9 2 2 b n e b e l b a s er e v i s i o no p e r a t i o n sa n ds c h e m e s ：s e m 勰t i c s ，r e p f e n t a t i o n ，a n dc o n 甲l e x i t y 【a 】i n ：c o h na g c d s ， 6 西南人学硕十学位论文 第l 章经典的信念逻辑 时，从九十年代中期开始，不少专家开始研究多主体的信念修j 下理论，其中多主 体的知识表示和推理为多主体系统协调、协商、学习以及结构等问题研究的关键 和基础。利用信念修正理论解决多主体系统中知识与信念的交互与冲突已有一些 初步的研究成果2 3 ，但多主体信念修正理论仍处于研究的初期，还有许多问题有待 突破。 经典的a g m 理论虽能较好地反映人类知识体系动态演化的逻辑规律，也能反 映人工智能系统中知识库的动态变化特征，但并非一个形式化的公理系统，也无 法考虑可靠性和完备性等问题。本文下一步要做的是建立一个形式化的信念逻辑 系统，同时用该系统也能处理信念修正问题。 p m c e e d l n g so fjn he u r o p e 口nc o n 佬r e n c e0 na r t i g c i n li n t e t l i 昏e n c 畦q 。、9 9 4 2 3 b ，m a l h e i r o ，0 e u g a n i o a r g u m e n t a t i o na sd i s t r i b u t e db e l i e fr e v i s i o n ：c o n n i c tr e s 0 1 u t i o ni nd e c e n 仃a l i z c d c o o p e r a t i v em u l t i a g e n ts y s t e m s a 】i n ：m c p p 螂矿珐p d 胁p d l 删咖c b 形叠m 卯d 丹爿一驴c 细，如据惭卯【q p o n o ，p o r t u g a i ，2 0 5 2l8 ，2 0 01 7 西南人学硕十学位论文第2 章信念逻辑系统s 锄 第2 章信念逻辑系统s s 眼 在通常情况下，为刻画知道算子和相信算子的性质，应分别为它们定义不同 的可及关系。知道逻辑系统中的可及关系是等价关系( 自反、传递、对称) ，其中 自反关系对应的是知道公理：k q 专q ，直观上的意义是“知道的事实为真”；而信 念逻辑系统中的可及关系不应具有自反性，因为b ( p 一( p 表达的直观意义“相信的 事实为真”，明显地不合常理。在一些知识和信念的混合系统中2 4 ，模型给出的可 及关系有两种，一种是针对知识的等价关系，另一种是针对信念的关系，满足持 续性、传递性和欧性。 本章所建立的信念逻辑系统s 。啪将知识看成是一种特殊的信念( 知识是一种 最强的信念) ，可及关系只有等价关系一种。但同时为了刻画主体的合理性偏好， 给出了一个k 算子，对可能世界进行排序，由此对信念定义了一种新的语义。 由此可见，本系统与经典的信念逻辑系统s 删。相比，最大的特点在于对可能世 界进行排序，下文中将首先介绍一种重要的排序理论顺序条件函数( o c f ； o r d i n a lc o n d i t i o n a l 如n c t i o n ) 。 2 1顺序条件函数 本小节将首先给出一个可能世界排序的机制基于可能世界模型的g r o v e 方法2 5 ，接着给出信念集与可能世界集之间的关系，在此基础上提出球系统( s y s t e m o f s p h e r e s ) ，最后给出修正函数。 给定一个有限的命题变元集p ( p p ，p 为原子命题) 和一个非空的可能世界 集w ( w w ) ，现对每个命题变元在每个可能世界上进行赋值： v ：p 一2 w 则命题可以由可能世界集来表示，在下文中，命题通常用可能世界集来表示。 而对于可能世界w 而言，每一个命题对应一个真值，所以w 意味着关于命题的一 个极大一致集。 由此可知信念集与可能世界集有着非常密切的对应关系。对任意的可能世界 集w k ，可以定义相应的信念集心6 在w k 中任意一个可能世界都为真的句子2 7 集。反之，对任意的信念集k ，我们也可以定义一个相应的可能世界模型w k 用k 的极大一致扩充来给出w k 中的可能世界。信念集k 的每一个极大一致扩充 2 4 s k r 叫s ，d l e h m a n n k n o w l e d g e ，b e l i e fa n dt i m e 【a 】i n ：l k o ne d p m “吣腑p ，3 咖而，c b ，如可“m 小。一 彳“，d 肌口f 口，l 口一g w e g e 苫口，l d 尸，p g ，口埘_ ，l f gr e n n e s ，l n c s 2 2 6 【c 】，b e r l i n ：s p r i n g e r 19 8 6 2 5 a ，g r o v e t w o m o d e l l i n g s f o r n e o r y c h a n g e 明。如“埘口，d 厂黝f 幻s 印觚，l 嚼c ，1 7 ：1 5 7 1 7 0 ，1 9 8 8 。 2 6 假定信念集中的原予命题( 句子) 有限。 2 7 这里我们不严格区别“句子”与“命题”。 8 两南大学硕士学位论文第2 章信念逻辑系统s s 蛐 对应一个可能世界，所有的极大一致扩充对应的可能世界组成一个集合，即为w k 。 如下图2 i ，矩形内每一点代表一个可能世界，标记旧的圆代表k 中所有句子 均为真的可能世界集，标记【p 】的区域则表示p 为真的可能世界集。【豳和【p 有一非空 交，表明k 与p 一致。故p 修正k 的结果等于 圈n 【p 】。 图2 1p 修正髟8 例子2 1语言l 中的原子命题a 、b 、c 分别表示“小王是东北人”、“小王会 跳舞”、“小王是大学生”。则有：0 = ( a 、b 、c ) ，w l = ( a ) ，w 2 = 伯) ，w 3 = ( c ) ， w 4 = ( a 、b ) ，w 5 = ( a 、c ) ，w 6 = ( b 、c ) ，w 7 = a 、b 、c ) ，w 8 = g 。 假设主体初始的信念集为( 小王是东北人，小王会跳舞) ，即肛 a 、b ) ，所 以有 豳= ( w 4 、w 7 ) 。现在收到了新信息“小王是大学生”，故有 p 】- ( w 3 、w 5 、w 6 、 w 7 ) 。两者的交 圈n p = 0 时，主体不相信a 。 例子2 3 对于明天天气的预测，有四种可能：w 1 = ( 无雨、无风) ，w 2 = ( 无 雨、有风) ，w 3 = 有雨、无风) ，w 3 = ( 有雨、有风) ，且( w 1 ) = o 以w 2 ) ( w 3 ) k ( w 4 ) 。 由定义2 1 知，主体相信“明天无雨”且“明天无风”。但对于这两个命题，又该如 何刻画它们之间的顺序? s p o l l i l 为此引入了牢固度( d e g r e eo ff i m m e s s ) 的概念： 3 1 么表示w 执，即集合( x i x w 且x 叠a ) 。 l o 西南大学硕士学位论文 第2 章信念逻辑系统s 湖 命题a 被相信的牢固度为仅当且仅当k ( a ) = o 且k ( 彳) = 仅。的值越大，则越合理( 牢 固) 。由于“明天有雨”的值大于“明天有风”的k 值，所以“明天无雨”比“明天无风” 牢固。 命题2 3a 和b 是任意命题，则a 比b 更合理当且仅当a ) 畋b ) 或者以县) 0 ，此时收到牢固度为仅的新信 息a ，即新旧信息发生冲突时，则顺序条件函数陬，a 实质上是信念修正的一种形式 化。特别地，当k ( 彳) = o 且k ( a ) = o 时，由于在k 中主体保持中立态度，所以收到牢 固度为仅的新信息a 后，信念变化的过程对应于a g m 理论中的扩充。将顺序条件 函数a 看成是定义在信念集上的修正函数，则它满足a g m