Nonmonotonic Reasoning

Reasoning in which adding new premises can invalidate previously-derivable conclusions — unlike classical logic, where the consequence relation is monotonic. The standard formalisations are McCarthy’s circumscription (model-theoretic minimisation), Reiter’s Default Logic (defaults as fixed-point operators), Moore’s autoepistemic logic, and — the unifying framework — Dung’s argumentation frameworks under which nonmonotonic logics correspond to extension-acceptance computations.

In this vault

Backlinks

Linked Pages

Closed World Assumption

The inference rule that any ground atom not entailed by the knowledge base is taken to be false. It is the default for logic-programming semantics and is what allows negation-as-failure, but it is unsound for open, distributed knowledge such as the Semantic Web.

In this vault

Abnormality Predicate

McCarthy’s ab(x): a catch-all predicate marking cases where a default rule fails; circumscribing ab enforces ‘all abnormalities have been listed’.

In this vault

Belief Revision

AGM theory of rationally updating a belief set in light of new, possibly contradictory, information — backbone of ontology-change and agent-belief reasoning.

In this vault

Argumentation Framework

Dung’s (1995) abstraction: a directed graph (A, R) whose nodes are arguments and whose edges R ⊆ A × A are attacks. The semantics is content-free — what an argument is is supplied by the instantiating theory — but the family of extensions (Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, complete) is universal. The substrate for ASPIC+, ABA, DeLP, multi-agent dialogue protocols, legal reasoning systems, and (recently) LLM-agent debate.

In this vault

On the Acceptability of Arguments

On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and n-Person Games

Reference: Dung, P. M. (1995). On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2), pp. 321–357. DOI · Open access PDF (CUNY)

Summary

Dung shows that an enormous span of problems in AI — nonmonotonic reasoning, logic programming, n-person game theory — share a single underlying abstraction: a directed graph whose nodes are arguments and whose edges are attacks. He calls this an abstract argumentation framework (AF) and develops, in 30 pages, the entire theory of argument acceptability that has dominated computational argumentation ever since. The headline definitions: a set of arguments is conflict-free if it contains no attacker-attackee pair; admissible if it is conflict-free and defends each of its members against every attacker (an argument is defended if every attacker on it is itself attacked by something in the set); complete if it is admissible and contains every argument it defends; grounded (the unique smallest complete extension), preferred (a maximal admissible set), stable (admissible and attacks every argument outside it). Dung then proves the unifying results: the stable extensions of an AF coincide with the stable models of the corresponding logic program (Gelfond–Lifschitz); preferred extensions correspond to the preferred logic-programming semantics; default-logic extensions arise as stable extensions of an AF derived from default rules; and (the n-person game result) the stable extensions of a game’s argumentation graph correspond to the stable strategies of the game. The framework is content-agnostic — what an “argument” is is left to the instantiating theory — which is precisely what makes it apply across so many domains. Three decades later it is the substrate for legal reasoning systems, multi-agent dialogue protocols, structured argumentation calculi (ASPIC+, ABA, DeLP), and the theoretical underpinning of LLM-agent debate frameworks.

Key Ideas

Argument as a black box, attack as a binary relation: the AF (A, R) with A a set of arguments and R ⊆ A × A is the entire syntactic apparatus. All domain-specific structure (premises, conclusions, defeasible rules) is internalised when the AF is instantiated.
Defence as the operative concept: an argument a is defended by a set S iff every attacker of a is itself attacked by some member of S. Acceptability is “S defends every member of S.”
Family of extensions: admissible (defends itself), complete (admissible + closure), grounded (least complete — sceptical), preferred (maximal admissible — credulous), stable (admissible + attacks everything outside).
Universal correspondences: stable extensions ⇔ stable models of normal logic programs; preferred extensions ⇔ preferred semantics of logic programs; default-logic extensions ⇔ stable extensions of the AF generated by the defaults; the stable extensions of a 2-person game’s defeat graph ⇔ winning strategies.
Inference as fixed-point computation: each semantics is the fixed point of a characteristic operator on 2^A; the order-theoretic structure (complete partial order of admissible sets) makes the theory algorithmically tractable.
Sceptical vs credulous reasoning: every AF supports both — a is sceptically accepted iff in every preferred extension; credulously accepted iff in some preferred extension. The choice is a downstream policy decision.
Why it works as a unifier: nonmonotonic reasoning, default logic, logic programming with negation-as-failure, and game-theoretic equilibria all reduce to “find a coherent set of accepted positions in the presence of mutual challenge” — which is exactly what Dung’s framework computes.

Connections

Conceptual Contribution

Claim: Acceptability of arguments under attack is the abstraction common to nonmonotonic reasoning, logic programming with negation-as-failure, default logic, and equilibrium notions in n-person games. A single, content-free framework — a directed graph of arguments and attacks plus a fixed family of acceptability conditions — captures all of them.
Mechanism: Abstract argumentation framework (A, R); characteristic function F_AF : 2^A → 2^A mapping a set to the arguments it defends; admissible / complete / grounded / preferred / stable extensions defined as fixed points of F_AF under various conditions; instantiation theorems mapping logic-programming and default-logic problems to AFs and proving extension-correspondence.
Concepts introduced/used: Argumentation Framework, Attack Relation, Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, Defence (Argumentation), Sceptical Reasoning, Credulous Reasoning.
Stance: foundational technical paper.
Relates to: Conceptually the missing companion of Circumscription - A Form of Nonmonotonic Reasoning (McCarthy 1980) — both address nonmonotonicity, but Dung gives an argumentation-graph framing that plays directly with logic-programming semantics where circumscription works at the level of model-theoretic minimisation. Provides the formal substrate beneath the dialogue-game tradition: a Persuasion Dialogue (Walton & Krabbe) is operationally a process for constructing the attack edges of a shared AF and computing extensions over it. The structured-argumentation systems (ASPIC+, ABA, DeLP, defeasible logic programming) instantiate Dung’s abstract framework with rule-based languages — and the SPL/Hence defeasible-logic engine used elsewhere in this vault is in this same family. In the LLM-agent era, multi-agent debate / self-consistency protocols recapitulate Dung’s machinery: agents generate arguments, attacks are mined from contradictions, and grounded/preferred extensions correspond to convergent / multi-modal answers. The paper’s reach into n-person games supplies a bridge to the game-theoretic / mechanism-design strands of Pact - A Choreographic Language for Agentic Ecosystems and Deals Among Rational Agents.

In this vault

Circumscription - Applications to Formalizing Common Sense Knowledge

Circumscription — Applications to Formalizing Common Sense Knowledge

Reference: John McCarthy (1986). “Applications of Circumscription to Formalizing Common Sense Knowledge.” Artificial Intelligence 28(1): 89-116. Source file: mccarthy-applications1986.pdf. Sequel to the 1980 paper; see Circumscription - A Form of Nonmonotonic Reasoning for the original formulation and motivation. URL

Summary

The 1986 sequel that supersedes the technical machinery of McCarthy’s 1980 Circumscription paper. Where the 1980 paper introduced predicate and domain circumscription as rules of conjecture for handling the qualification problem, this paper presents a new, more symmetric version — now called formula circumscription — and shows how it, together with a uniform abnormality predicate ab, can formalise a wide range of common-sense reasoning tasks: is-a hierarchies with exceptions, the unique-names hypothesis, the frame problem (via circumscribing abnormality-of-fluents rather than asserting individual frame axioms), and defeasible defaults.

The central methodological move is to express a typical common-sense rule as “normally, P” — formalised as ∀x. ¬ab(aspect₁(x)) ⊃ P(x) — and then circumscribe ab relative to the known facts, with certain other predicates and functions allowed to vary during the minimisation. Allowing predicates other than the one being minimised to vary was the key technical gap in the 1980 formulation; it is what lets circumscription express the frame problem properly (the ab predicate is circumscribed while the fluent values are varied), and what makes prioritised and parallel circumscriptions possible. Birds-fly/Tweety, blocks-on-blocks, and other benchmark examples are worked out in detail.

Alongside Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions, this is the paper that consolidates McCarthy’s logicist programme for common-sense knowledge into a concrete technical agenda: formalise in sorted first-order logic, add concepts-as-individuals where modality is needed, use circumscription (over ab) to handle defaults and the frame problem, and build large reusable common-sense databases. It is the paper cited in the ACL/agent-communication literature whenever “McCarthy on circumscription” is invoked as a foundation for defeasible agent reasoning.

Key Ideas

Formula circumscription generalises predicate circumscription: circumscribe a formula with some predicates and functions allowed to vary.
The abnormality predicate ab provides a uniform idiom: “normally P” becomes ¬ab(aspect(x)) ⊃ P(x), and the formalisation is combined with ab being circumscribed.
Solves the frame problem via circumscribing ab(aspect, action, fluent, situation) while letting the fluents vary — no more individual frame axioms per (action, fluent) pair.
Is-a hierarchies with exceptions: “birds fly except when abnormal”, cancellation of inheritance via ab.
Unique-names hypothesis stated and circumscribed in the same framework.
Prioritised circumscription briefly explored: minimise one abnormality before another.
Supersedes the 1980 paper; references in the literature “to this paper only would better refer to the latter paper in addition or to the latter paper only” (quoting McCarthy on the 1980 paper’s jmc.stanford.edu page).

Connections

Circumscription - A Form of Nonmonotonic Reasoning — the 1980 original, whose formalism this paper supersedes while retaining its motivation.
Programs with Common Sense
Recursive Functions of Symbolic Expressions and Their Computation by Machine
Some Philosophical Problems from the Standpoint of Artificial Intelligence — names the frame problem solved (or at least much reduced) here.
Epistemological Problems of Artificial Intelligence
Ascribing Mental Qualities to Machines
First Order Theories of Individual Concepts and Propositions
Generality in Artificial Intelligence
Towards a Mathematical Science of Computation
Correctness of a Compiler for Arithmetic Expressions
Elephant 2000 - A Programming Language Based on Speech Acts
Common Business Communication Language
Common Sense Reasoning
Knowledge Representation
Non-monotonic Reasoning
Circumscription
Epistemic Logic
The Knowledge Level
The Society of Mind
Formal Verification
Frame Problem

Conceptual Contribution

Claim: Common-sense knowledge — including default rules, is-a hierarchies with exceptions, the unique-names hypothesis, and (most importantly) the frame problem — can be uniformly formalised by expressing “normally P” as ¬ab(aspect) ⊃ P, then circumscribing ab while allowing other relevant predicates and functions to vary. This formula circumscription supersedes the 1980 predicate/domain circumscription.
Mechanism: Formula circumscription schema: given A(P;Q) with P minimised and Q varied, conjoin the second-order sentence stating that no smaller assignment to P (with Q varied accordingly) satisfies A. Reduce A to first-order form in cases where second-order quantifiers can be eliminated. Uniform use of ab(aspectᵢ(x)) to carry all defeasibility. Prioritised circumscription for ordering defaults.
Concepts introduced/used: Formula Circumscription, Abnormality Predicate, Frame Problem, Default Reasoning, Is-a Hierarchy, Unique Names Hypothesis, Prioritised Circumscription, Non-monotonic Reasoning, Circumscription.
Stance: foundational
Relates to: Supersedes Circumscription - A Form of Nonmonotonic Reasoning; provides the defeasibility infrastructure on which Elephant 2000 - A Programming Language Based on Speech Acts and Common Business Communication Language implicitly rely; one of the three McCarthy pillars alongside Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions; technically addresses the frame problem named in Some Philosophical Problems from the Standpoint of Artificial Intelligence and the default-reasoning open problems listed in Epistemological Problems of Artificial Intelligence.

Circumscription - A Form of Nonmonotonic Reasoning

Circumscription — A Form of Non-Monotonic Reasoning (1980)

Reference: John McCarthy (1980). “Circumscription — A Form of Non-Monotonic Reasoning.” Artificial Intelligence 13(1-2): 27-39. The author-hosted PDF (2004 reformatting) adds a 1996 addendum; file is mccarthy-circumscription1980.pdf. Disambiguated from the 1986 sequel Circumscription - Applications to Formalizing Common Sense Knowledge which introduces formula circumscription and the abnormality predicate. URL

Summary

McCarthy’s landmark treatment of the qualification problem: any common-sense rule (e.g. “a rowboat can be used to cross a river”) is subject to an open-ended list of possible defeaters (no oars, a leak, cannibals, a sea monster) that cannot plausibly be enumerated in advance. Standard first-order logic is monotonic — adding premises never removes conclusions — so it cannot support the everyday inference “no defeater mentioned, therefore none present.”

Circumscription is a formally specified rule of conjecture that licenses jumping to the conclusion that the objects (or tuples) shown to satisfy a predicate P are the only ones that do. Adding a sentence “There is a bridge upstream” then legitimately retracts the original conclusion — non-monotonicity is thus built in at the rule-of-conjecture level, not by weakening the logic itself. The paper explains predicate circumscription, shows how domain circumscription (minimal inference) is a special case, works through the missionaries-and-cannibals puzzle to show how circumscription blocks sea-monster-style pedantry, and connects the technique to default reasoning (Reiter), to THNOT in MICROPLANNER (Sussman et al.), and to McCarthy’s broader project of formalising common-sense knowledge in logic.

Together with Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions, this is one of the three pillars of McCarthy’s logicist programme. Its non-monotonic commitment is directly inherited by the CBCL proposal (partial-understanding messages) and by Elephant 2000’s treatment of commitments and speech-act preconditions.

Key Ideas

The qualification problem: common-sense rules have unbounded implicit preconditions that cannot be enumerated.
Monotonicity of FOL is the obstacle; circumscription is a rule of conjecture over FOL, not a modification of its proof theory.
Predicate circumscription: the tuples shown to satisfy P are all the tuples that do.
Domain circumscription (minimal inference) subsumed as a special case.
Non-monotonicity at the level of conjecture rather than entailment — new facts retract conjectures without breaking soundness of FOL.
“Common-sense knowledge must be expressed in a form that says a boat crosses rivers unless something prevents it” — ontology must admit prevention-entities.

Connections

Ascribing Mental Qualities to Machines — philosophical companion; circumscription is the formal tool for the ascriptive logicist programme argued for there.
First Order Theories of Individual Concepts and Propositions — shares the methodology of extending expressive power without abandoning first-order logic.
Common Sense Reasoning
Knowledge Representation
Elephant 2000 - A Programming Language Based on Speech Acts — Elephant’s commitments and speech-act preconditions are governed by defeasible, common-sense rules of exactly the kind circumscription was designed to formalise.
Foundations of Logic Programming - Lloyd — negation-as-failure in logic programming is a close cousin of circumscription.
Common Business Communication Language — CBCL’s ADJECTIVE construct and partial-understanding fallback are predicated on non-monotonic reading.

Conceptual Contribution

Claim: Common-sense reasoning requires non-monotonic inference, and this can be supplied to ordinary first-order logic by a rule of conjecture (circumscription) without modifying the logic itself.
Mechanism: Predicate circumscription schema: from a set of facts A mentioning P, conjecture that the only tuples satisfying P are those whose satisfaction follows from A. Domain circumscription as minimal-model inference. Combination with ordinary FOL rules of inference. Explicit introduction into the ontology of prevention-entities (“something wrong with the boat”).
Concepts introduced/used: Circumscription, Non-monotonic Reasoning, Qualification Problem, Default Reasoning, Minimal Model, Common Sense Reasoning, Rule of Conjecture.
Stance: foundational
Relates to: One of the three McCarthy pillars alongside Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions; provides the defeasibility semantics that Elephant 2000 - A Programming Language Based on Speech Acts needs for commitment revision and Common Business Communication Language needs for partial-understanding messaging.