Database Reference
In-Depth Information
CWA
(
P
):=
P∪{¬
P (x
1
,...,x
n
)
←
not
P (x
1
,...,x
n
).
|
P
∈
Pred
P
}
wobei die Anzahl n der auftretenden Variablen jeweils der Stelligkeit des Pradikats
entspricht. Die folgende Proposition stellt eine genaue Beziehung her zwischen den
stabilen Modellen eines normalen logischen Programms und den Antwortmengen
seiner
CWA
-Erweiterung.
Proposition 9.44 ([8])
Sei
P
ein normales logisches Programm. Ist
S
ein stabiles
Modell von
P
,soist
S
∪{¬
A
|
A
∈H
(
P
)
\
S
}
(9.5)
eine Antwortmenge von CWA
(
P
)
,wobei
H
(
P
)
die Herbrandbasis zu
P
ist. Umge-
kehrt lasst sich jede Antwortmenge von CWA
(
P
)
als Erweiterung der Form (9.5)
eines stabilen Modells
S
von
P
darstellen.
Dank dieses engen Zusammenhangs lassen sich nun auch stabile und Antwort-
mengensemantik normaler logischer Programme zueinander in Beziehung setzen.
Proposition 9.45
Sei
P
ein normales logisches Programm. Fur jedes Grundliteral
L
gilt:
=
stab
L
=
as
L
P|
gdw.
CWA
(
P
)
|
Selbsttestaufgabe 9.46
Beweisen Sie Proposition 9.45 mit Hilfe von Proposition
9.44.
Abschließend weisen wir noch darauf hin, dass Antwortmengen im Allgemeinen
und stabile Modelle im Besonderen sich als Fixpunkte eines passenden Operators
darstellen lassen: Zu einem erweiterten logischen Programm
P
definieren wir einen
Operator γ
P
auf den Zustanden S von
P
durch
S
)
γ
P
(S)=
Cl
(
P
S
geschlossenen Zustand bezeichnet (vgl.
Abschnitt 9.5). Dann ist S Antwortmenge von
S
) den minimalen, unter
wobei
Cl
(
P
P
P
genau dann, wenn gilt
S = γ
P
(S)
9.9
Truth Maintenance-Systeme und Default-Theorien
Die Ahnlichkeit zwischen Justification-based Truth Maintenance-Systemen und nor-
malen logischen Programmen ist auffallend. Jede Begrundung
{
A
1
,...,A
n
}|{
B
1
,...,B
m
}→
H
eines JTMS
T
=(N,
J
)mitKnotenA
1
,...,A
n
,B
1
,...,B
m
,H
∈
N lasst sich als
Regel
H
←
A
1
,...,A
n
,
not
B
1
,...,
not
B
m
.
