# Answer Set Programming for Regular Inference
## 2 Preliminaries
### Answer Set Programming  
Let us shortly introduce the idea of answer set programming (ASP). The readers interested in the details of ASP, alternative definitions, and the formal specification of AnsProlog are referred to handbooks [18; 19; 20]. Let \(\mathcal{A}\) be a set of _atoms_. A _rule_ is of the form:  
\[a\gets b_{1},\ldots,b_{k},\sim c_{1},\ldots,\sim c_{m}. \tag{2}\]  
where \(a\), \(b_{i}\)s, and \(c_{i}\)s are atoms and \(k,m\geq 0\). The _head_ of the rule, \(a\), may be absent. The part on the right of '\(\leftarrow\)' is called the _body_ of the rule. The symbol \(\sim\) is called _default negation_ and, by analogy to database systems, in logic programming it refers to the absence of information. Informally, \(a\leftarrow\ldots\sim b\) means: if \(\ldots\) and there is no evidence for \(b\) then \(a\) should be included into a solution. A _program_\(\Pi\) is a finite set of rules. Let \(R\) be the set of rules of the form:  
\[a\gets b_{1},\ldots,b_{k}. \tag{3}\]and \(\mathcal{A}\) be a set of atoms occurring in \(R\). The _model_ of a set \(R\) of rules without negated atoms is a subset \(M\subseteq\mathcal{A}\) which fulfills the following conditions:  
1. if \(a\leftarrow\). is in \(R\), then \(a\in M\);
2. if \(\gets b_{1},\ldots,b_{k}\). is in \(R\), then at least one \(b_{i}\) (\(1\leq i\leq k\)) is in \(\mathcal{A}-M\); for \(k=0\) (i.e., the head and the body of a rule \(r\in R\) are simultaneously absent) this condition does not hold, so no model exists;
3. for rules \(a\gets b_{1},\ldots,b_{k}\). with non-empty head and \(k>0\), \(b_{1},\ldots,b_{k}\in M\) implies \(a\in M\). Alternatively, if all atoms were treated as Boolean variables (i.e., presence is true, absence is false), \(M\) would be the model of an \(R\) exactly when all rules (i.e., clauses) are satisfied. The semantics of a program is defined by an answer set as follows. The _reduct_\(\Pi^{X}\) of a program \(\Pi\) relative to a set \(X\) of atoms is defined by  
\[\Pi^{X}=\{a\gets b_{1},\ldots,b_{k}\cdot\mid a\gets b_{1},\ldots,b_ {k},\sim c_{1},\ldots,\sim c_{m}.\in\Pi\text{ and }\{c_{1},\ldots,c_{m}\}\cap X= \emptyset\}. \tag{4}\]  
The \(\subseteq\)-smallest model of \(\Pi^{X}\) is denoted by \(\text{Cn}(\Pi^{X})\). A set \(X\) of atoms is an _answer set_ of \(\Pi\) if \(X=\text{Cn}(\Pi^{X})\). For the sake of simplicity, AnsProlog programs are written using variables (by convention, variables start with uppercase letters). Such programs are then grounded, i.e., transformed to programs with no variables, by applying a Herbrand substitution. Note, however, that clever grounding discards rules that are redundant, i.e., that can never apply, because some atoms in their bodies have no possibility to be derived [19]. For example, the program:  
\(el(a)\leftarrow\). \(el(b)\leftarrow\). \(equal(L,L)\gets el(L)\). \(neq(L,Y)\gets el(L)\), \(el(Y)\), \(\sim\)\(equal(L,Y)\). can be transformed to \(\Pi\):  
\(el(a)\leftarrow\). \(el(b)\leftarrow\). \(equal(a,a)\gets el(a)\). \(equal(b,b)\gets el(b)\). \(neq(a,a)\gets el(a)\), \(el(a)\), \(\sim\)\(equal(a,a)\). \(neq(a,b)\gets el(a)\), \(el(b)\), \(\sim\)\(equal(a,b)\). \(neq(b,a)\gets el(b)\), \(el(a)\), \(\sim\)\(equal(b,a)\). \(neq(b,b)\gets el(b)\), \(el(b)\), \(\sim\)\(equal(b,b)\). which has a single answer set: \(X=\{equal(a,a)\), \(equal(b,b)\), \(el(a)\), \(el(b)\), \(neq(b,a)\), \(neq(a,b)\}\). A reduct \(\Pi^{X}\) becomes:  
\(el(a)\leftarrow\). \(el(b)\leftarrow\). \(equal(a,a)\gets el(a)\). \(equal(b,b)\gets el(b)\). \(neq(a,b)\gets el(a)\), \(el(b)\). \(neq(b,a)\gets el(b)\), \(el(a)\). Its minimal model \(\text{Cn}(\Pi^{X})\) is just \(X\). In other words, a set \(X\) of atoms is an answer set of a logic program \(\Pi\) if: (i) \(X\) is a classical model of \(\Pi\) and (ii) all atoms in \(X\) are justified by some rule in \(\Pi\). Recently, Answer Set Programming has emerged as a declarative problem-solving paradigm. This particular way of programming in AnsProlog is well-suited for modeling and solving problems that involve common sense reasoning.