Distributing Knowledge into Simple Bases

1 Introduction

Belief change and belief merging have been topics of interest in Artificial Intelligence for three decades [Alchourr´on et al., 1985; Katsuno and Mendelzon, 1991; Konieczny and Pino P´erez, 2002]. However, the restriction of such operators to specific fragments of propositional logic has received increasing attention only in the last years [Delgrande et al., 2013; Creignou et al., 2014a; 2014b; Zhuang and Pagnucco, 2012; Zhuang et al., 2013; Zhuang and Pagnucco, 2014; Delgrande and Peppas, 2015; Haret et al., 2015]. Mostly, the question tackled in these works is "How should rationality postulates and change operators be adapted to ensure that the result of belief change belongs to a given fragment?". Surprisingly, the question concerning the extent to which the result of a belief change operation can deviate from the fragment under consideration has been neglected so far. In order to tackle this question, we focus here on a certain form of reverse merging. The question is, given an arbitrary knowledge base K and some IC-merging (i.e. merging with integrity constraint, see [Konieczny and Pino P´erez, 2002]) operator ∆, can we find a profile E, i.e. a tuple of knowledge bases, and a constraint θ, both from a given fragment of classical logic, such that ∆θ(E) yields a result equivalent to K? In other words, we are interested in seeing if K can be distributed into knowledge bases of simpler structure, such that the task of merging allows for a reconstruction of the original knowledge. We call this operation knowledge distribution.

Studying the concept of knowledge distribution can be motivated from different points of view. First, consider a scenario where the storage devices have limited expressibility, for instance, databases or logic programs. Our analysis will show which merging operators are required to reconstruct arbitrary knowledge stored in such a set of limited devices. Second, distribution can also be understood as a tool to hide information; only users who know the used merging operator (which thus acts as an encryption key) are able to faithfully retrieve the distributed knowledge. Given the high complexity of belief change (even for revision in "simple" fragments like Horn and 2CNF [Eiter and Gottlob, 1992; Liberatore and Schaerf, 2001; Creignou et al., 2013]), bruteforce attack to guess the merging operator is unthinkable. Finally, from the theoretical perspective our results shed light on the power of different merging operators when applied to profiles from certain fragments. In particular, our results show that merging 1CNF formulas via the Hammingdistance based operator ∆H↪⌃ does not need additional care, since the result is guaranteed to stay in the fragment.

Related Work. Previous work on merging in fragments of propositional logic proposed an adaptation of existing belief merging operators to ensure that the result of merging belongs to a given fragment [Creignou et al., 2014b], or modified the rationality postulates in order to function in the Horn fragment [Haret et al., 2015]. Our approach is different, since we do not require that the result of merging stays in a given fragment. On the contrary, we want to decompose arbitrary bases into a fragment-profile. Recent work by Liberatore has also addressed a form of meta-reasoning over belief change operators. In [Liberatore, 2015a], the input is a profile of knowledge bases with the expected result of merging R, and the aim is to determine the reliability of the bases (for instance, represented by weights) which allow the obtaining of R. In another paper, Liberatore [2015b] identifies, given a sequence of belief revisions and their results, the initial pre-order which characterizes the revision operator. Finally, even if our approach may seem related to Knowledge Compilation (KC) [Darwiche and Marquis, 2002; Fargier and Marquis, 2014; Marquis, 2015], both methods are in fact conceptually different. KC aims at modifying a knowledge base K into a knowledge base K0 such that the most important queries for a given application (consistency checking, clausal entailment, model counting, ▷ ▷ ▷ ) are simpler to solve with K0 . Here, we are interested in the extent to which it is possible to equivalently represent an arbitrary knowledge base by simpler fragments when using merging as a recovery operation.

Main Contributions. We formally introduce the concept of knowledge distributability, as well as a restricted version of it where the profile is limited to a single knowledge base (simplifiability). We show that for drastic distance arbitrary knowledge can be distributed into bases restricted to mostly any kind of fragment, while simplifiability is limited to trivial cases. On the other hand, for Hamming-distance based merging the picture is more opaque. We show that for 1CNF, distributability w.r.t. ∆H↪⌃ is limited to trivial cases, while slightly more can be done with ∆H↪GMin and ∆H↪GMax . For 2CNF we show that arbitrary knowledge can be distributed and even be simplified. Finally, we discuss the Horn fragment for which the results for ∆H↪⌃, ∆H↪GMin and ∆H↪GMax are situated in between the two former fragments.

2 Background

Fragments of Propositional Logic. We consider L as the language of propositional logic over some fixed alphabet U of propositional atoms. We use standard connectives _, ^, ≻, and constants >, ?. A clause is a disjunction of literals. A clause is called Horn if at most one of its literals is positive. An interpretation is a set of atoms (those set to true). The set of all interpretations is 2U . Models of a formula ' are denoted by Mod('). A knowledge base (KB) is a finite set of formulas and we identify models of a KB K via Mod(K) = T'2K Mod('). A profile is a finite non-empty tuple of KBs. Two formulae '1↪ '2 (resp. KBs K1↪K2) are equivalent, denoted '1 ⌘ '2 (resp. K1 ⌘ K2), when they have the same set of models.

We use a rather general and abstract notion of fragments.

Definition 1. Amapping Cl : 22U -! 22U is called closureoperator if it satisfies the following for anyM↪N ✓ 2U :

• ÷ IfM✓N, then Cl(M) ✓ Cl(N)
• ÷ If ♣M♣ = 1, then Cl(M) =M
• ÷ Cl(;) = ;.

Definition 2. L0 ✓ L is called a fragment if it is closed under conjunction (i.e., ' ^ 2 L0 for any '↪ 2 L0 ), and there exists an associated closure-operator Cl such that (1) for all 2 L0 , Mod( ) = Cl(Mod( )) and (2) for all M ✓ 2U there is a 2 L0 with Mod( ) = Cl(M). We often denote the closure-operator Cl associated to a fragment L0 as ClL0 .

Definition 3. For a fragment L0 , we call a finite set K ✓ L0 an L0 -knowledge base. An L0 -profile is a profile over L0 - knowledge bases. A KB K ✓ L is called L0 -expressible if there exists an L0 -KB K0 , such that K ⌘ K0 .

Many well known fragments of propositional logic are indeed captured by our notion. For the Horn-fragment LHorn, i.e. the set of all conjunctions of Horn clauses over U, take the operator ClLHorn defined as the fixed point of the function

The fragment L2CNF which is restricted to formulas over clauses of length at most 2 is linked to the operator ClL2CNF defined as the fixed point of the function Cl1L2CNF given by

Here, we use the ternary majority function maj3(!1↪ !2↪ !3) which yields an interpretation containing those atoms which are true in at least two out of !1↪ !2↪ !3. Finally, we are also interested in the L1CNF fragment which is just composed of conjunctions of literals; its associated operator ClL1CNF is defined as the fixed point of the function

Note that full classical logic is given via the identity closure operator ClL(M) = M.

Merging Operators. We focus on IC-merging, where a profile is mapped into a KB, such that the result satisfies some integrity constraint. Postulates for IC-merging have been stated in [Konieczny and Pino P´erez, 2002]. We recall a specific family of IC-merging operators, based on distances between interpretations, see also [Konieczny et al., 2004].

Definition 4. A distance between interpretations is a mapping d from two interpretations to a non-negative real number, such that for all !1↪ !2↪ !3 ✓ U, (1) d(!1↪ !2) = 0 iff !1 = !2; (2) d(!1↪ !2) = d(!2↪ !1); and (3) d(!1↪ !2) + d(!2↪ !3) ≥ d(!1↪ !3). We will use two specific distances:

drastic distance D(!1↪ !2) = 1 if !1 = !2, 0 otherwise;

We overload the previous notations to define the distance between an interpretation ! and a KB K: if d is a distance between interpretations, then d(!↪K) = min!02Mod(K) d(!↪ !0 ). Next, an aggregation function must be used to evaluate the distance between an interpretation and a profile.

Definition 5. An aggregation function ⌦ associates a nonnegative number to every finite tuple of non-negative numbers, such that (1) if x  y, then ⌦(x1↪ ▷ ▷ ▷ ↪ x↪ ▷ ▷ ▷ ↪ xn)  ⌦(x1↪ ▷ ▷ ▷ ↪ y↪ ▷ ▷ ▷ ↪ xn); (2) ⌦(x1↪ ▷ ▷ ▷ ↪ xn) = 0 iff x1 = · · · = xn = 0; (3) for every non-negative number x, ⌦(x) = x. As aggregation functions, we will consider the sum ⌃, GMax and GMin 1 , defined as follows. Given a profile (K1↪ ▷ ▷ ▷ ↪Kn), let V! = (d!1 ↪ ▷ ▷ ▷ ↪ d!n ) be the vector of distances such that d!i = d(!↪Ki). GMax(d!1 ↪ ▷ ▷ ▷ ↪ d!n ) (resp. GMin(d!1 ↪ ▷ ▷ ▷ ↪ d!n )) is defined by ordering V! in decreasing (resp. increasing) order. Given two interpretations !1↪ !2, GMax (d!1 1 ↪ ▷ ▷ ▷ ↪ d!1 n )  GMax(d!2 1 ↪ ▷ ▷ ▷ ↪ d!2 n ) (resp. GMin(d!1 1 ↪ ▷ ▷ ▷ ↪ d!1 n )  GMin(d!2 1 ↪ ▷ ▷ ▷ ↪ d!2 n )) is defined by comparing themw.r.t. the lexicographic ordering.

Finally, let d be a distance, ! an interpretation and E = (K1↪ ▷ ▷ ▷ ↪Kn) a profile. Then, d⌦(!↪E) = ⌦(d(!↪K1)↪ ▷ ▷ ▷ ↪ d(!↪Kn)). If there is no ambiguity about the function ⌦, we write d(!↪ E) for d⌦(!↪ E).

Definition 6. For any distance d between interpretations, and any aggregation function ⌦, the merging operator ∆d↪⌦ is a mapping from a profile E and a formula θ to a KB, such that Mod (∆d↪⌦ θ (E)) = min(Mod(θ)↪d↪⌦ E ), with !1 d↪⌦ E !2 iff d⌦(!1↪ E)  d⌦(!2↪ E).

When we consider a profile containing a single knowledge base K, all aggregation functions are equivalent; we write ∆dθ (K) instead of ∆d↪⌦ θ ((K)) for readability. For drastic distance, GMin, GMax , and ⌃ are equivalent for arbitrary profiles. Thus, whenever we show results for ∆D↪⌃, these carry over to ∆D↪GMin and ∆D↪GMax .

3 Main Concepts and General Results

We now give the central definition for a knowledge base being distributable into a profile from a certain fragment with respect to a given merging operator.

Definition 7. Let ∆ be a merging operator, K ✓ L be an arbitrary KB, and L0 be a fragment. K is called L0 -distributable w.r.t. ∆ if there exists an L0 -profile E and a formula θ 2 L0 , such that ∆θ(E) ⌘ K.

Example 1. Let U = ¶a↪ b♦ and consider K = ¶a _ b♦ which we want to check for LHorn-distributability w.r.t. operator ∆H↪⌃. We have Mod(K) = ¶¶a♦↪ ¶b♦↪ ¶a↪ b♦♦, thus K is not LHorn-expressible (note that ClLHorn (Mod(K)) = ¶;↪ ¶a♦↪ ¶b♦↪ ¶a↪ b♦♦ 6= Mod(K)), otherwise K would be distributable in a simple way (see Proposition 1 below).

Take the LHorn -profile E = (K1↪ K2) with K1 = ¶a ^ b♦, K2 = ¶≻a _ ≻b♦, together with the empty constraint θ = >. We have Mod(K1) = ¶¶a↪ b♦♦, Mod(K2) = ¶¶a♦↪ ¶b♦↪ ;♦. In the following matrix, each line corresponds to the distance between a model of θ and a KB from the profile E, or between a model of θ and the profile using the ⌃-aggregation over the distances to the single KBs.

1 GMax and GMin are known as leximax and leximin respectively. These functions return a vector of numbers, not a single number. However, GMax (resp. GMin) can be associated with an aggregation function as defined in Def. 5 which yields the same vector ordering than GMax (resp. GMin). We do a slight abuse by using GMax and GMin as the names of aggregation functions. See [Konieczny et al., 2002].

We observe that Mod(∆H↪⌃ θ (E)) = ¶¶a♦↪ ¶b♦↪ ¶a↪ b♦♦, thus ∆H↪⌃ θ (E) ⌘K as desired. It is easily checked that also other aggregations work: ∆H↪GMax θ (E) ⌘ ∆H↪GMin θ (E) ⌘K. ⇧

Next, we recall that IC-merging of a single KB yields revision. Thus, the concept we introduce next is also of interest, as it represents a certain form of reverse revision.

Definition 8. Let ∆ be a merging operator, K ✓ L an arbitrary KB, and L0 a fragment. K is called L0 -simplifiable w.r.t. ∆ if there exists an L0 -KB K0 and θ 2 L0 , such that ∆θ(K0 ) ⌘ K.

As we will see later, the KB K from Example 1 cannot be LHorn-simplified w.r.t. ∆H ; in other words, we need here at least two KBs to "express" K. However, it is rather straightforward that any L0 -expressible KB can be L0 -simplified.

Proposition 1. For every fragment L0 and every KB K, it holds that K is L0 -simplifiable (and thus also L0 - distributable) w.r.t. ∆, whenever K is L0 -expressible.

Proof. Let K0 be an L0 -KB equivalent to K, and let θ = (V'2K0 '). Thus, θ 2 L0 by definition of fragments and it is easily verified that ∆θ(K0 ) ⌘ K.

Next, we show that in order to determine whether a KB K is L0 -distributable, it is sufficient to consider constraints θ such that Mod(θ) = ClL0 (Mod(K)).

Proposition 2. Let K 2 L be a KB, L0 be a fragment, E an L0 -profile and θ 2 L0 . Then ∆θ(E) ⌘ K implies ∆θ0 (E) ⌘ K for any θ0 such that Mod(θ0 ) = ClL0 (Mod(K)).

Proof. Let ∆ = ∆d↪⌦. By Definition 6, Mod(K) = min(Mod (θ)↪ d↪⌦ E ), henceMod(K) ✓Mod(θ). Moreover, θ is L0 -closed, so ClL0(Mod(K)) = Mod(θ0 ) ✓ Mod(θ). We get Mod(K) ✓ Mod(θ0 ) ✓ Mod(θ). Thus, Mod(K) = min(Mod (θ0 )↪ d↪⌦ E ), i.e. ∆θ0(E) ⌘K.

Next, we give two positive results for distributing knowledge in any fragment. The key idea is to use KBs in the profile which have exactly one model (our notion of fragment guarantees existence of such KBs). The first result is independent of the distance notion but requires GMin as the aggregation function. The second result is for drastic distance and thus works for any of the aggregation functions we consider.

Theorem 3. Let d be a distance and L0 be a fragment. Then for every KB K, such that for all distinct !1↪ !2 2 Mod(K), d(!1↪ !2) = e for some e > 0, it holds that K is L0 - distributable w.r.t. ∆d↪GMin ▷

Proof. Build the L0 -profile E such that for each ! 2 Mod(K), there is a KB with ! as its only model. Thus all models of K get a GMin-vector (0↪ e↪ e↪ e↪ e↪ ▷ ▷ ▷). All interpretations from ClL0(Mod(K)) ∩ Mod(K) get a vector (f↪ g↪ ▷ ▷ ▷) with f > 0. Hence, we have min(Mod (θ)↪ d↪GMin E ) = Mod(K) using θ 2 L0 with Mod (θ) = ClL0 (Mod (K)).

Theorem 4. For every fragment L0 and every knowledge base K, it holds that K is L0 -distributable w.r.t. ∆D↪⊕, for ⊕ 2 ¶⌃↪ GMin↪ GMax ♦.

The proof is similar to the one of Theorem 3 and thus omitted. For simplifiability w.r.t. drastic distance based operators, Proposition 1 cannot be improved, as we show next.

Theorem 5. For every fragment L0 and every KB K, K is L0 -simplifiable w.r.t. ∆D iff K is L0 -expressible.

Proof. The if-direction is by Proposition 1. For the other direction, suppose K is not L0 -expressible. We show that for any L0 -KB K0 , ∆Dθ (K0 ) 6⌘ K with θ = ClL0 (K). By Proposition 2 the result then follows. Now suppose there exists an L0 -KB K0 such that ∆Dθ (K0 ) ⌘ K. First observe that since K is not L0 -expressible, Mod(θ) ⊃ Mod(K). Since we are working with drastic distance, in order to promote models of K, we also need them in K0 , hence Mod(K0 ) ◆ Mod(K) and since K0 is from L0 we have Mod(K0 ) ◆ ClL0(K) = Mod(θ). Thus there exists ! 2 ClL0(Mod(K)) ∩ Mod(K) having distance 0 to K0 , and thus ! 2 ∆Dθ (K0 ). Since ! ◁2 Mod(K), this yields a contradiction to ∆Dθ (K0 ) ⌘ K.

4 Hamming Distance and Specific Fragments

We first consider the simplest fragment under consideration, namely conjunction of literals. As it turns out, (non-trivial) distributability for this fragment w.r.t. ∆H↪⌃ is not achievable. We then see that more general fragments allow for nontrivial distributions. In particular, we show that every KB is distributable (and even simplifiable) in the 2CNF case, and we finally give a few observations for LHorn .

4.1 The 1CNF Fragment

The following technical result is important to prove the main result in this section.

Lemma 6. For any L1CNF-profile E = (K1↪ ▷ ▷ ▷ ↪Kn) and interpretations !1↪ !2, it holds that:

Proof. It suffices to show that for each Ki in profile E, H(!1↪ Ki)+H(!2↪ Ki) = H(!1\!2↪ Ki)+H(!1[!2↪ Ki). Indeed, summing up these equalities over all Ki 2 E, we get

Since H(!↪ E) = ⌃Ki2EH(!↪ Ki), for any interpretation !, our conclusion then follows immediately.

Thus, take !01 ↪ !02 to be two interpretations that are closest to !1 and !2, respectively, among the models of Mod(Ki). In other words, H(!1↪ !01 ) = min!2Mod(Ki) H(!1↪ !) and H(!2↪ !02 ) = min!2Mod(Ki) H(!2↪ !). By induction on the number of propositional atoms in L, we can show that !01 \!02 and !01 [ !02 are closest in Mod(Ki) to !1 \ !2 and !1 [ !2, respectively. Thus, we have that H(!1↪Ki) = H(!1↪ !01 ), H(!2↪ Ki) = H(!2↪ !02 ), H(!1\!2↪ Ki) = H(!1\!2↪ !01 \ !02 ), H(!1 [ !2↪Ki) = H(!1 [ !2↪ !01 [ !02 ), and our problem reduces to showing that H(!1↪ !01 ) + H(!2↪ !02 ) = H(!1 \!2↪ !01 \!02 )+H(!1 [!2↪ !01 [!02 ). By using induction on the number of propositional atoms in L again, we can show that this equality holds. The argument runs as follows:

in the base case, when the alphabet consists of just one propositional atom, the equality is shown to be true by checking all the cases. For the inductive step we assume the claim holds for an alphabet of size n and show that it also holds for an alphabet of size n+1. Concretely, we analyze the way in which the Hamming distances between interpretations change when we add a propositional atom to the alphabet. An analysis of all the possible cases shows that the equality holds.

Next we observe certain patterns of interpretations that indicate whether a KB is L1CNF -expressible or not.

Definition 9. If K is a knowledge base, then a pair of interpretations !1 and !2 are called critical with respect to K if !1 * !2 and !2 * !1, and one of the following cases holds:

1. !1↪ !2 2 Mod(K) and !1 \!2↪ !1 [!2 ◁2 Mod(K),
2. !1↪ !2↪ !1 \!2 2 Mod(K) and !1 [!2 ◁2 Mod(K),
3. !1↪ !2↪ !1 [!2 2 Mod(K) and !1 \!2 ◁2 Mod(K),
4. !1 \!2↪ !1 [!2 2 Mod(K) and !1↪ !2 ◁2 Mod(K), or
5. !1↪ !1 \!2↪ !1 [!2 2 Mod(K) and !2 ◁2 Mod(K).

Lemma 7. If a KB K is not L1CNF-expressible, then there exist !1↪ !2 2 ClL1CNF (K) being critical with respect to K.

Proof. The fact that K is not L1CNF -expressible implies that either: (i) K is not closed under intersection or union, or (ii) there are w1↪w2↪w3 2 ClL1CNF (K) such that w1 ✓ w3 ✓ w2, and w1↪ w2 2 Mod(K), w3 ◁2 Mod(K). Case (i) implies that there exist w1↪ w2 2 Mod(K) such that one of Cases 1-3 from Definition 9 holds. If we are in Case (ii), then consider the interpretation w4 = (w2∩w3) [ w1. Clearly, w1 ✓ w4 ✓ w2, hence w4 2 ClL1CNF (K). Also, w3 \ w4 = w1 and w3 [ w4 = w2. There are two sub-cases to consider here. If w4 ◁2 Mod(K), then we are in Case 4 of Definition 9. If w4 2 Mod(K), then we are in Case 5 of Definition 9.

We can now state the central result of this section.

Theorem 8. A KB K is L1CNF -distributable with respect to ∆H↪⌃ if and only if K is L1CNF -expressible.

Proof. If part is by Proposition 1. Only if part: let K be a KB that is not L1CNF -expressible. We will show that it is not L1CNF-distributable w.r.t. ∆H↪⌃. Suppose, on the contrary, that K is L1CNF-distributable. Then there exists an L1CNF profile E = (K1↪ ▷ ▷ ▷ ↪Kn) such that ∆H↪⌃ θ (E) ⌘ K, where Mod(θ) = ClL1CNF (Mod(K)) (cf. Proposition 2).

By Lemma 7, there exist interpretations !1↪ !2 2 Mod(θ) that are critical with respect to K. By Lemma 6, we have

Let us now do a case analysis depending on the type of critical pair we are dealing with. If we are in Case 1 of Definition 9, then it needs to be the case that H(!1↪ E) = H(!2↪ E) = m, H(!1 \ !2↪ E) = m + k1 and H(!1 [ !2↪ E) = m + k2, for some integers m ≥ 0 and k1↪ k2 > 0. Plugging these numbers into Equality (1), we get that 2m = 2m+ k1 + k2 and k1 + k2 = 0. Since k1↪ k2 > 0, we have arrived at a contradiction. If we are in Case 2, then it needs to be the case that H(!1 \!2↪E) = H(!1 [ !2↪E) = m, H(!1↪E) =

m+k1 and H(!2↪ E) = m+k2, for some integers m ≥ 0 and k1↪ k2 > 0. Plugging these numbers into Equality (1) again, we get a contradiction along the same lines as in Case 1. If we are in Case 3, then it needs to hold that H(!1↪ E) = H(!1 \ !2↪E) = H(!1 [ !2↪E) = m, H(!2↪E) = m + k, for some integers m ≥ 0 and k > 0. Plugging these numbers into Equality (1) gives us 2m + k = 2m and hence k = 0. Since k > 0, we have arrived at a contradiction. Cases 4 and 5 are entirely similar.

In other words, for any L1CNF-profile and θ 2 1CNF, ∆H↪⌃ θ is guaranteed to be L1CNF-expressible as well. As we have already shown in Theorem 3, this is not necessarily the case if we replace ⌃ by GMin. The following example shows how to obtain a similar behavior for GMax; we then generalize this idea below.

Example 2. Let U = ¶a↪ b♦ and K = ¶a _ b↪ ≻a _≻b♦. We have Mod(K) = ¶¶a♦↪ ¶b♦♦. K is not L1CNF-expressible, since ClL1CNF (Mod(K)) = 2U . Let KS be the L1CNFKB with a single model S for any S ✓ U and let us have a look at the following distance matrix for θ with Mod(θ) = ClL1CNF (Mod(K)), E = (K¶a♦↪K¶b♦), and E0 = (K;↪K¶a↪b♦).

The lexicographic order of the involved vectors is (0↪ 2) < (1↪ 1) < (2↪ 0). We thus get that ∆H↪GMin θ (E) ⌘ K (see also Theorem 3), and on the other hand, ∆H↪GMax θ (E0 ) ⌘K. ⇧

Theorem 9. Any KB K such that Mod(K) = ¶!↪ !0 ♦ is L1CNF -distributable with respect to ∆H↪GMax .

Proof. If K is L1CNF-expressible, then the conclusion follows from Proposition 1. If K is not L1CNF-expressible, then consider the set ClL1CNF (Mod(K))∩Mod(K) = ¶!1↪ ▷ ▷ ▷ ↪ !n♦. We define the profile E = (K1↪ ▷ ▷ ▷ ↪Kn), where Mod(Ki) = ¶U∩!i♦, for i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦. We show that ∆H↪GMax θ (E) ⌘ K, where Mod(θ) = ClL1CNF (Mod(K)). First, we have that H(!i↪ U∩!i) = ♣U♣, which implies that HGMax (!i↪E) = GMax(♣U♣↪ ▷ ▷ ▷ ), for any i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦. Furthermore, since H(!↪ U∩!i) < ♣U♣ and H(!0 ↪ U∩!i) < ♣U♣, for any i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦, it follows that ! <H↪GMax E !i and !0 <H↪GMax E !i. Next, we show that HGMax (!↪E) = HGMax (!0 ↪E). Consider the vectors V = (H(!↪ !1)↪ ▷ ▷ ▷ ↪H(!↪ !n)) and V 0 = (H(!0 ↪ !1)↪ ▷ ▷ ▷ ↪H(!0 ↪ !n)). Our claim is that GMax(V ) = GMax(V 0 ). To see why, notice that the elements in ClL1CNF (Mod(K)) form a complete subset lattice with ![!0 and ! \ !0 as the top and bottom elements, respectively. Let us write H(!↪ !0 ) = m. This lattice has 2m elements, and the maximum distance of two elements in it is m. Thus, the vector V is the vector of distances between ! and every other element in this lattice, except itself and !0 . A similar consideration holds for V 0 . Hence V and V 0 are vectors of length

2m-2 whose elements are m-1↪ m-2↪ ▷ ▷ ▷ ↪ 1. We can actually count how many times each number appears in V and V 0 . The number of interpretations in the lattice that are at distance of 1 from ! (and !0 ) is ( 1m): thus, m-1 appears ( 1m) times in V (and V 0 ). The number of interpretations that are at distance 2 from ! (and !0 ) is ( 2m), thus m- 2 appears ( 2m) times in V and V 0 . We iterate this argument for every distance, up to 1. It is then easy to see that, based on these considerations, V and V 0 are equal when sorted in descending order. Our conclusion follows from this.

4.2 The 2CNF Fragment

We show that every knowledge base K can be distributed in the fragment L2CNF . Even a single L2CNF knowledge base is enough to represent K. Before giving the general result, we sketch the idea via an example.

Example 3. Let K be a KB with Mod(K) = ¶¶a↪ b♦↪ ¶b↪ c↪ e♦↪ ¶a↪ c↪ d♦♦. We observe that K is not L2CNF -expressible since ClL2CNF (Mod(K)) = Mod(K) [ ¶a↪ b↪ c♦. However, we can give an L2CNF-KB K0 using three new atoms x↪ y↪ z to penalize the undesired interpretation ¶a↪ b↪ c♦ such that ∆Hθ (K0 ) ⌘ K, with θ 2 L2CNF of the formMod(θ) = ClL2CNF (Mod(K)). To this end, assume K0 with Mod(K0 ) = ¶!1↪ !2↪ !3↪ !4♦ of the form

One can verify that ClL2CNF (Mod(K0 )) = Mod(K0 ). Thus, K0 can be picked from L2CNF . We use θ such that Mod(θ) = ClL2CNF (Mod(K)) and get distances

Here, each line gives the distance between a model of θ and a model of K0 (!i columns), or between a model of θ and K0 (min column). The key observation is that pairs from x↪ y↪ z as used in !1, !2, !3 give minimal distances 2 while the remaining interpretation !4, which corresponds to the closure of K, contains all three new atoms (since maj3(¶x↪ y♦↪ ¶x↪ z♦↪ ¶y↪ z♦) = ¶x↪ y↪ z♦). ⇧

Theorem 10. Any KB K is L2CNF -simplifiable w.r.t. ∆Hθ .

Proof. We have to show that for any KB K, there exists an L2CNF-KB K0 and a formula θ 2 L2CNF such that ∆Hθ (K0 ) ⌘ K. If K is L2CNF-expressible, the result is due to Proposition 1. So suppose that K is not L2CNFexpressible and let Mod(K) = ¶!1↪ ▷ ▷ ▷ ↪ !n♦. Consider a set of new atoms A = ¶a1↪ ▷ ▷ ▷ ↪ an♦, and for each !i 2 Mod(K), let !0i = !i [ A ∩ ¶ai♦. We define the L2CNF-KB K0 and θ 2 L2CNF such that Mod(K0 ) = ClL2CNF (¶!0i ♣ !i 2 Mod(K)♦) and Mod(θ) = ClL2CNF (Mod(K)). Let ⌦0 = ¶!0i ♣ !i 2 Mod(K)♦. We first show that for each ! 2 Mod(K0 ) ∩ ⌦0 , A ✓ !. Indeed, for any triple !j↪ !k↪ !l 2 Mod(K), such that !jkl = maj3(!j ↪ !k↪ !l) ◁2 Mod(K), we observe that maj3(!0j ↪ !0k ↪ !0 l ) = !jkl [ maj3(A ∩ ¶aj♦↪ A ∩ ¶ak♦↪ A∩¶al♦) = !jkl[A. Thus, for each ! 2 Cl1L2CNF (⌦0 )∩ ⌦0 , A ✓ !. Recall that Mod(K0 ) = ClL2CNF (⌦0 ). It follows quite easily that each further interpretation ! 2 ClL2CNF (⌦0 ) ∩ (Cl1L2CNF (⌦0 ) [ ⌦0 ), also satisfies A ✓ !.

This shows that each model of K0 contains at least n - 1 atoms from A. Thus, for every model !i 2 K, H(!i↪K0 ) = H(!i↪ !0i ) = n - 1. It remains to show that for each ! 2 Mod(θ) ∩Mod(K), H(!↪K0 ) ≥ n. First, let !0 2 ⌦0 . Since ! ◁2 Mod(K), !0 ∩ A 6= ! and since !0 contains n - 1 elements from A, we have H(!↪ !0 ) ≥ n. As shown above all other interpretations !00 2 Mod(K0 ) ∩ ⌦0 contain all n atoms fromA, thus H(!↪ !00 ) ≥ n, too.

As an immediate consequence, we obtain that any KB K is L2CNF -distributable w.r.t. ∆H↪⌦ for any aggregation function ⌦. Note that this result is in strong contrast to the L1CNF fragment, where only L1CNF-expressible KBs are L1CNFdistributable w.r.t. ∆H↪⌃.

4.3 The Horn-Fragment

We now turn our attention to the LHorn fragment. Recall Example 1 where we have shown how to distribute some non LHorn-expressible KB using a profile over two LHorn-KBs. Our first result shows that in this example case we cannot reduce to profiles of a single KB, i.e. that there are KBs which are LHorn -distributable but not LHorn -simplifiable.

Proposition 11. A KB K with Mod(K) = ¶!1↪ !2↪ !3♦, where !3 = !1 [ !2, H(!1↪ !2) = 2 and !1↪ !2 are incomparable, is not LHorn-simplifiable w.r.t. ∆H .

Proof. The situation described in the proposition corresponds to a KB K = ¶! [ ¶a♦↪ ! [ ¶b♦↪ ! [ ¶a↪ b♦♦ with ! some interpretation which does not contain a or b. We need Mod (θ) = ¶!↪ ! [ ¶a♦↪ ! [ ¶b♦↪ ! [ ¶a↪ b♦♦, as required by Proposition 2. We want to identify a LHorn-KB K0 such that ∆Hθ (K0 ) ⌘ K. This means that ! is the single model of θ which is not minimal w.r.t. the Hamming distance. Let !01 be the model in K0 closest to !1 = ! [ ¶a♦ and !02 the one closest to !2 = ! [ ¶b♦. We need a 2 !01 and b 2 !02 ; otherwise H(!↪ !01 ) < H(!1↪ !01 ) or H(!↪ !02 ) < H(!2↪ !02 ); further we need b ◁2 !01 and a ◁2 !02 ; otherwise H(!3↪ !01 ) < H(!1↪ !01 ) or H(!3↪ !02 ) < H(!2↪ !02 ). Hence !01 and !02 are incomparable thus also !01 \ !02 2 Mod(K0 ), since K0 is a Horn KB. But then H(!↪ !01 \ !02 )  H(!1↪ !01 ).

Our last result shows that ∆H nonetheless increases the range of LHorn -simplifiable KBs compared to ∆D .

Proposition 12. Any knowledge base K with Mod(K) = ¶!1↪ !2♦ is LHorn -simplifiable w.r.t. ∆H .

Proof. If !1↪ !2 are comparable, we can apply Proposition 1. Thus, assume !1↪ !2 are incomparable and let d1 = ♣!1 ∩ !2♣ and d2 = ♣!2 ∩ !1♣. W.l.o.g. assume d1  d2. Also note that d1 > 0. We use K0 with Mod(K0 ) = ¶!+ 1 ↪ !1 [ !2♦ where !+ 1 adds d1 elements from !2 ∩ !1 to !1. Thus, !+ 1 ✓ !1[!2 and we can choose K0 from LHorn . Moreover, let θ 2

distributable w.r.t. ∆H↪GMin - X -

Table 1: Summary of Results

LHorn such that Mod(θ) = ¶!1↪ !2↪ !1 \ !2♦. We have the following distances (note that d(!2↪ !+ 1 ) = d1 + (d2 - d1)).

5 Conclusion

In this paper we have proposed the notion of distributability and we have studied the properties of several merging operators with respect to different fragments of propositional logic. Our results are summarized in Table 1.

Symbol ⇥ means that only "trivial" KBs (belonging to the considered fragment) can be distributed with the corresponding operator. Alternately, X means that any KB can be distributed. Symbol - means we know that some non-trivial KBs can be distributed, and finally ◦ means that some, but not all, non-trivial KBs can be simplified. Interestingly, the picture emerging from Table 1 is that merging operators behave quite differently depending on the distance and aggregation function employed, in a way that does not lend itself to simple categorization. For instance, our results on simplifiability imply that using Dalal revision to L1CNF KBs never takes us outside the 1CNF fragment; applying the same revision operator to L2CNF KBs can produce any KB in L; and applying it to LHorn KBs can produce some, though not all possible KBs.

Several questions are still open for future work. We plan to study the exact characterization of what can (and cannot) be distributed, in order to replace the symbols - and ◦ in the Table 1. Other merging operators can also be integrated to our study. Some of our results on distributability require the addition of new atoms to the interpretations. We want to determine whether similar results can be obtained without modifying the set of propositional variables. We are also interested in the number of KBs needed to distribute knowledge: given an integer n, a KB K and a merging operator ∆, is it possible to distribute K w.r.t. ∆ such that the resulting profile contains at most n KBs? This paper was a first step to understand the limits of distributability; the actual construction of the profile and complexity of this process are important questions that will be tackled in future research. Finally, we also consider applying the concept of distributability to non-classical formalisms, in particular in connection with merging operators proposed for logic programs [Delgrande et al., 2013].

Acknowledgments

This work was supported by the Austrian Science Fund (FWF) under grant P25521.