Databases Reference
In-Depth Information
In some cases, it is possible to emulate disjunction by unstratified normal rules by “shift-
ing” the disjunction to the body [32,33,34], as shown in the following example. Con-
sider
P
5
=
{
a
∨
b.
}
P
5
=
{
a
←
not
b.
;
b
←
not
a.
}
and its “shifted version”
.
Both programs have the same answer sets, namely
.
However, this is not possible in general. For example, consider
{
a
}
and
{
b
}
P
6
=
{
a
∨
b.
;
a
←
b.
;
b
←
a.
}
.Ithas
{
a, b
}
as its single answer set, while its “shifted version”
P
6
=
{
a
←
not
b.
;
b
←
not
a.
;
a
←
b.
;
b
←
a.
}
has no answer set at all.
P
5
are not strongly equivalent [35].
However, there is no deep relationship between “shifted” programs and strong equiv-
alence: They can be strongly equivalent (e.g.
Note that these considerations prove that
P
5
and
P
5
∪{←
P
5
∪{←
a,b.
}
and
a,b.
}
),
P
6
).
ASP inherits its main two reasoning tasks from nonmonotonic reasoning:
brave rea-
soning
(also called credulous reasoning) and
cautious reasoning
(also called skeptical
reasoning). Given a program
P
5
), or not equivalent at all (e.g.
equivalent (e.g.
P
5
and
P
6
and
P
and a formula
φ
without variables,
P|
=
b
φ
if
φ
is true
in some answer set of
. While these
definitions work for any formula, in ASP
φ
is often restricted to an atom, a literal, or a
conjunction of literals. When
φ
contains variables, one is asking for those substitutions
σ
for which
P
,
P|
=
c
φ
if
φ
is true in all answer sets of
P
P|
=
b
φσ
(or
P|
=
c
φσ
).
3.2
Semantic Characterizations
While the semantic definition given in the previous section is the one originally given
in [7], several other definitions have been shown to be equivalent to it.
For instance, Pearce showed in [36] how to link stable models and answer sets to the
intermediate logic HT (“Here and There”) proposed by Heyting [37] (corresponding
also to the three-valued Godel Logic
G
3
) by essentially adding an equilibrium criterion.
Another characterization has been provided by means of a simplified reduct that
became known as the
FLP reduct
[38,39]. The FLP reduct of a ground program
P
w.r.t.
X
, obtained from
aset
X
⊆
B
P
is the positive ground program
P
P
by
-
deleting all rules
r
∈P
for which the body is false (i.e.,
B
+
(
r
)
⊆
X
or
B
−
(
r
)
∩
X
=
∅
holds).
The definition of an answer set then remains equal modulo the replacement of Gelfond-
Lifschitz reduct by FLP reduct. The motivation for this reduct was a language extension
by aggregates (cf. the next section), but it also significantly simplifies the handling of
core programs, as rules that are not deleted by the reduct remain intact.
Further characterizations have been provided in [40].
3.3
Language Extensions
The work on ASP started with standard rules, but fairly soon implementations extend-
ing the basic language started to emerge. The most important extensions to the ASP
language can be grouped in three main classes:
-
Optimization Constructs
-
Aggregates and External Atoms
