论文部分内容阅读
一个逻辑程序可能有一个回答集、多个回答集或者根本就没有回答集。我们提出了一类逻辑程序—弱自相容逻辑程序。它们保证具有回答集而且有多项式时间算法可以计算其中一个回答集。另外,我们还获得了如下结果:(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)数,则判定一个逻辑程序是否有有穷的完备环集是多项式时间可判定的。