40 Years of Research in Possibilistic Logic – a Survey

1 Introduction

Possibilistic logic is an offspring of possibility theory. Possibility theory offers a setting for the representation of epistemic uncertainty due to incomplete information. This theory was pioneered by the economist G. L. S. Shackle who introduced a calculus of degrees of potential surprise (degrees of impossibility in modern language); it was independently rediscovered by L. A. Zadeh who focused on the idea of graded possibility in relation with the modeling of linguistic information, and finally developed in [Dubois and Prade, 1988] jointly using the dual pair of possibility and necessity measures associated with a possibility distribution.

Possibilistic logic [Dubois et al., 1994] (in its basic form) manipulates classical logic formulas associated with lower bounds of necessity measures understood as certainty levels. Then the modus ponens rule takes, semantically, the form:

where N is a necessity measure, p and q are logical formulas, and α, β ∈ [0, 1]. This corresponds to the old intuition (dating back to Theophrastus [Rescher, 1976]) that the strength of a conclusion reflects the strength of the weakest premise(s). This weighted inference rule appears for the first time (in English) in [Prade, IJCAI'1983,130-136] (equation 56). However it is only in the second half of the 1980s that the first elements of a full-fledged possibilistic logic have begun to be developed, starting with [Dubois et al., 1987].

Incomplete information is everywhere and properly handling epistemic uncertainty is important. As we shall see, possibilistic logic, by stratifying knowledge in certainty levels, offers a simple setting, close to classical logic, for dealing with uncertainty and inconsistency, but possibilistic logic can also take other forms, such as possibilistic networks or matrices. What's more, possibilistic logic inherits its versatility from the great representational power of possibility theory.

This article offers an up-to-date and as complete as possible survey of possibilistic logic developments in the last 40 years. There have already been several surveys that are all partly or fully outdated. Some surveys either focus on relations with modal logic [Dubois and Prade, 2018], or offer a more applied perspective [Dubois and Prade, 2019]. Besides, there are also longer and more detailed introductions (but now incomplete) [Dubois et al., 1994; Dubois and Prade, 2014]. The present survey, with a renewed structure, offers a fresh look at possibilistic logic.

The paper is organized in two main parts. The first part presents the main theoretical aspects of possibilistic logic and insists on representational issues. The second part reviews a series of areas of AI research to which possibilistic logic has been applied and can still contribute. More precisely, the first part, after having restated what possibility and necessity measures are, recalls the syntax, the semantics and the proof theory of basic possibility theory where only constraints of the formN(p)≥α are handled. Then the main features of the possibilistic matrix calculus, and of possibilistic (Bayesian-like) networks, are presented. Then various types of extensions of possibilistic logic are reviewed: i) for handling inconsistency; ii) for dealing with symbolic certainty levels (whose precise value remains unknown); iii) for introducing new kinds of weights for dealing with time, sources, agents, reasons, or ill-known certainty levels, thanks to the use of generalized possibility and necessity functions taking their values on a Boolean or on a pseudo-complemented distributive lattice rather than a linear scale; iv) for coping with bipolar information (i.e., having positive and negative components) thanks to the notion of guaranteed possibility, another set function of possibility theory; v) for handling not only conjunctions, but also negations and disjunctions of the constraints present in basic possibilistic logic. The first part ends with a brief discussion of the link with related calculi: Spohn's ranking functions and Markov logic. The second part surveys the use of possibilistic logic in default reasoning, in belief revision, information fusion, in description logics, in logic programming, in preference modeling and decision, in argumentation, and in machine learning. A short subsection is also devoted to databases applications due to close concerns with knowledge representation.

2 Theoretical and Representational Issues

This first part deals with the basics of possibilistic logic and related representation settings, before presenting various extensions of possibilistic logic, and finally discussing relations with other frameworks.

2.1 Possibility Theory

In possibility theory, the available information is represented by possibility distributions. A possibility distribution is a mapping π from a set U, understood as a set of mutually exclusive states, values, or alternatives (one of which being the actual world, if U is exhaustive), to a totally ordered scale S, with top denoted by 1 and bottom by 0. Different types of scales may be used from a finite scale S = {1 = λ1 > . . . λn > λn+1 = 0} in the qualitative case, to the unit interval S = [0, 1] in the quantitative case, see [Dubois and Prade, 2016] for other options. π(u) = 0 means that u is rejected as impossible; π(u) = 1 means that state u is fully possible. The larger π(u), the more possible u. The consistency of the epistemic state described by π is expressed by the normalization condition ∃u, π(u) = 1 that makes sure that at least one u is fully possible. When information is all-or-nothing, π is the characteristic function of some subset E of U and π(u) ∈ {0, 1}. Complete information corresponds to situations where E is a singleton. S is assumed to be equipped with an order-reversing map n: n(0) = 1, n(1) = 0, here denoted n(λ) = 1 - λ, ∀λ ∈ S.

A possibility measure Π and a dual necessity measure N are associated with a possibility distribution π: ∀A ⊆ U, Π(A) = supu∈A π(u); N(A) = 1-Π(Ac ) = infu/∈A 1-π(u) with Ac = U \A. When the possibility distribution reduces to a classical subset E ⊆ U, we have: i) Π(A) = 1 if A∩E ̸= ∅, and 0 otherwise; ii) N(A) = 1 if E ⊆ A, and 0 otherwise. Π(A) (resp. N(A)) evaluates to what extent event A is consistent with π (resp. A is implied by π). By normalization, Π(U) = N(U) = 1 and Π(∅) = N(∅) = 0.

Possibility measures are characterized by the "maxitivity" property Π(A ∪ B) = max(Π(A),Π(B)), and necessity measures are "minitive": N(A ∩ B) = min(N(A), N(B)). Due to the normalization of π, min(N(A),N(Ac )) = 0 and max(Π(A),Π(Ac )) = 1, or equivalently Π(A) = 1 whenever N(A) > 0, namely something somewhat certain should be first fully possible, i.e. consistent with the available information. Moreover, one cannot be somewhat certain of both A and Ac , without being inconsistent. We only have N(A ∪ B) ≥ max(N(A), N(B)), which goes well with the idea that one may be certain about the event A ∪ B, without being really certain about more specific events like A or B. Possibility and necessity depart from a probability P , which is self-dual, and such that P(Ac ) = 0 ⇒ P(A) = 1, while N(Ac ) = 0 ̸⇒ N(A) = 1 (but Π(Ac ) = 0 ⇒ Π(A) = 1).

Certainty-qualified statements of the form "A is certain to degree α" can be represented by the constraint N(A) ≥ α. The largest, so the least restrictive, possibility distribution π that obeys this constraint is given by [Dubois and Prade, 1988]: π(A,α)(u) = 1 if u ∈ A, π(A,α)(u) = 1-α otherwise.

If α = 1 we get the characteristic function of A. If α = 0, we get total ignorance. It is a key building-block of the semantics of possibilistic logic.

2.2 Basic Possibilistic Logic

A basic possibilistic logic (BPL for short) formula is a pair (p, α) where p is a classical closed logic formula and α a certainty level in S \{0}, viewed as a lower bound of a necessity measure: (p, α) means semantically N(p) ≥ α. Due to the minitivity of necessity measures, a BPL base, i.e., a set of BPL formulas, can be put in an equivalent clausal form.

Syntactic aspects Here we focus on the case where p in (p, α) is a proposition; for (basic) possibilistic first order logic, see [Dubois et al., 1994].

Axioms and inference rules. The BPL axioms [Dubois et al., 1994] are those of propositional logic, where each axiom schema has certainty 1. Its inference rules are:

• if β ≤ α then (p, α) ⊢ (p, β) (certainty weakening)
• (¬p ∨ q, α), (p, α) ⊢ (q, α), ∀α ∈ (0, 1] (modus ponens). Moreover the following inference rule is valid:
• (¬p ∨ q, α), (p ∨ r, β) ⊢ (q ∨ r, min(α, β)) (resolution) The following inference rule, we call formula weakening holds also as a consequence of α-β-resolution.
• if p ⊢ q then (p, α) ⊢ (q, α), ∀α ∈ (0, 1]

Inference and consistency. Let K = {(pi, αi), i = 1, ...,m} be a set of BPL formulas. Then, proving K ⊢ (p, α) amounts to proving K, (¬p, 1) ⊢ (⊥, α) by repeated application of resolution rule. Moreover, note that K ⊢ (p, α) iff Kα ⊢ (p, α) iff (Kα)∗ ⊢ p, where Kα = {(pi, αi) ∈ K, αi ≥ α} and K∗ = {pi | (pi, αi) ∈ K}. The certainty levels stratify the knowledge base K into nested level cuts Kα, i.e. Kα ⊆ Kβ if β ≤ α. A consequence (p, α) from K can only be obtained from formulas in Kα.

The inconsistency level of K is defined by inc(K) = max{α|K ⊢ (⊥, α)}. Formulas (pi, αi) in K such that αi > inc(K) are safe from inconsistency. Indeed, if α>inc(K), (Kα)∗ is consistent, and K∗ consistent ⇔ inc(K) = 0.

The complexity of the inference in BPL remains similar to the one of classical logic [Lang, 2001].

Semantic aspects The semantics of BPL [Dubois et al., 1994] is expressed in terms of possibility distributions, and necessity measures on the set Ω of interpretations ω of the language. The base K is semantically associated with the possibility distribution, which is a fuzzy set of interpretations:

where [pi] is the characteristic function of the models of pi, namely [pi](ω) = 1 if ω ⊨ pi and [pi](ω) = 0 otherwise. This is in agreement with certainty qualification: Intuitively, this means that any interpretation that is a counter-model of pi, is all the less possible as pi is more certain; πK is obtained as the min-based conjunction of the possibility distribution representing each formula. As expected, NK(pi) ≥ αi for i=1,. . . ,m, where NK is defined from πK. The semantic entailment is defined by K ⊨ (p, α) if and only if ∀ω, πK(ω) ≤ π{(p,α)}(ω). BPL is sound and complete [Dubois et al., 1994] wrt this semantics:

Note that the sole use of the (locally optimal) resolution rule Prob(¬p ∨ q) ≥ α, Prob(p ∨ r) ≥ β ⊢ Prob(q ∨ r) ≥ max(0, α+β-1), cannot insure the completeness of a probabilistic counterpart of BPL.

Moreover, we have inc(K) = 1-maxω∈Ω πK(ω), which acknowledges the fact that the normalization of πK is equivalent to the classical consistency of K∗ .

2.3 Matrix Form

The representation of a rule "if p then q" is more naturally assessed in terms of conditioning than in logical terms using material implication that allows for contraposition. The conditioning Π(q | p) of q by p, in possibility theory, obeys the identity

where ⋆ is min or the product, depending on whether we choose to be within a qualitative or quantitative framework. 1 For ⋆ = min, the greatest, least restrictive solution of the above equation is Π(q | p) = Π(p ∧ q) if Π(p ∧ q) < Π(p), Π(q | p) = 1 otherwise. For ⋆ = product, the (quantitative) conditioning looks like a probabilistic conditioning: Π(q | p) = Π(p∧q) Π(p) provided that Π(p) ̸= 0 and corresponds to Dempster's rule of conditioning in Shafer evidence theory. Conditional necessity is defined by duality: N(q|p) = 1 - Π(¬q|p).

Using qualitative conditional possibility, a matrix calculus (see [Dubois and Prade, 1986][2020] for thorough studies) can be developed using the max-min matrix product ⊗

Such a matrix product can be applied to a set of m parallel uncertain rules of the form "if a1i (x) is P 1 i and · · · and aki (x) is P k i then bi(x) is Qi" (i = 1, · · · ,m) that relates variables pertaining to the attribute values of some item x, and where the P j i 's and Qi are classical subsets in the corresponding attribute domains. Then, it has been shown that the result of their joint application (including the fusion of the results obtained from each rule) can be put under the form of a minmax matrix product [Dubois and Prade, 2020]; see [Baaj et al., 2021] for the general case. The output of this min-max product is a possibility distribution over a collection of mutually exclusive alternatives (induced by weighted conclusions on the Qi's).

Besides, the conditional view can be closely related to possibilistic logic, since N(q|p) = N(¬p ∨ q) if N(q|p) > 0.

2.4 Possibilistic Networks

As with joint probability distributions, a joint possibility distribution associated with ordered variables X1, . . . ,Xn can be decomposed in terms of conditional possibility distributions using a chain rule, using ⋆ = min, or product:

1 In this latter case possibility and necessity can be interpreted as upper and lower probability, see, e.g., [Dubois and Prade, 2020].

In a way similar to Bayes nets, independence enables the simplification of the decomposition. However 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 a stronger one, being asymmetric: Π(x|z) = Π(x|z, y). In the quantitative setting, product-based independence between variables (∀x, y, z, Π(x|y, z) = Π(x|z) where Π(y, z) > 0) is symmetric since it is equivalent to ∀x, y, z, Π(x, y|z) = Π(x|z) · Π(y|z). Efficient algorithms exist for inference in possibilistic networks. [Ben Amor et al., 2003], [Levray et al., 2020].

Possibilistic nets and BPL bases are compact representations of possibility distributions. A remarkable feature of this framework is that possibilistic nets can be directly translated into BPL bases and vice-versa, both when conditioning is based on minimum or on product [Benferhat et al., 2002a].

Hybrid representations formats have been introduced where local BPL bases are associated to the nodes of a graphical structure rather than conditional possibility tables [Benferhat and Smaoui, 2007].

Thus, the BPL setting offers multiple equivalent representation formats: set of prioritized logical formulas, possibilistic networks, but also set of conditionals of the form Π(p ∧ q) > Π(p ∧ ¬q) (⇔ N(q|p) > 0), all semantically equivalent to preorders on interpretations (i.e., to possibility distributions). There are algorithms for translating one format in another [Benferhat et al., 2002a].

Besides, possibilistic networks have been investigated from the standpoint of causal reasoning, using the concept of intervention, that comes down to enforcing the values of some variables so as to lay bare their influence on other ones [Benferhat, 2010].

2.5 Handling Inconsistency

The inconsistency level inc(K) of a BPL base K provides a tool for handling inconsistency. However it suffers from a "drowning effect" since all the formulas below inc(K) are lost even if they are not involved in some inconsistent subbase. There are different ways to enlarge the set of consequences that can be inferred fromK [Benferhat et al., 1999a].

One way to do it while preserving a consistent set of consequences is the following. Given a BPL base K, we build its paraconsistent completion Ko made of bi-weighted formulas: for each formula (p, α) in K, we compute a triple (p, β, γ) where β (resp. γ) is the highest degree with which p (resp. ¬p) is supported in K (p is said to be supported in K at least at degree β if there is a consistent sub-base of (Kβ)∗ that entails p).

The subset of formulas of the form (p, β, 0) in Ko are not paraconsistent, and leads to safe conclusions. We can still get a larger set of consistent conclusions from Ko as follows. We need two evaluations: i) the undefeasibility level of a consistent set S of formulas: UD(S) = min{β | (p, β, γ) ∈ Ko and p ∈ S} ; ii) the unsafeness level of a consistent set S of formulas: US(S) = max{γ|(p, β, γ) ∈ Ko and p ∈ S}. Then an entailment ⊢SS, named safely supported consequence relation, is defined by Ko ⊢SS q if and only ∃ a minimal consistent subset S that classically entails q such that UD(S) > US(S). It can be shown that the set {q | Ko ⊢SS q} is classically consistent. See [Dubois and Prade, 2015] for details, discussions and other approaches to the handling of inconsistency in the BPL setting, including quasi-possibilistic logic where the use of resolution after the introduction of a disjunction is forbidden (to get rid of the ex falso quodlibet sequitur).

2.6 Symbolic Possibilistic Logic

There may exist several reasons for handling the certainty levels of BPL formulas in a symbolic manner: in particular, keeping track of the impact of some levels in the computation, or acknowledging that their value is unknown. The latter concern leads to consider that the values of certainty levels associated to formulas (still assumed to belong to a totally ordered scale) are unknown, while the relative ordering between some of them may be partially known. In [Benferhat and Prade, 2005] this is encoded by means of a possibilistic-like manysorted propositional logic, where formulas are clauses with special literals that refer to the levels. Constraints about the ordering of some of the levels translate into logical formulas of the corresponding sort and are gathered in a distinct auxiliary knowledge base. The inference process is characterized by the use of "forgetting variables" for handling the symbolic levels, and hence an inference process is obtained by means of a DNF compilation of the two knowledge bases.

When the ordering of the weights is completely known, this encoding provides a way of compiling a possibilistic knowledge base in order to be able to process inference from it in polynomial time [Benferhat and Prade, 2006].

In an approach that ties in with the previous one for handling partial knowledge on the relative strength of certainty levels, two syntactic inference methods are proposed: one calculates the necessity degree of a possibilistic formula using the notion of minimal inconsistent sub-base, while the other is inspired from ATMS (Assumption-based Truth Maintenance System), using nogoods and labels [Cayrol et al., 2018].

2.7 Lattice-Based Extensions of Possibilistic Logic

There exist several extensions of possibilistic logic where weights are certainty levels combined with sets such as time periods [Dubois et al., 1991], sets of sources, or groups of agents [Belhadi et al., 2016; Dubois and Prade, 2024a] that lead to use a pseudo-complemented distributive lattice structures. When the sets are replaced by a unique singleton (i.e., we consider one time instant, one source, or one agent), basic possibilistic logic is restored.

We take the example of multi agent possibilistic logic for explaining the idea. Now (propositional) formulas are associated with a subset of agents: Each formula (p,A) means that at least all the agents in A believe that p is true. Such a Boolean weighting introduces a noticeable difference: the supremum of two proper subsets may be the whole universe (while the supremum of two non top levels is never the top level in a totally ordered scale). This is why the explicit strengthening rule (p,A), (p,B) ⊢ (p,A ∪ B) is needed beside inference rules for subset weakening, modus ponens and resolution, at the syntactic level. Soundness and completeness theorems hold with respect to a semantics in terms of set-valued possibility and necessity functions: Π(p) = ⋃w⊨p π(w) where π(w) is the maximal subset of agents that find the interpretation ω possible, and N(p) = [Π(¬p)]c = ⋂w⊨¬p [π(w)]c (where c denotes the set complementation.

We have now two types of normalization leading to a richer view of (in)consistency: one which means that each agent finds at least one ω possible (∀a, ∃ω, a ∈ π(ω), i.e. no agent is inconsistent). This condition is weaker than the condition ∃ω,π(ω) = All (All is the set of all agents), which means that there is an interpretation that all agents believe possible, expressing a collective consistency condition. For instance, the base K = {(p, A), (¬p, Ac )} violates the latter condition, but not the former.

This extends to the general case where propositions are both associated with a certainty level and a set of agents. Then formulas are of the form (p, α/A) where A is a subset of agents and α ∈ (0, 1], which reads "at least all agents in A believe p at least at level α". Then the semantics is in terms of fuzzy set-valued possibility and necessity functions: The symbolic weight α/A represents a fuzzy set of agents a with membership grades α if agent a ∈ A, and 0 otherwise.

A logic for reasoning about reasons [Dubois and Prade, 2024a] handles pairs of the form (p, x) where p and x are two propositional logical formulas expressed in two distinct languages, p is called a claim, and x a reason. The formula (p, x) thus reads "x is a reason for p". (p, x) is weaker than (¬x ∨ p, 1) (the former does not entail the latter). The truth of (p, x) means that all the situations where x is true are reasons to believe p. The semantics of the reason-based logic is isomorphic to the one of the previous multi-agent logic; an extension can accommodate the strength of reasons [Dubois and Prade, 2024a]. The logic of reasons is akin to the logic of supporters [Lafage et al., 1999], but a bit simpler.

Interval-based possibilistic logic [Benferhat et al., 2011; Benferhat et al., 2015] is another lattice-based extension of possibilistic logic, where the possible values of ill-known certainty levels are restricted by intervals.

Let us finally mention a way to remain with a linearly ordered structure while enriching the scale. In BPL, only the smallest weight of the formulas used in a proof is retained; no difference is made for instance between a proof with only one weak premise and a proof with several weak premises of the same strength. This can be captured by using a new resolution rule (¬a ∨ b, ⃗α); (a ∨ c, ⃗ β) ⊢ (b ∨ c, ⃗α⃗ β) where ⃗α and ⃗ β are lists of weights, and ⃗α⃗ β is the list obtained by concatenation. We can then rank-order the proofs according to their strength using a lexicographic ordering of the vectors (once they have been completed with 1's for making them of equal length); this is outlined in [Dubois and Prade, 2019].

2.8 Bipolar Possibilistic Logic

In possibility theory there are two other set functions: i) a measure of guaranteed possibility or strong possibility (see,e.g., [Dubois and Prade, 2014]) : ∆(A) = infu∈A π(u) which estimates to what extent all states in A are possible according to evidence. ∆(A) can be used as a degree of evidential support for A, and its dual conjugate ∇ is such that ∇(A) = 1 - ∆(Ac ) = supu̸∈A 1 - π(u). ∇(A) evaluates the degree of potential or weak necessity of A, as it is 1 only if some state u out of A is impossible. Thus, the functions ∆ and ∇ are decreasing wrt set inclusion (in full contrast with Π and N which are increasing). They satisfy the characteristic properties ∆(A∪B) = min(∆(A), ∆(B)) and ∇(A ∩ B) = max(∇(A), ∇(B)).

Thus the constraint ∆(p) ≥ γ, syntactically denoted [p, γ], expresses that any model of p is at least possible with degree γ. This can be represented by the fuzzy set δ[p,γ](ω) = 0 if ω |= ¬p, and δ[p,γ](ω) = γ if ω |= p. A set of constraints P = {[qj, γj]|j = 1, k} is then represented by the possibility distribution δP (ω) = maxj=1,k δ[qj ,γj ](ω) by cumulating the guaranteed possibilities. Note that δP is obtained as the max-based disjunctive combination of the representation of each formula in P. This contrasts with πK (in Section 2.2) obtained as a min-based conjunctive combination. Thus, a possibility distribution can be represented from above by means of necessity-based constraints, and from below by means of guaranteed possibility-based constraints. At the syntactic level, necessity-based constraints are naturally associated with a weighted CNF decomposition, while ∆- based constraints leads to a weighted DNF decomposition. The latter is governed at the inference level by the following counterpart of the resolution rule

A ∆-based constraint [p, γ] naturally fits with the expression of positive information, i.e., interpretations that are models of p are possible for sure at least at degree γ, while a N-based constraint (p, α) corresponds to a negative expression stating that the counter-models of p are somewhat impossible (their possibility is at most 1 - α). Thus more positive information increases δP by making more interpretations more actually possible, while more negative information decreases πK by restricting more the possible worlds [Benferhat et al., 2008].

One can use either formulas based on ∆ or formulas based on N to represent the available information, whichever seems more practical. If it makes sense to distinguish between positive information and negative information (for instance, actual examples of prices, and prices allowed by regulations), we need to keep separate a K and a P knowledge base each semantically associated with their respective distributions (supposed to satisfy the consistency condition δP ≤ πK); see [Dubois et al., 2000], [Benferhat et al., 2002b] for settings for handling this latter case.

2.9 Generalized Possibilistic Logic

In basic possibilistic logic, only conjunctions of possibilistic logic formulas are allowed. But since (p, α) is semantically interpreted as N(p) ≥ α, a possibilistic formula can be manipulated as a propositional formula that is true (if N(p) ≥ α) or false (if N(p) < α). Then possibilistic formulas can be combined with all propositional connectives, including disjunction and negation. This is generalized possibilistic logic (GPL) [Dubois et al., 2017b; Dubois and Prade, 2018]. GPL is a two-tiered propositional logic, in which propositional formulas are encapsulated by weighted modal operators interpreted in terms of necessity and possibility measures.

GPL uses a finite scale of certainty degrees Λk = {0, 1k , 2k ,...,1} (k ∈ N \ {0}) ; Λ+k = Λk \ {0}. The language of GPL, LkN, is built on top of a propositional language L as follows: i) If p ∈ L, α ∈ Λ+k , then Nα(p) ∈ LkN; ii) if φ ∈ LkN,ψ ∈ LkN, then ¬φ and φ ∧ ψ are also in LkN. Here Nα(p) stands for (p, α), emphasizing the closeness with modal logic. So, an agent asserting Nα(p) has an epistemic state such that N(p) ≥ α > 0. Hence ¬Nα(p) stands for N(p) < α, which means N(p) ≤ α - 1k and thus Π(¬p) ≥ 1 - α + 1k . In particular, Π1(p) ≡ ¬N1k (¬p) if k > 1. So, in GPL, one can distinguish between the absence of sufficient certainty that p is true (¬Nα(p)) and the stronger statement that p is somewhat certainly false (Nα(¬p)).

The semantics of GPL is as in BPL defined in terms of normalized possibility distributions over propositional interpretations, where possibility degrees in Λk. A model of a GPL formula Nα(p) is any Λk-valued possibility distribution such that N(p) ≥ α. More generally, the set of possibility distributions satisfying a formula in GPL has not always a largest element, as in BPL.

GPL can be viewed as a fragment of the modal logic KD without nested modalities, but modalities are graded. See [Dubois et al., 2017b] for its axiomatics, soundness and completeness results, complexity studies. GPL is a powerful unifying framework for various knowledge representation formalisms, including possibilistic logic with partially ordered formulas, or a logic of conditional assertions. Reasoning about explicit ignorance, or some multiple agent reasoning tasks, such as the muddy children problem can be also handled in GPL [Dubois and Prade, 2019].

Similarly, a generalizedmulti-agent possibilistic logic that allows for the disjunction and negation of its formulas have been recently studied and a similar construct also applies to the logic of reasons [Dubois and Prade, 2024a]. .

2.10 Relations to Other Frameworks

Spohn's ranking functions are similar to possibility measures but they are valued on positive integers. So, they use different scales for grading (im)plausibility, which makes their expressive powers somewhat different. Indeed, there is no logical side for the ranking functions since there is no counterpart to the weighted modus ponens, and Spohn's conditioning, based on addition, is inspired by infinitesimal probabilities, while possibilistic logic uses only idempotent operations such as max and min [Dubois and Prade, 2016].

Markov logic uses weighted formulas to compactly encode a probability distribution, but the weights are not easy to interpret. However one can always build a possibilistic logic base that exactly captures a Markov logic network; see [Kuzelka et al., 2015], [Dubois et al., 2017b].

3 Applications

Applications of possibilistic logic can be found in many areas of AI research. Due to the limited space for references, we selected a small sampling of references for each application.

3.1 Uncertainty Handling and Default Reasoning

BPL was originally designed for propagating uncertainty in inference engines for expert systems, taking advantage of the matrix format [Farreny et al., 1986].

The ability of BPL to deal with inconsistency, using the inconsistency level of a knowledge base is exploited in default reasoning. A default rule "generally, if p then q" is represented by the conditional Π(p ∧ q) > Π(p ∧ ¬q) ⇐⇒ N(q|p) > 0. Thus, N(q|p) > 0 expresses that in the context where p is true, having q true is strictly more possible than q false. Like with probability, this conditioning is not monotonic. One may have that N(q|p) > 0, while the opposite conclusion N(¬q|p ∧ p′ ) > 0 holds in a more restricted context p ∧ p′ .

Then by laying bare the largest possibility distribution underlying a consistent set of defaults Π(pi ∧qi) > Π(pi ∧¬qi) for i = 1, n, it is possible to stratify the set of defaults according to their specificity (roughly speaking the most specific defaults receive the higher levels), and then to encode them by possibilistic logic formulas [Benferhat et al., 1998]: each default is turned into a possibilistic clause (¬ai∨bi, N(¬ai∨bi)), where N is computed from the greatest possibility distribution induced by the set of constraints modeling default knowledge base. This encoding takes advantage of the fact that when new sure information is received, the level of inconsistency of the base cannot decrease, and if it strictly increases, some inferences that were safe before are now drawn in the new inconsistency level of the base and are thus no longer allowed, hence a non monotonic consequence mechanism takes place. This approach has been proved to be in full agreement with a postulates-based approach to nonmonotonic reasoning [Benferhat et al., 1997]. This is also equivalent with a probabilistic modeling of conditionals in terms of a special type of probability distributions named big-stepped probabilities [Benferhat et al., 1999b].

3.2 Belief Revision

Nonmonotonic reasoning and belief revision can be closely related, so PL finds application also in belief revision. Indeed, comparative necessity relations (which can be encoded by necessity measures) are nothing but the epistemic entrenchment relations that underly well-behaved belief revision processes. This enables the PL setting to provide syntactic revision operators that apply to possibilistic knowledge bases, including the case of uncertain inputs [Benferhat et al., 2010; Qi and Wang, 2012]. In BPL, the epistemic entrenchment is made explicit through the certainty levels of the formulas. Besides, in a revision process it is expected that all formulas independent of the validity of the input information should remain in the revised state of belief; this idea may receive a precise meaning using a definition of possibilistic causal independence between events [Dubois et al., 1999a].

3.3 Information Fusion

The combination of possibility distributions can be equivalently performed in terms of PL bases: The syntactic counterpart of the pointwise combination of two possibility distributions π1 and π2 into a distribution π1 ⊛ π2 by any monotonic combination operator ⊛ such that 1 ⊛ 1 = 1, can be computed, following an idea first proposed in [Boldrin and Sossai, 1997]. Namely, if the BPL base K1 is associated with π1 and the base K2 with π2, a BPL base K1⊛2 semantically equivalent to π1 ⊛ π2 is given by : {(pi, 1 - (1 - αi) ⊛ 1) s.t. (pi, αi) ∈ K1}∪{(qj, 1-1⊛(1-βj)) s.t. (qj, βj) ∈ K2} ∪ {pi ∨ qj, 1 - (1 - αi) ⊛ (1 - βj)) s.t. (pi, αi) ∈ K1, (qj, βj) ∈ K2}. For ⊛ = min,we get K1⊕2 = K1 ∪ K2 with πK1∪K2 = min(π1, π2) as expected (conjunctive combination). For ⊛ = max (disjunctive combination), we get Γ1⊕2 = {(pi ∨ qj, min(αi, βj)) s.t. (pi, αi) ∈ K1, and (qj, βj) ∈ K2}. With non idempotent ⊕ operators, some reinforcement effects may be obtained. See, e.g., [Kaci et al., 2000] for further studies on possibilistic logic merging operators. Besides, this approach can be also applied to the syntactic encoding of the merging of classical logic bases based on Hamming distance (where distances are computed between each interpretation and the different classical logic bases, thus giving birth to counterparts of possibility distributions); see, e.g., [Benferhat and Kaci, 2003] where a ∆-based representation is used. See [Benferhat and Sossai, 2006] for an illustrative example.

3.4 Description Logic

The possibilistic handling of uncertainty in description logic was first proposed in [Qi et al., 2007]. It has computational advantages, in particular in the case of the possibilistic DLLite family where the extension of the expressive power of DL-Lite is done without additional extra computational costs [Benferhat et al., 2013]; then it is also convenient to use the min operation for the fusion of possibilistic DL-Lite bases.

A tractable method for computing a single possibilistic repair for a partially preordered weighted ABox that may be inconsistent with respect to the TBox has been proposed in [Belabbes and Benferhat, 2022].

3.5 Logic Programming

Various proposals have been made for providing a possibilistic handling of uncertainty in logic programming and answerset programming [Alsinet et al., 2002; Nicolas et al., 2006; Nieves et al., 2007; Hu´e et al., 2014; Bauters et al., 2015].

Besides, a remarkable application of GPL is its capability to encode answer set programs, using a 3-valued scale Λ2 = {0, 1/2, 1}. Then, we can discriminate between propositions we are fully certain of and propositions we consider only more plausible than not. It is enough to encode nonmonotonic ASP rules (with negation as failure) within GPL and lay bare their epistemic semantics. For instance, the ASP rule a ← b ∧ not c is encoded as N1(b) ∧ Π1(¬c) → N1(a) in GPL. See [Dubois et al., 2017b].

3.6 Databases

Provenance calculus, based on two operations forming a semi-ring, combines and propagates annotations associated with data. This calculation, when based on max and min operations, exactly corresponds to query evaluation when data are labeled with levels of certainty, as in BPL [Dubois and Prade, 2024b].

BPL has been recently shown to be of interest in database design where the presence of tuples in the database is possible only to some extent, and where functional dependencies are certain only to some extent [Link and Prade, 2019].

3.7 Preference Modeling and Qualitative Decision

A BPL formula (p, α) can represent a goal p with a priority level α. Preferences such as "I prefer p to q and q to r" (where p, q, r may not be mutually exclusive) can be represented by the possibilistic base P = {(p∨q∨r, 1), (p∨q, 1γ), (p, 1-β)} with γ < β < 1, as a set of more or less imperative goals. Other formats such as conditionals, possibilistic networks, ∆-based representation are also of interest for representing preferences [Benferhat et al., 2001]. Moreover the expression of preferences may be bipolar: stating situations that are more or less strongly rejected, and situations that are guaranteed to be satisfactory to some extent. Let us mention the representational equivalence [Benferhat et al., 2004] between qualitative choice logic (QCL) and actual (guaranteed) possibility logic.

Possibilistic logic formulas with symbolic weights have been used in preference modeling [Ben Amor et al., 2018]. Then, interpretations (corresponding to the different alternatives) are compared in terms of symbolic vectors acknowledging the satisfaction or the violation of the formulas associated with the different (conditional) preferences, using suitable order relations.

Possibility theory provides a setting for qualitative decision under uncertainty where pessimistic and optimistic decision criteria have been axiomatized. The counterpart of these criteria, when knowledge and preferences are under the form of two distinct BPL bases, is given by [Dubois et al., 1999b]:

• the pessimistic utility u∗(d) of decision d is the maximal α ∈ S s.t. Kα ∧ d ⊢PL Pν(α),
• the optimistic utility u∗ (d) of d is the maximal ν(α) ∈ S s.t. Kα ∧ d ∧ Pα ̸≡ ⊥,

where S is a finite bounded totally ordered scale, ν the ordered reversing map of this scale; Kα is a set of classical logic formulas gathering the pieces of knowledge that are certain at a level at least α, and where Pβ is a set of classical logic formulas made of a set of goals whose priority level is strictly greater than β. An optimal pessimistic decision leads for sure to the satisfaction of all goals in Pν(α) with a priority as low as possible, using only a part Kα of knowledge which is which has high certainty. An optimal optimistic decision maximizes the consistency of all the more or less important goals with all the more or less certain pieces of knowledge.

3.8 Argumentation

A possibilistic defeasible logic programming language which combines features from argumentation theory and logic programming, also incorporating the treatment of possibilistic uncertainty has been proposed in [Alsinet et al., 2008].

Possibilistic logic can be used for representing the mental states of the agents (beliefs possibly pervaded with uncertainty, and prioritized goals), for revising belief bases and for describing the decision procedure for selecting a new offer in argumentation-based negotiation [Amgoud and Prade, 2004].

The logic of reasons [Dubois and Prade, 2024a] which handles formulas (p, x) expressing that "x is a reason for p", where negation can be applied to p, x and (p, x), offers a rich setting for argumentative reasoning.

3.9 Machine Learning

The learnability of possibilistic logic theories have been investigated in [Persia and Ozaki, 2020], showing that many polynomial time learnability results for classical logic can be transferred to the respective possibilistic extension.

Bipolar possibilistic logic offers a graded setting for extending the framework of version space learning [Prade and Serrurier, 2008].

BPL can be also applied to inductive logic programming (ILP). Indeed having a stratified set of first-order logic rules as an hypothesis in ILP is of interest for learning both rules covering normal cases and more specific rules for exceptional cases [Serrurier and Prade, 2007], [Kuzelka et al., 2017].

A cascade of min-max product of matrices representing possibilistic if-then rules has a structural resemblance with a min-max neural network. Such a cascade can be shown to be equivalent to a min-max neural net, each matrix product corresponding to a layer, and the activation function used being the identity. See [Baaj et al., 2021] for details. Moreover [Baaj and Marquis, 2025] offers a very comprehensive neurosymbolic possibilistic approach.

3.10 Other Applications

Other applications may be found for modeling desires using ∆ functions [Dubois et al., 2017a], or for expressing agents' goals by possibilistic logic in Boolean games when agents may have incomplete knowledge of each other's preferences [Clercq et al., 2018].

Still another application is the encoding of control access policies [Benferhat et al., 2003]. A formal description of security policies is necessary to check if security properties are satisfied or not. Access control rules, guaranteeing the properties of confidentiality and integrity, are encoded in terms of stratified knowledge bases. The stratification reflects the hierarchy between roles and is useful for dealing with conflicts.

4 Conclusion

This paper has reviewed a large amount of works on the development of possibilistic logic and its applications. Possibilistic logic is well-suited for the representation of incomplete information and more or less entrenched accepted beliefs. It remains close to classical logic and offers a rich, simple and versatile setting for qualitative reasoning under uncertainty. Possibility, as probability, deserves consideration.