回答集編程是語法上類似傳統邏輯編程而語義上密切於非單調邏輯的一種聲明式編程。在傳統邏輯編程和回答集編程之間的主要區別是如何表示否定為失敗。在傳統邏輯編程中，否定為失敗指示推導失敗；在回答集編程中，它指示一個文字的一致性。
基本介紹
- 中文名：回答集編程
- 學科：計算機
語法,語義,比較,比較、複雜性和實現,
語法
回答集編程由規則的集合構成，每個規則由一個頭部和一個後部構成:
<math>head \leftarrow body</math>
規則的頭部和後部二者都是文字的集合，每個文字都是可能被否定的原子。與傳統邏輯程式相反，原子都是命題而不是一階的，並且可以使用兩種形式的否定去否定它們: 經典否定(指示為 <math>\neg</math>)和否定為失敗(指示為 <math>not</math>)。文字要么是原子要么是(使用經典否定)否定的原子。下面是一個例子程式:
<math>a \leftarrow b, not~c</math>
<math>a, not~\neg c \leftarrow not~d, \neg e</math>
<math>\neg c \leftarrow not~\neg e, a</math>
依據第一個規則，<math>a</math> 是真，只要 <math>b</math> 是真，並且 <math>c</math> 可以被假定為假而不產生矛盾。
語義
程式的語義基於它的回答集，每個回答集都是文字集合。對於不包含否定為失敗的程式，程式的語義基於閉包和最小性的概念:
程式在一個文字集合下閉合，如果這個集合包含至少一個在某個規則的頭部中的文字，而總是包含在規則的體部中的所有文字。
文字集合是一個程式回答集，如果在這個程式閉合於的文字集合中、它(在集合的容量(containment)上)是最小化的。
如果程式包含使用否定為失敗否定的一些文字，語義要求額外的簡約概念:
一個程式在一個文字集合下的簡約是通過對每個規則進行下列變更而獲得的程式:
除去在頭部中的、使用否定為失敗否定的並且在集合中的所有文字；
除去在後部中的、使用否定為失敗否定的並且在集合中不包含的所有文字；
刪除整個規則，如果在套用完上面兩個規則之後，它仍然包含(使用否定為失敗)否定的原子。
文字集合是一個程式的回答集，如果它是這個程式在這個集合自身下的簡約的回答集。換句話說，可以通過運行下列非確定性的算法來計算一個回答集可以:
選擇文字集合 L;
計算程式 P 在 L 下的簡約 PL;
如果 L 是 PL 所閉合的最小化文字集合則
輸出 L
最初的文字集合 L 的選擇是非確定性的。確定 L 是否為一個回答集的算法，首先計算程式在 L 下的簡約，並接著檢查 L 是否是這個無否定為失敗的程式的回答集。
一個回答集程式可以有零個、一個或多個回答集。一個程式蘊涵一個文字，如果它的所有的回答集都包含這個文字。
比較
與 Prolog 相反，回答集程式的語義不依賴於規則的求值和原子在每個規則中的特定次序。
