Anthony J. Bonner
Originally presented at AAAI-88
Abstract
Classical logic serves as the foundation for most early artificial intelligence systems, yet it remains fundamentally ill-equipped to handle hypothetical reasoning. This paper addresses the "what-if" problem: the ability to determine if a conclusion would hold true if a specific fact were added to a knowledge base. By introducing a logic based on embedded implications—a subset of intuitionistic logic—this work provides a mathematically rigorous and computationally practical framework for hypothetical queries that maintains "rulebase independence."
Introduction
A central requirement for intelligent systems is the ability to reason about hypothetical scenarios. A user might ask, "If I were to add fact $X$ to my knowledge base, would $Y$ then be true?" In classical logic, such a statement is typically represented as a material implication ($C \rightarrow B$). However, this representation fails to capture the dynamic nature of adding information to a database. Anthony J. Bonner demonstrates that classical logic cannot express these queries in a way that is independent of the underlying rules, leading to brittle systems that require constant query reformulation as the database evolves.
The Problem of Rulebase Independence
The core issue identified by Bonner is rulebase independence. In a robust AI system, a user should be able to pose a query without needing to know every specific rule currently stored in the database.
For example, consider a query: "Would $C$ become true if we added either $B_1$ or $B_2$?" In classical logic, there is no single expression that can represent this simple hypothetical across all possible rulebases. Bonner provides a formal proof (Theorem 1) showing this impossibility result. If a query must be rewritten every time the internal rules of the system change, the system becomes unusable for non-experts and fails to scale.
Proposed Methodology: Embedded Implications
To resolve these limitations, the paper moves away from classical logic and builds upon Horn-clause logic (the foundation of Prolog) by introducing embedded implications.
Syntax and Framework
The logic introduces rules of the form $A \leftarrow (B \leftarrow C)$. This is interpreted as: "$A$ is true if adding $C$ to the rulebase causes $B$ to be true."
Bonner demonstrates that these rules are a subset of intuitionistic logic. Unlike classical logic, where an implication $(A \rightarrow B)$ is merely a shorthand for $(\neg A \lor B)$, intuitionistic implication has an independent semantic definition that aligns with the "process" of hypothetical addition.
Canonical Kripke Models
To provide a formal semantic basis, Bonner utilizes techniques from modal logic to construct canonical Kripke models. These mathematical structures represent all possible states of the rulebase and the transitions between them as facts are hypothetically added. This allows for a rigorous definition of truth within the system.
Key Insights and Results
The Minimal Substate Property
Horn-clause logic is favored in computer science because it possesses a "unique minimal model"—a single simplest way for facts to be true. Bonner discovers that his hypothetical logic maintains a similar property: a unique minimal substate in its Kripke model. This ensures the logic remains "well-behaved" and consistent with standard logic programming expectations.
The Disjunction Property
The logic satisfies the disjunction property: if the system entails $(A \lor B)$, it must entail either $A$ or $B$ individually. This eliminates the ambiguity often found in classical logic, where a system might know that "A or B" is true without knowing which one is true, thereby making theorem-proving significantly more efficient.
Complexity and Soundness
Bonner proves the soundness and completeness of the proposed inference rules against intuitionistic semantics. Regarding computational cost, query processing in this system is PSPACE-complete for function-free predicates. While more complex than standard database lookups, it remains far more tractable than general automated theorem proving in classical first-order logic.
Conclusion and Future Work
This paper successfully bridges the gap between classical Horn-clauses and intuitionistic logic, providing a formal path for hypothetical reasoning in AI. However, the framework is currently limited to the hypothetical addition of facts. Bonner notes that hypothetical deletion (non-monotonic reasoning) is a significantly harder problem, with complexity jumping to EXPTIME-complete. Future research directions include extending the canonical model approach to full first-order logic with functions and integrating a more robust treatment of formal negation within the intuitionistic framework.
Summary updated