描述逻辑εL(-)和εLu(-)表达力的刻画与比较

摘要：

逻辑的表达力及其推理问题的计算复杂性一直是逻辑研究的两个重点.描述逻辑是一族重要的知识表示语言,目前,国内外对其计算复杂性的研究成果比较丰富.而对其表达力的研究相对较少.从逻辑语义的角度看,解释之间的互模拟关系是刻画表达力的一个有效途径,其较具代表性的结论是刻画命题模态逻辑表达力的van Benthem定理.文中主要研究了包含顶概念、原子概念、原子概念否定、概念交和完全存在约束等5个概念构造子的描述逻辑εL(-),给出了εL(-)模拟关系,建立了刻画εL(-)表达力的van Benthem定理.在εL(-)基础之上,再增加概念并构造子,还给出了刻画εLu(-)表达力的van Benthem定理.在这些工作的基础上,给出了εL、εL(-)、εLu和εLu(-)等4个系统表达力之间的比较结果.再依据若干概念包含关系问题的计算复杂性结果,明确了如下结论:在表达力要求不高的情形下,可以优先选择εL作为知识的表示语言.而对表达力要求较高的情形下,应该优先选择ACC作为知识的表示语言.同时,在没有特殊要求的情况下,应尽量避免使用εL(-)、εLu和εLu(-)作为知识的表示语言.

关键词：描述逻辑、概念描述、术语公理集、表达力

所属期刊栏目：41

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金61103169,61403088;国家社会科学基金13CGL130;广东省自然科学基金S2013010013050;广东省高等学校学科与专业建设专项资金科技创新项目2013KJCX0069基金

在线出版日期：2018-07-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共17页

页码：898-914