Information Technology Reference
In-Depth Information
Definition 2.9
A set E of closed formulas is an extension for
∆
=<D, W> iff E is a
fixed point of the operator
Γ
w.r.t.
∆
, i.e., iff
Γ
(E) = E.
Definition 2.10
A formula F can be deduced from a default theory
∆
=<D, W>,
in symbols
∆
|~F, iff F is contained in the extension of
∆
.
Example 2.6
Suppose D={
:
MA
A
} and W=∅. Then the default theory ∆=<D, W>
¬
has no extension.
The result of this example can be demonstrated as follows. Suppose there is a
fixed point E of the operator Γ w.r.t. ∆, then: (a) If ¬A∉E, we will get ¬A∈E
according to the third property of Definition 5.2 and arrive in a contradiction. (b)
If ¬A∈E, then the default rule of D must has been applied in such a way that ¬A
was added into E, therefore it must be ¬A∉E otherwise the rule can not be
applied. So, we arrive in a contradiction again. As a result, there is no fixed point
of the operator Γ w.r.t. ∆, i.e., the default theory ∆=<D, W> has no extension.
Example 2.7
Suppose
:
MA
:
MB
:MC
, W=∅. Then the default theory
D
=
{
,
,
}
¬
B
¬
C
¬
F
∆=<D,W> has a unique extension E=Th({¬B, ¬F}).
For this example, it is easy to demonstrate that E is a fixed point of the
operator Γ w.r.t. ∆. However, for any set S ⊆ {¬B, ¬C, ¬F} except {¬B, ¬F},
we can demonstrate that Th(S) is not a fixed point of Γ w.r.t. ∆.
:
MA
B
:
MC
F
∨
A
C
∧
E
¬
F
∨
A
:ME :MA , M( )
, , ,
:ME :MA , M( )
Example 2.8
Suppose D=
,
{
}
, , ,
A
C
E
G
W = {B, C→F∨A, A∧C→¬E}. Then there are three extensions for the default
theory ∆=<D,W>:
E1=Th(W ∪{A,C})
E2=Th(W ∪{A,E}),
E3=Th(W ∪{C,E,G}).
According to the above example, we can see that not all default theories have
their extensions; at the same time, the number of extensions for a default theory
is not limited to be one. Effective default reasoning on a default theory is based
