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
Search WWH ::




Custom Search