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

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

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

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