Information Technology Reference
In-Depth Information
Example 2.13
Suppose
is (¬
B
). Then
can be transformed
p
q
)
∧
(¬
B
q
p
as (
B
). Therefore, there are four maximal
sets,
◇
p
∧
q
,
◇
p
∨
q
,
◇
p
and
◇
q
, which might have the O-property. It can be
easily examined that
◇
p
and
◇
q
are the only two sets that have the O-property.
Therefore, there are just two stable expansions for
.
p
∧
B
q
)
∨
(
B
p
∧
p
)
∨
(
B
q
∧
q
)
∨
(
p
∧
q
Finally, we can present a procedure to determine the stable expansions of
basic formulas:
Inputs: a basic formula
.
Initial state: N=0.
Step 1:
Transform
into a disjunctive normal form
' with rank(
')=1;
Let
be the number of disjunctive branches of
';
Set 2
K
= 2
k
, where 2
k
is a set that composed of all the subsets of
k
}.
Step 2:
Repeat the following operation until 2
K
= Ø: take out an element
the set {1,
···
,
k
J
form 2
K
, if
J
has the
O
-property then set
N
=
N
+1.
Outputs:
N
(i.e., the number of stable expansions of
).
2.9 Truth Maintenance System
Truth Maintenance System (TMS) is a problem solver subsystem for recording
and maintaining beliefs in knowledge base (Doyle,1979). The relationship
between TMS and default inference is similar to the relationship between
production system and first-order logic. A truth maintenance system is composed
of two basic operations: a) Make assumptions according to incompleted and
finite informations, and take these assumptions as a part of beliefs; and b) Revise
the current set of beliefs when discoveries contradict these assumptions.
There are two basic data structures in TMS: nodes, which represent beliefs,
and justifications, which represent reasons for beliefs. Some fundamental actions
are supported by the TMS. Firstly, it can create a new node, to which some
statements of a belief will be attached. Secondly, it can add (or retract) a new
justification for a node, to represent a step of an argumrnt for the belief