In the early 1990s, the field of non-monotonic reasoning—the study of how artificial intelligence handles "default" assumptions like "birds usually fly"—faced a significant challenge: fragmentation. Researchers had proposed several competing versions of Default Logic, each with its own definitions of consistency and rule application. In their 1993 paper, "A Context-Based Framework for Default Logics," Philippe Besnard and Torsten Schaub addressed this by proposing Contextual Default Logic (CDL), a framework that acts as a universal mediator for these logical dialects.
The Challenge of Logical Consistency
Default logic is essential for AI systems that must make reasonable inferences in the face of incomplete information. However, by 1993, the field had diverged into several variants, most notably Reiter’s classical logic, Lukaszewicz’s justified logic, and Delgrande’s constrained logic.
The primary point of divergence was the treatment of consistency. When applying a default rule (e.g., "if it's a bird, assume it flies"), the system must check if the assumption is consistent with existing knowledge. The "dialects" disagreed on the scope of this check:
- Local Consistency: Checking each rule's justification against the current set of conclusions individually.
- Joint Consistency: Checking if all applied rules and their justifications are consistent with each other simultaneously.
Before Besnard and Schaub's work, these systems were treated as distinct entities. There was no formal way to compare them or to integrate rules from different systems into a single knowledge base.
Contextual Default Logic (CDL)
The authors' solution was to introduce an explicit context ($C$) to the standard logical pair of facts ($W$) and conclusions (the extension, $E$). In this framework, a strict relationship is maintained: $W \subseteq E \subseteq C$.
The core innovation of CDL is a highly generalized default rule format:
$$\frac{\alpha_W | \alpha_E | \alpha_C : \beta_C | \beta_E | \beta_W}{\gamma}$$
Unlike standard default rules that typically feature one prerequisite and one justification, this format allows for six distinct types of conditions. These conditions check the validity of an inference against the facts, the current conclusions, or the broader context. This granularity allows the logic to distinguish between:
- Hard facts (derivable from $W$).
- Default conclusions (derivable from $E$).
- Contextual assumptions (elements belonging to the "sub-contexts" in $C$).
Theoretical Insights and Semantics
Besnard and Schaub identified a Hierarchy of Strength among these application conditions. These range from the strongest (is the condition a proven fact?) to the weakest (is it merely not proven false?). This hierarchy maps directly to the Closed World Assumption (CWA), providing a spectrum of reasoning rigor.
Furthermore, the authors provided a Possible Worlds Semantics using Kripke structures. This offers a geometric way to visualize the relationships between extensions and contexts. They demonstrated that context acts as a "kernel"—a collection of sub-contexts. This explains how certain logics can handle seemingly contradictory justifications by isolating them within different "pockets" of the overall context.
Results and Unification
The power of CDL lies in its ability to simulate other systems. Through a series of formal proofs (Theorems 1, 2, and 3), the authors demonstrated that Classical, Justified, and Constrained default logics are specific subsets of CDL. By adjusting the parameters of the contextual rule, one can perfectly replicate the behavior of any of these major variants.
Beyond simple simulation, CDL offers:
- Expressive Power: The ability to model complex scenarios, such as prioritizing specific defaults or embedding the Closed World Assumption directly within rule sets.
- Iterative Construction: Theorem 5 provides a step-by-step algorithm for building an extension and its context from scratch, ensuring the framework is computationally well-defined.
Limitations and Future Directions
While CDL provides a robust mathematical foundation, the authors noted certain areas for further exploration. Specifically, the condition regarding membership in a context ($\alpha \in C$) was described as "the strangest one," requiring more research to determine its practical utility in real-world AI applications.
Additionally, while the framework is mathematically elegant, the paper does not focus on the computational complexity of calculating these contexts. In non-monotonic reasoning, the "Achilles' heel" is often the high cost of consistency checks. Future work suggested by the authors includes exploring how context-dependency can be used to build sophisticated agents capable of switching reasoning modes based on their environment.
Conclusion
Besnard and Schaub’s Contextual Default Logic succeeded in unifying a fractured field. By making the notion of "context" explicit rather than implicit, they provided a single mathematical language that encompasses the diversity of default reasoning, paving the way for more flexible and integrated AI systems.
Summary updated