Information Technology Reference
In-Depth Information
Proposition 3.3 ((Rass, 2005, Lemma 5.3.4)) . Let
K
be a knowledge-base and C be a minimal and
irreducible conflict-set, and let
C be an axiom involving the literals X , Y 1 ,..., Y n . Then X can be
removed without loosing the minimality or inconsistency if, and only if,
A∈
X
(
rhs
(
C
) \
lhs
(
C
))
lit
( K )
.
Proof. ("if") Let C
= {A
1 ,...,
A
}
be inconsistent, that is B
C
| =
for some consistent
n
background theory B . Without loss of generality, we assume
A 1 : p
(
..., X ,...
)
to be the
axiom that shall be simplified by removing X . Then it is clear that
B
(
C
\ {A 1 } ) ∪ {A 1 } | =
.
(4)
Since the literal X neither appears on the left-hand side of any axiom nor anywhere else in
the knowledge-base, we do not have any specification or information on it. Thus, by the
open-world assumption, equation (4) does especially hold if we assume an arbitrary but fixed
value c for X . Let c be the neutral element for the operator p (which would be false if p
=
or true if p
=
, respectively). By setting X
c we get
B
[(
C
\ {A 1 } ) ∪ {A 1 } ] ∪ {
X
c
} | =
,
which can be rewritten as
B
(
C
\ {A 1 } ) ( {A 1 } ∪ {
X
c
} ) | =
,
being equivalent to
\ { A 1 } ) { A 1 } | =
(
B
C
A 1 being the axiom
A
with
1 having X removed.
} ) A 1 , because removing
A 1 results in the set C
If C is minimal, then so is
(
C
\ {A 1
\ {A 1
}
,
which is consistent due to the minimality of C .
("only if") we show that removing a literal in
(
(
) \
(
))
( K )
=
(
)
(
)
( K )
rhs
C
lhs
C
lit
rhs
C
lhs
C
lit
destroys either the conflict or the minimality: by the construction of an irreducible
decomposition as used in lemma 3.1, the structure graph induced by C is a tree. Assume
the existence of another axiom
A k : X
(
)
C and that the set is still a minimal conflict
after having removed X from the right hand side of
q
...
A
1 . However, if we do so, then the edge
between
A k disappears and the tree breaks up into two non-connected components.
By lemma 3.2, the resulting set is not a minimal conflict any more, thus contradicting our
assumption. Furthermore, we cannot remove any literal L
A 1 and
( K )
, because the construction
employed by lemma 3.1 implies that all axioms having L appear on their right hand side are of
the form Y
lit
L . This does not involve any operator so no further simplification is possible.
Example: for illustrating the last result, take the set of three (inconsistent) rules
= {
X 1
→¬
C
X 2
X 3
X 4 , X 2
B , X 3
B
}
.
They form a minimal conflict set for some axiom decomposition. The literal X 4 appears on
the right-hand sides of C , but not on the left-hand side, since we have lhs
(
)= {
}
C
X 1 , X 2 , X 3
 
Search WWH ::




Custom Search