（计算机应用技术专业论文）时态逻辑及其对知识库的构架与研究.pdf

摘要 传统的适应冯诺依曼机器体系可执行语言的特征即表示自动机的状态转换 机制，其方式是命令式的，其语义是动态的；而适于这种模型的规范语言，其语 义则是静态的。当遇到动态的、实时的、并发的或具有其他时态特性的推理时， 这种静态的推理方式则有较大缺陷。作为模态逻辑的继承，与数理逻辑的又一外 延，时态逻辑断言推理则有效地解决这方面出现的难题。它能有效地运用于规则 的组织、推理与架构，并应用于知识库、智能决策支持系统、实时数据库、专家 系统等。 另一方面，在现行知识库中对于规则的组织、调度与推理并无统一标志。这 种无统一陛，造成在设计知识库时，由于外部条件、事件的不可确定性，使得库 内结构复杂，增加了设计的困难，也增加了推理的复杂度和准确性。 由此，针对知识库，可以做一个这样的探讨：使用时态逻辑对知识规则进行 构架，在知识库内则用时态逻辑断言进行推理，从而使得对知识库的规则驱动有 了一个统一的标志时态。 本文从时态逻辑及其知识表达开始介绍，并给出了时态逻辑对知识规则的构 架与推理的实例在新应用领域的研究与模拟实现，最后对知识库的时态驱动给出 探讨。其主要工作与贡献包括：一、在时态逻辑对知识规则的构架与推理方面， 针对性地给出了实例，在新应用领域上进行了研究与模拟实现；二、针对知识库 外部的事件驱动特性，以及内部规则组织与架构，对知识时态驱动给出了开创性 探讨。 关键词模态逻辑；时态逻辑；断言推理：知识库；时态驱动 广东工业大学工学硕士学位论文 a b s t r a c t t r a d i t i o n a le x e c u t a b l e l a n g u a g e ss u i t i n gt o t h ev o n - n e u m a u na r c h i t e c t u r ea r e c h a r a c t e r i z e db yt h es t a t es w i t c h i n go ft h ea u t o m a t i cm a c h i n e ，t h ec o m a n a n d - d r i v e n m o d e ，a n d t h ed y n a m i cs y n t a x b u tt h er u l eb a s e d l a n g u a g es u i t i n gt ot h i sp r ea n dp o s t a s s e r t i o nm o d e lh a sas t a t i cs y n t a x s ow h e ni tc o m e st ot h ei n f e r e n c ew h i c hi si n v o l v e d 谢md y n a m i c ，s y n c h r o n i z e d , r e a l - t i m ea n ds o m eo t h e rt e m p o r a lf e a t u r e s ，t h i ss t a t i c i n f e r e n c em e t h o dw i l le n c o u n t e ra g r e a td e a lo f t r o u b l e a si si n h e r i t e df r o mm o d a ll o g i c a n da n o t h e re x t e n s i o no f m a t h e m a t i c l o g i c ，t e m p o r a ll o g i ca s s e r t i o n i n f e r e n c ec a r ls o l v e s u c h p r o b l e m s i tc a n b e e f f i c i e n t l ya p p l i e d t ot h er u l e so r g a n i z a t i o na n di n f e r e n c e a n d i tc a nb ea l s oa p p l i e dt ok b ，i d s s ，r e a l - t i m ed a t a b a s ea n d e x p e r ts y s t e m s e t c o nt h eo t h e r h a n d , t h eo r g a n i z a t i o na n di n f e r e n c eo f t h er o l e si nt h ep r e s e n tk b h a s n ou n i f i e ds y m b o l ，w h i c hm a k e ss t r u c t u r ec o m p l i c a t e d , d e s i g n d i f f i c u l t , r e a s o n 曲gm o r e c o m p l e x a n da c c u r a t eb e c a u s eo f u n c o n f o r m a b l eo u t e rc o n d i t i o na n d e v e n t t h e r e f o r e ， w ec a nm a k es u c had i s c u s s i o na b o u tk bt h a tk n o w l e d g er u l ei s f r a m e db yu s i n g t e m p o r a ll o g i ca n du s i n gt e m p o r a ll o g i ca s s e r t i o nt oi n f e r t h u sm a k e st e m p o r a l i t ya s t h eu n i f i e ds y m b o lo f r u l e sw h i c hd r i v ei nk b f i r s t l y , t h ep a p e ri n t r o d u c e st e m p o r a ll o g i ca n di t s k n o w l e d g er e p r e s e n t a t i o n s e c o n d l y , i td e s c r i b e st h a tk n o w l e d g er u l e s s t r u c t u r eo nt e m p o r a ll o g i ca n dg i v e s i n f e r e n c ei n s t a n c ea n di t ss i m u l a t e d r e a l i z a t i o n l a s t l y , i td i s c u s s e st h et e m p o r a l d r i v e n o fk b t h em a i nt a s ka n dc o n t r i b u t i o ni n c l u d e st w op o i n t sa sf o l l o w s o n ei s t h a ti t g i v e si n s t a n c ea b o u tk n o w l e d g e r o l es t r u c t u r ea n di n f e r e n c eo n t e m p o r a ll o g i c ，w h i c hi s r e s e a r c h e da n ds i m u l a t i v er e a l i z a t i o ni nt h en e w a p p l i c a t i o nf i e l d t h eo t h e ri st h a ti t d i s c u s s e sk n o w l e d g et e m p o r a l d r i v e nb a s e do i lt h eo u t e re v e n t - d r i v e nc h a r a c t e ra n d i n n e rr u l eo r g a n i z a t i o no f t h ek b k e y w o r d sm o d a ll o g i c ，t e m p o r a ll o g i c ，a s s e r t i o n i n f e r e n c e ，k b ，t e m p o r a l d r i v e n i i 1 1 研究背景及意义 第一章绪论 早在公元前，亚里士多德( 前3 8 4 前3 z z ) 最初创建形式逻辑时，模 态逻辑与实然逻辑就开始同时讨论。在工具论中，前者的篇幅较后 者仍多之两倍。但是，从亚里士多德的底子开始，从中世纪以至近代逻 辑学的复兴与数理逻辑的突起，人们对知识的表达、规则推理乃至现代 计算机技术中知识库的形式表达以及架构都以数理逻辑为基础，对事物 的解释只简单地以由“真”与“非真”来表达，模态逻辑逐渐被忽略m 。 然而，在现实世界中，作为人类智慧源泉的知识，相当一部分是不 精确、不肯定、不完全、不必然的，很难通过简单的二值逻辑系统来表 达。而与此同时，模态逻辑开始复兴，路易斯开创了近代模态逻辑，并 避免了实质蕴涵怪论，引入了模态概念，并从而定义了严格蕴涵用以代 替实质蕴涵。 模态逻辑对命题演算提供了一个非常恰当的非真值系统。这种非真 值系统正是计算机科学所找寻的、一阶逻辑以外的逻辑工具之一，因此 模态逻辑从纯粹逻辑领域走到了应用领域一一传统的适应冯诺依曼机 器体系可执行语言的特征即表示自动机的状态转换机制，其方式是命令 式的，其语义是动态的；而适于这种模型的规范语言，即p r e 与p o s t 断 言( p r e 一 p o s t ) 其语义则是静态的i “。当遇到动态的、实时的、并发的 或具有其他时态特性的推理时，这种静态的推理方式则有较大缺陷。作 为模态逻辑的继承，与数理逻辑的又一外延，时态逻辑断言推理则有效 地解决这方面出现的难题。它能有效地运用于规则的组织、推理与架构， 并应用于知识库、智能决策支持系统、实时数据库、专家系统等。 广东工业大学工学硕士学位论文 另一方面，在现行应用软件、数据库软件和模型中，基本上都是以 事件驱动的。这主要表现在系统外部发生某一事件后，系统或主动或被 动地做出处理，以事件为驱动可以认为是系统外部( 对知识库而言则是 库外) 触发处理的一个统一标志；而在系统内部( 知识库内部) ，一般 来说处理根据各自条件，加以分析、判断来进行的，并无统一标志。这 种无统一性，使得在设计知识库的结构时，由于外部条件、事件的不可 确定性，造成库内结构复杂、规则的组织没有统一的标志，既增加了设 计的困难，也增加了系统的复杂度和准确性，无论在系统使用前的设计， 还是日后的维护、再开发上都有很大难度。 由此，针对知识库，可以做一个这样的探讨：使用时态逻辑对知识 规则进行构架，在知识库内则用时态逻辑断言进行推理，从而使得对知 识库的规则驱动有了一个统一的标志一一时态。 本文希望将从时态逻辑及其知识表达开始介绍，并给出了时态逻辑 对知识规则的构架与推理的实例在新应用领域的研究与模拟实现，最后 对知识库的时态驱动给出探讨。 1 2 国内外研究现状 在人工智能领域，不少学者提出了关于时态知识表达的模型，这些 模型大部基于时态逻辑的表达方法，一般被分为两大类：分别是基于时 间点和基于时间区间的时态模型。其中比较有影响的有：j a m e s a l l e n 指 出了时态区间( t e m p o r a li n t e r v a l ) 的1 3 种相互关系，并用一阶谓词来形 式化描述这1 3 种关系，这些时态关系可以较好的描述事件和活动 4 1 。 而在描述时态的逻辑语言方面，国内外具有较大影响力且已形成一 定理论与实践规模的有国内中科院唐稚松院士为首研究的x y z e 时态 逻辑语言口i 、与日本东京电子通信大学t a n d t l 语言 5 1 等。 其中，中科院软件所唐稚松院士等研究而成的x y z 系统是一种以时 第一章绪论 序逻辑语言x y z e 为基础的软件工程工具系统，而时序逻辑语言x y z e 基本是由一阶时序逻辑语言拓展得来。x y z e 属于多种类逻辑系统，即 其中变量具有多种类型。x y z e 的类型分为两个层次，上层为逻辑型， 用于表示逻辑公式，下层为非逻辑型，用于表示常见高级语言中所有在 表达式中出现的各种类型。其包括时态逻辑语言x y z e 与一组实现个 中方法论的c a s e 工具，并将各种分裂的程序设计，面向对象的模块程 序设计及可视化图形程序设计等以一种一直的逻辑框架统一起来，作为 共同形式予以的基础，以c a s e 工具作为系统支撑。 而国外方面，则在1 9 9 8 年，由日本东京电子通信大学的g a m i n i 弓i 入 t a n d 逻辑连接来描述不完全的相关时态知识，并构造了t a n d t l 时态 逻辑( t a n d t e m p o r a ll o g i c ) 。在他的博士论文中详细介绍了传统时态 逻辑在软件需求规格语言中存在的不足，提出了t a n d t l 时态逻辑，并 在此基础上设计了软件需求规格语言g s l ，论文附录中曾给出2 个应用实 例【 。 x y z 系统主要应用于工业化流程的实时控制，而t a n d t l 贝o 在商务 系统中得到应用，对于时态逻辑在知识库中的应用，尤其在面向w e b 、 面向多a g e n t 的应用方面，二者缺乏全面介入、开拓与研究。 1 3 前期工作 “协同软件研究开发中心”多年来一直从事时态知识与时态数据库 方向的研究工作。研发中心承担的广东省十五重点攻关项目工资智能决 策支持系统( 简称s i d s s ) 这一科研项目，为时态知识( t e m p o r a l k n o w l e d g e ) 、时态数据库( t e m p o r a ld a t a b a s e ) 及作为其基础的时态逻 辑( t e m p o r a ll o g i c ) 等课题提供了研究基础和应用。s i d s s 在时态处理 上有如下特色： 1 s i d s s 的工资、人员信息具有时态特性。目前的商用关系数据库 广东工业大学工学硕士学位论文 管理系统只存储现实世界的一个状态，也就是“最近”瞬像，而 这个状态并不涉及现实世界的动态变化，所以不一定能反映现实 世界的真正状态，这种数据库也称为瞬像数据库( s n a p s h o t d a t a b a s e ) 。s i d s s 在传统关系型数据库的基础上扩展了有效时 间，能够存储和管理用户的历史数据。 2 s i d s s 中考虑了时态知识的表达与逻辑推理。s i d s s 是一个智能 决策支持系统，其智能决策几个关键点是：历史数据库记录人员 的各类信息( 包括时态信息和非时态信息) ；把工资政策作为一种 时态知识，并可使用时态逻辑进行描述；事件生成器( 推理机) 在推理的过程中从数据库和知识库中分别获取时态信息和时态 知识，最后得出推理结果。在s i d s s 中，工资政策作为一种知 识存在，必须考虑其有效时间，推理过程所依据了大量的时态逻 辑断言推理，而尤其在于规则、方法的架构与调度方面 6 1 m 8 1 。 在前期研究工作中，我们已经在时态数据库和时态知识表达这两个 课题上做了大量工作，本文在此基础上，对知识规则的组织与架构，其 时态逻辑在知识库中的进一步应用进行了研究与探讨。 1 4 本文贡献及论文组织 在本文的工作中，主要贡献为：一、在时态逻辑对知识规则的构架 与推理方面，针对性地给出了实例，在新应用领域上进行了研究与模拟 实现；二、针对知识库外部的驱动特性，以及内部规则组织与架构，对 知识时态驱动给出了开创性探讨。 其研究的内容主要包括： 1 模态逻辑标准模型与正规系统： 2 一阶时态逻辑的一般基础、组成、分类与模型 3 时态逻辑及其知识表达 4 第一章绪论 4 时态逻辑对知识规则的架构与组织 5 传统断言的不足及时态逻辑断言推理 6 知识库的驱动方法与规则组织 7 时态驱动的知识库 本文第二章从时态逻辑的起源模态逻辑开始介绍，给出了时态逻辑 的基础知识，分别介绍了模态逻辑标准模型与正规系统、一阶时态逻辑 的一般组成、分类与模型以及时态逻辑的p e t r i 网描述。 第三章对时态逻辑方面的进阶知识进行了讨论，如时态逻辑及其知 识表达的基本方法与分类，以及几种经典的时态逻辑知识表达。 第四章，进而对传统断言及其不足进行了分析，并针对此介绍了时 态逻辑语言及其断言推理，结合实例讲述了其在新应用领域上的研究与 模拟实现。 第五章，则从时态逻辑断言推理的特点和优势，以及知识库外部的 驱动方法与内部规则组织，对知识库的时态驱动提出了开创性探讨，对 其在w e b 与多a g e n t 情况下的应用前景进行了分析与讨论。 2 。1 模态逻辑 第二章时态逻辑基础 模态逻辑是一种关于可能性和必然性的逻辑【1 l ，被讨论的命题可能 为真( 假) ，或者必然为真( 假) 。近代以来，它直被称为“非经典逻 辑”，但值得一提的是，早在亚里士多德创建形式逻辑时，模态逻辑和 实然逻辑就已经在工具论中一同讨论，且篇幅约为后者的3 倍。然 而由于后续研究的断层，直至中世纪模态逻辑才复兴，这时人们已习惯 把数理逻辑称为“经典逻辑”了。在本文中，我们仍以近代说法为准， 将“数理逻辑”称为“经典逻辑”，将“模态逻辑”称为“非经典逻辑” 之一种。 “必然”与“可能”的相关讨论是由数学家、哲学家莱布尼兹提出 的：一个命题是必然的，如果它在所有的可能世界中都使用；一个命题 是可能的，如果它在某个可能世界中使用。 模态逻辑( m o d a ll o g i c ) 就是研究形如“必然的”或“可能”这 种表达式的推理行为 2 1 ，它引入了两个模态算子：口( 必然) 和( 可 能) 【1 。 将莱布尼兹的思想做语言表述就是：口a ，必然a ，是真的当且仅当 a 本身在每一个可能世界都是真的；a ，可能a ，是真的当且仅当a 在 某个可能世界中是真的。 此外，在模态逻辑中符号f 。”k 表示在可能世界集“的某个可能世界 。中，a 成立，这为模态逻辑模型打下基础。 2 1 1 模态逻辑的标准模型 逻辑的表述依靠模型，在模态逻辑的标准模型中可能世界可表示为 一个三元组： m ，这里w 是可能世界集，p 是w 的无穷序列p 。， p 。，p 。，r 则为可能世界中的一切关系。关于此三元组的标准模型， 我们可定义为： 定义：2 1 u = 是一个标准模型，当且仅当： 1 ) w 是一个集合： 2 ) r 是w 之上的二元关系( r w w ) ； 3 ) p 是从自然数( 包括0 ) 到w 的子集的一个影射，对于每一个自 然数1 3 ，p 。w 由此，我们可以得到在标准模型中，f 。“口a 和f 。”a 的定义如下： 定义：2 2 设q 为标准模型u = 的一个世界： 1 ) f 。“口a 表示，当且仅当对于u 中的每一个使得nrb 的b ，f 。“a ； 2 ) f 。“a 表示，当且仅当对于“中的某一个使得nrp 的b ，f 。“a 。 于是，我们得到模态逻辑标准模型中的两条最基本定理m ： 定理：2 3 设c 为一个标准模型类。则： 1 ) f 。a 一口一a 2 ) 对于n 0 ，若f 。( a l 八八a n ) 一 a ， 则f 。( 口a 1 八八口a n ) 一 口a 2 1 2 模式与正规系统 由模态逻辑的标准模型，在一定条件下，我们可以得到以下五条合 法的模式： d 口a 一 a t 口a 一 a 广东工业大学工学硕士学位论文 b a 一 口a 4 口a - - 口口a 5 a 一 口a 它们分别在以下条件下成立： d 标准模型中，r 是序列的 t 标准模型中，r 是自反的 b 标准模型中，r 是对称的 4 标准模型中，r 是传递的 5 标准模型中，r 是欧几里得的 由这5 条模式，我们可以组合成1 5 个相异的模态逻辑正规系统。例 如，最简单而又最经典的公理系统s 5 ( 即刘易斯s 5 系统) ，其又称k t 5 一 系统，由模式t 和模式5 推理而得，包括5 条公理和2 条规则，对模态 逻辑及其模型进行公理化描述如下： 5 条公理： t 口a 一 a 5 a - - 口a k 口( a b ) ( 口a 口b ) d f a ，口一a pl a ，在此，a 是一个重言式 2 条规则 r n 尘 ej a m p a - b , a 占 对于s 5 中的定理，首先公理自动是定理，其次则是指任何一个能够 在公理和推理规则基础上得到的语句，例如记“j a ”，表示a 为一个定 理a 一个推理规则被严格理解为：如果其各个假设是一个定理，那么其 结论也是一个定理。如，规则r n ，只要| _ a ，就有| e a 。 第二章时态逻辑基础 此外还有几个最重要的正规系统，如由模式d 为主定理得到的k d 一 系统( 基本义务模态逻辑系统) 、由模式t 为主定理得到的k t - 系统( 真 理模态逻辑系统) 、由模式t 和b 为主定理得到的k t b 一系统( 布劳维尔 系统) 、由模式t 和4 为主定理得到的k t 4 一系统( 刘易斯s 4 系统) 和 由模式t 和5 为主定理得到的k t 5 一系统( 刘易斯s 5 系统) 。 现有方法已证明系统k d 一、k t 、k b t 、k t 4 、k t 5 都是可靠的， 一致的，并且是完备的，鉴于章节有限，在此不做详细讨论，有兴趣的 读者可参考文献1 。 2 2 时态逻辑 模态逻辑为计算机科学( 如数据库、知识库和并发程序等) 的研究 提供了一种非真值系统，并成为一种形式化的途径，模态词可用来表示 “知道”、“相信”等概念。 如果把模态算子口为将来时模态，读作“将总是这种情形” ( h e n c e f o r t h ) 。于是我们得到一个时态的必然概念，它是基于时间点的， 在标准模型中r 提供了时间集的次序关系，使nrb 表示“时刻n 先于 时刻1 3 ”，因而口a 在时刻a 是真的，当且仅当a 在每一个使得nrd ， 即使得迟于a 的时刻b 中是真的。同样，我们可以将解释为“将来会” ( e v e n t u l l y ) ，于是便衍生了时态逻辑( t e m p o r a ll o g i c ) 。 时态逻辑的概念是a r t h u rp r i o r 在1 9 6 0 年左右在探讨哲学逻辑问题 时首先提出的( 原名为：t e n s el o g i c ) ，它的逻辑语言包括四个模态算 子：p 、f 、h 和g 。其含义如下】： p ：过去的某个时间是 f ：未来的某个时间是 h ：过去一直是 g ：未来一直是 广东工业大学工学硕士学位论文 p 和f 也被称作弱时态算子( w e a ko p e r a t o r s ) ，而ha n dg 被称为强 时态算子( s t r o n g t e n s eo p e r a t o r s ) 它们之间可以等价定义为： p p8h7p( 过去某个时间为p 一不会过去一直不为p ) f p57g7p( 未来某个时间为p - - = 不会未来一直不为p ) k a m p 扩展了a r t h u rp r i o r 的t e n s el o g i c ，他提出2 个时态算子 s ( “s i n c e ”) 和u ( “u n t i l ”) 。其含义如下： sp q ：在过去某个时间p 为真，然后q 才开始为真。 up q ：到将来某个时间p 为真，然后q 才开始为真。 逻辑学家和计算机科学家最后在此基础上进一步展了时态逻辑 ( t e m p o r a ll o g i c ) ，下面我们以一阶时态逻辑为主( 二阶逻辑主要讨论 的是谓词作用在集合而非对象时的关系，非计算机科学中的重点) ，详 细介绍时态逻辑的各个组成部分。 2 2 1 一阶时态逻辑的组成 一阶逻辑常由命题、谓词符号、函数符号、运算符、变量等组成， 一阶时态逻辑也不例外。但就目前来说，一阶时态逻辑及一阶逻辑语言 仍在发展当中，未形成统一，其种类非常繁多，各有差异，各系统定义 的时态运算符和操作及功能等虽大部相似，但都不尽相同m m 【9 】 10 1 。就一 般而言，其组成如下： 谓词符号p ； 与经典逻辑一样，对于命题“人总是要呼吸的”，我们可表示为p ( x ) ， 其中x 为人。 实际上，谓词符号是任何一阶逻辑系统中最基本的元素，我们在这 里提到，是为了对以下函数符号的提出加以区分。 函数符号f ； 我们可以用谓词符号表示关系，这本身对于数理逻辑和模态逻辑来 1 0 说都是足够的，但考虑到对于某些数学系统，函数作为特殊类型的关系， 具有直觉上的清晰性，因此a g 汉密尔顿在数理逻辑中将其加入，在 模态逻辑、时态逻辑中也不例外，而且是相当重要的。 例如，假设我们用f 。2 表示+ ，f 。2 表示，用p 表示= ，那么p ( f ，2 ( x l ，x 2 ) ，f 。2 ( x 1 ，x 2 ) ) 可解释为“x l + x 2 = x l x 2 ”，这里上标表示变 元的数目，而下标具体指向一变元的序号。 时态运算符( o ，口，u ，w ，s ) 时态运算符是一阶模态逻辑中最重要的组成部分，也是区别于经典 一阶逻辑的标志，在t e n s el o g i c 之后，相关学者对其作了一下扩充 5 1 ： 1 ) oa ( n e x ta ) ：i faa n dba r ef o r m u l a et h e n 0 a ： 2 ) 口a ：a l w a y si n t h ef u t u r ea ： 3 ) o a ：s o m e t i m e si nt h ef u t u r ea ) ： 4 ) a u b ：au n t i lb ) ： 5 ) a ：l a s ta ) ： 6 ) 一a ：a l w a y s i nt h e p a s ta ： 7 ) a ：s o m e t i m e si nt h ep a s ta ： 8 ) a s b ：as i n c eb ： 其语义解释为 1 ) 卜_ 2 ) 卜- 3 ) _ 4 ) 卜 j ) t h e n 5 ) 卜 6 ) 卜 7 ) 卜 oa i f f _ a ； 口a i f f 留j i _ a ； o a i f f 目j i 卜a ； a u bi f f g j i 卜ba n d 眺i f ( i k 卜a ： ai f fi = 0 o r 卜a ； _ ai f f 呵j0 4j i ， _ a a i f f 园jo j 卜a ； 广东工业