（计算机软件与理论专业论文）基于描述逻辑的时态扩充研究及应用.pdf

中山大学硕士学位论文基于蕊逻辑的时态扩充研究及应用 基于描述逻辑的时态扩充研究及应用 专业：计算机软件与理论 硕士生：王浩 导师：汤庸教授 摘要 近年来，描述逻辑由于其强大的表达能力和良好的计算性质，在知识工程领 域受到广泛关注。但是，描述逻辑适用于表达静态信息，难以表示在许多领域都 有应用前景的时态信息。因此，我们有必要对描述逻辑进行时态扩充。而使用具 体领域( c o n c l c t cd o m a i n ) 方法可使得我们方便地处理时态信息，因此我们设计 了时间具体领域，扩充到描述逻辑语言a l c 中，从而提出新语言a l c ( t ) 。 本文中，我们首先介绍了a l c ( t ) 的语法和语义解释，然后在此基础上介绍 了a l c ( t ) 可提供的推理服务，并提出时间具体领域的一致性检测算法和a l c ( t ) 概念的可满足性判定算法，并对其计算性质做出一定的分析。另外，我们对描述 逻辑的d i g 通信接口做出相应的修改，并设计了简易a l c ( t ) 推理机以及d i g 客 户端，推理机内则实现了我们所提出的概念可满足性判定算法。最后，提出了今 后的研究方向。 通过算法的可靠性分析和最后的实例演示，我们可得出结论a l c ( t ) 同时具 备了a l c 的表达推理能力和一定的时态处理能力，基本达到了我们对描述逻辑 时态扩充的目的。同时，我们在本文中所提出的扩充方法同样适用于其它领域如 空间领域等，并且，时间具体领域的一致性算法也具有通用性，只要其它具体领 域符合本文中所提出的a d m i s s a b l e 条件，也可使用该算法检测具体领域的一致 性。因此，本文对于描述逻辑的其它领域的扩充也具有一定的指导意义。 关键字：描述逻辑，c o n c r e c ed o m a i n ，时态扩展，a l c ( t ) ，概念可满足性 中山大学硕士学位论文 基于描述逻辑的时态扩充研究及应用 r e s e a r c ha n da p p l i c a t i o no nt e m p o r a le x t e n s i o no fd l s p e c i a l t y ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ： w a n g h a n s l | p 盯、r i s o f ：p r o f e s s o rt a n gy o n g a b s t r a c t r e c e n t l y , d e s c r i p t i o nl o g i c s ( d i s ) h a v eb e e ng i v e ne x t e n s i v ea t t e n t i o ni n k n o w l e d g ee n g i n e e r i n gf i d do w i n gt o t h e i re x c e l l e n te x p r e s s i n ga n dc o m p u t i n g c a p a b i l i t i e s b u td is a r eh a r dt oe x p r e s st e m p o r a lk n o w l e d g ew h i c hi si m p o r t a n ti n m a n yf i e l d sw h i l et h e yc a ne x p r e s ss t a t i ck n o w l e d g ew e l l s oi t sn e c e s s a r yf o ru st o a d dt e m p o r a la b i l i t yt od i s b e c a u s ew ec a np r o c e s st e m p o r a li n f o r m a t i o nw e l lu s i n g c o n c r e t ed o m a i n ( c d ) ，w ed e s i g nt i m ec d , i n t e g r a t ei tw i t ha l cw h i c hi sad l l a n g u a g e , a n dt h e nf o r man 删d ll a n g u a g e - - - a l c ( t ) i nt h i sa r t i c l e , f i r s tw ei n t r o d u c et h es y n t a xa n ds e m a n t i ci n t e r p r e t a t i o n , t h e nt h e r e a s o n i n gs e r v i c e sa l en a r r a t e d b a s e do na b o v e , w ci n t r o d u e nt h ec o n s i s t e n td c t e c t i n g m g o f i t h ma n da l c ( t ) c o n c e p ts a t i s f i a b i l i t yd e t e r m i n i n ga l g o r i t h m , a n dt h e na n a l y z e i t sc o m p u t i n gp r o l m t y o t h c n v i s e , w em o d i f yt h ed i gi n t e r f a c eu s e df o rd is r e a s o n e r s , a n dd e s i g nas i m p l ea l c ( t ) 懒n f , ra n dad i gc l i e n t , w i t ht h ea l g o r i t h m s i n t r o d u c e da b o v ei m p l e m e n t e di nt h i sr e a s o n e r f i n a l l y , w es h o wt h ef u t u r er e s e a r c h 0 1t h i st o p i c a c c o r d i n g t ot h e a n a l y s i so fc o i t c c l n c s so fa l g o r i t h m sa n dt h ei n s t a n c e d e m o n s t r a t i o n , w ec a nc o n c l u d et h a ta l c ( t ) c a na l s op r o c e s st e m p o r a li n f o r m a t i o n w h i l eh a v i n gt h ea b i l i t yo fa l c ，a n dw eh a v ea c h i e v e dt h eg o a lo fe x t e n d i n gd l s w i t ht e m p o r a la b i l i t y m e a n w h i l e , t h ea p p r o a c ho fe x t e n s i o nc , a 1 1a l s ob eu s e dt o i n t e g r a t eo t h e rd o m a i n s ( s p a t i s ld o m a i n , e t c ) w i t hd is ，a n dt h ec o n s i s t e n td e t e c t i n g a l g o r i t h mc a l la l s ob eu s e d t os o l v et h ec o n s i s t e n tp r o b l e mo f c dw h i c hi sa d m i s s i b l e s o ，t h i sa r t i c l e nb eu s e df o rr e f e r e n c eb yt h er e l e v a n t 储瞄呦，t o o 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 k e y w o r d ：d e s c r i p t i o nl o g i c ，c o n c r e t ed o m a i n ，t e m p o r a le x t e n s i o n ，a l c ( t ) ，c o n c e p t s a t i s f i a b i l i t y i h 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 1 1问题背景 1 1 1 描述逻辑介绍 第1 章引言 知识表示方法在2 0 世纪7 0 年代得到发展，其中语义网络( s e m a n t i c n e t w o r k ) 和框架系统( f r a m es y s t e m s ) 等基于网络结构的系统具有较好的应用 前景，受到了广泛关注。但是语义网络和框架系统均缺乏精确的语义刻画，导致 了它们通用性较差，阻碍了其进一步发展。而一阶逻辑虽然可以胜任，但是后来 人们认识到语义网络和框架系统并不需要它的全部机制，而只需要其片断就足够 了，并且没有必要使用一阶逻辑的推理技术，而可以根据不同的片断使用其特定 的推理技术，从而具有更优的计算特性。于是，作为一阶逻辑片断的描述逻辑 ( d e s c r i p t i o nl o g i c s ) 开始发展起来 1 。 描述逻辑是一种基于对象的知识表示方法，同时提供了基于逻辑的精确语义 刻画。描述逻辑被认为是目前知识表示中最重要的形式化方法。它统一了框架系 统、语义网络、k l - o n e - l i k el a n g u a g e s 、面向对象表示( o b j e c t - o r i e n t e d r e p r e s e n t a t i o n s ) 、语义数据模型( s e m a n t i cd a t am o d e l s ) 等许多传统表示方 法的逻辑基础 2 。 描述逻辑历史上也叫作术语语言或概念语言。它具有两个基本元素，即概念 和关系。概念插述了一个具有共同属性的对象集合，可解释为对象集的一元谓词， 关系则可解释为对象之间的二元关系。d l s 将大量的构造算子作用到简单概念上， 从而可以建立更多复杂的概念。不同的描述逻辑具有不同的构造算子，从而具有 不同的计算特性。a l c 是基本的描述逻辑，它提供了求反、存在量词、全称量词、 中山大学硕士学位论文 基于描述逻辑的时态扩充研究及应用 交、并等算子，具有令人满意的表达能力，更高级的描述逻辑语言往往是在其基 础上通过扩充算子等方式来增强表达能力的。 作为一阶逻辑的子集，描述逻辑具有合适定义的语义，拥有较强的表达能 力。但与一阶逻辑不同的是，它将推理服务作为自身的中心服务，即从知识库中 显式包含的知识中推导出隐含表示的知识，并且为了满足用户对知识库系统的查 询等应用要求，格外重视推理算法的可判定性和计算复杂性。描述逻辑的良好计 算性质是其得到关注的主要原因 描述逻辑为其关键推理服务提供了可判定的、可靠的、完备的推理算法。其 主要的推理服务有检测概念的可满足性、概念的包含问题、一致性检测、实例检 测等。其中，概念包含等许多问题可转化为概念的可满足性检测，因此它是最基 本的问题。s c h m i d t s c h a ub 与s m o l k a 3 首次提出t a b l e a u 算法，用来解决概 念的可满足性问题。之后，这种算法经常被扩展用来得到正确完备的算法，用以 解决其它描述逻辑的可满足性问题。早期使用t a b l e a u 算法的系统证明该算法的 可接受性能，而经优化后的系统如f a c t 、d l p 、r a c e 等所表现的性能则更令人满 意 4 5 。因此，这种算法具有很强的实用价值。 在众多知识表示的形式化方法中，描述逻辑由于有清晰的模型一理论机制， 很适合于通过概念分类学来表示应用领域，并且提供了很有用的推理服务，从而 在十多年来受到人们的特别关注。目前的主要应用领域包括：概念建模、软件工 程、规划、信息系统、自然语言处理、术语学、本体论等。 1 1 2 描述逻辑与语义网 近年，语义网的概念被提出，它指出了互联网的发展方向，得到了广泛重视 并得到迅速发展。其中，本体层是语义网的核心层，而作为本体层逻辑基础的描 述逻辑也因此在语义网中占有重要地位。下面我们将简介本体和语义网。 随着因特网的快速发展，如何组织、管理和维护海量信息并为用户提供有效 的服务成为一项重要而迫切的研究课题。为了适应这要求，o n t o l o g y 作为一种能 2 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 在语义和知识层次上描述信息系统的概念模型建模工具被提出，它有利于知识的 共享、互操作、重用，因此得到广泛应用，如知识工程、数字图书馆、软件复用、 信息检索和w e b 上异构信息的处理、语义w e b 等 6 。 o n t o l o g y 有许多不同的定义。其中最著名并被引用得最为广泛的定义是由 g r u b e r 提出的，“本体是概念模型的明确的规范说明” 7 。f e n s e l 对这个定义 进行分析后认为本体的概念包括四个主要方面 8 ： ( 1 ) 概念化( c o n c e p t u a l i z a t i o n ) ：客观世界中一些现象的概念抽象模型； ( 2 )明确( e x p l i c i t ) ：概念及它们之间联系都被精确定义； ( 3 )形式化( f o r m a l ) ：精确的数学描述，是计算机可读的； ( 4 ) 共享( s h a r e ) ：本体中反映的知识是其使用者共同认可的 w e b 经过多年发展已经成为一个巨大的全球化信息资源库。但是，计算机只 起个数据存储、传递、展示的作用，如果计算机能够理解内容的语义，那么计算 机就可以帮助人们做很多有意义的事情。w e b 的创始a b e r n e r s l e e 9 于2 0 0 0 年 在x m l 2 0 0 0 的会议上正式提出了语义w e b 。它的研究目的就是扩展当前的w e b ，使 得网络中所有的信息都具有语义。从长远看，这将会使语义w e b 成为一个全球化 的知识库，不仅仅满足人们的浏览信息的需求，更重要的是通过标准的语义规范 使得计算机可以理解和自动处理信息。语义网使得机器可以理解知识，同时就使 得机器有能力对知识进行推理，从而得到蕴含的新信息，这是传统的w e b 所无法 比拟的。而使机器理解语义的前提是对领域的概念体系有清晰的认识，语义w e b 是通过本体来做到的。 如图l - l 所示，语义w e b 的体系从底层到高层分别为：u n i c o d e 和u r i 、 x m l 、r d f 、o n t o l o g y 、l o g i c 、p r o o f t r u s t 。其中x m l 、r d f 、o n t o l o g y 是核心，它们用来表示w e b 信息的语义。本体描述语言提供了语义w e b 中的领 域信息之问共享的基础，是语义w e b 的核心。 语义w e b 中需要通过本体来描述领域中的资源，包括分类、属性、子类关系、 定义域和值域等。因此需要一些本体语言来描述这些信息，以便将其发布到w e b 上。目前的本体描述语言主要有r d f 、d a m l + o i l 、o w l 。2 0 0 2 年7 月，w 3 c 在提 交的d a m l + o i l 基础上发展了o w l ( w e bo n t o l o g yl a n g u a g e ) 语言，以使其成为 3 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 国际通用的标准本体描述语言 1 0 1 1 。 图1 - 1语义网的体系 o w l 语言由o w ll i t e 、o w ld l 和o w lf u l l 三种子语言组成，表达能力从弱 到强。其中，o w ld l 是最重要和应用最广泛的子语言。o w ld l 的逻辑基础是 s h o i n ( d ) 1 2 ，而o w l 的前身d a b l l + o i l 则是s h i q 的变式 1 3 。选择描述逻辑并 不偶然，因为描述逻辑有着其特有的优势 1 4 ： ( 1 ) 定义良好的语义和表达能力； ( 2 ) 基于逻辑的推理能力； ( 3 ) 保证计算复杂性和可判定性； ( 4 ) 效率良好的推理算法，如基于t a b l e a u 的算法； ( 5 ) 现有工具的有力支持，如f a c t + + 、r a c e r p r o 、p e l l e t 等。 这些特点使得描述逻辑优于其它逻辑形式，适于处理w e b 上的大规模数据。 语义w e b 本体语言的表达能力也直接依赖于相应描述逻辑的表达能力。在实际应 用中o w ld l 书写的本体被相应地映射为描述逻辑表示的知识库，然后借助描述 逻辑的推理服务实现对本体的推理。 1 2问题的提出 4 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 虽然描述逻辑提供了许多构造算子，但它们只能表达静态知识，而在许多实 际应用领域中，存在着许多动态知识则很难表达和推理。时态知识的表示和推理 是知识工程中一个重要分支，在许多应用领域都有其应用前景而在我们先前所 开发的法律知识库原型系统中同样有这方面的需求，如判断某法律目前是否生 效，以及判决书、案例、违法行为之间的时态关系等，都需要对相关的时间信息 表达和推理。 1 3 研究现状 为了表达时态信息，我们可以将“时问”作为一种特定领域，通过对时态的 相关概念建模建立起本体，在需要表达时态信息的时候使用该本体。目前已经有 d a i l l t i m e n 5 等本体被提出并应用于实践。但本体作为描述逻辑的高级应用， 在其基础上的时态表达必然会过于繁琐，并导致推理算法的低效。我们更倾向于 对逻辑层即描述逻辑本身进行时态扩展来增加时态表达和推理能力，对此国外已 有不少这方面的文献。 文献中对时间的表示有基于时刻( p o i n t - b a s e d ) 和基于区间( i n t e r v a l b a s e d ) 两种形式基于区间的描述逻辑通常以a l l e n 1 6 的1 3 种区间关系为基础， 具有强大的表达能力，但常导致推理算法的不可判定。基于时刻的描述逻辑的时 态表达能力虽然欠缺，但已可满足一般的应用要求，并且具有不错的计算性质。 文献中对描述逻辑的扩充大多是对联结词的扩充，可看作描述逻辑与时态逻 辑的结合，新语言的非时态部分描述知识的静态方面，时态部分则描述知识的动 态方面。s c h m i e d e i 1 7 首先提出将描述逻辑与基于区间的时态逻辑结合起来， 采用的描述逻辑是较早版本的f l z n r 一，添加的时态联结词是 a t ，s o m e t i m e ，a l l t i m e ；b e t t i n i 指出了该语言牺牲了描述逻辑的可判定性； a r t i c l e 和f r a n c o n i 将描述逻辑m f 与时态逻辑t l 结合，生成一个推理算法 可判定的新语言t l - a l c f 。以上的时间均是基于区间的。 另外s c h i l d 1 8 在描述逻辑a l c 的基础上添加了基于时刻的模态联结词， 形成了新语言a l c t 。扩充的联结词有将来某时( ) ，将来总是( 口) ，下一时 5 中山大学硕士学位论文 基于描述逻辑的时态扩充研究及应用 刻( 0 ) ，直到( u ) 。同时指出增加的联结词并未改变描述逻辑的良好计算性质。 上述所有的描述逻辑时态扩充通过添加额外的时间维度来描述行为或事件的时 态关系，并通过各自确定的时态运算实现时态知识推理。对于大规模的知识库尤 其是时间因素并非首要要素的场合，由于增加了额外的时间维度，其存储及推理 效率并不高，这种外部扩充的方式并不合适。 另外有人引入了具体领域( c o n c r e t ed o m a i n ) 对描述逻辑进行扩充。未引 入之前，描述逻辑中所有知识都在抽象的逻辑层次上表示，在整合特定领域中数 字、字符串等知识方面有所不足，例如定义一个概念“年轻人”，比较自然的方 式是引入角色a g e ，然后用c o n c r e t ed o m a i n 中的整数表示实际年龄值，这样可 以更准确得定义这个新概念，比起直接用抽象概念表示更为容易和自然。时态知 识与数值关系紧密，于是实践中，有人引入了c o n c r e t ed o m a i n ，结合d o m a i n 上提前定义的谓词来更好得定义时态相关概念。 b a a d e r 和h a n s c h k e 1 9 首先将具体领域整合进描述逻辑，形成a l c 的一个 扩展a l c ( d ) ，并且给出了具体领域的形式化描述及可接纳性质，还给出了最基 本的t a b l e a u 算法，但a l c ( d ) 只给出了f e a t u r e 的语法描述，并未区分具体特 性和抽象特性，而且未能确定明确的具体领域运算，因此缺乏实用性；l u t z 在 描述逻辑的具体领域扩充方面做了较多的工作，在文献 2 0 中将数字领域加入到 s h i o 描述逻辑中，其中包括一元和二元运算，通过构建h i n t i k k a - t r e e 来完成 逻辑推理任务，由于将抽象层次的逻辑推理与具体领域的校验结合在一起，算法 与经典的t a b l e a u 有较大区别，推理过程较为复杂；在文献 2 1 中针对特定的约 束系统给出了在g c i 下的t a b l e a u 算法，给出具体领域的w - s a t i s f i a b l e 性质， 限定谓词具备j p e d ( j o i n t l ye x h a u s t i v ea n dp a i r w i s ed i s j o i n t ) 的特性， 虽然可以适用于基于时间区间及a l l e n 区间关系的时态领域，但由于过多的限制 使其不适用于更一般性的时态知识表示及推理；在文献 2 2 2 3 中将实数具体领 域可满足性问题分别转化为线性方程问题和求环问题，但它们只适用实数领域， 不具有一般性；v o l k e rh a a r s l e v 等人【2 5 】 2 6 】提出了a l c f ( d ) ，并在推理机r a c e r 上实现，但其中的c d 处理能力受限，例如不允许f e a t u r ec h a i n s 等。 国内尚未发现对描述逻辑进行时态扩展的相关文献。 6 中山大学硕士学位论文 基于描述逻辑的时态扩充研究及应用 1 4 本文研究内容 在知识的表示和推理中，有两个层次的研究：一个是基础理论上基于逻辑形 式化的工作，即以一阶谓词逻辑为代表的各种逻辑体系；一个是基于这些逻辑理 论的本体论的研究，可看作具体的应用研究。本文的研究类型属于前者，主要内 容如下； 第1 章，介绍问题背景、应用需求以及研究现状。 第2 章，在描述逻辑a l c 的基础上，弓i 入时态具体领域，提出新的描述逻辑 语言a l c ( t ) ，并给出它的语法、语义解释。 第3 章，论述a l c ( t ) 可以提供的推理服务，并提出a l c ( t ) 概念的可满足性 判定算法，最后给出该算法的计算性质。 第4 章，对描述逻辑推理机的d i g 通信接口修改扩充，使其适合a l c ( t ) 的语 法特点。 第5 章，介绍我们所设计的a l c ( t ) 推理机以及客户端，它们利用上章提出的 d i g 接口通信。最后利用推理机和客户端进行概念可满足性判定算法的演示。 7 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 第2 章时态扩展后的描述逻辑a l c ( t ) 描述逻辑语言a l c 提供了基本的构造算予，我们可以用来表达许多复杂的概 念。我们在它的基础上加入了时间具体领域，形成新的语言a l c ( t ) ，它在不减 弱a l c 的强大表达能力的同时，还可以表示一些与时间相关的概念。本章，我们 将详细论述a l c ( t ) 的语法和语义，并简要阐述它与一阶逻辑的联系。 2 1 a l c ( t ) 的语法 2 1 1a l c ( t ) 的语法综述 我们将时间作为特定范畴并为之设计了具体领域，然后扩充到a l c 中，形 成具有一定时态信息处理能力的描述逻辑语言a l c ( t ) 。图2 - l 是a l c ( t ) 的语法 结构： t b o xa b o x p b o x l 公理 断言 l li 实例概念属性值角色谓词 图2 - 1 a l c ( t ) 的语法结构 8 中山大学硕士学位论文 基于描述逻辑的时态扩充研究及应用 其中，实例、概念、属性值、角色、谓词属于a l c ( t ) 的基础语法。实例代 表了现实世界中的各种对象；概念则是对于具有某一方面共同性质的实例的抽 象，与a l c 相比，a l c ( t ) 可以表达时态相关的概念；属性值则表示实例相关的 时间点；角色表示实例之间或实例与属性之间的二元关系；谓词则约束了属性值 之间的关系。在基础语法中，a l c f r ) 与a l c 相比的不同点是：属性值和谓词均 来自我们所扩充的时间具体领域，而概念和角色也相应的与a l c 有了诸多不同。 而在高级语法中，a l c f r ) 可看作由t i 如x 、a b o x 、p b o x 组成。t b 佩是领域 的术语规范，它不仅提供了原予概念和角色，并且利用多个构造算子，在原子概 念和角色的基础上构造定义更为复杂的概念，以定义公理的形式存储在t b o x 中； a b o x 中则提供了实例和属性值，并以概念断言、抽象角色断言、具体特性断言 的形式表达了实例的概念归属以及实例属性值相互之间的关系，以面向对象的形 式刻画了现实世界，并且，a b o x 中涉及到的概念和角色均来自t b o x ，这充分 体现了t b o x 作为领域概念规范的主要作用；p b o x 中则存储了谓词断言，表示 了时间点之间的谓词关系。在高级语法中，a l c ( t ) 相对于a l c 的特点是：增加 了p b o x ；1 1 如x 中增加了时态相关概念的构造算子；a b o x 中增加了具体特性断 言。 另外在扩充的同时，我们一直实践着模块化的思想，它有三层含义：一是具 体领域相对于原有的描述逻辑主体是一个单独的存储模块，与具体领域相关的元 素会集中存储在p b o x 中( 本章讲述) ；二是对描述逻辑原有的t a b l e a u 推理算法 做相应的扩充之外，我们另外设计了用于检测具体领域一致性的独立推理模块， 它与原有的推理算法协同推理a l c ( t ) 的概念可满足性问题( 第三章讲述) ；三是 由于我们所提出的具体领域一致性判定算法对某一类领域具有通用性，我们在实 践中可在推理机下同时挂接若干个具体领域模块，不同领域互相独立( 第五章讲 述) 。以上特点使得我们所提出的a l c ( t ) 在理论和实践上都具有可扩展性。 下面，我们将详细说明a l c ( t ) 的基础语法和高级语法。 2 1 2 a l c ( r ) 的基础语法 9 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 下面我们将形式化的定义相关概念。 f r a n zb a a d e r 和p h i l i p ph a n s c h k e 首先对描述逻辑与c o n c r e t ed o m a i n 的结合作 了尝试，在文献【1 6 】中，他们提出的具体领域的定义常被后来研究者引述，我们 也基本沿用该定义如下。 定义2 1 ( 具体领域) 一个具体领域( c o n c r e t e d o m a i n ) d 是一个二元组( a d ，九) 。其中，如是 某一应用领域的值域，即取值的集合；如是一组谓词的有限集合，每一个谓词 p 九都有一个元数n ，且p 被解释为全函数d ”一 t ，f ) 。 d 可以是自然数集合、有理数集合、字符串集合等，用来表示事物的某个 属性值，如年龄、长度、温度等；九中的谓词刻画了各种关于d 的有用关系， 正是通过这些谓词才使得我们可以通过具体领域更为细致的定义概念，同时，谓 词是检测具体领域一致性的主要考虑因素。 时间的表示有基于时刻( p o i n t b a s e d ) 和基于区间( i n t e r v a 卜b a s e d ) 两 种形式。基于区间的描述逻辑通常以a l l e n 的1 3 种区间关系为基础。时间区间 具有强大的表达能力，但是常常导致推理算法的不可判定。基于时刻的描述逻辑 的时态表达能力虽然不如区间表达方法丰富，但已可满足一般的应用要求，并且 具有不错的计算性质。而在文献 1 6 、 2 4 中，都通过将时间区间与时刻之间的 相互转化的方法使得基于区间的描述逻辑在推理算法上可判定。因此，在本论文 中，我们对描述逻辑扩充所设计的具体领域是基于时刻的。 以下我们将扩充到a l c 的时间具体领域t 给出定义。 定义2 2 ( 时间具体领域t ) 我们定义时间具体领域为r ( a ，c t ) ，其中， a r = r 办= ，乏= ， 如该定义所示，我们用实数表示时间点，并将两个实数之间的六个比较关系 1 0 作为时间具体领域的谓词集，它们可完全涵盖两个时间点的关系。 我们将角色足划分为两个互不相交的子集合、，且l 净乜。u 。 其中，表示抽象角色( a b s t r a c tr o l e ) ，属于该集合的角色表示实例之间的关 系，等价于描述逻辑扩充具体领域之前的角色；表示具体特性( c o n c r e t e 限定为单射的，即对任意的， 0 ，任意的实例口，厂国) 最多只有一个值。 我们将又划分为两个互不相交的集合m 。、玉，r r = m 。u 。 其中， 玉表示全局具体特性( g l o b a lc o n 口e t ef e a t u r e ) ，属于该结合的具体特性 示当前时间；川”表示普通具体特性( n o r m a l c o n c r e t e f e a t u r e ) ，是玉在如上 震k ： 为了定义引入c o n c r e t e d o m a i n 后的相关概念，我们需要引入路径( p a t h ) 的 定义2 4 ( 路径p a t h ) 我们定义路径( p a t h ) 为如下两种形式之一： 氖墨r r 厂，其中置，r ，咒虬。，栉0 ，啊。 中山大学硕士学位论文 基于描述逻辑的时志扩充研究及应用 b g ，其中g 玉 我们使用路径表达实例的属性。按第一种形式，我们可表达一个实例的具体 特性，也能表达出通过各种抽象角色所关联的实例的具体特性，例如定义一个路 径f a t h e r a g e ，我们可用它来表示某个实例的f a t h e r 的a g e ：第二种形式包含一 个全局具体特性，因为全局具体特性独立于各个实例，可看作任何实例的通用特 性，所以在这种定义形式中，没有抽象特性。 根据以上的定义，我们提出a l c ( t ) 的定义，以及给出它的概念构造语法。 定义2 5 ( a l c m ，a l c f d 的概念) 我们将时间具体领域扩充到a l c 中，形成新的描述逻辑语言a l c ( t ) 。 a l c ( t ) 的构造算子集合为 一，| ，v ，n u ) 。 我们递归定义a l c ( t 1 可以构造的概念如下： a 原始概念( a t o m i cc o n c e p t ) a 、全域概念( u i l i v e 侣a lc o n c e p t ) t 、底域 概念( b o t t o mc o n c e p t ) 上是概念，例如w o m a n ； b 如果c 是概念，- 1 c 是概念，例如- ，w o m a n ； c 如果嵋、u 2 是路径，p e 办，则j 嵋，屹p ，v ，屹p 都是概念，例如 了s t a r t t i m e d t i m e o d 如果c 是概念，r e 心，则了足c ，v r c 是概念，如3 h a s c h i l d p e r s o m e 如果c 、d 是概念，c n d ，c u d 都是概念，如p e r s o n nw o m a n 。 2 1 3a l c ( t ) 的高级语法 我们给出各公理断言、t b o x 、a b o x 、p b o x 的定义，它们也是基于描述逻辑 的知识系统的主要构成部分。 定义2 6 ( 定义公理，原子概念，原始概念，被定义的概念，a l c f r ) 的t b o x ) 定义公理( d e f i n i t i o na x i o m ) 是形如c ；d 的式子，其中c 是一个概念名， d 为a l c ( t ) 的概念，这样我们就可以为复杂概念引入一个新概念名称以简化书 1 2 写 如果一个集合由有限个定义公理组成，并且每一个概念至多被定义一次，即 每一个概念最多出现在定义公理的左侧一次，我们就将该集合成为t b o x 或 t e r m i n o l o g y 。 t b o x 中出现的每一个概念都是原子概念( a t o m i cc o n c e p t ) ，其中我们又可 以将其分为两类，我们把那些在定义公理左边出现过的概念称为被定义的概念 ( d e f i n e dc o n c e p t ) ，而剩下的即只出现在定义公理右边的概念称为原始概念 ( p r i m i t i v ec o n c e p t ) 。 定义2 7 ( 概念断言，抽象角色断言，具体特性断言，a l c ( t ) 的a b o x ) a l c ( t ) 的a b o x 由有限个概念断言( c o n c e p ta s s e r t i o n ) 、抽象角色断言 ( a b s t r a c tr o l ea s s e r t i o n ) 和具体特性断言( c o n c r e t ef e a t u r ea s s e r t i o n ) 组成，它们的形式分别为c ( a ) 、r ( a ，6 ) 和y ( a ，曲，其中r e 磁，e 弼。，口、 b 是实例，工是属性值。 c ( a ) 表示实例口属于概念c ，r ( b ，c ) 表示实例b 与实例c 之间存在关系r 。 ，瓴功表示实例a 的，属性值是j ； 如果a b o x 中存在断言r ( 6 ，c ) ，我们称实例c 是实例b 的r 后继。同理，如果 a b o x 中存在断言f ( a ，曲，我们称属性值j 是实例a 的，后继。 a b o x 的定义可用图2 - 3 示意： 图2 - 3 a b o x 的组成 定义2 8 ( 谓词断言、a l c f f ) 的p b o x ) 1 3 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 a l c ( t ) 的p b o x 由有限个谓词断言( p r e d i c a t ea s s e r t i o n ) 组成，它的形式是 p “) ，) ，其中，p 办，善、y 是属性值。 p ( x , y ) 表示属性值工与属性值y 具有谓词关系p 2 2 a l c ( t ) 的语义解释 2 2 1 时间具体领域的语义解释 定义2 9 ( 时间具体领域t 的语义解释) 我们给时间具体领域t 赋以特定的语义解释厶，给卉中的谓词符号赋以其数 学中常用的语义，如( ) ( 工，y ) = t r u e 当且仅当z 小于) ，善、y e r 。 2 2 2a l c 0 r ) 的语义解释 有了时间具体领域的定义，我们则可以在a l c 的语义解释的基础上扩充得到 a l c ( t ) 的语义如下： 定义2 1 0 ( a l c c d 的语义) a i 的一个解释j- - 四元组( a ，婶，s o ) ，其中，a ，为j 的论域，是实 例取值的集合；如是时间具体领域的论域；j o 由定义1 9 所定义，解释了具体 领域中谓词的语义；j 为解释函数，它有如下映射： a 将每一个概念c 映射为，的一个子集c 。； b 将每一个抽象角色r k 映射为a 。x 7 的一个子集r 。； 1 4 中山大学硕士学位论文 基于描述逻辑的时态扩充研究及应用 c 将每一个普通具体特性，e j 。映射为，的一个子集。； d 将每一个全局具体特性g e 7 玉映射为a ， ，其中黾r ； e 将每一个实例a 映射为岛的一个值 将每一个属性值x 映射为的一个值 j 对路径的解释如下： & “= 局足r 厂 ) = 0 ，善) ，x a rlj q ，a 2 ，a n ( ( 口，q ) 墨a ( a i ，a z ) 足 a a ( a i _ i a n ) r ( ，力d ) ， 其中墨，是，r 心，f e 川咿 b 甜= g m ) 。= a ，x 其中g 玉，而r j 对概念语义的构造如下： 对于原始概念爿，一。为的一个子集 对于全域概念t ，t 1 = ， 对于底域概念上，i t - _ o b ( 1 c ) 。= a ，、 c ( 3 u i ，“2 ) ) = 口a ，i 丑毛，而( 五a r a x z a r a ( a ，x d 蚝a ( a ，屯) 1 1 2 “，x z ) 一) ) ( v u l ，屹固= 扣，i ，屯( 毛c a r a x 2 a r a ( a ， ) 0 ，而) c u z 一( 一，屯) 一) ) d ( 3 r c ) 7 = 和a 1 3 b ( 6 a ，a ( a ，e r a b e c ) ) 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 ( v r c ) = 口e ，i v b ( 6 a ， ( 口，6 ) _ 6 c ) ) e ( c n d ) 。= 扣，i a c 4 d 。) ( c u d ) 7 = 口a ，i a c 7 v a e d 7 ) 定义2 1 1 ( 公理、断言的语义解释) 定义公理a ；d 当且仅当a ；d 概念断言c ) 当且仅当a c 。 抽象角色断言r ( a ，当且仅当( a t , b ) e r 具体特性断言f ( a ，曲当且仅当( d ，x t ) f 谓词断言p ( 工，j ，) 当且仅当( ，y l , t r u e ) p 山 定理2 1 2 ( 模型) 如果一个解释j 同时满足t b o x 的所有公理，我们称解释，满足t b o x ，或解 释j 是t b o x 的模型。 如果一个解释，同时满足a b o x 的所有概念公理、抽象角色断言以及具体特 性断言，我们称解释j 满足a b o x ，或解释，是a b o x 的模型。 如果一个解释，同时满足p b o x 的所有公理，我们称解释j 满足p b o x ，或解 释，是p b o x 的模型。 2 3 a l c f r ) 与一阶逻辑的关系 描述逻辑以面向对象的方式表示知识，但从语义上说，它是一阶逻辑的片断， 这使得它在保持良好的计算性质的同时，具备了强大的逻辑表达能力。下面，我 们将通过详细阐述a l c ( r ) 与一阶逻辑的等价形式，说明a l c 经过我们的时态扩 展之后，依然是一阶逻辑的片断。 1 6 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 从上节我们可知，模型，将每一个概念c 解释为，上的一元关系，每一个抽 象角色r 解释为，上的二元关系，每一个普通具体特性，和每一个全局具体特 性g 解释为a ，u a ，上的二元关系，所以，我们可以将每一个概念c 等价于一阶 逻辑中的一阶谓词，记为丸，每一个角色等价于一阶逻辑中的二元谓词，为简 洁起见，我们将谓词名等同于角色名。 同理，路径“亦可看作是，u r 上的二元关系，我们先给出在模型j 下路径 “与对应谓词的转化关系： a = 墨心民f ，墨，曼，焉心，m 。 o ) “力= i 厨t r 酝u e , 共3 q 它, a 2 置 q 群瓴- l ，吒) ，。心，瑚 4 ，q ，a n a i ，e a r b 甜= g ，g e ” 一( 4 ，x o ) = t r u e ， a e ，而为a ，中的特定值。 下面，我们给出在模h i 下概念c 与疙的转换关系； a c 是原始概念，则 丸) = t r u e , a 4 芒c c ，t t 是全域概念，则 丸和) = t r u e , aea ， 上是底域概念，则 孛i ( a ) = f a l s e , a e l b 丸c 1 ( 口) = ，龙0 ) ，a a 1 7 中山大学硕士学位论文基于描述逻辑的时态扩充研究及应用 c 虬地，( 口) = 3 而，而( 7 ( 口，x 1 ) u ( 口，屯) ( 而，而” 九q 魁p 7 ( 口) = v 毡，而( “l 0 ，而) a u 2 7 ( 4 ，恐) p “，而) ) a ，五，毛仨a r d 虹f 7 扣) - = 3 b ( r