邏輯程序的相容性與環(huán)公式研究.pdf

1、一個(gè)邏輯程序可能有一個(gè)回答集、多個(gè)回答集或者根本就沒有回答集。我們提出了一類邏輯程序一弱自相容邏輯程序。它們保證具有回答集而且有多項(xiàng)式時(shí)間算法可以計(jì)算其中一個(gè)回答集。另外，我們還獲得了如下結(jié)果： (1)利用弱自相容邏輯程序中的相容性概念和A算子，獲得了邏輯程序協(xié)調(diào)性質(zhì)的一個(gè)充要條件。 (2)兩個(gè)有趣的弱自相容邏輯程序的本質(zhì)特征，即強(qiáng)半單調(diào)性和任意良序下的前向鏈構(gòu)造均生成一個(gè)回答集。 (3)弱自相容邏輯程序的輕信推

2、理(credulous reasoning)和懷疑推理(skepticalreasoning)的復(fù)雜性分別是NP-完全和co-NP-完全的。前向鏈正規(guī)邏輯程序的輕信推理和懷疑推理的復(fù)雜性也分別是NP-完全的和co-NP-完全的。判定一個(gè)邏輯程序是否是弱自相容的是co-NP-完全的。 (4)弱自相容邏輯程序不同于命名協(xié)調(diào)的邏輯程序，他們互不包含。即使在限制邏輯程序必須是良基不可歸約(WF-irreducible)的情形也是如此。前

3、向鏈正規(guī)邏輯程序與命名協(xié)調(diào)邏輯程序也是不可比的。 (5)另外，我們還發(fā)現(xiàn)，(a)對(duì)任何前向鏈正規(guī)的邏輯程序P，總存在一個(gè)最小的P上的一致性性質(zhì)使得P是關(guān)于它前向鏈正規(guī)。(b)命名協(xié)調(diào)邏輯程序和Lifschitz的序協(xié)調(diào)(order-consistent)邏輯程序是等價(jià)的：而且它們有多項(xiàng)式時(shí)間算法來檢查一個(gè)邏輯程序是否是命名協(xié)調(diào)(序協(xié)調(diào))的。 邏輯程序的環(huán)和環(huán)公式思想開辟了求解其回答集的新方法。我們將這一思想從命題情形推廣