What's Wrong with Non-Monotonic Logic?

David J. IsraelAAAI 1980

Introduction

In the late 1970s, a movement within Artificial Intelligence research—led by figures such as Doyle, McDermott, and Reiter—argued that classical logic was fundamentally ill-equipped for the demands of intelligent systems. Their primary grievance was the property of monotonicity: in classical logic, if a conclusion follows from a set of premises, adding new premises can never invalidate that conclusion.

Real-world reasoning, however, is clearly "defeasible." We might assume a bird can fly until we learn it is a penguin, at which point we must retract our conclusion. To bridge this gap, researchers proposed "non-monotonic logic" (NML). In his foundational critique, David J. Israel argues that this entire endeavor rests on a category error. He contends that while human reasoning is non-monotonic, logic itself is not—and should not be.

The Category Error: Logic vs. Epistemology

Israel’s central thesis is that the AI community conflated logic (the formal rules of truth-preservation) with epistemology (the management of belief).

Logic, Israel argues, is a tool for determining what must be true if certain premises are true. It is a relation between sentences, not a set of instructions for the mind. He critiques the common misconception of deductive rules like Modus Ponens as "commands." Logic does not force an agent to believe $Q$ just because they believe $P$ and $P \rightarrow Q$; rather, it presents a choice: accept $Q$, or stop believing $P$ or $P \rightarrow Q$. The decision of which belief to keep or discard is a matter of epistemic policy, not a logical requirement.

The Critique of the "M" Operator

To formalize non-monotonicity, NML advocates introduced operators like "M" (read as "it is consistent to assume that..."). This allowed for rules such as: "If $x$ is a bird, and it is consistent to assume $x$ can fly, then $x$ can fly."

Israel attacks this approach on two fronts:

  1. Conceptual Incoherence: By embedding the notion of "consistency with everything else I know" into the logic itself, NML attempts to turn a global state of an agent's knowledge into a local syntactic proof step.
  2. Computational Impossibility: Israel points out the inherent undecidability of this task. Per Church’s Theorem, checking for global consistency in a first-order language is not computable. By trying to make the logic "smarter," NML researchers inadvertently created a system that is theoretically and practically unworkable for an autonomous agent.

The Scientific Method as a Model

Israel suggests that instead of inventing "weird" new logics, AI researchers should look toward the philosophy of science. Science is the quintessential non-monotonic process: scientists hold theories, gather new data, and frequently revise or retract their beliefs. Crucially, they do this while using standard, monotonic logic (mathematics and formal deduction) to derive the consequences of their theories. The "non-monotonicity" resides in the scientific method—the policy for belief revision—not in the underlying logic used to perform the calculations.

Conclusion and Future Directions

Israel’s critique serves as a reminder that the "pessimistic" results of NML—such as its computational complexity and undecidability—are not flaws in the implementation, but direct consequences of trying to treat belief revision as a proof-theoretic problem.

He concludes that "Logic—the logic we have, know, and have every reason to love—is monotonic." The path forward for AI lies not in changing the rules of logic, but in developing "rational epistemic policies." He urges a shift toward understanding how facts are represented and what rules govern "legitimate" (though potentially fallible) conclusions, drawing inspiration from John McCarthy’s work on the epistemological problems of AI. The goal should be to build agents that can navigate a changing world using the stable, reliable tools of classical logic.

Summary updated

BibTeX
@inproceedings{israel1980what,
  author = {David J. Israel},
  title = {{What's Wrong with Non-Monotonic Logic?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure