AI-Portal Artificial Intelligence for Enthusiasts

Truth Maintainance System

In logics, truth can "change" over time. What I mean with this concept :

Obama is the president of the United States.

In time the truth value of this sentence might change. In 2056 we will probably have it false. During the life of our logic reasoning facts can change from true to false and so forth. The purpose of a Truth Maintainance System is too keep track of the truth values of the sentences, complying with the fact that facts are generated from already existing facts that might change truth value.

For example we know that




In this case we can add to the knowledge base the fact


because P is true and we know that P->Q.

However if later on we need to retract P and assert ~P (eg. P is now false), the truth value for Q is wrong, because it was based on the assertion of P. In this case we have either to rollback all statements that were asserted after asserting P, or recheck them. A truth maintainance system ensures all this.

A simple method of keeping tracks of true and untrue values is keeping a list of IN and OUT facts. Each fact has a list of facts that have to be IN so that the fact itself is IN. This is the IN list. Also each fact has to have a list of facts that are OUT so that the fact is IN. This is called the OUT list.

This method creates a graph of facts each dependent on others, and it''s easy to propagate modifications from leafs ( that are basic assumptions) to the end of the tree to see what states changed.

For example in our P->Q statement, the node is Q, and it''s IN list is P. The OUT list is empty. If P becomes OUT, then Q becomes OUT as well. If we had a statement like P ^ ~R -> Q then the IN list was P and the OUT list was R. Any change in this facts would change Q as well.