没有合适的资源?快使用搜索试试~ 我知道了~
论文研究-2-CNF理论的逻辑差.pdf
需积分: 18 0 下载量 79 浏览量
2019-07-22
17:59:27
上传
评论
收藏 844KB PDF 举报
温馨提示
试读
3页
如何刻画知识库不同版本之间的区别是研究知识库动态更新中的一个重要问题。提出了命题逻辑知识库的逻辑结论差概念(称为逻辑差)。然而,一般知识库之间逻辑差的计算是不易处理的,而且不满足范畴性,即不能保证其结果仍然可以用同类型的知识库来表达;由于2-CNF理论的可满足问题的易处理性,证明了2-CNF理论的逻辑差具有范畴性,并设计了一个多项式时间算法计算它们的逻辑差。
资源推荐
资源详情
资源评论
收稿日期:20140625;修回日期:20140803 基金项目:国家自然科学基金资助项目(61370161)
作者简介:刘蕻(1991),女,贵州六盘水人,硕士,主要研究方向为人工智能与模式识别(276771061@qq.com);原国伟(1988),男,硕士,主要
研究方向为人工智能与模式识别;梅俊杰(1988),男,硕士,主要研究方向为人工智能与模式识别;王以松(1975),男,教授,博士,主要研究方向
为知识的表示与推理.
2CNF理论的逻辑差
刘 蕻,原国伟,梅俊杰,王以松
(贵州大学 计算机科学与技术学院,贵阳 550025)
摘 要:如何刻画知识库不同版本之间的区别是研究知识库动态更新中的一个重要问题。提出了命题逻辑知
识库的逻辑结论差概念(称为逻辑差)。然而,一般知识库之间逻辑差的计算是不易处理的,而且不满足范畴性,
即不能保证其结果仍然可以用同类型的知识库来表达;由于 2CNF理论的可满足问题的易处理性,证明了 2
CNF
理论的逻辑差具有范畴性,并设计了一个多项式时间算法计算它们的逻辑差。
关键词:知识工程;2CNF理论;算法;逻辑差;归结
中图分类号:TP182 文献标志码:A 文章编号:10013695(2015)09257803
doi
:10.3969/j.issn.10013695.2015.09.004
Logicaldifferenceof2CNFtheories
LiuHong,YuanGuowei,MeiJunjie,WangYisong
(SchoolofComputerScience&Technology,GuizhouUniversity,Guiyang550025,China)
Abstract:Itisimportanttocapturethedifferencebetweendifferentversionsofaknowledgebase,intheviewofdynamical
change.Firstofall,thispaperintroducedthenotionoflogicaldifferenceforpropositionalknowledgebases.However,computing
thedifferencewasgenerallyintractable.Thelogicaldifferenceofaclassofknowledgebasewaspossiblynotcategorical
,i.e.,
thedifferencecouldn’tbepresentedinthesamedomain.Duetothetractabilityforthesatisfiabilityof2CNFtheories,itwas
provedthatthelogicaldifferenceof2CNFtheorieswascategorical,anddevelopedapolynomialtimealgorithmtocomputethe
logicaldifferencebetweentwo2CNFtheories.
Keywords:knowledgeengineering;2conjunctivenormalform;algorithm;logicaldifference;resolution
+
引言
知识库是一种在计算机系统里使用、被用来存储复杂的结
构化或非结构化信息的技术,它们被广泛地应用于语义网络、
医疗信息、专家系统等领域。其规模总是庞大又复杂的,从而
维护和使用知识库是一件费时费力的任务,在没有适当工具的
支持下是不可行的。
在知识库的维护和使用问题上,已存在很多良好建立的计
算机技术来支持知识库的合并、改进、重用以及扩展等操作。
在此过程中,知识库也会因此产生一些差异,这些差异分为基
于句法、基于结构和基于逻辑三种形式。对本体的版本控制问
题,
Conradi等人
[1]
对本体版本间基于句法的差异进行了相关
研究,如 CVS等。但本体的版本控制不能仅仅依靠基于句法
的差异,因为许 多句 法差 对版 本的 语义 没有 影响
[2,3]
。文 献
[3~6]对本体版本间基于结构的差异进行了相关研究,同时
考虑本体的结构信息,如增删改一个类、改变一个类的层次等。
逻辑差是最近才被提出来的
[7]
,它的表示完全抽象于本体,被
当做定义在 逻辑语 言上的 一个原 子公式 的集合。Konev等
人
[7]
的研究是基于一阶逻辑的子集———描述逻辑的,其中包
含很复杂难解的计算。文献[8,9]对逻辑差进行了具体的研
究,使用轻量级描述逻辑 DLLite等。在命题逻辑方面,Eiter
等人
[10]
对 Horn理论的布尔差进行了研究,其结果已不再是
Horn。
本文主要研究命题逻辑理论间的逻辑差问题。在描述问
题的过程中,通常需要使用较容易处理的命题理论子类。在命
题逻辑中,2CNF就是这样一种特殊的子类,其可满足性是易
处理的。首先提出了命题理论的逻辑差概念,然后证明了 2
CNF理论的逻辑差仍然可以用 2CNF理论来表达,最后提出
了一个多项式时间算法计算 2CNF理论的逻辑差。
!
预备知识
假设一个命题语言 L,文字是一个原子公式 x
i
或者其否定
「
x
i
。子句是文字的析取,k文字子句是 k个不同文字的析取
c=l
1
∨
l
2
∨
…
∨
l
k
,也可以表示为{l
1
,l
2
,…,l
k
},k称为子句的
长度。
子句的合 取 称 为 合 取 范 式 (
CNF)。CNF公 式 (或 称 为
CNF理论)中每个子句的长度不超过 k的公式称为 kCNF公
式(或 kCNF理论)。2CNF理论(简称 2CNFs)是 2CNF公式
的集合。
给定一个公式
Γ
,该公式中所有原子公式的集合用
Σ
Γ
表
示。命题逻辑中的归结规则是一种单一有效的推理规则。对
于包含互补文字的两个子句 a
1
∨
…
∨
a
n
∨
c和 b
1
∨
…
∨
b
m
第 32卷第 9期
2015年 9月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol32No9
Sep.2015
资源评论
weixin_39840588
- 粉丝: 448
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功