Page 118 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes Truth Maintenance Systems can have different characteristics:

Justification-based Truth Maintenance System (JTMS)
It is a simple TMS where one can examine the consequences of the current set of assumptions.
The meaning of sentences is not known.

Assumption-based Truth Maintenance System (ATMS)

It allows to maintain and reason with a number of simultaneous, possibly incompatible, current
sets of assumption. Otherwise it is similar to JTMS, i.e. it does not recognise the meaning of
sentences.
Logical-based Truth Maintenance System (LTMS)

Like JTMS in that it reasons with only one set of current assumptions at a time. More powerful
than JTMS in that it recognises the propositional semantics of sentences, i.e. understands the
relations between p and ~p, p and q and p&q, and so on.
A Justification-based Truth Maintenance System is a simple TMS where one can examine the
consequences of the current set of assumptions. In JTMS, labels are attached to arcs from sentence
nodes to justification nodes. This label is either “+” or “-”. Then, for a justification node we can
talk of its in-list, the list of its inputs with “+” label, and of its out-list, the list of its inputs with
“-” label.
The meaning of sentences is not known. We can have a node representing a sentence p and one
representing ~p and the two will be totally unrelated, unless relations are established between
them by justifications. For example, we can write:
~p^p Contradiction Node
o
|
x 'x' denotes a justification node
/ \ 'o' denotes a sentence node
+/ \+
o o
p ~p
which says that if both p and ~p are IN we have a contradiction.
The association of IN or OUT labels with the nodes in a dependency network defines an in-out-
labeling function. This function is consistent if:

The label of a justification node is IN if the labels of all the sentence nodes in its in-list are
all IN and the labels of all the sentence nodes in its out-list are OUT.
The label of a sentence node is IN if it is a premise, or an enabled assumption node, or it
has an input from a justification node with label IN.
Here are examples of JTMS operations:

create-jtms (node-string contradiction-handler enqueue-procedure) creates a dependency
network. The parameters are:
node-string, a function to be used by the JTMS, which, given a node, returns its
description
contradiction-handler, a function to be invoked by the JTMS when it recognises a
contradiction

enqueue-procedure, a function to be called by the JTMS when it changes the label of
a node to IN.

112 LOVELY PROFESSIONAL UNIVERSITY