The P-Systems: A Systematic Classification of Logics of Nonmonotonicity

Wolfgang NejdlAAAI 1991

Abstract

In the late 20th century, the field of Artificial Intelligence experienced a proliferation of nonmonotonic logics, including counterfactuals, default reasoning, and belief revision systems. However, these systems were often developed in isolation using disparate formalisms. This paper introduces the "P-Systems," a unified hierarchical framework that classifies these logics by varying a core set of axioms. By manipulating parameters such as plausibility ordering, centering, and absoluteness, the P-System framework provides a common semantic yardstick to compare and unify previously fragmented theories of nonmonotonicity.

Introduction

Nonmonotonic logic is a cornerstone of Artificial Intelligence, designed to model the way humans reason under uncertainty. Unlike classical logic, where adding new premises never invalidates previous conclusions, nonmonotonic systems allow for the retraction of inferences. A classic example is the "Tweety" problem: if we learn Tweety is a bird, we infer he can fly; however, if we subsequently learn Tweety is a penguin, we must retract that conclusion.

By the early 1990s, the landscape of nonmonotonic reasoning was chaotic. Researchers had developed numerous specialized systems—such as David Lewis’s counterfactuals, Kraus, Lehmann, and Magidor’s preferential consequence relations, and Gärdenfors’s belief revision axioms—but lacked a cohesive way to relate them. This work addresses that fragmentation by proposing the P-Systems, a family of logics that demonstrates these disparate theories are actually close relatives within a single logical family tree.

The P-System Framework

The foundation of the P-System is Conditional Logic. Rather than using the standard material implication ($A \supset B$), the framework employs a conditional operator ($A \Rightarrow B$), interpreted as: "In the most plausible worlds where $A$ is true, $B$ is also true."

The hierarchy is constructed by adjusting three primary logical "knobs":

  1. Plausibility Ordering: This defines how possible states or "worlds" are ranked. The system can vary from a simple partial pre-order to a strict linear chain, determining how we compare the likelihood of different scenarios.
  2. Centering: This parameter determines whether the "actual world" holds a privileged status. Strong centering assumes the actual world is always the most plausible one. This is a requirement for counterfactual reasoning (e.g., "If I had taken the train...") but is often omitted in general default reasoning (e.g., "Normally, birds fly"), where the focus is on an idealized normal state rather than the specific current state.
  3. Absoluteness: This refers to whether the plausibility ranking is global (the same from every world's perspective) or local (changing depending on the observer's world).

Mapping the Logical Landscape

The P-System successfully maps several famous but historically separate systems into a single hierarchy, providing a roadmap of equivalences:

  • System P: This represents the minimal preferential consequence relations. It is equivalent to the minimal counterfactual logic $S$ without centering.
  • System $P_C$: By adding the centering axiom, the framework recovers the classic work of Stalnaker and Lewis on counterfactuals.
  • System $P_A$: By adding the absoluteness axiom, the framework aligns with modal logics like $S4$ and specific logics of normality.
  • System $P_{MC}$: This system incorporates "rationality" (linked to the mathematical property of almost-connectedness). It is equivalent to the Gärdenfors rationality axioms for belief revision and Lewis’s $VC$ logic.
  • System $P_{MCX}$: The most restrictive system in the hierarchy, it validates the "conditional excluded middle," asserting that for any $A$ and $B$, either $A \Rightarrow B$ or $A \Rightarrow \neg B$ must be true.

Key Insights

One of the paper's most significant contributions is identifying centering as the primary divider between counterfactual logics and normality logics. While counterfactuals are anchored to the actual world, default reasoning is anchored to an idealized "most normal" world.

Furthermore, the paper simplifies the perceived complexity of these systems for practical AI applications. The author argues that for most AI needs, we primarily deal with "unnested" conditionals—simple if-then statements. In this restricted space, many complex and intimidating logical systems collapse into the same set of manageable rules, making them easier to implement in computational systems.

Limitations and Conclusion

While the P-System provides a robust classification for propositional nonmonotonic logic, it has specific boundaries. The framework focuses heavily on unnested conditionals; while these cover the majority of AI use cases, nested conditionals (e.g., $(A \Rightarrow B) \Rightarrow C$) require more complex "index principles" not fully explored here. Additionally, the current classification is limited to propositional logic, though many of the underlying systems have independent first-order extensions.

By providing a "common axiomatic yardstick," the P-Systems transform a fragmented field into a structured hierarchy. This unification allows researchers to see that many "different" logics are simply variations of the same underlying principles of plausibility and preference.

Summary updated

BibTeX
@inproceedings{nejdl1991p,
  author = {Wolfgang Nejdl},
  title = {{The P-Systems: A Systematic Classification of Logics of Nonmonotonicity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure