Horn Belief Change: A Contraction Core
Richard Booth1 Thomas Meyer2
Ivan Varzinczak3 Renata Wassermann4
Abstract. We show that Booth et al.’s Horn contraction based on
infra-remainder sets corresponds exactly to kernel contraction for be-
lief sets. This result is obtained via a detour through Horn contrac-
tion for belief bases, which supports the conjecture that Horn belief
change is best viewed as a “hybrid” version of belief set change and
belief base change. Moreover, the link with base contraction gives us
a more elegant representation result for Horn contraction for belief
sets in which a version of the Core-retainment postulate features.
While there has been some work on revision for Horn clauses [4, 7,
6], it is only recently that attention has been paid to its contraction
counterpart. Delgrande  investigated two classes of contraction
functions for Horn belief sets, viz. e-contraction and i-contraction,
while Booth et al.  subsequently extended Delgrande’s work.
A Horn clause has the form p1 ∧ p2 ∧ . . . ∧ pn → q with n ≥ 0,
and pi, q atoms. A Horn sentence is a conjunction of Horn clauses.
The semantics is the same as for propositional logic, just restricted to
Horn sentences. A Horn base B is a set of Horn sentences. We use
CnHL(X) to denote the set of all consequences of X which are in
the language of Horn sentences. A Horn belief set H is a Horn base
closed under logical consequence (containing only Horn sentences).
Delgrande’s construction method for Horn contraction is in terms
of partial meet contraction . The standard definitions of remainder
sets, selection functions, partial meet contraction, as well as maxi-
choice and full meet contraction all carry over for the Horn case. We
refer to these as e-remainder sets (denoted by H⊥eϕ), e-selection
functions, partial meet e-contraction, maxichoice e-contraction and
full meet e-contraction respectively. As in the full propositional case,
all e-remainder sets are also Horn belief sets, and all partial meet e-