Abstract
In the field of Artificial Intelligence, the ability to reason across different environments and perspectives is crucial for achieving generality. This paper, originally presented at AAAI-93, provides the first formal logical foundation for the concept of "context." By introducing a propositional logic with a specialized modality and context-specific vocabularies, the authors establish a mathematically sound and complete system for contextual reasoning.
Introduction
During the early 1990s, Artificial Intelligence research faced a significant hurdle known as the "lack of generality." Most knowledge representation systems operated under the assumption of a single, global "world" where every fact held a universal truth value. However, human cognition is inherently contextual; a statement may be true in a fictional narrative, a specific historical period, or a particular scientific framework, while being false or even meaningless in another.
John McCarthy proposed the use of "contexts" as a mechanism to overcome this brittleness, a concept notably applied in the Cyc project. Despite its intuitive appeal, the logic of context lacked a rigorous mathematical foundation. This paper addresses that gap by formalizing McCarthy's ideas into a propositional logic, providing the necessary proofs for soundness and completeness.
The Formalism of Context
The authors extend standard propositional logic through two primary innovations: the $ist$ modality and context-specific vocabularies.
The $ist$ Modality
The core of the system is the operator $ist(\kappa, \phi)$, which is read as "it is true in context $\kappa$ that $\phi$." This allows the logic to treat contexts as formal objects within the reasoning process. Unlike standard modal logics where the world is often implicit, this system explicitly references the context $\kappa$.
Context-Specific Vocabularies
A significant departure from classical logic is the treatment of variables. In this framework, each context $\kappa$ possesses its own vocabulary. A proposition might be well-defined and meaningful in one context but "meaningless" (undefined) in another. This reflects real-world scenarios where technical terms or specific entities only exist within certain domains of discourse.
Non-flatness and Nesting
The logic treats contexts as sequences ($\bar{\kappa}$), allowing for "non-flat" or nested perspectives. For instance, one can reason about the context of "19th-century literature" as viewed from the context of "modern literary criticism." This nesting is essential for capturing complex, multi-layered human reasoning.
Semantics and Proof System
The authors model contexts as sets of partial truth assignments. The statement $ist(\kappa, \phi)$ is interpreted as a form of validity: it is true if and only if $\phi$ holds in all possible states associated with the context $\kappa$.
Hilbert-style System
To enable formal reasoning, the paper defines a Hilbert-style proof system. This includes:
- Axioms: Adapted versions of classical axioms, including the K-axiom from modal logic ($ist(\kappa, \phi \to \psi) \to (ist(\kappa, \phi) \to ist(\kappa, \psi))$).
- Inference Rules: Standard rules such as Modus Ponens and Necessitation (if $\phi$ is a theorem, then $ist(\kappa, \phi)$ is a theorem).
The CNF Lemma
A major technical milestone in the paper is the development of a Conjunctive Normal Form (CNF) lemma for contextual logic. The authors demonstrate that any formula within this logic can be reduced to a CNF, which serves as the structural backbone for their completeness proof.
Key Results
The primary contribution of the work is the rigorous proof of Soundness and Completeness. The authors successfully demonstrate that their general system proves only true statements (soundness) and is capable of proving all valid statements (completeness) within the defined semantics.
Furthermore, the paper explores various "flavors" of context by adding specific axioms:
- Flatness: If the sequence of contexts does not change the truth value, the system collapses into something resembling modal systems S4 or S5.
- Consistency: By adding the (D) axiom ($ist(\kappa, \neg \phi) \to \neg ist(\kappa, \phi)$), the system ensures that every context describes at least one possible state of affairs.
Limitations and Future Directions
While providing a landmark foundation, the paper identifies several areas for expansion:
- Quantification: The current system is strictly propositional. A truly general AI requires First-Order Logic to express relations between objects across different contexts.
- Usability: The Hilbert-style system, while mathematically elegant for proofs, is difficult for human use or automated theorem proving. The authors suggest a transition to Natural Deduction systems.
- Complexity: The paper does not provide a computational complexity analysis for deciding validity, leaving the path open for future research into efficient decision procedures.
Conclusion
By formalizing the "logic of context," this paper bridged the gap between intuitive AI concepts and rigorous mathematical logic. It provided the theoretical justification needed for building more general and robust knowledge-based systems, ensuring that contextual reasoning could be performed with mathematical certainty.
Summary updated