Combining Circumscription and Modal Logic

Jacques WainerAAAI 1992

Abstract

This paper introduces LKM (Logic of Knowledge and Minimization), a formal framework designed to bridge the gap between nonmonotonic reasoning—specifically circumscription—and epistemic modal logic. While classical logic is monotonic, real-world reasoning often requires "defaults" that can be retracted upon receiving new information. LKM addresses a critical failure in existing systems: the inability to handle "epistemic cancellations," where a speaker uses modal qualifiers like "perhaps" to explicitly block a default assumption. By extending the semantic definition of circumscription into the modal domain, LKM provides a robust mechanism for reasoning about knowledge and defaults simultaneously.

Introduction

In classical logic, the addition of new premises never invalidates previously held conclusions. However, human reasoning and advanced AI systems often rely on nonmonotonic logic to handle "defaults"—assumptions that are true in the absence of evidence to the contrary (e.g., "If it is a bird, it flies"). Circumscription is a well-established method for formalizing this by "minimizing abnormality."

Despite its utility, circumscription struggles when defaults are nested within a speaker’s knowledge or beliefs. For instance, if a speaker states, "Tweety is a bird," a listener typically concludes the speaker believes Tweety flies. However, if the speaker says, "Tweety is a bird, perhaps a penguin," the default assumption that Tweety flies should be cancelled. Standard methods, which often rely on "internal reasoning"—stripping away the epistemic operators, performing default reasoning, and then reapplying the operators—fail here because the "perhaps" (an epistemic possibility) is lost during the process. This paper proposes LKM to solve this by integrating default reasoning directly into the modal framework.

Methods: The LKM Framework

The author proposes LKM as a semantic extension of circumscription into the modal domain, utilizing S5 (or weak-S5) semantics to model a "perfect reasoner" with full self-awareness of their own knowledge.

1. Worlds as Models

The core innovation of LKM is treating "possible worlds" in modal logic as first-order models. This allows the application of the existing partial-order ($\le$) from circumscription, which ranks models based on their degree of "abnormality." By ranking individual worlds, the system can compare the relative normality of different epistemic possibilities.

2. Model Ordering ($\sqsubseteq$)

The paper defines a new partial order among modal models (sets of possible worlds). A modal model is considered "preferred" if its constituent worlds are "smaller" (less abnormal) or if it contains fewer abnormal possibilities. This allows the logic to prefer states of knowledge that align with the most normal scenarios while still respecting explicit mentions of abnormality.

3. Elementary Improvement

To formalize the transition toward more preferred models, the author introduces the concept of "elementary improvement." This involves swapping an abnormal world for a more "normal" one or removing non-minimal worlds from the set of possibilities, provided such changes do not contradict the agent's explicit knowledge.

4. Rigid Designators

To maintain logical tractability, LKM assumes the use of rigid designators. This means that terms refer to the same objects across all possible worlds within a model, simplifying the cross-world identification of entities during the minimization process.

Key Insights and Results

The "Internal Reasoning" Flaw

A primary contribution of this work is the formal identification of the flaw in "internal reasoning." The paper demonstrates that one cannot separate "what is known" from "how we reason by default." In communication, the two are inextricably linked; the mention of a possibility (epistemic possibility) serves as a constraint on the minimization of abnormality.

Solving the Bird/Penguin Paradox

LKM successfully resolves the paradox of epistemic cancellation. In LKM, the utterance "$b$ is a bird, perhaps a penguin" correctly leads to the conclusion that the speaker does not necessarily believe $b$ flies. Because the "perhaps" introduces a possible world where $b$ is a penguin (and thus abnormal), LKM’s minimization rules respect this explicit possibility rather than discarding it in favor of the default.

Formal Extension

The author provides a mathematical proof sketch showing that LKM is a true extension of first-order nonmonotonic logic. If a standard logic would conclude $\beta$ from $\alpha$, LKM will conclude "the speaker knows $\beta$" from "the speaker knows $\alpha$," provided no epistemic cancellations (like "perhaps $\neg \beta$") are present.

Limitations and Future Work

While LKM represents a significant step forward, it has several limitations:

  • Rigid Designators: The assumption that all terms denote the same object in every world is restrictive, particularly for multi-agent scenarios or when comparing belief to reality.
  • Non-S5 Logics: The framework currently relies on S5 semantics. Extending LKM to other modal logics (such as temporal or conditional logics) is complex, as the relationship between the abnormality order and the accessibility relation between worlds remains undefined.
  • Auto-epistemic Integration: Future research may involve combining LKM with auto-epistemic logic to create more robust models of agent reasoning, potentially allowing for more nuanced self-referential knowledge bases.

Conclusion

LKM provides a rigorous foundation for reasoning about defaults within an epistemic context. By integrating circumscription directly into the semantics of modal logic, it allows AI systems to respect the nuances of human communication, specifically the ability of epistemic possibilities to cancel default assumptions.

Summary updated

BibTeX
@inproceedings{wainer1992combining,
  author = {Jacques Wainer},
  title = {{Combining Circumscription and Modal Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure