Reiter's Default Logic in Non-Monotonic AI

This article explores how Raymond Reiter's Default Logic formalizes reasoning with typicality assumptions in artificial intelligence. It provides an overview of non-monotonic reasoning, breaks down the mathematical components of a default theory, and explains how inference rules called defaults allow AI systems to jump to plausible conclusions when facing incomplete information. Finally, it examines how the concept of extensions resolves conflicts and allows AI to revise its beliefs dynamically as new facts emerge.

Traditional classical logic is monotonic, meaning that once a conclusion is drawn, adding new information can never invalidate it. However, human reasoning and real-world artificial intelligence require non-monotonic logic, where conclusions are tentative and can be retracted when new, contradictory evidence appears. In 1980, computer scientist Raymond Reiter introduced Default Logic to mathematically formalize this process, enabling AI to reason using "typicality assumptions"—rules that are generally true but admit exceptions.

To understand how Default Logic operates, one must look at its core structure, known as a Default Theory. A Default Theory consists of a pair, denoted as \((W, D)\):

  • \(W\) (World Knowledge): A set of standard first-order logic formulas representing indisputable facts that are known to be true (e.g., "Tweety is a bird").
  • \(D\) (Default Rules): A set of specialized inference rules that allow the system to make plausible assumptions based on typicality.

A default rule in \(D\) is written in the following format:

\[A : B / C\]

This expression consists of three distinct components that dictate how the AI jumps to a conclusion:

  1. The Prerequisite (\(A\)): What must already be known to be true for the rule to activate.
  2. The Justification (\(B\)): What must be consistent with the current knowledge base. Essentially, there must be no known evidence contradicting \(B\).
  3. The Consequent (\(C\)): The tentative conclusion that the AI adopts if \(A\) is known and \(B\) is consistent.

The classic example in artificial intelligence is the "birds fly" scenario. In Default Logic, the typicality assumption "birds typically fly" is formalized as:

\[\text{Bird}(x) : \text{Flies}(x) / \text{Flies}(x)\]

This reads: If \(x\) is a bird (Prerequisite), and it is consistent to assume that \(x\) can fly (Justification), then conclude that \(x\) flies (Consequent).

If the AI's world knowledge \(W\) contains only the fact that "Tweety is a bird," the prerequisite is met. Because there is no information stating Tweety cannot fly, the justification is consistent with the known facts. The AI successfully applies the default rule and concludes that Tweety flies.

The non-monotonic power of Reiter's logic becomes evident when an exception is introduced. Suppose \(W\) is updated with two new facts: "Tweety is a penguin" and "Penguins do not fly." Using standard logic, the AI deduces directly from \(W\) that Tweety does not fly. Now, when the AI attempts to apply the default rule, the justification (\(\text{Flies}(\text{Tweety})\)) directly contradicts the proven fact that Tweety does not fly. The justification fails the consistency check, the default rule is blocked, and the previous conclusion is retracted.

When an AI system applies all possible default rules to its world knowledge, the resulting set of beliefs is called an Extension. An extension represents a complete, internally consistent worldview derived from the known facts and the maximum number of applicable defaults.

Sometimes, different default rules conflict with one another, leading to multiple possible extensions. A famous example is the "Nixon Diamond," which involves two defaults: "Quakers are typically pacifists" and "Republicans are typically not pacifists." Given the fact that Richard Nixon is both a Quaker and a Republican, Reiter's Default Logic generates two separate extensions:

  • Extension 1: Applies the Quaker default first, concluding Nixon is a pacifist, which subsequently blocks the Republican default.
  • Extension 2: Applies the Republican default first, concluding Nixon is not a pacifist, which subsequently blocks the Quaker default.

In such cases, AI systems use these extensions to reason either credulously (accepting a conclusion if it appears in at least one extension) or skeptically (accepting a conclusion only if it appears in every possible extension). Through the interplay of prerequisites, consistency checks, and extensions, Reiter's Default Logic provides a rigorous, clear mechanism for AI to navigate an uncertain world using common-sense assumptions.