Authors: Zhiqiang Zhuang (College of Intelligence and Computing, Tianjin University, China) Zhe Wang (School of Information Communication Technology, Griffith University, Australia) Kewen Wang (School of Information Communication Technology, Griffith University, Australia) James Delgrande (School of Computing Science, Simon Fraser University, Canada)
Introduction
The Alchourrón, Gärdenfors, and Makinson (AGM) framework is the foundational theory for rational belief change in artificial intelligence. It defines how an agent should update its beliefs when encountering new information that may conflict with its existing knowledge. However, the original AGM framework assumes an underlying logic at least as expressive as classical propositional logic, relying heavily on connectives like negation ($\neg$) and disjunction ($\vee$). This requirement is a significant barrier for many practical AI systems—such as those using Description Logics for the Semantic Web or Horn fragments for logic programming—which intentionally restrict expressivity to maintain computational tractability.
The Problem: Bridging the Gap in Belief Change
Because restricted fragments often lack the connectives assumed by AGM theory, researchers have historically had to develop specialized, "one-off" belief change methods for each specific logic. This paper addresses this fragmentation by proposing a universal approach applicable to any fragment of first-order logic that supports conjunction ($\wedge$), which the authors term First-Order Conjunctive (FC) logic. By generalizing the framework, the authors provide a path for consistent and rational belief updates across a wide variety of restricted logical systems.
Methodology: FC Approximations and Cuts
The authors redefine the core operations of belief change—contraction and revision—without relying on the missing logical connectives. Their framework introduces two key technical innovations:
1. FC Approximations
In standard propositional logic, the contraction of a belief set by $\phi$ often involves the disjunction $\phi \vee \psi$. In an FC logic where such a disjunction may not be expressible, the authors introduce "FC approximations." These are sets of formulas within the fragment that, when taken together, logically entail the intended expression. This allows the agent to approximate the logical behavior of complex connectives using only the simpler syntax available in the fragment.
2. Cuts and Epistemic Entrenchment
The framework utilizes the concept of a "cut"—the set of all beliefs strictly more important (entrenched) than a specific formula. By ranking beliefs by importance, the authors define "FC contraction" based on the agent's preferences rather than purely on logical syntax. A belief $\psi$ is retained when removing $\phi$ only if there is an approximation of $\phi \vee \psi$ that is more important than $\phi$ itself. This shift from syntax-based to preference-based change is a cornerstone of the generalisation.
3. Revision Strategies
The paper explores three methods to derive revision from contraction, based on variants of the Levi Identity:
- Contraction-generated revision: Derived directly from the contraction operator.
- Withdrawal-generated revision: Based on a weaker form of contraction.
- Cut-generated revision: Defined directly through the structure of the entrenchment cuts.
Key Results and Insights
The research yields several significant theoretical contributions:
- Connective Independence: The authors demonstrate that rational belief change does not strictly require negation or disjunction. By using cuts and approximations, the spirit of the AGM framework can be preserved in restricted logics.
- The Recovery Postulate: The paper shows that the controversial "recovery" postulate is often impossible to satisfy in restricted fragments. Their framework remains rational and robust without it, proving that recovery is not a necessary condition for rationality in these contexts.
- Representation Theorems: The authors prove that FC contraction complies with standard AGM rationality postulates (excluding recovery). Furthermore, if the logic contains tautologies, the proposed revision operators satisfy the standard AGM revision postulates.
- Unification: When applied to Horn logic or standard propositional logic, the general framework perfectly matches existing specialized theories, proving its validity as a true generalization.
- Practicality of Cuts: The authors identify "cut-generated revision" as the most promising direction for real-world application, as it avoids the potential computational complexity of finding all possible approximations.
Conclusion and Future Work
This work provides a unified theoretical foundation for belief change in practical, restricted AI systems. While some equivalences between revision methods currently rely on a "finiteness condition" for approximations, the framework offers a clear path for implementing rational belief updates in systems like Description Logic-based ontologies. Future research will focus on providing a complete set of postulates that uniquely characterize FC revision and exploring implementations in large-scale knowledge bases.
Summary updated