Information Technology Reference
In-Depth Information
We are now prepared to prove general correctness of our entire axiomati-
zation.
Theorem 3.6.2.
Let
(
O; D
)
be a qualication scenario whose axiomatiza-
tion is the prioritized default theory
(
O;D
)
=(
W
(
O;D
)
;D
D
;<
D
)
, then for
each prioritized extension of
(
O;D
)
there exists a corresponding preferred
model of
(
O; D
)
and vice versa.
Proof.
Let
F
ab
be the set of abnormality fluents of
D
.
\
(
":
Let
M
=(
;Res
) be some preferred model of (
O; D
), and let
E
=
Th
(
F
)
be the potential extension corresponding to
M
. To begin with, we prove
that
E
is a standard extension of (
W
(
O;D
)
;D
D
). Let
1.
Γ
0
=
W
(
O;D
)
;
2.
Γ
1
=
Th
(
Γ
0
)
[f!
:
:
!
!
2 D
D
; :! 62 Eg
; and
3.
Γ
2
=
Th
(
Γ
1
).
Then we have to verify that
Γ
2
=
E
(c.f. the proof of Lemma 3.6.1). Clearly,
Γ
2
E
, since for any
:
!
!
2 D
D
such that
! 2 Γ
1
,wehave
:! 62 E
, which
in turn implies
! 2 E
given that
E
is a potential extension. Moreover, the
assumption
Γ
2
E
leads to a contradiction: Suppose
Γ
2
E
, then this
indicates the existence of some
:
!
!
2 D
D
(where
!
=
Initially
(
:f
ab
) for
some
f
ab
2F
ab
) such that
:! 2 E
but
:! 62 Γ
2
. Let
Ω
be the set of all
these
!
, i.e.,
Ω
=
f:! 2 E
:
:! 62 Γ
2
g
. Then
E
0
=(
E n Ω
)
[f!
:
:! 2 Ωg
is an extension of (
W
(
O;D
)
;D
D
). From Lemma 3.6.1 we conclude that
E
0
is
a potential extension of
(
O;D
)
. Let
M
0
be an interpretation corresponding
to
E
0
such that
M
0
is a model of (
O; D
). From the construction of
E
0
and the denition of correspondence it follows that
M
0
contains strictly
less abnormality assumptions than
M
, given that
Ω
is non-empty. Hence,
M
0
M
, which contradicts
M
being a preferred model.
Having proved that
E
is an extension of (
W
(
O;D
)
;D
D
), it remains to be
shown that it is prioritized. Let
D
be an arbitrary strict ordering induced
by
E
. Furthermore, let
E
0
be any extension of (
W
(
O;D
)
;D
D
) and
M
0
be an
interpretation corresponding to
E
0
and which is a model of (
O; D
). Suppose
f
ab
0
2 D
D
is a default which is applied in
E
0
n E
. Then
:f
ab
0
2 Res
0
([ ])
but
f
ab
0
2 Res
([ ]). Model
M
being preferred, we know that
M
0
6 M
.
Therefore, we can also nd some
f
ab
2F
ab
such that
:f
ab
2 Res
([ ]) but
f
ab
2 Res
0
([ ]). It follows that
f
ab
D
f
ab
0
(since
D
is induced by
E
), that
is, there exists a default which is preferred (wrt.
D
)to
f
ab
0
and which is
applied in
E n E
0
.
\
)
":
Let
E
be a prioritized extension of
(
O;D
)
. Then
E
is an extension of
(
W
(
O;D
)
;D
D
) and also, according to Lemma 3.6.1, a potential extension.
Let
M
be an interpretation corresponding to
E
such that
M
is a model
of (
O; D
). By contradiction, we prove that
M
is preferred. Suppose there
