Answer Set Semantics

Introduction

The Answer Set Semantics are a declarative, non-monotonic semantics for logic programs with negation as failure introduced by Michael Gelfond and Vladimir Lifschitz. Unlike standard Prolog, the Answer Set Semantics define the models (in this context called Answer Sets) of a logic program independently of a particular inference mechanism. In contrast with other non-monotonic logics, the Answer Set Semantics are not super-classical; Instead, they use a collection of new logical connectives.

Syntax

A program $\Pi \,$ consists of a signature $\sigma \,$ and a collection of rules of the form:

$l_{0}\ or\ ...\ or\ l_{k}\ \gets \ l_{k+1},...,l_{m},\ not\ l_{m+1},...,not\ l_{n}$

where $l_{i}\,$ 's are literals (an atom $p(t)\,$ or its negation $\lnot p(t)$ ) from $\sigma \,$ . The logical connectives $not\,$ and $or\,$ are called negation as failure or default negation and epistemic disjunction respectively.

Given a rule $r\,$ ,
${\begin{aligned}head(r)&=\{l_{0}\ or\ ...\ or\ l_{k}\}\\pos(r)&=\{l_{k+1},...,l_{m}\}\\neg(r)&=\{l_{m+1},...,not\ l_{n}\}\\\end{aligned}}$

Satisfiability

A set $S\,$ of literals satisfies a literal $l\,$ if $l\in S\,$ .
A set $S\,$ satisfies a rule $r\,$ if one of the following conditions hold:
${\begin{aligned}pos(r)&\subseteq S\\neg(r)&\cap S\neq \emptyset \\head(r)&\cap S\neq \emptyset \end{aligned}}$

Semantics

The Answer Set Semantics assigns to a logic program $\Pi \,$ a collection of answer sets: consistent sets of literals over signature $\sigma \,$ . Logic programs under the Answer Set Semantics may have one, many or zero answer sets.

The precise definition of the answer sets is given in two parts: first for programs whose rules do not contain default negation, and then extended to arbitrary programs using the concept of the reduct of a program.

Answer Set - Part One

Let program $\Pi \,$ consists of rules of the form:

$l_{0}\ or\ ...\ or\ l_{k}\ \gets \ l_{k+1},...,l_{m}.$

An Answer Set of $\Pi \,$ is a consistent set $S\,$ of literals satisfying the following conditions:
- $S\,$ satisfies the rules of $\Pi \,$ .
- $S\,$ is minimal. i.e. no proper subset of $S\,$ satisfies the rules of $\Pi \,$ .

Reduct

Let $\Pi \,$ by an arbitrary logic program and $S\,$ be a consistent set of literals. The reduct, $\Pi ^{S}\,$ , of $\Pi \,$ relative to $S\,$ is the program obtained from $\Pi \,$ by:
i) removing all rules containing $not\ l$ such that $l\in S\,$ .
ii) removing all other premises containing $not$ .

Notice that $\Pi ^{S}\,$ is a logic program without default negation.

Answer Set - Part Two

A consistent set of literals $S\,$ is an answer set for logic program $\Pi \,$ if and only if $S\,$ is an answer set for $\Pi ^{S}\,$ .

Entailment

A program $\Pi \,$ entails a literal $l\,$ , $(\Pi \models l)$ if $l\,$ is satisfied by every answer set of $\Pi \,$ .

Answer to a Query

A logic program $\Pi \,$ 's answer to a query $q\,$ is 'yes' if $\Pi \models q$ ; 'no' if $\Pi \models \neg q$ and 'unknown' otherwise.