Database Reference
In-Depth Information
Definition 9.33 (Antwortmengen log. Progr. mit Default-Negation)
Seien
ein erweitertes logisches Programm und S ein Zustand. S heißt
Ant-
wortmenge (answer set) von
P
S
P
,wennS Antwortmenge des Reduktes
P
ist.
Beispiel 9.34
Wir erweitern das normale logische Programm
P
0
aus Beispiel 9.22
um die Regel(n)
¬Q(x) ←
not
Q(x).
und erhalten
P
5
:=
P
0
∪{¬
Q(x)
←
not
Q(x).
}
. Wir wollen zeigen, dass S
1
=
{
Q(a),
¬
Q(b),P(b)
}
eine Antwortmenge zu
P
5
ist: Wegen Q(a)
∈
S sind we-
S
5
der P (a). noch
¬
Q(a). im Redukt
P
. Andererseits impliziert Q(b) /
∈
S,dass
P (b).,
¬
Q(b).
∈P
S
5
gilt, insgesamt also
P
S
5
=
{
Q(a)., P (b).,
¬
Q(b).
}
. S ist trivialer-
weise Antwortmenge zu
P
S
5
und damit zu
P
5
.
Im Unterschied zu der stabilen Semantik gibt es allerdings nun fur ein Literal
A und eine Antwortmenge S drei Moglichkeiten: A ist
wahr in
S,wennA
∈
S, und
falsch in
S,wennA
S; liegt jedoch weder A noch A in S,soreprasentiert das
den Zustand des Nichtwissens. Die Antwortmengensemantik (
answer set semantics
)
wird in der gewohnten Weise durch die Inferenzrelation
∈
=
as
definiert:
|
=
as
A
P|
gdw.
A ist wahr in allen Antwortmengen von
P
wobei
ein erweitertes logisches Programm und A ein Literal ist. Entsprechend
werden die Antworten auf (literale) Anfragen Q an ein erweitertes logisches Pro-
gramm
P
P
unter der Antwortmengensemantik definiert:
yes
,wennP=
as
Q;
•
=
as
Q;
•
no
,wenn
P|
•
unknown
in allen anderen Fallen.
Das
no
der Antwortmengensemantik bedeutet also nun, dass man die entsprechende
Anfrage definitiv widerlegen kann.
Die folgende Proposition stellt die Verbindung zwischen Antwortmengen einer-
seits und klassischen bzw. stabilen Modellen andererseits her:
Proposition 9.35
Ist
ein klassisches logisches Programm, so stimmt seine Ant-
wortmenge mit seinem kleinsten Herbrandmodell uberein. Ist
P
ein normales logi-
sches Programm, so sind seine stabilen Modelle identisch mit seinen Antwortmen-
gen.
P
Die Semantik der Antwortmengen ist also eine Verallgemeinerung der klassischen
und der stabilen Semantik.
Fur das Antwortverhalten ist die Anzahl der Antwortmengen von Bedeutung.
Am einfachsten fallt die Beantwortung einer Anfrage, wenn man weiß, dass es genau
eine Antwortmenge gibt. Wie bei den normalen logischen Programmen ist auch hier
das Auftreten der Default-Negation verantwortlich fur das Vorhandensein mehrerer
Modelle, denn ein erweitertes logisches Programm P ohne Default-Negation besitzt
wegen P
S
=
P
fur jeden Zustand S hochstens eine Antwortmenge.
