Database Reference
In-Depth Information
a :
¬
b
,δ
2
=
: c
b
Δ=
{
δ
1
=
}
d
wobei
eine tautologische Formel ist (also z.B. a
∨¬
a).
Der Prozess Π
1
=(δ
1
) ist erfolgreich, denn es ist
In
(Π
1
)=
Cn
(
{
a, d
}
)
und
Out
(Π
1
)=
{
b
}
.
Π
1
ist jedoch nicht geschlossen, da δ
2
auf
In
(Π
1
) angewendet werden kann.
Der Prozess Π
2
=(δ
1
,δ
2
) zeigt ein genau entgegengesetztes Verhalten: Hier ist
In
(Π
2
)=
Cn
(
{
a, d, b
}
)
und
Out
(Π
2
)=
{
b,
¬
c
}
.
Π
2
ist also nicht erfolgreich, da
In
(Π
2
) und
Out
(Π
2
)beideb enthalten. Π
2
ist
jedoch geschlossen: Die Defaults δ
1
und δ
2
der Defaultmenge konnen auf
In
(Π
2
)
angewendet werden und kommen auch beide in Π
2
vor.
Ein Prozess, der sowohl erfolgreich als auch geschlossen ist, ist der Prozess
Π
3
=(δ
2
). Damit ist E =
In
(Π
3
)=
Cn
(
{
a, b
}
)eineExtensionvonT .
Uberzeugen Sie sich bitte davon, dass es sich bei allen drei Default-Folgen im
obigen Beispiel auch wirklich um Prozesse handelt!
Selbsttestaufgabe 8.18 (erfolgreiche und geschlossene Prozesse)
Zeigen
Sie, dass Π
3
im obigen Beispiel 8.17 ein erfolgreicher und geschlossener Prozess ist.
Beweis:
(
zu Theorem 8.16
)SeiT =(W, Δ) eine Default-Theorie.
Wir beweisen zunachst, dass wir aus einem geschlossenen und erfolgreichen
Prozess eine Extension erhalten.
Sei Π ein geschlossener und erfolgreicher Prozess von T mit E =
In
(Π). Wir
bestimmen Λ
T
(E).
Nach Definition 8.11 ist
In
(Π) deduktiv abgeschlossen und enthalt die Fakten-
menge W .Damiterfullt E die ersten beiden Bedingungen aus Definition 8.7. Da es
sich bei Π um einen geschlossenen Prozess handelt, ist E auch abgeschlossen bzgl.
der Anwendung von Defaults, erfullt also auch die dritte Bedingung aus Definition
8.7. Da Λ
T
(E) die kleinste solcher Formelmengen ist, gilt Λ
T
(E)
⊆
E.
Um nun noch E
⊆
Λ
T
(E) zu beweisen, zeigen wir mit einem Induktionsbeweis
In
(Π[k])
⊆
Λ
T
(E)
(8.5)
fur alle k.Fur k = 0 ist Π[0] = (), also
In
(Π[0]) =
Cn
(W )
⊆
Λ
T
(E). Nehmen wir
nun an, (8.5) sei bewiesen fur k, und sei δ =
ϕ : ψ
1
,...,ψ
n
χ
der (k+1)-te Default in
Π. Da Π ein Prozess ist, kann δ auf
In
(Π[k]) angewendet werden, insbesondere ist da-
mit ϕ
∈
In
(Π[k])
⊆
Λ
T
(E). Weiterhin sind
¬
ψ
1
,...,
¬
ψ
n
∈
Out
(Π[k+1])
⊆
Out
(Π).
Π ist nach Voraussetzung erfolgreich, daher folgt
¬
ψ
1
,...,
¬
ψ
n
/
∈
In
(Π) = E.Nach
Definition von Λ
T
(E) ist dann auch χ
∈
Λ
T
(E). Zusammen mit der Induktionsvor-
aussetzung (8.5) erhalten wir
