Quantifying information and contradiction in propositional logic through test actions

1 Introduction

Information and contradiction are two fundamental aspects of knowledge processing. Quantifying them is an important issue when reasoning about beliefs (or preferences) stemming from one or different sources. Here are some contexts where quantifying information and contradiction is relevant:

• diagnosis and testing. In model-based diagnosis, some initial assumptions that each component works correctly are made; these assumptions may conflict with actual observa­ tions. Measuring the conflict of the resulting base may be a good hint about how hard it will be to identify the faulty com­ ponents.
• preference elicitation. In the interactive process of elicitat­ ing the preference profile of an individual (user) about a set of possible alternatives, it is not unfrequent that contradictory preferences arise. In this situation, it is useful to quantify and localize the contradictions as well as the information about the user's preferences, so as to be in position to choose the next questions to ask.
• belief merging. In this framework, degrees of information and contradiction can be the basis on which one can decide whether to take or not into account the data conveyed by an agent. If the degree of contradiction of the data given by an agent is high, it may be relevant to reject the information, since there is a significant evidence that the source is not reli­ able; however, this must be balanced by the quantity of infor­ mation furnished by the agent, especially when she also gives some important and uncontroversial pieces of information.
• group decision making. Contradictions arise frequently

Pierre Marquis

CRIL - Universite d' Artois F-62307 Lens - France

marquis®cril.univ-artois.fr

when trying to reach a compromise among several agents who have possibly conflictual preferences about a common deci­ sion (like voting, resource sharing, public goods buying). In this context, not only it is relevant to compute a global degree of conflict (among the set of agents) but also degrees of con­ flicts associated with small groups of agents (coalitions) so as to localize as precisely as possible where the conflicts are.

Now, what do "degree of information" and "degree of con­ tradiction" mean? There is no consensus about it. The main features shared by existing definitions (and there are not nu­ merous, cf. Section 7) is that ( 1) such degrees are numerical values, and (2) they vary depending on the representation lan­ guage. Thus, one may consider a as fully informative in the case where a is the single atomic proposition of the language but surely not fully informative when the vocabulary also con­ tains b (provided that a and bare independent propositions).

In this paper, our point of view is that it is inadequate to quantify the information/contradiction conveyed by some data without considering at the same time a set of available actions and a goal to be reached. Accordingly, our degrees of information and contradiction are defined in an "active" way. Acting so as to reduce inconsistency or to gain infor­ mation often relies on performing knowledge-gathering ac­ tions (also called tests). We consider that the degree of in­ formation of an information base is based on the number (or the cost) of actions needed to identify the truth value of each atomic proposition (the lower the cost the more informative the base); and that the degree of contradiction of an infor­ mation base is based on the number (or the cost) of actions needed to render the base classically consistent. Thus, both degrees are dependent on the language but also on the given set of tests and the way plans costs are computed.

The rest of this paper is organized as follows. After some formal preliminaries in Section 2, we present our framework in Section 3. In order to show the generality of our frame­ work, we instantiate it to three different propositional log­ ics: classical logic (Section 4), the paraconsistent logic LPm (Section 5) and a syntax-based approach to inconsistency handling (Section 6). Related work is given in Section 7, and some conclusions in Section 8.

2 Formal preliminaries and notations

We consider a propositional language Lps based on a finite set of propositional symbols P S and a set of connectives that may vary depending on the logic used. Well-formed formulas are denoted by r.p, '1/J, etc. The available information is repre­ sented by a formula I: of .Cps (called information base).

Since we wish to keep a reasonable level of generality, we do not want to commit right now to a particular propositional logic. Indeed, flexibility is a major feature of our framework, and it is essential at least for two reasons. On the one hand, classical logic is inadequate to handle contradiction: exfalso quodlibet sequitur (a single, local contradiction is sufficient to pollute the whole information base). On the other hand, there is no unique, fully accepted, logic for reasoning under inconsistency. This is reflected by the various approaches that can be found in the literature under different names like belief revision, merging, paraconsistent logics, etc.

.Cps is required to possess the following ingredients:

1. A consequence relation FL on .Cps x .Cps.
2. An acceptance functionAL ~ .Cps x .Cps: AL(I:, r.p) means that given the information base I:, r.p is accepted as a true information (we say that I: accepts r.p). By de­ fault, acceptance is defined by: AL(I:, r.p) iff (I: FL r.p and I: ~ L ·r.p ). We say that I: is informative about r.p iff exactly one of AL(I:, r.p) or AL(I: , ·r.p) holds, and that I: is fully informative iff for any r.p E .Cps, I: is infor­ mative about r.p.
3. A contradiction indicator CL ~ .Cps x .Cps: if C L(I:, r.p) holds, then we say that I: is contradictory about r.p. By default, we define CL(I:, r.p) iff (I: F L r.p and I: F L ·r.p ). I: is said to be contradiction-free iff for every r.p E .Cps, we do not have CL(I:, r.p).
4. A weak revision operator* : .Cps x .Cps __, .Cps: I:* r.p represents the new information base obtained once taking account of the observation r.p into the informa­ tion base I:. For the sake of generality, we are not very demanding about*· The only requirement is that I:* r.p F L r.p, which expresses that our tests are assumed reliable (each test outcome must be true in the actual world) 1 . In the following we will simply refer to those operators as revision operators (omitting the weak). It would be interesting to explore in more details what hap­ pens when one puts more requirements on* (this is left for further research).

3 Degree of ignorance and degree of contradiction

In this section, we give general definitions of degrees of con­ tradiction and ignorance, i.e., of lack of information, which are to a large extent independent of the logic chosen to repre­ sent information. These definitions will be specified further in Sections 4 to 6 where the logic will be fixed.

Definition 3.1 (test contexts) A test context CcPs (w.r.t. .Cps) is a pair (T, c) where T is a finite set of tests and c is a cost function from T to N*. The outcome to any test t.., E T is one of r.p, ·r.p, where r.p E .Cps. We say that t.., is the test about r.p, and we assume w.l.o.g. that at most one test t.., ofT is about r.p for each r.p E .Cps. A context is stan­ dard iff 'tit.., E T, we have c( t..,) = 1 (every test has a unit cost). A context is universal iff for every r.p E .Cps, there is a test t.., E T. A context is atomic iff the testable formulas are exactly the atomic propositions (tx E T iff x E P S ).

1 While this condition corresponds to the "success" postulate in the AGM framework [Alchourr6n eta/., 1985], we do not ask our operators to be AGM ones, especially because the AGM framework is not suited to characterize the revision of an inconsistent formula.

Definition 3.2 (test plans, trajectories) Given a test context CcPs· a test plan 1r is a finite binary tree; each of its non­ terminal nodes is labelled with a test action t..,; the left and right arcs leaving every non-terminal node labelled with t.., are respectively labelled with the outcomes r.p and ·r.p. An (outcome) trajectory (o1 , ... , on) with respect to 1r is these­ quence of test outcomes on a branchof7r. The cost of a trajec­ tory (o1 , ... , on) with respect to 1r is defined as I:f= 1 c(t..,.), where each t..,, is the test labelling the node of 1r reached by following the path (o1, ... , oi-d from the root of 1r .

Definition 3.3 (disambiguation, purification) Let 1r be a test plan and I: the initial information base.

• The application of7r on I: is the tree apply(1r, I:), iso­ morphic to 1r, whose nodes are labelled with informa­ tion bases defined inductively as follows:
• the root E of apply( 1r, I:) is labelled with I:( E) = I:;
• letn be a nodeofapply(7r, I:), labelled with the information base I: ( n ), whose corresponding node in 1r is non-terminal and labelled with t..,; then n has two children in apply(1r, I:), labelled respectively with I:(n) * r.p and I:(n) * ·r.p.
• 1r disambiguates r.p given I: iff for every terminal node n of apply(1r, I:), I:(n) is informative about r.p (i.e. , either AL(I:, r.p) or AL(I:, ·r.p)). 1r (fully) disambiguates I: iff it disambiguates all formulas of .Cps, i.e., iff for any ter­ minal node n of apply(1r, I:), I:(n) is fully informative.
• 1r purifies r.p given I: iff for every terminal node n of apply( 1r, I:), I:( n) is not contradictory about r.p (i.e., not CL(I:(n), r.p)). 1r (fully) purifies I: iff it eliminates all contradictions in I:, i.e., iff for any terminal node n of apply(1r, I:), I:(n) is contradiction-free.

Clearly enough, it can be the case that there is no plan to purify or disambiguate a formula; especially, there is no plan for purifying the constant .l (false) in any of the three logics considered in the following.

In our framework, degrees of ignorance and contradiction are defined in a uniform way: the degree of ignorance (resp. of contradiction) of I: measures the minimal effort necessary to disambiguate (resp. to purify) I:.

Definition 3.4 (degree of contradiction, of ignorance)

Let us define the cost c( 1r) of a test plan 1r as the maximum of the costs of its trajectories. Then

• The degree of contradiction of I: is defined by dc(I:) = min({c(1r) l1r purifies I:}). When no plan purifies I:, we let dc(I:) = +oo.
• The degree of ignorance of I: is defined by d1 (I:) = min( { c( 1r) I 1r disambiguates I:}). When no plan disambiguates I:, we let d1(I:) = +oo.

Clearly, both degrees depend on the test context; by default, we consider the standard atomic context.

In the previous definition, we actually define pessimistic degrees of contradiction and ignorance (because the cost of a plan is defined as the maximum cost among its trajecto­ ries); this principle, consisting in assuming the worst out­ come, is known in decision theory as Wald criterion. Other criteria could be used instead, such as the optimistic crite­ rion obtained by replacing max by min. More interesting, the criterion obtained by first using max and then min for tie-breaking, or the leximax criterion, allow for a better dis­ crimination than the pure pessimistic criterion. The choice of a criterion is fairly independent from the other issues dis­ cussed in this paper, which gives our framework a good level of flexibility and generality. Due to space limitations, how­ ever, we consider only the pessimistic criterion in the rest of the paper.

The definitions below concern the cost of being informa­ tive about a formula cp (resp. of getting rid of contradictions about cp) given an initial information base 2:.

Definition 3.5 (disambiguation cost, purification cost)

• The disambiguation cost of cp given 2:, denoted by Co(I:, cp), is the minimum cost of a test plan applied to 2: and disambiguating cp.
• The purification cost of cp given 2:, denoted by C p (I:, cp ), is the minimum cost of a test plan applied to 2: and pu­ rifying cp.

The disambiguation cost of cp given 2: can be seen as the price one is ready to pay for being informed about cp. The pu­ rification cost of cp given 2: is a bit less intuitive: in a database context, for instance, it represents the cost that the database holder is ready to pay to ensure that the database does not contain any contradictory information about a given formula.

Proposition 3.1 The degrees defined above are related as follows:

• d1(I:) ~ de (I:);
• Co(I: ,cp) ~ Cp(I: ,cp);
• Co(I: , cp) = Co(I:, ·cp);
• d1(I:) ~ Co(I:, cp);
• Cp(I:, cp) = Cp(I:, · cp);
• de(I:) ~ Cp(I: , cp).

4 Case study 1: classical logic

In this section, we fix .Cps to classical propositional logic C L, which means that we fix the following:

• The language of C L is built up from the connectives /\, V, ...,, __. and the constants T, l_;
• Interpretations are mappings from PS to {T, F} and the consequence relation is defined as usual by 2: l=eL cp iff Mode L(I:) ~ ModeL('~/!), where Mode L(I:) denotes the set of classical models of 2: .

Clearly enough, AeL(I:, cp) holds iff 2: l=e L cp and 2: is consistent; and GeL( I: , cp ) holds iff 2: is inconsistent. Fi­ nally, let 2: * cp = 2: 1\ cp (i .e., the revision operator is simple expansion).

Example 4.1 Figure 1 reports a test plan of minimal cost that fullydisambiguatesi: = (a v b) l\ (a __.c) (w.r.t. the standard atomic test context).

Accordingly, the degree of ignorance of 2: is 2 given the standard atomic context; as Figure 1 also shows, such a de­ gree can be strictly lower than the number of literals built up from P S that are not accepted by 2: (here, the information given by the test outcomes within the test plan are crucial).

(a v b) II (a_, c)

Proposition 4.1 Given any test context:

• Co(I:, cp) = 0 iff I: is consistent and (2: I= cp or 2: I= ·cp);
• if I: is inconsistent, then Co(I:, cp) = +oo;
• Co(I:, cp V '1/!) :::; Co(I:, cp) + Co(I:, '1/J);
• Co(I:, cp 1\ '1/!) :::; Co(I:, cp) + Co(I:, '1/J);
• d1(I:) :S 'l:xEPS Co(I:, x ).

Degrees of conflict and purification are not relevant when .Cps is classical logic, just because inconsistency is an ex­ tremely rough notion in classical logic. Indeed, we have:

Example 4.2 Let a, b be two (independent) atomic proposi­ tions we focus on. Starting from an information base rep­ resented by T (no contradiction, no information), stepwise expansions progressively lead to a base 2: having a single model over {a, b} like (a = T, b = T). In this situation, the degrees of ignorance and of contradiction (given the standard atomic context) are minimal (no contradiction, full informa­ tion). But each additional expansion that does not lead to an equivalent information base leads to an inconsistent one; for instance, the resulting base 2: * ·a has a maximal degree of contradiction. This is counterintuitive since it seems that a 1\ b 1\ ·a is both more informative and less contradictory than a 1\ b 1\ ·a 1\ ·b. This is not reflected by our degrees when classical logic is considered.

• d1( {T}) = 2, de ( {T}) = 0
• di({a}) = 1, de({a}) = 0
• di({a l\ b}) = O,de ({al\b})=O
• d1( {a 1\ b 1\ ·a}) = +oo, de( {a 1\ b 1\ ·a}) = +oo
• d1( { al\bl\ ·a/\ ·b}) = +oo, de ( { al\bl\ ·a /\ ·b}) = +oo

This example also shows that mere expansion is not a very satisfying revision operator. Indeed, since it does not enable to purify any inconsistent base (whatever the test context), expansion does not enable as well to disambiguate any incon­ sistent base. Furthermore, it may lead to degrees of contra­ diction (or purification costs) that are not intuitively correct. Thus, on the example, we have d1 ( {a 1\ b 1\ ·a}) = +oo , while given the standard atomic context, two tests are suffi­ cient to determine the actual world (over {a, b} ). The rea­ son of this discrepancy between what is expected and what is achieved is that expanding an inconsistent information base always leads to an inconsistent base, while it would be neces­ sary to restore consistency 2 for achieving purification and dis­ ambiguation in classical logic. Note that using AGM revision instead of expansion would not help a lot since AGM opera­ tors do not behave well when applied to inconsistent bases.

2 A way to do it consists in forgetting information [Lang and Mar­ quis, 2002] (possibly everything) in {a A b A -,a}.

5 Case study 2: the para consistent logic LP m

Paraconsistent logics have been introduced to avoid ex falso quodlibet sequitur of classical logic, hence handling incon­ sistent bases in a much more satisfying way. While many paraconsistent logics have been defined so far and could be used in our framework, we focus here on the LPm logic as defined in [Priest, 1991]. This choice is mainly motivated by the fact that this logic is simple enough and has an inference relation that coincides with classical entailment whenever the information base is classically consistent (this feature is not shared by many paraconsistent logics).

• The language of LPm is built up from the connectives /\, V, · , --+ and the constants T , ..L.
• An interpretation w for LPm maps each propositional atom to one of the three "truth values" F, B, T, the third truth value B meaning intuitively "both true and false". 3PS is the set of all interpretations for LPm. "Truth val­ ues" are ordered as follows: F <t B <t T.

• The set of models of a formula 1.p is ModLP( I.P ) = {wE 3PS I w(l.fJ ) E {T, B} }. Define w! = {x E PSI w(x ) = B}. Then min(ModLP(I.P)) ={wE ModLP(I.P) I ~w' E ModLP(I.P) s.t. w'! C w!}. The consequence relation is defined by E FLPm i.p iff m in(ModLP(E)) ~ ModLP(I.fJ) .
• The definitions of ALPm (E, l.fJ) and CLPm (E, l.fJ) are those by default; CLPm (E, I.P) holds only if E has no classical model.

Now, what about the revision operator? Actually, the issue of revision in paraconsistent logic has never been considered so far. Expansion is not satisfactory as a revision operator for LPm because it enables neither the purification task nor the disambiguation one when E has no classical model w (i .e., such that w(x) =f. B for each x E P S), whatever the test con­ text. Among the many possible choices, we have considered the following revision operator, defined model-theoretically (for the sake of brevity, we characterize only its restriction to the case the revision formula 1.p is a literall).

Let force(w, l) be the interpretation of 3PS defined by (for every literall = x or ·x):

Then the revision operator is defined by:

Example 5.1 Stepping back to Example 4.2, we can check that LPm leads to more intuitive values for the degrees of ig­ norance and contradiction of the bases we considered. Given the standard atomic test context, we now have:

• di( {T}) = 2, de( {T}) = 0
• di({a})=l,de ({a})=O
• d I ( {a 1\ b}) = 0, de ( {a 1\ b}) = 0
• d I ( {a 1\ b 1\ ·a}) = 1, de( {a 1\ b 1\ ·a}) = 1
• d I ( {a 1\ b 1\ ·a 1\ -,b}) = 2, de ( {a 1\ b 1\ ·a 1\ ·b}) = 2

Thus, starting from T, expansion (i. e. the logical strength­ ening of an information base) leads to more information up to a point where full information is reached, then progres­ sively to more contradiction and less information, up to an information base with full contradiction and no information.

Example 5.2 Let us now consider the base E = {a 1\ · a 1\ ((b 1\ c) V d)}. Figure 2 reports a plan of minimal cost (given the standard atomic context) which disambiguates E (the sub­ tree rooted below the ·a outcome is similar to the one of a and is not represented). Here, the degree of ignorance of E is 4 and the degree of contradiction ofE is 1 (after testing a there is no contradiction any more).

Contrariwise to expansion, this revision operator is ade­ quate to our objective:

Pr~osition 5.1 Every information base that has a model E 3P has a finite degree of ignorance and a finite degree of contradiction given any atomic or universal test context.

6 Case study 3: "syntax-based" information bases

Many approaches to reasoning under inconsistency make use of the selection of maximal consistent subsets of a belief base. This principle comes down to [Rescher and Manor, 1970] and is known under different names such as the possible-world approach [Ginsberg and Smith, 1988], assumption-based the­ ories [Poole, 1988], supernormal default theories [Brewka, 1989], syntax-based approaches [Nebel, 1991] etc. We retain the last name and call the logic SBL 3 ·

The language of SBL is defined as the set of all pairs E = (o, ~), where ~ = { 01, ... , On}; o, 01, .. . , On are propositional formulas from the language of C L. o represent the set of hard facts and o1 , . . . , On the defaults. Formulas of the form (o, 0) are called simple formulas and, slightly abus­ ing notations, are abbreviated into o - thus the language of S B L can be seen as an extension of that of classical logic. A

3 Saying that the approach is "syntax-based" actually means that { 'Pl, .. . , 'Pn} should not be identified with <p1 1\ ... 1\ <pn , or, in other words, that the comma is viewed as a (non truth-functional) connective.

maximal scenario of E is a subset 6.' of 6. such that a 1\ 6.' is consistent and there is no 6." ::J 6.' such that a 1\ 6." is consistent. We denote by M S(E) the set of all maximal sce­ narios of E.

The semantics of SBL is defined by a preference rela­ tion over classical interpretations. Let E = (a, 6. ). If w E 2Ps, we define Sat(w, E) = {i I w l=cL 8i}. For w,w' E ModcL(a), we say that w ~E w' iff Sat(w, E) 2 Sat(w', E) . Now, M odssL(E) = { w I w l=cL a and there is no w' l=cL a such that w' >E w }. Conse­ quence in SBL is defined byE l=sBL E' iff ModssL(E) ~ M odssL(E') - especially, if 'P is a simple formula, then E l=sBL 'P iff 'Pis a skeptical consequence of E in the sense of default logic.

Let 'P be a simple formula. Acceptance is defined by the default formulation. Equivalently, Ass£( (a, 6.), 'P) holds iff (a, 6. ) l=sBL 'P and a is consistent. Contradiction refers to maximal scenarios: CssL(E, 'P) iff M S(E) = 0 or there exists 6.', 6." E MS(E) such that a 1\ 6.' l=cL 'Panda 1\ 6." l=cL ''P· Lastly, (a, 6.)*'-P is defined as (aAi.p, 6.), i.e., the hard facts are expanded with the revision formula.

Example 6.1 E = (0, {a, ·a 1\ b, a____. c, ·c, c ____. a}). Here is a purification plan of minimal cost for E with respect to the standard atomic context. We start by testing a; E * ·a = ( ·a, 6.) is contradiction-free because it has a single maximal scenario {-,a 1\ b,a----> c,·c,c----> a}; E *a= (a,6.) is not contradiction-free because it has two maximal scenarios {a, a ----> c, c ----> a} and {a, ·c, c ----> a}; then testing c leads to E * (a 1\ c) and E * (a 1\ ·c), both being contradiction­ free. Hence, given the standard atomic context, dc(E) = 2 and d1(E) = 3 (since disambiguating b will require one additional test).

Proposition 6.1

• E is contradiction-free iff M S(E) is a singleton.
• E = (a, 6. ) is fully informative iff M S(E) is a singleton {6.'} and ModeL( a 1\ 6.') is a singleton.

Despite it mainly amounts to expansion of the hard facts, if the hard constraint a of E is true for sure in the actual world (i.e., it is consistent and consistency cannot be ques­ tioned by expansion with test outcomes), then E has a finite degree of contradiction and a finite degree of ignorance given any atomic or universal context.

7 Related work

To the best of our knowledge, only few proposals for a notion of degree of information can be found in the literature, and things are even worse to what concerns the notion of degree of contradiction. All existing approaches are stuck to specific propositional logics with the corresponding consequence re­ lations, which address only some aspects of the paraconsis­ tency issue, if any (as evoked previously, there is no undebat­ able paraconsistent inference relation).

Shannon's information theory [Shannon, 1948] provides the most famous approach on which notions of quantity of information can be defined, but it relies on the assumption that the available information is given under the form of a probability distribution; furthermore, it cannot directly ad­ dress inconsistent data. Interestingly, our definition of degree of information is general enough to recover classical entropy, applied to classical logic 4 .

Lozinskii [1994a] gives a set of properties that a measure of quantity of information should satisfy. Our degree of ig­ norance is fully compatible with Lozinskii 's requirements in several cases. The degree of information defined by Lozin­ skii corresponds to the notion in Shannon's theory, assuming a uniform distribution over the set of propositional interpre­ tations5. It is thus required that the input information base E has a classical model. [Lozinskii, 1994b] extends [Lozin­ skii, 1994a] by considering as well some inconsistent logi­ cal systems, through a more general notion of model. It is specifically focused on so-called quasi-models of the infor­ mation set E, which are the models of the maximal (w.r.t. ~) consistent subsets of E. This is sufficient to avoid the notion of degree of information to trivialize when applied to an inconsistent E (unless it is a singleton). However, no no­ tion of degree of contradiction is specifically introduced in Lozinskii's approach. He claims that "an inconsistent infor­ mation base always contains less semantic information than any of its maximal consistent subsets". In our point of view, this may lead to counterintuitive results. For instance, given P S = {a, b, c}, according to Lozinskii, {a} contains more information than {a 1\ ·a 1\ b 1\ c}. That is not always the case in our framework: it depends on the context under consider­ ation. Thus, while the degree of contradiction of the former is lower than the degree of contradiction of the latter, the de­ gree of information of the latter is greater than the one of the former (w.r.t. the standard atomic test context).

Wong and Besnard [200 1] criticize the syntax-sensitivity of Lozinskii's approach. In particular, the presence of tautolo­ gies in E may unexpectedly change the quantity of informa­ tion. As they note this can be easily repaired by considering the models of E over the set of variables on which E depends [Lang and Marquis, 1998], instead of the set of variables oc­ curring in E. Wong and Besnard also adhere to Lozinskii's definition of degree of information; what changes is the un­ derlying notion of quasi-model, since the paraconsistent logic they considered is quasi-classicallogic [Besnard and Hunter, 1995; Hunter, 2000].

[Knight, 2003] reports some other postulates for a mea­ sure of quantity of information. Our measure d1 does not satisfy all of them, even in simple cases (for space reasons, we cannot detail it here). This contrasts with the two mea­ sures introduced by Knight, which generalize in an elegant way Shannon's entropy-based measure to the case the infor­ mation base is an inconsistent set of formulas. However, both measures trivialize when the information set is an inconsis­ tent singleton.

The only two approaches we are aware of, which con­ sider (non-trivial) degrees of inconsistency defined for classical formulas (i .e., without additional information, like a preference preorder), are [Knight, 2002] and [Hunter, 2002]. Knight finds a set I: of classical formulas maximally a­ consistent whenever o: is the greatest number for which a probability measure P exists, satisfying P( r.p ) 2: o: for ev­ ery r.p E I:. Accordingly, his measure makes sense when the logic SBL is considered, but trivializes whenever I: is a singleton. Hunter appeals to quasi-classicallogic as a frame­ work for dealing with inconsistent information. Considering the minimal quasi-classical models of the information base I: (roughly, the "most classical" ones), Hunter defines the de­ gree of coherence of I: as the ratio between the amount of contradiction (conflict) and the amount of information (opin­ ion) of the formula. Such a degree of coherence does not always give what is expected. Consider for instance the two information sets I: = { e A · e, a V (b A c A d)} and I:' = { e A · e, (a A b) V ( c A d)}. [Hunter, 2002] shows that Coherence( I:) > Coherence( I:'). We feel it counterintu­ itive since the two bases shares the same contradiction e A ·e, which is not related to the other formulas of both bases 6 .

4 Let prr; be the probability distribution stating that all models of

L: over P S are equiprobable (and the other ones impossible), i.e., for any w f= L:, prr;(w) = IMod~L{E)I" The entropy of prr; is defined as H(prr;) = l::::wi=E -prr;(w).log2prr;(w) = log2IModcL(L:)I. Therefore, the integer upper part of H(prr;) is nothing but the min­ imal number of tests that have to be performed to identify the actual world given the standard universal test context.

5 Such a degree was already known by Kemeny [1953] and Hin­ tikka [1970] .

Finally, Hunter [2003] defines a degree of significance of the contradictions, which makes sense when some informa­ tion about the importance of potential conflicts is available.

8 Conclusion

The main contribution of the paper is a uniform action-based framework for quantifying both degrees of information and of contradiction. The framework is parameterized by a proposi­ tional logic (together with the corresponding notions of con­ sequence, acceptance, contradiction and a revision operator), a test context and an aggregation criterion for computing plan costs. These parameters enable a great flexibility.

There are many interesting notions that can be easily de­ fined in our framework but that we cannot mention here for space reasons. Let us note that through the notion of purifi­ cation plan, our approach for quantifying contradiction also allows to localize conflicts. Note also that notions of joint de­ grees and conditional degrees of information I contradiction can be easily defined. Another simple extension would con­ sist in taking advantage of additional knowledge about the sources of information and the origin of conflicts (e.g., in a diagnosis setting, it can be the case that the failure of a com­ ponent physically causes the failure of other components).

Many other extensions of our approach can be envisioned. For instance, coping with preferences over the goal variables (determining whether a holds is more important than deter­ mining whether b holds). Another possible extension con­ cerns the case where ontic actions are available and the objec­ tive is to let the actual world as unchanged as possible (i.e., we can execute invasive actions but we prefer not to do it).

Acknowledgements

The third author has been partly supported by the IUT de Lens, the Universite d' Artois, the Region Nord I Pas-de­ Calais under the TACT-TIC project, and by the European Community FEDER Program.

6 If we instantiate our framework with LPm logic (under standard atomic context), we get dc (I:) = dc (L:') = 1, d1(L:) = 5, and di (I:') = 4, showing that there is the same amount of contradiction in the two bases and that there is less information in I: than in I:'.