Nonmonotonic reasoning & truth maintenance

Abduction: reasoning backward from effects

Classical inference runs forward: given $P\to Q$ and $P$, conclude $Q$ (modus ponens, sound). Abduction runs the other way — given $P\to Q$ and observed $Q$, conclude $P$ — inferring the most likely cause from an observed effect. It is logically unsound ($Q$ could have other causes) yet indispensable: causes imply effects (a bad battery causes dim lights), but diagnosis must work backward from the dim lights to the battery. Expert systems lean on abductive rules and attach certainty factors precisely because the inference is not deductively guaranteed.

Three assumptions of classical logic that real problems break

Conventional predicate logic quietly assumes:

1. Sufficiency — all knowledge needed to solve the problem is represented. (Fails: diagnosis works with incomplete patient data.)
2. Consistency — no two facts contradict. (Fails: we entertain competing hypotheses at once.)
3. Monotonicity — the set of believed truths only grows as we infer; nothing is ever retracted. (Fails: a new test result can overturn a prior conclusion.)

Nonmonotonic reasoning relaxes all three. It is called defeasible because a previously drawn conclusion can be defeated by later information. The classic device is the ‘unless’ (default) operator: “$p(X)$ unless $\text{abnormal}(X)\to \text{flies}(X)$” captures “birds fly unless they are abnormal.” The conclusion holds as long as $\text{abnormal}(X)$ is not believed; if it later becomes believed, $\text{flies}(X)$ and everything resting on it must be retracted. (Reiter’s default logic generalizes this with rules $A(Z):B(Z)\to C(Z)$ — “if $A$ is provable and $B$ is consistent to assume, conclude $C$” — producing multiple plausible extensions.)

The closed-world assumption

The closed-world assumption (CWA) says: anything not provable from the knowledge base is taken to be false. It is what lets a database answer “no flight at 14:05” by failing to find one, and it is exactly the assumption behind Prolog’s negation as failure. CWA is a form of default reasoning — and it is nonmonotonic, because adding a fact can flip a previous “false” answer to “true.”

Truth-maintenance systems (TMS)

If conclusions can be retracted, the system must know which conclusions depend on which assumptions so it can retract surgically rather than recompute from scratch. A truth-maintenance system records the justification (dependency) of every belief.

• A JTMS (Justification-Based TMS, Doyle 1979) labels each node IN (believed) or OUT (not believed); each justification lists the IN-nodes and OUT-nodes that together support a belief. Its three operations are inspection (“should I believe $p$? what assumptions underlie it?”), modification (add propositions, premises, contradictions), and update (recompute the IN/OUT labels when the network changes). The JTMS is cleanly separated from the problem solver — one TMS design serves theorem provers, expert systems, and planners alike.
• An ATMS (Assumption-Based TMS, deKleer 1984) labels each node with the set of minimal assumption sets under which it holds — representing all possible belief states at once, which is ideal for design and diagnosis (each assumption set is a fault hypothesis), at the cost of potentially exponential bookkeeping.

When a contradiction is found, a TMS performs dependency-directed backtracking: instead of undoing the last $N$ inference steps in order (chronological backtracking), it jumps straight to the assumption responsible and retracts only the conclusions that actually depend on it — often saving most of the work.