描述逻辑第二章csdn

1第二章描述逻辑基础概述本章简单介绍了表示、推理知识的形式语言：描述逻辑。首先，给出了DL基本概念的简短综述；然后，介绍了句法和语义，包括应用在系统中或在文献中提到的基本结构，以及这些结构被用来建造知识库的方法；最后，定义了典型的推理问题，展现了它们是如何相互联系的，并且描述了解决这些问题的不同方法。在本章中只简单提到的一些主题在接下来的章节中会有更为详细地介绍。2.1简介在前一章中已经概略提到，DLs是知识表示体系族的最近才使用的名字，首先，通过定义该领域内的相关概念（terminology），表示一个应用领域（the”world”）的知识；然后，使用这些概念指明出现在该领域（theworlddescription）内的对象和个体的性质。正如DL的名字所显示的，这些语言的特点之一在于，不像他们的前辈一样，他们装备了一个形式的、基于逻辑的语义。另外一个显著的特点在于以推理为中心服务作为重点：推理允许我们从知识库中的外层知识得到蕴含在其内部的知识。DL支持出现在很多智能信息处理系统的应用中的推理模式，它也是人们用来构建和理解世界的：概念和个体的分类。概念的分类确定了给定的术语（terminology）中概念间的子概念/父概念的关系（在DL中称为包含），而且分类允许我们以包含层级的形式去构造术语。这种层级为不同概念间的联系提供了有用的信息，而且能被用来提高其他推理服务。个体的分类确定了一个给定的个体是否总是一个概念的实例（也就是说，这种实例关系是否由个体的描述和概念的定义来暗示），这样就提供了个体性质的有用信息，更为有用的是，实例关系可以触发那些想知识库中插入附加事实的规则的应用。因为DL是知识表示的一种形式，而且在知识表示中，我们通常假设一个知识表示系统总能在一个合理的时间内回答用户的查询，所以，DL研究者所感兴趣的这个推理过程，即决策过程，不管肯定或否定回答，总之是要结束的，这一点与一阶理论证明是不同的。答案在有限时间内给出，并不意味着这个有限时间是合理的，所以，调查一个包含决策推理问题的DL的计算复杂度是很重要的。推理问题的确定度和复杂度依赖于正在使用的DL的表达能力，一方面，表达能力很强的DLs可能会使得推理问题很复杂，或者根本没法确定；另一方面，表达能力很弱的DLs（包含有效的推理过程）可能无法准确表示给定应用中的重要概念。正如前一章中提到的，调查DLs的表达能力和他们的推理问题的复杂性的折衷，已经是DL研究的最重要的主题之一。DL是由所谓的“结构化层级网络”（Brachman,1977b;1978）发展而来的，结构化层级网络是为了克服早期语义网络和框架的歧义性提出的，语义网络和框架最早是在KL-ONE系统中实现的（BrachmanandSchmolze,1985）。下面这三点，首先在Brachman的有关结构化层级网络的著作中被提出，在很大程度上影响了DLs的接下来的发展：基本的依照造句法构建的模块有原子概念（一元谓词）、一元角色（二元谓词）和个体（常量）。因为它使用了一个相当小的构建复杂概念和角色的构造器（知识完备的）集合，语言的表达能力被束缚了。在推理过程的帮助下，概念和个体的内部知识能够被自动地推理。特别地，概念间的包含关系以及个体和概念间的实例关系起到了重要的作用。这与语义网络中的由用户明显给出的IS_A关系是不一样的，包含关系和实例关系是由概念的定义以及个体的性质推出的。在第一个基于逻辑的语义学应用于KL-One-like知识表示语言之后，像包含这样的推理问题也能够有一个准确的意义，这导致了此类语言的计算特性的第一次正式调查。结果证明，早期DL系统使用的语言的表达能力太强，这使得包含问题无法确定。第一个最坏情况复杂度调查结果显示，即便对于表达能力很差的语言，包含问题也是难于处理的（也就是说，不是多项式级可以解决的），正如前一章中提到的，这本书是KL-One-like知识表示语言中的推理的最坏情况复杂度的彻底调查的开始（详情见第三章）。但是，后来的研究表明，推理的难处理性（最坏情况下复杂度是非多项式级的）并没有妨碍DL在应用中的有用性，在实现一个基于DL的系统时，只要使用那些复杂的最优化技术，就可以了2（见第九章）。可是，实现一个基于DL的系统时，基本的推理算法的有效实现并不是唯一的问题。一方面，起源系统服务（比如说分类，也就是说，构建一个terminology中定义的所有概念间的包含层级）也必须被最优化；另一方面，一个DL系统还需要一个好的使用者和好的应用程序接口（详情见第七章）。大多数实现的DL系统提供了一种规则语言，规则语言可以被看作一种非常简单的，但是有效的应用编程机制（详情见2.2.5）。2.2节介绍了DL的基本形式。经由一个原型的例子，首先介绍了描述概念的形式（也就是描述语言），然后，定义了Tbox和Abox的形式。接下来，介绍了基本的推理问题，并展示了它们是如何相互联系的。最后，定义了许多实现的DL系统中可用的规则语言。2.3节描述了DLs中解决基本的推理问题的算法，在简短地概述了结构化包含算法之后，重点解释了tableau-based算法，最后，评论了基于terminology的推理问题。最后，2.4节描述了一些附加的语言构造器，也就是那些虽然没有被包括在2.2节中介绍的描述语言的原型族系中，但是在文献中被考虑到了，以及在某些DL系统中是可用的。2.2基本形式的定义基于DL的知识表示系统提供了建立知识库、推理知识库中的内容以及处理这些内容的工具，图2.1概略地描绘出了这样一个系统的结构（关于DL系统的更多信息见第八章）。一个知识库（KB）包含了两部分：TBox和ABox。Tbox介绍术语，也就是一个应用领域的词汇表，而Abox中则包含了根据这个词汇表的命名个体的声明。这个词汇表包含了表示个体的集合的概念（concept），以及表示个体之间二元关系的角色（roles），除了原子概念和角色（概念和角色名）之外，所有的DL系统都允许它们的使用者构建复杂的概念和角色描述。Tbox可以被用来将名字分配给复杂的描述，用来构建描述的语言是每个DL系统的特性，而且不同的系统是通过它们的描述语言区分开来的，描述语言有一个model-theoretic语义，这样，TBox和Abox中的陈述就可以用一阶逻辑的公式来区分，或者在有些时候，使用这个公式（it指代什么）的简单扩展。一个DL系统不仅要存储terminologies和assertions，而且还要提供terminologies和assertions的推理服务。terminology的典型的推理任务，是要确定一个描述是否是可以满足的（也就是说是没有矛盾的），或者一个描述是否比另外一个更加概括，即第一个是否包含第二个。ABox的重要问题是要弄清楚它的陈述（assertions）集合是否是一致的，也就是说，它是否有一个模型，而且Abox中的陈述是不是使得一个特定的个体是一个给定概念描述的实例。描述的可满足性检查和陈述集合的一致性检查，在确定一个知识库是否有意义时，是很重要的。通过包含性测试，我们可以根据terminology中的概念的一般性，把这些概念组织成一个层3级结构，一个概念描述也可以被认为是一个我们感兴趣的对象集合的查询，这样，通过实例测试，我们就可以取回满足查询的个体了。在任何一个应用中，一个知识表示系统都是被嵌入到一个更大的环境中的，该环境中的其他组件通过查询和修改知识库来与知识表示组件相联系，也就是通过增加和取消概念、角色以及陈述达到的。规则（rules）就是增加陈述的束缚机制，是逻辑的核心形式的扩展，它仍然是被逻辑地解释的。但是，包括提供应用程序接口的很多系统，都有定义好的逻辑语义的功能，通过提供一个escapehatch，应用程序就可以任意地操作知识库了。2.2.1描述语言基本的描述有原子概念和原子角色，通过使用概念构造器，复杂的描述可以在基本描述的基础上归纳性地构建，在抽象符号中，我们使用字母A、B代表原子概念，使用字母R代表原子角色，使用C、D代表概念描述，描述语言因为它们本身提供的构造器的不同而不同，下面，我们将讨论AL语言族中各种各样的语言，AL语言（定语语言），作为有实用价值的最小的语言，在[Schmidt-SchauBandSmolka,1991]中被介绍过。该族系中的其他语言都是AL语言的扩展。2.2.1.1AL语言的基本描述AL语言中的概念描述根据下面的语法规则构成：C，D→A∣（原子概念）∣（全局概念）∣（底层概念）A∣（原子否定形式）C∩D∣（交集）CR.∣（值束缚）.R（有限制的存在变量）需要注意的是，在AL语言中，否定只能被应用于原子概念，而且，在某角色的存在变量的范围内，只允许全局变量使用。因为历史的原因，AL语言的子语言中，不允许否定应用于原子概念的被称为FL-,FL-的子语言中，不允许使用由限制的存在变量的，叫FL0。为了给AL语言中描述的概念一个形象的例子，我们假设Person和Female是原子概念，那么，Person∩Female和Person∩Female就是AL语言中描述的概念，很直观的，有一些人是女人，而有些人不是女人。另外，如果我们假设hasChild是一个原子角色，我们可以使用概念.PersonhasChild和FemalehasChild.Person表示那些有一个孩子的人，以及那些所有的孩子都是女孩的人。使用底层概念，我们也可以用.PersonhasChild描述那些没有孩子的人。为了定义AL语言中概念的形式语义，我们使用解释I，I包含一个非空集合I（解释的领域），以及一个解释功能，解释功能分配给每一个原子概念A一个集合IIA，分配给每一个角色R一个二元关系IIIR。通过下面的诱导定义，解释功能被扩展为概念描述。IITIIIIAA\)(4IIIDCDC)(}),.(|{).(IIIICbRbabaCR}),.(|{).(IIIRbabaTR如果对于所有的解释I都有IIDC，那么，我们说这两个概念C、D是等价的，写做DC，例如，回到概念语义的定义，我们可以很容易地证明StudenthasChildFemalehasChild..和).(StudentFemalehasChild是等价的。2.2.1.2AL语言族系如果我们给AL语言另外添加构造器，就可以获得表达能力更强的语言，概念的合并（用字母U表示）写做DC，并且解释为IIIDCDC)(。完全的存在变量（用字母ε表示）写做CR.，解释为}),.(|{).(IIIICbRbabaCR，需要注意的是，CR.允许任何概念出现在存在变量的范围内，这一点是和TR.不同的。数量限制（用字母N表示）写做nR（至少的限制）nR（最多的限制），此处的n是非负的整数，它们可以被分别解释为nRbabanRIII}),({{)(和nRbabanRIII}),({{)(，这里的“|.|”表示集合的势。从语义的观点来看，数量限制中的数字译码是非实质的？？，但是，对于推理的复杂度分析来说，n是由二进制（或十进制）表示，还是由字符串表示，是有关系的，因为二进制（十进制）表示更为简洁、紧凑。任何概念的否定（用字母C表示，complement）写做C，解释为IIICC\)(。举个例子，使用这些附加的构造器，我们可以描述那些或者最多有一个孩子，或者至少有三个孩子，并且其中一个是女孩的人：)).3(1(FemalehasChildhasChildhasChildPerson。通过以上提到的构造器的任意子集，扩展AL语言，可以生成一个特殊的AL语言,我们用字符串的形式给命名AL[U][ε][N][C],名字中的字母代表相应的构造器的存在。例如，AlεN是AL语言的扩展，其中包含了完全的存在变量和数量限制（要了解如何扩展命名方案，以得到表达能力更强的DLs，参见关于DLterminology的