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