Abstract
Standard belief merging techniques often fail when restricted to Horn logic because the merged result may no longer be a Horn formula. This paper addresses this challenge by introducing "Horn-compliant" rankings and a strengthened set of logical postulates. The authors provide the first concrete merging operator guaranteed to remain within the Horn fragment while satisfying all rational requirements, bridging the gap between computational efficiency and logical consistency.
Introduction
In Artificial Intelligence, belief merging is the process of combining multiple, potentially conflicting knowledge bases—sourced from various agents or sensors—into a single, consistent view. While full propositional logic is a common framework, researchers often prefer the Horn fragment. This subset of logic, where rules typically follow the form "if A and B, then C," is computationally more efficient for reasoning and serves as a natural fit for expert systems.
However, Horn logic is "brittle" under standard merging operations. If two Horn knowledge bases are merged using standard methods (such as those based on Hamming distance), the resulting set of "most plausible" worlds might not be representable as a Horn formula. This forces systems out of the efficient Horn fragment and into the computationally expensive domain of full propositional logic.
Methods: Strengthening the Foundations
The authors tackle this problem by revisiting the foundational "IC-merging postulates"—the set of rules that any rational merging operator should follow.
Horn Compliance and Postulate Strengthening
They define a property for rankings (pre-orders) called "Horn compliance." This ensures that the set of minimal (most plausible) elements in a ranking is always closed under intersection, which is the semantic requirement for a formula to be Horn.
The authors argue that standard postulates are too weak for the Horn fragment. They introduce a new postulate, Acyc', to prevent non-transitive cycles in rankings, and reformulate several other postulates ($IC_4, IC_5, IC_6$) to be more restrictive and better suited for Horn logic.
The Summation Assignment
A novel, concrete merging operator is proposed: the "summation assignment." This recursive matrix-based approach generates rankings that are guaranteed to be "well-behaved" and Horn-compliant, even after being aggregated using the sum ($\Sigma$) function.
Key Insights and Results
A major contribution of the paper is a Representation Theorem, which proves a one-to-one correspondence between merging operators satisfying the strengthened postulates and specific types of rankings on possible worlds. To keep the result in the Horn fragment, the ranking of worlds must respect the underlying structure of the logic through "Horn-connectedness."
The authors successfully characterized the class of Horn merging operators and presented the first concrete operator that satisfies all standard merging postulates along with the new requirements. Previous attempts had failed to satisfy at least one of these core "rationality" requirements.
Conclusion and Future Work
While the paper focuses heavily on the "Sum" ($\Sigma$) operator, the authors note that other common aggregation functions, like GMAX (which minimizes the maximum disagreement), remain largely unexplored in the Horn context. Furthermore, the methodology of strengthening postulates could serve as a blueprint for solving merging problems in other logical fragments, such as Krom or dual-Horn logic. Future research will also need to address the computational complexity of constructing the summation assignment as the number of variables increases.
Summary updated