Information Technology Reference
In-Depth Information
The purpose of Default Logic is to extend classical logic, which is taken to en-
code precise knowledge, by expressions that formalize somehow vague, defeasible
knowledge. Called
default rules
(or
defaults
, for short), these expressions allow
for stating that some property
`normally' implies some property
!
. The ref-
erence to normality is made precise by specifying circumstances
:
which must
provably hold in order that the conclusion from
to
!
shall not be valid. The
formal syntax of a default is
:
!
where
(the
prerequisite
),
(the
justi-
cation
), and
!
(the
consequence
) all are formulas in classical logic. For our
purpose, it suces to consider only so-called normal defaults, where justication
and consequence coincide. In case one or more components of a default contain
free variables, the then so-called open default is considered representative for all
of its ground instances. A
default theory
=(
W; D
) consists of a set of de-
faults
D
and a set of closed formulas
W
, the latter of which is called
world-
(or
background
)
knowledge
. Reasoning in default theories is based on the formation of
so-called extensions. These are obtained by starting with the background knowl-
edge,
W
, and successively applying defaults chosen from
D
, which amounts to
adding their consequences provided their justication is consistent with what is
nally obtained as extension. Once there are no more applicable defaults left, the
deductive closure of the resulting set of formulas constitutes an extension. An
extension may be regarded as one coherent view on the state of aairs. Formally,
let
E
be a set of closed formulas. We dene
1.
Γ
0
=
W
2.
Γ
i
=
:
!
!
Th
(
Γ
i−
1
)
[f!
:
2 D; 2 Γ
i−
1
; :! 62 Eg
, for
i>
0.
(where
Th
(
Ψ
) denotes the (classical) deductive closure of
Ψ
). Then
E
is an
extension
of
i
E
=
S
i
=0
Γ
i
. A default theory may admit multiple extensions,
each of which is obtained by applying dierent subsets of the underlying defaults.
Then a closed formula is said to be
skeptically entailed
in a default theory i it
is contained in all extensions of the latter.
When constructing extensions of a default theory in the way just described, all de-
faults are applied with the same priority. For applications where this is undesired,
an extension of classical Default Logic called
Prioritized Default Logic
supports
the specication of (possibly partial) preference orderings among defaults. This
ordering is exploited to select among the extensions of a default theory those
in which the most preferred defaults have been applied. Formally, a
prioritized
default theory
is a triple
=(
W; D; <
) where
W
and
D
are as in standard
Default Logic and
<
is a partial ordering on
D
.If
E
is a closed set of formulas,
then a default
:
!
!
is said to be
applied in E
i
; ! 2 E
. An extension
E
of
the (standard) default theory (
W; D
)isa
prioritized extension
of
i there
is a strict ordering
extending
<
such that the following holds for all exten-
sions
E
0
of (
W; D
) and all defaults
0
2 D
:If
0
is applied in
E
0
n E
, then
there is some
0
which is applied in
E nE
0
. In words, a standard extension
E
is prioritized if we can nd a strict ordering respecting
<
and the following is
true: Whenever some default
0
is not applied in
E
but in some other standard
extension
E
0
, then there is also a default
which is applied in
E
but not in
E
0
and which has higher priority than
0
according to the strict ordering.
Annotation 3.3.
Classical and Prioritized Default Logic.
