逻辑程序的相容性与环公式研究

来源 :贵州大学 | 被引量 : 5次 | 上传用户:manhong85
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个逻辑程序可能有一个回答集、多个回答集或者根本就没有回答集。我们提出了一类逻辑程序—弱自相容逻辑程序。它们保证具有回答集而且有多项式时间算法可以计算其中一个回答集。另外,我们还获得了如下结果:(1)利用弱自相容逻辑程序中的相容性概念和A算子,获得了逻辑程序协调性质的一个充要条件。(2)两个有趣的弱自相容逻辑程序的本质特征,即强半单调性和任意良序下的前向链构造均生成一个回答集。(3)弱自相容逻辑程序的轻信推理(credulous reasoning)和怀疑推理(skeptical reasoning)的复杂性分别是NP-完全和co-NP-完全的。前向链正规逻辑程序的轻信推理和怀疑推理的复杂性也分别是NP-完全的和co-NP-完全的。判定一个逻辑程序是否是弱自相容的是co-NP-完全的。(4)弱自相容逻辑程序不同于命名协调的逻辑程序,他们互不包含。即使在限制逻辑程序必须是良基不可归约(WF-irreducible)的情形也是如此。前向链正规逻辑程序与命名协调逻辑程序也是不可比的。(5)另外,我们还发现,(a)对任何前向链正规的逻辑程序P,总存在一个最小的P上的一致性性质使得P是关于它前向链正规。(b)命名协调逻辑程序和Lifschitz的序协调(order-consistent)逻辑程序是等价的;而且它们有多项式时间算法来检查一个逻辑程序是否是命名协调(序协调)的。逻辑程序的环和环公式思想开辟了求解其回答集的新方法。我们将这一思想从命题情形推广到一阶的环和环公式,并得到了如下结果:(1)一个逻辑程序的一阶环公式和其Clark完备化(也是一阶的)一起精确地刻画了原来逻辑程序的回答集。(2)如果固定逻辑程序中出现的谓词符号的最大元(arity)数,则判定一个逻辑程序是否有有穷的完备环集是多项式时间可判定的。
其他文献
积极视角的开放教育学生管理工作在力求规范的同时应更关注提升学生的主观幸福感,在管理过程中应充分挖掘并利用好开放学生自身的优势,同时要努力提升辅导员的情商,还要进一步完
针对堤防工程综合安全监测体系,基于物联网技术,建立堤防工程海量数据资源的采集、汇集、交换与共享云平台;同时针对堤防工程质量、险情演化、致溃机理,基于大数据和人工智能
在当前这个快得让人窒息的时代,普遍陷入情绪焦虑的大众最希望看到积极向上、带给人希望和向善力量的故事。美国沃顿商学院教授Jonah Berge与同事Kathenne Milkman于2013年对
在线性系统理论中,系统的能控性和能观性是表征系统性质的两个重要特性。电子工程师们通常没有考虑网络是否能控或者能观这些特性,但他们设计的电路都工作得很好,是因为他们设计
远期外汇合同不能完全避免国际贸易和国际金融上的外汇风险,有时甚至可能丧失潜在的收益,“保值”不是履行远期外汇合同的必然结果。一般地,签订远期外汇合同,是外汇买卖交易
在计算机辅助几何设计中,定义在千变万化的拓扑结构上的自由曲线曲面,存在着千变万化的形式,而广义Ball曲线曲面则是其中一种在曲线求值及升降阶的计算速度方面明显优于Bézi
目的:通过对肺气虚证大鼠血清丙二醛(MDA)和肿瘤坏死因子-α(TNF—α)变化的实验研究,为肺气虚证客观定量化诊断和深入研究肺气虚证的本质提供依据。方法:将60只大鼠随机分为对照组
商品经济的发展,要求人们更清楚地认识商品的本质。从人的本质是智慧性,人有三种需求开始,分析商品的本质是服务性,是满足他人的需求,它体现了人的智慧。从而得出发展商品生
本研究主要观察了不同日粮锌水平对鸡肠粘膜结构和粘膜免疫相关细胞的形态、结构、细胞数量和分布变化的影响,以探讨日粮中锌对鸡肠道消化吸收和免疫屏障功能的动态影响。这奖
经济地理学是一门研究经济地域系统的形成过程、结构特征、发展趋向和优化调控的学科,是由地理学和经济学交叉而成的,介于自然、经济、技术三者之间的边缘学科。学科在发展过程