Database Reference
In-Depth Information
In
(Π[k +1])=
Cn
(
In
(Π[k])
∪{
χ
}
)
⊆
Λ
T
(E)
also (8.5) fur k +1.
Damit ist insgesamt E =
In
(Π)
Λ
T
(E) und folglich E =Λ
T
(E). E ist also
ein Fixpunkt des Operators Λ
T
und damit Extension von T .
⊆
Nehmen wir nun umgekehrt an, E =Λ
T
(E) sei eine Extension von T . Wir legen
eine beliebige, aber feste Nummerierung der Defaults in Δ fest: Δ =
}
(wobei Δ wie ublich als endlich vorausgesetzt wird). Wir werden im Folgenden einen
Prozess Π von T mit den folgenden Eigenschaften konstruieren:
{
δ
0
,δ
1
,...
(i)
In
(Π[k])
⊆
E
(ii)
Out
(Π[k])
∩
E =
∅
Wir gehen dabei algorithmisch vor und beginnen mit dem leeren Prozess Π[0] = ().
Ausgehend von Π[k] erweitern wir den Prozess in der folgenden Weise:
if
Jeder Default δ
∈
Δ, der anwendbar ist auf
In
(Π[k]) bzgl. E, ist schon in Π[k]
enthalten.
then
Setze Π := Π[k], HALT.
else
Wahle aus den auf
In
(Π[k]) bzgl. E anwendbaren Defaults in Δ denje-
nigen Default δ mit der kleinsten Nummer aus, der nicht bereits in Π[k]
enthalten ist, und setze Π[k +1]:=(Π[k], δ).
Es ist leicht zu sehen, dass der so konstruierte Prozess die obigen beiden Bedin-
gungen erfullt: Jeder hinzugefugte Default δ =
ϕ : ψ
1
,...,ψ
n
χ
ist anwendbar auf
In
(Π[k]) bzgl. E,also
¬
ψ
1
,...,
¬
ψ
n
/
∈
E. Daher ist die Bedingung (ii) erfullt. Wegen
ϕ
E ist δ anwendbar auf E. Als Extension ist E unter der Anwendung
von Defaults abgeschlossen, folglich χ
∈
In
(Π[k])
⊆
E. Dies zeigt (i).
Wir werden nun zeigen, dass fur den fertigen Prozess Π
∈
E =
In
(Π)
gilt. Nach Konstruktion (Eigenschaft (i)) ist
In
(Π)
E =Λ
T
(E). Jede
In
-Menge
eines Prozesses enthalt W und ist deduktiv abgeschlossen, d.h. W
⊆
In
(Π) und
Cn
(
In
(Π)) =
In
(Π). Jeder Default δ,derauf
In
(Π) bzgl. E anwendbar ist, wurde
im Konstruktionsvorgang angesprochen. Damit gehort auch die Konsequenz eines
jeden solchen Defaults zu
In
(Π). Insgesamt erfullt also
In
(Π) alle drei Bedingungen
der Definition 8.7. Wegen der Minimalitat von Λ
T
(E) folgt Λ
T
(E)
⊆
⊆
In
(Π) und
daher, wie gewunscht, E =
In
(Π).
Hieraus ergibt sich nun schließlich auch, dass Π ein erfolgreicher und geschlos-
sener Prozess ist.
Die Suche nach Extensionen zu einer Default-Theorie reduziert sich damit auf
die Bestimmung erfolgreicher und geschlossener Prozesse. Dabei geht man folgen-
dermaßen vor: Ausgehend von der Faktenmenge W wendet man sukzessive anwend-
bare Defaults an und vergroßert so die aktuelle Wissensbasis. Erreicht man dabei
