Non-monotonic logic

• 1. Introduction

  ›

  Non-monotonic logic begins with a problem that classical reasoning cannot solve: what happens when you have to take back a conclusion you already made? In standard formal logic, adding new information to a set of hypotheses can only expand what you know. It never forces you to erase a conclusion you already reached. Non-monotonic logic was built precisely for the cases where that guarantee breaks down. What kinds of reasoning require the ability to retract? How do you build a formal system that lets a reasoner change its mind? And once you can retract conclusions, how do you stop the whole structure from collapsing into contradiction?

• 2. The Monotonicity Problem

  ›

  Most formal logics share one foundational property: their entailment relations are monotonic. That word means learning something new cannot shrink the set of things you can conclude. Every theorem you have proved stays proved, no matter what facts you add. This sounds reassuring until you meet the tasks it cannot handle. Reasoning by default draws conclusions only because there is no evidence against them; the moment contrary evidence arrives, those conclusions must go. Abductive reasoning treats explanations as tentative best guesses rather than certainties. Reasoning about knowledge runs into trouble because a formula that says something is not known has to be removed the moment that thing becomes known. And belief revision requires throwing out old beliefs to make room for new ones that contradict them. None of these tasks can be modelled by a logic that only ever accumulates conclusions.

• 3. Abduction and the Wet Grass

  ›

  Abductive reasoning is the process of deriving a sufficient explanation for a known set of facts. The classic illustration involves wet grass. If you see wet grass, the most likely explanation is rain. A logic that models explanation should let you conclude it rained. But if you then learn that a sprinkler was running, that explanation has to be retracted in favour of the sprinkler. The old conclusion, that it rained, is withdrawn not because it was disproved outright but because new information arrived. Any logic that models this kind of reasoning is therefore necessarily non-monotonic, because an addition of knowledge caused a removal of a conclusion.

• 4. Knowledge, Belief, and Revision

  ›

  Autoepistemic logic is the formal system designed for reasoning about what a reasoner does and does not know. Its non-monotonic character follows directly from the structure of knowledge formulae. If a system includes a formula stating that some fact is not known, then learning that fact forces the removal of that formula. A removal triggered by an addition is precisely what monotonicity forbids, so the logic must be non-monotonic. Belief revision handles a related but distinct situation. When a new belief conflicts with existing ones, some of the old beliefs must be retracted to restore consistency. The assumption is that the incoming belief is correct, and consistency is the goal. This makes belief revision a different approach from paraconsistent logics, which tolerate inconsistency rather than trying to eliminate it.

• 5. Two Paths to Formalization

  ›

  Logicians have approached the formalization of non-monotonic reasoning along two distinct lines. The proof-theoretic path starts by adopting non-monotonic rules of inference and then specifies the conditions under which those rules can be applied. Fixed-point equations are the typical mechanism for relating sets of premises to their non-monotonic conclusions. Default logic and autoepistemic logic are the two most cited examples built this way. The model-theoretic path begins instead with a standard monotonic logic and restricts its semantics to a special class of models, such as minimal models. Rules of inference are then derived from that restricted semantic base. The resulting system is designed to be sound and complete with respect to those restricted models. Model-theoretic formalizations carried a practical advantage: the proof-theoretic approach had produced well-known paradoxes and was often difficult to evaluate against the intuitions it was supposed to capture. Model-theoretic formalizations were paradox-free, and left little room for confusion about which patterns of reasoning they actually covered. First-order circumscription, the closed-world assumption, and autoepistemic logic are all examples of systems that had proof-theoretic formulations with undesirable properties and were later successfully given model-theoretic treatments.