（计算机应用技术专业论文）基于可拓集的描述逻辑研究.pdf

基于可拓集的描述逻辑研究 摘要 描述逻辑是一种基于对象的知识表示的形式化工具，在众多知识表示的形 式化方法中，它越来越受到人们的特别关注，尤其是随着本体和语义w e b 研究 的不断升温，作为本体语言和语义w e b 逻辑基础的描述逻辑更成为了研究的热 点问题。 根据应用领域的不同需求，需要描述的信息各式各样、纷繁复杂，这就要 求描述逻辑能够具有表达各类知识的能力，但是，传统的描述逻辑只能描述静 态的、确定的知识，表达能力有限，所以必须对它进行扩展研究。为了使它不 仅能够对动态的、模糊的知识进行表示和推理，而且能够描述矛盾问题的求解 策略，以实现策略的共享和重用，本文引入可拓学中的可拓集合和可拓变换， 对传统的描述逻辑进行如下扩展： 首先，针对传统描述逻辑不能描述模糊信息，而模糊扩展的描述逻辑虽然 可以描述模糊信息，但不适合于描述矛盾问题的不足，提出了一种基于静态可 拓集合的描述逻辑。该描述逻辑采用静态可拓集合代替经典集合和模糊集合作 为描述逻辑的集合论基础，对领域概念、关系以及个体等进行语义解释，并对 传统描述逻辑断言集的一致性检测算法t a b l e a u 算法进行扩展，实现对关联度 值为正负域的断言的扩充，从而判定断言集的一致性。 然后，针对传统描述逻辑和模糊描述逻辑都不能通过描述事物的质变和量 变，为矛盾问题的求解提供策略的不足，在基于静态可拓集合的描述逻辑的基 础上进行了动态可拓集合扩展，提出了新的基于动态可拓集合的描述逻辑。定 义了该描述逻辑的语法形式；结合动态可拓集合与传统描述逻辑的语义解释方 法共同对描述的知识进行语义解释；研究该描述逻辑的基本推理问题，对基于 静态可拓集合的描述逻辑的一致性检测算法进行了可拓扩展，即增加了可拓变 换规则，生成了新的断言集的一致性检测算法，并证明了该算法的可靠性、可 终止性以及可判定性；分析了矛盾问题以及如何寻找求解矛盾问题的策略。 最后，为了增强基于动态可拓集合的描述逻辑描述概念的能力，在它的基 础上增加了构造算子一限定性数目约束( q ) ，提出了带限定性数目约束的可拓 描述逻辑。引入了形如蚣c 、敞c 的概念描述，并根据动态可拓集合与传 哈尔滨工程大学博士学位论文 hn 统描述逻辑的语义解释方法对它进行语义解释；重点研究了关于概念姓c 、 k r c 的断言的扩充规则，生成了带限定性数目约束的可拓描述逻辑的一致性 检测算法，并证明了该算法的可靠性、可终止性以及可判定性。 以上三个描述逻辑依次增强了传统描述逻辑在描述模糊的、动态的知识方 面的能力，并且实现了对矛盾问题求解策略的描述，使传统描述逻辑具有了更 强的知识表示能力。 关键词：描述逻辑；可拓学；静态可拓集合；动态可拓集合；可拓变换；限定 性数目约束 基于可拓集的描述逻辑研究 a b s t r a c t d e s c r i p t i o nl o g i ci sak n o w l e d g er e p r e s e n t a t i o nf o r m a l i s m sb a s e do n t h eo b j e c t , t ow h i c hp e o p l ep a ym o l ea n dm o r ep a r t i c u l a ra t t e n t i o na m o n gan u m b e ro ff o r m a l m e t h o d sr e p r e s e n t e db yk n o w l e d g e e s p e c i a l l yw i t ht h er e s e a r c ho fo n t o l o g ya n d s e m a n t i cw e br i s i n g ，t h ed e s c r i p t i o nl o g i ct h a ti st h eb a s eo fo n t o l o g yl a n g u a g ea n d s e m a n t i cw e bl o g i ch a sb e e nt h er e s e a r c hf o c u s a c c o r d i n gt ot h ed i f f e r e n td e m a n d so fa p p l i c a t i o nf i e l d s ，t h ek n o w l e d g et ob e d e s c r i b e di sa r a n g eo fc o m p l e x ，r e q u i r i n gt h ed e s c r i p t i o nl o g i ct ob ea b l et oe x p r e s s a l lk i n d so fk n o w l e d g e h o w e v e r , t h et r a d i t i o n a ld e s c r i p t i o nl o g i cc a no n l yd e s c r i b e t h es t a t i c ，c e r t a i nk n o w l e d g e ，w i t hf i n i t ee x p r e s s i o na b i l i t y , t h u sw en e e dt og oa l o n g t h ee x t e n s i o nr e s e a r c h i no r d e rt oe n d o wt h et r a d i t i o n a ld e s c r i p t i o nl o g i cw i t ht h e a b i l i t yt on o to n l ye x p r e s sa n di n f e rt h ed y n a m i c ，f u z z yk n o w l e d g e ，b u ta l s od e s c r i b e t h es o l v i n gs t r a t e g yo ft h ec o n t r a d i c t i o np r o b l e mt or e a l i z et h es h a r ea n dr e u s eo f s t r a t e g y , i nt h i sp a p e rt h ee x t e n s i o ns e ta n de x t e n s i o nt r a n s f o r m a t i o ni ne x t e n i c sa l e i n t r o d u c e da sf o l l o w s ： f i r s to fa l l ，s i n c et h et r a d i t i o n a ld e s c r i p t i o nl o g i cc a nn o td e s c r i b ef u z z y i n f o r m a t i o na n dt h ef u z z ye x t e n s i o nd e s c r i p t i o nl o g i ci sn o ts u i t a b l et od e s c r i b et h e c o n t r a d i c t i o np r o b l e ma l t h o u g hi tc a nd e s c r i b ef u z z yi n f o r m a t i o n , ad e s c r i p t i o n1 0 9 i c b a s e do ns m i l ee x t e n s i o ns e ti sp r o p o s e d t h es t a t i ce x t e n s i o ns e t , i n s t e a do ft h e c l a s s i c a ls e ta n df u z z ys e t , i su s e dt ob et h es e tt h e o r yf o u n d a t i o no ft h ed e s c r i p t i o n l o g i c s e m a n t i ce x p l a n a t i o n so f d o m a i nc o n c e p t s ，r e l a t i o n sa n di n d i v i d u a l sa r cg i v e n , a n dt h ec o n s i s t e n c yc h e c k i n ga l g o r i t h mt a b l e a uo ft h et r a d i t i o n a ld e s c r i p t i o nl o g i c a s s e r t i o nf o r m u l as e ti se x t e n d e dt oi m p l e m e n tt h ee x p a n s i o no fa s s e r t i o nf o r m u l as e t w i t hp o s i t i v eo rn e g a t i v er e g i o nd e p e n d e n td e g r e e , t h u st h ec o n s i s t e n c yo fa s s e r t i o n f o r m u l as e ti sd e c i d e d s e c o n d l y , s i n c en e i t h e r t h et r a d i t i o n a ld e s c r i p t i o nl o g i cn o rt h ef u z z yd e s c r i p t i o n l o g i cc a np r o v i d es t r a t e g yf o rt h es o l v i n go fc o n t r a d i c t i o np r o b l e mb yd e s c r i b i n gt h e q u a n t i t a t i v ec h a n g ea n dq u a l i t a t i v ec h a n g eo fm a t t e r , an e wd e s c r i p t i o nl o g i cb a s e d 哈尔滨工程大学博十学位论文 o nt h ed y n a m i ce x t e n s i o ns e ti sp r o p o s e d ，w h i c hi sf l l le x t e n s i o no ft h ed e s c r i p t i o n l o g i cb a s e d0 1 1t h es t a t i ce x t e n s i o ns e t t h es y n t a xf o r mi sd e f i n e d , a n dt h ed y n a m i c e x t e n s i o ns e tc o m b i n e dw i t ht h es e m a n t i ce x p l a n a t i o nm e t h o do ft r a d i t i o n a l d e s c r i p t i o nl o g i ci su s e dt og i v et h es e m a n t i ce x p l a n a t i o no f t h ed e s c r i b e dk n o w l e d g e t h eb a s i cr e a s o n i n gp r o b l e mi sr e s e a r c h e d , t h ec o n s i s t e n c yc h e c k i n ga l g o r i t h mo f t h e d e s c r i p t i o nl o g i cb a s e do ns t a t i ce x t e n s i o ns e ti se x t e n d e d ，a n di e t h ee x t e n s i o n t r a m f o r m a t i o nr u l ei sa d d e dt og e n e r a t et h en e wc o n s i s t e n c yc h e c k i n ga l g o r i t h mo f t h ea s s e r t i o nf o r m u l as e t t h er a t i o n a l i t yo ft h en e wa l g o r i t h mi sp r o v e dd e t a i l e d , i n c l u d i n gt h ep r o o f so fr e l i a b i l i t y , t e m f i n a b i l i t ya n dd e c i d a b i l i t y t h ec o n t r a d i c t i o n p r o b l e m a n dh o wt of i n dt h es t r a t e g yo fs o l v i n gc o n t r a d i c t i o np r o b l e ma r ea n a l y z e d f i n a l l y , t oi m p r o v et h ea b i l i t yo fd e s c r i b i n gc o n c e p to ft h ed e s c r i p t i o nl o g i c b a s e do nd y n a m i ce x t e n s i o ns e t ，t h ec o n s t r u c t o r - q u a l i f y i n gn u m b e rr e s t r i c t i o ni s a d d e da n dt h ee x t e n s i b l ed e s c r i p t i o nl o g i cw i t hq u a l i f y i n gn u m b e rr e s t r i c t i o n si s p r o p o s e d t h ec o n c e p td e s c r i p t i o n , s u c ha s k r c ，g 氓c ，i si n j e c t e d , a n dt h e s e m a n t i ce x p l a n a t i o ni sg i v e na c c o r d i n gt ot h es e m a n t i ce x p l a n a t i o nm e t h o do ft h e d y n a m i ce x t e n s i o ns e ta n dt h et r a d i t i o n a ld e s c r i p t i o nl o g i c t h em a i nr e s e a r c hf o c u s i st h ee x t e n s i o nr u l e so fa s s e r t i o nf o r m u l ac o n c e r n i n gt h ec o n c e p t 拙c ，蚴cm c o n s i s t e n c yc h e c k i n ga l g o r i t h mo ft h ee x t e n s i b l ed e s c r i p t i o nl o g i cw i t hq u a l i 驰g n u m b e rr e s t r i c t i o n si sg e n e r a t e d , a n dt h ep r o o f so fi t sr e l i a b i l i t y , t e r m i n a b i l i t ya n d d e c i d a b i l i t ya r eg i v e n t h ea b o v et h r e ed e s c r i p t i o nl o g i cm e t h o d si nt u r ne n h a n c et h ea b i l i t i e so ft h e t r a d i t i o n a ld e s c r i p t i o nl o g i ci nd e s c r i b i n g 血z 2 孤d y n a m i ck n o w l e d g e ，a n dr e a l i z et h e d e s c r i p t i o no ft h es o l v 吨s t r a t e g yo fc o n t r a d i c t i o np r o b l e m ，e n d o w i n g t h et r a d i t i o n a l d e s c r i p t i o nl o g i cw i t has t r o n g e ra b i l i t yo fk n o w l e d g er e p r e s e n t a t i o n k e y w o r d s ：d e s c r i p t i o nl o g i c ；e x t e n i c s ；s t a t i ce x t e n s i o ns e t ；d y n a m i ce x t e n s i o n s e t ；e x t e n s i o nt r a n s f o r m a t i o n ；q u a l i f y i n gn u m b e rr e s t r i c t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：王前 日期：2 曲甲年月膨日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定；即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、 作者( 签字) ：王静 导师( 签字) 日期： 吖年彳月f 汨 ? c | 年( 月 第1 章绪论 第1 章绪论 1 1 课题的研究意义 在当今信息膨胀的时代，建立良好的知识表示系统以求有效而准确地表达 信息是非常重要的，目前为止，已有大量的研究成果在许多领域中得到了很好 的应用。现实生活中信息形式多种多样，为了在计算机中描述这些信息，应构 建多个形式系统以满足实际需要。描述逻辑( d e s c r i p t i o nl o g i c ，d l ) 恰好是 这样一族形式系统，因此在众多知识表示的形式化方法中，它越来越受到人们 的特别关注，成为近十几年来研究和发展最快的知识表示的形式化工具之一l l j 。 描述逻辑具有很强的表达能力，能提供有效的推理服务并保证推理过程总能停 止，返回确定的结果，因此它被认为是以往表示工具的逻辑重构和统一形式化。 随着描述逻辑经典理论研究的相对成熟，它应用的范围也日趋广泛，如在软件 工程【2 】、数据库网、概念建模f 4 】和服务计算1 5 】等领域中得到了很好的应用。 随着网络的飞速发展，特别是语义w e b 的提出加快了描述逻辑的研究进程 嘲。语义咖究的主要目的是使网络中的信息具有语义，能够让计算机理解 并对网络资源进行分析、处理，最终实现自动推理。语义w e b 是通过本体来描 述语义的【1 - 8 1 ，所以为了很好的使用本体，首先要解决的问题就是研究一种合适 的本体描述语言【9 】。2 0 0 1 年w 3 c 在语义w r e ba c t i v i t y 下专门成立了一个 “w e b - o n t o l o g y ( w e b o n t ) 的工作组，其主要目标就是在现有w - e b 标准之上 创建一种对本体进行定义和描述的语言。目前已有的主要的w e b 本体语言是 d a m l + o i l 1 0 。1 1 1 和已成为w 3 c 国际标准的o w l 语言【1 2 1 3 1 ，而这些本体语言均 可与描述逻辑对应。例如，i a nh o r r o c k s 证明了d a m l + o i l 语言与描述逻辑 s h o i q ( d ) 等价【1 0 】；i a nh o r r o e k s 和pfp a t e l s c h n e i d e r i 正明了o w ld l 与描述逻 辑s h o 吖( d ) 等价【1 2 1 。因此，f r a n zb a a d e r 等人明确指出描述逻辑可以作为语义 w e b 的本体语言，为语义w b b 提供必要的逻辑基础 9 1 。描述逻辑也因此成为了人 们关注的热点，并且随着语义w e b 和本体研究的不断升温，描述逻辑将发挥巨 大的作用。 本体的提出是为了描述信息的语义，从而实现知识的共享和重用。根据应 哈尔滨工程大学博十学位论文 用领域的不同需求，本体要描述的信息也各式各样，纷繁复杂，那么描述逻辑 作为它的描述语言就要有表达各类知识的能力。但是，传统的描述逻辑只能描 述静态的、确定的知识，而不能对动态的、模糊的、不确定的信息等进行表示 和推理，所以传统的描述逻辑被认为是不充分的。 为了适应领域的需求，目前对描述逻辑的各种扩展研究也越来越多。但是， 如何通过描述逻辑描述领域事物的量变和质变，从而实现目标与条件不相容的 问题( 矛盾问题) 的求解策略的共享和重用，是目前研究较少的。而事实上， 各个应用领域中，矛盾问题无处不在，所以本文认为使描述逻辑具有这方面的 能力是很重要的。 对于矛盾问题，我国学者蔡文研究员提出了一门新的学科可拓学【悼1 刀对它 进行研究，为矛盾问题的求解提供了合理的理论和方法。为了推进可拓学与人 工智能的结合应用，中国人工智能学会特成立了可拓工程专业委员会对它进行 研究【陆1 9 1 。2 0 0 5 年1 2 月在北京召开的香山科学会议，针对“可拓学的科学意义 与未来发展 进行了讨论，会议指出“可拓学是哲学、数学和工程学交叉的学 科，它的研究对象决定了它与控制论、信息论和系统论一样，是- - f - j 涉及范围 广泛的横断学科。它在各门学科和工程技术领域中应用的成效，不在于发现新 的实验事实，而在于提供一种新的思想和方法 2 0 l 。经过多年的研究，可拓学 在理论和方法上已取得了创新性、突破性的研究成果1 2 1 1 ，在人工智能 2 2 - 2 3 1 、数 据挖掘 2 4 - 2 5 1 、检测防明、控制【2 冽、管理和决策 3 0 - 3 1 】等领域取得了良好的成绩。 特别是可拓集合、可拓逻辑等的提出，为矛盾问题的求解提供了合理的理论基 础。 基于可拓学求解矛盾问题的思想和方法，本文认为将可拓学的理论引入到 传统描述逻辑中，对它进行扩展研究，是一个重要的研究课题，它能够使描述 逻辑具有描述矛盾问题的求解策略的能力，从而可以实现对这些策略的共享和 重用，也使描述逻辑作为语义w e b 的逻辑基础和本体语言更加充分。 1 2 描述逻辑的研究现状 描述逻辑是一种基于对象的知识表示的形式化工具，也叫概念表示语言或 术语逻辑。描述逻辑吸收了k l o n e 3 2 】的主要思想，是一阶逻辑的一个可判定 子集，它具有合适定义的语义，并且具有很强的表达能力和可判定性，能保证 2 第1 章绪论 推理过程总能停止，并返回确定的结果( 1 j 。正是由于描述逻辑在语义、可判定 性以及面向对象的分类表示等方面的优点，它越来越受到人们的特别关注。 最早的描述逻辑系统是a l ，它包含的概念构造算子有原子非、交、全称 量词与限定存在量词，这个系统的语法、语义及推理算法已经非常完善【3 3 】。描 述逻辑族系中的其他语言都是a l 语言的扩展。 一般的，描述逻辑都建立在概念和关系之上，它依据提供的构造算子，在 简单的概念和关系之上构造复杂的概念和关系。通常描述逻辑包含以下构造算 子：交( 几) 、并( u ) 、非( ，) 、存在量词( 弓) 、全称量词( v ) 。当描述逻辑 系统包含的算子不一样时，对应的性质特征也不相同。因此，可以通过取算子 集合的某一个子集来构建应用所需的系统。 为了适应应用领域的需求，一些表达能力更强的描述逻辑语言被提出。例 如，在a g c 的基础上，增加数量限定、函数性约束或定性数量限定，就可以 分别生成不同表达能力的描述逻辑a l c n 、a l c f 、a l c q t 3 4 。 理论方面的研究，成绩最为突出的是德国t e c h n i s c h e 大学的f r a n zb a a d e r 教授及其合作者，他们共同撰写了n ed e s c r i p t i o nl o g i ch a n d b o o k ：t h e o r y ， i m p l e m e n t a t i o n ，a n da p p l i c a t i o n s ) ) 一书 3 4 1 ，该书几乎囊括了研究和学习描述逻 辑这门学科必需的所有基础知识。 在此基础上，英国m a n c h e s t e r 大学的i a nh o r r o c k s 和u l r i k e s a t t l e r 等人研 究了一系列与角色有关的描述逻辑系统，如带不同传递角色的概念语言1 3 5 删， 判定a l c n i f 满足性p s p a c e 算法1 3 7 1 ，带传递角色、逆角色及角色分层的描述 逻辑【3 8 坞各种强表达能力描述逻辑系统的实际推理【3 喇，并且全面研究了 s h i q 系统【4 ，证明了语义w c b 的本体语言o i l 与s h i q 的等价1 4 2 1 。基于s h i q 推理机制的有效性，它目前已成为国内外研究的热点，而描述逻辑的理论知识 体系也正日趋完善。 随着描述逻辑在应用领域的研究的不断深入，研究者们发现在许多情形 下，即使是对描述逻辑进行经典扩充，如添加构造算子，关系的复合等，也已 经不能满足具体应用的需要。针对现实领域中( 特别是语义w e b 领域) 需要描 述的信息种类，国内外学者对传统描述逻辑进行了深入的扩展研究，如模糊扩 展、动态扩展、缺省扩展 4 3 琊】等等，下面着重介绍与本文相关的前两种的国内 外研究情况。 哈尔滨工程大学博士学位论文 1 描述逻辑的模糊扩展研究 虽然经典的描述逻辑能很好的处理精确信息，但是它不能处理模糊和不精 确的信息，现实世界的人类知识和自然语言中存在着大量的不精确性和不确定 性，因此，经典的描述逻辑是不充分的，必须对它进行模糊扩展，目前这方面 的研究已经有很多。 s t r a c c i a 提出的模糊描述逻辑f a l c ( f u z z y a l c ) 是在传统描述逻辑a l c 的基础上进行的模糊化扩展，它的语法与a l c 的语法相同，但它的语义是根 据z a d e h 对模糊集的语义解释方法 4 6 1 和描述逻辑a l c 的语义解释方法来共同 给出的 4 7 1 。f a l c 结合模糊逻辑和描述逻辑的特性，给出了基于约束传播的推 理算法，并证明了f a l c 推理问题的复杂性。 随着模糊描述逻辑思想的提出，人们开始在f a l c 的基础上，增加各种构 造算子或算子的集合来提高模糊描述逻辑的表达能力，例如，s a n c h e z 等人在 f a l c 的基础上扩展了模糊关系的数量约束【4 3 j ；g i o r g o ss t o i l o s 等人则在f a l c 的基础上增加构造算子模糊关系的传递、包含、逆以及对模糊关系的不带资格 限定的数量约束等，提出了模糊表示能力更强的模糊描述逻辑f s h i n 4 9 1 ，并且 给出了该模糊描述逻辑的推理算法【5 0 j ；之后，为了充分的描述语义w e b 中的信 息，g - i o r g o ss t o i l o s 在文献 5 1 1 中，提出了模糊描述逻辑f - s h o i n ，f - s h o i n 是 在f - s h i n 的基础上又添加了模糊构造算子枚举个体，文中给出了e f a l c n 、 f - s h i n 和f s h o m 的a b o x 约束下的可满足性推理算法，但它没有给出t b o x 约束下的包含推理算法。 为了使表达能力更强的描述逻辑s h o i q ( d ) t l o 】能表示模糊知识，s t r a c e i a 将 模糊具体论域和模糊修饰词引入到s h o i q ( d ) h b ，提出了一种模糊描述逻辑 f s h o i q ( d ) t 5 2 1 ，f s h o i q ( d ) 将f - s h o i n t 5 1 】的不带资格限定的数量约束构造算子 扩展为带资格限定的数量约束构造算子，并增加了具体数据类型构造算子，给 出了f s h o i q ( d ) 的语法和语义。f - s h o i n 和f s h o i q ( d ) 的语义都建立在模糊 逻辑【5 3 】的基础上，但是目前f o s h o i n 只有a b o x 约束下的可满足性推理算法， 而f s h o i q ( d ) 的推理算法还没有解决。 为此，蒋运承等人提出了一种新的模糊描述逻辑f s h o i q i s 4 1 ，它介于 f - s h o i n 和f s h o i q ( d ) 之间，即f s h o i q 的表达能力大于f - s h o i n 的表达能 力，而小于f s h o i q ( d ) 的表达能力，该描述逻辑给出了f s h o i q 的语法和语义， 4 第1 章绪论 宣皇昌高昌暑；昌宣暑宣暑i 宣i i 置昌i i i i 暑葺皇昌高i 毒置萱暑暑i 暑i i i 置暑i 暑i 暑暑i 宣i 葺暑暑葺毒 还给出了f s h o i q 的a b o x 约束下的可满足性推理算法，并证明了可满足性推 理算法的正确性，以及f s h o i q 的t b o x 约束下的包含推理可以转化为可满足 性推理问题。 除了以上模糊描述逻辑，国内还有以东南大学为首的非常突出的研究。 针对在模糊解释中的隶属度不是离散值，而是区间【0 ，1 】上的连续值的问 题，李言辉在文献【5 5 】中提出了模糊描述逻辑f a l c n 下的模糊解释离散化方 法，从而使解释中的隶属度都属于一个特殊的有限离散集合，文中给出了一般 术语公理下f a l c n 推理问题的离散t a b l e a u 推理技术，包括离散t a b l e a u 的定 义以及离散t a b l e a u 的构造算法，并证明了算法的正确性、完备性和复杂度； 文献【5 6 】提出了一种扩展的模糊描述逻辑e f a l c ，它是针对f a l c 不能描述复 杂模糊信息的缺点，将模糊概念和模糊关系的截集引入到了描述逻辑中，建立 了新的知识表示逻辑体系，并给出了模糊描述逻辑到扩展模糊描述逻辑的转化， 从而证明模糊描述逻辑e f a l c 具有比f a l c 更强的表达能力；文献【5 7 】在 e f a l c 的基础上，研究了支持数量约束的扩展模糊描述逻辑e f a l c n ，并研究 了它的空间复杂性，该描述逻辑因为引入了不带资格限定的数量约束构造算子， 所以描述逻辑e f a l c n 的表达能力又比e f a l c 的表达能力更强；文献 5 8 n 是在e f a l c 的基础上，研究了支持术语公理约束的扩展模糊描述逻辑e f a l c r + 的推理算法，并对该算法进行了优化，证明了优化后的算法是正确完备的而 且它的最坏时间复杂性已达到该问题推理算法的复杂度下界，是实现术语公理 约束下模糊知识库推理的有效算法；文献 5 9 】针对e f a l c 缺乏t b o x 约束下的 推理算法的不足，提出了t b o x 约束下的可满足性问题推理算法；文献【6 0 】为了 使模糊描述逻辑能够支持模糊隶属度的比较，在描述逻辑a l c n 的基础上定义 了一种新的扩展模糊描述逻辑f c a l c n 。并给出了f c a l c n 的推理算法，在 表达能力方面该描述逻辑比现有模糊扩展的a l c n 更强，而它的推理复杂性却 没有增加，所以它能够表达应用领域中涉及模糊隶属度比较的复杂模糊知识， 并且实现对它们的推理。 以上这些研究成果，为语义w e b 和描述逻辑的发展做出了重要的贡献。 不过，目前对描述逻辑的模糊扩展都是通过引入了模糊集理论来实现的， 而模糊集合在定义的时候只会给出元素属于集合的程度，并不会对不属于集合 的元素进行度量，所以模糊解释下的描述逻辑很难描述事物量变和质变的过程， 5 哈尔滨工程大学博士学位论文 但是现实领域中，特别是描述问题的求解过程时是需要描述这样一个事物变化 的过程的，所以有必要对描述逻辑进行这方面的研究。 2 描述逻辑的动态扩展研究 作为知识表示的形式化工具，描述逻辑在信息系统、软件工程、自然语言 处理【6 l 】等领域得到了广泛的应用，特别是在语义w e b 中，描述逻辑扮演着重要 的角色。它具有较强的描述能力，同时保证了相关推理问题的可判定性，具有 有效的推理算法。但是，传统描述逻辑主要是用来对静态知识进行表示和推理 的，不能有效的对动态知识进行表示和推理，而实际的应用领域中，不仅仅存 在静态知识，还有大量的动态性知识需要描述，所以相对于实际应用的需要， 描述逻辑仍然存在不足。为了满足领域需求，人们开始研究动作的表示和推理 问题，并用来扩展传统描述逻辑。 文献【6 2 】中对目前关于动作的相关研究进行了总结归纳，并分析了动作理 论的主要研究趋势。动作的表示和推理是人类智能的重要组成部分，m c c a r t h y 认为关于动作的表示和推理在常识推理中具有根本性的作用【6 3 j ，因此动作推理 在人工智能研究中占有重要的地位。目前，关于动作理论的研究，它主要有基 于情景演算的唧】和基于动态逻辑的【6 5 j ，另外还有时态逻辑、流演算、进程代数 及7 演算等也是动作推理中常采用的形式系统。它们的研究对象都是动态领域 中的动作表示与推理问题。文献【6 6 对状态的描述、动作的表示与推理以及动 态领域中的知识表示等问题进行了研究，但在关于动作的前提公理和效果公理 中，文章并没有仔细考虑世界的当前事实和状态，也没有指明如何删除那些不 再成立的事实或公式，因而这些公理的表达能力是不够的。m a c a r t h y 在1 9 6 9 年提出情景演算【6 3 】，主要是针对动态领域中的问题求解和逻辑程序设计而提出 的，近来有很多工作对它进行了扩充和应用。由l e v c s q u e 和r e i t e r 等人提出的 g o l o g 6 7 1 及其变种 6 s - 6 9 就是在情景演算的基础上建立的一种动态逻辑设计语 言1 7 0 】，可以使用g o l o g 编写的程序来指导主体的行为。虽然动作理论和情景 演算都可以描述动作，但是，这些动作描述基本上都是以命题的形式给出的具 体动作的描述，很少采用面向对象的方法来表示，因而其表达能力受到很大限 制。此外，他们描述的动作公理( 如前提公理、后继状态公理等) 一般是以每 个动态关系为基础进行刻画的，公理的数量较多，且没有把动作看作一个整体 来考虑，容易出现不一致的情况。 6 第1 章绪论 文献【7 l 】中通过分析描述逻辑与命题动态逻辑p d l 之间的关系，提出了一 种认知操作符k 来对动作语言进行扩充，从而表示关于动作的知识，有效地解 决规划问题。文中将世界的状态表示为个体，状态之间的转换表示为个体之间 的关系，并以描述逻辑为基本框架，给出了静态公理、前提公理、效果公理、 框架公理模式以及初始状态描述公理等，进而使用这些公理来进行规划。但是， 把每个状态表示为描述逻辑中的个体时，这些个体是抽象的个体，当状态数量 急速增加时，状态转化图就将变得更为复杂，这样将导致整个规划算法的时间 复杂度和空间复杂度都同时增加，影响了规划的效率。另外，动作和知识是密 切相关的，动作是否能够执行，要根据领域知识是否能够满足动作执行的前提 条件来判断，而执行动作之后必将导致领域知识的修改，因此应该将动作和知 识有机地结合起来。 为了对动作和规划进行统一表示和推理，文献【7 2 】对描述逻辑进行了扩充， 提出了时序描述逻辑a l c q l t 和a l c q i u s ，即在描述逻辑的基础上进行了时序 扩充，从而可以对依赖于时序的概念、关系以及动作等进行描述，具有较强的 表达能力和可计算性能，但是由于时序的引入使得概念、关系和动作的描述更 为复杂，而且他们的工作主要是在时序描述逻辑方面的理论性研究，并没有结 合动作理论进行研究。文献【7 3 】则提出使用描述逻辑l o o m 来刻画动作间的层 次关系，将动作看成静态概念来描述，这是一种有效的描述动作的方法，但是 它限定的领域范围比较窄，还不能推广到动态领域中。 w o l t e r 提出了一种动态描述逻辑 7 4 1 ，其主要目的是在概念描述逻辑中引入 动态维表示动态概念和关系，是对描述逻辑在某些表达能力方面的理论扩充， 只是它没有体现领域世界的动态变化。 以中科院史忠植为首的一些学者也提出了动态描述逻辑d d l 7 5 1 ，但是d d l 与w o l t e r 的不同，它是根据语义w e b 的特点和需求，在传统描述逻辑a l c 的 基础上增加了对动作的表示和推理，从而描述语义w e b 中的动态服务。文中将 静态知识和动态知识的表示与推理有机的整合在一起，不但给出了具体的动作 描述方法，而且按照传统描述逻辑的语义解释给出了动作的语义解释，从而形 成了一种能同时处理静态知识和动态知识的统一的形式化逻辑框架。d d l 具有 清晰的语义特征，既提供了可判定的推理服务，又能有效地对静态知识、动态 过程和运行机制进行表示和推理。d d l 还可以很好的应用于主体模型与设计 7 哈尔滨t 程大学博七学位论文 中，文献 6 2 ，6 6 ，6 7 d f l 提出了基于动态描述逻辑的主体模型以及基于动态描述逻 辑的多主体协作模型，为智能主体的设计奠定了很好的基础。 广西师范大学王驹、蒋运承等人在动态描述逻辑d d l 的基础上进行了模 糊扩展，提出了一种模糊动态描述逻辑f d d l y s ，定义了它的语法和语义，研 究了它的推理机制，为语义w e b 提供了更为合理的逻辑基础。 由于动态描述逻辑d d l 仅适用于闭世界假设( c l o s e dw o r l da s s u m p t i o n ) 的情况，而语义w e b 的开放性和分布性，往往需要采用开世界假设，在信息不 完全的情况下进行推理。为此，文献 7 9 】在d d l 的基础上进行了扩展研究，它 以描述逻辑a l c o 的动态扩展为例，提出了动态描述逻辑d - a l c o ，并将 a l c o 和命题动态逻辑的t a b l e a u 算法以及对可能模型途径的处理有机地结合 起来，文中给出了d a l c o 的t a b l e a u 判定算法，并证明了算法的可终止性、 可靠性和完备性。 针对动态描述逻辑d d l 在描述和分析多个动作间关系( 尤其并发关系) 时，能力不足的问题，济南大学马炳先提出了对多个动态描述逻辑动作间关系 描述和分析的p e t r i 网方法i 舳1 ，讨论了动态描述逻辑动作的等价p e t r i 网描述， 进一步通过对动作描述的推理和各个动作的p e l r i 网共享合成操作，得到多个动 态描述逻辑动作的p e t r i 网系统。在此基础上，应用p e t r i 网的相关理论与方法， 如可达图分析方法，研究了多个动态描述逻辑动作间关系的分析与判定方法， 对动态描述逻辑动作理论的描述和分析能力进行了必要的扩充。 以上这些描述逻辑都是为了使传统描述逻辑能具有描述动态知识的能力 而提出的，它们都在一定程度上实现了对动态性知识的表示和推理，除此之外， 还有很多的相关研究。但是这些研究都不是针对矛盾问题而进行的动态扩展， 即它们不是将动态知识作为求解矛盾问题的策略而提出的，然而现实生活中矛 盾又无处不在，因此，本文认为这是一个值得研究的问题。 随着描述逻辑表示和推理能力的不断提高，它在各个领域中的应用也越来 越多。近年来，在计算机科学和人工智能的研究中，描述逻辑占据着非常重要 的地位，应用的范围也日趋广泛，在软件工程 2 , s l 】、概念建模心8 2 】和服务计算 5 1 等领域中得到了很好的应用，另外，描述逻辑在数据库方面的应用也非常突出 3 1 。文献【8 3 】首先研究了描述逻辑与数据库的关系，分析了描述逻辑在数据库中 的各种应用，针对数据库的模式设计问题，提出了描述逻辑d l r i s 4 i 和 3 第1 章绪论 a l n u i 龉，研究了如何将数据库的e r 模型转化为描述逻辑d l r