编程算法和逻辑_描述逻辑FLε合一算法

  本文关键词：描述逻辑FLε的合一算法，由笔耕文化传播整理发布。

描述逻辑FLε合一算法

【摘 要】描述逻辑（DL）一族知识表示系统，是一个非常热门的研究方向。一方面，重要的推理问题如包含问题是多项式得；另一方面，FLε被用做定义大的本体。已经提出的描述逻辑的合一算法能够作为一个新奇的推理服务，它被用做发现本体的冗余。本文主要的结果是FLε合一算法是可判定的。更精确地，FLε的一个部分εL是多项式完全，因此它和εL匹配有相同的计算复杂性。本文首先给出了描述逻辑系统FLε的语法和语义，特别地，蕴含合一问题没有有限的完备合一算子集，基于合一算法的规则探讨了可判定性问题。

【关键词】描述逻辑；FLε；合一算法；合一类型；可判定性

0 引言

描述逻辑是一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑，，一个描述逻辑系统包含四个基本组成部分：表示概念和关系的构造集；TBox包含断言；ABox实例断言；TBox和ABox上的推理机制。它们能够被用作表示在结构上和形式上为人所熟知的方法的应有领域中的概念知识。它们应用于各种各样的应用领域，例如：自然语言，组态，数据库和本体[1]。

两个项？坌child.Rich∩？坌child.Woman和？坌child.（Rich∩Woman）是相等的，如果我们用存在限制符（？埚r.C）取代值限算子符，那么这个等式不再成立。然而，？埚child.Rich∩？埚child.（Woman∩Rich）≡？埚child.（Woman∩Rich）通过用项Female∩Human取代Woman，这个概念项Woman∩？埚child.Woman和Female∩Human∩？埚child.（Female∩Human）是不相等的，但是它们意味着表示相同的概念。这两个项明显地能通过概念项Female∩Human替代第一个项中的概念名Woman而被做成相等。这导出我们的概念项的合一算法，也就是，两个概念项通过应用一个适当的替代，其中替代通过概念项取代概念名。

1 FLε的合一算法

5 结论

本文分析了描述逻辑合一算法的研究进展和存在问题，在Badder F 的基础上又进一步研究了带存在和任意算子的描述逻辑FLε的合一算法问题。给出了FLε的合一算法的定义，我们已经证明在DL FLε的合一算法是零型和其中的εL-合一算法是非决定性多项式完全（NP- complete）。

模态逻辑和描述逻辑有一个紧密的联系是众所周知的。例如这个DL ALC，它能向FLε加入否定来获得，对应于基本的（多）模态逻辑K，在K中的合一算法的判定是一个长期存在的开问题。最近，在K-一些扩展（例如，通过一元模态）的合一算法不可判定已经被证明，子布尔模态逻辑的合一算法（也即是，

  本文关键词：描述逻辑FLε的合一算法，由笔耕文化传播整理发布。