回答集编程

回答集编程是语法上类似传统逻辑编程而语义上密切于非单调逻辑的一种声明式编程。在传统逻辑编程和回答集编程之间的主要区别是如何表示否定为失败。在传统逻辑编程中，否定为失败指示推导失败；在回答集编程中，它指示一个文字的一致性。

语法

回答集编程由规则的集合构成，每个规则由一个头部和一个后部构成:

$head\leftarrow body$

规则的头部和后部二者都是文字的集合，每个文字都是可能被否定的原子。与传统逻辑程序相反，原子都是命题而不是一阶的，并且可以使用两种形式的否定去否定它们: 经典否定(指示为 $\neg$)和否定为失败(指示为 $not$)。文字要么是原子要么是(使用经典否定)否定的原子。下面是一个例子程序:

$a\leftarrow b,not~c$
$a,not~\neg c\leftarrow not~d,\neg e$
$\neg c\leftarrow not~\neg e,a$

依据第一个规则，$a$ 是真，只要 $b$ 是真，并且 $c$ 可以被假定为假而不产生矛盾。

语义

程序的语义基于它的回答集，每个回答集都是文字集合。对于不包含否定为失败的程序，程序的语义基于闭包和最小性的概念:

• 程序在一个文字集合下闭合，如果这个集合包含至少一个在某个规则的头部中的文字，而总是包含在规则的体部中的所有文字。
• 文字集合是一个程序回答集，如果在这个程序闭合于的文字集合中、它(在集合的容量(containment)上)是最小化的。

如果程序包含使用否定为失败否定的一些文字，语义要求额外的简约概念:

• 一个程序在一个文字集合下的简约是通过对每个规则进行下列变更而获得的程序:
  1. 除去在头部中的、使用否定为失败否定的并且在集合中的所有文字；
  2. 除去在后部中的、使用否定为失败否定的并且在集合中不包含的所有文字；
  3. 删除整个规则，如果在应用完上面两个规则之后，它仍然包含(使用否定为失败)否定的原子。

文字集合是一个程序的回答集，如果它是这个程序在这个集合自身下的简约的回答集。换句话说，可以通过运行下列非确定性的算法来计算一个回答集可以:

 选择文字集合 L;
 计算程序 P 在 L 下的简约 PL;
 如果 L 是 PL 所闭合的最小化文字集合则
   输出 L

最初的文字集合 L 的选择是非确定性的。确定 L 是否为一个回答集的算法，首先计算程序在 L 下的简约，并接着检查 L 是否是这个无否定为失败的程序的回答集。

一个回答集程序可以有零个、一个或多个回答集。一个程序蕴涵一个文字，如果它的所有的回答集都包含这个文字。

比较、复杂性和实现

与 Prolog 相反，回答集程序的语义不依赖于规则的求值和原子在每个规则中的特定次序。

检查一个程序的回答集的存在性的复杂性，和检查一个程序是否蕴涵一个文字复杂性，范围是从 P 到多项式层次的第二级，依赖于一个程序可以满足也可以不满足的一组条件(就是说分层、头部中的析取)。

实现了回答集编程的三个系统是：smodels、dlv 和 cmodels。

参见

• 逻辑编程
• Prolog
• 非单调逻辑
• 缺省逻辑

引用

• T. Eiter, N. Leone, C. Mateis, G. Pfeifer, F. Scarcello (1998). The KR System dlv: Progress Report, Comparisons and Benchmarks. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98): 406-417
• V. Lifschitz (2002). Answer set programming and plan generation. Artificial Intelligence. 138(1-2): 39-54. doi:10.1016/S0004-3702(02)00186-8
• I. Niemela, P. Simons, T. Syrjanen (2000). Smodels: A System for Answer Set Programming. CoRR cs.AI/0003033

外部链接

• Working group on Answer Set Programming
• The DLV Project（页面存档备份，存于互联网档案馆）
• Smodels（页面存档备份，存于互联网档案馆）
• CMODELS（页面存档备份，存于互联网档案馆）