Measuring conflict and agreement between two prioritized belief bases

1 Introduction

In the belief revision and belief merging literature, the wellknown Dalal distance known as the Hamming distance between interpretations [Dalal, 1988], plays a key role in the notion of minimal change. The Dalal distance between two interpretations models how many atoms are in conflict, so it measures only the quantity of conflict between them. Hunter has defined a degree of conflict between two knowledge bases based on the Dalal distance [Hunter, 2004].

In recent years, relationships between two knowledge bases have been defined by measures of information and contradiction. In [Konieczny et al., 2003], a degree of contradiction and a degree of ignorance were defined and they can be used to order the sources of information. If a knowledge base has a high degree of contradiction and a low degree of ignorance, then it has a low order. In [Hunter, 2002], some compromise relations between two knowledge bases were defined according to the quantities of conflict information and total information in them.

In all the relationships described above, the quantity of conflict information between two knowledge bases was focused upon. However, in reality, when establishing the relationships between two agents, not only information in conflict, but also information in agreement should be considered. The quantities of conflict and agreement can affect each other. Considering two agents with low quantity of conflict between them, our perception of the degree of conflict between them will be further weakened if they have a lot in common. Furthermore, when two agents have no information in conflict, it is useful to consider the agreement between them.

We use two quantities of agreement; one is called the quantity of strong agreement which measures the information that both agents "totally" agree with, and the other is called the quantity of weak agreement which measures the information that is believed by one source but is unknown to the other. Both quantities will influence the degree of conflict, but their influences are different. Intuitively, the quantity of strong agreement will have more influence on the degree of conflict than the quantity of weak agreement. To illustrate, let us consider the following three knowledge bases: B1 = {φ, ψ}, B2 = {¬φ, ψ}, and B3 = {¬φ}. B1 is in conflict with both B2 and B3. B1 and B2 strongly agree on ψ, whilst B1 only weakly agrees with B3 on ψ. Clearly the degree of conflict between B1 and B2 should be smaller than that between B1 and B3 because there is a topic that both B1 and B2 agree opon. However, when defining the degree of conflict [Hunter, 2004], Hunter did not distinguish the influences of strong agreement and weak agreement. To accompany the degree of conflict, we can define a degree of strong agreement and a degree of weak agreement.

In this paper, we will measure the conflict and agreement between two prioritized knowledge bases, where the priority of a formula, based on necessity degrees, is handled in possibilistic logic. It is well-known that priority plays an important role in inconsistency handling, belief revision and belief merging [G¨ ardenfors, 1988; Konieczny & Ramon, 1998; Benferhat et al., 2002]. Possibilistic logic provides a good framework for expressing priority. We first define the weighted prime implicant (WPI), which is a generalization of the regular prime implicant to possibilistic logic. Then, the measures of conflict and agreement will be defined by WPIs.

This paper is organized as follows. Section 2 gives some preliminaries. We then define the weighted prime implicant and measures of conflict and agreement in Section 3. Section 4 discusses the impact of the measures of conflict and agreement. Finally we conclude the paper in Section 5.

2 Preliminaries

Classical logic: In this paper, we consider a propositional language LPS from a finite set PS of propositional symbols. The classical consequence relation is denoted as ⊢. An interpretation is a total function from PS to {true, false}. Ω is the set of all possible interpretations. An interpretation w is a model of a formula φ iff w(φ) = true. p, q, r,... represent atoms in PS. A literal is an atom p or its negation ¬p. We will denote literals by l, l1, .. and formulae in LPS by φ, ψ, γ,... For each formula φ, we use M(φ) to denote its set of models. A classical knowledge base B is a finite set of propositional formulae. B is consistent iff there exists an interpretation w such that w(φ) = true for all φ∈B. A clause C is a disjunction of literals: C = l1∨...∨ln and its dual clause, or termD, is a conjunction of literals: D = l1∧...∧ln.

Possibilistic Logic [Dubois et al., 1994]: Possibilistic logic is a weighted logic where each classical logic formula is associated with a number in [0, 1], a necessity degree, which represents the extent to which the formula is true. A possibilistic knowledge base (PKB) is the set of possibilistic formulae of the form B = {(φi, αi) : i = 1, ..., n}. Possibilistic formula (φi, αi) means that the necessity degree of φi is at least equal to αi. A classical knowledge base B = {φi : i = 1, ..., n} corresponds to a PKB B ′ = {(φi, 1) : i = 1, ..., n}. In this paper, we consider only PKBs where every formula φ is a classical propositional formula. The classical base associated with B is denoted as B ∗ , namely B ∗ = {φi|(φi, αi) ∈ B}. A PKB is consistent iff its classical base is consistent.

Semantically, the most basic and important notion is possibility distribution π: Ω → [0, 1]. π(ω) represents the possibility degree of interpretation ω with available beliefs. From possibility distribution π, two measures can be determined, one is the possibility degree of formula φ, defined as Π(φ) = max{π(ω) : ω |= φ}, the other is the necessity degree of formula φ, defined as N(φ) = 1 - Π(¬φ). The possibility measure is max-decomposable, i.e. Π(φ ∨ ψ) = max(Π(φ),Π(ψ)). Whilst the necessity measure is mindecomposable, i.e. N(φ ∧ψ) =min(N(φ),Π(ψ)).

Definition 1 [Dubois et al., 1994] Let B be a PKB, and α ∈ [0, 1]. The α-cut of B is B≥α = {φ∈B ∗ |(φ, a)∈B and a≥α}.

Definition 2 [Dubois et al., 1994] Let B be a PKB. A formula φ is said to be a possibilistic consequence of B to degree a, denoted by B⊢π(φ, a), iff the following conditions hold: (1) B≥a is consistent; (2) B≥a⊢φ; (3) ∀b>a, B≥b ̸ ⊢ φ.

3 Measures of Conflicts and Agreements

3.1 Weighted prime implicant

In this section, we will define and discuss weighted prime implicants of PKBs.

A term D is an implicant of formula φ iff D⊢φ and D does not contain two complementary literals.

Definition 3 [Cadoli & Donini, 1997] A prime implicant of knowledge base B is an implicant D of B such that for every other implicant D ′ of B, D̸ ⊢D ′ .

Prime implicants are often used in knowledge compilation [Cadoli & Donini, 1997] to make the deduction tractable. Suppose D1, ..., Dk are all the prime implicants of B, we have B⊢φ, for any φ iff for every prime implicant Di, Di⊢φ.

Now we define weighted prime implicants of a PKB. Let us first define weighted prime implicants for PKB B = {(φ1, a1), ..., (φn, an)} where φi are clauses. For a more general PKB, we can decompose it to an equivalent PKB whose formulae are clauses by the min-decomposability of necessity measures, i.e., N(∧i=1,kφi)≥m⇔∀i,N(φi)≥m.

Let B = {(φ1, a1), ..., (φn, an)} be a PKB where φi are clauses. A weighted implicant of B is D = {(ψ1, b1), ..., (ψk, bk)}, a PKB, such that D ⊢π B, where ψi are literals. Let D and D ′ be two weighted implicants of B, D is said to be more specific than D ′ iff D̸ =D ′ , D ′∗⊆D ∗ and ∀(ψi, ai)∈D, ∃(ψi, bi)∈D ′ with bi≤ai.

Definition 4 Let B = {(φ1, a1), ..., (φn, an)} be a PKB where φi are clauses. A weighted prime implicant (WPI) of B is D such that

1. D is a weighted implicant of B
2. ̸ ∃ D ′ of B such that D is more specific than D ′ .

Let us look at an example to illustrate how to construct WPIs.

Example 1 Let B = {(p, 0.8), (q∨r, 0.5), (q ∨ ¬s, 0.6)} be a PKB. The WPIs of B are D1 = {(p, 0.8), (q, 0.6)}, D2 = {(p, 0.8), (r, 0.5), (¬s, 0.6)}, and D3 = {(p, 0.8), (q, 0.5), (¬s, 0.6)}.

The WPI generalizes the prime implicant.

Proposition 1 Let B = {(φ1, 1), ..., (φn, 1)} be a PKB which contains formulae with weight 1, i.e., B is a classical knowledge base. Then D is a WPI of B iff D is a prime implicant of B.

However, given PKB B, if D is a WPI of B, then D ∗ is not necessarily a prime implicant of B ∗ . A counterexample can be found in Example 1, where D3 is a WPI, but D ∗ 3 = {p, q, ¬s} is not a prime implicant of B ∗ .

The following proposition says that WPIs can be used to compile a PKB.

Proposition 2 Let B be a PKB. If D1,...,Dn are all the WPIs of B, then for any formula φ, we have,

Next we give some justification for the WPI.

First of all, to measure information in a single classical knowledge base (this knowledge base may be inconsistent), most of the current methods are based on the models of the knowledge base [Hunter, 2002; Lozinskii, 1994]. In [Hunter, 2002], the degree of inconsistency is measured based on the model of an inconsistent knowledge base in the framework of quasi-classical logic. In [Lozinskii, 1994], a quasi-model of an inconsistent knowledge base, which is a maximal consistent subbase of the knowledge base, is defined to measure information for inconsistent sets. By Definition 4, each WPI can be interpreted as a partial truth assignment. Suppose p is an atom and D is a WPI, then (p, a)∈D means that there is an argument for p in D with certainty degree a, and (¬p, b)∈D means that there is an argument against p in D with certainty degree b, while φ̸∈D ∗ means the truth value of φ is undetermined in D. By Proposition 2, a WPI can be viewed as a partial model of a possibilistic knowledge base. This is consistent with the methods in [Hunter, 2002; Lozinskii, 1994].

Second, when all the formulae in a PKB have the same weight 1, a WPI is a prime implicant. In classical logic, a classical model is often used to define the distance between two knowledge bases [Dalal, 1988]. However, classical models are not suitable for us to define the quantities of agreement between knowledge bases because a classical model must assign a truth value to every atom in the knowledge bases. Let us look at the example in the introduction again. The only model for B1 is w = {φ, ψ} and there are two models for B3, i.e., w1 = {¬φ, ψ} and w2 = {¬φ, ¬ψ}. B1 and B3 weakly agree on ψ because only B1 supports ψ. However, by comparing w with w1 or comparing w with w2 we cannot get such a conclusion. In contrast, a prime implicant can be viewed as a partial truth assignment. That is, only some of the atoms are assigned truth values. Given a prime implicant D of B, a three-value semantics can be associated with it as follows:

In the example, B1 has one prime implicant D1 = {φ, ψ} and B3 has one prime implicant D2 = {¬φ}, where D2 does not contain any information on ψ; so the quantity of weak agreement between D1 and D2 is 1. As a consequence, the weak agreement between B1 and B3 is 1, which is consistent with our analysis above.

3.2 Quantity of conflict and quantities of agreement

In this section, we will measure the quantities of conflict and agreement between two PKBs based on the WPI.

First we define the quantity of conflict between two WPIs.

Definition 5 Let B1 and B2 be two PKBs. Suppose C and D are WPIs of B1 and B2 respectively, then the quantity of conflict between C and D is defined as

When all the weights are 1, qCon(C,D) is the cardinality of the set of atoms which are in conflict in C∪D.

Definition 6 Let B1 and B2 be two PKBs. Suppose C and D are the sets of WPIs of B1 and B2 respectively, then the quantity of conflict between B1 and B2 is defined as

The quantity of conflict between B1 and B2 measures the minimum amount of information in conflict between them.

WPIs of B1 are C1 = {(¬p, 0.8), (¬q, 0.6)} and C2 = {(¬p, 0.8), (r, 0.6)}, and the WPIs of B2 are D1 = {(p, 0.7), (q, 0.5)} and D2 = {(¬r, 0.7), (q, 0.5)}. It is easy to calculate that qCon(C1,D1) = 1.2, qCon(C1,D2) = 0.5, qCon(C2,D1) = 0.7, qCon(C2,D2) = 0.6. Therefore, the quantity of conflict between B1 and B2 is 0.5.

Proposition 3 Let B, B1 and B2 be three PKBs. If B1⊆B2, then QCon(B, B1) ≤QCon(B, B2).

Proposition 3 tells us that the quantity of conflict between two PKBs will increase (not strictly) when one of them has some new information added.

Let X be a set of classical propositional formulae. Let I(X) be the set of interpretations of X delineated by the atoms used in X (i.e. I(X) = 2 Atoms(X) , where Atom(X) denotes the set of atoms appearing in X). Let M(X, Y ) be the set of models of X that are in I(Y ). That is, M(X, Y ) = {w|=∧X|w∈I(Y )}. The Dalal distance [Dalal, 1988] between two models wi, wj of a classical formula is the Hamming distance between them, i.e., Dalal(wi,wj) = |wi - wj | + |wj - wi|.

Proposition 4 Let B1 and B2 be two consistent classical knowledge bases. Let Dalal (B1,B2) = min {Dalal(wi , wj )|wi∈M(B1, B1∪B2), wj ∈M(B2, B1∪B2)}. Then we have

Proposition 4 is very important, because it reveals that our quantity of conflict coincides with the Dalal distance in classical logic. Therefore, the quantity of conflict QCon(B1,B2) can be taken as a generalization of the Dalal distance.

Definition 7 Let B1 and B2 be two PKBs. Suppose C and D are WPIs of B1 and B2 respectively, then the quantity of strong agreement between C and D is defined as

When all the weights are 1, qCon(C,D) is the cardinality of the set of literals that are in both C and D.

Definition 8 Let B1 and B2 be two PKBs. Suppose C and D are the sets of WPIs of B1 and B2 respectively, then the quantity of strong agreement between B1 and B2 is defined as

The quantity of strong agreement between B1 and B2 measures how much information is supported by both B1 and B2.

Example 3 (Continue Example 2) By Equation 4, we have qSA(C1,D1) = qSA(C1,D2) = 0 and qSA(C2,D1) = qSA(C2,D2) = 0. Therefore, the quantity of strong agreement between B1 and B2 is QSA(B1, B2) = 0.

Definition 9 Let B1 and B2 be two PKBs. Suppose C and D are WPIs of B1 and B2 respectively, then the quantity of weak agreement between C and D is defined as

When all the weights are 1, qCon(C,D) is the cardinality of the set of literals which are in only one of C or D.

Definition 10 Let B1 and B2 be two PBKs. Suppose C and D are the sets of WPIs of B1 and B2 respectively, then the quantity of weak agreement between B1 and B2 is defined as

The quantity of weak agreement between B1 and B2 measures the information supported by only one knowledge base and unknown to the other.

Example 4 (Continue Example 2) By Equation 6, we have qWA(C1,D1) = 0, qWA(C1,D2) = 1.5, and qWA(C2,D1) = 1.1, qWA(C2,D2) = 1.3. Therefore, the quantity of weak agreement between B1 and B2 is QWA(B1, B2) = 1.5.

The function QWA is not monotonic with regard to the subset relation, as shown below

Example 5 Let B1 = {(p, 1)} and B2 = {(q, 1)}, then QWA(B1,B2) = 2. However, the quantity of weak agreement between B3 = {(p, 1), (p → ¬q, 1)} and B2 is QWA(B2, B3) = 1, where B1⊆B3.

Based on the quantity of conflict and quantities of agreement, we can define the following relationships between two knowledge bases B1 and B2 as

• B1 and B2 are said to be totally in conflict iff Qc(B1,B2) > 0 and QSA(B1,B2) = QWA(B1, B2) = 0.
• B1 and B2 are totally in agreement iff QCon(B1, B2) = QWA(B1, B2) = 0 and QSA(B1, B2) > 0.
• B1 and B2 are partially in conflict iff QCon(B1,B2) > 0 and QSA(B1, B2) + QWA(B1, B2) > 0.

3.3 Degree of conflict and degrees of agreement

In this subsection, we will define a degree of conflict and two degrees of agreement between two PKBs. The degree of conflict measures the extent to which two knowledge bases are in conflict. It was first introduced in [Hunter, 2004] to measure the believability of arguments.

Definition 11 Let B1 and B2 be two self-consistent knowledge bases, and Dalal(B1,B2) be the Dalal distance between B1 and B2. The degree of conflict between B1 and B2, denoted as C(B1,B2), is defined as follows:

Although this definition gives a method to measure the degree of conflict, it can sometimes overestimate the degree of conflict between two knowledge bases, because it doesn't distinguish the influences of strong agreement and weak agreement. For example, let us consider two pairs of knowledge bases (B1,B2) and (B ′ 1 ,B2), where B1 = {p, q, r}, B2 = {¬p, q, r} and B ′ 1 = {p}. Although the quantity of conflict between B1 and B2 is 1, the quantity of strongly agreement between them is 2. This means B1 and B2 have more in agreement than in conflict. In contrast, although the quantity of conflict between B ′ 1 and B2 is also 1, but with DSA(B ′ 1 ,B2) = 0 and DWA(B ′ 1 ,B2) = 2, the degree of conflict between B ′ 1 and B2 should be higher than that between B1 and B2. However, by Equation 8, C(B1,B2) = C(B ′ 1 ,B2) = 1/3. This is not reasonable.

We propose the following revised definition of the degree of conflict.

Definition 12 Let B1 and B2 be two PKBs. Let C and D be WPIs of B1 and B2 respectively. AtomC(C,D) denotes the cardinality of the set of atoms which are in conflict in C∪D. Then the degree of conflict between C and D is defined as

where λ ∈ (0, 1] is used to weaken the influence of the quantity of weak agreement on the degree of conflict. In the following, we always assume that λ = 0.5, that is, the quantity of weak agreement only has "half" as much the influence on the degree of conflict as the quantity of strong agreement.

Definition 13 Let B1 and B2 be two PKBs. Suppose C and D are the sets of WPIs of B1 and B2 respectively, then the degree of conflict between B1 and B2 is defined as

The advantage of our degree of conflict can be seen from the following example.

Example 6 Let us consider a dialogue between three people John, Mary, and Gary. They are discussing "whether Italy is the best football team in the world "(p) and "whether the best forwards are in Brazil" (q). John says "I think Italy is the best football team in the world and the best forwards are in Brazil", Mary says "No, I think France is the best team, but I agree with you that the best forwards are in Brazil", and Gary says "No, I think France is the best team". So the knowledge bases are John = {p, q}, Mary = {¬p, q} and Gary = {¬p}. By Equation 8, we have C(John,Mary) = C(John,Gary) = 1/2. This is not reasonable, because John and Mary agree on q, the degree of conflict between them should be less than the degree of conflict between John and Gary. In contrast, we have Dc(John,Mary) = 1/2 and DCon(John,Gary) = 2/3, so Dc(John, Mary) < Dc(John, Gary).

Proposition 5 Let B1, B2 be two classical knowledge bases. Suppose C(B1,B2) and DCon(B1,B2) are the degrees of conflict defined by Definition 11 and Definition 13 respectively. Then C(B1,B2)≥DCon(B1,B2).

Similarly, we can define the degree of strong agreement. We hold that the influence of the quantity of conflict on the degree of strong agreement is more than that of the quantity of weak agreement.

Definition 14 Let B1 and B2 be two PKBs. Let C and D be WPIs of B1 and B2 respectively. AtomSA(C, D) denotes the cardinality of the set of atoms which are included in both C and D. Then the degree of strong agreement between C and

where λ ∈ (0, 1] is used to weaken the influence of the quantity of weak agreement on the degree of conflict. As in Definition 12, we usually take λ = 0.5.

Definition 15 Let B1 and B2 be two PKBs. Suppose C and D are the sets of weighted prime implicants of B1 and B2 respectively, then the degree of strong agreement between B1 and B2 is defined as

Example 7 Let B1 = {(p, 0.8), (q ∨ r, 0.4), (p → s, 0.5)} and B2 = {(p ∨ ¬r, 0.8), (q, 0.6), (¬s, 0.7)}. The WPIs of B1 are C1 = {(p, 0.8), (q, 0.4), (s, 0.5)} and C2 = {(p, 0.8), (r, 0.4), (s, 0.5)}, and the WPIs of B2 are D1 = {(p, 0.8), (q, 0.6), (¬s, 0.7)} and D2 = {(¬r, 0.8), (q, 0.6), (¬s, 0.7)}. So dSA(C1,D1) = 0.48, dSA(C1,D2) = 0.17, dSA(C2,D1) = 0.4, dSA(C2,D2) = 0. Therefore, DSA(B1, B2) = 0.48.

The degrees of conflict and strong agreement are related to each other.

Proposition 6 Let B1 and B2 be two PKBs. Then their degree of conflict and degree of strong agreement cannot be greater than 0.5 at the same time, i.e., if DCon(B1,B2) > 0.5, then DSA(B1,B2)≤0.5.

We can also define the degree of weak agreement.

Definition 16 Let B1 and B2 be two PKBs. Let C and D be WPIs of B1 and B2 respectively. AtomWA(C,D) denotes the cardinality of the set of atoms which are included in only one of C and D but not both. Then the degree of weak agreement between C and D is defined as

In Definition 16, the quantity of conflict and quantity of strong agreement have the same influence on the degree of weak agreement. When both B1 and B2 are classical knowledge bases, we have dWA(C, D) = AtomWA(C,D) |Atom(C∪D)| .

Definition 17 Let B1 and B2 be two PKBs. Suppose C and D are the sets of WPIs of B1 and B2 respectively, then the degree of weak agreement between B1 and B2 is defined as

Example 8 (Continue Example 7) By Definition 16, we have dWA(C1,D1) = 0, dWA(C1,D2) = 0.55, dWA(C2,D1) = 0.3, dWA(C2,D2) = 0.48. So the degree of weak agreement between B1 and B2 is 0.55.

Proposition 7 Let B1 and B2 be two possibilistic knowledge bases. If dWA(B1, B2) > 0.5, then dCon(B1, B2) < 0.5 and dSA(B1, B2) < 0.5.

Proposition 7 shows that if the degree of weak agreement between two knowledge bases is large, i.e., greater than 0.5, then both the degree of conflict and degree of strong agreement between them should be small, i.e., less than 0.5.

4 Impact of Measures of Conflict and Agreement

4.1 Choice of combination operators

Many operators have been proposed for merging PKBs. Given two PKBs B1 and B2 with possibility distributions πB1 and πB2 respectively, the semantic results of their combination by a T-norm tn and a T-conorm ct are

The syntactic results associated with πtn and πct are respectively the following PKBs [Benferhat et al., 2002]:

If we require that the result of the combination be a consistent knowledge base, then the T-norm based operator cannot be used when there is a conflict between B1 and B2. In this case, we can only use a T-conorm based operator.

Typical T-norm operators are the minimum operator, the product operator and the Łukasiewicz T-norm (tnŁ for short) (max(0, a + b - 1)). The duality relation respectively yields the following T-conorm: the maximum operator, the probabilistic sum (ctps for short) (a+b-ab), and the bounded sum (ctbs for short) (min(1, a + b)).

Although some criteria to choose between merging operators have been given in [Benferhat et al., 1997; 2002], these criteria are not enough.

Suppose two PKBs B1 and B2 are consistent, then the degree of conflict between them must be 0 and at least one of the degrees of agreement is greater than 0. If the degree of strong agreement between B1 and B2 is very high, then B1 and B2 share beliefs on most of the topics. In this case, it is advisable to combine them using an operator with higher reinforcement effect, for example, the Łukasiewicz t-norm max(0,a+b-1). However, if the degree of strong agreement between B1 and B2 is low and the degree of weak agreement between them is very high, it is advisable to combine them using the minimum operator which does not have any reinforcement effect.

Suppose B1 and B2 are in conflict, we usually use a Tconorm to combine them. When the degree of conflict between B1 and B2 is very high, then B1 and B2 have mostly different beliefs and we can choose the "bounded sum" operator which has a high counteract effect. On the other hand, if the degree of conflict between B1 and B2 is very low, we can choose the maximum which does not have any counteract effect.

More formally, we have the following criteria to choose between merging operators.

Merging operators selection criterion: Let ⊕1 and ⊕2 be two operators applied to merge A and B, and C and D respectively, then for all a, b∈[0, 1],

Example 9 Let B1 = {(p, 0.6), (q ∨ ¬r, 0.7), (s, 0.6)} and B2 = {(p, 0.5), (q, 0.4), (s, 0.4)}, where DCon(B1,B2) = 0 and DSA(B1,B2) = 0.43. The merging operator here should be the product operator, and the result of merging is B = {(p, 0.6), (q∨¬r, 0.7), (s, 0.6), (p, 0.5), (q, 0.4), (s, 0.4), (p, 0.8), (p∨q, 0.76), (p∨s, 0.76), (p∨q∨¬r, 0.85), (q∨¬r, 0.88), (q∨¬r∨s, 0.88), (p∨s, 0.8), (q∨s, 0.76), (s, 0.76)}. However, if we use a Lukasiewicz t-norm, the result of merging is B ′ = {{(p, 0.6), (q∨¬r, 0.7), (s, 0.6), (p, 0.5), (q, 0.4), (s, 0.4), (p, 1), (p∨q, 1), (p∨s, 1), (p∨q∨¬r, 1), (q∨¬r, 1), (q∨¬r∨s, 1), (p∨s, 1), (q∨s, 1), (s, 1)}}. In B ′ , the weights of formulae p and s are reinforced to 1. However, the certainty degrees of p and s are not high in both B1 and B2. Moreover, B1 and B2 are not in strong agreement with each other because DSA(B1,B2) = 0.43. So it is not reasonable to increase the weights of p and s to the highest certainty degree 1. In contrast, in B, p and s have certainty degrees of 0.8 and 0.76 respectively. Therefore the result of the product operator reflects the reinforcement of B1 and B2 more accurately than that of the Lukasiewicz t-norm.

4.2 Ordering sources

In this section, we define an ordering relation to compare different knowledge bases based on the degree of conflict.

Definition 18 Let Bi, Bj, B be three PKBs. A closeness relation ⪯B with regard to B is defined as.

Bj is closer to B than Bi to B (Bi⪯BBj) iff Bj has less quantity of conflict and more quantities of agreement with B than Bi. If Bi⪯BBj, then we may view Bj is less problematic or more reliable than Bi with regard to B.

Example 10 Let B1 = {(¬p, 0.8), (¬q, 0.5), (¬r ∨ s, 0.7)}, B2 = {(¬p, 0.8), (¬q, 0.5), (¬r, 1), (s, 0.7)}, and B = {(p∨q, 0.8), (¬s ∨ r, 1)}. Since DCon(B1,B) = 0.22 < 0.41 = DCon(B2, B), so B2⪯BB1.

5 Conclusion

The main contribution of this work is that we not only measure the conflict between two prioritized knowledge bases but also measure their agreement in two ways. We defined the quantity of conflict and two quantities of agreement. The quantity of conflict is a generalization of the Dalal distance. We then defined the degree of conflict and degrees of agreement based on both the quantity of conflict and the quantities of agreement. We have shown that the definition of degree of conflict is more reasonable than that defined in [Hunter, 2004]. The measures of conflict and agreement can be very useful in many applications, such as belief merging, argumentation and heterogeneous source integration and management. Another potential application of the measures of conflict is to belief revision as we have shown that the quantity of conflict generalizes the Dalal distance.

We didn't touch the computational issue in this paper. It is clear that the computations of measures of conflict and agreement defined in Section 3.2 and 3.3 depend on the computation of WPIs. It has been shown in [Bittencourt et al.,

2004] that the computation of the set of prime implicants of a formula represented by conjunctive normal form is NPcomplete using a transformation algorithm in [Bittencourt et al., 2003]. Given a PKB B = {(φ1, a1), ..., (φn, an)} where φi are clauses, it is expected that the computation of all the WPIs of B is also NP -complete by generalizing the transformation algorithm. This problem will be discussed in a future paper.