Page 101 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 7: Symbolic Reasoning under Uncertainty

7.5.1 Implementations: Truth Maintenance Systems Notes

A multiplicity of Truth Maintenance Systems (TMS) have been generated as a means of executing
Non-Monotonic Reasoning Systems.
Fundamentally Truth Maintenance Systems (TMSs):

 All do some kind of dependency directed backtracking
 Assertions are connected through a network of dependency.

Justification-based Truth Maintenance Systems (JTMS)

 This is a simple TMS such that it does not recognize anything regarding the structure of the
assertions themselves.

 Every supported belief (assertion) in has a explanation.
 Each justification consists of two parts:

 An IN-List — which supports beliefs held.
 An OUT-List — which supports beliefs not held.
 An assertion is associated to its justification via an arrow.
 One assertion can feed a different explanation thus building the network.
 Assertions may be labelled with a belief status.

 An assertion is valid if every declaration in the IN-List is supposed and none in the OUT-
List are believed.
 An declaration is non-monotonic is the OUT-List is not empty or if any declaration in the
IN-List is non-monotonic.

Figure 7.1: A JTMS Assertion
+ IN-List
– OUT-List

David Mellor’s Adultery Supported belief

Justification
+ –

Mistress’s Claim “Ugly” Appearance
Tbry MP
........
Logic-based Truth Maintenance Systems (LTMS)

Logic-based Truth Maintenance Systems (LTMS) is similar to JTMS except:
 Nodes (assertions) presume no relationships between them except ones overtly specified
in justifications.

LOVELY PROFESSIONAL UNIVERSITY 95