Default Reasoning Using Monotonic Logic: A Modest Proposal

Jane Terry NutterAAAI 1983

This classic paper from the 1983 AAAI proceedings offers a "modest proposal" to a heated debate in early Artificial Intelligence: how should machines reason when they have incomplete information? While the trend at the time was to invent complex "non-monotonic" logics, Jane Terry Nutter argues that we can handle defaults perfectly well by sticking to the virtues of standard, monotonic logic.

TL;DR

Instead of building complex new systems where conclusions are retracted when new facts appear, this paper proposes a simple extension to standard first-order logic. By introducing a "presumably" operator ($p$) and a three-valued semantic model, the author demonstrates that default reasoning can be handled without sacrificing the mathematical stability of monotonicity.

What Problem Does This Paper Address?

In the early 1980s, AI researchers were obsessed with "default reasoning"—the ability to assume something is true unless told otherwise (e.g., "If it's a bird, it flies"). The problem is that standard logic is monotonic: once you prove something is true, it stays true forever, no matter what new premises you add.

If you learn a bird is a penguin, a standard logic system that already concluded "it flies" would hit a contradiction. To solve this, pioneers like McDermott, Doyle, and Reiter developed non-monotonic logics that allowed for the retraction of conclusions. Nutter argues these systems are unnecessarily complex and prone to technical weaknesses. She suggests that the "non-monotonic" nature of human reasoning is an illusion; we don't retract truths, we simply distinguish between "warranted assertions" (facts) and "warranted assumptions" (defaults).

Methods

Nutter proposes an extension to standard first-order predicate logic called LD. The core additions are:

  1. The $p$ Operator: A new unary operator, $p$, which stands for "presumably." For any formula $\phi$, $p\phi$ means "presumably $\phi$."
  2. Grammar Rules: The paper defines how $p$ interacts with standard connectives (AND, OR, NOT) and quantifiers ($\forall, \exists$). For example, "Birds generally fly" becomes $\forall a (Bird(a) \rightarrow p Flies(a))$.
  3. Deductive Rules: Two specific rules are added to a standard natural deduction system:
  4. Inheritance ($rpX$): If you can infer a conclusion from a set of premises, you can infer a "guarded" (presumably) version of that conclusion if the premises themselves are guarded.
  5. Collapsing ($rpE$): Multiple layers of "presumably" (e.g., "presumably, presumably $\phi$") collapse into a single $p\phi$.
  6. Three-Valued Semantics: To make the math work, Nutter uses a Tarskian semantic model where propositions can be True $\{t\}$, False $\{f\}$, or a "newcomer" state $\{t, f\}$. This third state represents something that is "presumably" true but not a hard fact, allowing the logic to remain sound even when defaults are challenged.

Datasets

Not applicable. This is a theoretical paper focused on formal logic and mathematical proofs of soundness.

Key Insights and Ideas

  • Monotonicity is a Virtue: By keeping the logic monotonic, we retain the simplicity and clarity of standard first-order logic. We don't need to "erase" old conclusions; we just need to label them correctly.
  • The "Presumably" Distinction: The "aha moment" is realizing that we don't actually stop believing "birds presumably fly" just because we meet a penguin. We simply learn a more specific fact ("this penguin does not fly") that takes precedence in our decision-making, while the general default remains a valid (if currently inapplicable) assumption.
  • Logic as a Tool, Not a Brain: Nutter emphasizes that logic's job is to determine what is legal to infer, not to resolve every heuristic conflict. Resolving which default to follow when they clash is a matter of "salience" and "heuristics," which should sit on top of the logic, not be baked into its fundamental rules.

Key Results

  • Soundness: The author provides a formal proof that the LD system is sound. It will never permit a false conclusion to be derived from true premises.
  • Expressive Power: The system successfully distinguishes between universals (All men are mortal) and defaults (Birds generally fly), a distinction that was often blurred in other AI reasoning systems of the era.
  • Simplicity: The extension is "trivial" in the sense that it requires very little change to existing logical frameworks, making it easier to implement in systems like SNePS (Semantic Network Processing System).

Limitations and Future Work

  • Conflict Resolution: The paper explicitly notes that this logic does not tell you what to do when two defaults conflict (e.g., "Quakers are pacifists" vs. "Republicans are not pacifists"). It provides the language to state the conflict but leaves the resolution to higher-level heuristics.
  • Philosophical Depth: The author admits the proposal is "modest" and perhaps "shallow" in terms of deep philosophical inquiry into the nature of truth, focusing instead on providing a practical tool for AI engineers.
  • Implementation: While the paper mentions the system is being implemented in SNePS, it does not provide empirical data on performance or efficiency in large-scale knowledge bases.

Summary updated

BibTeX
@inproceedings{nutter1983default,
  author = {Jane Terry Nutter},
  title = {{Default Reasoning Using Monotonic Logic: A Modest Proposal}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure