Thierry Denoeux
email: tdenoeux@utc.fr

Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Representations of Uncertainty in Artificial Intelligence: Probability and Possibility

Due to its major focus on knowledge representation and reasoning, artificial intelligence was bound to deal with various frameworks for the handling of uncertainty: probability theory, but more recent approaches as well: possibility theory, evidence theory, and imprecise probabilities. The aim of this chapter is to provide an introductive survey that lays bare specific features of two basic frameworks for representing uncertainty: probability theory and possibility theory, while highlighting the main issues that the task of representing uncertainty is faced with. This purpose also provides the opportunity to position related topics, such as rough sets and fuzzy sets, respectively motivated by the need to account for the granularity of representations as induced by the choice of a language, and the gradual nature of natural language predicates. Moreover, this overview includes concise presentations of yet other theoretical representation frameworks such as formal concept analysis, conditional events and ranking functions, and also possibilistic logic, in connection with the uncertainty frameworks addressed here. The next chapter in this volume is devoted to more complex frameworks: belief functions and imprecise probabilities.

Introduction : An Historical Perspective

The question of including, hence modeling, uncertainty in scientific matters is not specific to the field of artificial intelligence. Historically, this concern already appears in the XVIIth century, with pioneering works of Huyghens, Pascal, chevalier de Méré, and Jacques Bernoulli. There existed at that time a major distinction between the objective notion of chance in connection with the study of games (of chance), and the subjective notion of probability in connection with the issue of unreliable testimonies at courts of law. With J. Bernoulli, chances are related to frequencies of events and are naturally additive, while subjective probabilities are not supposed to be so. This view is still present in the middle of the XVIIIth century with the works of Lambert. He proposed a combination rule which turns out to be a special case of Dempster's rule of combination; see [START_REF] Shafer | Non-additive probabilities in the work of Bernoulli and Lambert[END_REF][START_REF] Martin | Logique du probable de Jacques Bernoulli à J.-H. Lambert[END_REF], and Chapter 4 of this volume. However, with the rapid development of physics and actuarial sciences later on, the interest for the non-additive side of probability eventually waned and the issue was forgotten for almost two centuries, while the additive view became prominent, with the works of Laplace, whether the focus was on frequentist probability or not. Noticeably, in the middle of the XXth century, in economics, not only the main approach to decision under (frequentist) risk after [START_REF] Von Neumann | Theory Games and Economic Behavior[END_REF], but also the mainstream theory of decision under (subjective) uncertainty relied on additive probability.

It is the emergence of computer sciences that brought issues related to knowledge representation and reasoning in the presence of imprecision, uncertainty, and conflicting information to the front. This went on till the 1980's almost independently of probability theory and the issue of decision-making. Instead, artificial intelligence first put the emphasis on logical and qualitative formalisms, as well as the modeling of linguistic information (in trends of research such as fuzzy set theory).

Indeed, the available information to be stored in a computer is often unreliable, as is human knowledge, so that reasoning is based on rules that may lead to uncertain conclusions even starting from sure premises. The need to handle uncertainty arose in fact with the emergence of the first expert systems at the beginning of the 1970's. One of the first and best known expert rule-based system, namely MYCIN [START_REF] Shortliffe | Computer-based Medical Consultations MYCIN[END_REF]Buchanan and Shortliffe, eds.], already proposed an ad hoc, entirely original, technique for uncertainty propagation based on degrees of belief and disbelief. This method will not be described here for lack of space, and because it is now totally outdated, especially due to its improper handling of exceptions in ifthen rules. But the uncertainty propagation technique of MYCIN pioneered the new, more rigorous frameworks for uncertainty modeling that would appear soon after. On this point, see [START_REF] Dubois | Handling uncertainty in expert systems: pitfalls, difficulties, remedies[END_REF], and [START_REF] Lucas | Principles of Expert Systems[END_REF] as well.

This chapter is structured in four sections. In Section 2, basic notions useful for describing the imperfection of information are defined and discussed. Section 3 deals with probability theory, focusing on the possible meanings of probability and the difficulty to handle plain incomplete information with probability distributions, as well as the connections between conditioning and logic. Section 4 deals with set functions extending the modalities of possibility and necessity, distinguishing between qualitative and quantitative approaches, and describing connections with reasoning tolerant to exceptions, formal concept analysis, probability and statistics. Section 5 explains the links between uncertain reasoning and Aristotelian logic, generalizing the square of opposition.

2 Imprecision, Contradiction, Uncertainty, Gradualness, and Granularity

Before presenting various representation frameworks (see [START_REF] Halpern | A logic for reasoning about upper probabilities[END_REF][START_REF] Dubois | Formal representations of uncertainty[END_REF][START_REF] Liu | Propositional, Probabilistic and Evidential Reasoning: Integrating Numerical and Symbolic Approaches[END_REF][START_REF] Parsons | Qualitative Approaches for Reasoning Under Uncertainty[END_REF] for interesting focused overviews), it is useful to somewhat clarify the terminology. We call information item any collection of symbols or signs produced by observing natural or artificial phenomena, or by human cognitive activity, whose purpose is communication. Several distinctions are in order. First, one must separate so-called objective information items, coming from sensor measurements or direct observations of the world, from subjective ones, expressed by individuals and possibly generated without using direct observations of the outside world. Information items may be couched in numerical formats, especially objective ones (sensor measurements, counting processes), or in qualitative or symbolic formats (especially subjective ones, in natural language for instance). However the dichotomy objective numerical vs. subjective qualitative is not so clearcut. A subjective information item can be numerical, and objective observations can be qualitative (like a color perceived by a symbolic sensor, for instance). Numerical information can take various forms: integers, real numbers, intervals, real-valued functions, etc. Symbolic information is often structured and encoded in logical or graphical representations. There are also hybrid representation formats, like Bayesian networks [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. Finally, another important distinction should be made between singular and generic information. Singular information refers to particular facts and results from an observation or a testimony. Generic information pertains to a class of situations and expresses knowledge about it: it can be a law of physics, a statistical model stemming from a representative sample of observations, or yet commonsense statements such as "birds fly" (in this latter case the underlying class of situations is not precise: is it here a zoological definition, or the birds of any epoch, or of any place, etc. ?).

Imprecise Information

To represent the epistemic state of an agent, one must beforehand possess a language for representing the states of the world under interest, according to the agent, that is, model relevant aspects by means of suitable attributes. Let v be a vector of attribute variables1 relevant for the agent, and let S be its domain (possibly not described in extension). S is then the set of (precise descriptions) of the set of possible states of affairs. A subset A of S is viewed as an event, or as a proposition that asserts v ∈ A.

An information item v ∈ A possessed by an agent is said to be imprecise if it is not sufficient to enable the agent to answer a question of interest about v. Imprecision corresponds to the idea of incomplete or even missing information. The question to which the agent tries to answer is of the form what is the value of v, or more generally does v satisfy a certain property B, given that v ∈ A is known? The notion of imprecision is not absolute. When concerned with the age of a person, the term minor is precise if the referential set is S = {minor, ma jor} and the question is : has this person the right of vote? In contrast if the question is to determine the age of this person and S = {0, 1, . . . , 150} (in years), the term minor is very imprecise.

The standard format of an imprecise information item is v ∈ A where A is a subset of S containing more that one element. An important remark is that elements of A, seen as possible values of v are mutually exclusive (since the entity v possesses only one value). So, an imprecise information item takes the form of a disjunction of mutually exclusive values. For instance, to say that John is between 20 and 22 years old, that is, v = age(John) ∈ {20, 21, 22} means to assume that v = 20 or v = 21 or v = 22. An extreme form of imprecise information is total ignorance: the value of v is completely unknown. In classical logic, imprecision explicitly takes the form of a disjunction (stating that A ∨ B is true is less precise than stating that A is true). The set A representing an information item is called an epistemic set.

Two imprecise information items can be compared in terms of informational content: an information item v ∈ A 1 is said to be more specific than another information item v ∈ A 2 if and only if A 1 is a proper subset of A 2 .

The disjunctive view of sets used to represent imprecision contrasts with the more usual conjunctive view of a set as a collection of items forming a certain complex entity. It then represents a precise information item. For instance, consider the set of languages that John can speak, say v = Lang(John). This variable is setvalued and stating that Lang(John) = {English, French} is a precise information item, as it means that John can speak English and French only. In contrast, the variable v = NL(John) representing the native language of John is single-valued and the statement NL(John) ∈ {English, French} is imprecise. The domain of v is the set of all spoken languages while the domain of v is its power set. In the latter case, an imprecise information item pertaining to a set-valued variable is represented by a (disjunctive) set of (conjunctive) subsets.

Contradictory Information

An information item is said to be contradictory if it is of the form v ∈ A, where A = / 0. Under this form there is not much we can do with such an information item. In mathematics, the presence of a contradiction ruins any form of reasoning, and it is only used to prove claims by refutation (a claim is true because assuming its falsity leads to a contradiction). In artificial intelligence, contradiction often stems from the conflict between several information items, e.g., v ∈ A and v ∈ B where A ∩ B = / 0. It is thus a natural situation that is to be expected each time there are several sources, and more generally if collected information items are numerous. Another cause of conflicting information is the presence of exceptions in generic information items such as rules, which may lead to simultaneously infer opposite conclusions. There are several approaches in the literature that aim at coping with contradictory information, and that are studied in this book:

• information fusion techniques that aim at restoring consistency, by deleting unreliable information items, taking into account the sources that deliver them, and analyzing the structure of the conflict between them. See Chapter 14 in this volume.

• argumentation methods that discuss the pros and the cons of deriving a proposition v ∈ A using a graph-theoretic representation of an attack relation between conflicting arguments. See Chapter 13 in this volume.

• paraconsistent logics that try to prevent the infection of the contradiction affecting some variables or some subgroups of information items to other ones, by for instance changing the inference relation, thus avoiding the explosive nature of standard inference from inconsistent bases in classical logic. See Chapter 13 in this volume. • nonmonotonic reasoning formalisms that try to cope with exceptions in rules by giving priority to conclusions of the most specific ones. See Chapter 2 in this volume.

Uncertain Information

An information item is said to be uncertain for an agent if the latter does not know whether it is true or false. If an elementary information item of the form of a proposition v ∈ A, where A contains a set of non-impossible values for v, is tainted with uncertainty, a token of uncertainty is attached to it. This token is a qualifier situated at the meta-level with respect to the information item. It can be numerical or symbolic: compare statements expressing uncertainty such as The task will take at least one hour, with probability 0.7, and It is not fully sure that John comes to the meeting. Uncertainty has two main origins: the lack of information, or the presence of conflicting information. A special case of the latter is aleatory uncertainty, where due to the variability of an observed phenomenon, it is difficult to predict the next event, hence the information item v ∈ A that may describe it.

The most usual representation of uncertainty consists in assigning to each proposition v ∈ A or event A ⊆ S, a number g(A) in the unit interval. This number expresses the agent's confidence in the truth of the proposition v ∈ A. Note that this proposition is ultimately only true or false, but the agent may currently ignore what its actual truth-value is. Natural conditions are required for the set function g:

g( / 0) = 0; g(S) = 1; if A ⊆ B then g(A) ≤ g(B). (1)
Indeed the contradictory proposition v ∈ / 0 is impossible, and the tautological proposition v ∈ S is certainly true. Moreover, if A is more specific than B (and thus implies B), a rational agent cannot trust v ∈ A more than v ∈ B. When S is infinite, one must add suitable continuity properties with respect to monotonic sequences of subsets. Such a function g is often called a capacity [START_REF] Choquet | Theory of capacities[END_REF], or fuzzy measure [START_REF] Sugeno | Fuzzy measures and fuzzy integrals -A survey[END_REF], or yet plausibility function [START_REF] Halpern | Plausibility measures: A general approach for representing uncertainty[END_REF] (not to be confused with the dual to belief functions, defined in the next chapter in this volume). An important consequence of ( 1) is in the form of two inequalities:

g(A ∩ B) ≤ min(g(A), g(B)); g(A ∪ B) ≥ max(g(A), g(B)).
(2)

These inequalities suggest to consider extreme confidence measures g such that one of these inequalities is an equality, and more generally, when A and B are mutually exclusive, assume that g(A ∪ B) only depends on g(A) and g(B) [START_REF] Dubois | A class of fuzzy measures based on triangular norms. a general framework for the combination of uncertain information[END_REF], i.e., if

A ∩ B = / 0 then g(A ∪ B) = g(A) ⊕ g(B). (3)
for some binary operation ⊕ on [0, 1]. The conjugate set function, defined by g(A) = 1g(A), then satisfies the dual property g [START_REF] Dubois | A class of fuzzy measures based on triangular norms. a general framework for the combination of uncertain information[END_REF]. The set functions g and g are said to be decomposable. Compatibility constraints with the Boolean algebra of events suggests considering operations ⊕ and ⊥ that are associative, which leads to choose ⊥ and ⊕ among triangular norms and co-norms [START_REF] Klement | Triangular norms[END_REF] (they get their name from their role in the expression of the triangular inequality in stochastic geometry [START_REF] Schweizer | Associative functions and abstract semi-groups[END_REF]). The main possible choices for a⊥b (resp. ). The use of more complex operators (like ordinal sums of the above ones) may make sense [Dubois et al, 2000b].

(A ∩ B) = g(A)⊥g(B) if A ∪ B = S where a⊥b = 1 -(1 -a) ⊕ (1 -b)

Graduality and Fuzzy Sets

Representing a proposition in the form of a statement that can only be true or false (or an event that occurs or not) is but a convenient convention. It is not always an ideal one. Some information items are not easily amenable to respecting this convention. This is especially the case for statements involving gradual properties, like in the proposition John is young, that may sometimes be neither completely true nor completely false: it is clearly more true if John is 20 than if he is 30, even if in the latter case, John is still young to some extent. Predicates like young can be modified by linguistic hedges. It makes sense to say very young, not so young, etc. Such linguistic hedges cannot be applied to Boolean predicates, like single. In other words, the proposition John is young is not Boolean, which denotes the presence of an ordering between age values to which it refers. This type of information can be taken into account by means of fuzzy sets [START_REF] Zadeh | Fuzzy sets[END_REF]. A fuzzy set F is a mapping from S to a totally ordered set L often chosen to be the unit interval [0, 1]. The value F(s) is the membership degree of the element s in F. It evaluates the compatibility between the situation s and the predicate F.

Fuzzy sets are useful to deal with information items in natural language referring to a clear numerical attribute. [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning[END_REF] introduced the notion of linguistic variable with values in a linearly ordered linguistic term set. Each of these terms represents a subset of the numerical domain of the attribute, and these subsets correspond to a partition of this domain. For instance, the set of terms T = {young, adult, old} forms the domain of the linguistic variable age(John) and partitions the domain of this attribute. Nevertheless it is not surprising to admit that the transitions between the ranges covered by the linguistic terms are gradual rather than abrupt. And in this situation, it sounds counterintuitive to set precise thresholds separating these continuous ranges. Namely, it sounds absurd to define the set F =young ∈ T by a precise threshold s such that F(s) = 0 if s > s and F(s) = 1 otherwise, beyond which an individual suddenly ceases to be young. The membership function of the fuzzy set valued in the scale [0, 1], representing here the gradual property young, is but a direct reflection of the continuous domain of the attribute (here the age). This also leads to the idea of a fuzzy partition made of non-empty fuzzy subsets F 1 , • • • , F n , often defined by the constraint ∀s, Σ i=1,n F i (s) = 1 [START_REF] Ruspini | Numerical methods for fuzzy clustering[END_REF].

If we admit that some sets are fuzzy and membership to them is a matter of degree, one issue is to extend the set-theoretical operations of union, intersection and complementation to fuzzy sets. This can be done in a natural way, letting

(F ∪ G)(s) = F(s) ⊕ G(s); (F ∩ G)(s) = F(s)⊥G(s); F(s) = 1 -F(s),
where ⊕ and ⊥ are triangular co-norms and norms already encountered in the previous subsection. The choice ⊕ = max and ⊥ = min is the most common. With such connectives, the De Morgan property between ∪ and ∩ are preserved, as well as their idempotence and their mutual distributivity. However, the excluded middle (A ∪ A = S) and contradiction laws (A ∩ A = / 0) fail. Choosing ⊕ = min(1, • + •) and ⊥ = max(0, • + • -1) re-install these two laws, at the cost of losing idempotence and mutual distributivity of ∪ and ∩. As to fuzzy set inclusion, it is oftentimes defined by the condition F ⊆ G ⇔ ∀s, F(s) ≤ G(s). A more drastic notion of inclusion requires the inclusion of the support of F (elements s such that F(s) > 0) in the core of G (elements s such that G(s) = 1). In agreement with the spirit of fuzzy sets, inclusion can also be a matter of degree. There are various forms of inclusion indices, of the form d(F ⊆ G) = min s F(s) → G(s), where → is a many-valued implication connective.

Fuzzy sets led to a theory of approximate reasoning and the reader is referred to a section dedicated to interpolation in Chapter 10 of this volume. Besides, since the mid-1990's, there has been a considerable development of formal fuzzy logics, understood as syntactic logical systems whose semantics is in terms of fuzzy sets. These works, triggered by the book by [START_REF] Hájek | The Metamathematics of Fuzzy Logics[END_REF], considerably improved the state of the art in many-valued logics developed in the first half of the XXth century (see [Dubois et al, 2007] for a detailed survey of both approximate reasoning and formal fuzzy logic.)

Degree of Truth vs. Degree of Certainty: A Dangerous Confusion

It is very crucial to see the difference between the degree of adequacy between a state of affairs and an information item (often called degree of truth) and a degree of certainty (confidence). Already, in natural language, sentences like John is very young and John is probably young do not mean the same. The first sentence expresses the fact that the degree of membership of age(John) (e.g., age(John) = 22) to the fuzzy set of young ages is for sure high. The degree of membership F(s) evaluates the degree of adequacy between a state of affairs s 0 , e.g., s 0 = 22, and the fuzzy category F =young. According to the second sentence, it is not ruled out that John is not young at all. Degrees of truth and degrees of certainty correspond to distinct notions that occur in distinct situations with unrelated semantic contents. Moreover they are driven by mathematical frameworks that should not be confused despite their superficial resemblances as to the involved connectives. Indeed, as seen earlier in this text, truth degrees are usually assumed to be compositional with respect to all connectives like conjunction, disjunction, and negation (respectively corresponding to intersection, union, and complementation of fuzzy sets). However, full-fledged compositionality is impossible for degrees of certainty. This is because the Boolean algebra of standard events is not compatible with the structure of the unit interval, nor any finite totally ordered set with more than 2 elements [Dubois and Prade, 2001]: they are not Boolean algebras. For instance, probability is compositional only for negation (Prob(A) = 1 -Prob(A)), and as we shall see later on, possibility (resp. necessity) measures are compositional only for disjonction (resp. conjonction). For instance one can be sure that v ∈ A ∪ B is true (especially if B = A !), without being sure at all that any of v ∈ A, and v ∈ B is true.

A typical situation where certainty and truth tend to be confused is when using a three-valued logic to capture partial information, changing Boolean interpretations of a language into three-valued ones. The usual truth set {0, 1} is turned into, say, {0, 1/2, 1}, with the idea that 1/2 stands for unknown as in Kleene logic [START_REF] Kleene | Introduction to Metamathematics[END_REF]. Now the problem is that under the proposed calculus by Kleene with conjunction, disjunction and negation expressed by operations min, max and 1 -(•), respectively, the excluded middle law is lost. This is a paradox here as, since a proposition v ∈ A can only be true or false, the composite proposition v ∈ A or v ∈ A is always valid while, in the three-valued setting, it will have truth value 1/2 if v ∈ A is set to unknown. The way out of the paradox consists in noticing that the negation of unknown is known, actually known to be true or known to be false. So the three alleged truth-values {0, 1/2, 1} are degrees of certainty, and actually stand for the three non-empty subsets of {0, 1}, 1/2 standing for the hesitation between true and false, namely {0, 1}. And then it becomes clear the statement either v ∈ A is known to be true or v ∈ A is known to be false is not a tautology.

The Kleene approach to ignorance has been extended by Belnap [1977a;1977b] to include contradictory information stemming from conflicting sources, adding a fourth truth value expressing contradiction. The 4-valued truth set forms a bilattice structure and is isomorphic to the four subsets of {0, 1} (now including / 0), equipped with two partial orderings: the truth-ordering (where the two new truth-values are incomparable and lie between true and false) and the information ordering (that coincides with inclusion of subsets in {0, 1}). These "epistemic truth-values" are attached to atomic propositions, and truth-tables in agreement with the bilattice structure enable the epistemic status of complex propositions to be computed. The same kind of analysis as above applies regarding the use of compositional truth values in this logic (e.g., true in the sense of Belnap means approved by some source and disapproved by none, an epistemic stance). See [START_REF] Dubois | Reasoning about ignorance and contradiction: many-valued logics versus epistemic logic[END_REF] for a discussion. Besides, [START_REF] Ginsberg | Bilattices and modal operators[END_REF] used Belnap bilattices to propose a unified semantic view for various forms of non-monotonic inferences (see Chapter 2 in this volume and the subsection 4.2.1 in this chapter).

Granularity and Rough Sets

In the preceding sections, we did not question the assumptions that underlie the definition of the set S of states of the world. It should not be taken for granted, as it presupposes the definition of a language. The logical approach to Artificial Intelligence often starts from a set of statements expressed in a propositional language, to which it may assign degrees of confidence. Then the set S is the set of states or interpretations generated by these propositions (mathematically, the subsets of S are the smallest Boolean algebra supporting these propositions). This view has important consequences for the representation and the updating of bodies of information items. For instance, a new information item may lead to a refinement of S: this is called a change of granularity of the representation.

The simplest case of change of granularity is when the basic propositions are taken as atomic ones, or more generally when describing objects by attributes. Let Ω be a set of objects described by attributes V 1 ,V 2 , . . . ,V k with respective domains

D 1 , D 2 , . . . , D k . Then S is the Cartesian product D 1 × D 2 × • • • × D k .
Each element of S can be refined into several ones if a (k + 1)th attribute is added. Clearly, nothing prevents distinct objects from having the same description in terms of such attributes. Then they are indiscernible by means of this language of description.

Consider a subset Θ of objects in Ω . It follows from the above remark, that in general Θ cannot be described precisely using such an attribute-based language. Indeed let R be an equivalence relation on Ω clustering objects having the same description: ω 1 Rω 2 if and only if V i (ω 1 ) = V i (ω 2 ), ∀i = 1, . . . , k. Let [ω] R be the equivalence class of object ω. We only have such equivalence classes to describe the set Θ , so only approximate descriptions of it can be used. The only thing we can do is to build upper and lower approximations Θ * and Θ * defined as follows:

Θ * = {ω ∈ Ω : [ω] R ∩Θ = / 0}; Θ * = {ω ∈ Ω : [ω] R ⊆ Θ } (4)
The pair (Θ * ,Θ * ) is called a rough set [START_REF] Pawlak | Rough Sets. Theoretical Aspects of. Reasoning about Data[END_REF][START_REF] Pawlak | Rudiments of rough sets. 2. Rough sets: Some extensions. 3. Rough sets and Boolean reasoning[END_REF].

Only subsets of objects such as Θ * and Θ * can be accurately described by means of combinations of attribute values V 1 ,V 2 , . . . ,V k .

There are various examples of situations where rough sets implicitly appear, for instance histograms or digital images correspond to the same notions of indiscernability and granularity, where equivalence classes correspond, respectively, to the bins of the histograms and to pixels.

The concept of rough set is thus related to the ones of indiscernibility and granularity, while the concept of fuzzy set is related to gradualness. It it is possible to build concepts where these two dimensions are at work, when the set to be approximated or the equivalence relation become fuzzy [START_REF] Dubois | Putting rough sets and fuzzy sets together[END_REF]. Rough sets are also useful in machine learning to extract rules from incomplete data [START_REF] Jw | Knowledge acquisition under uncertainty -a rough set approach[END_REF][START_REF] Hong | Learning rules from incomplete training examples by rough sets[END_REF], as well as fuzzy decision rules [START_REF] Greco | Fuzzy rough sets and multiple-premise gradual decision rules[END_REF] (see Chapter 12 in Volume 2).

Uncertainty: The Probabilistic Framework

Probability theory is the oldest uncertainty theory and, as such, the best developed mathematically. Probability theory can be envisaged as a chapter of mathematics. In that case, we consider a probability space, made of a set Ω (called a sample space) and an application v from Ω to S (called random variable), where oftentimes S is taken as the real line. In the simplest case S is a finite set which determines via v a finite partition of Ω . If B is the Boolean algebra generated by this partition, a probability space is actually the triple (Ω , B, P), and P is a probability measure, i.e., an application from B to [0, 1] such that:

P( / 0) = 0; P(Ω ) = 1; (5) if A ∩ B = / 0 then P(A ∪ B) = P(A) + P(B). (6)
Elements of B are called measurable subsets of Ω . The probability distribution induced by v on S is then characterized by a set of weights p 1 , p 2 , . . . , p card(S) , defined by p i = P(v -1 (s i )), and such that card(S)

∑ i=1 p i = 1.
Probabilities of events can be extended to fuzzy events by considering the expectation of their membership functions [START_REF] Zadeh | Probability measures of fuzzy events[END_REF], which indeed generalizes the usual expression P(A) = ∑ s i ∈A p i of a classical event.

Beyond the apparent2 unity of the mathematical model of probability, there are strikingly different views of what probability means [START_REF] Fine | Theories of Probability[END_REF]. The aim of this section is to discuss some of these views, emphasizing some limitations of the representation of uncertainty by means of a unique probability distribution. This section is completed by a glance at De Finetti's conditional events and their three-valued logic, and at a very specific kind of probability distribution (so-called big-stepped) that play a noticeable role in the representation of default rules.

Frequentists vs. Subjectivists

If probability theory is considered as a tool for knowledge representation, one must explain what probability means, what is it supposed to represent. There are at least three understandings of probability, that have been proposed since its inception.

The simplest one is combinatorial. The set Ω is finite and p i is proportional to the number of elements in v -1 (s i ). Then a probability degree is just a matter of counting, for each event, the proportion of favorable cases over the number of possible ones. The well-foundedness of this approach relies on considerations about symmetry (a principle of indifference or insufficient reason, after Laplace), or the assumption that the phenomenon we deal with is genuinely random (like coin flipping, fair die tossing, etc.), and follows a uniform distribution.

The most common interpretation is frequentist. It is assumed that we accumulate observations (a finite n-element subset Ω (n) of the sample space Ω ). Then frequencies of observing v = s i defined by:

f i = card(v -1 (s i ) ∩ Ω (n)) n
can be obtained. When S is infinite, we can build a histogram associated to the random variable v by considering frequencies of elements of a finite partition of S (possibly adjusting a continuous distribution to it).

As the number of observations increases, Ω (n) becomes a representative sampling of Ω , and it is assumed that such frequencies f i converge to probability values defined as limits, by p i = lim n→∞ f i . To use this definition of probability, one must clearly have a sufficient number of observations available (ideally an infinite number) for the phenomenon under study. Under this view, the probability of a nonrepeatable event makes no sense. Moreover, the frequentist probability distribution is a mathematical model of a physical phenomenon, hence objective, even if it can be part of the knowledge of an agent.

Under the third, subjectivist, view, the degree of probability P(A) is interpreted as a degree of belief of an agent in the truth of the information item v ∈ A. Hence it should apply to any event, be it repeatable or not. What plays the role of frequencies for making subjective probability operational for non-repeatable events is the amount of money one should pay for a gamble on the occurrence or the non occurrence of event A. More precisely the degree of probability P(A) for an agent is equated to the fair price this agent is willing to pay to a bookmaker for a lottery ticket with a 1 euro reward in case the event occurs. The price is fair in the sense that the agent would also agree to sell it at this price to the bookmaker, should the latter decide to buy it. Clearly the more the agent believes in A the greater (i.e., the closer to 1 euro) the price (s)he is likely to offer. This approach then relies on a rationality principle, called coherence, saying that the agent is not willing to lose money for sure. It ensures that degrees of belief (betting prices) behave in an additive way like probabilities. To see it, suppose the agent buys two lottery tickets, the first one to bet on A, the second one to bet on its complement A. The agent is sure to have one winning ticket, which means a profit of 1 -P(A) -P(A) euros in relative value. Prices such that P(A) + P(A) -1 > 0 are not rational as it means a sure loss for the agent. However, prices such that P(A) + P(A) -1 < 0 are unfair and will lead the bookmaker to buy the tickets at those prices instead of selling them, to avoid sure loss on the bookmaker side. So the only choices left for the agent is to propose prices such that P(A) + P(A) = 1. The same reasoning can be carried our for three mutually exclusive events, A, B, A ∪ B, leading to the constraint P(A) + P(B) + P(A ∪ B) = 1, which, since P(A ∪ B) = 1 -P(A ∪ B), leads to P(A ∪ B) = P(A) + P(B). Note that the probability degrees so-defined are personal, and may change across agents, contrary to frequentist probabilities.

Apparently, the subjectivist approach looks like a mere copy of the calculus of frequentist probabilities. In fact as shown by [START_REF] Finetti | Theory of Probability[END_REF] and his followers [START_REF] Coletti | Probabilistic Logic in a Coherent Setting[END_REF], things are not so simple. First, in the subjectivist approach there is no such thing as a sample space. The reason is that a subjective probability is either assigned to a unique event (after betting one checks whether this event did occur or not), or to a single realization of a repeatable one (e.g., flipping this coin now). Next, on infinite spaces, only finite additivity (in contrast with σ -additivity for the frequentist approach) can be justified by the above betting paradigm. Finally, the initial data does not consist of statistics, but a collec-tion of bets (prices c i ) on on the truth of propositions A i in an arbitrary set thereof {A j : j = 1, . . . , m}, along with a number of logical constraints between those propositions. The state space S is then constructed based on these propositions and these constraints. It is assumed, by virtue of the coherence principle, that the agent assigns prices c j to propositions A j in agreement with the probability calculus, so that there is a probability distribution that satisfies P(A j ) = c j , j = 1, . . . , m. While the frequentist approach leads to assuming a unique probability distribution representing the random phenomenon (obtained via an estimation process from statistical data), this is not the case in the subjectivist setting, if the bets bear on arbitrary events. Indeed there may be several probability measures such that c j = P(A j ), ∀ j = 1, . . . , m. Any of those probability functions is coherent but the available information may not allow us to select a single one. It may also occur that no such probability exists (then the bets are not coherent). To compute the probability degree P(A) of some arbitrary event A based on a collection of pairs {(A j , c j ) : j = 1, . . . , m}, one must solve linear programming problems whose decision variables are probabilities p i attached to singletons of S of the form: maximise (or minimise) ∑ s i ∈A p i under constraints

c j = ∑ s k ∈A j p k , ∀ j = 1, . . . , m.
It is then clear that the subjectivist approach to probability is an extension of the logical approach to artificial intelligence based on propositional logic and classical inference. The latter is recovered by assigning probability c j = 1 to A j , j = 1, . . . , m, which enforces P(A) = 1 to all logical consequences A of {A j : j = 1, . . . , m}.

There are other formal differences between frequentist and subjectivist probabilities when it comes to conditioning.

Conditional Probabilities

By considering S as the state space, it is implicitly assumed that S represents an exhaustive set of possible worlds. To emphasize this point of view we may as well write the probability P(A) as P(A | S). If further on the agent receives new information that comes down to restraining the state space, probabilities will be defined based on a different context, i.e., a non-empty subset C = / 0 ⊂ S and the probability P(A) becomes P(A | C) in this new context. Changing P(A) into P(A | C) essentially consists in a renormalization step for probabilities of states inside C, setting other probabilities to 0:

P(A | C) = P(A ∩C) P(C) (7)
We can indeed check that P(A) = P(A | S). This definition is easy to justify in the frequentist setting, since indeed P(A | C) is but the limit of a relative frequency. Justifying this definition in the subjectivist case is somewhat less straightforward. The probability P(A | C) is then assigned to the occurrence of a conditional event denoted by A | C 3 . The quantity P(A | C) is again equated to the fair price of a lottery ticket for the conditional bet on A | C. The difference with a standard bet is that if the opposite of C occurs, the bet is called off and the amount of money paid for the ticket is given back to the agent [START_REF] Finetti | Theory of Probability[END_REF]. The conditional event A | C represents the occurrence of event A in the hypothetical context where C would be true. In this operational set-up it can be shown that the identity

P(A ∩C) = P(A | C) • P(C) holds.
This definition of conditional probability contrasts with the one of Kolmogorov based on a quotient, which presupposes P(C) = 0, and proves to be too restrictive in the subjectivist setting. Indeed, in the latter setting, conditional probabilities are directly collected, so that conditional probability is the primitive concept in the subjectivist setting of De Finetti, and no longer derived from the unconditional probability function. The conditional probability satisfying [START_REF] Coletti | Probabilistic Logic in a Coherent Setting[END_REF]).

P(A ∩ C) = P(A | C) • P(C) still makes sense if P(C) = 0 (see
Under the subjectivist view, a body of knowledge consists of a set of conditional probability assignments {P(A i | C j ) = c i j , i = 1, . . . , m; j = 1, . . . , n}. Such conditional events correspond to various hypothetical contexts whose probability is allowed to be 0. The questions of interest are then (i) to derive a probability distribution in agreement with those constraints (actually a sequence of probability measures on disjoint parts of S (see [START_REF] Coletti | Probabilistic Logic in a Coherent Setting[END_REF]); (ii) to find induced optimal bounds on some conditional probability P(A|C). For instance, one may consider the probabilistic syllogism already studied by Boole and De Morgan. Namely suppose the quantities P(B|A), P(C|B) are precisely known, what can be inferred about P(C|A) ? It turns out that if P(C|B) < 1, we can only conclude that P(C|A) ∈ [0, 1]. However when the values of P(A|B) and P(B|C) are known as well, we can compute non-trivial bounds on P(C|A). These bounds can be found in [START_REF] Dubois | Qualitative reasoning with imprecise probabilities[END_REF]. For example, it can be shown that

P(C|A) ≥ P(B|A) • max 0, 1 - 1 -P(C|B) P(A|B)
and that this lower bound is tight. Yet another mathematical attempt to justify probability theory as the only reasonable belief measure is the one of R. T. [START_REF] Cox | Probability, frequency, and reasonable expectation[END_REF]. To do so he relied on the Boolean structure of the set of events and a number of postulates, considered compelling. Let g(A|B) ∈ [0, 1] be a conditional belief degree, A, B being events in a Boolean algebra, with B = / 0:

i) g(A ∩C|B) = F(g(A|C ∩ B), g(C|B)) (if C ∩ B = / 0); ii) g(A|B) = n(g(A|B)), B = /
0, where A is the complement of A; iii) function F is supposed to be twice differentiable, with a continuous second derivative, while function n is twice differentiable.

On such a basis, Cox claimed g(A|B) is necessarily isomorphic to a probability measure. This result is important to recall here because it has been repeated ad nauseam in the literature of artificial intelligence to justify probability and Bayes rule as the only reasonable approach to represent and process numerical belief degrees [START_REF] Horvitz | A framework for comparing alternative formalisms for plausible reasoning[END_REF][START_REF] Cheeseman | An inquiry into computer understanding[END_REF][START_REF] Jaynes | Probability Theory: The Logic of Science[END_REF]. However some reservations must be made. First, the original proof by Cox turned out to be faulty -see [START_REF] Paris | The Uncertain Reasoner' Companion[END_REF] for another version of this proof based on a weaker condition iii) : it is enough that F be strictly monotonically increasing in each place. Moreover, Halpern [1999a,b] has shown that the result does not hold in finite spaces, and needs an additional technical condition to get it in the infinite setting. Independently of these technical issues, it should be noticed that postulate (i) sounds natural only if one takes Bayes conditioning for granted; the second postulate requires self-duality, i.e., it rules out all other approaches to uncertainty considered in the rest of this chapter and in the next one; it forbids the representation of uncertainty due to partial ignorance as seen later on. Noticing that P(A|B) can be expressed in terms of P(A ∩ B) and P(A ∩ B), an alternative option would be to start with assuming g(A|B) to be a function of but dropping (iii). This could lead to a general study of conditional belief as outlined in [START_REF] Dubois | Conditional measures: An alternative to Cox functional equation[END_REF]. The above comments seriously weaken the alleged universality of Cox results.

g(A ∩ B) and g(A ∩ B)), adding the postulate g((A|B)|C) = g(A|B ∩ C), if B ∩ C = / 0,

Bayes Rule: Revision vs. Prediction

Assuming that a single probability measure is available, the additivity property of probability theory implies two noticeable results for conditional probabilities, that are instrumental in practice:

• The theorem of total probability: If {C 1 , . . . ,C k } forms a partition of S, then

P(A) = k ∑ i=1 P(A | C i )P(C i ).
• Bayes theorem

P(C j | A) = P(A | C j )P(C j ) ∑ k i=1 P(A | C i )P(C i )
.

The first result makes it possible to derive the probability of an event in a general context S given the probabilities of this event in various subcontexts C 1 , . . . ,C k , provided they form a partition of the set of possible states, and if probabilities of these subcontexts are available. Bayes theorem is useful to solve classification problems: suppose k classes of objects forming a partition of S. If the probability that objects in each class C j satisfy property A is known, as well as prior probabilities of classes C j , then if a new object is presented that is known to possess property A, it is easy to compute the probability P(C j | A) that this object belongs to class C j . Diagnosis problems are of the same kind, replacing "class" by "disease" and "observed property" by "symptom". The use of conditional probabilities in Bayesian networks first proposed in [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] is extensively discussed in Chapter 8 of Volume 2 of this treatise.

Most of the time, the information encoded in a probability distribution refers to some population. It represents generic information, with a frequentist meaning. One can use this information to infer beliefs about a particular situation, in which one has made partial, but unambiguous observations. This task is referred to as prediction. If P(A | C) is the (frequentist) probability of event A in context C, one measures the agent's confidence g(A | C) in proposition A, when only information C is known, by the quantity P(A | C), assuming the current situation is typical of context C. The agent's belief about proposition A is updated from g(A) = P(A) to g(A | C) = P(A | C) after observing that C is true in the current situation, and nothing else. Conditioning is thus used to update the agent's contingent beliefs about the current situation by exploiting generic information. For instance, probability measure P represents medical knowledge (often compiled as a Bayesian network). Contingent information C represents test results for a given patient. Conditional probability P(A | C) is then the probability that disease A is present for patients with test results C; this value also measures the (contingent) probability that the particular patient under consideration has disease A. We can remark that, under inference of this kind, the probability measure P does not change. One only applies generic knowledge to the reference class C, a process called focalization.

In the context of subjective probability à la De Finetti, to say that a probability distribution P is known means to know P(A | C) for all events in all contexts. The agent only chooses the conditional probability of the event of interest in the context that is in agreement with the information on the current situation.

These views of conditioning differ from a revision process leading to a change of probability measure. Indeed some authors justify conditional probability in terms of belief revision [START_REF] Gärdenfors | Knowledge in Flux[END_REF]. The quantity P(A | C) is then viewed as the new probability of A when the agent learns that C occurred. A basic principle of belief revision is minimal change: the agent revises its beliefs minimally while absorbing the new information item, interpreted as the constraint P(C) = 1. Under this view, the nature of the prior probability, and of the input information is the same, as is the posterior probability. In this revision scenario (see Chapter 14 of this volume), the probability function can be generic (e.g., frequentist, populationbased) or singular (a subjective probability) and the input information is of the same kind as P (we learn that C has actual probability 1). The revision problem is then defined as follows: find a new probability P as close as possible to P such that P (C) = 1, which obeys minimal change [START_REF] Domotor | Probability kinematics -Conditional and entropy principles[END_REF]. Using a suitable measure of relative information (e.g., Kullback-Leibler relative entropy) it can be shown that

P (A) = P(A | C), ∀A.
This revision scenario contrasts with the one of making predictions based on generic knowledge (in the form of a probability measure P describing the behavior of a population) and singular information items describing a situation of interest, even if the same tool, conditional probability, is used. As will be seen later on in this chapter and in the next one, the two tasks (revision vs. prediction) will no longer be solved by the same form of conditioning in more general uncertainty theories.

Probability Distributions and Partial Ignorance

The so-called Bayesian approach to subjective probability theory postulates the unicity of the probability distribution as a preamble to any kind of uncertainty modeling (see, for instance, [START_REF] Lindley | Scoring rules and the inevitability of probability[END_REF]), which could read as follows: any state of knowledge is representable by a single probability distribution. Note that indeed, if, following the fair bet procedure of De Finetti, the agent decides to directly assign subjective probabilities via buying prices to all singletons in S, the coherence principle forces this agent to define a unique probability distribution in this case. However, it is not clear that the limited perception of the human mind makes the agent capable of providing real numbers with infinite precision in the unit interval as prices. The measurement of subjective probability should address this issue in some way. If one objects that perhaps the available knowledge of the agent hampers the assignment of precise prices, the Bayesian approach sometimes resorts to selection principles such that the Laplace Principle of Insufficient Reason that exploits symmetries of the problem, or the maximal entropy principle [START_REF] Jaynes | Where do we stand on maximum entropy[END_REF][START_REF] Paris | The Uncertain Reasoner' Companion[END_REF]. Resorting to the latter in the subjectivist setting is questionable because it would select the uniformly distributed probability whenever it is compatible with the imprecise probabilistic information, even if imprecise probabilities suggest another trend.

Applying the Bayesian credo as recalled above forces the agent to use a single probability measure as the universal tool for representing uncertainty whatever its source. This stance leads to serious difficulties already pointed fifty years ago [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. For one, it means we give up making any difference between uncertainty due to incomplete information or ignorance, and uncertainty due to a purely random process, the next outcome of which cannot be predicted. Take the example of die tossing. The uniform probability assignment corresponds to the assumption that the die is fair. But if the agent assigns equal prices to bets assigned to all facets, how can we interpret it? Is it because the agent is sure that the die is fair and its outcomes are driven by pure randomness (because, say, they could test it hundreds of times prior to placing the bets)? Or is it because the agent who is given this die, has just no idea whether the die is fair or not, so has no reason to put more money on one facet than on another one? Clearly the epistemic state of the agent is not the same in the first situation and in the second one. But the uniformly distributed probability function is mute about this issue.

Besides, the choice of a set of mutually exclusive outcomes depends on the chosen language, e.g., the one used by the information source, and several languages or points of view can co-exist in the same problem. As there are several possible representations of the state space, the probability assignment by an agent will be language-dependent, especially in the case of ignorance: a uniform probability on one state space may not correspond to a uniform one on another encoding of the same state space for the same problem, while in case of ignorance this is the only representation left to the betting agent. [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] gives the following example. Consider the question of the existence of extra-terrestrial life, about which the agent has no idea. If the variable v refers to the claim that life exists outside our planet (v = l), or not (v = ¬l), then the agent proposes P 1 (l) = P 1 (¬l) = 1 2 on S 1 = {l, ¬l}.

However it makes sense to distinguish between animal life (al), and vegetal life only (vl), which leads to the state space S 2 = {al, vl, ¬l}. The ignorant agent is then bound to propose P 2 (al) = P 2 (vl) = P 2 (¬l) = 1 3 . As l is the disjunction of al and vl, the distributions P 1 and P 2 are not compatible with each other, while they are supposed to represent ignorance. A more casual example comes from noticing that expressing ignorance by means of a uniform distribution for v ∈ [a, b], a positive interval, is not compatible with a uniform distribution on v = log v ∈ [log(a), log(b)], while the agent has the same ignorance on v and v .

Finally, it is not easy to characterize a single probability distribution by assigning lottery prices to propositions that do not pertain to singletons of the state space. Probability theory and classical logic, understood as knowledge representation frameworks, do not get along very conveniently. A maximal set of propositions to each of which the same lower bound of probability strictly less than 1 is assigned is generally not deductively closed. Worse, the conditioning symbol in probability theory is not a standard Boolean connective. The values Prob(A|B) and Prob(B → A) = Prob(B ∪ A) can be quite different from each other, and will coincide only if they are equal to 1 [START_REF] Kyburg | The logic of risky knowledge, reprised[END_REF]. A natural concise description of a probability distribution on the set of interpretations of a language is easily achieved by a Bayesian network, not by a weighted set of propositional formulas.

Besides, in first-order logic, we should not confuse an uncertain universal conjecture [START_REF] Gaifman | Probabilities over rich languages, testing and randomness[END_REF] (for instance, Prob(∀x, P(x) → Q(x)) = α) with a universally valid probabilistic statement (for instance, ∀x,

Prob(P(x) → Q(x)) = α, or ∀x, Prob(Q(x)|P(x)) = α).
Extensions of Bayesian networks to first-order logical languages can be found in [START_REF] Milch | First-order probabilistic languages: Into the unknown[END_REF]. Finally we give a number of references to works that tried to reconcile probabilistic and logical representations (propositional, first-order, modal) in various ways: [START_REF] Halpern | An analysis of first-order logics of probability[END_REF]Bacchus, 1991;Nilsson, 1993;[START_REF] Abadi | Decidability and expressiveness for first-order logics of probability[END_REF][START_REF] Marchioni | A logic for reasoning about coherent conditional probability: A modal fuzzy logic approach[END_REF][START_REF] Jaeger | Automatic derivation of probabilistic inference rules[END_REF]Halpern andPucella, 2002, 2006;[START_REF] Jaeger | Probabilistic role models and the guarded fragment[END_REF]. See Chapter 9 in Volume 2 for a detailed account of probabilistic relational languages.

The above limitations of expressive power of single probability distributions have motivated the emergence of other approaches to uncertainty representations. Some of them give up the numerical setting of degrees of belief and use ordinal or qualitative structures considered as underlying the former subjectivist approaches. For instance [START_REF] Renooij | Enhancing QPNs for trade-off resolution[END_REF][START_REF] Parsons | Qualitative Approaches for Reasoning Under Uncertainty[END_REF][START_REF] Bolt | Introducing situational signs in qualitative probabilistic networks[END_REF][START_REF] Renooij | Enhanced qualitative probabilistic networks for resolving trade-offs[END_REF] for works that try to provide a qualitative counterpart of Bayesian nets. Another option is to tolerate incomplete information in the probabilistic approaches, which leads to different mathematical models of various level of generality. They are reviewed in the rest of this chapter and in the next chapter in this volume. Possibility theory is the simplest approach of all, and is found in both qualitative and quantitative settings [START_REF] Dubois | Possibility theory: Qualitative and quantitative aspects[END_REF]].

Conditional Events and Big-Stepped Probabilities

Instead of considering a conditional probability function P(• | C) as a standard probability distribution on C, De [START_REF] Finetti | La logique de la probabilité[END_REF] was the first scholar to consider the set of conditional probabilities {P(A | C) : A ⊆ S,C = / 0} as a probability assignment to three-events, or conditional events A | C. A conditional event can be informally understood as a conditional statement or an if-then rule: if all the currently available information is described by C, then conclude that A holds.

A three-event is so called because it partitions the state space S into three disjoint sets of states s:

• Either s ∈ A ∩C; s is called an example of the rule "if C then A". The three-event is considered as true at state s, which is denoted by Representing if-the rules by conditional events avoids some paradoxes of material implications, such as the confirmation paradox: in the material implication representation, the rule if C then A is the same as its contrapositive version if A then C. If we use material implication, we are bound to say that an example confirms a rule if it makes this material implication true. So, both s 1 ∈ A ∩C and s 2 ∈ A ∩C confirm the rule. But this is questionable: suppose the rule means all ravens are black. Then meeting a white swan would confirm that all ravens are black [START_REF] Hempel | Studies in the logic of confirmation, I and II[END_REF]. This anomaly does not occur with conditional events as A | C is not equivalent to C | A: they have the same counterexamples (e.g., white ravens) since they have the same material conditional representations, but they do not have the same examples: s 2 is an example of C | A (e.g., a white swan), but this three-event does not apply to s 1 ∈ A ∩C [START_REF] Benferhat | Modeling positive and negative information in possibility theory[END_REF].

t(A | C) = 1; • or s ∈ A ∩ C; s is called a counter-example of the rule "if C then A".
It is worth noticing that a conditional probability P(A | C) is indeed the probability of a conditional event A | C since P(A | C) is entirely determined by the pair (P(A ∩ C), P(A ∩ C)). Moreover, if all probabilities of singletons are positive, and

B | A D | C, it is clear that P(B | A) ≤ P(D | C).
A three-valued logic for conjunctions of conditional events was developed by Dubois and Prade [1994]. A three-valued extension of standard conjunction is used where the third truth-value I is a semi-group identity. The three-valued logic truthtable for conjunction and the above inference rule offer an alternative simple semantics for the non-monotonic inference system P [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF]] that captures exception-tolerant reasoning, where conditional events B | A model generic rules of the form: generally if A then B (see also the section on non-monotonic inference in Chapter 2 in this volume and Section 4.2.1 of the present chapter). Nonmonotonicity manifests itself by the fact that the inference B | A B | A ∩C does not hold (the latter has less examples than the former), so that, like in probability theory, conditional events B | A and B | (A ∩C) can coexist in the same rule base without ruling out any possible world (contrary to material conditionals in propositional logic that would enforce A ∩ C = / 0). Under this logic, to infer a plausible conclusion F from a state of knowledge described by the epistemic set E, and a conditional base (a set of conditional events) C that encodes generic information, means to infer the conditional event F | E from a conditional event obtained as a suitable conjunction of a subset of conditional events in C [Benferhat et al, 1997].

Note also that under this inference scheme, the conditional event A∩B | C follows from C = {A | C, B | C}, so that the set of plausible conclusions obtained from C will be deductively closed. But as pointed our earlier, P(A ∩ B | C) > 1θ does not follow from P(A | C) ≥ 1θ and P(B | C) > 1θ , however small θ may be.

In particular, if we minimally define A as an accepted belief whenever P(A | C) > P(A | C) (in other words P(A | C) > 1/2), we see that contrary to what happens with conditional events, a set of probabilistically accepted beliefs will not be closed in the sense of classical deduction. To ensure compatibility between symbolic inference between conditional events and accepted beliefs in the above sense, we can restrict the set of probability distributions to a subset for which deductive closure will be respected. This kind of probability measure is called big-stepped probability and is defined as follows by the condition: ∀i < n -1, p i > ∑ j=i+1,..,n p j where p i = P(s i ) and p 1 > .. > p n-1 ≥ p n > 0.

For an example of big-stepped probability distribution when n = 5, consider p 1 = 0.6, p 2 = 0.3, p 3 = 0.06, p 4 = 0.03, p 5 = 0.01. This type of exponential-like (or super-decreasing) probability distributions are at odds with uniform distributions. They offer a full-fledged probabilistic semantics to the logic of conditional events and Kraus, Lehmann and Magidor [1990]'s system P for coping with exceptions in rule-based systems [Benferhat et al, 1999b;[START_REF] Snow | Diverse confidence levels in a probabilistic semantics for conditional logics[END_REF].

Possibility Theory

Basic building blocks of possibility theory go back to a seminal paper by [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] and further works by [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty[END_REF] quite independently of the works of an English economist, [START_REF] Shackle | Decision, Order and Time in Human Affairs[END_REF] who had outlined a similar theory some thirty years before (in terms of so-called degrees of surprize to be equated to degrees of impossibility). Actually, Zadeh and Shackle did not have the same intuitions in mind. Zadeh viewed his possibility distributions as representing flexible constraints representing pieces of fuzzy information in natural language (viz. "what is the possibility that John is more than 30 years old assuming he is young"?).

In contrast Shackle tried to offer a representation of how the human mind handles uncertainty that is supposedly more faithful than probability theory. After the publication of Zadeh's paper, it soon became patent that possibility distributions were not necessarily generated from the representation of gradual properties in natural language (like young), but that they allowed to formalize a gradual notion of epistemic states by extending the disjunctive view of sets to fuzzy sets, whereby degrees of possibility, understood as plausibility, can be assigned to interpretations induced by any propositional language.

Possibility measures are maximum-decomposable for disjunction. There have companion set-functions called necessity measures, obtained by duality, that are minimum-decomposable for conjunction. They can be completed by two other setfunctions that use the same basic setting. This general framework is first recalled in the following subsections. Then the distinction between qualitative and quantitative possibility theories is recalled. Qualitative possibility theory is best couched in possibilistic logic, which is briefly outlined. This section is completed by an exposition of the relationships between qualitative possibility theory and non-monotonic reasoning, and the modeling of default rules. We end the section by a possibilitytheory rendering of formal concept analysis, which was originally developed in a very different perspective.

General Setting

Consider a mapping π v from S to a totally ordered scale L, with top denoted by 1 and bottom by 0. It can be the unit interval as suggested by Zadeh, or generally any finite chain such as L = {0, 0.1, 0.2, . . . , 0.9, 1}, or a totally ordered set of symbolic grades. The possibility scale can be the unit interval as suggested by Zadeh, or generally any finite chain, or even the set of non-negative integers. For convenience, it is often assumed that the scale L is equipped with an order-reversing map denoted by λ ∈ L → 1λ . More generally L can be a complete lattice with a top and a bottom element, denoted by 1 or 0 respectively. The larger π v (s), the more possible, i.e., plausible the value s for the variable v, that supposedly pertains to some attribute (like the age of John in Section 2.4). The agent information about v is captured by π v called a possibility distribution. Formally, the mapping π is the membership function of a fuzzy set [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF], where membership grades are interpreted in terms of plausibility. If the possibility distribution stems from gradual linguistic properties, plausibility is measured in terms of distance to fully plausible situations, not in terms of, e.g., frequency. Function π represents the state of knowledge of an agent (about the actual state of affairs), also called • π(s) = 0 means that state s is rejected as impossible; • π(s) = 1 means that state s is totally possible (= plausible).

If the universe S is exhaustive, at least one of the elements of S should be the actual world, so that ∃s, π(s) = 1 (normalised possibility distribution). This condition expresses the consistency of the epistemic state described by π. Distinct values may simultaneously have a degree of possibility equal to 1. In the Boolean case, π is just the characteristic function of a subset E ⊆ S of mutually exclusive states, ruling out all those states considered as impossible. Possibility theory is thus a (fuzzy) set-based representation of incomplete information. There are two extreme cases of imprecise information

• Complete ignorance: without information, only tautologies can be asserted. It is of the form v ∈ S, corresponding to the possibility distribution π ? v (s) = 1, ∀s ∈ S. • Complete knowledge: it is of the form v = s 0 for some value s 0 ∈ S, corresponding to the possibility distribution π s 0 v (s) = 1 if s = s 0 and 0 otherwise. Note that it is the value 0 that brings information in π v .

Possibility theory is driven by the principle of minimal specificity. It states that any hypothesis not known to be impossible cannot be ruled out. It is a minimal commitment, cautious information principle. Basically, we must always try to maximize possibility degrees, taking constraints into account. Measures of possibilistic specificity have been proposed in a way similar to probabilistic entropy [START_REF] Higashi | Measures of uncertainty and information based on possibility distributions[END_REF].

The Two Basic Set-Functions

Plausibility and certainty evaluations, induced by the information represented by a distribution π v , pertaining to the truth of proposition v ∈ A can then be defined. We speak of degrees of possibility and necessity of event A:

Π (A) = max s∈A π v (s); N(A) = 1 -Π (A) = min s / ∈A 1 -π v (s) (8)
By convention Π ( / 0) = 0 and then N(S) = 1. Π (S) = 1 (hence N( / 0) = 0) follows if π v is normalized. The symbol 1 -(•) should not suggest these degrees are numerical. It is just the order-reversing map on L.

When distribution π v takes value on the binary scale {0, 1}, i.e., there is a subset E ⊆ S such that π v (s) = 1 ⇔ s ∈ E, it is easy to see that Π (A) = 1 if and only if the proposition v ∈ A is not inconsistent with the information item v ∈ E, i.e., if

A ∩ E = / 0. Likewise, N(A) = 1 if and only if proposition v ∈ A is implied by the information item v ∈ E (since E ⊆ A). Π (A) = 0 means that it is impossible that the assertion v ∈ A is true if v ∈ E is true. N(A) = 1 expresses that the assertion v ∈ A is certainly true if v ∈ E is true.
Functions N and Π are tightly linked by the duality property N(A) = 1 -Π (A). This feature highlights a major difference between possibility and necessity measures and probability measures that are self dual in the sense that P(A) = 1 -P(A).

The evaluation of uncertainty in the style of possibility theory is at work in classical and modal logics. If K is a set of propositional formulas in some language, suppose that E is the set of its models. Consider a proposition p which is the syntactic form of the proposition v ∈ A, then N(A) = 1 if and only if K implies p, and Π (A) = 0 if and only if K ∪ {p} is logically inconsistent. Of course, the presence of p inside K encodes N(A) = 1, while the presence of its negation ¬p in K encodes Π (A) = 0. In contrast, in the propositional language of K, one cannot encode N(A) = 0 nor Π (A) = 1, e.g., that v ∈ A is unknown. To do this inside the language, one must use the formalism of modal logic (see Chapter 2 in this volume), that prefixes propositions by modalities of possibility (♦) and necessity ( ): in a modal base K mod , ♦p ∈ K mod directly encodes Π (A) = 1, and p ∈ K mod encodes N(A) = 1 (the latter merely encoded by p ∈ K in propositional logic). The duality relation between Π and N is very well known in modal logic, where it reads ♦p = ¬ ¬p. A simple modal logic (a very elementary fragment of the KD logic), called MEL (for minimal epistemic logic), has been defined by Banerjee et [START_REF] Dubois | Possibilistic logic -An overview[END_REF] with a semantics in terms of non-empty subsets of interpretations ({0, 1}-valued possibility distributions (a similar idea was first suggested by [START_REF] Mongin | Some connections between epistemic logic and the theory of nonadditive probability[END_REF]). The satisfaction of p by an epistemic set E means that E ⊆ A, if p encodes v ∈ A.

In the possibilistic setting one distinguishes three extreme epistemic attitudes pertaining to an information item v ∈ A:

• the certainty that v ∈ A is true: N(A) = 1, hence Π (A) = 1; • the certainty that v ∈ A is false: Π (A) = 0, hence N(A) = 0: • ignorance pertaining to v ∈ A: Π (A) = 1, and N(A) = 0.
These attitudes can be refined as soon as L contains at least one value differing from 0 or 1 leading to situations where 0 < N(A) < 1 or 0 < Π (A) < 1.

It is easy to verify that possibility and necessity measures saturate inequalities (2) verified by capacities:

Π (A ∪ B) = max(Π (A), Π (B)). (9) N(A ∩ B) = min(N(A), N(B)). (10)
Possibility measures are said to be maxitive and are fully characterized by the maxitivity property (9) in the finite case; necessity measures are said to be minitive and are fully characterized by the minitivity property (10) in the finite case, including when these functions take values in [0, 1].

In general possibility and necessity measures do not coincide. It is impossible for a set function to be at the same time maxitive and minitive for all events, except in case of complete knowledge (E = {s 0 }). Then N = Π also coincide with a Dirac {0, 1}-valued probability measure.

Observe that we only have

N(A ∪ B) ≥ max(N(A), N(B)) and Π (A ∩ B) ≤ min(Π (A), Π (B)),
and it may occur that the difference is maximal. Indeed in the {0, 1}-valued case, if it is not known whether A is true or false (namely, A ∩ E = / 0 and

A ∩ E = / 0), then Π (A) = Π (A) = 1 and N(A) = N(A) = 0; however, by definition Π (A ∩ A) = Π ( / 0) = 0 and N(A ∪ A) = N(S) = 1.

Two Decreasing Set Functions. Bipolarity

Yet another set function ∆ and its dual companion ∇ (first introduced in 1991, see [START_REF] Dubois | Possibility theory: Qualitative and quantitative aspects[END_REF]) can be naturally associated with the possibility distribution π v in the possibilistic framework:

∆ (A) = min s∈A π v (s); ∇(A) = 1 -∆ (A) = max s / ∈A 1 -π v (s) (11)
Observe first that in contrast with Π and N, ∆ and ∇ are decreasing functions with respect to set inclusion (hence to the logical consequence relation). Function ∆ is called strong possibility or guaranteed possibility since inside set A, the degree of possibility is never less than ∆ (A) (while Π is only a weak possibility degree that just measures consistency); dually, function ∇ is a measure of weak necessity, while N is a measure of strong necessity. Besides, the following inequality hold:

∀A, max(∆ (A), N(A)) ≤ min(Π (A), ∇(A))
provided that both π v and 1π v are normalised. Characteristic properties of ∆ and ∇ are:

∆ (A ∪ B) = min(∆ (A), ∆ (B)); ∆ ( / 0) = 1. (12) ∇(A ∩ B) = max(∇(A), ∇(B)); ∇(S) = 0. ( 13
)
From the standpoint of knowledge representation, it is interesting to consider the case when the possibility distribution π v only takes a finite number of distinct values

α 1 = 1 > • • • > α n > α n+1 = 0. It can then be described by n nested subsets E 1 ⊆ • • • ⊆ E i ⊆ • • • ⊆ E n where π v (s) ≥ α i ⇔ s ∈ E i . One can then ver- ify that ∆ (E i ) ≥ α i , while N(E i ) ≥ 1 -α i+1 for i = 1, . . . , n, and that π v (s) = max E i s ∆ (E i ) = min E i s (1 -N(E i ))
(with conventions max / 0 = 0 et min / 0 = 1). A distribution π v can thus be seen as a weighted disjunction of sets E i , from the point of view of ∆ , and as a weighted conjunction of sets E i from the point of view of N. The reading of π v viewed from ∆ offers a positive understanding of the possibility distribution, expressing to which extent each value is possible, while viewed from N, π v expressed to what extent each value is not impossible (since each value s is all the more impossible as it belongs to fewer subsets E i ).

These positive and negative flavors respectively attached to ∆ and N lay the foundation of a bipolar representation of information in possibility theory [START_REF] Benferhat | Modeling positive and negative information in possibility theory[END_REF]. The idea of bipolarity refers to an explicit handling of positive or negative features of information items [Dubois and Prade, eds.]. There are several forms of bipolarity and we only focus on the case when it comes from the existence of distinct sources of information. In the possibilistic setting, two possibility distributions δ v and π v are instrumental to respectively represent values that are guaranteed possible for v and values that are just known to be not-impossible (because not ruled out). The concept of bipolarity applies to representing knowledge as well as preferences. These distributions are differently interpreted: when representing knowledge δ v (s) = 1 means that s is certainly possible because this value or state has been actually observed, and, when representing preferences, s is an ideal choice. Moreover, when representing knowledge, δ v (s) = 0 just means that nothing is known about this value that has not been observed, and, when representing preferences, that the choice s is not at all attractive. In contrast, when representing knowledge, π v (s) = 1 means that s is not impossible (just feasible when representing preference), but π v (s) = 0 means that s is completely ruled out (or not acceptable for preferences). Intuitively, any state that is guaranteed possible should be among the non-impossible situations. So there is a coherence condition to be required: δ v ≤ π v . It corresponds to a standard fuzzy set inclusion). In possibilistic logic presented further on, the distribution π v stems from constraints of the form N(A i ) ≥ η i , and distribution δ v from statements of the form ∆ (B j ) ≥ δ j where A i ⊆ S, B j ⊆ S, and η i ∈ L, δ j ∈ L. The idea of bipolar representation is not limited to possibility theory, even if it was not often considered in other frameworks (see [Dubois et al, 2000a]).

Possibility and Necessity of Fuzzy Events

The set functions Π , N, ∆ et ∇ can be extended to fuzzy sets. The (weak) possibility of a fuzzy event F is defined by Π (F) = sup s min(F(s), π v (s)) [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF]; still using duality, the necessity of a fuzzy event then reads

N(F) = 1 -Π (F) = inf s max(F(s), 1 -π v (s))
. Functions Π and N still satisfy, respectively, maxitivity (9) and minitivity (10) properties. The values Π (F) and N(F) turn out to be special cases of Sugeno integrals (see Chapter 16 in this volume). Possibility and necessity of fuzzy events are instrumental to evaluate the extent to which a flexible condition is satisfied by an ill-known piece of data [START_REF] Cayrol | Fuzzy pattern matching[END_REF]; in particular, if π v = F, only N(F) ≥ 1/2 obtains, which at first glance may be question-able. To get N(F) = 1, the condition ∀s π v (s) > 0 ⇒ F(s) = 1 is needed, which means the inclusion of the support of π in the core of F so that any value that is possible even to a very low extent be fully in agreement with F. Such evaluations have been applied to fault diagnosis problems using a qualitative handling of uncertainty, where one may separate anomalies that more or less certainly appear when a failure occurs, from anomalies that more or less possibly appear [START_REF] Cayrac | Handling uncertainty with possibility theory and fuzzy sets in a satellite fault diagnosis application[END_REF]Dubois et al, 2001]. Functions ∆ and ∇ extend similarly to fuzzy events as ∆ (F) = inf s max(1 -F(s), π v (s)), letting ∇(F) = 1 -∆ (F) by duality, while preserving respective properties ( 12) and ( 13).

Set functions N and ∆ on fuzzy events are also very useful to represent fuzzy if-then rules (see also Chapter 10 in this volume) of the form the more v is F, the more it is sure that y is G, and the more v is F, the more it is possible that y is G respectively, where F (but possibly G as well) are gradual properties represented by fuzzy sets [START_REF] Dubois | What are fuzzy rules and how to use them[END_REF]. Indeed, the first type of rule expresses a constraint of the form N(G) ≥ F(s) while the second one is better modeled by the inequality ∆ (G) ≥ F(s). However, the first type of rule, where 1 -F(s) is viewed as the degree of possibility that the conclusion G is false, while in the second type of rule F(x) is the minimal degree of possibility that the conclusion G holds, which corresponds to the following possibility distributions on the joint domain of (x, y):

π x,y (s,t) ≤ max(1 -F(s), G(t)) and π x,y (s,t) ≥ min(F(s), G(t)).
Definitions of the strong necessity and possibility functions compatible with these inequalities are not the ones based on Zadeh's weak possibility of a fuzzy event.

Based on the following equivalence:

c ≤ max(a, 1 -b) ⇔ (1 -a) → (1 -c) ≥ b, where → is Gödel implication u → v = 1 si u ≤ v, v otherwise,
the following extensions of strong necessity and possibility of fuzzy events N et ∆ must be used:

N(G) = inf s (1 -F(s)) → (1 -π v (s)) and ∆ (G) = inf s F(s) → π v (s).
These evaluations do reduce to strong necessity and possibility of standard events, like the ones in the previous paragraph, but the necessity function satisfies N(G) = 1 when π v = G (since we expect some equivalence between statements such as it is sure that John is young and John is young). Likewise, ∆ (G) = 1 when π v = G. See [Dubois et al, 2017a] for a systematic analysis of extensions of the four set functions of possibility theory to fuzzy events. The two types of fuzzy rules reflect a bipolar view of a standard rule R of the if v ∈ A then y ∈ B, which, on a Cartesian product of domains S × T can be represented either by the constraint R(s,t)

≥ (A × B)(s,t) pointing out examples, or by the constraint R(s,t) ≥ (A × B)(s,t) ⇔ R(s,t) ≤ (A + B)(s,
-α k = α m-k ) on a bounded chain {α 0 , • • • , α m })
, it is not imperative to use a numerical setting for the measurement of possibility and necessity. When the set functions take values in the unit interval, we speak of quantitative possibility theory. When they take values in a bounded chain, we speak of qualitative possibility theory [START_REF] Dubois | Possibility theory: Qualitative and quantitative aspects[END_REF]]. In both cases, possibility theory offers a simple, but non trivial, approach to non-probabilistic uncertainty. The two versions of possibility theory diverge when it comes to conditioning. In the qualitative case, there is no product operation, and the counterpart of Bayes rule is naturally expressed replacing it by the minimum operation on the bounded chain L:

Π (A ∩ B) = min(Π (A | B), Π (B)). ( 14
)
This equation has no unique solution. In the spirit of possibility theory, one is led to select the least informative solution, according to minimal commitment, namely when B = / 0, and A = / 0:

Π (A | B) = 1 if Π (A ∩ B) = Π (B), Π (A ∩ B) otherwise. ( 15
)
This is just like conditional probability, except that we no longer make a division by Π (B). When Π (B) = 0, Π (A | B) = 1 as soon as A = / 0. It reflects the idea than you may destroy available information when conditioning on an impossible event. Conditional necessity is defined by duality as5 :

N(A | B) = 1 -Π (A | B) = 0 if Π (A ∩ B) = Π (B); N(A ∪ B) otherwise.
The least specific solution to equation ( 14) does capture an ordinal form of conditioning due to the following result:

N(A | B) > 0 ⇐⇒ Π (A ∩ B) > Π (A ∩ B)
when Π (B) > 0. Intuitively, it means that a proposition A is an accepted belief in context B if it is more plausible than its negation in this context. Like with probability, one may have that

Π (A ∩ B) > Π (A ∩ B) while Π (A ∩ B ∩C) > Π (A ∩ B ∩C) in a more restricted context B ∩ C.
An alternative approach to conditional possibility is the one of [START_REF] Coletti | Possibility theory: Conditional independence[END_REF], in which coherent possibility assessments on conditional events are defined based on equation ( 14), in the style of De Finetti's conditional probability.

In the case of quantitative possibility theory, the lack of continuity of the set function Π (A | B) in Equation ( 15) [START_REF] De Cooman | Possibility theory. Part I: Measure-and integral-theoretic ground-work; Part II: Conditional possibility; Part III: Possibilistic independence[END_REF]] has led to replace minimum by the product in this equation, mimicking conditional probability:

Π (A | B) = Π (A ∩ B) Π (B) provided that Π (B) = 0.
As we shall see, it coincides with Dempster's rule of conditioning in evidence theory (see the next chapter in this volume). More generally, on the unit interval, the product can be extended to a triangular norm, and this general setting has been studied by [START_REF] Coletti | T-conditional possibilities: Coherence and inference[END_REF] under the coherence approach in the style of De Finetti.

A major difference between possibility and probability theories concern independence. While stochastic independence between events with positive probability is a symmetric, negation-invariant, notion, since Prob(B|A) = Prob(B) is equivalent to Prob(A ∩ B) = Prob(A) • Prob(B) and to Prob(B|A) = Prob(B), this is no longer the case for possibilistic independence, several versions of which exist. For instance, in qualitative possibility theory, the equality N(B|A) = N(B) > 0 expresses that learning A does not question the accepted belief B and is not equivalent to

N(A|B) = N(A) > 0 nor to N(B|A) = N(B) > 0. Another form of independence is N(B|A) = N(B) = N(B|A) = N(B) = 0,
which means that learning A leaves us ignorant about B; see [START_REF] Dubois | A roadmap of qualitative independence[END_REF] for a complete study. There exist several definitions of conditional possibilistic independence between variables, in qualitative possibility theory, one being symmetric (Π (x, y|z) = min(Π (x|z), Π (y|z))) and one being asymmetric (Π (x|z) = Π (x|z, y)); see [Ben Amor et al, 2002]. In the quantitative setting, independence between variables (∀x, y, z, Π (x|y, z) = Π (x|z)) is symmetric since it is equivalent to ∀x, y, z, Π (x, y|z) = Π (x|z) • Π (y|z). The notion of possibilistic independence has also been studied in [START_REF] Coletti | Possibility theory: Conditional independence[END_REF].

Conditional probability is the basis of representation of uncertain information in the form of Bayesian networks. There also exist graphical possibilistic representations in quantitative possibility theory, and in qualitative possibility theory as well (see Chapter 8 in Volume 2) and some variants of possibilistic independence are useful to develop local uncertainty propagation methods.

Qualitative Possibility Theory

The main application of qualitative possibility theory is the development of possibilistic logic, an extension of classical logic that handles qualitative uncertainty, and is useful for encoding non monotonic reasoning and dealing with inconsistency. Besides, the basic setting of formal concept analysis can be seen as a set-valued counterpart of possibility theory, which leads to an interesting parallel between the two theories. We first present possibilistic logic. Note that qualitative possibility theory can be used for decision under uncertainty. Decision-theoretic foundations of qualitative possibility theory are presented in Chapter 17 of this volume.

Possibilistic Logic

The building blocks of possibilistic logic [Dubois et al, 1994;Dubois and Prade, 2004] are pairs made of a (well-formed) formula of classical logic (propositional, or first order), and a weight (or level) which may be qualitative or numerical. The weights usually belong to a totally ordered scale, but may only belong to a lattice structure with a smallest and a greatest element).

Necessity-based possibilistic logic

In its basic version, possibilistic logic only allows to consider conjunctions of pairs of the form (p, α) where p is a propositional logic formula associated with a weight α belonging to the interval (0, 1] (or to a finite totally ordered scale). The weight α is understood as a lower bound of a necessity mesure, i.e., the pair (p, α) encodes a constraint of the form N(p) ≥ α. It either corresponds to a piece of information (one is certain at level α that p is true), or a preference (p then represents a goal to be reached with priority α). The decomposability property of necessity mesures (10) ensures that we make no difference between (p ∧ q, α) and (p, α) ∧ (q, α), and thus possibilistic bases, which are sets of such possibilistic pairs, can be expressed as conjunctions of weighted clauses.

Let B N = {(p j , α j ) | j = 1, . . . , m} be a possibilistic base. At the semantic level, a possibility distribution π over the set of interpretations satisfies B N (denoted by π |= B N ) if and only if N(p) ≥ α j , j = 1, . . . , m. The least specific possibility distribution that satisfies B N exists and is of the form

π N B (s) = min j=1,...,m π (p j ,α j ) (s) = min j: s |=¬p j 1 -α j ,
where π (p j ,α j ) (s) = 1 if s |= p j and 1α j otherwise. Thus an interpretation s is all the more possible as it does not violate any formula p j with a high priority level α j , and π |= B N if and only if π ≤ π N B . The possibility distribution π N B provides a description "from above" (each pair (p j , α j ) combined by min restricts the set of interpretations regarded as possible to some extent). It takes the form of a min-max combination, since π (p j ,α j ) (s) is of the form max(M(p j )(s), 1α j ), where M(p) denotes the characteristic function of the set of models of p. So, B N can be expressed as a conjunction of weighted clauses, i.e., the extension of a conjunctive normal form, in agreement with the fact (p, α) and (q, α) is equivalent to (p ∧ q, α).

Basic possibilistic logic possesses the cut rule

(¬p ∨ q, α); (p ∨ r, β ) (q ∨ r, min(α, β )).
This rule is sound and complete for refutation, with respect to possibilistic semantics. It should be noticed that the probabilistic counterpart to this rule, namely

Prob(¬p ∨ q) ≥ α; Prob(p ∨ r) ≥ β ) Prob(q ∨ r) ≥ max(0, α + β -1)
is sound, but not complete with respect to probabilistic semantics. This is related to the fact that the deductive closure of possibilistic base {(p j , β j ) with β j ≥ α} j=1,n only contains formulas with weights at least α, while this is wrong in general for the set of probabilistic formulas {p j |Prob(p j ) ≥ α} j=1,n after closure with the corresponding resolution rule (except if α = 1).

Dual possibilistic logic with guaranteed possibility weights A dual representation for possibilistic logic bases relies on guaranteed possibility functions. A formula is then a pair [q, β ], understood as the constraint ∆ (q) ≥ β , where ∆ is a guaranteed possibility (anti-)measure. It thus expresses that all the models of q are at least possible, at least satisfactory at level

β . A ∆ -base B ∆ = {[q i , β i ] | i = 1, . . . , n} is then associated with the distribution π ∆ B (s) = max i=1,...,n π [q i ,β i ] (s) = max i: s |=q i β i , with π [q i ,β i ] (s) = min(M(q i )(s), β i ). We define π |= B ∆ if and only if ∆ (q i ) ≥ β i , ∀i = 1, . . . , n, which is equivalent to π ≥ π ∆ B . So, π ∆
B provides a description "from below" of the distribution representing an epistemic state. Taking advantage of decomposability property (12) of guaranteed possibility measures, it is easy to see that the set {[p, α], [q, α]} is equivalent to the formula [p ∨ q, α]. Then putting classical logical formulas in disjunctive normal form, we can always rewrite a dual possibilistic base B ∆ into an equivalent base where all formulas q i are conjunctions of literals.

A base B ∆ in dual possibilistic logic can always be rewritten equivalently in terms of a standard possibilistic logic N-base B N [Benferhat and Kaci, 2003;[START_REF] Benferhat | Modeling positive and negative information in possibility theory[END_REF], and conversely, in such a way that π N B = π ∆ B . However, note that ∆based possibilistic logic obeys an inference rule different from the above resolution rule for N-bases: [¬p ∧ q, α]; [p ∧ r, β ] [q ∧ r, min(α, β )]. It propagates guaranteed possibility levels in agreement with the decreasingness of set function ∆ (indeed, if r = , and q p, then α = 1 since ∆ (⊥) = 1, and the rule concludes [q, β ] from [p, β ]).

A set of pieces of possibilistic Boolean information (with a finite number of possibility levels) can thus be represented by a possibility distribution on interpretations, but also in a more compact manner under the form of a finite set of formulas associated either with a certainty (resp. priority) level, or with a level of guaranteed possibility (resp. satisfaction) when modeling knowledge (resp. preferences). Moreover, graphical representations of possibilistic bases in terms of possibilistic networks (either based on qualitative or on quantitative conditioning) have been proposed, with exact translations from one type of representation to the other [Benferhat et al, 2002]. For an introduction to possibilistic networks and their algorithms, the reader is referred to Chapter 8 in Volume 2. Possibilistic networks are also useful for preference modeling [Ben Amor et al, 2017] (see also Chapter 7 in this volume).

There exist different variants of possibilistic logic where a logical formula is, in particular, associated with lower bounds of (weak) possibility measures. They can express different forms of ignorance by asserting that two opposite events are both at least somewhat possible). Other kinds of weights can be attached to logical formulas such as time slots where one is more or less certain that the formula is true, or subsets of sources or agents that are certain to various extents that the formula is true; see [Dubois andPrade, 2004, 2014] for references. For further developments on multiple agent possibilistic logic, see [Belhadi et al, 2013].

Generalized possibilistic logic Another type of extension allows for negations or disjunctions of basic possibilistic formulas (and not only conjunctions as in standard possibilistic logic). It then results into a two-tiered logic, named "generalized possibilistic logic" (GPL) [Dubois et al, 2017c], where connectives can be placed inside or outside basic possibilistic formulas. Its semantics is in terms of subsets of possibility distributions. Indeed, elementary formulas in the logic GPL encode lower or upper bounds on the necessity or the possibility of logical formulas. GPL is both a generalization of the minimal epistemic logic MEL [Banerjee and [START_REF] Dubois | Possibilistic logic -An overview[END_REF] (where weights are only 1 or 0), and of standard possibilistic logic, in full agreement with possibility theory. GPL has been axiomatized and inference in GPL has been shown sound and complete w.r.t. semantics in terms of subsets of possibility distributions.

GPL appears as a powerful unifying framework for various knowledge representation formalisms. Among others, logics of comparative certainty, and reasoning about explicit ignorance can be modeled in GPL. There also exists a close connection between GPL and various existing knowledge representation formalisms. It includes possibilistic logic with partially ordered formulas [START_REF] Touazi | Possibilistic reasoning with partially ordered beliefs[END_REF], the logic of conditional assertions of [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF], three-valued logics [START_REF] Ciucci | A modal theorem-preserving translation of a class of three-valued logics of incomplete information[END_REF], and the 5-valued "equilibrium logic" of [START_REF] Pearce | Equilibrium logic[END_REF] as well as answer set programming [Dubois et al, 2012] (see Chapter 4 in Volume 2). More specifically, the intended meaning of answer-set programs can be made more explicit through a translation in GPL (using a 3-level scale for the possibility distributions).

Lastly, in the same way as imprecise probabilities (see next chapter in this volume) are of interest, one may think of imprecise possibilities. In that respect, the following result is particularly worth noticing: any capacity (i.e., any monotonic increasing set function) on a finite domain can be characterized by a set of possibility mesures; then capacities offer a semantics to non regular modal logics (useful for the handling of paraconsistency) [Dubois et al, 2015b], and it may provide a unifying framework for multiple source information processing in the spirit of Belnap logic.

Inconsistency and Non Monotonic Reasoning

An important feature of possibilistic logic is its ability to deal with inconsistency. The inconsistency level inc(B) of a possibilistic base B is defined as

inc(B) = max{α| B (⊥, α)}.
No formula whose level is strictly greater than inc(B) contributes to inconsistency. It can be shown that 1inc(B) is the height h(π B ) of π B , defined by h(π B ) = max s π B (s) (π B being the possibility distribution induced by B). Moreover, inc(B) = 0 if and only if the set of logical formulas appearing in B, irrespective of the weights, is consistent in the classical sense. All the formulas in B whose level is smaller or equal to inc(B) are ignored in the standard possibilistic inference mechanism; they are said to be "drowned". However, there exist other extensions of possibilistic inference that take into account formulas at the inconsistency level or below, especially those not involved in any inconsistent subset of formulas (called free formulas), see [Benferhat et al, 1999a] for a complete overview of these inferences.

The application of default rules having potential exceptions (for instance, "birds fly") to particular situations (e.g., "Tweety is a bird") about which information is incomplete, may lead to tentative conclusions (here, "Tweety flies") that become inconsistent with the new conclusions obtained when more information becomes available on such particular situations (e.g., "Tweety is a penguin"). The non monotonic nature of conditional qualitative possibility enables us to handle this problem. Indeed it allows N(B | A) > 0 and N(B | A ∩ A ) > 0 to simultaneously hold, i.e., the arrival of the piece of information A leads to reject a previously accepted proposition B in the context where we only knew A.

Indeed, a default rule "if A i then generally B j " can be represented by the possibilistic constraint Π (B j ∩ A i ) > Π (B j ∩ A i ) expressing that it is more possible to have B i true than B i false in the context where A i is true. A base of default rules is then represented by a set of such constraints, which in turn determines a set of possibility measures that satisfy them. From such a rule base, two types of inference are natural in order to deduce new rules applicable to the situation where one exactly knows A (i.e., the rules of the form "if A then generally B", which will allow us to conclude B (tentatively) in this situation).

A first type of inference, which is cautious, requires that the inequality constraint Π (A ∩ B) ≥ Π (A ∩ B) associated with B|A be satisfied by par all possibility measures that agree with the constraints (supposed to be consistent) associated with the set of default rules. A second, bolder, inference only considers the largest (the least specific) possibility distribution that is a solution of the latter constraints (it can be shown that this distribution is unique when it exists). It can be established that the first inference relation exactly corresponds the so-called preferential inference (system P [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF]) obeying basic postulates for non monotonic plausible inference (see Chapter 2 in this volume), while the second one is nothing but the "rational closure" inference of [START_REF] Lehmann | What does a conditional knowledge base entail?[END_REF]. These two types of inference can be justified also using other semantics such as conditional objects [Dubois and Prade, 1994], infinitesimal probabilities, systems Z and Z + [START_REF] Pearl | System Z: A natural ordering of defaults with tractable applications for default reasoning[END_REF][START_REF] Goldszmidt | System Z + : A formalism for reasoning with variable-strength defaults[END_REF], conditional modal logic [START_REF] Boutilier | Modal logics for qualitative possibility theory[END_REF], Halpern's plausibility measures [START_REF] Halpern | Plausibility measures: A general approach for representing uncertainty[END_REF]; see [Benferhat et al, 1997] for an overview and references. There are also semantics in terms of big-stepped probabilities [Benferhat et al, 1999b], or conditional probabilities in De Finetti sense [START_REF] Coletti | Probabilistic Logic in a Coherent Setting[END_REF]. In this latter case the rule "if A then generally B" simply corresponds to a constraint Prob(B|A) = 1 where Prob(B|A) still makes sense when Prob(A) = 0 (0 does not mean impossible here, but rather something as "negligible at first glance"), thanks to a prioritized handling of constraints induced by a partitioning of the set of interpretations [START_REF] Biazzo | Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in system P[END_REF]. The setting of possibilistic logic thus enables us to practically handle a form of default reasoning [Benferhat et al, 1998], as well as reasoning from qualitative uncertain information; il is even possible to combine both [Dupin de [START_REF] De Saint-Cyr | Handling uncertainty and defeasibility in a possibilistic logic setting[END_REF].

Belief revision theory [START_REF] Gärdenfors | Knowledge in Flux[END_REF] (see Chapter 14 in this volume), which is closely related to non monotonic reasoning, relies on the notion of epistemic entrenchment, used by the revision process for ordering the way pieces of information are called into question. It is interesting to note that an epistemic entrenchment relation is nothing but a qualitative necessity relation [START_REF] Dubois | Epistemic entrenchment and possibilistic logic[END_REF] (whose unique counterpart on a totally ordered scale is a necessity measure [START_REF] Dubois | Belief structures, possibility theory and decomposable confidence measures on finite sets[END_REF]). Moreover the possibilistic setting can make sense of the intuition that propositions in the belief base that are independent of the input information should remain after revision [START_REF] Dubois | A roadmap of qualitative independence[END_REF]. Besides, updating and revision can be combined, just as in [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF] filtering, in the qualitative setting of possibilistic logic [Benferhat et al, 2000].

Let us also mention a model of causal ascription where an agent, in the presence of a sequence of events that took place, is supposed to assert causal relations between some of these events on the basis of his beliefs on the normal course of things [START_REF] Bonnefon | Predicting causality ascriptions from background knowledge: model and experimental validation[END_REF]. The normal course of things is represented by default rules (obeying system P postulates). In this approach, causality plays a role different from the one in the logics of action (see Chapter 15 in this volume) or in diagnosis (see Chapter 21 in this volume), where causality relations are supposed to be known. The possibilistic framework for causal ascription favors "abnormal" events as potential causes which may be adopted by the agent; a detailed comparison of this approach with the probabilistic modeling of causation can be found in [START_REF] Bonnefon | Qualitative and quantitative conditions for the transitivity of perceived causation -theoretical and experimental results[END_REF]. The prediction of the way people ascribe causality relations between reported events is not to be confused with actual causality judgements that get rid of spurious correlations by means of interventions in the sense of [START_REF] Pearl | Causality. Models, Reasoning and Inference[END_REF] (such interventions can also be handled in the possibilistic setting [Benferhat and Smaoui, 2011]). The reader is referred to Chapter 9 in this volume for an overview of approaches to causality modeling.

Possibility Theory and Formal Concept Analysis

Formal concept analysis (FCA) is a knowledge representation formalism at the basis of a data mining methodology (see Chapters 12 and 13 of Volume 2). It provides a theoretical setting for learning hierarchies of concepts. Strong similarities between this representation framework and possibility theory have been pointed out in the last decade (and also to some extent with rough set theory [START_REF] Pawlak | Rudiments of rough sets. 2. Rough sets: Some extensions. 3. Rough sets and Boolean reasoning[END_REF]). This is the reason for the presence of this -maybe unexpected -subsection in this chapter.

In FCA [Barbut and Montjardet, 1970;[START_REF] Ganter | Formal Concept Analysis[END_REF], one starts with a binary relation R, called formal context, between a set of objects O and a set of properties P; xRy means that x possesses property y. Given an object x and a property y, let R(x) = {y ∈ P | xRy} be the set of properties possessed by object x and let R(y) = {x ∈ O | xRy} be the set of objects having property y. In FCA correspondences are defined between the sets 2 O and 2 P . These correspondences are Galois derivation operators. The Galois operator at the basis of FCA, here denoted by (.) ∆ (for a reason made clear in the following), enables us to describe the set of properties satisfied by all the objects in X ⊆ O as

X ∆ = {y ∈ P | ∀x ∈ O (x ∈ X ⇒ xRy)} = {y ∈ P | X ⊆ R(y)} = x∈X R(x).
In a dual manner, the set of objects satisfying all the properties in Y is given by

Y ∆ = {x ∈ O | ∀y ∈ P (y ∈ Y ⇒ xRy)} = {x ∈ O | Y ⊆ R(x)} = y∈Y R(y).
The pair of operators ((.) ∆ , (.) ∆ ) applied respectively to 2 O and 2 P constitutes a Galois connection that induces formal concepts. Namely, a formal concept is a pair (X,Y ) such that X ∆ = Y and Y ∆ = X.

In other words, X is a maximal set of objects, and Y a maximal set of properties such that each object in X satisfies all the properties in Y . Then the set X (resp. Y ) is called extension (resp. intension) of the concept. In an equivalent way, (X,Y ) is a formal concept if and only if it is a maximal pair for the inclusion

X ×Y ⊆ R.
The set of all formal concepts is naturally equipped with an order relation (denoted by ) and defined by:

(X 1 ,Y 1 ) (X 2 ,Y 2 ) iff X 1 ⊆ X 2 (or Y 2 ⊆ Y 1 )
. This set equipped with the order relation forms a complete lattice. Then association rules between properties can be found by exploiting this lattice, see [START_REF] Guigues | Familles minimales d'implications informatives résultant d'un tableau de données binaires[END_REF][START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF].

Note that X ∆ = x∈X R(x) mirrors the definition of a guaranteed possibility measure ∆ (F) = min s∈F π(s) (where π is a possibility distribution), changing L into 2 Y and π into a set-valued map (R(x) is the set of properties satisfied by object x). On the basis of this parallel with possibility theory, other operators can be introduced [Dubois and Prade, 2012]. Namely, the possibility operator (denoted by (.) Π ) and its dual necessity operator (denoted by (.) N ), as well as the operator (.) ∇ dual to the operator (.) ∆ on which FCA is based. They are defined as follows:

• X Π is the set of properties satisfied by at least one object in X:

X Π = {y ∈ P | ∃x ∈ X, xRy} = {y ∈ P | X ∩ R(y) = / 0} = x∈X R(x);
• X N is the set of properties that only the objects in X have:

X N = {y ∈ P | ∀x ∈ O (xRy ⇒ x ∈ X)} = {y ∈ P | R(y) ⊆ X} = x ∈X R(x),
where R(x) is the set of properties that x has not; • X ∇ is the set of properties that are not satisfied by at least one object outside X:

X ∇ = {y ∈ P | ∃x ∈ X, xRy} = {y ∈ P|R(y) ∪ X = O} = x ∈X R(x).
The operators Y Π , Y N , Y ∇ are obtained similarly. While the equalities X ∇ = Y and Y ∇ = X provide another characterization of usual formal concepts, it can be shown that pairs (X,Y ) such that X N = Y and Y N = X (equivalently, X Π = Y and Y Π = X) characterize independent sub-contexts (i.e., that have no object or property in common) inside the initial context [Dubois and Prade, 2012]. The pairs (X,Y ) such that X N = Y and Y N = X are such that:

(X ×Y ) ∪ (X ×Y ) ⊇ R.
It can be checked that the four sets X Π , X N , X ∆ , X ∇ are complementary pieces of information, all necessary for a complete analysis of the situation of X in the formal context K = (O, P, R). In practice, one supposes that both R(x) = / 0 and R(x) = P, i.e., each object possesses at least one property in P, but no object possesses all the properties in P. Under this hypothesis of bi-normalisation, the following inclusion relation holds:

R N (Y ) ∪ R ∆ (Y ) ⊆ R Π (Y ) ∩ R ∇ (Y )
, which is a counterpart of a relation that holds as well in possibility theory (provided that distributions π and 1π are both normalized).

Finally, let us also mention that there exists an extension of FCA to graded properties [Belohlavek, 2002], as well as an extension to formal contexts displaying incomplete or uncertain information [START_REF] Burmeister | Treating incomplete knowledge in formal concepts analysis[END_REF][START_REF] Ait-Yakoub | Asymmetric composition of possibilistic operators in formal concept analysis: Application to the extraction of attribute implications from incomplete contexts[END_REF]. Another extension deals with the capability of associating objects no longer with simple properties, but with structured descriptions, possibly imprecise, or with logical descriptions, thanks to so-called patron structures [START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Ferré | Introduction to logical information systems[END_REF]. They remain in agreement with the possibilistic paradigm [START_REF] Assaghir | A possibility theory-oriented discussion of conceptual pattern structures[END_REF].

Quantitative Possibility and Bridges to Probability

In the quantitative version of possibility theory, it is natural to relate possibility and probability measures. It can be done in several independent ways. In the following, we outline the three main ones: namely, a possibility distribution can be viewed as a likelihood function in non-Bayesian statistics, possibility (resp. necessity) degrees of events can be viewed either as upper (resp. lower) probability bounds, or as a suitable transformation of exponents of infinitesimal probabilities.

Possibility Distributions as Likelihood Functions

The idea of casting likelihood functions inside the framework of possibility theory was suggested by [START_REF] Smets | Possibilistic inference from statistical data[END_REF], but it has roots in considerations relating statistical inference and consonant belief functions (another name for necessity measures) in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]'s book; see also [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF] on this topic. The connection was formalized in [START_REF] Dubois | A semantics for possibility theory based on likelihoods[END_REF], and further studied in the coherence framework of De Finetti in [START_REF] Coletti | Coherent conditional probability as a measure of uncertainty of the relevant conditioning events[END_REF]. Consider an estimation problem where the value of a parameter θ ∈ Θ that governs a probability distribution P(• | θ ) on S is to be determined from data. Suppose the obtained data is described by the information item A. The function (θ ) = P(A | θ ), θ ∈ Θ is not a probability distribution, it is a likelihood function: a value θ is all the more plausible as P(A | θ ) is greater, while this value can be ruled out if P(A | θ ) = 0 (in practice, less that a small relevance threshold). Such a function is often renormalized so that is maximal value is 1, since a likelihood function is defined up to a positive multiplicative constant. There are some good reasons why one may see (θ ) as a degree of possibility of θ , and let π(θ ) = P(A | θ ) (up to renormalizing). First, it can be checked that, in the absence of prior probability on Θ , ∀B ⊆ Θ , P(A | B) is upper and lower bounded as follows: min However, note that under this view, possibility degrees are known in relative values, which means that not all basic notions of possibility theory apply (e.g., comparing the informativeness of π and π using fuzzy set inclusion, by checking if π ≤ π becomes questionable).

Possibility as Upper Probability

Alternatively, possibility degrees valued on [0, 1] viewed as an absolute scale can be exactly defined as upper probability bounds as [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] had the intuition from the start. The generation process can be described as follows: consider an increasing sequence of nested sets E 1 ⊂ E 2 ⊂, . . . , ⊂ E k and let α 1 ≤ α 2 ≤, . . . , ≤ α k ∈ [0, 1], such that α i is a lower bound on P(E i ). This type of information is typically provided by an expert estimating a quantity v by means of set E k with confidence α k that E k contains v. Consider the probability family P = {P : P(E i ) ≥ α i , ∀i = 1, . . . , k}. It is easy to check [START_REF] Dubois | Putting rough sets and fuzzy sets together[END_REF]] that the function P * (A) = inf P∈P P(A) is a necessity measure and the function P * (A) = sup P∈P P(A) is a possibility measure induced by the possibility distribution:

∀s ∈ S, π(s) = min i=1,...,k max(E i (s), 1 -α i ). ( 16
)
where E i (s) = 1 if s ∈ E i and 0 otherwise. See [START_REF] De Cooman | Supremum preserving upper probabilities[END_REF] for the extension of this result to infinite settings. Each pair (E k , α k ), made of a set and its confidence level is encoded by the possibility distribution max(E i (s), 1α i ), where 1α i is an upperbound on the probability that v ∈ E k . Equation ( 16) just performs the conjunction of these local distributions. It is clear that π is a very concise encoding of the probability family P. Conversely, the (convex set) of probability measures encoded by a possibility distribution π can be retrieved as

P(π) = {P, P(A) ≤ Π (A), ∀A measurable} = {P, P(A) ≥ N(A), ∀A mesurable},
and it can be checked that Π (A) = sup P∈P(π) P(A). In the case where the sets E i are not nested, the above formula (which is in agreement with possibilistic logic semantics of Section 4.2.1) only yields an approximation of the probability family P; better approximations can be obtained by means of pairs of possibility distributions enclosing P [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes. II. Clouds[END_REF]. This view of possibility measures cast them in the landscape of imprecise probability theory studied in the next chapter of this volume.

Nested shortest dispersion intervals can be obtained from a given probability distribution (or density) p, letting E α = {s : p(s) ≥ α}, and α α = P(E α ). The obtained possibility distribution, that covers p as tightly as possible, is called optimal probability-possibility transform of p [Dubois et al, 2004] and is instrumental for comparing probability distributions in terms of their peakedness or entropies (by comparing their possibility transforms in terms of relative specificity) [START_REF] Dubois | Comparing probability measures using possibility theory: A notion of relative peakedness[END_REF].

Possibility as Infinitesimal Probability

Ranking functions, originally called ordinal conditional functions (OCF), have been proposed by [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF][START_REF] Spohn | The Laws of Belief: Ranking Theory and Its Philosophical Applications[END_REF] to represent the notion of belief in a setting that is basically equivalent to possibility theory, but for the direction and nature of its value scale. Each state of the world s ∈ S is assigned a degree κ(s) not in [0, 1], but in the set of non-negative integers N, (sometimes even ordinals). The convention for ranking functions is opposite to the one in possibility theory, since the smaller κ(s) the more possible s. It is more in agreement with a degree of potential surprise suggested by [START_REF] Shackle | Decision, Order and Time in Human Affairs[END_REF]: κ(s) = +∞ means that s is impossible, while κ(s) = 0 means that nothing opposes to s being the true state of the world. Set functions similar to possibility distribution are then built in the same style as [START_REF] Shackle | Decision, Order and Time in Human Affairs[END_REF]:

κ(A) = min s∈A κ(s) and κ( / 0) = +∞.
More specifically, [START_REF] Spohn | A general, nonprobabilistic theory of inductive reasoning[END_REF] interprets κ(A) as the integer exponent of an infinitesimal probability P(A) = ε κ(A) , which is indeed in agreement with the unionminitivity property κ(A ∪ B) = min(κ(A), κ(B)) of ranking functons.

Conditioning is defined by [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF] as follows: B) . Casting ranking functions in possibility theory is easy, due to the following transformations [START_REF] Dubois | Epistemic entrenchment and possibilistic logic[END_REF] :

κ(s | B) = κ(s) -κ(B) si s ∈ B +∞ sinon It is obvious that κ(s | B) is the exponent of the infinitesimal conditional probability P(s | B) = ε κ(s) /ε κ(
π κ (s) = 2 -κ(s) , Π κ (A) = 2 -κ(A) .
As a consequence possibility distributions π κ and functions Π κ take values on a subset of rational numbers in

[0, 1]. Function Π κ is indeed a possivility measure since Π κ (A ∪ B) = 2 -min(κ(A),κ(B)) = max(Π κ (A), Π κ (B)).
Moreover, for the conditional ranking function one obtains ∀s,

π κ(s|B) = 2 -κ(s)+κ(B) = 2 -κ(s) 2 -κ(B) = π κ (s) Π κ (B) ,
which is the product-based conditioning of possibility theory. The converse (logarithmic) transformation of a possibility distribution into a ranking function is only possible if it maps real numbers to non-negative integers. More on the comparison between possibility theory and ranking functions can be found in [START_REF] Dubois | Qualitative and semi-quantitative modeling of uncertain knowledge -A discussion[END_REF]. Note that this approach is often presented as qualitative while it is a numerical one. In some applications, or when modeling expert opinions, it may be more convenient to describe degrees of (dis)belief by means of integers rather than by real numbers in [0, 1]. However it is easier to introduce intermediary grades with a continuous scale. The integer scale of ranking functions has been used recently by [START_REF] Kern-Isberner | Structural inference from conditional knowledge bases[END_REF] to encode non-monotonic inferences and applied in [START_REF] Eichhorn | Using inductive reasoning for completing ocfnetworks[END_REF] to belief networks.

The Cube of Opposition: A Structure Unifying Representation Frameworks

Many knowledge representation formalisms, although they look quite different at first glance and aim at serving diverse purposes, share a common structure where involutive negation plays a key role. This structure can be summarized under the form of a square or a cube of opposition. This in particular true for frameworks able to represent incomplete information. It can be observed that the properties of non empty intersection and of inclusion related by negation are at the basis of possibility theory, formal concept analysis, as well as rough set theory. It is still true for belief functions presented in the next chapter in this volume. This section first introduces the square and the cube of opposition, and indicates the formalisms to which it applies.

The traditional square of opposition [START_REF] Parsons | The traditional square of opposition[END_REF], which dates back to Aristotle's time, is built with universally and existentially quantified statements in the following way. Consider four statement of the form (A): "all P's are Q's", (O): "at least one P is not a Q", (E): "no P is a Q", and (I): "at least one P is a Q". They can be displayed on a square whose vertices are traditionally denoted by the letters A, I (affirmative half) and E, O (negative half), as pictured in Figure 1 (where Q stands for "not Q"). As can be checked, noticeable relations hold in the square provided that there a non empty set of P's to avoid existential import problems:

1. A and O (resp. E and I) are the negation of each other; 2. A entails I, and E entails O (it is assumed that there is at least one P); 3. A and E cannot be true together; 4. I and O cannot be false together.

Another classical example of such a square is obtained with modal logic operators by taking A as p, E as, ¬p, I as ♦p, and O as ♦¬p. This structure largely forgotten with the advent of modern logic after G. Boole, was rediscovered by [START_REF] Blanché | Structures Intellectuelles. Essai sur l'Organisation Systématique des Concepts[END_REF] and then by [START_REF] Béziau | New light on the square of oppositions and its nameless corner[END_REF] who both advocate its interest. In particular, Blanché noticed that adding two vertices U and Y defined respectively as the disjunction of A and E, and as the conjunction of I and O, leads to a hexagon that includes three squares of opposition in the above sense. Such a hexagon is obtained each time we start with three mutually exclusive statements, such as A, E, and Y, and it turns out that this structure is often encountered when representing relationships between concepts on the same domain (e.g., deontic notions such as permission, obligation, interdiction, etc.).

Switching to first order logic notations (e.g., A becomes ∀x, P(x) → Q(x)), and negating the predicates, i.e., changing P into ¬P, and Q in ¬Q leads to another similar square of opposition aeoi, where we also assume that the set of "not-P's" is non-empty. Altogether, we obtain eight statements that may be organized in what may be called a cube of opposition [START_REF] Reichenbach | The syllogism revised[END_REF]. The front facet and the back facet of the cube are traditional squares of opposition, and the two facets are related by entailments.

Such a structure can be extended to graded notions [START_REF] Ciucci | Structures of opposition induced by relationsthe Boolean and the gradual cases[END_REF], using an involutive negation such as 1 -(•), and where the mutual exclusiveness of A and E translates into a sum of degrees less or equal to 1, while entailments are translated by inequalities between degrees (in agreement with residuated implications). An example of a graded cube is given by possibility theory. Indeed, assuming a normalized possibility distribution π : S → [0, 1], and also assuming that 1π is normalized (i.e., ∃s ∈ S, π(s) = 0), we obtain a cube of opposition on Fig. 2, linking Π (A), N(A), ∆ (A), ∇(A), Π (A), N(A), ∆ (A), and ∇(A). The front and back facets form two squares of opposition, while the side facets express a different property, namely inequalities such as min(Π (A), ∇(A)) ≥ max(N(A), ∆ (A)). Since these set functions rely on ideas of graded inclusion and degrees of non-empty intersections, the fact that they fit with a graded structure of cube of opposition should not be too surprizing. In fact, the structure of cube of opposition is quite general. As noticed in [START_REF] Ciucci | Structures of opposition induced by relationsthe Boolean and the gradual cases[END_REF], any binary relation R on a Cartesian product X × Y (one may have Y = X) gives birth to a cube of opposition, when applied to a subset. Indeed, we assume R = / 0. Let R(x) = {y ∈ Y | (x, y) ∈ R}. R denotes the complementary relation ((x, y) ∈ R iff (x, y) ∈ R), and R t the transposed relation ((y, x) ∈ R t if and only if (x, y) ∈ R); let R(y) = {x ∈ X | (x, y) ∈ R} = R t (y). Moreover, it is assumed that ∀x, R(x) = / 0, which means that the relation R is serial, namely ∀x, ∃y such that (x, y) ∈ R. Similarly, R t is also supposed to be serial, i.e., ∀y, R(y) = / 0, as well as R and its transpose, i.e. ∀x, R(x) = Y and ∀y, R(y) = X.

Let T be a subset of Y and T its complement. We assume T = / 0 and T = Y . The composition is defined in the usual way R(T ) = {x ∈ X | ∃t ∈ T, (x,t) ∈ R}. From the relation R and the subset T , one can define the four following subsets of X (and their complements):

R(T ) = {x ∈ X | T ∩ R(x) = / 0} (17) R(T ) = {x ∈ X | R(x) ⊆ T } (18) R(T ) = {x ∈ X | T ⊆ R(x)} (19) R(T ) = {x ∈ X | T ∪ R(x) = X}. ( 20
)
These four subsets and their complements can be nicely organized into a cube of opposition (Fig. 3). Some of the required conditions for the cube hold thanks to seriality (which plays the role of normalization in possibility theory). The front facet of the cube fits well with the modal logic reading of the square where R is viewed as an accessibility relation, and T as the set of models of a proposition p. Indeed, p (resp. ♦p) is true in world x means that p is true at every (resp. at some) possible world accessible from x; this corresponds to R(T ) (resp. R(T )) which is the set of worlds where p (resp. ♦p) is true.

Other than the semantics of modal logics, there are a number of AI formalisms that exploit a relation and to which the cube of opposition of Fig. 3 applies: formal concept analysis, as seen in Section 4.2.3, rough sets induced by an equivalence relation (see Section 2.6), or abstract argumentation based on an attack relation between arguments. Graded squares or cubes also apply to belief functions and to upper and lower probabilities [START_REF] Pfeifer | Probabilistic squares and hexagons of opposition under coherence[END_REF] presented in the next chapter in this volume, [Dubois et al, 2015a], as well as to aggregation functions such as Sugeno integrals used in multiple criteria aggregation and qualitative decision theory, or yet Choquet integrals [Dubois et al, 2017b], both presented in Chapter 16 in this volume.

This common structure is deeply related to the interplay of three negations as revealed by the relational cube. In contrast the square and the cube collapse to a segment in case of probabilities since they are autodual.

The cube of opposition lays bare common features underlying many knowledge representation formalisms. It exhibits fruitful parallelisms between them, which may even lead to highlight some missing components present in one formalism and currently absent from another.

Conclusion

In this chapter, we have tried to show that while probability theory properly captures uncertainty due to the randomness of precisely observed phenomena, the representation of uncertainty due to incomplete information requires a different setting having roots in classical and modal logics, where incompleteness is a usual feature. The corresponding uncertainty framework is possibility theory, which allows for a qualitative representation of uncertainty as well as a quantitative one. It has been shown that numerical possibility theory is appropriate provided that the available information items, although imprecise, are consonant, i.e., do not contradict each other. The handling of imprecise and possibly conflicting information items require joint extensions of probability and quantitative possibility theory studied in the next chapter.

Scalable Uncertainty Management (SUM'10), Toulouse, Sept. 27-29, Springer, no. 6379 in LNCS, pp 70-83 Bacchus F (1991)

  a ⊕ b) are the operators minimum min(a, b), product (a × b), and truncated addition max(0, a + b -1) (resp. maximum max(a, b), probabilistic sum a + ba × b, and bounded sum min(1, a + b)). Probability measures are recovered by defining a ⊕ b = min(1, a + b) (equivalently a⊥b = max(0, a + b -1)), and possibility measures and necessity respectively for a ⊕ b = max(a, b) and for a⊥b = min(a, b

  The threeevent is considered as false at state s, which is denoted by t(A | C) = 0;• or s ∈ C; then the rule "if C then A" is said not to apply to s. In this case the three-event takes a third truth-value at s, which is denoted by t(A | C) = I where I stands for inapplicable. A three-event A | C can thus be interpreted as a pair (A ∩ C, A ∩ C) of disjoint sets of examples and counter-examples. A qualitative counterpart of Bayes rule holds, noticing that as the set-valued solutions of the equation A∩C = X ∩C are all sets {X : A ∩C ⊆ X ⊆ A ∪C}, which is another possible representation of A | C (as an interval in the Boolean algebra of subsets of S). This definition of conditional events as pairs of subsets suggests a natural consequence relation between conditional events defined as follows[Dubois and Prade, 1994]:B | A D | C ⇔ A ∩ B C ∩ Dand C ∩ D A ∩ B which reads: all examples of B | A are examples of D |C and all counter-examples of D | C counter-examples of B | A. Note that only the second condition coincides with the deductive inference between material conditional counterparts of the threeevents. Material conditionals highlight counter-examples of rules, not examples. When ordering the truth-values as 0 < I < 1, this inference also reads B | A D |C ⇔ t(B | A) ≤ t(D | C).

  t) excluding counter-examples, where the overbar means complementation and where A + B = A × B. The view of an if-then rule as a conditional event B|A is thus retrieved. 4.1.4 Conditioning in Possibility Theory: Qualitative vs. Quantitative Settings Since the basic properties in possibility are based on minimum, maximum and an order-reversing map on the uncertainty scale (1 -(•) on the unit interval, and 1

  | θ ) ≤ P(A | B) ≤ max θ ∈B P(A | θ ) It suggests that we can apply the maxitivity axiom to get an optimistic estimate of P(A | B) from {P(A | θ ), θ ∈ B}. However, insofar as (b) is the likelihood of θ = b, and we extend it to all subsets B of Θ , we should have that (B) ≥ (b), for all b ∈ B. Hence, in the absence of prior probability, we can identify (B) as a possibility measure with distribution π(θ ) = P(A | θ ) [Coletti and Scozzafava, 2003]. Considering the lower bound of P(A | B) would yield a guaranteed possibility measure.

Fig. 1

 1 Fig. 1 Square of opposition

Fig. 2

 2 Fig. 2 Cube of opposition of possibility theory

Fig. 3

 3 Fig. 3 Cube induced by a relation R and a subset T

  Representing and Reasoning With Probabilistic Knowledge: A Logical Approach to Probabilities. MIT Press, Cambridge, Ma Banerjee M, Dubois D (2014) A simple logic for reasoning about incomplete knowledge. Int J Approx Reasoning 55:639-653 Barbut M, Montjardet B (1970) Ordre et Classification: Algèbre et Combinatoire. Hachette Belhadi A, Dubois D, Khellaf-Haned F, Prade H (2013) Multiple agent possibilistic logic. J of Applied Non-Classical Logics 23(4):299-320 Belnap ND (1977a) How a computer should think. In: Contemporary Aspects of Philosophy, Oriel Press, Boston, pp 30-56 Belnap ND (1977b) A useful four-valued logic. In: Epstein G (ed) Modern Uses of Multiple-valued Logic, Reidel, pp 8-37 Belohlavek R (2002) Fuzzy Relational Systems. Foundations and Principles. Kluwer Ben Amor N, Benferhat S, Dubois D, Mellouli K, Prade H (2002) A theoretical framework for possibilistic independence in a weakly ordered setting. Int J of Uncertainty, Fuzziness and Knowledge-Based Systems 10(2):117-155 Ben Amor N, Dubois D, Gouider H, Prade H (2017) Possibilistic preference networks. Information Sciences to appear Benferhat S, Kaci S (2003) Logical representation and fusion of prioritized information based on guaranteed possibility measures: Application to the distance-based merging of classical bases. Artificial Intelligence 148:291-333 Benferhat S, Smaoui S (2011) Inferring interventions in product-based possibilistic causal networks. Fuzzy Sets and Systems 169(1):26-50 Benferhat S, Dubois D, Prade H (1997) Nonmonotonic reasoning, conditional objects and possibility theory. Artificial Intelligence 92:259-276 Benferhat S, Dubois D, Prade H (1998) Practical handling of exception-tainted rules and independence information in possibilistic logic. Applied Intelligence 9:101-127 Benferhat S, Dubois D, Prade H (1999a) An overview of inconsistency-tolerant inferences in prioritized knowledge bases. In: Dubois D, Prade H, Klement E (eds) Fuzzy Sets, Logic and Reasoning about Knowledge, Applied Logic Series, vol 15, Kluwer, Dordrecht, pp 395-417 Benferhat S, Dubois D, Prade H (1999b) Possibilistic and standard probabilistic semantics of conditional knowledge bases. J of Logic and Computation 9:873-895 Benferhat S, Dubois D, Prade H (2000) Kalman-like filtering in a possibilistic setting. In: Horn W (ed) Proc.14th Europ.Conf. on Artificial Intelligence (ECAI'00), Berlin, Aug. 20-25, pp 8-12 Benferhat S, Dubois D, Garcia L, Prade H (2002) On the transformation between possibilistic logic bases and possibilistic causal networks. Int J of Approx Reasoning 29:135-173

  an epistemic state distinguishing what is plausible from what is less plausible, what is the normal course of things from what is not, what is surprising from what is expected. It represents a flexible restriction on what is the actual state with the following conventions (similar to probability, but opposite to Shackle's potential surprise scale) 4 :

In fact, in this chapter, v denotes an ill-known entity that may be for instance a random variable in a probabilistic setting, or rather an imprecisely known entity but which does not vary strictly speaking.

Apparent, because the mathematical settings proposed byKolmogorov and De Finetti [1974] are different, especially for the notion of conditioning, even if the Kolmogorov setting seems to be overwhelmingly adopted by mathematicians.

We come back to the logic of conditional events at the end of this section.

If L = N, the conventions are opposite: 0 means possible and ∞ means impossible.

The Bayesian-like rule in terms of necessity measures,N(A ∩ B) = min(N(A | B), N(B)), is trivial. Its least specific solution, minimizing necessity degrees, is N(A | B) = N(A ∩ B) = min(N(A), N(B)), which defines in turn Π (A | B) = Π (B ∪ A).It comes down to interpret a conditional event as a material implication.

Thierry Denoeux, Didier Dubois, and Henri Prade