论文部分内容阅读
描述逻辑(DL)是一族知识表示形式系统,是人工智能领域的一个热门研究方向。以Baader F和Nebel B为代表的学者在描述逻辑上进行了大量富有成果的研究。他们早期的研究方向主要是针对表达能力比较弱的描述逻辑系统如:εL和FL0,研究它们在非循环定义下的标准推理算法和非标准推理算法。同时在这两人的工作基础上通过增加算子等方法的扩充工作有很多并而也出现很多很好的成果。
近年来以Baader F 发现循环定义下描述逻辑系统的表达在许多情况下更符合人们的直觉,而且具有更强的表达力,是非循环定义下的描述逻辑系统不可代替的,对此Baader F等人给出了描述逻辑系统εL和FL0 循环定义下的三种语义包含关系推理算法和一些非标准推理算法。这些成果可谓是一个重要突破,但也可以看出其难度是很大的。在国内,蒋运承,史忠植,王驹等人也做出了令人幸喜的结果。随着研究工作的深入人们发现只带交算子和存在算子的描述逻辑系统εL和只带交算子和任意算子的描述逻辑系统FL0的表达力是不能令人满意的。
因此本文初步探讨基于最大不动点语义下描述逻辑系统FLε循环定义的包含关系推理算法,并给出算法的可靠性和完全性证明。
说明:由2008年起,Baader,Distel等人也在从与我们不同的角度出发,研究系统FLε的推理机制问题。从最新的获得的非正式的资料来看: 1.他们的方法和过程十分冗长,有很多漏洞,其正确性不能令人信服。2.工作是完全独立于他们的工作的。3.方法简单得多,正确性有保证。
本文的主要内容安排如下:
第一章,介绍描述逻辑研究现状和本文的出发点。
第二章,给出描述逻辑系统FLε概念描述语法和语义,给出描述逻辑系统FLε有最大不动点模型的证明。
第三章,定义描述逻辑系统FLε正规术语集,描述图,模似关系各描述树。
第四章,给出FLε循环术语集的包含关系推理算法,和算法的可靠性和完全性证明。
第五章,结束语。
本文主要结论如下:
引理8 T为一个FLε- Tbox,J为一个原始解释,I为T的基于J的gfp-模型,对任意A ∈Ndef和x∈△x,下面两点等价:
1. X∈AI,2. 存在一个模型-模拟: Z:(G)T→~(G)I 使得(A,x)∈Z定理10 令T为一个FLε- Tbox,A和B 是两个被定义概念,则如果存在一个模拟: Z:(G)T→~(G)I 使得(B,A)∈Z,则 A(□)gfp,T B。
定理13 令T1和T2为两个包含有相同角色集和原始概念集的正规FLε- Tbox,且T=(T1 ∪ T2),A和B 分别是T1和T2中的任一被定义概念,(G)T1 和(G)T2分别是它们的描述图,I 是T的gfp-模型。如果B(A)gfp,T1,T2A则存在一个包含(A,B)的从(G)T1到(G)T2的模拟。
定理14 令T为一个FLε- Tbox A和B 是两个被定义概念。则如果存在一个模拟: Z:(G)T→~(G)I 使得(B,A)∈Z 当且仅当A(□)gfp,T B。
定理15 描述逻辑系统FLε的最大不动点语义下的包含关系算法的复杂度是多项式级的。