Abstract
This paper presents a sound and complete axiom system for the propositional subset of $O_3L$, a logic that unifies Moore’s Autoepistemic Logic, Konolige’s variant, and Reiter’s Default Logic. By transitioning from meta-logical definitions like "extensions" to a standard proof theory, the authors demonstrate that nonmonotonic reasoning can be formalized as classical theorem proving.
Introduction
In classical logic, a proven theorem remains true regardless of new information. However, "nonmonotonic" reasoning reflects real-world scenarios where new data can invalidate previous conclusions—such as learning that a bird is a penguin and thus cannot fly. Historically, the primary frameworks for this—Moore’s Autoepistemic Logic (AEL), Konolige’s variant, and Reiter’s Default Logic (DL)—relied on "fixed points" or "extensions." These meta-logical constructions are mathematically elegant but lack a standard proof theory, requiring practitioners to check if a conclusion belongs to all possible extensions rather than deriving it directly.
Lakemeyer and Levesque address this by developing a formal axiom system within a monotonic logic called $O_3L$, allowing nonmonotonic conclusions to be derived as standard theorems.
Methodology
The authors build upon the logic of "only knowing" ($OL$) to create a unified framework. Their approach involves several key components:
- Uniform Representation: Defaults are represented by the modal formula $K\alpha \wedge M\beta \supset \gamma$ (if $\alpha$ is known and $\beta$ is consistent, conclude $\gamma$).
- Dual Epistemic States: $O_3L$ utilizes two sets of possible worlds to interpret $K$ (knowledge) and $M$ (consistency) independently. This decoupling is essential for modeling Reiter’s Default Logic, where the standard duality between knowledge and consistency is broken.
- The $N$ Operator: A modal operator $N$ represents an "upper bound" on belief, defining "only knowing" $\alpha$ as knowing $\alpha$ ($K\alpha$) and knowing at most $\alpha$ ($N\neg\alpha$).
- Inductive Reduction: The proof theory employs axioms that systematically "peel off" consistency operators ($M$), reducing complex queries into simpler Moore-style queries.
Key Insights
The paper reveals that the differences between Moore, Konolige, and Reiter are not rooted in the structure of defaults, but in the behavior of the "only knowing" operator. By decoupling $M\beta$ from $\neg K \neg \beta$, $O_3L$ provides a more general framework than standard AEL. This shift moves nonmonotonic inference into the realm of classical theorem proving, bypassing the need for complex meta-arguments about set intersections.
Results and the "Tweety Test"
The primary achievement of this work is the proof of soundness and completeness for the propositional subset of $O_3L$. The authors demonstrate that their system accurately captures the nuances of Reiter’s Default Logic with a relatively simple axiomatization.
To validate the system, the paper provides a formal derivation of the classic "Tweety" problem. The axioms correctly lead to the conclusion that a generic bird flies, while a penguin (Chilly) does not, despite both being birds.
Limitations and Future Work
The current system is restricted to propositional logic. The authors suggest that a complete axiom system for first-order logic is likely impossible due to complexities involving infinite sets of exceptions. Furthermore, while theoretically sound, the current rules can be cumbersome. Future research will focus on developing more computationally efficient versions of these rules and exploring "sufficient" (if incomplete) systems for first-order AI applications.
Summary updated