Abstract
Belief change in artificial intelligence typically relies on the AGM framework, which assumes full propositional logic. However, many practical systems use Horn logic for its computational tractability. This paper bridges the gap by developing an entrenchment-based contraction method specifically for Horn logic. By utilizing "Horn strengthening" to approximate non-Horn disjunctions, the authors provide a representation theorem that aligns specific contraction functions with a set of rational postulates, ensuring predictable and unique belief updates.
Introduction
In the field of AI, the AGM framework serves as the standard for "belief change"—the formal rules governing how an agent updates its knowledge base. While robust, AGM assumes the use of full Propositional Logic. In practice, many systems (e.g., databases, automated reasoners) employ Horn logic because it is "tractable," allowing for significantly faster computation.
The primary challenge is that Horn logic is less expressive; specifically, it cannot always represent the disjunction (OR) of two formulas. Since standard belief retraction (entrenchment-based contraction) relies on these disjunctions to determine which beliefs to discard, the classical AGM tools fail when applied to Horn-based systems. This paper, published in the Journal of Artificial Intelligence Research, proposes a mathematically rigorous adaptation to resolve this incompatibility.
Methodology: Strengthening and Entrenchment
The authors introduce several key techniques to adapt AGM for Horn logic:
- Horn Strengthening: To handle the inability of Horn logic to represent every disjunction, the authors use "strengthening." This technique identifies the "weakest" Horn formula that implies a non-Horn disjunction, acting as a logical "best fit" approximation.
- Horn Epistemic Entrenchment: The concept of "ranking" belief importance (entrenchment) is redefined specifically for Horn formulas. This ensures that the ranking adheres to the constraints of the restricted logic.
- Horn-Adapted Postulates: A new set of axioms is proposed to govern rational belief change within the Horn fragment.
The figure above illustrates how different entrenchment relations—rankings of formula importance—result in different sets of retained beliefs (shaded areas). This visualization underscores the "uniqueness" property: a specific ranking leads to a unique, predictable contraction result.
Key Insights
The Approximation Workaround
A significant finding is that full propositional logic is not strictly necessary for rational contraction. By substituting "illegal" non-Horn disjunctions with their closest Horn approximations (strengthenings), systems can satisfy nearly all classical requirements for rationality.
The Recovery Problem
The authors acknowledge that Horn logic is intrinsically incompatible with the Recovery postulate—the idea that removing and then re-adding a belief should restore the original knowledge base. This is a known characteristic of weaker logics. Consequently, the authors explore "Withdrawal" operations as a more suitable alternative.
Preservation of Uniqueness
Unlike previous Horn contraction theories where different preference rankings might yield the same result, this method ensures that one ranking leads to exactly one unique contraction. This predictability is vital for the reliable behavior of AI systems.
Theoretical Results
The core of the research is encapsulated in two major theorems:
- Theorem 2 (Representation Theorem): This proves that a contraction function is "entrenchment-based" if and only if it satisfies a specific list of eight Horn-adapted postulates.
- Theorem 3 (Uniqueness): This confirms that every distinct Horn entrenchment ranking produces a distinct contraction function.
Furthermore, the concept of Horn Equivalence demonstrates that this Horn-based method behaves identically to a strict version of classical AGM when restricted to the Horn subset, validating the "approximation" approach.
Conclusion and Future Work
While the loss of the Recovery postulate marks a departure from classical AGM, the proposed framework provides a robust foundation for belief change in tractable logic fragments. Future research aims to generalize the "strengthening" strategy to develop a universal entrenchment-based contraction method applicable to any fragment of propositional logic.
Summary updated