Database Reference
In-Depth Information
Mittels Constraints kann man Antwortmengen mit unerwunschten Eigenschaf-
ten gezielt eliminieren. Fugt man beispielsweise dem Programm
P
3
aus Beispiel 9.24
Q(a)hinzu,soistS
1
=
noch den Constraint
die einzige Antwort-
menge des neuen Programms. Die zweite Antwortmenge S
2
=
←
{
P (a),P(c)
}
wurde
eliminiert. Allgemein bilden die Antwortmengen eines um Constraints erweiterten
Programms eine Teilmenge der Antwortmengen des ursprunglichen Programms, so
dass das Hinzufugen von Constraints immer einen einschrankenden,
monotonen
Ef-
fekt auf die Menge der Antwortmengen hat. Dieser Zusammenhang lasst sich noch
genauer beschreiben:
{
Q(a),P(c)
}
P
das
Selbsttestaufgabe 9.41
Sei
P
ein erweitertes logisches Programm, und sei
aus
P
durch Hinzufugen des Constraints
← A
1
,...,A
n
,
not
B
1
,...,
not
B
m
.
entstandene Programm. Zeigen Sie: Ein Zustand S ist genau dann eine Antwort-
menge von
P
,wennS eine Antwortmenge von
P
ist derart, dass nicht gleichzeitig
{
A
1
,...,A
n
}⊆
S und
{
B
1
,...,B
m
}∩
S =
∅
gilt.
Um bei mehreren moglichen Antwortmengen die “passendste” auswahlen zu
konnen, kann man (ahnlich wie bei Default-Logiken) die Regeln in logischen Pro-
grammen mit Prioritaten versehen und aus diesen Prioritaten Praferenzen fur die
Antwortmengen ableiten. Aktuelle Ansatze dazu werden z.B. in [26, 202] vorgestellt.
9.8
Stabile Semantik und Antwortmengensemantik
Syntaktisch gesehen stellen normale logische Programme eine Unterklasse der erwei-
terten logischen Programme dar, und stabile Modelle sind insbesondere Antwort-
mengen. Tatsachlich sind erweiterte Programme nicht wirklich ausdrucksstarker als
normale logische Programme, denn jedes erweiterte logische Programm kann auf ein
normales logisches Programm reduziert werden, und zwar in der folgenden Weise:
Fur jedes Pradikat P ,dasin
auftritt, fuhren wir ein Duplikat P
der glei-
chen Stelligkeit ein. Das Atom P
(t
1
,...,t
n
) hat die Aufgabe, das negierte Literal
¬
P
P (t
1
,...,t
n
)zureprasentieren und wird als seine
positive Form
bezeichnet. Die
positive Form
eines Atoms P (t
1
,...,t
n
) ist das Atom selbst. Generell wird die po-
sitive Form eines Literals L mit L
+
notiert. Die
positive Form
P
+
eines erweiterten
logischen Proramms
P
entsteht aus
P
in zwei Schritten:
•
In allen Regeln werden die Literale durch ihre positiven Formen ersetzt, d.h.
jede Regel der Form (9.3) (s. Seite 284) wird ersetzt durch die Regel
H
+
A
1
,...,A
n
,
not
B
1
,...,
not
B
m
.
←
•
Die Unvertraglichkeit komplementarer Literale wird durch das Hinzufugen der
Constraints
P (t
1
,...,t
n
),P
(t
1
,...,t
n
).
←
fur jedes in
P
auftretende Atom P (t
1
,...,t
n
) implementiert.