Nonmonotonic reasoning and commonsense reasoning

Nonmonotonic reasoning is reasoning in which adding new information can remove a conclusion that was drawn before. It formalises how people reason with defaults and exceptions, such as “birds fly, but penguins do not”, and is the logical basis of commonsense reasoning in AI. Classical logic cannot do this, because it is monotonic.

1. Why classical logic is monotonic

Write $\Gamma \models \phi$ when every interpretation that makes all the premises $\Gamma$ true also makes $\phi$ true (see formal systems for the definitions).

Now try to say “birds fly” classically. With $\Gamma =\{\forall x(\mathrm{Bird}\left(x\right)\to \mathrm{Flies}\left(x\right)),\mathrm{Bird}(\mathrm{tweety}\left)\right\}$ we get $\mathrm{Flies}\left(\mathrm{tweety}\right)$. Add $\mathrm{Penguin}\left(\mathrm{tweety}\right)$ and $\forall x\left(\mathrm{Penguin}\right(x)\to \neg \mathrm{Flies}(x\left)\right)$, and by monotonicity $\mathrm{Flies}\left(\mathrm{tweety}\right)$ is still entailed, together with its negation. The premises are now inconsistent, and in classical logic an inconsistent set entails everything. The only classical repair is to list every exception inside the rule (“birds that are not penguins, ostriches, injured, … fly”), which nobody can finish.

A nonmonotonic consequence relation, usually written $|\sim$, drops the property on purpose: $\mathrm{Bird}\left(\mathrm{tweety}\right)|\sim \mathrm{Flies}\left(\mathrm{tweety}\right)$, yet $\mathrm{Bird}\left(\mathrm{tweety}\right),\mathrm{Penguin}\left(\mathrm{tweety}\right)|\sim \neg \mathrm{Flies}\left(\mathrm{tweety}\right)$. Each formalism below is a different way of saying which conclusions are licensed and when they are withdrawn. The same need appears in frames, whose slot defaults can be overridden.

2. Defaults and minimal models

Default logic

Who and when. Raymond Reiter, “A Logic for Default Reasoning”, Artificial Intelligence 13, 1980 [1].

How it works. A default theory is a pair $(W,D)$: $W$ is a set of ordinary first-order facts, and $D$ is a set of default rules of the form prerequisite : justification / conclusion. The rule reads: if the prerequisite is derivable and the justification is consistent with what is believed, conclude the conclusion. “Birds typically fly” in Reiter’s notation:

Tweety. With $W=\left\{\mathrm{Bird}\right(\mathrm{tweety}\left)\right\}$ and $D=\left\{\delta \right\}$, the justification $\mathrm{Flies}\left(\mathrm{tweety}\right)$ is consistent with $W$, so the theory has one extension, the deductive closure of $W\cup \left\{\mathrm{Flies}\right(\mathrm{tweety}\left)\right\}$. Now enlarge the facts:

Now $\neg \mathrm{Flies}\left(\mathrm{tweety}\right)$ follows from the facts, the justification is inconsistent, the default is blocked, and the single extension contains $\neg \mathrm{Flies}\left(\mathrm{tweety}\right)$. More facts, fewer default conclusions: nonmonotonic, with no inconsistency.

Multiple extensions. Conflicting defaults can yield several extensions. In the Nixon diamond, Nixon is a Quaker (Quakers are typically pacifists) and a Republican (Republicans are typically not); there is one extension in which he is a pacifist and one in which he is not. A credulous reasoner accepts what holds in some extension, a skeptical one only what holds in all. Limits. Reasoning is expensive: in the propositional case skeptical entailment is Π₂^P-complete and credulous entailment Σ₂^P-complete, one level above NP.

Circumscription

Who and when. John McCarthy, “Circumscription—A Form of Non-Monotonic Reasoning”, in the same 1980 volume [2].

How it works. Circumscription formalises the assumption that things are as expected unless otherwise specified by keeping only the minimal models of a theory: those in which a chosen predicate is true of as few objects as possible. In McCarthy’s later formulations typicality is expressed with an abnormality predicate:

Circumscribing $\mathrm{Ab}$ makes it true only where the facts force it. With just $\mathrm{Bird}\left(\mathrm{tweety}\right)$, minimal models have $\mathrm{Ab}$ empty, so Tweety flies; add that penguins are abnormal and Tweety is a penguin, and the minimal models change. McCarthy stated it syntactically as a second-order formula. Limits. Choosing what to minimise, what to hold fixed and what may vary is a modelling decision; Vladimir Lifschitz’s extensions with fixed and varying predicates give finer control, and the Yale shooting problem (§5) showed how naive minimisation can go wrong.

Non-monotonic logic (McDermott and Doyle)

Who and when. Drew McDermott and Jon Doyle, “Non-Monotonic Logic I”, also in Artificial Intelligence 13, 1980 [3]. How it works. They added a modal operator $M$, read “is consistent”, so that a default becomes $\mathrm{Bird}\left(x\right)\wedge M\mathrm{Flies}\left(x\right)\to \mathrm{Flies}\left(x\right)$, and defined the theorems as fixed points of a consistency-checking operation. Limits. The semantics of the original logic proved hard to interpret; Moore’s autoepistemic logic grew out of an analysis of it.

Autoepistemic logic

Who and when. Robert C. Moore, “Semantical Considerations on Nonmonotonic Logic”, Artificial Intelligence 25, 1985 [4]. How it works. Moore reads the modal operator $L$ as “I believe”, and treats defaults as reasoning about one’s own beliefs: $\mathrm{Bird}\left(x\right)\wedge \neg L\neg \mathrm{Flies}\left(x\right)\to \mathrm{Flies}\left(x\right)$, “if I do not believe Tweety cannot fly, Tweety flies”. A reasoner’s acceptable belief sets are the stable expansions of its premises $A$, the sets $T$ that satisfy

The logic is nonmonotonic because what a reasoner does not believe changes as its premises grow. Legacy. The stable model semantics of logic programs can be seen as a simplified form of autoepistemic logic (§3).

3. Closed worlds and logic programs

The closed-world assumption

Who and when. Raymond Reiter, “On Closed World Data Bases”, in Logic and Data Bases (Gallaire and Minker, eds., 1978) [5]. What it is. Under the closed-world assumption (CWA) any ground atom that cannot be derived is taken to be false. A flight database that lists no flight from Oslo to Lima is read as saying there is none. Why it is nonmonotonic. Adding the flight retracts the conclusion that there is none. Where it is used. Every relational database answers queries this way. Ontology languages such as OWL deliberately use the open-world assumption instead, where the missing flight is merely unknown. Mixing the two readings is a common source of error.

Negation as failure

Who and when. Keith Clark, “Negation as Failure”, in the same 1978 volume [6]. How it works. In Prolog, \+ G (“not G”) succeeds when every attempt to prove G finitely fails. Tweety as a logic program:

flies(X) :- bird(X), \+ abnormal(X).
abnormal(X) :- penguin(X).
bird(tweety).

The query flies(tweety) succeeds; add penguin(tweety). and it fails. Clark showed that negation as failure is sound with respect to the completion of the program, which reads each predicate’s clauses as an “if and only if” definition. Stable models. In 1988 Michael Gelfond and Vladimir Lifschitz gave programs with negation the stable model semantics [7], the basis of answer set programming. Limits. Negation as failure is not classical negation: \+ G means “G is not provable from this program”, which is only as good as the program’s completeness.

4. Keeping beliefs consistent

Truth maintenance systems

Who and when. Jon Doyle, “A Truth Maintenance System”, Artificial Intelligence 12(3), 1979 [8]. What it is. A truth maintenance system (TMS), later also called a reason maintenance system, is a bookkeeping component that sits beside a problem solver. The solver reports each conclusion together with its justification; the TMS records the resulting dependency network and keeps it consistent. How it works. In Doyle’s design a justification has an in-list (beliefs that must be held) and an out-list (beliefs that must not be held); a node is IN when some justification is valid. When a belief is withdrawn, everything that depended on it is withdrawn too, and when a contradiction appears the TMS traces back to the assumptions responsible, a technique called dependency-directed backtracking. The out-list is what makes the system nonmonotonic: “Tweety flies” is IN while “Tweety is a penguin” is OUT. Today. The same idea, recording why each derived fact holds so that it can be retracted exactly, is what incremental view maintenance in databases and incremental build systems do.

Assumption-based truth maintenance (ATMS)

Who and when. Johan de Kleer, “An Assumption-based TMS”, Artificial Intelligence 28, 1986 [9]. How it works. Instead of maintaining one current set of beliefs, an ATMS labels each derived fact with the minimal sets of assumptions (environments) under which it holds, and records the sets that lead to contradiction as nogoods. All consistent contexts are available at once, so a problem solver can compare alternatives without repeated backtracking. Today. The ATMS became a standard component of model-based diagnosis, where the assumptions are “component c works correctly” and the nogoods point at the candidate faults. Limits. Labels can grow exponentially with the number of assumptions.

Belief revision (AGM)

Who and when. Carlos Alchourrón, Peter Gärdenfors and David Makinson, “On the Logic of Theory Change”, Journal of Symbolic Logic, 1985 [10]. What it is. The AGM theory asks what rational change of a logically closed belief set $K$ looks like. It distinguishes expansion $K+\phi$ (add $\phi$ and close under consequence, without checking consistency), contraction $K-\phi$ (give up $\phi$) and revision $K*\phi$ (add $\phi$ while staying consistent), and states rationality postulates for each. Revision can be built from the other two by the Levi identity:

Belief revision and nonmonotonic inference turn out to be two views of one subject: “$\psi$ follows from $\phi$” can be read as “$\psi$ is in $K*\phi$”, and the AGM postulates translate into postulates for that inference relation.

5. Reasoning about action and change

The frame problem

Who and when. John McCarthy and Patrick Hayes named it in 1969 [11]. What it is. To describe in logic what an action changes, one also has to say what it does not change: painting a block leaves its position, every other block and the weather alone. Writing a separate frame axiom for every action and every unaffected fact is infeasible. Solutions. Nonmonotonic reasoning supplied the general answer: assume by default that things persist unless an action is known to change them (a “law of inertia”). Reiter’s successor-state axioms (1991) give a monotonic encoding of the same idea for the situation calculus, collecting all the ways a fact can change into one axiom per fluent; see the situation calculus and the STRIPS assumption on the planning page. By the late 1980s the technical frame problem was considered solved; the broader philosophical question of how any system decides what is relevant was not.

The Yale shooting problem

Who and when. Steve Hanks and Drew McDermott, “Nonmonotonic Logic and Temporal Projection”, Artificial Intelligence 33(3), 1987 [12]. The scenario. A turkey is alive and a gun is unloaded. The gun is loaded, time passes, the gun is fired at the turkey. Minimising change with circumscription or defaults yields two equally minimal stories: the expected one, where the turkey dies, and an anomalous one, where the gun mysteriously becomes unloaded while waiting and the turkey survives. Each story contains exactly one “abnormal” change, so plain minimisation cannot prefer the right one. Legacy. The problem forced more careful theories of action, including Sandewall’s occlusion, Reiter’s situation calculus with successor-state axioms, and action description languages. The paper received the AAAI Classic Paper Award in 2005.

The event calculus

Who and when. Robert Kowalski and Marek Sergot, “A Logic-based Calculus of Events”, New Generation Computing, 1986 [13]; reformulated in first-order logic with circumscription by Murray Shanahan and Rob Miller in the 1990s. How it works. Time points replace situations. Happens(e, t) says event e occurs at time t; Initiates(e, f, t) and Terminates(e, f, t) say it makes fluent f true or false; HoldsAt(f, t) says f holds at t. The core persistence axiom:

where $\mathrm{Clipped}(t_1,f,t_2)$ means some event terminating $f$ happens in between. The negated $\mathrm{Clipped}$ is read by negation as failure or by circumscription, which is how the event calculus handles the frame problem. Today. Variants run in Prolog and answer set programming and are used in research on narrative understanding and on recognising composite events in data streams.

6. Unifying frameworks

Preferential models and System P

Who and when. Sarit Kraus, Daniel Lehmann and Menachem Magidor, “Nonmonotonic Reasoning, Preferential Models and Cumulative Logics”, Artificial Intelligence, 1990 [14]. What it is. Instead of proposing another logic, KLM asked which properties any reasonable consequence relation $|\sim$ should have. Their System P gives up monotonicity but keeps weaker rules, including cautious monotonicity: a conclusion can be added to the premises without losing other conclusions.

Semantically, $\alpha |\sim \beta$ holds when $\beta$ is true in the most preferred (most normal) models of $\alpha$. This gave the field a common yardstick for comparing formalisms.

Abstract argumentation

Who and when. Phan Minh Dung, “On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games”, Artificial Intelligence 77(2), 1995 [15]. How it works. An argumentation framework is a pair $(A,R)$ of abstract arguments and an attack relation. A set of arguments is admissible if it is conflict-free and defends each of its members against every attacker; the grounded, preferred and stable extensions are different choices of acceptable sets. Dung showed that several nonmonotonic formalisms, including default logic and logic programming under the stable model semantics, can be read as argumentation. Today. Argumentation is used in legal reasoning, explanation and multi-party decision support, because an accepted conclusion comes with the arguments that defend it.

7. Commonsense reasoning

Commonsense reasoning projects

The goal. Commonsense reasoning is the ability to draw the everyday conclusions people take for granted: that a glass dropped on stone probably breaks, that a person in Paris is not simultaneously in Tokyo, that a restaurant customer usually pays. McCarthy set out the programme in “Programs with Common Sense” (1959), proposing to represent such knowledge in logic [16]. Nonmonotonic reasoning exists largely because common sense is made of defaults.

• Cyc (from 1984) set out to hand-encode common sense at scale, with contexts (microtheories) to hold defaults that conflict across situations; see Cyc on the knowledge representation page [17].
• Open Mind Common Sense, begun at the MIT Media Lab in 1999, collected commonsense statements from volunteers on the web; its semantic network, ConceptNet, is still developed.
• The Winograd Schema Challenge (Levesque, Davis and Morgenstern, 2012) tests common sense through pronoun resolution [18]: in “The city councilmen refused the demonstrators a permit because they feared violence”, they is the councilmen; change feared to advocated and it becomes the demonstrators.

Where it stands. Large pretrained language models reached near-human accuracy on the original Winograd schemas by around 2019–2020, and WinoGrande, a larger adversarial version, was built in response [19]. Benchmark accuracy is not the same as a guarantee: a language model revises its answers when the context changes, but nothing states which conclusions it will withdraw or why. The symbolic formalisms on this page give that account exactly, at the cost of someone having to write the defaults.

8. Timeline

9. Where it is used today, and its limits

• Databases and logic programs. Relational databases answer queries under the closed-world assumption, and answer set programming, built on stable models, is used for configuration, scheduling and planning problems with defaults and exceptions.
• Rules with exceptions. Law, regulation and business policy are written as general rules with exceptions and priorities, which is exactly what default logic and argumentation model; see expert systems for the rule engines that run such policies.
• Diagnosis and change. ATMS-style reasoning in model-based diagnosis, and the event calculus for tracking what holds over time.

Limits. Nonmonotonic reasoning is harder than classical reasoning, often a full level higher in the polynomial hierarchy. Multiple extensions force a choice between credulous and skeptical answers. Different formalisms can give different answers on the same example, so the formalism is itself a modelling decision. And all of them presuppose that someone has written the defaults, which returns the problem to the knowledge representation bottleneck. For the historical arc, see the history of symbolic AI; for how this family sits among all symbolic methods, see the symbolic AI techniques hub and the symbolic AI overview.

10. How this connects to fail-safe models

A fail-safe model is an AI model built so that failure drives it to a safe, controlled state: it abstains when evidence is missing, and its learning can narrow what it does but never widen what it is authorised to do. Nonmonotonic reasoning is relevant in two directions. It is the honest account of how conclusions should be withdrawn when new evidence arrives, and a system that can say exactly which conclusions depended on a retracted fact, as a truth maintenance system can, is a system whose mistakes can be traced and undone.

It also warns where not to be clever. A default is a guess that is allowed to stand until contradicted. For facts, a fail-safe design treats what it has not admitted as unknown, the open-world reading, rather than filling the gap with a default; for permissions, it treats what has not been granted as refused, the closed-world reading. Neither gap is filled by a guess. Peel, by Perslis Research, is to our knowledge the first fail-safe model: its knowledge is typed, sourced cards, learning is readable counts, and there is no neural network in the loop that decides. A language model may propose; only the floor admits a fact. Peel is a research prototype, not a certified safety system.

11. Questions

What is nonmonotonic reasoning?

Nonmonotonic reasoning is reasoning in which adding new information can remove a conclusion drawn earlier. From “Tweety is a bird” it concludes that Tweety flies; after learning that Tweety is a penguin it withdraws that conclusion. It formalises reasoning with defaults and exceptions, which classical logic cannot do.

Why is classical logic monotonic?

In classical logic a conclusion follows from premises when it is true in every model of them. Adding premises can only remove models, so anything true in all the old models is still true in all the remaining ones. Once entailed, a conclusion stays entailed whatever is added.

What is default logic?

Default logic, introduced by Raymond Reiter in 1980, adds default rules to first-order logic. A default rule says: if the prerequisite holds and the justification is consistent with what is believed, conclude the conclusion. For example, if x is a bird and it is consistent that x flies, conclude that x flies. The sets of conclusions a default theory supports are called extensions.

What is the difference between default logic and circumscription?

Default logic adds inference rules that fire when their justification is consistent. Circumscription, introduced by John McCarthy in 1980, keeps ordinary logic but restricts attention to minimal models, in which chosen predicates such as “abnormal” are true of as few things as possible. Both let conclusions be withdrawn when facts are added.

What is negation as failure?

Negation as failure is the rule, used in Prolog and other logic programming languages, that “not G” succeeds when every attempt to prove G fails. Keith Clark showed in 1978 that it is sound with respect to the completion of the program. It is nonmonotonic because adding a fact that makes G provable turns “not G” from true to false.

What is a truth maintenance system?

A truth maintenance system, introduced by Jon Doyle in 1979, records why each conclusion of a problem solver is believed and keeps those dependencies consistent. When a belief is withdrawn, everything that depended on it is withdrawn too. Johan de Kleer’s assumption-based variant of 1986 tracks all consistent sets of assumptions at once.

What is the frame problem in AI?

The frame problem, named by McCarthy and Hayes in 1969, is the difficulty of stating in logic what an action does not change without writing an axiom for every unaffected fact. Nonmonotonic reasoning addresses it by assuming that facts persist unless an action is known to change them, and Reiter’s successor-state axioms give a compact monotonic encoding.

What is commonsense reasoning in AI?

Commonsense reasoning is the ability to draw the everyday conclusions people take for granted, such as that a dropped glass may break. McCarthy proposed representing it in logic in 1959. Projects include Cyc, ConceptNet and the Winograd Schema Challenge. Large language models now score well on such benchmarks, but without a stated account of which conclusions they will withdraw or why.

12. References

1. R. Reiter. A Logic for Default Reasoning. Artificial Intelligence 13(1–2):81–132, 1980.
2. J. McCarthy. Circumscription—A Form of Non-Monotonic Reasoning. Artificial Intelligence 13(1–2):27–39, 1980. doi:10.1016/0004-3702(80)90011-9.
3. D. McDermott, J. Doyle. Non-Monotonic Logic I. Artificial Intelligence 13(1–2):41–72, 1980. doi:10.1016/0004-3702(80)90012-0.
4. R. C. Moore. Semantical Considerations on Nonmonotonic Logic. Artificial Intelligence 25(1):75–94, 1985. doi:10.1016/0004-3702(85)90042-6.
5. R. Reiter. On Closed World Data Bases. In H. Gallaire, J. Minker (eds.), Logic and Data Bases. Plenum Press, 1978.
6. K. L. Clark. Negation as Failure. In H. Gallaire, J. Minker (eds.), Logic and Data Bases, 293–322. Plenum Press, 1978.
7. M. Gelfond, V. Lifschitz. The Stable Model Semantics for Logic Programming. Proceedings of the Fifth International Conference on Logic Programming (ICLP), 1070–1080. MIT Press, 1988.
8. J. Doyle. A Truth Maintenance System. Artificial Intelligence 12(3), 1979.
9. J. de Kleer. An Assumption-based TMS. Artificial Intelligence 28:127–162, 1986.
10. C. E. Alchourrón, P. Gärdenfors, D. Makinson. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. Journal of Symbolic Logic 50(2):510–530, 1985.
11. J. McCarthy, P. J. Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. In B. Meltzer, D. Michie (eds.), Machine Intelligence 4, 463–502. Edinburgh University Press, 1969.
12. S. Hanks, D. McDermott. Nonmonotonic Logic and Temporal Projection. Artificial Intelligence 33(3):379–412, 1987.
13. R. Kowalski, M. Sergot. A Logic-based Calculus of Events. New Generation Computing, 1986. doi:10.1007/BF03037383.
14. S. Kraus, D. Lehmann, M. Magidor. Nonmonotonic Reasoning, Preferential Models and Cumulative Logics. Artificial Intelligence, 1990. doi:10.1016/0004-3702(90)90101-5.
15. P. M. Dung. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence 77(2):321–357, 1995.
16. J. McCarthy. Programs with Common Sense. Symposium on Mechanization of Thought Processes, National Physical Laboratory, Teddington, 1959.
17. D. B. Lenat. CYC: A Large-Scale Investment in Knowledge Infrastructure. Communications of the ACM 38(11), 1995.
18. H. J. Levesque, E. Davis, L. Morgenstern. The Winograd Schema Challenge. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), 2012.
19. K. Sakaguchi, R. Le Bras, C. Bhagavatula, Y. Choi. WinoGrande: An Adversarial Winograd Schema Challenge at Scale. Proceedings of AAAI 2020. doi:10.1609/aaai.v34i05.6399. arXiv:1907.10641.