Abstract
This paper introduces a novel framework for default reasoning that departs from the traditional view of knowledge bases as monolithic sets of formulas. By proposing a "referential level" composed of partially ordered theories, the framework enables natural handling of exceptions, local consistency, and hierarchical knowledge. This approach addresses key challenges in nonmonotonic reasoning, including the "explosion" of classical logic in the presence of contradictions and the computational complexity of reasoning over infinite domains.
Introduction
In the late 1980s, artificial intelligence research faced significant hurdles in formalizing nonmonotonic reasoning—the process where new information can invalidate previous conclusions. Standard systems, such as Reiter’s Default Logic and McCarthy’s Circumscription, often struggled with global consistency. In these systems, a single contradiction could render the entire knowledge base useless. Furthermore, representing hierarchical rules with exceptions required complex predicates, and reasoning over infinite domains often proved undecidable. This paper proposes a structural solution to these issues by redefining how knowledge is organized and interpreted.
The Three-Level Logical Structure
The proposed framework organizes reasoning into three distinct levels:
- Object Level: Contains descriptions of specific, current situations.
- Referential Level ($R$): The core innovation of the paper, consisting of background "defaults" organized as a collection of partially ordered theories.
- Metalevel: Provides rules to filter or eliminate models permitted by the lower levels.
The Referential Level as a Forest
Instead of a flat list of rules, the referential level $R$ is a set of theories where some interpretations are prioritized over others. This structure allows the system to maintain local consistency; an inconsistency in one branch of the hierarchy does not invalidate the entire system. This "forest" of theories allows for a more granular approach to knowledge representation.
To ensure computational tractability, the author adopts the Principle of Finitism, requiring all theories to have finite models. Reasoning proceeds by constructing Partial Models ($PM$) of a formula. By iteratively applying the most plausible defaults from the referential level, the system converges toward Default Models ($DM$), representing the most likely extensions of the initial knowledge.
Key Insights and Theoretical Results
Knowledge Representation
The framework treats a knowledge base as a collection of smaller, internally consistent theories. Nonmonotonicity emerges naturally from the partial ordering of these theories rather than through specialized default rules. This allows for a "coarse-to-subtle" reasoning pipeline, where the system first makes quick assumptions and subsequently refines them as more specific defaults are applied.
Formal Properties
The author establishes several key results for this framework:
- Soundness and Completeness: Every consistent object theory is shown to have an extension within this framework.
- Relationship to Existing Logics: The theory maintains the desirable properties of Reiter’s "normal defaults" while offering greater flexibility in handling exceptions through the hierarchical ordering of theories.
- Provability: The paper formally distinguishes between weak provability (truth in at least one default model) and strong provability (truth in all default models).
Discussion and Limitations
While the framework provides a robust mathematical foundation for common sense reasoning, it faces practical challenges. The Finitism Constraint, while useful for natural language applications, may limit the theory's utility in domains requiring infinite mathematical structures. Additionally, the framework assumes that the partial ordering of defaults is pre-defined; in large-scale industrial applications, establishing the correct plausibility ranking for thousands of conflicting theories remains a significant open problem. Future work is needed to evaluate the scalability of this approach compared to established methods like circumscription.
Summary updated