Introduction
Historically, the field of nonmonotonic reasoning has relied on "strong" modal logics, such as S5 or KD45, to model the epistemic states of intelligent agents. These systems are built upon the assumption that knowledge ($L$) must satisfy specific axioms, most notably the K axiom: $L(\phi \supset \psi) \supset (L\phi \supset L\psi)$. In their 1993 AAAI paper, "Subnormal Modal Logics for Knowledge Representation," the authors challenge this paradigm, demonstrating that "subnormal" logics—systems that lack even the K axiom—are not only sufficient for knowledge representation but offer unique theoretical advantages.
The Problem: The Burden of Strong Logics
Nonmonotonic logic is essential for "common-sense" reasoning, where agents must draw conclusions based on the absence of information. For instance, an agent might assume it is dry if it does not explicitly know it is raining. While strong modal logics provide a robust mathematical framework, they often introduce counterintuitive results or "collapse" into simpler monotonic systems under certain conditions.
The authors pose a fundamental question: Is the K axiom actually necessary? By moving below the threshold of "normal" modal logic, can we create a more flexible foundation for reasoning that avoids the mathematical baggage of stronger systems?
Defining Subnormal Logics: N and NT
The paper introduces and analyzes two primary subnormal systems:
- Logic $N$: This is the logic of "pure necessitation." It retains standard propositional logic and the rule of necessitation (if $\phi$ is a theorem, then $L\phi$ is a theorem), but it discards all other axioms for the $L$ operator, including K.
- Logic $NT$: An extension of $N$ that incorporates Axiom T ($L\phi \supset \phi$). This axiom ensures that if a proposition is known, it must be true, grounding the agent's knowledge in reality.
To analyze these logics, the authors utilize multi-relational Kripke semantics. Unlike standard Kripke models that use a single accessibility relation, this approach employs an infinite set of relations—one for every possible formula—to define the truth conditions of the modal operator. This is complemented by minimal model semantics, which provides a semantic bridge to the concept of "expansions" (consistent sets of beliefs) in nonmonotonic theories.
Key Insights: The Strength of Weakness
The authors' investigation reveals several surprising properties of these subnormal systems:
1. The Embedding Surprise
Perhaps the most significant finding is that "strong" systems like Moore’s autoepistemic logic can be faithfully simulated within the "weak" logic $N$. By applying a specific translation mapping—specifically replacing every instance of $L\phi$ with $\neg L \neg L \phi$—the authors prove that $N$ can replicate the expressive power of its more complex counterparts.
2. Computational Parity and the U-Shaped Curve
One might assume that a simpler logic would be computationally easier to process. However, the authors demonstrate that nonmonotonic $N$ and $NT$ maintain the same complexity as stronger logics: they are $\Sigma_2^P$-complete on the polynomial hierarchy.
Interestingly, the authors identify a "U-shaped" complexity curve in the monotonic case. Very weak logics (like $N$) and very strong logics (like S5) are relatively "easy" (NP-complete), while "middle-ground" logics (like K or T) are actually more difficult (PSPACE-complete). This justifies the focus on the extremes of the modal spectrum.
3. Conservativity
The authors prove that these logics are "conservative" regarding new definitions. If an agent defines a new term $q$ as equivalent to a formula $\phi$, this definition does not alter the agent's existing knowledge base regarding the original language.
Limitations and Future Directions
Despite their power, subnormal logics have limitations. Because they lack the K axiom, they are not closed under the equivalence substitution rule. This means that one cannot always substitute a formula for a logically equivalent one within the scope of the $L$ operator, which complicates certain algebraic proofs.
Furthermore, this research is confined to propositional modal logic. Extending these subnormal frameworks to first-order logic—incorporating quantifiers like "for all" and "there exists"—remains a significant challenge. Finally, while the theoretical complexity is established, the paper does not offer optimized algorithms for practical implementation in automated reasoning systems.
Conclusion
By stripping modal logic down to its barest essentials, the authors demonstrate that the K axiom is not a prerequisite for sophisticated knowledge representation. Logic $N$ and $NT$ provide a minimalist yet powerful alternative to traditional systems, offering a new perspective on the relationship between the strength of a logic and its utility in modeling common-sense reasoning.
Summary updated