Database Reference
In-Depth Information
Definition 9.17 (geschlossener Zustand)
Sei
ein erweitertes logisches Pro-
gramm, in dessen Regeln keine Default-Negation auftritt, und sei S ein Zustand. S
heißt
geschlossen unter
P
P
,wennfur jede Regel r aus
P
gilt: Ist
pos
(r)
⊆
S,soist
head
(r)
∩
S
=
∅
.
Fur Regeln H
←
A
1
,...,A
n
eines logischen Programms
P
ohne Default-Negation
und unter
P
geschlossene Zustande S gilt also: Ist
{
A
1
,...,A
n
}⊆
S, so folgt H
∈
S.
Ist hingegen r :
←
A
1
,...,A
n
ein Constraint von
P
, so kann wegen
head
(r)=
∅
niemals
head
(r)
S nicht
erfullt sein - ein geschlossener Zustand darf also nicht die positiven Rumpfliterale
eines Constraints enthalten.
Der Durchschnitt zweier geschlossener Zustande ist wieder geschlossen. Zu
einem erweiterten logischen Programm
∩
S
=
∅
gelten, und daher darf die Voraussetzung
pos
(r)
⊆
ohne Default-Negation gibt es also
hochstens einen minimalen geschlossenen Zustand, den wir (im Falle der Existenz)
mit
Cl
(
P
) bezeichnen.
Bei erweiterten logischen Programmen, in denen auch die Default-Negation
auftritt, sind - wie bei Truth Maintenance-Systemen und Default-Theorien - kom-
pliziertere Konstruktionen notwendig. Von zentraler Bedeutung dafur sind gewisse
syntaktische Modifikationen von erweiterten logischen Programmen, die so genann-
ten Redukte, deren Ziel die Elimination der Default-Negation ist.
P
Definition 9.18 (Redukt)
Sei
ein erweitertes logisches Programm mit Regeln
der Form (9.3). Fur einen Zustand S definieren wir das
Redukt
P
S
P
von
P
bzgl.
S
wie folgt:
P
S
:=
{
H
←
A
1
,...,A
n
.
|
H
←
A
1
,...,A
n
,
not
B
1
,...,
not
B
m
.
∈P
,
(9.4)
{
B
1
,...,B
m
}∩
S =
∅}
Diese Reduktion wird nach ihren Erfindern auch
Gelfond-Lifschitz-Reduktion
genannt (siehe [81]). Das Redukt
S
P
entsteht also aus
P
in zwei Schritten:
1. Alle Regeln, deren Rumpf ein
not
B mit B
∈
S enthalt, werden entfernt.
2. In den verbleibenden Regeln werden alle negativen Rumpfliterale (mit den
zugehorigen
not
-Ausdrucken) entfernt.
Damit ist in jedem Fall
S
ein logisches Programm ohne Default-Negation. Be-
achten Sie, dass seine Form entscheidend von dem Zustand S abhangt, auf den
es sich bezieht. In jedem Fall enthalt ein Redukt aber alle Fakten eines logischen
Programms sowie alle Regeln ohne Default-Negation.
P
Beispiel 9.19
Es sei
P
das (normale) logische Programm
P
:
P (a)
←
not
Q(a).
Q(a)
←
not
P (a).
Fur S
1
=
S
1
{
P (a)
}
ist
P
=
{
P (a).
}
,wahrend wir fur S
2
=
{
Q(a)
}
das Programm
S
2
=
P
erhalten.
Fur jedes logische Programm
{
Q(a).
}
P
ergibt sich als Redukt bzgl. der leeren Menge
P
∅
=
{
H
←
A
1
,...,A
n
.
|
H
←
A
1
,...,A
n
,
not
B
1
,...,
not
B
m
.
∈P}
.
