AIL C7 回答集编程

回答集编程，ASP是一种建模非单调推理的逻辑编程与问题求解范式。一个 ASP 程序由一组规则组成，每条规则与霍恩子句类似，但可以包含带缺省否定($not$)的文字。故ASP可以建模非单调推理。

ASP 结合了逻辑编程语言 Prolog 的语法和语义定义，以及 SAT 求解器的可满足搜索机制。

逻辑程序

逻辑程序由一组逻辑编程规则组成。

逻辑编程规则

每条逻辑编程规则形如：

$$a_0 \leftarrow a_1, . . . , a_n, not\ a_{n+1}, . . . , not\ a_{n+k}.$$

其中$a$ 是原子公式, $not\ a$ 称作 “失败即否定” 公式，简称 $\textbf {naf}$公式。

not 与 $\lnot$: 强否定与弱否定

• $\lnot a$: 表示明确知道 $a$为假。
• $\rm not\ a$ : 表示$a$为真是不可证明的，是弱否定。

记上公式为$r$，则

• $a_0$被称为规则头，记作$head(r)$
• $\left\{a_1, . . . , a_n, not\ a_{n+1}, . . . , not\ a_{n+k}\right\}$ 被称为规则身体，记作$body(r)$。

则$r$可记作

$$head(r)\leftarrow body(r).$$

• 基规则：规则中的所有文字都是基文字的规则。
• 肯定规则：$k = 0$，即不包含naf。
  • 肯定程序 / 霍恩程序：只包含肯定规则的程序。
• 事实： $body(r) = \empty$
• 约束/目标：$head(r) = \empty$

基化，grounding

给定一个语言 $\cal L$， 则该语言的

• 赫布兰德域$HU_{\cal L}$：所有可以由 $\cal L$ 中的个体常元和函数形成的基项 的集合。
• 赫布兰德基底$HB_{\cal L}$：所有可以由$\cal L$中的谓词和$HU\cal_L$ 的项形成
  的基原子公式的集合。

设 $r$ 是语言 $\cal L$中的一条规则。$r$ 在 $\cal L$中的基化，grounding，记作 $ground(r, {\cal L})$：HU_\cal L 中的元素对 $r$ 中的变元进行所有可能的代换而得到的所有规则集合。

字母表

给定一个字母表，回答集语言是所有可以从该字母表中的符号建构起来的基规则集合。

基程序

给定一个逻辑程序$\Pi$，则基程序：

$$ground(\Pi,{\cal L}) = \cup_{r\in\Pi}ground(r,{\cal L})$$

通常简写为$ground(\Pi)$。

程序的语义

给定一个程序$\Pi$，它的语义按照它的基程序 $ground(\Pi)$ 的语义来定义。

肯定程序的语义

给定程序$\Pi$，

• $\Pi$的一个赫布兰德解释：赫布兰德基底的任意子集。记作 $I,I \sube HB_{\cal L}$。

• $\Pi$的一个赫布兰德模型：$\Pi$的赫布兰德解释$I$，且满足以下条件：

  1. 对于每条规则$r = a_0 \leftarrow a_1, . . . , a_n.$，如果$a_1, . . . , a_n$ 关于 $I$ 为真，即 $\{a_1, . . . , a_n\} \sube I$，那么 $a_0$ 也关于 $I$ 为真。
     也即说 $I$ 满足规则 $r$。
  2. 对于每条规则$r = \leftarrow a_1, . . . , a_n.$，如果 $\{a_1, . . . , a_n\}\not\sube I$，那么 说 $I$ 满足规则 $r$。

• $\Pi$的极小赫布兰德模型：赫布兰德解释$I$ 在集合$\{I_1, . . . , I_n\}$中是极小的，如果不存在$j:1 \le j\le n$，使得$I_j \subsetneq I$。把这样的$I$简称极小模型，记作$M_\Pi$。

  极小赫布兰德模型不是唯一的。可能出现两个不可比的赫布兰德解释，任何解释都不是它们的真子集。如$\{a\}$，$\{b\}$，$\{a,b\}$中$\{a\}$，$\{b\}$是极小的。

• $\Pi$的最小赫布兰德模型：赫布兰德解释$I$ 在集合$\{I_1, . . . , I_n\}$中是最小的，如果$\forall j: 1 \le j\le n,I \sube I_j$。

回答集

$\Pi$的回答集：$\Pi$的极小赫布兰德模型。

不动点算子$T_\Pi$

定义一个不动点算子$T_\Pi$把程序$\Pi$的一组原子公式集合$X$映射到另外一组原子公式集合$T_\Pi(X)$，使得

$$T_{\Pi}(X) = \{a \in HB_\Pi | \exist r \in \Pi:(head(r) = a )\wedge (\forall b\in body(r):b\in X)\}$$

计算极小模型

极小模型是$T_\Pi$算子的不动点。即$T_\Pi(X) = X$。计算不动点的方法如下：

1. $k = 1: X_1 = T_\Pi(\empty)$。
2. $k \ge 2:X_{k + 1} = T_\Pi(X_k)$
   • 若$X_{k+1} = X_k$， 停止并返回$X_k$作为不动点，记作$T_\Pi^\infty(\empty)$或者${\rm lfp}(T_\Pi)$。
   • 否则，$k = k + 1$，并重复2.。

LEMMA 1 对于一个肯定程序$\Pi$和有穷的赫布兰德基底$HB_\Pi$，上述算法将会停止。

$T_\Pi$的性质：

• $T_\Pi$ 是单调的：如果$X \sube Y$， 则$T_\Pi(X) \sube T_\Pi(Y)$。
• $M_\Pi = {\rm lfp}(T_\Pi)$
• 不含约束的肯定程序$\Pi$的$M_\Pi$ 是唯一的。

一般/正规逻辑程序的语义

一般逻辑程序 / 正规逻辑程序： 含含形如式

$$a_0 \leftarrow a_1, . . . , a_n, not\ a_{n+1}, . . . , not\ a_{n+k}.$$

的规则的逻辑程序。

肯定程序的极小模型方法不能被直接用来定义正规逻辑程序的回答集。

考虑仅含一条规则的程序$\Pi$：

$$a \leftarrow not\ b.$$

则$\Pi$有两个"极小模型" $\{a\}$ 和 $\{b\}$。但是由于没有理由说明$b$ 为真的理由，故该方法的结果是违反直觉的。

正规逻辑程序回答集

设$\Pi$是一个不含约束的正规逻辑程序，$S$是任意原子公式集合 。

$\Pi^S$ 是通过如下步骤得到的约简的逻辑程序：

1. 将$\Pi$赋值给$\Pi^S$。$\Pi^S <= \Pi$。
2. 对于每条$\Pi_S$中的规则$r$ ：
   1. 如果 $not\ a \in body(r)$ 且 $a \in S$，则把$r$从$\Pi_S$中删除。
   2. 否则把其 $body(r)$的每个形如 $not\ a$ 的文字删除。

显然$\Pi^S$ 是一个肯定程序。称$S$是$\Pi$的回答集，若$M_{\Pi^S} = S$，也即$\Pi^S$的回答集存在且为$S$。

有些程序可能没有回答集。考虑程序$\Pi$：

$$\begin{align*}&p \leftarrow not\ p, d.\\&r \leftarrow .\\&d \leftarrow .\end{align*}$$

由于 $r$ 和 $d$ 必须在任何回答集中，$\Pi$的两个可能回答集是$S_1 = \{r, d, p\}$ 和$S_2 = \{r, d\}$。

• $\Pi^{S_1} = \left\{r \leftarrow .,d \leftarrow .\right\}$ 有回答集 $\{r, d\} \not = S_1$。
• $\Pi^{S_2} = \left\{r,d,p\right\} \not= S_2$

因此$S_1$和$S_2$均不为$\Pi$的回答集。形如$p \leftarrow not\ p.$的规则会导致程序没有回答集合。

注意区分回答集为空和没有回答集的区别。

含约束逻辑程序的回答集

对于一个含约束的逻辑程序$\Pi$，把 $\Pi$ 分为两个集合:

• $\Pi_O = \{r | r \in \Pi, head(r) \not = \empty\}$ 是一个不含约束的程序。
• $\Pi_C = \Pi - \Pi_O = \{r | r \in \Pi, head(r) = \empty\}$。

对于一个基原子公式集合 $S$ 和一个约束 $c$：

$$\leftarrow a_1, . . . , a_n, not\ a_{n+1}, . . . , not\ a_{n+k}.$$

称 $S$ 满足 $c$，如果 $\{a_0, . . . , a_n\} - S \not = \empty$ 或 $\left\{a_{n+1}, . . . , a_{n+k}\right\} \cap S \not = \empty$。

一个基原子公式集合 $S$ 是程序 $\Pi$ 的一个回答集，如果

• $S$ 是 $\Pi_O$ 的回答集;
• $S$满足 $ground(\Pi_C)$ 的所有约束。