（计算机科学与技术专业论文）基于描述逻辑的推理机设计实现及其分布化研究.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅：学校可以公布学位论 文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文 ( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保 密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 2 日期： 冱2 生：l 日期：细7 ，年f 基于描述逻辑的推理机设计实现及其分布化研究 摘要 语义w e b 的发展使得其逻辑基础描述逻辑也成为研究的一个 热点。描述逻辑支持推理，其推理主要涉及如下问题：概念可满 足性( c o n c e p ts a t i s f i a b i l i t y ) ，包含关系( s u b s 姗p t i o n ) ，可满 足性( s a t i s f i a b i l t y ) ，实例检测( i n s t 锄c ec h e c k i n g ) ；而可满 足性是关键问题。用于解决可满足性的t a b l e a u 算法，在当前国 外的推理机研究中发挥了重要的作用。但t a b l e a u 算法复杂性和 低效率制约了其实际的应用。鉴于国内推理机研究的贫乏和当前 推理机效率不高，本文将设计实现一个基于t a b l e a u 算法的推理 机原型系统，作为算法优化和相关研究的起点；同时，本文将研 究算法内部机制，结合并行计算研究，进行对t a b l e a u 算法基础 上的推理机分布化的探索。 关键词：t a b l e a u 算法，描述逻辑，并行计算，语义w e b t 丑罡d e s i g n0 fr e a s o n i n gs y s t e mb a s e do n d la n dp a ra i ，l e la l g o r i t h mr e s e a r c h t h ed e v d o p m 钮to fs a 丑趾t i cw 曲i n 、r i t e sm o r ea n dm o r e 坞s a m ho nt h ed 鹤c r i p t i v el o g i cw h i c hi s 也el o g i c 内喇1 捌o no f t h e s e m 蛆t i cw r c b d ls u p p o 懈吐l cr e 船o n i n g 锄dm e 圮啪n i n g0 fd l c o n l 痢- m sf - o u rm a i ne l e m c n t s ： c o n c e p ts a t i s f i a b i l i t ms u b 吼i m p t i o n s a t i s f ia _ b i l t ki n s t 锄1 c 七c h e c i 【i n g ；锄o n gt l l e s ef o u re l 锄e n t st h e s a t i s 丘a b i n yi st 1 1 ek e yp o i n tf o rt h ed l 哟s o n i n g 1 1 1 e1 a b l 咖 a l g o r i t l l mn o wi sp l a 姐n ga ni m p o r t a n tr o l ei nm er e 勰o n i n gs y s t 锄 r e s 黜h ；h o w e v e r ，t h el o we 伍c i e n c ya n dc o m p l e x i t yr e s t r i c t i t s a p p l i c a t i o n t bf i l l f i ut h ed o m e s t i cr e q u i r e 蜘e n tf o rt 1 1 e 麟o n i n ga n d r c a l i z c 锄a r c h e 呻a ls y s t 锄f o rf h r t h 凹r 龉e 砌，t h i sp 印盯f o c i l s 部 0 n d i 目l i n gar e 邪o n i n gs y s t 锄b 鹪e do nt a b l 船ua l g o r i t h mf o fd l ； 跏t h e rt a s ki st a _ k i i l ga d v 嘲g eo ft h e i s 仃i b u t o do p s y s t e m 锄d p a r a l l c lc o m p u t i n g t h n o l o g y t or c a l i z ean e 、 rr e 弱o n i n gs y s t 锄 1 锄rw o r d s ：t a b l e a ua l g o r i t l m ，d e s c r i p t i o nl o g i c ， p a r a l l e lc o m p u t i n g ，s e m a n t i cw e b 4 第一章绪论 1 1 研究背景 2 0 0 1 年，w w w 的创始人b 锄e r s 【七e 提出语义w 曲【面mb 锄e r s - 【脱， 2 0 0 1 1 。语义w 曲研究的主要目的就是扩展当前的w w w ，使得网络中信息 都是具有语义的，是计算机能够理解和处理的，便于人和计算机之间的交互 与合作。其研究的侧重点就是如何把信息表示为计算机能够理解和处理的形 式，即带有语义。语义w 曲主要基于l 和i f 瓜d f s ，并在此基础上构 建本体和逻辑推理规则，以完成基于语义的知识表示和推理，从而能够为计 算机所理解和处理。在语义w 曲的研究中，知识表示、本体论等都是其重要 的研究内容，它们都是不可分割的。在知识的语义表示和推理中，有两个层 次的研究：一是在理论上，基于逻辑形式化的研究工作，即以一阶谓词逻辑 为代表的各种逻辑体系，最常见的即描述逻辑；二是基于这些逻辑理论的本 体论的研究，可以看作是具体的应用研究。 描述逻辑建立在概念( c c c p t ) 和关系( r e l a t i o n ，r o l e ) 之上，其中概念解释 为对象的集合，关系解释为对象之间的二元关系，描述逻辑具有合适定义的 语义和很强的表达能力。一个描述逻辑系统包含四个基本组成部分：表示概 念和关系的构造器，t b o x 包含断言，a b o x 实例断言，n 町x 和a b o x 上的推 理机制。一个描述逻辑系统的表达能力和推理能力取决于对以上几个要素的 选择以及不同的假设。在众多知识表示的形式化方法中，描述逻辑在十多年 来受到人们的特别关注，主要原因在于：它们有清晰的模型理论机制，很适 合于通过概念分类学来表示应用领域，并提供了很好的推理服务 f m z b 船d 2 0 0 3 】。 描述逻辑是一阶谓词逻辑的一个可判断的子集，可以提供推理的支持， 推理可由描述逻辑的推理机实现。在语义w e b 的应用中，推理机起着至关重 要的作用，信息的有效的分类和检索即是推理机的功用。在当前的推理机的 设计与实现中，t a b l e a u 算法是实现推理的核心：这一算法也来自于谓词逻 辑，当描述逻辑作为谓词逻辑的子集引入后，t a b l e a u 算法也被引入了描述 逻辑，并成为推理的基础。 描述逻辑只是知识表示的一种方式，在此之前发展起来的如产生式系统 等表示方式，也有相应推理机，常称为通用推理机。例如j e s s ： j 髑s ( j a v ae x p e f ts h d is y s t 锄) 是基于产生式的前向推理引擎，许多上层的推 7 理任务，都要映射到这个推理引擎上来运行。j 嚣s 原则上可以处理各种领域 的推理任务，只要系统能够为j e s s 提供这个领域的特有领域规则( 产生式形 式给出) 和事实信息( a s s e r t i o n 形式给出) 。 但是由于通用推理机在基于描述逻辑领域的应用效率低下，针对本体的 推理，越来越多地集中在了几种标准的本体语言上，如o w l 、d a m l 、 r d f s r d f 等，这样，研究者给出效率更高的，针对这些具体应用的推理机。 如r a c e r 、f a c = t 、p e l l c t 就是这类具体有强烈针对性的推理机。它们的优 点是：效率上有所提高，使用上非常方便，并在实际中得到了一定应用。以 i 认c e r 为例，在语义w 曲、电子商务、医疗、自然语言处理、工程决策系 统、知识工程、软件工程领域都得到了实际的应用。尽管国外在基于1 抽l e 孤 算法的研究中已有成功的商用化产品，但国内在此领域的研究还是刚刚开 始。 1 a b l e a l l 算法是较复杂的，从效率上，需要多项式级的时间。在实际的 应用受到很大的限制，在描述逻辑的主要应用语义网中，提供现有网络条件 下的推理是很难实现的，因为基于本体的研究，本体的数目是惊人的。例如 w e b l ( b 一2 是一个允许w e b 使用者在一个知识库中检索和增加知识的系统，目 前使用了6 9 0 0 0 个分类和8 7 8 0 0 个同w o r d n e t 的链接，并且可以扩展。一个 基于如此规模的w e b 应用，当同时收到多方用户的查询或检索请求时，在现 有的，r 曲l e 棚算法的复杂度及效率下，以及考虑现有的网络传输速率及延时， 无法要求系统在合理的时间给出正确的结论。 针对这种情况，如果想及时得到推理的结果，必须对呦l e 孤算法进行 优化，或是寻找其他出路。我们的思路是：是否可以利用分布化环境的优势， 有效的实现推理的并行计算，从而为问题提供一个解决方案。 1 2 本文的主要工作 1 讨论了推理问题中的关键问题一概念可满足性问题 张健，2 0 0 0 ；作 为一种一阶逻辑的公式可满足性证明方法，引入t a b l e a u 一算法 d o n i n ie t a l ，2 0 0 0 并分析了其性质，包括终止性、可靠性、完全性。然后讨论了其 他一些重要推理问题到概念可满足性问题的转化。 2 设计实现t a b l e a u 算法为核心的推理机原型。本文首先基于描述逻辑 的文法规则，设计实现其) ( i i l ls c h e m a 表示。在此基础上，围绕t a b l e a u 算 法，构造了一个推理机的原型系统。需要说明的是，试验系统目前仅仅作为 一种概念性验证来实现，因此系统的稳定性、执行效率、优化措施、界面友 好性等暂时不是研究内容。 3 基于推理机模型基础上的并行化研究。针对前文实现的推理机原型系 统，基于原型系统，结合并行计算技术和程序并行化研究，对t a b l e a u 算法 基础上的推理机分布化的探索，并提供了描述逻辑推理机并行化的一个思 路。 1 3 本文的组织 论文主要分四个部分：第一部分( 第l 章) 阐述本课题提出的背景、研 究目的和研究内容，深入分析了描述逻辑推理机研究现状，简单介绍了描述 逻辑以及t a b l e a u 算法，提出了本文的主要工作和意义。第二部分包括第2 、 3 章，第二章详细介绍了描述逻辑的发展，内涵及描述逻辑的推理问题，同 时阐述了a l c ( a t t r i b u t i v ec o n c e p td e s c r i p t i o nl a n g u a g e w i t h c o m p l e m e n t s ) 和描述逻辑推理中的关键问题一可满足性问题，进而详细的介 绍了t a b l e a u 算法。第三章则是对并行计算技术的介绍和对当前串行程序并 行化方法和思路的描述。第三部分包括第4 、5 章，这部分设计了基于t a b l e a u 算法为核心的推理机原型，并在此基础上进行了推理算法的并行化研究。第 四部分( 第6 章) 对设计实现进行了评价，对未来重点研究方向和前景作出 了展望。 9 2 1 描述逻辑的概述 第二章描述逻辑 2 。1 1 描述逻辑研究的发展 知识表示是人工智能的一个研究范畴，它主要涉及到知识表达的形式化 设计。其中一个主要的研究方面，就是用刻画对象的类和对象之间的关系方 法来表示知识。这种方法促进框架系统和语义网络在2 0 世纪7 0 年代的发展。 但是框架系统和语义网络一般都没有形式化定义和基于执行策略相应的推 理工具。k l o n e 系统的提出为基于逻辑的形式化迈出了重要一步，i ( l o n e 汲取了早期的语义网络和框架系统的思想，它提供了解释对象、类( 或者概 念) 、以及它们之间的关系( 或者联系) 的逻辑基础。这样的逻辑结构有两个 目的，首先是对用来构建类和关系的构造集的精确刻画；其二就是提供关于 语义的健壮和完全的推理过程。1 9 8 4 年r o nb r a c h 眦n 和h e c t o rl e v e s q u e 发表了文章”t h et r a c t a b i l i t yo fs u b s u m p t i o ni nf r 锄e b a s e dd e s c r i t i o n l a n g u a g e ”，该文章把k l o n e 作为语言的表达能力和推理的复杂性进行了折 衷。这就是描述逻辑研究的起源 f r a n zb a a d e r 。2 0 0 3 。 描述逻辑的研究经历了以下几个发展过程： 第一阶段( 1 9 8 0 1 9 9 0 ) ：提出执行系统，如k - l o n e b r a c h m a n ，1 9 8 5 ， k l o n e b r a c h r n a n ，1 9 8 5 ，k r e p m a y s ，1 9 9 1 ，b a c k p e l t a s o n ，1 9 9 1 ，l o o m m a e g r e g o r ，1 9 9 1 ，这些系统都借用了算法s t r u c t u r a ls u b s u m p t i o n a l g o r i t h m s ，该算法首次范化了概念描述，然后比较了规范化描述的语法结 构。这些算法通常是有效的，但缺点是没有表达能力，例如，对于有表达能 力的描述逻辑就不能区分s u b s u p t i o n i n s t a n c e 关系。 第二阶段( 1 9 9 0 1 9 9 5 ) ：开始引入新的算法到描述逻辑中，此算法被称 为t a b l e a u - b a s e da l g o r i th l i l s c h m i d t ，1 9 9 1 。算法对于少数的描述逻辑( 如 带有布尔算子的描述逻辑) 有效。为了判断知识库的一致性，算法 t a b l e a u _ b a s e da l g o r i t h l n 通过分解知识库中的概念来构建一个模型，然后 推导模型中元素上新的限制。算法要么因为构建模型产生矛盾而结束，要么 是得到规范模型而结束。由于少数描述逻辑系统中的s u b s 伽p t i o n 和 s a t i s f i a b i l i t y 降低了一致性，所以要用一致性检测算法来解决推理中出现 的问题。首次应用算法和c r a c k b r e s c i a n i ，1 9 9 5 的系统证明这些算法的优 1 0 化可以得到系统可接受的结果，但时间复杂度不再是多项式级。这一阶段也 看作描述逻辑系统推理复杂度分析阶段。 第三阶段( 1 9 9 5 2 0 0 0 ) ：这一阶段被描述为有表达能力的描述逻辑推理 的发展阶段，在基于t a b l e a u a p p r o c h 或者基于模型逻辑的转换下发展。优 化系统( f a c t h o r r o c k s ，1 9 9 8 ，r a c e h 明r s l e v ，1 9 9 9 ) 展示了有表达能力的 t a b l e a u 呐a s e da l g o r i t i l m 对一些大知识库都有好的应用效果。在这一阶段， 逻辑模型之间的关系和一阶逻辑的可判定部分的关系得到了详细的研究。 第四阶段( 2 0 0 0 至今) ：借用有表达能力的描述逻辑来加强描述逻辑系 统，继续完善算法t a b l e a u - b a s e da l g o r i t h m ，把描述逻辑应用到语义w e b ， 知识表示和集成生物信息 s t e v e n s ，2 0 0 1 s c h u l z ，2 0 0 4 中。 2 1 2 描述逻辑的研究内容 描述逻辑是人工智能领域研究的分支，它基于对象的形式化知识表示的 方法。它研究概念知识的表示问题，提供了定义好的语义和推理机制。描述 逻辑建立在概念( c o n 唧t ) 和关系( r o l e ) 的基础上，概念指的就是对象集，关系 就是指对象之间的二元关系。一个描述逻辑系统包括四个基本的组成部分： 表示概念和关系的构造集，t b o x 断言集，a b o x 断言集，t b o x 和a b o x 上 的推理。其中，t b o x ( t e r m i n 0 1 0 9 i c a lp a r t ) 是描述领域的公理 集。a b o x ( a s s e r t i o np a r t ) 是描述具体情形的公理集。 描述逻辑的研究主要涉及到以下几方面： ( 1 ) 理论研究方面：描述逻辑的表达能力主要取决于构造器的选择，选择 适当的构造器进行描述逻辑的扩展是描述逻辑的一个研究方面。其次寻找合 理的描述逻辑推理方法，提出相应的优化策略是另一个研究方面 ( 2 ) 知识表示系统的实现方面：现有的系统对有一定表达能力的描述逻 辑虽然有一定的应用效果，但对表达能力强的描述逻辑应用效果就不好，对 应表达能力强的描述逻辑的系统的开发是研究的一个方面。 ( 3 ) 描述逻辑的应用方面：描述逻辑有清晰的模型一理论语义，很适合于 通过概念分类来表示知识的应用领域。描述逻辑已用于概念建模、软件工程 中，但商业应用平台还未出现，这有待进一步研究。最近，提出的描述逻辑 应用于语义w e b 中。描述逻辑很适合于应用于有概念分类的地方。它的应用 领域可以进一步扩展。 ( 4 ) 推理领域的研究。推理领域研究针对描述逻辑的概念和关系，提供 t b o x 和a b o x 上的推理支持。目前主要的研究是针对t a b l e a u - b a s e d a l g o r i t l l i i l 效率，优化等的研究。本文即侧重这一方面的研究。 2 1 3 描述逻辑与谓词逻辑 描述逻辑的语义是以t a r s k i 一形式的模型理论给出。描述逻辑是可以转 换为谓词逻辑 b o r g i d a ，1 9 9 4 ，在转换的过程中主要由描述逻辑决定转换是 否产生一阶谓词还是超过一阶谓词，当描述逻辑允许关系传递闭包或者固定 点时，转换结果就超过一阶谓词。由于描述逻辑变元自由的语法和概念表示 个体集的事实，因而概念转换为带有一个自由变元的公式 b o r g i d a ，1 9 9 6 。 把概念看作一元谓词符号，关系看作二元谓词符号，于是得到如图2 1 所示 从描述逻辑到谓词逻辑的转换： 接述i 量辑掏迄器接连逻辑珥转换为豹谓词 顶橇含t伽e 危撬念上 j j m 跎 原子j 臀忿 cc ( x ) 枥仑空 c r dc ( x ) d ( x ) 概念并 c l d c o 帆d 氍念百定 1 i c ，c 毽约束讯c v x r 阮y ) - c 耗约束弧cj x r 伍y ) 愆曲 最小基敷约京 旨瞳 j ”习蝎帅舢 r 弧v - 炉y l 最尢萋数约束 血卫 聊- 一v i m 僻，1 ) r 亿孙l ) j _ 饥= y 一 v 2y 叶1 ) 茸性毋小基敲约束矶kc y i ，一，：l y 墨( 1 ，y 1 ) 1 ：x h j ，崩 c l 了j 属哇最大差致约束细& c v y l ，v y - 。v 舳( r ) c ，y ：) 。 r o l y 叭扒 c ( 蛐 d i 可：v - yy ，；，一) 粟子_ ；乏系r r 执 图z l 描述逻辑到谓词逻辑的转换 描述逻辑是一阶谓词逻辑的一个可判断的子集，使用描述逻辑代替一阶 谓词逻辑的原因是若直接使用一阶逻辑，而不附加任何约束，则： l 知识的结构将被破坏，这样就不能用来有效的驱动推理。 2 其表达能力太高，对兴趣表达，但仍然可判定的理论，其推理能力太 低。通过引入描述逻辑这一谓词逻辑的子集，可以使得基于描述逻辑的推理 1 2 机理论上可以在有限步内产生结果，即推理必然是可以终止而得到结果。对 于这一点，在推理部分我们将详细论述。 最后来看一个例子，它说明怎样用描述逻辑来表示知识，描述家庭领域 中的一些概念如果p e r s o n 是一个原子概念表示人个体集，m a l e 是一个原子 概念表示男性个体集，h a s c h i i d 是一个原子关系表示有孩子，那么可以用描 述逻辑提供的构造器来构造不同的概念否定( 记为一) 表示概念的补，如 1 妇l e 表示女性个体集；概念交( 记为c d ) 表示既属于概念c 又属于概念d 的个体实例集，如p e r s o n 州a l e 表示男人；概念并( 记为c v d ) 表示属于概念 c 或者属于概念d 的个体实例集，如m a l e v i i a l e 表示男性或者女性个体实 例集；全局约束( 记为v r c ) 表示与一些个体实例( 要求这些个体实例都属于 概念c ) 有关系r 的个体实例组成的个体实例集，如v h a s c h i l d 地l e 表示他 们的孩子都是男性的个体实例集：存在约束( 记为j r c ) 表示与属于概念c 的个体实例有关系r 的个体实例组成的个体实例集，如孙a s c h i l d m a l e 表示 有孩子是男性的个体实例集。 2 2 基本描述逻辑a l c 描述逻辑建立在概念( c o n c e p t ) 和关系( r o l e ) 的基础上，概念指的就是对 象集，关系就是指对象之间的二元关系。一个描述逻辑系统包括四个基本的 组成部分：表示概念和关系的构造集，t b o x 断言集，a b o x 断言集，t b o x 和 a b o x 上的推理机制。 1 表示概念和关系( r 0 1 e ) 的构造集： 概念解释为一个领域的子集关系( r 0 1 e s ) 一属性( 二元谓词，关系) 2 t b o x ：关于概念术语的断言是描述领域结构的公理的集合 定义：引入概念的名称包含：声明包含关系的公理 3 a b o x ：关于个体的断言是描述具体情形的公理的集合 概念断言表示一个对象是否属于某个概念 关系断言一表示两个对象是否满足一定的关系 4 t b o x 和a b o x 上的推理机制。 如上文所述，描述逻辑描述形成了层次知识：概念( c o n c e p t ) 和关系 ( r 0 1 e ) 名。关系表示二元描述，如h a s c h i l d ( x ，y ) 。概念表示一元描述，如 p a r e n t ( x ) ：p e r s o n ( x ) 用y ( h a s c h i l d ( x ，y ) p e r s o n ( y ) ) 。描述逻辑具有 固定的表示符号，像构造符。由原始概念和角色用构造符集可以建立复杂的 概念和角色，从而实现知识的表示和推理最基本描述逻辑 a l c ( a t t r i b u t i v ec o n c e p td e s c r i p t i o nl a n g u a g ew i t hc 唧l e 啪n t s ) 只提 供了否定、概念交、概念并、全局约束、存在约束构造器，具有一定的表达 能力和推理能力。这里我们详细论述a l c 的目的是：1 通过对最小化的描述 逻辑获得对描述逻辑的整体认识。2 a l c 也是我们下一步构造推理算法的基 础。 2 2 1 基本描述逻辑 l c ( a t t r b u t i v ec o n c e p td e s c r i p t i o nl a n g u a 聃w i t h c o 忡ie 鹏n t s ) 的语法与语义 一般地，描述逻辑依据提供的构造器，在简单的概念和关系上构造出复 杂的概念和关系通常描述逻辑至少包含以下构造器：交，并，非，存在量词 和全称量词。这种最基本的描述逻辑称之为a l c s c h i n i d t ，1 9 9 1 。在a l c 的基础上再添加不同的构造器，则构成不同表达能力的描述逻辑，我们将再 下文描述。a l c 的语法和语义如图2 2 ： 构造算 诱法语义 铸予 予 原子概 且4 ，7h u m a n 念 腰子关 只硭曼厶f x 厶i h a 8 - c h d 系 对概念c ，嘞关系i m k l r 合取d 伊nd rh u m a n 几m a i e 析取d 伊ud r d 0 c t o ru i 卸吖e r 非 1 c e1 m a i e 存在量 j 兄e ( r ij ， r v 了n a s - 词 c q c h d m a i e 全称量 v 兄c ( 叫v ， 彤= 廿 vh a s - 词研 c h i i dd 0 c t 吖 图2 2a l c 的语法语义 下面是对表中的有些概念进行说明： ( 1 ) 合取解释为个体集合的交。 ( 2 ) 析取解释为个体集合的并。 ( 3 ) 否定解释为个体集合的补。 ( 4 ) j r t 等价j r 。 ( 5 ) - 1 ( c v d ) 等价- 1 c v - 1 d 。 ( 6 ) - 1 ( c d ) 等价_ 1 c ，d 。 ( 7 ) ，( v r c ) 等价j r ，c 。 ( 8 ) ，( j r c ) 等价v r ，c 。 一个解释i 由一个非空集合( 域) 和一个函数i ( 一个解释函数) 组 成其中，函数i 能把每个概念映射到1 ，的一个子集，每个关系映射到 1 x 1 的一个子集，每个个体映射到的一个元素。 1 4 2 2 2 基本描述逻辑 l c 的知识库 基本描述逻辑a l c 的知识库其构成 e n r i c of r a n c o n i ) 如图2 3 所示； 图2 3 基本描述逻辑a l c 的知识库构成 其中，t b o x 表示术语断言集合，它描述语义，例如： p a r e n t ( x ) = p e r s o n ( x ) j y ( l a s c h i l d ( x ，y ) p e r s o n ( y ) ) 。a b o x 表示实例 断言集合，它描述成员关系，有成员函数：c ( a ) ，r ( a ，b ) ，例如： m a l e ( j o h n ) ，h a s c h i l d ( j o h n ，t 伽) 。 ( 1 ) t b o x 用来描述语义，不同的语义要用不的t b o x 来表达，主要依赖 于断言是否允许被循环。如下是从古典逻辑的角度来说明t b o x 表示的语义， i fc 属于d ，则一个解释i 满足断言c 1 属于d 1 ； i fc = d ，则一个解释i 满足断言c i - d 1 ； 一个解释i 是一个t b o xt 的模型要求i 满足t 中的所有断言。 ( 2 ) a b o x ：如果i = ( 1 ，i ) 是一个解释，且， 如果留a 1 属于c 1 ，则c ( a ) 的在解释i 下被满足； 如果( a 1 ，b 1 ) er ，则r ( a ，b ) 在解释i 下被满足； 则断言的一个集合a 叫做a b o x 。 ( 3 ) 几个概念的说明。 如果a 中的每个断言在解释i 下被满足，则解释i 被称为a b o xa 的一 个模型：如果一个a b o xa 有一个模型，则说a b o xa 是满足的。 一个解释i = ( 1 ，i ) 是一个知识库i 的模型，如果知识库e 中的每个 断言被i 满足；一个知识库e 被满足如果知识有一个模型。 2 3 描述逻辑中的推理 a l c 中的推理服务 h o r r o c k se ta l ，1 9 9 9 ( g i u n c h i 9 1 i aa n d s e b a s t i a n i ，1 9 9 6 包括：概念可满足性( c o n c 印ts a t i s f i a b i l i t y ) ，包含关 系( s u b s u m p t i o n ) ，可满足性( s a t i s f i a b i l t y ) ，实例检测( i n s t a n c e c h e c k i n g ) f r a n zb a a d e r ，2 0 0 3 。下面分别对它们进行说明： ( 1 ) 一致性( 协调性c o n s i s t e n c y ) 即检测是否有t 的模型i 使得c 空集。 即检测是否有知识库 的模型( 解释) i 。 ( 2 ) 可满足性( s a t i s f i a b i l i t y ) 对一个概念c ，如果存在一个解释i 使得c 在i 下的解释是非空的，则 概念c 是可满足的，否则是不可满足的。 1 5 定理：概念c 是可满足盼，当且仅当c 不包含于空集。 ( 3 ) 包含检测( s u b s u m p t i o n ) 在t b o x 中检测：c 是否属于d 。 即检测c 在i 下解释属于d 在i 下解释是否在t b o x 的所有解释成立。 ( 4 ) 实例检测( i n s t a n c ec h e c k i n g ) 概念的实例：s t u d e n t ( j o h n ) ，或者表示为j o h n ：s t u d e n t ，即j o h n 是 否为s t u d e n t 的一个实例。 关系的实例：f a t h e r ( j o h n ，m a r y ) ，即检测j o h u 与m a r y 关系是否为 f a t h e r 关系的实例。 2 3 1 可满足性问题 t a b l e a u 演算是一种一阶逻辑的公式可满足性证明方法 张健，2 0 0 0 。 描述逻辑的t a b l e a u 算法最早由s ch l i d t s c h a ub 和s m o l k a 为检验a l c 概念 的可满足性而提出的( f r a n z b a a d e r ，2 0 0 1 。 检验一个概念的可满足性，实际就是看是否有解释使得这个概念成立 例如：概念m a l e f e 嘞1 e ，即需要检测是否有性别既是男的又是女的这样的人 若确实没有两性人，刚我们断言，这个概念是不可满足的。 设c 是一个概念，那么下面几条是相等的：( 1 ) c 是不可满足的；( 2 ) c 包含于b 0 r r t o m ( 空集) ；( 3 ) c 和b c r r t o m 是相等；( 4 ) c 和t o p ( 全集) 不相 交。 证明：由c 是不可满足的可得，任意解释i 使得c 1 = 空，而由c l - 空可 得c 1 属于空，也就是c 属于b c r r t o m1 这可得到c 包含于b 0 r r t o m ；再由c l - 空可得c 1 没有任何元素的，于是c 1 = b 0 r r t o m 我们可得到c 和b 0 r r t 伽相等； 最后由c i - 空可得是c 没有任何元素的，于是c 1 t o p i 空，这说明c 和t 不 相交同理，可分别由( 2 ) ，( 3 ) ，( 4 ) 均可推出其他三式。a l c 的t a b l e a u 算 法是通过构造表达式d 的解释模型来证明d 的可满足性称这个构造的解释模 型为一棵完整树该完整树是一棵树，完整树的结点标注是一组a l c 概念集合， 边的标注是某个关系为了简化构造，我们把所有概念都转化为否定范式，即 否定只出现在概念前面通过d e m 0 r g a n 法则。这种转化是容易实现的，具体 如下所示： 栅d ) | c u d t ( c u d 川n h d ，、，r c 舅习r ，1 c - a r c i v r 1 c _ 1 墨n rc 尊电+ 1 r c 童咄c i 铲u c 1 6 2 3 2t a b l e a u 算法 t a b l e a u 算法是解决可满足性问题的一个决策过程 r e i n e r h a h n l e ，2 0 0 1 。如果一个公式是可满足的，那么此过程将构造性的显示该公 式的一个模型。该算法的基本思路：通过公式来逐渐构建模型，通过自项向 下的方式来分解公式。此过程一直持续直到找完所有可能的公式，找完所有 可能公式的目的是为了证明没有找到不可满足公式的模型。 下面以与规则和存在规则为例说明t a b l e 叫算法中的扩展规则； ( 1 ) 与规则： 规则 如果在一个给定的解释i 中包含一个元素a ，可以得到a 属于( c d ) ， 那么从语义的角度来讲元素a 应该在c 1 和d l 的交集中，也就是元素a 应该既 在c 中也在d 1 中。因为该规则对任何解释都必须正确，所以从解释和它们的 元素可以得出在一般解释中可得到一个在概念c d 的解释中的一般元素 x ( 记为x ：( c d ) ) ，那么元素既属于c 的解释又属于d 的解释。假设现在要构 造一个继承解释s ，该解释使与概念c d 相当的集合至少包含一个元素。我 们可以把这最初的要求说成约束x ：( c d ) 。从语义来说，可以知道s 必须 是约束x ：c 和x ：d 共有的。所以能添加这些新约束到s 中，还可以知道 如果s 满足这些约束那么s 也将满足首先的约束。通过以上的考虑可以得到 下而的扩展规则：s 一 x ：c ，x ：d v si f1 x ：c d 在s 中，2 x ：c 和 x ：d 都不在s 中 ( 2 ) 存在规则刍规则 如果在一个给定的解释i 中包含一个元素a ，可以得到a 属于( j r c ) 气那么从语义的角度来讲必须存在一个元素b ( 不必与a 有区别) 使得( a ，b ) 属于r i 和b 属于c 1 成立。因为该规则对任何解释都必须正确，所以从解释和 它们的元素可以得出在一般解释中可得到一个在概念3 r c 的解释中的一般 元素x ( 记为x ：| r c ) ，那么必须存在一般元素y 使得x 和y 在关系r 中( 记 为x r y ) 和y 属于c 的解释( 记为，y ：c ) 通过以上的考虑可以得到下面的传 递规则：s 一 了 x r y ，y ：c ) v si f1 x ：| r c 在s 中，2 y 是一个新变量， 3 在s 中不存在z 使得x r z 和z ：c 成立其他的规则我们不再具体说明。下 面给出了a l c 中的完全规则： 1 ) 几规则：s n x ：c 1 ，x ：c 2 u s ，若x ：c ”c 2 在s 中，且x ：c 1 和x ：c 2 不在s 中同时出现。 1 7 2 ) u 规则：s u x ：d u s ，若x ：c l u c 2 在s 中，x ：c 1 和x ：c 2 都不 在s 中，且d ：c 1 或者d = c 2 。 3 ) j 规则：s j x p l y ，x p k y ，y ：c ) u s ，若x ：j r c 在s 中，r = p 1 几n p k ，没有z 使得x r z 在s 中成立，且z ：c 在s 中，y 为一个新变量。 4 ) v 规则：s v y ：c u s ，若x ：j r c 在s 中，x r y 在s 中成立， 且y ：c 不在s 中。 2 3 3 其他问题向可满足性的转化 除了检测概念可满足性外，概念包含、概念相等、概念不相交，对这些 问题的检测也是很重要，这些问题的检测可以转化为概念的可满足性检测， 下面我们说明了这一点对于概念c 和概念d ， ( 1 ) c 包含于d 当且仅当c 一d 是不可满足的。 ( 2 ) c 和d 相等当且仅当c 1 d 和d - 1 c 都是不可满足的。 ( 3 ) c 和d 不相交当且仅当c d 是不可满足的。我们来证明这几点。 ( 1 ) = 让c 包含于d ，假设c 1 d 是可满足的由c ，d 是可满足的可得， 存在一个解释i 使得( c _ 1 d ) 1 = 空集这说明在1 中至少存在一个元素a 使 得a 属于c 1 且a 不属于d 1 ，即存在元素属于c 但不属于d ，这与己知c 包含 于d 相矛盾。 让c 和d 相等，假设c - 1 d 和d _ 1 c 是可满足的。那么由c - 1 d 和d - 1 c 是可满足的可得，存在一个解释i 使得( c 1 d ) 1 和( d 一c ) 1 都不为 空，下面对两种情况进行讨论，当( c ，d ) 1 不为空时，于是1 中至少存在一 个元素a 使得a 属于c 1 且a 不属于d 1 。而由c 和d 相等可得，任意解释i 使得c i ：d 1 ，这说明在1 中对于任意元素a 如果a 属于c 1 那么必须a 属于d 1 ， 和如果a 属于d 1 那么必须a 属于c 1 ，这与1 中至少存在一个元素a 使得a 属于c 且a 不属于d 1 相矛盾；当( d - 1 c ) 不为空时，于是1 中至少存在一 个元素a 使得a 属于d 1 且a 不属于c 1 而假设中c 和d 相等可得，任意解释i 使得c l - d 1 ，这说明在1 中对于任意元素a 如果a 属于c 那么必须a 属于d i ， 和如果a 属于d 1 那么必须a 属于c 1 ，这与1 中至少存在一个元素a 使得a 属于d i 且a 不属于c 相矛盾。 让c 和d 不相交，假设c d 是可满足的由c d 是可满足可得，存 在解释i 使得( c d ) 1 不为空，这与已知c 和d 不相交相矛盾； = 让c d 是不可满足的假设c 和d 相交，由c 和d 相交可得，存在解释i 使得c 1 d 1 不为空；而由c d 是不可满足的可得，任意解释i 使得c 1 d 1 为 空，这与c 1 d 1 不为空矛盾。证毕。 由上阐述，我们可以知道：其他问题的解决可以转化为可满足性问题加 以解决。 2 3 4 算法的特点和例子 t a b l e a u 一算法具有可终止性、可靠性和完全性。 1 对每个a l c 概念d 来说，t a b l e a u 算法是可终止的一个系统如果没 有扩展规则运用到它里面，它是完全的。从一个系统s 导出的完全系统也叫 s 的完全性。当存在规则运用的非无限链时，就可以得到完全性。 2 如果一个概念d 有一个t a b l e a u ，那么恰当应用t a b l e a u 规则，则可产 生概念d 的一棵完全的、无冲突的完整树如果s 是完全的并且s 没有包含 冲突，那么总能构造一个基于s 的c 的解释，目的是让c 1 非空。 3 ( 可靠性) 如果对一个a l c 概念d 应用t a b l e 叫规则得到一棵完全的、 无冲突的完整树，那么概念可满足。算法没有加入非必要的矛盾。换句话说， 1 9 判定规则总是保持系统的可满足性，非判定性规则总有一个保持可满足性运 用的选择。 给出一个实例，如图2 - 4 ： k 8 = m a n u n m a n c l 每，m a n t 如k 8 = c 鲰譬鼬嗫 醚a n c l 肆，1 酗锄谯虮 l 矗妇疗枷 材翩c 桫 i ，赫解勰添 士 le 铅烈8 腻翩a 妒 l ，知渤t 。舸 图2 4 实例1 运用交规则，第一个k b ( 知识库) 出现了冲突，第二个l ( b 是可满足的。 另一个实例如图2 5 ： 艚= 僦鲫v 越新踟，1 a 撼鼬曩叫w 矗n 踟 图2 5 实例2 图2 5 中，运用并规则，第一个l ( b 出现了冲突，第二个k b 是可满足的。 由上面的例子可以看出算法的步骤就是以知识库作为树根，不断运用规则， 构造出子节点，直到出现冲突，或没有规则可以再运用，而证明是可满足的。 2 4 描述逻辑的扩展 基本描述逻辑a l c ( a t t r i b u t i v ec o n c e p td e s c r i p t i o n1 a n g u a g ew i t h c o m p l e m e n t s ) 只提供了否定、概念交、概念并、全局约束、存在约束构造器， 它有一定的表达能力和推理能力。但在a l c 中要表达如至少有两个男孩的人， 至多只有三