Merging in the Horn Fragment

1 Introduction

Belief merging uses a logical approach to study how information coming from multiple, possibly mutually inconsistent knowledge bases should be combined to form a single, consistent knowledge base. Merging shares a common methodology with other belief change operators, such as revision [Alchourr´on et al., 1985; Katsuno and Mendelzon, 1992], contraction [Alchourr´on et al., 1985] and update [Katsuno and Mendelzon, 1991]. Part of the methodology is the formulation of postulates, which any rational operator should satisfy. For merging, the IC-merging postulates [Konieczny and Pino P´erez, 2002; 2011] are commonly used. In a further step, a representation result is usually derived: this shows that all (merging) operators satisfying the postulates can be characterized using rankings on the possible worlds described by the underlying language, which is typically taken to be full propositional logic.

Recently, the restriction of belief change formalisms to different fragments of propositional logic has become a vivid research branch. There are pragmatic reasons for focusing on fragments, especially Horn logic. Firstly, Horn clauses are a natural way of formulating basic facts and rules, and thus are useful to encode expert knowledge. Second, Horn logic affords very efficient algorithms. Thus the computational cost of reasoning in this fragment is comparatively low.

∗Supported by the Austrian Science Fund (FWF) under grants P25518 and P25521.

While revision [Delgrande and Peppas, 2015; Van De Putte, 2013; Zhuang et al., 2013] and contraction [Booth et al., 2011; Delgrande and Wassermann, 2013; Zhuang and Pagnucco, 2012] have received a lot of attention in this direction, belief merging has yet remained unexplored, with the notable exception of [Creignou et al., 2014]. We aim to fill this gap and investigate the problem of merging in the Horn fragment of propositional logic. We find that restricting the underlying language poses a series of non-trivial challenges, as representation results which work for full propositional logic break down in the Horn case.

Firstly, we find that we cannot rely on the same types of rankings as the ones used for merging in the case of full propositional logic. The reason is that such rankings lead to outputs that can not be expressed as Horn formulas. We fix this problem by adding the restriction of Horn compliance: this narrows down the notion of ranking in a way that is coherent with the semantics of Horn formulas. Since standard merging operators are found not to be Horn compliant (hence useless for our needs), we also give a concrete operator that exhibits this property. This is remarkable, since previous research [Creignou et al., 2014] only resulted in Horn merging operators that do not satisfy all postulates. Secondly, Horn merging operators that satisfy the standard postulates turn out to represent more rankings than was expected, some of which are undesirable. We interpret this as an inadequacy of the standard postulates to capture the intended intuitive behaviour of a merging operator. Hence, we propose an alternative formulation of some key postulates, which allows us to derive an appealing representation result for the case of Horn merging. Our approach here is inspired by existing work on Horn revision [Delgrande and Peppas, 2015], though we go significantly beyond it to tackle the problems posed by merging.

The rest of the paper is organized as follows. In Section 2 we introduce the background to merging. In Section 3 we argue that standard model-based merging operators are inappropriate for Horn merging and introduce the property of Horn compliance. In Section 4 we argue that a subset of the IC-merging postulates should be replaced by a strengthened version, and introduce a representation result using the strengthened postulates. Finally, in Section 5 we describe a concrete Horn merging operator satisfying all postulates. Due to lack of space, we do not include here the proofs of the claims found in the text. These can be found in the full version [Haret et al., 2015].

2 Preliminaries

Propositional logic. We work with the language L of propositional logic over a fixed alphabet P = {p1, . . . , pn} of propositional atoms. We use standard connectives ∨, ∧, ¬ and the logical constants ⊤ and ⊥. A literal is an atom or a negated atom. A clause is a disjunction of literals. A clause is called Horn if at most one of its literals is positive. The Horn fragment LH ⊂ L is the set of all formulas in L that are conjunctions of Horn clauses. An interpretation is a set w ⊆ P of atoms. The set of all interpretations is denoted by W. We will typically represent an interpretation by its corresponding bit-vector of length |P|. As an example, if |P| = 3, then 101 is the interpretation {p1, p3}. A pre-order ≤ on W is a reflexive, transitive binary relation on W. If w1, w2 ∈ W, then w1 < w2 denotes the strict part of ≤, i.e., w1 ≤ w2 but w2 ≰ w1. We write w1 ≈ w2 to abbreviate w1 ≤ w2 and w2 ≤ w1. If M is a set of interpretations, then the set of minimal elements of Mwith respect to ≤ is defined as min≤M = {w1 ∈ M |̸ ∃w2 ∈ Ms.t. w2 < w1}. If interpretation w satisfies formula ϕ, we call w a model of ϕ. We denote the set of models of ϕ by [ϕ]. Given a set M of interpretations, we define Cl∩(M), the closure of M under intersection, as the smallest superset ofMthat is closed under ∩, i.e., if w1,w2 ∈ Cl∩(M) then also w1 ∩ w2 ∈ Cl∩(M). We recall here a classic result concerning Horn formulas and their models (see e.g. [Schaefer, 1978]).

Proposition 1. A set of interpretationsMis the set of models of a Horn formula ϕ if and only if M = Cl∩(M).

A formula is called complete if it has exactly one model. If wi is an interpretation, we sometimes write σwi or σi to denote the complete formula that has wi as a model. If σi and σj are complete formulas, then σi,j is a formula such that [σi,j] = {wi,wj}. If we are working in the Horn fragment, we take σi,j to be such that [σi,j] = Cl∩({wi,wj}).

Belief Merging. A knowledge base is a finite set of propositional formulas. A profile is a non-empty finite multi-set E = {K1, . . . ,Kn} of consistent knowledge bases. Horn knowledge bases and Horn profiles contain only Horn formulas and Horn knowledge bases, respectively. The sets of all knowledge bases, Horn knowledge bases, profiles and Horn profiles are denoted by K, KH, E and EH, respectively. If E1 and E2 are profiles, then E1 ⊔ E2 is the multi-set union of E1 and E2. Interpretation w is a model of knowledge base K if it is a model of every formula in K. Interpretation w is a model of profile E if it is a model of every K ∈ E. We denote by [K] and [E] the set of models of K and E, respectively. We write ∧ E for ∧K∈E ∧ϕ∈K ϕ. This reduces a profile to a single propositional formula. Clearly, [∧ E] = [E].

Profiles E1 and E2 are equivalent, written E1 ≡ E2, if there exists a bijection f : E1 → E2 such that for any K ∈ E1 we have [K] = [f(K)].

Amerging operator is a function ∆: E ×L→K. It maps a profile E and a formula µ, typically referred to as constraint, onto a knowledge base. We write ∆µ(E) instead of ∆(E, µ). As is common in the belief change literature, logical postulates are employed to set out properties which any merging operator ∆ should satisfy. An operator satisfying the following postulates is called IC-merging operator [Konieczny and Pino P´erez, 2002; 2011]:

• (IC1) If µ is consistent, then ∆µ(E) is consistent.
• (IC2) If ∧ E is consistent with µ, then ∆µ(E) ≡ ∧ E ∧µ.

• (IC4) If K1 |= µ and K2 |= µ, then ∆µ({K1,K2}) ∧K1 is consistent iff ∆µ({K1,K2}) ∧K2 is consistent.

It turns out that we can use a particular type of rankings on interpretations to compute the models of a merging operator.

Definition 1. A syncretic assignment is a function mapping each E ∈ E to a pre-order ≤E on W such that, for any E,E1,E2 ∈ E, K1,K2 ∈ K and w1,w2 ∈ W the following conditions hold:

• (s1) If w1 ∈ [E] and w2 ∈ [E], then w1 ≈E w2.

• (s3) If E1 ≡ E2, then ≤E1 =≤E2 .
• (s4) If w1 ∈ [K1], then there is w2 ∈ [K2] such that w2 ≤{K1,K2} w1.
• (s5) If w1 ≤E1 w2 and w1 ≤E2 w2, then w1 ≤E1⊔E2 w2.

We define syncretic assignments in a way that allows the pre-orders ≤E to be partial, as we will make use of partial pre-orders in our own results on Horn operators (Theorems 3 and 4). In the context of full propositional logic, however, the classical result below characterizes all IC-merging operators in terms of syncretic assignments with total pre-orders.

Theorem 1 ([Konieczny and Pino P´erez, 2002; 2011]). A merging operator ∆ is an IC-merging operator if and only if there exists a syncretic assignment mapping each E ∈ E to a total pre-order ≤E such that [∆µ(E)] =min≤E [µ], for any µ ∈ L.

When this equation holds we will say that the assignment represents the operator.

It is useful to think of a profile E = {K1, . . . ,Kn} as a multi-set of agents, represented by their sets of beliefs Ki. Each agent is equipped with a pre-order ≤Ki on W which can be thought of as the way in which the agent ranks possible worlds in terms of their plausibility. Merging is then the task of finding a common ranking that approximates, as best as possible, the individual rankings. Proposition 1 tells us that if this process is done using syncretic assignments, we are in agreement with postulates IC0 - IC8.

Two parts need to be filled out to get a concrete merging operator: how to compute the individual rankings and how to aggregate them. For the first part, the common approach in the literature is to use some notion of distance between interpretations, such as Hamming distance dH or the drastic distance dD. The minimal distance between interpretations and models of Ki is used to construct ≤Ki . For the second part, common functions used to aggregate the distances are the sum Σ or GMAX , giving us operators ∆dH,Σ, ∆dH,GMAX , ∆dD,Σ, ∆dH,GMAX . The reader is referred to [Konieczny and Pino P´erez, 2002; 2011] for more details.

3 Restricting assignments

A Horn merging operator is a function ∆: EH × LH → KH. Our aim is to characterize the class of such operators in the manner of Proposition 1 and to exhibit a concrete operator. The first problem occurs when we apply standard merging operators to Horn profiles and formulas: their output cannot always be represented by a Horn formula.

Examples 1 and 2 show how standard merging operators fail in the Horn fragment. In both cases we choose Horn profiles over the 2-letter alphabet and construct rankings using the Hamming distance and the drastic distance. We then aggregate the rankings with Σ and GMAX . The rankings and the result of their aggregation are shown in Tables 1 and 2. Each row displays one possible interpretation over {p1, p2} (denoted in the first column). The second column displays the minimal distance of the interpretation to any model of K. The third and fourth column show the aggregation of the distances (in our case only one distance) according to the Σ as well as the GMAX function. The output of the merging operator is the set of those interpretations that are models of µ (marked grey) and have the smallest aggregated value.

Example 1. Take K = {p1, p2}, E1 = {K} and µ = ¬p1 ∨ ¬p2 (all of them Horn). We compute ∆dH,Σ µ (E1) and ∆dH ,GMAX µ (E1), keeping in mind that [K] = {11} and [µ] = {00, 10, 01}. Table 1 displays how the output of these two mergings is computed.

We get [∆dH,Σ µ (E1)] = min[µ] = {10, 01}, and the same result is obtained for ∆dH,GMAX µ (E1). It holds, then, that ∆dH,Σ µ (E1) and ∆dH,GMAX µ (E1) cannot be expressed as Horn formulas.

Example 2. Take K1 = {p1, ¬p2}, K2 = {¬p1, p2}, E2 = {K1, K2} and µ = ¬p1 ∨ ¬p2: We get (see Table 2) [∆dD,Σ µ (E2)] = min[µ] = {10, 01}, and the same result is obtained for ∆dD,GMAX µ (E2). Again, ∆dD,Σ µ (E2) and ∆dD,GMAX µ (E2) cannot be represented by Horn formulas.

As we see in Examples 1 and 2, standard distance and aggregate functions are not adequate for the Horn fragment. Here we adopt a solution suggested by [Delgrande and Peppas, 2015], which is to impose an extra condition on the pre-orders.

Definition 2. A pre-order ≤ is Horn compliant if for any µ ∈ LH, min≤[µ] can be represented by a Horn formula.

Example 3. The computed pre-orders for E1 and E2 in Examples 1 and 2 are not Horn compliant, as we get that min[µ] = {01, 10} in both cases.

Adding Horn compliance makes it possible to define a merging operator for the Horn fragment, and this gives us one direction of a representation theorem.

Theorem 2. If there exists a syncretic assignment mapping every E ∈ EH to a Horn compliant total pre-order ≤E, then we can define an operator ∆: EH × LH → KH by taking [∆µ(E)] = min≤E [µ], for any µ ∈ LH, and ∆ satisfies postulates IC0 - IC8.

4 Strengthening the postulates

Conversely, we want to show that for any Horn merging operator ∆ there exists a syncretic assignment which represents it. This is true when the language is not restricted (see Proposition 1), but interesting problems arise as soon as we restrict ourselves to the Horn case.

We know from existing work on Horn revision [Delgrande and Peppas, 2015] that we can find non-syncretic assignments to represent a Horn operator ∆. Such assignments are nonsyncretic in the sense that they contain non-transitive cycles between interpretations. Yet, we can still define an operator on top of these rankings, which satisfies postulates IC0 - IC8. Furthermore, it can be shown that there are no non-cyclic pre-orders that represent the same operator ∆. The solution proposed in [Delgrande and Peppas, 2015] is to add an extra postulate, called Acyc, specifically to eliminate cycles:

Acyc provably follows from postulates IC0 - IC8 in full propositional logic, so it only makes a difference when we restrict the language to the Horn fragment. Here we employ the same strategy of adding an extra postulate to deal with non-transitive cycles, but we propose a postulate formulated in terms of complete formulas:

(Acyc′ ) For any complete formulas σ0, . . . , σn, n ≥ 1 and i ∈ {0, n - 1}, it holds that if σi ∧ ∆σi,i+1 (E) and σn ∧∆σn,0 (E) are all consistent, then σ0 ∧∆σ0,n (E) is also consistent.

There is clearly a strong similarity between Acyc and Acyc′ , though we prefer the latter here for its intuitive appeal. Moreover, it can be shown that they are equivalent modulo the merging postulates.

Proposition 2. Given postulates IC0 - IC8, Acyc and Acyc′ are equivalent.

The intuition behind Acyc′ is that it prevents non-transitive cycles between chains of interpretations of arbitrary length. Suppose n = 2 and the antecedent of Acyc′ is true: then from the fact that σ0∧∆σ0,1 (E) is consistent we conclude that w0 ∈ [∆σ0,1 (E)], where [σi] = {wi}. This means that w0 is among the models of σ0,1 that are 'preferred', or considered more plausible, by ∆. Thus, in the pre-order ≤E that represents ∆, it should hold that w0 ≤E w1. By the same token, we get that w1 ≤E w2 ≤E w0 should hold. Since we want ≤E to be transitive, it should also hold that w0 ≤E w2, and this is exactly what Acyc′ requires at this point. Thus, we need the extra postulate Acyc′ (or something equivalent) to ensure that the pre-orders representing a given Horn merging operator ∆ preserve intuitive properties such as (in this case) transitivity.

Introducing Acyc′ is not enough, as one can still find assignments that represent a Horn merging operator ∆ without being syncretic, this time because they do not satisfy properties s4 - s6. The following examples make this clearer.

Example 4. Consider Horn knowledge bases [K1] = {01}, [K2] = {10} and an assignment that works as in Figure 1 when restricted to K1 and K2. Figure 1 shows the rankings associated with K1 and K2 and the result of merging them into the new ranking ≤{K1,K2}. 1 Notice that s4 is not true: s4 requires that 01 ≈{K1,K2} 10, whereas we have 01 <{K1,K2} 10. However, we can define a (Horn) merging operator ∆ on top of this assignment in the usual way, by taking [∆µ(E)] = min≤E [µ], for any Horn formula µ, and ∆ will satisfy postulates IC0 - IC8 + Acyc′ . This can be verified by direct inspection; we focus here only on IC4. The problematic interpretations are the models 01 and 10 of K1 and K2, respectively. Notice that there is no Horn formula that represents exactly the set {01, 10}: the best we can do is take a Horn formula µ such that [µ] = [σ01,10] = {00, 01, 10}. Obviously, K1 |= µ and K2 |= µ, so we are in the range of application of IC4. We have that [∆µ({K1,K2})] = {00}, and [∆µ({K1, K2}) ∧K1] = [∆µ({K1, K2}) ∧K2] = ∅, so IC4 is satisfied for this particular µ.

1 It is worth noting that ≤K1 , ≤K2 and ≤{K1,K2} are not generated using any familiar notion of distance-the rankings were hand-picked.

Example 4 is significant because it shows that an assignment which does not satisfy s4 may still represent an operator ∆ obeying IC4. And given the standard formulation of IC4, this turns out to be unavoidable.

Proposition 3. There is no syncretic assignment representing ∆ from Example 4 that assigns to {K1, K2} a pre-order ≤⋆{K1,K2} where 01 ≈⋆{K1,K2} 10.

Proof. Suppose 01 ≈⋆{K1,K2} 10. From Figure 1 we know that [∆σ10,11 ({K1,K2})] = {11}, hence min≤⋆{10, 11} = {11} and thus 11 <⋆{K1,K2} 10. Similarly, we obtain 01 ≈⋆{K1,K2} 11, which implies 01 <⋆{K1,K2} 10. This creates a contradiction.

The following example shows how s5 fails to be enforced by IC5 in the case of Horn logic.

Example 5. Assume there exists an assignment which for two profiles E1 and E2 behaves as in Figure 2, and is otherwise Horn compliant and syncretic. Property s5 does not hold: 010 ≈E1 100 and 010 ≈E2 100, but 010 <E1⊔E2 100. However, as in Example 4, we can define a (Horn) merging operator ∆ on top of this assignment and ∆ will satisfy postulates IC0 - IC8 + Acyc′ . Let us check that IC5 holds. The problematic interpretations here are 010 and 100 (for which s5 does not hold). In this case we have that ∆σ010,100 (E1) ∧ ∆σ010,100 (E2) is consistent, and

[∆σ010,100 (E1) ∧ ∆σ010,100 (E2)] = [∆σ010,100 (E1 ⊔ E2)] = {000}. This shows that for the case we are interested in (µ = σ010,100) IC5 is true.

Similarly as for IC4, we can show that such a counterexample to s5 is unavoidable.

It is perhaps surprising to see that IC5 can be satisfied in an assignment where s5 does not hold, but closer thought shows this is to be expected: since in the Horn fragment we cannot represent the set {100, 010} with a formula, it becomes harder to control the order in which 100 and 010 appear. Without any additional constraints on ∆, one cannot prevent it from varying the order of 100 and 010 in ways that directly contradict s5. Similar counter-examples can be constructed for s6.

Examples 4 and 5 show that a syncretic assignment with total pre-orders is not the most natural way to represent a Horn merging operator. Hence, we introduce the following notion.

Definition 3. A pre-order ≤ on W is Horn connected if

• (h1) ≤ is Horn compliant,
• (h2) any wi,wj ∈W that are in the subset relation are in ≤, and
• (h3) for any wi,wj ∈W such that wi ⊈ wj and wj ⊈ wi, it holds that if wi ≤ wj then:

• (h3.2) for some n > 2, there exist pair-wise distinct interpretations w1, . . . ,wn, such that w1 = wi, wn = wj and w1 ≤ · · · ≤ wn.

A Horn connected pre-order ≤E is not necessarily total. Example 6 illustrates this.

Example 6. Consider the following pre-orders on the 2-letter alphabet: (a) 11 <1 01 <1 10 <1 00, (b) 00 <2 01 <2 11 <2 10, (c) 00 <3 01 <3 11, 00 <3 10 <3 11, 01 ≰3 10 10 ≰3 01, (d) 00 <4 01 ≈4 10 <4 11. It is immediately visible that all pre-orders are Horn compliant (h1) and that they satisfy h2. Let us focus on interpretations 01 and 10.

In ≤1 we have 01 ∈ min≤Cl∩({01, 10}). Thus h3.1 is satisfied, and ≤1 is Horn connected. In ≤2 we do not have 01 ∈ min≤Cl∩({01, 10}), but there is interpretation 11 such that 01 < 11 < 10. Thus h3.2 is satisfied and ≤2 is Horn connected. Pre-order ≤3 is partial, as 01 and 10 are not in ≤3, and thus h3 is vacuously true. In ≤4 we have 01 ≈ 10 though none of h3.1 and h3.2 holds, thus ≤4 is not Horn connected.

Next, for every Horn operator ∆ and Horn profile E, we define a (partial) pre-order on complete formulas of LH. 2

Definition 4. Given a Horn operator ∆, then for any Horn profile E and complete Horn formulas σi, σj, we say that σi ⪯E σj if there exist complete Horn formulas σ1, . . . , σn such that σ1 = σi, σn = σj, and for i ∈ {1, n - 1}, σi ∧ ∆σi,i+1 (E) are all consistent.

It is straightforward to check that ⪯E is reflexive and transitive, and thus a pre-order on complete Horn formulas. We write ≺E for the strict part of ⪯E. It is also worth noting that ⪯E is total when the underlying language is full propositional logic, since [σi,j] = {wi, wj} and we can take the sequence σ1, . . . , σn to be just σi, σj or σj, σi. This does not necessarily hold in the case of the Horn fragment, where ⪯E can be partial.

2 The pre-order ⪯E is not to be confused with the pre-order ≤E on interpretations, though it is meant to mirror it.

We now reformulate IC4, IC5 and IC6 for K1,K2 ∈ KH,

E1, E2 ∈ EH and complete Horn formulas σi, σj as follows: (IC′4 ) For any σi |= K1, there exists σj |= K2 such that

These postulates make a difference only in the Horn fragment, while in full propositional logic they are redundant.

Proposition 4. In the case of full propositional logic, IC′4 , IC′5 and IC′6 follow from the standard IC0 - IC8 postulates.

With postulates IC′4 , IC′5 and IC′6 we can derive a representation result for syncretic assignments with Horn connected pre-orders. The result is split across two theorems: Theorem 3 shows that Horn connected pre-orders can be used to construct a Horn merging operator satisfying our amended set of postulates. Its converse, Theorem 4, shows that any Horn merging operator satisfying the amended postulates is represented by a syncretic assignment with Horn connected pre-orders.

Theorem 3. If there exists a syncretic assignment mapping every E ∈ EH to a Horn connected total pre-order ≤E, then we can define an operator ∆: EH × LH → KH by taking [∆µ(E)] = min≤E [µ], for any µ ∈ LH, and ∆ satisfies postulates IC0 - IC3 + IC′4 + IC′5 + IC′6 + IC7 - IC8 + Acyc′ .

Theorem4. If a Horn operator ∆: EH×LH →KH satisfies postulates IC0 - IC3 + IC′4 + IC′5 + IC′6 + IC7 - IC8 + Acyc′ , then there exists a syncretic assignment mapping every Horn profile E to a Horn connected pre-order ≤E, such that, for any Horn formula µ, it holds that [∆µ(E)] =min≤E [µ].

In Theorem 4, the strengthened postulates IC′4 , IC′5 and IC′6 rule out Horn merging operators ∆ represented by nonsyncretic assignments such as the ones in Examples 4 and 5, and thus justify their presence. Our focus on Horn connected pre-orders, on the other hand, should not be seen as a restriction: we can translate any Horn compliant pre-order ≤E into a Horn connected one ≤⋆E such that the overall assignment (1) represents the same (Horn) merging operator and (2) remains syncretic. This can be done simply by 'uncoupling' pairs wi and wj which are not in the subset relation and do not satisfy either of the properties h3.1 and h3.2. Since wi and wj do not appear together in any set of the type min≤E [µ], for µ ∈ LH, the Horn merging operators represented by ≤E and ≤⋆E are the same.

However, the reverse is not as straightforward: for any Horn connected pre-order there exist more than one Horn compliant pre-orders representing the same Horn merging operator: any interpretations wi and wj that are not in ≤⋆E can be related in several ways if we care about making ≤⋆E total (we could have wi <⋆E wj , or wj <⋆E wi, etc.), and some of the configurations give rise to non-syncretic assignments. Our point is that wi and wj do not need to be related as long as the represented merging operator ∆ stays the same. Indeed, the main motivation for formulating the representation result with partial pre-orders is that if wi and wj do not satisfy h3.1 and h3.2 then a Horn merging operator ∆ does not give us any information on what the order between them should be. It makes sense, in this case, to not include wi and wj in the pre-order representing ∆.

5 A concrete Horn merging operator

By Theorem 2, we can find a Horn merging operator simply by exhibiting a Horn compliant, syncretic assignment. As in Examples 1 and 2, we can specify a pre-order ≤K by assigning numbers to interpretations, relative to K, and in the rest of this section this is how we will be thinking of pre-orders. We write lK(w) to denote the number assigned to w with respect to some knowledge base K. If K has exactly one model w′ , we simply write lw′ (w).

One difficulty here is that there is no obvious candidate for an off-the-shelf assignment that satisfies all the required properties: Horn compliance rules out standard approaches using familiar distances between interpretations. Therefore, we start by describing some general conditions sufficient to guarantee that the resulting assignment satisfies s1 - s6 and is Horn compliant.

We take lK(w) ≥ 0, for any knowledge base K and any w ∈ W, with lK(w) = 0 if and only if w ∈ [K]. This guarantees the assignment satisfies s1 - s3. We use the sum Σ to aggregate individual pre-orders, and this guarantees s5 - s6. The next conditions spell out what is needed for an assignment to satisfy s4.

Definition 5. The distance between knowledge bases K1 and K2 is defined as d(K1,K2) = min{lK1 (w) | w ∈ [K2]}.

We are interested in knowledge bases that satisfy the following property.

Definition 6. Knowledge bases K1 and K2 are symmetric if d(K1, K2) = d(K2, K1).

Symmetry is important because it guarantees s4.

Proposition 5 ([Konieczny and Pino P´erez, 2002]). If an assignment satisfies s1 - s3, then it satisfies s4 iff any two knowledge bases are symmetric.

Interestingly, it turns out that if we fix the pre-orders for every knowledge base K that has exactly one model, then pre-orders for knowledge bases K with more than one model are completely determined by this initial assignment (see Example 7). Thus, if symmetry is enforced, we can represent an assignment by just giving the pre-orders for single-model knowledge bases, as a 2n × 2n matrix. We shall call this the initial matrix. The same symmetry condition forces the initial matrix to be symmetric. For s1 - s3 to hold, the initial matrix needs to have positive entries and 0 on the main diagonal. 3

Example 7. Table 3 shows the initial matrix for the 2 letter alphabet, plus an additional ranking obtained through symmetry. Each column represents a ranking: for instance the first column represents the ranking for a knowledge base that has 00 as its sole model. The number assigned to 00 in this ranking is 0, the number assigned to 01 is 1, etc. The ranking for a knowledge base K that has {10, 11} as its set of models is computed from the initial assignment matrix with symmetry. For example, consider interpretation 00. By symmetry, we have that lK(00) = l00(K). Thus, we obtain l00(K) = min{l00(10), l00(11)} = min{2, 3} = 2.

3 All this is treated rigorously in [Haret et al., 2015].

All that is left is Horn compliance, and here we propose the following notion.

Definition 7. A pre-order ≤ is well-behaved if and only if for any interpretations w0, w1, w2 such that w1 ⊈ w2, w2 ⊈ w1 and w0 = w1 ∩ w2, it is the case that w0 ≤ w1 or w0 ≤ w2 and |min{l(w1), l(w2)} - l(w0)| ≤ |max{l(w1), l(w2)} - l(w0)|.

Notice that a well-behaved pre-order ≤ is also Horn compliant. What makes well-behavedness suitable for our needs, however, is that it is transmitted through Σ-aggregation.

Proposition 6. If ≤1 and ≤2 are well-behaved, then the preorder obtained by Σ-aggregating ≤1 and ≤2 is well-behaved.

Using all this knowledge, we can now define a specific Horn compliant syncretic assignment, which we will call the summation assignment. We define this assignment for the general case of an alphabet of size n. As suggested by the previous discussion, we give the initial matrix and use symmetry to determine pre-orders ≤K, when |[K]| > 1. Since the matrix for the initial assignment has to itself be symmetric and have 0 on the main diagonal, we will only define the entries in the matrix below the main diagonal, with the understanding that the entries above the main diagonal are fixed by symmetry. Also, the order in which interpretations appear in the rows and columns is fixed by the number of 1's in the corresponding bit-vector. For instance, the matrix for the 3-letter alphabet has its rows and columns ordered as follows: 000, 001, 010, 100, 011, 101, 110, 111.

The definition of the bottom half of the initial assignment matrix is recursive. First, put:

Hence, the levels on the first column are 0, 1, 2, . . . , 2n - 1 (see Table 4).

Second, for 1 ≤ i ≤ 2n - 1, put:

Roughly, this means that the number in a particular cell under the main diagonal is the sum of its two neighbours to the left. In Table 4: if lwi-1 (wi) = a, lwi-1 (wi+1) = b, then lwi (wi+1) = a + b. This is simpler than it sounds, and Table 3 shows the matrix that we get for the 2-letter alphabet.

The following proposition guarantees that the summation assignment is Horn compliant and stays Horn compliant through repeated Σ-aggregations.

Proposition 7. The summation assignment is well-behaved.

This is the last piece of information needed. We can now assert the following theorem.

Theorem 5. The summation assignment represents a Horn merging operator.

6 Conclusion and future work

In this paper, we provided a novel representation theorem for Horn merging by strengthening the standard merging postulates. Belief change operators for the Horn fragment have attracted increasing attention over the last years, in particular revision and contraction, while merging in the Horn fragment remained rather unexplored so far. An exception is the work by Creignou et al. [2014], who proposed to adapt known merging operators by means of a certain post-processing and studied the limits of this approach in terms of satisfaction of the merging postulates. One of the main results of that paper is that in their framework it is not possible to keep all postulates satisfied. In our work, we have presented a novel concrete Horn merging operator satisfying all postulates.

The moral of the present work is that, while going from syncretic assignments to Horn merging operators is relatively easy (Horn compliance is sufficient, by Theorem 2), going from Horn merging operators to syncretic assignments requires considerably more machinery (in particular, stronger postulates). Thus, all the work in Section 4 is needed to obtain a full representation result. Even so, Section 5 highlights that the easiness of the first direction is only relative, as finding concrete syncretic assignments that are also Horn compliant requires some conceptual work, and there is no obvious trivial operator that does the job. The main difficulty here lies in making sure that if two pre-orders ≤1 and ≤2 are Horn compliant, then the pre-order resulted from Σ-aggregating them is also Horn compliant. Our well-behavedness property guarantees this.

Future work on merging in the Horn fragment would have to consider extending the family of Horn merging operators. This requires seeing how Horn compliance interacts, on the model side, with other aggregation functions (such as GMAX ) and exploring the range of conditions guaranteeing Horn compliance of an assignment. We may add to this the study of other merging postulates (e.g., majority and arbitration), considered in the merging literature [Konieczny and Pino P´erez, 2002; 2011] but not touched upon here. Finally, we would like to extend our approach to other fragments of propositional logic (e.g., Krom or dual Horn), where similar problems arise and for which tailored notions of compliance and strengthened postulates are likely needed.