Possibilistic Logic, Preferential Models, Non-monotonicity and Related Issues

1 Introduction

For more than ten years, Artificial Intelligence· researchers have devoted a lot of efforts for developing various approaches to the handling of .incompl~te, uncertain or partially inconsistent knowledge I~ reasoning processes. At a superficial level a dichotomy IS usually ma~e between purely symbolic approaches and approaches whi~h rely ~n the use of numerical scales for grading uncertamty. This obvious and sometimes convenient distinction turns out to have a limited significance when we observe th~t the numerical and the non-numerical methods can deal With the same kind of examples and that there may exist more fundamental differences between two symbolic, or between two numerical approaches than between a symbolic and a numerical one in some cases ; see the comparative study by Lea Sombe [1990] on these points. ·

Moreover different kinds of unifying results have been provided at the theoretical level in the recent past years. On the symbolic side, Kraus, Lehmann and Magidor [1990], following pioneering works by Gabbay [19~5] a~d Makinson [1989], have studied non-monotonic logic systems from an axiomatic point of view. They have related these systems to the preference. relation-based lo~c ~dvocated by Shoham [1988] for unifymg non-monotonic m~ere~ce systems at th~ semantic level. Also on the symbohc .side, more recently, Makinson and �lirden~ors ha.ve estabhsh.ed connections between non-monotomc logic and behef revision mechanisms (see [Glirdenfors, 1990] for a summary sketch). They are based on so-called epistemic entrenchment relations [GWenfors, 1988].

On the numerical side, probabilistic semantics of defaults have been proposed by Geffner [1988] a~~ Pearl [1~88] ~n the basis of Adams [1975]'s logic of conditionals. This logic displays all properties of a well-behaved non-monotonic logic. Neufeld et al. [1990] also try to equip ~efaults with probabilistic semantics related to the con~~ation property "p favours q", i.e. the fact that the probability of as~rtion .q is strictly increased when the truth of a~sertion p .Is established. Besides, qualitative necessity relations [Dubois, 1986], whose unique numerical counterparts ~e neces~ity measures, are characterized by a system of axioms which was recently proved to be equivalent to the one characterizing epistemic entrenchment relations [Dubois and Prade, 1990b], where necessity measures are just the ~ual ~f possibility measures i~!J'oduced b~ ~d~h [1~78]. With. this result in mind, the abihty of possibdistic logic -a logic. of classical formulas weighted in terms of necessity measures- to deal with partially inconsistent knowledge bases and to exhibit in that case non-monotonic reasoning behaviors is not very surprizing [Dubois, Lang and Prade, 1989]. Be~ides, several researchers, including Goodman and Nguyen [1988], Dubois and Prade [1989 ·.. 19~0a] h~ve developed a new model of measll!e-free co.nditioning, .IJ?'mg to give a mathematical and a logical ~eanmg to co~~uonal objects q 1 p independently of the notion of probability, but still in agreement with this notion in the s~~se that Prob( q 1 p) can indeed be considered ~ the pro~ability of the entity q 1 p. As already suggested m Dubois and Pr~de [1989], there is more than an analogy between the logical calculus developed on conditional objects an~ no~­ monotonic consequence relation systems ; more precisely, It has been recently shown that there is a one-to-one correspondence between the inferenc.e rules governing ~e non-monotonic consequence relation "' and ordenng relationships between conditional objects equipped with a conjunction operation [Dubois and Prade, 1991]. Moreover conditional objects correspond to a qualitative view of conditioning which is compatible not only with probability but also with other uncertainty models including possibility measures and Shafer belief functions.

The aim of this paper is to pursue this exploration of the links between formalisms aiming at mechanizing reasoning under incomplete and uncertain information, by showing the close relationship between Shoham's preference relation­ based semantics and possibilistic logic ; this is not unexpected if we remember that possibilistic logic has a semantics [Dubois, Lang and Prade, 1989] in terms of a weight distribution on the set of worlds or interpretations, which clearly induces a total ordering among the possible worlds. More generally, possibilistic logic will be advocated as a simple numerical formalism for non-monotonic inference and belief revision which is in complete agreement with purely symbolic approaches.

In Section 2, after introducing the necessary background, we establish the link between Shoham's preference relation­ based semantics and conditional possibility measures. Section 3 shows that conditional possibilities enjoy properties similar to the ones of non-monotonic consequence relations. Section 4 relates conditional possibility measures to possibilistic logic and its semantics (which is itself in close relationship with epistemic entrenchment relations and belief revision processes as already said).

2 Preference logic and conditional possibility

Let ( al , A, v, -.) be a Boolean algebra induced by a set of classical propositions of interest. Let n be the set of atoms of al, i.e. the set of possible interpretations relative to al. n is assumed finite here for simplicity. If the proposition p is true in the interpretation CO E Q, we shall write CO I= p, which reads "co satisfies p". Starting with a preference relation denoted by c (co c co' reads co' is preferred over co) which equips n with a strict partial order, Shoham [1988] says that co preferentially satisfies p, written co l=c p, when

co 1= p and ~co·, co c co' and co' 1= p. Then preferential entailment is defined by Shoham [1988] as follows:

where p 1= c q reads "p preferentially entails q". In other words, p preferentially entails q iff the set of interpretations that make q true (i.e. the set of models of q) includes the preferred models of p, which has a fairly intuitive meaning. Note that if p is a contradiction (i.e. ~co. co 1= p), p l=c q trivially holds because the set of preferred models of p is empty. The intuitive appeal of preferential entailment is then lost in that particular situation.

Let 1t be a function from n to [0,1] called a possibility distribution on n that describes the fuzzy set of preferred interpretations. For each co e n, 1t assigns a numerical value which can be viewed as the assessment of a level of possibility or acceptability of interpretation co. 1t(CO) = 0 means that the interpretation co is totally impossible, totally excluded, while 1t(ro) = 1 only means that co is among the most plausible interpretations (there may be distinct co and co' such that 1t(ro) = 1t(ro')). Obviously, as soon as, 7t(ro) < 7t(ro'), we can say that co' is preferred to co, which will be written co c1t co', i.e. 1t induces a strict partial order on n (as well as a total order co £.1t co'<=> 1t(ro) ~ 1t(ro')). Then a possibility measure n is defined on al ' following Zadeh [1978], by V p e al, Il(p) = max{7t(ro) I co e nand co 1= p} (2) and Il(.L) = 0, II(T) = 1, where .L and T denote the bottom (contradiction) and the top (tautology) elements of al, respectively. The conditional possibility measure II( · I p) is defined as the maximal solution of the equation (first proposed by Risdal [1978]):

and II(.L I p) = 0. This solution has been first suggested in [Dubois and Prade, 1986] and reads :

since we always have II(p) ~ II(p A q) (indeed if co 1= p A q then co 1= p and II is monotonic with respect to entailment). Justifications for (3) can be found in Dubois and Prade [1990a] ; in any case, the meaning of (3) is intuitively clear since it looks like Bayes rule with product changed into min. In the framework of possibility theory, the choice of the maximal solution is based on the so-called minimum specificity principle (e.g. [Dubois and Prade, 1988]) which calls for the assignment of the greatest possibility degrees compatible with the constraint(s) under consideration. Indeed as already said the smallest the possibility degree, the stronger the information that it conveys (recall that 1t(ro) = 0 means that co is totally impossible while 1t(ro) = 1 only means that co is among the most plausible interpretations, but does not mean at all that we are (somewhat) certain that co is the right interpretation).

Let us observe that as soon as p entails q (i.e. V co, co 1= p => co 1= q) then p = p A q (where = denotes the equivalence) and thus II(p) = II(p A q) and II(q I p) = 1, which is satisfying. Let us also note that if 1 ~ II(p) > II(p A q) then II(q I p) = II(p A q) < 1. Moreover II(q I p) is defined even if II(p) = 0 and in that case II(q I p) = Il(-,q I p) = 1 when q i' .L, thus expressing total ignorance about q when p is impossible. By duality a so-called necessity measure N (e.g. [Dubois and Prade, 1988]) is associated with II. i.e.

which expresses that we become somewhat certain of something when the contrary turns out to be more or less impossible. (5) requires the normalization of 1t, 3 co e n , 7t(ro) = 1 which guarantees II(T) = 1. This also applies to conditional possibility measures, and yields

where p ~ q denotes material implication (-,p v q).

Let us show now that conditional possibility is in agreement with Shoham's preferential entailment

Definition 1 : co is said to be a 7t-preferential model of p e al {denoted co 1=1t p) if and only if co 1= p, Il(p) > 0, and :$ro' such that ro' 1= p and 7t(ro) < 7t(ro'). Lemma 1 : ro 1=1t p ¢:::> Il(p) = 7t(ro) > 0

Proof: obvious since Vro', ro' 1= p => 7t(ro') ~ 7t(ro). Q.E.D. The 7t-preferential entailment p 1=1t q is then defined by

This definition is equivalent to (1) where c has been changed into c1t and the condition Il(p) > 0 is forced. This extra condition enables preferential entailment to exclude the case when p is a contradiction.

Proof:

(7) ¢:::> Vro, (ro 1= p and Il(p) = 1t(ro) > 0) => ro 1= q

¢:::> ( ro, ro 1= p, Il(p) = 1t(ro) > 0} ~ ( ro, ro 1= q}

¢:::> Il(p) = Il(p" q) > Il(p" -,q) (since no preferential interpretation of p is an interpretation of -,q)

Thus given a possibility distribution 1t over the set of interpretations, the set. NMC(~) of non-monotonic consequences of a (consistent) knowledge base ~. viewed as a conjunction of (classical) formulas, will be defined by NMC(~),;. (q I Il(q I~)> Il(-,q I~)}. Our conventions suggest that NMC(~) = 0 when ~is inconsistent. It can be easily seen that Il(q I p) > IJ(--.,q I p) does not imply Il(q I p" r) > Il(-,q I p A r), since the supremum of 1t over the interpretations of p" q corresponds to interpretation(s) which do(es) not necessarily belong to the set of interpretations of p " q" r (recall that Il(qlp) > Il(--.,q I p) means that all the interpretations of p which maximize 1t are among the interpretations of q). This explains the non­ monotonic behavior ofll(q I p) when greater than Il(--.,q I p). Note that Il(q I p) > Il(--.,q I p) implies Il(q I p) = 1 (the converse being false). However if Il(q I p) < 1 then Il(q I p) = Il(p A q) and monotonicity is recovered.

An immediate corollary of Proposition 1 is obtained for necessity measures

i.e. p preferentially entails q (in the sense of the ordering induced by 1t) if we are at least somewhat certain about the truth of q in the context p. (8) is easily obtained noticing that Il(q I p) > Il(--.,q I p) is equivalent to IJ(--.,q I p) < 1, since Il(q I p) = 1 in that case. Note also that N(q I p) > 0 => N(--.,q I p) = 0 due to (5). We now investigate the behavior of conditional possibility from a proof-theoretic point of view and mention its relation to the framework of conditional objects.

3 Conditional possibility and the non-monotonic consequence relation

Starting from a logical point of view, Gabbay [1985] proposed several properties that a non-monotonic deduction operation fv- should satisfy, and especially the cut and the restricted or cautious monotonicity, i.e.:

Note that in the above patterns of inference, the terms p fv- r and p " q fv- r are exchanged, as pointed out by Makinson [1989]. It is then possible to put these two patterns together and claim that given p fv- q, the non-monotonic deductions p A q fv- r and p fv- r are equivalent. This is what Makinson [1989] calls the cumulativity condition.

Moreover the following property [Adams, 1975] is also worth considering

It can be checked that these properties, stated in terms of conditional possibility, do hold, interpreting p fv- q as p 1=1t q, and using the equivalence between p 1=1t q and Il(--.,q I p) < 1 :

Proposition 2 : Cut

IJ(--.,q I p) < 1 and Il(--.,r I p "q) < 1 => Il(--.,r I p) < 1 (9) £r..Q.Qf : the two premisses of (9) are equivalent to Il(p) > Il(p A --.,q) and Il(p " q) > Il(p " q" --.,r) ; then Il(p " --.,r) = max(Il(p " q A --.,r),Il(p A --.,q A --.,r)) ~ max(Il(p A q" --.,r),Il(p " --.,q)) < max(Il(p A q),Il(p)) = Il(p) Q.E.D.

Proposition 3 : Restricted monotonicity

Il(--.,q I p) < 1 and IJ(--.,r I p) < 1 => IJ(--.,r I p "q) < 1 (10) Stated positively, (10) simply means that if all maxima of 1t over the models of p are at the same time among the models of q and among the models of r then these maxima are also those of 1t over the models of p A q and they are among the models of r. A formal proof as the one of (9) is as easy.

PrQVOsition 4: OR property

Il(--.,q I p) < 1 and Il(--.,q I r) < 1 => Il(--.,q I p v r) < 1 (11) £mQf : from (4), Il(--.,q A p) < Il(p), IJ(--.,q A r) < Il(r). Using the axiom of possibility measures, it follows Il(-,q A (p v r)) < Il(p v r). Q.E.D.

Other requirements for non-monotonic consequence relations proposed by Kraus et al. [1990] hold as well. The reflexivity axiom p fv- p obviously holds since Il(p I p) = 1 and Il(--.,p I p) = 0 except if p is a contradiction. Right

weakening, i.e. l=p--+ ~; r fv- P corresponds to r q IJ(--.,p I r) < 1 => IJ(--.,q I r) < 1, if p entails q, which holds (since we have Il(--.,q I r). ~ IJ(-,p I r) in this case). Left logical equivalence l=p H 2,; r fv- P holds with conditional q r possibility since if l=p H q then Il(r I p) = Il(r I q) due to Il(p) = Il(q).

Kraus et al. [1990] have shown that other rules can be derived from the so-called system C (consisting of reflexivity, cut, cautious monotonicity, right weakening and left equivalence), e.g. the equivalence rule P tv q ; q ~ P ; P tv r . In terms of conditional possibility, it q r

reads:

Inference based on conditional possibility is actually a model for the non-monotonic inference system P of Kraus et al. [1990] (i.e. C and the OR rule), as well as a model for the non-monotonic system of Geffner [1988] after Adams

[1975]. We have seen that the counterpart of the non­ monotonic consequence relation p tv- q is IJ(-,q I p) < 1 or equivalently N(q I p) > 0 in the conditional possibility model. As pointed out in Pearl [1988], a probabilistic counterpart is Prob(q I p) ~ 1 - e where e is infinitely small, using results by Adams [1975] who showed that the rules, named cut, cautious monotonicity and the OR rule later on, are in full agreement with this semantics. However this semantics is not very realistic in practice for default rules since then the exceptions should have an infinitely small probability to be encountered. By contrast, it may seem more natural to view a "default rule" p tv- q as a rule which means that q is more possible than -,q in the context p (as seen above this is exactly what N(q I p) > 0 means).

In [Dubois and Prade, 1989] it has been shown that the cut, the cautious monotonicity and the OR rule have exact counterparts in the framework of symbolic conditional objects. Counterparts of the other rules of Kraus et al.' system P are also discussed in this framework in [Dubois and Prade, 1991]. Conditional objects offer a natural qualitative basis for defining conditional measures of uncertainty. It can be shown [Dubois and Prade, 1989, 1991] that various conditional measures of uncertainty can be built on top of conditional objects. It holds in particular for probability, possibility measures and belief functions. Hence the fact that conditional possibility leads to a system of non­ monotonic inference should not be too surprizing (since conditional objects behave in a non-monotonic way).

To the reader, it must be clear that results presented above do not require the use of the unit interval [0,1]. Any totally ordered set V can be used to express degrees of possibility, 0 and 1 standing for the least and the greatest element of V. (2), (3), Definition 1, (7), and all Propositions remain true, as long as we stick to possibility measures, and we obviate necessity measures (although the latter could be properly defined on V). Beyond the obvious convenience of a real­ valued scale for possibility degrees, the main reason to use [0,1] explicitly is that it enables the link between degrees of possibility and degrees of probability to be preserved. It is well known indeed that degrees of possibility can also be viewed as upper probabilities or degrees of plausibility in the sense of Shafer's evidence theory [Dubois and Prade, 1988].

4 Preferential entailment in possibilistic logic

A necessity-valued knowledge base~ in possibilistic logic is a collection of pairs (pi,<Xi), i = 1,n, where Pi is a classical logic formula, here a proposition for the sake of simplicity, and <Xi is a number belonging to (0,1] interpreted as a lower bound of the value of a necessity measure N for Pi· i.e. N(pi) ~ <Xi, i = 1,n. This necessity measure N is associated with a possibility distribution 1t on the set of interpretations .Q, which represents the semantics of ~ and which can be built in the following way [Dubois, Lang and Prade, 1989]. To (pi,<Xi) is associated the fuzzy set of interpretations

Then 1t is obtained by intersection of these fuzzy sets (since

~ is viewed as the conjunction of the pairs (pi,<Xi)), i.e. 1t(ro) = mini=1,n J..li(ro). It can be checked that the necessity measure N defined from 1t, namely

is such that V i = 1,n, N(pi) = <Xi. In other words, in agreement with the principle of minimum specificity, the least restrictive, i.e. the largest, possibility distribution 1t on .Q, which saturates the constraints N(pi) ~ <Xi, is in accordance with the semantics associated with ~. Note that here the possibility distribution 1t on the set of interpretations is built from the weights given in ~ and is not given a priori, as in Section 2, for defining c1t. The degree of inconsistency of~. Inc{~) is defmed from 1t, by Inc(~)= 1- max(1t(ro), roe .Q}. In other words,~ is all the more inconsistent as 1t is subnormalized. When Inc(~) = 0, ~ is said to be consistent. It can be shown [Dubois, Lang and Prade, 1989] that the three following statements are equivalent : i) Inc(~) = 0 ; ii) K is consistent in the usual sense where K is the set of propositions obtained from ~ by ignoring the weights <Xi ; iii) the assignment of the a i 's is such that V p , min(N(p),N(-,p)) = 0. When 1 > Inc(~)= a> 0, ~ is said to be a-inconsistent and we have Vp, min(N(p),N(-,p))= Inc(~) (indeed max(Il(p),Il(-,p)) = max{1t(ro), roe .Q} = l-Ine(~)).

Semantic entailment from such a possibilistic knowledge base ~ is defmed by

where N is defined from the possibility distribution 1t associated with~. Then N(-,p) =Inc(~)= 1- Il(p) since min(N(p),N(-,p)) =Inc(~). and 3~. N(p) ~~>Inc(~). Let ker(~) = .{roe .Q, 1t(ro) = 1 -Inc(~)} be the set of preferred interpretations with respect to the· Inc(~)­ inconsistent possibilistic knowledge base ~.Then we have the equivalence

Indeed N(p) > N(-,p) ~ 1 -Inc(~)= Il(p) > IJ(-,p) (using the duality between II and N), which makes the result obvious since Il(p) = max(1t(ro), ro 1= p}.

Now let us prove the following equivalence which relates, in the possibilistic framework, non-monotonicity and belief revision

Proposition 5 : N(q I p) > 0 ~ 3~ > Inc(~ u ((p,l)}), (~ u ((p,1)}) 1= (q.~) where N is the necessity measure defmed from the possibility distribution associated with ~. £rQQf: N(q I p) > 0 ~ p 1=1t q ~ (ro e .Q I 1t(ro) = Il(p) > 0} k (roe .a, ro 1= q)} ~ (ro e .a I 1t(ro) = 1- Inc(~ u ((p,l)}) > 0} ~(roe .a, ro 1= q} (since Inc(~ u((p,l)}) = 1- max(min(1t(ro),J..LM(p)(ro)), roe .Q} = 1- max{1t(ro), ro 1= p} = 1- Il(p) where M(p) is the non-empty set of models of p) ~ ker(~ u ((p,1)}) ~{roe .a, ro 1= q} ~ 3 ~>Inc(~ u ((p,l)}), (~ u ((p,l)}) 1= (q.~) using (12-13) Q.E.D.

The above equivalence illustrates, in the possibilistic framework, the translation in the sense of [Gfu"denfors, 1990] of a non-monotonic formalism, namely N(q I p) > 0 playing the role of p fv-K q (where K is a belief set representing our background beliefs), into a belief revision statement q E K*p· using Gardenfors [1988, 1990]'s notations, where K* p denotes the result of the revision of K when adding p, here expressed in our framework by (!:K. u ((p,1)}) 1= (q,a). Moreover note that it is also equivalent to preferential entailment in the sense of Shoham (upto the trivial entailment from contradictory propositions), here denoted p 1= 1t q. Here, instead of a belief set K, closed under deduction, we use any weighted set !:K. of propositions, and we derive a preference relation on interpretations.

A machinery described elsewhere [Dubois, Lang and Prade, 1987, 1989], based on extended resolution and refutation implements this non-monotonic/belief revision mechanism. Let us briefly restate the main points before giving an illustrative example. The necessity-valued possibilistic knowledge base !:K. with which we start is supposed to be put in clausal form. This is not constraining since if a formula p is the conjunction of n formulas PI· ... , Pn· then N(p) ;?: a <=> N(Pl "· .. "Pn) = min(N(pl), ... , N(pn)) ;?: a<=> Vi= l,n, N(pi);?: a. Extended resolution corresponds to the following pattern (c,a) (c',~) where (Res(c c'), min( a.~)) Res(c,c') is the classical resolvent of clauses c and c'. The refutation consists in adding to !:K. the set of clauses generated by the negation (-,p,l) of the proposition p of interest, with the weight 1 (total certainty). Then it can be shown that any weight obtained with the empty clause by the repeated application of the resolution pattern on !:K. u {(-,p,l)} is indeed a lower bound of the value of the necessity measure (associated with !:K.) for the event "p is true". So we are interested in obtaining the empty clause with the greatest possible lower bound. A procedure yielding such a refutation with the best possible weight frrst has been implemented using an ordered search method. Let us denote by !:K. 1--- (p,a) the fact that {.l,a) can be obtained by a refutation from !:K. u ((-,p,l)} (here a does not necessarily correspond to the best lower bound). Then the following soundness and completeness results holds, whether !:K. is totally consistent [Dubois, Lang and Prade, 1989] or partially inconsistent [Lang et al., 1990] :

!:K. 1--- (p,a) <=> !:K. 1= (p,a), for a > Inc( !:K.)

which guarantees the perfect agreement of the extended refutation machinery with the semantics presented above.

Let us now give an illustrative example

Let !:K. be the following knowledge base : .

• C 1. If Bob attends a meeting, then Mary does not.

C2. Bob comes to the meeting to-morrow.

• C3. If Betty attends a meeting, then it is likely that the meeting will not be quiet.
• C4. If is only somewhat certain that Betty comes to the meeting to-morrow.
• C5. If Albert comes to-morrow and Mary does not, then it is almost certain that the meeting will not be quiet.
• C6. It is likely that Mary or John will come to-morrow.
• C7. If John comes to-morrow, it is rather likely that Albert will come.
• C8. If John does not come to-morrow, it is almost certain that the meeting will be quiet.

This can be represented by the following weighted clauses :

Cl (-,Bob{x) v -,Mary(x) 1) ; C2 (Bob{m) 1)

C3 (.Betty(x) v -,quiet(x) 0.7) ; C4 (Betty(m) 0.3)

C5 {Mary{m) v .Albert(m) v -,quiet(m) 0.8)

C6 (John(m) v Mary(m) 0.7) ; C7 (John(m) v quiet(m) 0.8)

C8 (-,John(m) v Albert(m) 0.6)

If we want to try to prove that the meeting to-morrow will not be quiet, we add the clause CO : (quiet(m) 1). Then it can be checked that there exist two possible refutations : one from CO, C3, C4 which gives (.1,0.3) and another from CO, C5, C1, C2, C6, C8 which gives (.1,0.6). The last refutation is the optimal one. We proved that N(-,quiet(m)) ;?: 0.6, i.e. it is rather likely that the meeting to-morrow will not be quiet.

Moreover, adding to a consistent knowledge base !:K., a clause (c,a) that makes it partially inconsistent, produces a non-monotonic behavior. Namely, if from !:K. a conclusion (p.~) can be obtained by refutation, it may happen that, from !:K.' = !:K. u ( (c,a)}. an opposite conclusion (-,p,0)) with 0 > Inc( !:K. ') ;?: ~ can be derived.

Suppose we add to !:K. in the above example the clause (-,John(m),1), i.e. a= 1, expressing that we are now certain that John will not come to-morrow. Let !:K.' be the new knowledge base. The inconsistency degree of !:K.' is 0.7, i.e. Inc(!:K.') = 0.7 (as given by refutation from C1, C2, C6 and (-,John(m), 1)). Now the proof of (-,quiet(m),0.6) (it corresponds to ~ = 0.6) is no longer valid ; but we can prove (quiet(m),0.8), i.e. 0 = 0.8 ; which is obtained by a refutation from (-,quiet(m),1), C7 and (-,John(m),1), using only a consistent subpart of% u ((-,John(m),l)}. Thus a non-monotonic behaviour can be captured in this framework.

The above example shows not only the ability of possibilistic logic to cope with partial inconsistency but also that a revision mechanism is implicitly working in it. The deep reason for that has been recently discovered [Dubois and Prade, 1990b]. It is basically due to the equivalence between the system of axioms defining the so­ called epistemic entrenchment relations (on which well­ behaved revision processes should be based [Gfu"denfors, 1988]) and the systems of axioms characterizing qualitative necessity relations. Qualitative necessity relations [Dubois, 1986] are binary relations denoted .i where p .i q means q is at least as certain as p, are the perfect qualitative counterpart of necessity measures in the sense that for any necessity measure N there exists a qualitative necessity relation < such that the following equivalence holds V p, q, p < q <=> N(p) ~ N(q). Conversely only necessity measures are numerical representations of such kinds of ordering.This emphasizes the qualitative nature of possibility and necessity measures and points out that the numbers which are used in practice, as in the above example, have mainly an ordinal meaning.

5 - Conclusion

This paper has tried to take one more step towards the unification of symbolic and numerical knowledge representation approaches for reasoning under uncertainty. Namely possibilistic logic belongs to the family of non­ monotonic systems based on preferential models. Moreover the identity of axioms between necessity measures and epistemic entrenchment puts possibilistic logic in the current stream of ideas on belief revision. Stated compactly, any possibilistic knowledge base ~ induces a preference relation among interpretations. This preference relation is consistent with an epistemic entrenchment relation over formulas that can be deduced from ~ ; adding a new formula to ~ produces a revision effect, in accordance with this epistemic entrenchment relation, that is achieved by applying the resolution principle extended to necessity valued clauses. Moreover, deduction from a partially inconsistent possibilistic knowledge base has all properties of a well-behaved non-monotonic deduction. Note that our investigation parallels the one of Pearl and others on probabilistic semantics of default, but here in a purely non­ probabilistic framework .

A further topic of interest would be to try to bridge the gap between possibilistic logic and conditional logic, following the path opened by Bell [1990] who reinterprets Shoham's preference logic in the framework of conditional logics. This would enable Delgrande [1986]'s logic of typicality to be better understood in its links with other non­ monotonic logics. Note that our notion of conditional possibility and certainty have symbolic counterparts in Bell's logic.

Moreover the defmition of these conditional measures of uncertainty is based on the minimum operation here (ll(p A q) = min(TI(p I q),TI(q))), but clearly most of the results obtained here carry over to the case where min is changed into product, i.e. conditional possibility is then in accordance with Dempster rule of conditioning. This fact suggests that the close relationships displayed here between non-monotonic reasoning, belief revision and possibility theory might extend to belief functions .

Lastly, there is an obvious proximity of ideas between possibilistic logic and constraint-directed programming where constraints have various levels of priority [Satoh, 1990]. This topic will also be investigated in the future, interpreting a necessity-valued clause as a soft constraint.

Acknowledgements : The authors are grateful to a referee for pointing out the problem of preferential entailment from inconsistent premises, and for various other remarks that significantly improved the presentation of the paper. This work has been partially supported by the European ESPRIT Basic Research Action n° 3085 entitled "Defeasible Reasoning and Uncertainty Management Systems (DRUMS)".