A Crash Course on Generalized Possibilistic Logic

Abstract

This paper proposes a concise overview of the role of possibility theory in logical approaches to reasoning under uncertainty. It shows that three traditions of reasoning under or about uncertainty (set-functions, epistemic logic and three-valued logics) can be reconciled in the setting of possibility theory. We offer a brief presentation of basic possibilistic logic, and of its generalisation that comes close to a modal logic albeit with simpler more natural epistemic semantics. Past applications to various reasoning tasks are surveyed, and future lines of research are also outlined.

1 Introduction

Uncertainty often pervades information and knowledge. For this reason, the handling of uncertainty in inference systems has been an issue for a long time in artificial intelligence (AI). As logical formalisms have dominated AI research for several decades, this problem was first tackled using modal logics or non-monotonic reasoning, or yet many-valued logics. Key-issues are reasoning under incomplete information (how to infer useful conclusions despite incompleteness?) and inconsistent information (how to protect useful conclusions from inconsistency?).

With the advent of Bayesian networks, Bayesian probabilities have become prominent at the forefront of AI methods, challenging the original supremacy of logical representation settings. However, Bayesian networks are in some sense miraculous, because, viewed as representing human information, they are neither incomplete nor inconsistent. The problem of dealing with incomplete probabilistic knowledge is then avoided, especially by Bayesian probability proponents, assuming that any state of knowledge can be accounted for by a unique probability distribution. However, due to the self-duality of probabilities, the Bayesian approach cannot distinguish between the lack of belief in a proposition and the belief in its negation, which is precisely what incomplete information is all about. The need for this distinction seems to have led to the emergence of ad hoc uncertainty calculi in early expert systems.

Besides, there has been a divorce between logic and probability in the early 20th century. Logic was then considered as a foundation for mathematics, while probability theory was found instrumental in representing statistical data. The school of subjective probability took it for granted that degrees of belief should be additive and self-dual, which led to paradoxes when trying to account for ignorance. Yet, logic and probability were originally motivated by the formalisation of some aspects of human reasoning. Boole, De Morgan, De Finetti used to attach probabilities to logical formulas and try to make deductions from them. But so doing, and in contrast with Bayesian networks, you run the risk of at worst assigning incompatible probabilities, or at best only deriving probability intervals rather than precise probabilities for conclusions. While this can be considered as a weakness of the logical approach, one may also claim that this state of facts is more faithful to human knowledge, which is often incomplete and sometimes inconsistent. There are now well-defined approaches to uncertainty that try to marry additivity and incompleteness [1]. These settings are characterized by the existence of a pair of dual measures for distinguishing between the support of a proposition and the lack of support of its negation, for instance Walley’s imprecise probability theory, Shafer’s evidence theory, and possibility theory, the latter first outlined by Shackle [2] in a very hostile scientific environment, later on taken up by Cohen [3] and Zadeh [4].

Possibility theory has a remarkable situation among the settings devoted to the representation of imprecise and uncertain information. First, it may be numerical or qualitative [5]. In the first case, possibility measures and the dual necessity measures can be regarded respectively as upper bounds and lower bounds of ill-known probabilities; they are also particular cases of Shafer plausibility and belief functions respectively. In fact, possibility measures and necessity measures constitute the simplest, non trivial, imprecise probability system. Second, when qualitative, possibility theory provides a natural approach to the grading of possibility and necessity modalities on finite ordinal scales. Especially, possibility theory has a logical counterpart, namely possibilistic logic [6], which remains close to classical logic. In this overview paper, we focus our attention on the unifying power of all-or-nothing possibility theory for epistemic reasoning. Then we briefly present possibilistic logic (PosLog), which handles degrees of certainty, and its recent extension called generalized possibilistic logic (GPL). Then we briefly review some application areas for PosLog and GPL.

2 Three Approaches to Handling Incomplete Knowledge

There seems to be three traditions for dealing with incomplete information and the ensuing representation of beliefs.

The Set-Function Tradition. Set-functions are used to assign degrees of beliefs to propositions represented by subsets of possible states of affairs, also called events: for instance, subjective probability adopts this point of view. More generally, if S represents a set of states of affairs and A is a subset thereof, the idea is to attach a degree of confidence g(A) usually in the unit interval (but not always, for instance Spohn [7] uses integers). The main properties of the set-function g are monotonicity with inclusion ($g(B) \ge g(A)$ whenever $A\subseteq B$), and limit conditions $g(\emptyset ) = 0, g(S) = 1$. Other examples of such confidence functions g are possibility and necessity measures, belief or plausibility functions, upper and lower probabilities [1].

The Multiple-Valued Logic Tradition. Very early in the 20th century, scholars in logic like Łukasiewicz realized that it is not always possible to declare that a given proposition is true or is false. Due to a lack of knowledge, only weaker qualifiers may be used, such as possible, unknown, or yet indeterminate. So the idea was to define the epistemic status of complex propositions from truth-tables extending the ones of classical logic, augmenting the set of truth-values with a new symbol lying between true and false and standing for unknown and the like, while sticking to the propositional syntax. This led to three-valued logics such as the ones of Łukasiewicz or Kleene. Of course, it was then natural to extend this view to more truth-values, even a continuum thereof. In the same spirit, Belnap [8] proposed to add a fourth truth-value standing for the idea of conflicting information about a proposition.

The Modal Logic Tradition. In this approach, the idea is to represent the belief modality at the syntactic level using a necessity symbol $\Box$ that prefixes propositions from a standard propositional language, and more generally, any formula, in fact. In this way, one can explicitly express that a proposition p is believed or known, writing $\Box p$, and we can make a clear syntactic distinction between the fact of not believing p (i.e., $\lnot \Box p$) and believing its negation (i.e., $\Box \lnot p$). This is the setting of epistemic or doxastic logics originally due to von Wright, Hintikka, and developed further by Fagin et al. [9]. These logics often adopt axioms (K, D) that ensure (i) the equivalence between knowing or believing a conjunction $\Box (p \wedge q)$ and believing each of the conjoints $\Box p$ land $\Box q$ (this is called the adjunction law), and (ii) that $\Box p$ is a stronger statement than $\Diamond p \equiv \lnot \Box \lnot p$ (expressing a lack of support for the negation of p). This approach makes a clear difference between belief and knowledge (viewed as true belief), and allows to construct very complex formulas involving nested modalities and the usual Boolean connectives.

These three traditions are supposed to address closely related issues: they try to propose tools to represent belief and uncertainty when information is lacking. But they look at odds with one another. The main claim of this paper is that possibility theory is instrumental to bridge these apparently unrelated approaches and to put them in a unified setting.

3 The Simplest Logic of Belief and Partial Ignorance

The simplest format to express beliefs is propositional logic (PL). Consider a propositional language $\mathcal {L}= \{p, q, r, \dots \}$ built from atomic variables $\mathcal {A} = \{a, b, c, \dots \}$ and usual connectives $\wedge , \vee , \lnot , \dots$. A belief base is understood as a finite subset $\mathcal {K} \subset \mathcal {L}$ of propositions believed by an agent. In the usual semantics, a proposition p is evaluated on the set of interpretations of $\mathcal {L}$, say $S = \{s: \mathcal {A}\rightarrow \{0, 1\}\}$, assigning a truth-value to each variable. Let [p] be the set of models of p, interpretations s for which p is true (which is denoted by $s \,\models \, p$), and $[\mathcal {K}]$ be the set of models of all $p\in \mathcal {K}$, i.e., $[\mathcal {K}] = \cap _{p\in \mathcal {K}} [p]$. Denote by $\mathcal {K}\vdash p$ the syntactic inference of p from $\mathcal {K}$, using inferences rules in PL and modus ponens, and by $\mathcal {K}\,\models \,p$ the semantic inference, defined by $[\mathcal {K}]\subset [p]$. It is well-known that $\mathcal {K}\,\models \, p\iff \mathcal {K}\vdash p$ (soundness and completeness).

3.1 Boolean Beliefs

The semantics in terms of interpretations is ontic in the sense that it tells whether propositions are true or false in each state of the world. However it does not match the idea that propositions in $\mathcal {K}$ represent beliefs. A belief should be evaluated with respect to an epistemic state, namely a non-empty set E of interpretations that are not ruled out by the agent. This is the simplest representation of incomplete information. Epistemic states are more or less informed: E is said to be more specific than $E'$, if $E\subset E'$: E is more informed than $E'$. An epistemic state E is said to be fully informed if $E =\{s\}$ for some $s \in S$, and totally ignorant if $E = S$. In the tradition of epistemic logic, an agent is said to believe p if p is true in all interpretations the agent considers possible, i.e., in its epistemic state. This leads to an epistemic semantics for propositional logic, whereby propositions p are evaluated in epistemic states, namely:

$$E \,\models \,p \iff E \subseteq [p].$$

And we can define an epistemic semantic inference as $\mathcal {K}\,\models _e \,p \iff \forall E \ne \emptyset , E \subseteq [\mathcal {K}]$ implies $E \subseteq [p]$. However, there exists a least specific epistemic state for an agent whose belief base is $\mathcal {K}$ and this is $E = [\mathcal {K}]$. So the ontic and epistemic semantics lead to the same inference: $\mathcal {K}\,\models \, p \iff \mathcal {K}\,\models _e\, p$. But the epistemic semantics is potentially richer than the ontic one, as one may distinguish between the situation where $E \subseteq [\lnot p]$ (the agent believes the negation of p) and the situation where $E \not \subseteq [p]$ (the agent does not believe p), which collapse if $E = \{s\}$. Clearly, the propositional language cannot grasp this distinction. To account for it at the syntactic level we must let the belief modality $\Box$ appear in the syntax, to mean that the agent believes p. In fact, the precise meaning of this modality can range from the agent is informed that p to the agent knows that p.

On this basis, we consider an epistemic language $\mathcal {L}_\square$ built on top of $\mathcal {L}$:

• Atomic variables form the set $\mathcal {A}_\square = \{\square p: p \in \mathcal {L}\}$ (i.e., plain beliefs).

• $\mathcal {L}_\square$ is the propositional language based on $\mathcal {A}_\square$ with usual connectives $\wedge , \vee , \lnot$.

In this language not only can we state that p is believed, but also that the agent ignores p, the latter being expressed by the formula $\lnot \Box p\wedge \lnot \Box \lnot p$, or equivalently $\Diamond p\wedge \Diamond \lnot p$, where the formula $\Diamond p$ is short for $\lnot \Box \lnot p$. $\mathcal {L}_\square$ can be viewed as the minimal language to express partial knowledge about the truth of propositions.

We define an epistemic semantics for the formulas $\phi , \psi$ in $\mathcal {L}_\square$ by adapting the epistemic semantics of propositional logic with formulas in $\mathcal {L}$:

• $E\,\models \,\Box p$ if and only if $E\subseteq [ p]$ (p is certainly true in the epistemic state E);

• $E \,\models \, \phi \wedge \psi$ if $E \,\models \,\phi$ and $E \,\models \,\psi$;

• $E\, \models \lnot \phi$ if $E \,\models \,\phi$ is false.

A logic called MEL (Minimal Epistemic Logic) has been defined by Banerjee and Dubois [10] for reasoning about incomplete knowledge in $\mathcal {L}_\square$. Axioms are as follows:

• (PL) Axioms of propositional logic for $\mathcal{L}_\Box$-formulas

• (K) $\Box (p \rightarrow q) \rightarrow (\Box p \rightarrow \Box q)$

• (D) $\Box p\rightarrow \Diamond p$

• (Nec) $\Box p$, for each $p \in \mathcal{L}$ that is a PL tautology, i.e. if $[p] = S$.

The inference rule is modus ponens. In other words, this is a two-tiered propositional logic with additional axioms, and we define the syntactic inference as $\mathcal {B}\vdash _{MEL} \phi$ if and only if $\mathcal {B}\cup \{K, D, Nec\} \vdash \phi$, where $\mathcal {B} \subset \mathcal {L}_\square$ is a MEL base. This logic is sound and complete with respect to the epistemic semantics, defining as usual $\mathcal {B}\,\models _{MEL}\, \phi$ if and only if $E \,\models \, \psi , \forall \psi \in \mathcal {B}$ implies $E \,\models \,\phi$.

Note that the subjective language $\mathcal {L}_\square$ is disjoint from the objective language $\mathcal {L}.$ However, there is a clear embedding of propositional logic in MEL: Given a belief base $\mathcal {K}$ in PL, define the MEL base $\mathcal {K}_\Box = \{\Box p: p \in \mathcal {K}\}$. Then we have that $\mathcal {K}_\Box \vdash _{MEL} \Box q$ if and only if $\mathcal {K}\vdash q$.

3.2 Unifying Approaches to Reasoning with Incomplete Information

We are now in a position to reconcile the three traditions for reasoning with incomplete information.

Set Functions Underlying MEL. We have seen that at the semantic level incomplete information is represented by epistemic states $E\subseteq S$ representing mutually exclusive states of affairs, one of which is considered to be the real one by the agent with epistemic state E. Its characteristic function is a possibility distribution with values on $\{0, 1\}$ defined by $\pi (s) = {\left\{ \begin{array}{ll}1 \text { if } s \in E; \\ 0 \text { otherwise. }\end{array}\right. }$

This representation leads us to build 2 set-functions (e.g., [5]):

• A possibility function $\varPi (A) = 1$ if and only if $E\cap A\ne \emptyset$ and 0 otherwise

• A necessity function $N(A) = 1$ if and only if $E\subseteq A$ and 0 otherwise.

Possibility and necessity functions are examples of confidence functions like probabilities, except that they are 2-valued. Their characteristic properties on finite sets are maxitivity for $\varPi$ ($\varPi (A\cup B) = \max (\varPi (A), \varPi (B)$) and minitivity for N ($N(A\cap B) = \max (N(A), N(B))$, which encodes the adjunction law), along with $N(S) = \varPi (S)= 1$, $N(\emptyset ) = \varPi (\emptyset )= 0$.

It is clear that in a finite setting, an epistemic state is equivalent to a necessity function or to a possibility function, so that the semantics of MEL can be equivalently expressed in terms of these set functions. In particular, $\Box p$ means $N(p) = 1$ for some necessity function N, while $\Diamond p$ means $\varPi (p) = 1$ for some possibility function $\varPi$, and we have that $N(A) = 1 - \varPi (A^c)$, where $A^c$ is the complement of A. Axiom Nec in MEL corresponds to $N(S) = 1$. Axiom D expresses the inequality $\varPi (A) \ge N(A)$. Axioms K and D ensure the minitivity axiom. So we can claim that MEL is the logic of all-or-nothing possibility theory.

MEL vs. Doxastic Logic. The close connection between MEL and modal epistemic logic S5 and doxastic logic KD45 is very clear, as MEL uses a fragment of their language. Moreover, all inferences that can be made in MEL can equally be made in KD45 as proved in [11]. However there are noticeable differences, reflecting the fact that MEL is in some sense a minimal uncertainty logic:

• MEL allows neither nested modalities nor plain (non-modal) propositional formulas.

• In MEL, formulas are evaluated on epistemic states while in KD45 formulas are evaluated on possible worlds (it makes sense to write $s\,\models \, \Box p$) via accessibility relations R on S (as $R(s) \subseteq [ p]$).

• KD45 allows for very complex modal formulas that can be simplified using additional axioms (4: $\Box \phi \rightarrow \Box \Box \phi$; 5: $\lnot \Box \phi \rightarrow \Box \lnot \Box \phi$), while MEL minimally augments the expressive power of PL. These additional introspection axioms 4 and 5 cannot be written in MEL.

• MEL has the deduction theorem because it is a two-tiered propositional logic. Modal logics often do not because axiom (Nec) in MEL is expressed by means of the necessitation rule $p\vdash \Box p$ (that cannot be written in MEL).

So MEL can be viewed as the poor man’s epistemic or doxastic logic; we cannot see the difference here because axiom T: $\Box p \rightarrow p$ cannot be written in MEL (but we can include it by extending MEL to allow for objective formulas, see [11]).

While KD45 is supposed to model an agent reflecting on its own beliefs, MEL is rather dedicated to represent what an agent knows about the epistemic state of another agent. For instance $\lozenge p\wedge \lozenge \lnot p$ should be read: the agent knows that the other agent ignores the truth value of p. Likewise, having $\Box p\vee \Box \lnot p$ without having $\Box p$ nor $\Box \lnot p$ means that the first agent knows that the other agent knows the truth value of p, while this first agent does not know what the second one believes. Note that this formula would be hard to interpret if it concerns one’s own beliefs, as pointed out quite early in [12].

Regarding introspection, even if axioms 4 and 5 are absent from MEL, it is implicitly assumed in MEL that an agent can always say whether (s)he believes p, (s)he believes $\lnot p$ or is ignorant about p (the formula $\Box p\vee \Box \lnot p \vee (\lozenge p\wedge \lozenge \lnot p)$ is a MEL tautology). In other words, an agent is supposed to know its own epistemic state (it can be described by a complete MEL base), which is how introspection is handled in MEL.

MEL vs. Three-Valued Logics. The 3-valued logic approach to reasoning with incomplete information can be captured in MEL [13]. For the sake of simplicity we restrict to Kleene logic, often used in incomplete databases, or logic programming. It has 3 truth values forming the set $\mathbb {V}_3 = \{\mathbf {0}< \mathbf {\tfrac{1}{2}} < \mathbf {1}\}$, the same syntax as PL, with the same connectives semantically characterized as follows:

• Negation: $\mathbf t (\lnot p) = 1- \mathbf t (p)$;

• Conjunction: $\mathbf t (p \wedge q) = \min (\mathbf t (p), \mathbf t (q))$;

• Disjunction: $\mathbf t (p \vee q) = \max (\mathbf t (p),\mathbf t (q))$, by De Morgan laws;

• Implication: $\mathbf t (p \rightarrow _K q) = \max (1- \mathbf t (p), \mathbf t (q))$ (using $p \rightarrow _K q \equiv \lnot p \vee q$).

This logic has no tautologies, e.g., $\mathbf t (p \wedge \lnot p) = \mathbf t (p \vee \lnot p) = \mathbf {\tfrac{1}{2}}$ when $\mathbf t (p) = \mathbf {\tfrac{1}{2}}$.

In practice, the truth-value $\mathbf {\tfrac{1}{2}}$ is often used to model the idea that the truth-value of an otherwise Boolean proposition is unknown. But Unknown is in opposition with Known to be true and Known to be false, not with true and false. The three-valued $\mathbf t (p)$ thus informs about the state of knowledge concerning the plain truth value $t(p)\in \{0,1\}$ of a Boolean proposition. In this view, the lack of tautologies in Kleene logic may look paradoxical since $p \wedge \lnot p$ is known to be false regardless of our knowledge about p. The epistemic nature of Kleene truth-values led us to translate this logic into MEL [13]. Let $\mathcal {T} (\mathbf {t}(a) \in T)$ denote the translation into MEL of the atomic assertion $\mathbf {t}(a) \in T\subseteq \mathbb {V}_3$. We define, in agreement with the intended meaning of Kleene truth-values:

$$\begin{aligned} \mathcal {T} (\mathbf {t}(a)=\mathbf{1})&= \square a \text { (certainty of } a); \quad&\mathcal {T} (\mathbf {t}(a)=\mathbf{0}) =\square \lnot a = \mathcal {T} (\mathbf {t}(\lnot a)=\mathbf{1});\\ \mathcal {T} (\mathbf {t}(a)=\tfrac{1}{2} )&= \lozenge a \wedge \lozenge \lnot a \text { (ignorance)};&\\ \mathcal {T} (\mathbf {t}(a)\ge \tfrac{1}{2})&= \lozenge a \text { (possibility of } a); \quad&\mathcal {T} (\mathbf {t}(a)\le \tfrac{1}{2}) = \lozenge \lnot a. \end{aligned}$$

The translation of composite formulas in Kleene logic can be done recursively. In particular, for conjunction and disjunction we just have $\mathcal {T} (\mathbf {t}(a\vee b)=\mathbf{1}) = \square a \vee \square b$ and $\mathcal {T} (\mathbf {t}(a\wedge b)=\mathbf{1}) = \square a \wedge \square b$.

Asserting a formula p in Kleene logic comes down to the statement $\mathbf {t}(p )= \mathbf{1}$. A knowledge base $\mathcal {K}$ in Kleene logic can be put in conjunctive normal form (without simplifying the terms $a \vee \lnot a$). The translation $\mathcal {T}(\mathbf {t}(\mathcal {K}) =\mathbf{1})$ into MEL consists in the same conjunction of clauses with modality $\square$ in front of literals. As a consequence, the translation process reaches a small fragment of the MEL language, namely $\mathcal {L}_\square ^K:=\square a|\square \lnot a|\phi \vee \psi |\phi \wedge \psi$ where $\Box$ only appears in front of literals and no negation is allowed to prefix the $\Box$ symbol. This result clarifies the limited expressive power of Kleene logic.

• Knowledge can be expressed about atomic variables only. In particular, truth-functionality is a trivial matter as it just says that $a\vee b$ means $\square a \vee \square b$. We can never express $\square (a \vee b)$ using Kleene logic.

• The lack of tautologies in Kleene logic is explained, as $\square a \vee \square \lnot a$ (translation of $\mathbf {t}(a\vee \lnot a)=\mathbf{1}$) is not a tautology! More generally, replacing literals $\ell$ by $\square \ell$ in a tautology of propositional logic does not yield a tautology in MEL.

• In $\mathcal {L}_\square ^K$, only partial models can be expressed by conjunctions of plain beliefs, that is “rectangular” subsets of S of the form $[\wedge _{a\in A^+}a\wedge \wedge _{a\in A^-}\lnot a]$, where $A^+$ and $A^-$ are disjoint subsets of atomic formulas.

These results extend to many three-valued logics where the third truth-value refers to ignorance (like Łukasiewicz 3-valued logic). They can be translated into MEL and these translations are theorem-preserving; see [13].

4 Gradual Beliefs in Possibility Theory

In this section, we consider beliefs can be a matter of degree. We first show that in order to satisfy the adjunction law, we must rely on the graded version of possibility theory. Then we describe possibilistic logic, that augments propositional logic with certainty weights attached to formulas. We generalize this approach by extending the MEL framework with certainty and possibility weights. We then survey the applications of these formalisms.

4.1 Degrees of Accepted Belief

In order to relate accepted beliefs to graded beliefs, one should extract accepted beliefs from a confidence function g. A natural way of proceeding is to define a belief as a proposition in which an agent has enough confidence. So we should be in a position to define a positive belief threshold $\beta$ such that A is a belief if and only if $g(A) \ge \beta >0$. However the adjunction law (accepted beliefs are closed under conjunction) leads to enforce the following property

$$\begin{aligned} Accepted\,\,belief\,\,postulate {:}~ \text {If } g(A) \ge \beta \text { and } g(B) \ge \beta \text { then } g(A\cap B) \ge \beta . \end{aligned}$$

This requirement is very strong as (along with the monotonicity of g) it enforces the equality $g(A\cap B) = \min (g(A), g(B))$, that is g is a graded necessity measure, still denoted by N. Letting $\iota : S\rightarrow [0, 1]$ be the function defined by $\iota (s) = N(S\setminus \{s\})$ (the degree of belief that the actual state of affairs is not s), it is clear that

$$N(A) = \min _{s \not \in A} \iota (s).$$

The value $1 - \iota (s)$ can be interpreted as the degree of plausibility $\pi (s)$ of state s, where $\pi$ is the membership function of a fuzzy epistemic state $\tilde{E}$ that represents a possibility distribution [5]. The set function $\varPi :2^S\rightarrow [0, 1]$ such that

$$\varPi (A) = 1 - N(A^c) = \max _{s \in A} \pi (s)$$

represents the degree of plausibility of A, measuring to what extent A is not totally ruled out by the agent. This setting is the one of possibility theory that seems to be the only one that accounts for the notion of accepted belief.

Possibility theory was proposed by L.A. Zadeh in the late 1970’s for representing uncertain pieces of information expressed by fuzzy linguistic statements [4], and later developed in an artificial intelligence perspective [5]. Formally speaking, the proposal is quite similar to the one made some thirty years before by the economist Shackle [2], who had considered a non probabilistic view of uncertainty based on the idea of degree of potential surprise, which can be modelled as $N(A^c)$. Namely the more you believe in $A^c$, the more surprising you find the occurrence of A. The degree N(A) was explicitly used by Cohen [3] under the name “Baconian probability” capturing the idea of provability. Especially if you can prove A with some confidence, you cannot at the same time prove its negation, which makes condition $\min (N(A), N(A^c)) = 0$ natural. So, condition $N(A) >0$ expresses that A is prima facie an accepted belief, its absolute value expressing the strength of acceptance. Such Baconian probabilities, viewed as shades of certainty, are claimed to be more natural than probabilities in legal matters. Deciding whether someone is guilty cannot be based on statistics, nor on subjective probabilities: you must prove guilt using convincing arguments. About a decade later, Spohn [7] introduced ordinal conditional functions, now called ranking functions, as a basis for a dynamic theory of epistemic states. Ranking functions $\kappa$ are a variant of potential surprize, taking values on the non-negative integers, that is $g_\kappa (A) = 2^{-\kappa (A^c)}$ is a degree of necessity. The theory of ranking functions and possibility theory can be developed in parallel, even if they were independently devised [14].

4.2 Graded Possibilistic Logic

Possibilistic logic, PosLog for short, has been developed for about thirty years [6, 15]. Basic possibilistic logic has been first introduced in AI as a tool for the logical handling of uncertainty in a qualitative way. A basic possibilistic logic formula is a pair $(p, \alpha )$ made of a classical logic formula p associated with a certainty level $\alpha \in (0,1]$, viewed as a lower bound of a necessity measure, i.e., $(p, \alpha )$ is understood as $N(p) \ge \alpha$. A Poslog base is a conjunction of weighted formulas in PosLog. Formulas of the form (p, 0) do not contain any information and are not part of the language. The interval [0, 1] can be replaced by any linearly ordered scale.

The axioms of PosLog [6] are those of propositional logic where each axiom schema is now supposed to hold with maximal certainty, i.e., is assigned level 1. PosLog has two inference rules:

• if $\beta \le \alpha$ then $(p,\alpha ) \vdash (p, \beta )$ (certainty weakening);

• $(\lnot p \vee q, \alpha ), (p, \alpha ) \vdash (q, \alpha )$, $\forall \alpha \in (0, 1]$ (modus ponens).

We may equivalently use certainty weakening with the PosLog counterpart of the resolution rule: $(\lnot p \vee q, \alpha ), (p \vee r, \alpha ) \vdash (q \vee r, \alpha ), \ \forall \alpha \in (0, 1]$.

Using certainty weakening, the following inference rule is valid:

$$(\lnot p \vee q, \alpha ), (p \vee r, \beta ) \vdash (q \vee r, \min (\alpha ,\beta )) \ \text {(weakest link resolution}). $$

The idea that in a reasoning chain, the certainty level of the conclusion is the smallest of the certainty levels of the formulas involved in the premises is at the basis of the syntactic approach proposed by Rescher [16] for plausible reasoning, and would date back to Theophrastus, an Aristotle’s follower.

An interesting feature of possibilistic logic is its ability to deal with inconsistency. Indeed a PosLog base $\varGamma$ has an inconsistency level $incl(\varGamma )$ defined as the least degree such that the set of formulas with a strictly greater weight is consistent. When $incl(\varGamma ) >0$, the propositional part of $\varGamma$ is inconsistent but the consequences of the (consistent) maximal subset of formulas above the inconsistency level are said to be non-trivial.

A possibilistic logic base is semantically equivalent to a possibility distribution that restricts the set of interpretations (w.r.t. the propositional language) that are more or less compatible with the base. Instead of an ordinary subset of models as in classical logic, we have a fuzzy set of models, since the violation of a formula by an interpretation becomes a matter of degree. A PosLog formula $(p,\alpha )$ encodes the statement $N(p) \ge \alpha$. Its semantics is given by the possibility distribution $\pi _{(p, \alpha )}$ defined by:

$$\begin{aligned} \pi _{(p, \alpha )}(s) = 1 \text { if } s \vDash p \text { and } \pi _{(p, \alpha )}(s) = 1 - \alpha \text { if } s \vDash \lnot p \end{aligned}$$

The underlying idea is that any model of p should be fully possible, and that a counter-model of p is all the less possible as p is more certain, i.e., as $\alpha$ is higher. It can be easily checked that $\pi _{(p, \alpha )}$ is the least informative (i.e., maximizing possibility degrees) possibility distribution whose associated necessity measure N satisfies $N(p) \ge N_{(p, \alpha )}(p) = \alpha$. We write $\pi \,\models \,(p, \alpha )$ instead of $N(p) \ge \alpha$ to denote the satisfaction by epistemic models.

A PosLog knowledge base $\varGamma =\{(p_i,\alpha _i), i=1,\dots ,m\}$, corresponding to the conjunction of PosLog formulas $(p_i,\alpha _i)$, is semantically associated with the possibility distribution: $\pi _\varGamma (s)= \min _{i=1}^m \pi _{(p_i, \alpha _i)}(s)$. Thus, $\pi _\varGamma$ is the least informative possibility distribution that is a model of each weighted formula $(p_i, \alpha _i)$ in $\varGamma$. Due to the min-decomposability of necessity measures, $N(\bigwedge _i p_i) \ge \alpha \Leftrightarrow \forall i, N(p_i) \ge \alpha$, and then any possibilistic propositional base can be put in clausal form. Possibilistic logic with the inference rules recalled above is sound and complete with respect to this semantics.

4.3 Generalized Possibilistic Logic

In basic possibilistic logic, only conjunctions of possibilistic logic formulas are allowed. But since $(p,\alpha )$ is semantically interpreted as $N(p)\ge \alpha$, a possibilistic formula can be manipulated as a propositional formula that is true (if $N(p)\ge \alpha$) or false (if $N(p) < \alpha$). Then possibilistic formulas can be combined with all propositional connectives, including disjunction and negation. This is generalized possibilistic logic (GPL) [17]. GPL is a two-tiered propositional logic, in which propositional formulas are encapsulated by weighted modal operators interpreted in terms of uncertainty measures from possibility theory. Let $\varLambda _k = \{\!0,\!\frac{1}{k},\!\frac{2}{k},\!...,\!1\!\}$ with $k\in \mathbb {N}\setminus \{0\}$ be a finite set of certainty degrees, and let $\varLambda _k^+ =\varLambda _k \setminus \{0\}$. The language of GPL, $\mathcal {L}^k_{\mathbf {N}}$, with $k+1$ certainty levels is built on top of the propositional language $\mathcal {L}$ as follows:

• If $p\in \mathcal {L}$ and $\alpha \in \varLambda _k^+$, then $\mathbf {N}_{\alpha }(p) \in \mathcal {L}^k_{\mathbf {N}}$.

• If $\varphi \in \mathcal {L}^k_{\mathbf {N}}$ and $\psi \in \mathcal {L}^k_{\mathbf {N}}$, then $\lnot \varphi$ and $\varphi \wedge \psi$ are also in $\mathcal {L}^k_{\mathbf {N}}$.

Here we use the notation $\mathbf {N}_{\alpha }(p)$, instead of $(p,\alpha )$, emphasizing the closeness with modal logic. So, an agent asserting $\mathbf {N}_{\alpha }(p)$ has an epistemic state $\pi$ such that $N(p) \ge \alpha >0$. Hence $\lnot \mathbf {N}_{\alpha }(p)$ stands for $N(p) < \alpha$, which, given the finiteness of the set of considered certainty degrees, means $N(p) \le \alpha - \frac{1}{k}$ and thus $\varPi (\lnot p) \ge 1-\alpha +\frac{1}{k}$. Let $\nu (\alpha ) =1-\alpha +\frac{1}{k}$. Then, $\nu (\alpha )\in \varLambda _k^+$ iff $\alpha \in \varLambda _k^+$, and $\nu (\nu (\alpha )) = \alpha , \forall \alpha \in \varLambda _k^+$. Thus, we can write $\varvec{\Pi }_{\alpha }(p) \equiv \lnot \mathbf {N}_{\nu (\alpha )}(\lnot p)$. So, in GPL, like in MEL (retrieved by identifying $\Box p$ with $\mathbf {N}_{1}(p)$ and $\Diamond p$ with $\varvec{\Pi }_{1}(p)$) one can distinguish between the absence of sufficient certainty that p is true ($\lnot \mathbf {N}_{\alpha }(p)$) and the stronger statement that p is somewhat certainly false ($\mathbf {N}_{\alpha }(\lnot p)$).

The semantics of GPL is as in Poslog defined in terms of normalized possibility distributions over propositional interpretations, where possibility degrees are limited to $\varLambda _k$. A model of a GPL formula $\mathbf {N}_{\alpha }(p)$ is any $\varLambda _k$-valued possibility distribution $\pi$ such that $N(p) \ge \alpha$, where N is the necessity measure induced by $\pi$, and then the standard definition for $\pi \,\models \, \varphi _1 \wedge \ \varphi _2$ and $\pi \,\models \,\lnot \varphi$. As usual, $\pi$ is called a model of a set of GPL formulas $\varGamma$, written $\pi \,\models \,\varGamma$, if $\pi$ is a model of each formula in $\varGamma$. We write $\varGamma \,\models \, \phi$, for $\varGamma$ a set of GPL formulas and $\phi$ a GPL formula, iff every model of $\varGamma$ is also a model of $\phi$. Note that a formula in GPL will not always have one least specific possibility distribution that satisfies it. For instance, the set of possibility distributions satisfying the disjunction ‘$\mathbf {N}_{\alpha }(p)\vee \mathbf {N}_{\alpha }(q)$’ no longer has a unique least informative model as it is the case for conjunctions in PosLog. In fact, there are two of them: $\pi _{(p, \alpha )}$ and $\pi _{(q, \alpha )}$. The soundness and completeness of the following axiomatization of GPL holds with respect to the above semantics [17]:  

(PL) :

Axioms of propositional logic for $\mathcal {L}^k_{\mathbf {N}}$-formulas

(K) :

$\mathbf {N}_{\alpha }(p\rightarrow q) \rightarrow (\mathbf {N}_{\alpha }(p) \rightarrow \mathbf {N}_{\alpha }(q))$

(N) :

$\mathbf {N}_{1}(\top )$

(D) :

$\mathbf {N}_{\alpha }(p) \rightarrow \varvec{\Pi }_{1}(p)$

(W) :

$\mathbf {N}_{\alpha _1}(p) \rightarrow \mathbf {N}_{\alpha _2}(p)$, if $\alpha _1\ge \alpha _2$

 

with modus ponens as the only inference rule.

Note in particular that when $\alpha$ is fixed we get a fragment of the modal logic KD. See [11] for a survey of previous studies on the links between modal logics and possibility theory. When $k=1$, GPL with a value scale $\varLambda _1$ coincides with MEL. Figure 1 recaps the links between propositional logic, its extensions PosLog and MEL, and GPL that generalizes both. Note that in MEL, we have $\varvec{\Pi }_{1}(p) \equiv \lnot \mathbf {N}_{1}(\lnot p)$, whereas in GPL we only have $\varvec{\Pi }_{1}(p) \equiv \lnot \mathbf {N}_{\frac{1}{k}}(\lnot p)$ if $k > 1$.

Fig. 1.

Comparison of belief logics in possibility theory

GPL and MEL are suitable for reasoning about the revealed beliefs of an external agent (and not introspection). It captures the idea that while a consistent epistemic state of an agent about the world is represented by a normalized possibility distribution over possible worlds, the meta-epistemic state of another agent about the former’s epistemic state is a family of possibility distributions. Standard inference in GPL is co-NP complete, but other kinds of inference (e.g., using specificity criterion) can be more complex; see [17] for a detailed study.

5 Applications to Reasoning and Decision

PosLog and GPL proved to be useful for modeling some forms of commonsense reasoning [15].

Reasoning with Exceptions. A rule having exceptions “if p then q, generally”, denoted by $p \leadsto q$, is understood formally in possibility theory as the constraint $\varPi (p \wedge q) > \varPi (p \wedge \lnot q)$ on a possibility distribution $\pi$ describing the normal course of things. Any finite set $\varDelta =\{p_i\leadsto q_i, i=1, \cdots , n\}$ of conditional statements is represented by a set constraints of the form $\varPi (p_i \wedge q_i ) > \varPi (p_i \wedge \lnot q_i)$. The family of possibility distributions on S compatible with these constraints, if not empty, possesses a maximal element according to the principle of minimal specificity, e.g., [18]. This principle assigns to each interpretation s the highest possibility level (yielding a well-ordered partition of S) without violating the constraints. This defines a unique complete plausibility preorder on S. Let $E_1, \ldots , E_k$ be the obtained partition. A possibility distribution $\pi _\varDelta$ can be defined on S by $\pi _\varDelta (s)=\frac{k + 1 - i}{k}$ if $s \in E_i, i=1,\ldots ,k$. Note that this numerical scale is arbitrary. Namely the range of $\pi$ is used as an ordinal scale.

Each default $p_i \leadsto q_i \in \varDelta$ can be turned into a possibilistic clause of the form $(\lnot p_i \vee q_i, N(\lnot p_i \vee q_i))$, where N is computed from $\pi _\varDelta$ induced by the set of constraints corresponding to the conditional knowledge base. We thus obtain a possibilistic logic base $\varGamma _\varDelta$ encoding the generic knowledge embedded in $\varDelta$. As shown in [19], non trivial inference of q from $\varGamma _\varDelta \cup \{p\}$ using possibilistic logic turns out to be equivalent to inferring $p \leadsto q$ from $\varDelta$ using rational closure in the sense of Lehmann and Magidor [20]. As for preferential inference [21], it can be captured in GPL since its semantics in terms of possibilistic logic reads: $\varDelta$ implies $p \leadsto q$ if and only if $\forall \pi$, for which $\varPi (p_i \wedge q_i ) > \varPi (p_i \wedge \lnot q_i), \forall i = 1, \dots , k$, we have that $\varPi (p \wedge q) > \varPi (p \wedge \lnot q)$. It just needs a proper encoding of such statements in GPL. In [17], we encode this constraint as $\bigvee _{i = 1}^k \mathbf {N}_{\frac{i}{k}}(\lnot p \vee q) \wedge \lnot \mathbf {N}_{\frac{i}{k}}(\lnot p \vee \lnot q)$.

Prioritized Constraints. Basic possibilistic logic can also be used for representing preferences. Then, each logic formula $(p, \alpha )$ represents a goal p to be reached with some priority level $\alpha$ (rather than a statement that is more or less believed) [22]. Beyond PosLog, interpretations (corresponding to the different alternatives) can be compared in terms of vectors acknowledging the satisfaction or the violation of the formulas associated with the different goals, using suitable order relations. Thus, partial orderings of interpretations can be obtained [23].

Non-monotonic Logic Programming. Another remarkable application of GPL is its capability to encode answer set programs, adopting a three-valued scale $\varLambda _2 = \{0, 1/2, 1\}$. In this case, we can discriminate between propositions we are fully certain of and propositions we consider only more plausible than not. This is sufficient to encode non-monotonic ASP rules (with negation as failure) within GPL and lay bare their epistemic semantics. For instance, an ASP rule of the form $a \leftarrow b \wedge \text {not}\,c$, where “$\text {not}\,$” denotes negation as failure, is encoded as $\mathbf {N}_{1}(b) \wedge \varvec{\Pi }_{1}(\lnot c) \rightarrow \mathbf {N}_{1}(a)$ in GPL. See [17] for theoretical results, and [24] for the GPL encoding of Pearce equilibrium logic [25].

Reasoning About Ignorance. All that is known is p means that p is known but no q such that $q \,\models \,p$ is known. This can be expressed in MEL by the formula $OKp \equiv \Box p \wedge \bigwedge _{w \models p} \Diamond p_w$ where $p_w$ is a propositional formula whose only ontic model is w [10]. It is clear that $E\,\models \,\bigwedge _{w \models p} \Diamond p_w$ if and only if $[p] \subseteq E$, so that the only epistemic model of OKp is [p]. In terms of set-functions it corresponds to the guaranteed possibility $\varDelta (A) = \min _{w\in A} \pi (A)$ [5]. The expression of OKp can be related to the Moebius transform of a belief function in the sense of Shafer [10]. In GPL, one can similarly define a formula whose only epistemic model is a possibility distribution $\pi$ [17].

6 Perspectives Beyond GPL

As per the above discussions, GPL is a rather versatile tool for knowledge representation and reasoning that has simpler and more natural semantics than epistemic logic, and can handle degrees of belief. On this basis, several lines of research can be envisaged, some of which were already investigated in the recent past

• Comparative certainty logic. Rather than using weighted formulas, one might wish to represent at a syntactic level statements of the form “p is more certain than q”. This kind of statements can be to some extent captured by GPL. The idea is to define a partial certainty ordering on a propositional belief base, and to induce a partial order on the propositional language that completes it, via suitable inference (see [17, 26] for examples of such logics). This topic is related to Lewis logics of comparative possibility [27].

• Symbolic possibilistic logic. Instead of using weights from a totally ordered scale, one may use pairs (p, x) where x is a symbolic entity that stands for an unknown weight. Then we can model the situation where only a partial ordering between ill-known weights is known. See [28] for this approach. It differs from comparative certainty logic [26], because the latter does not rely on the principle of minimal specificity at work in possibilistic logic.

• The logic of capacities. The connection between epistemic logic and possibility theory can be extended to general capacities (monotonic set-functions). The corresponding modal logics are then non-normal, only classical, and the semantics in terms of capacities is close to neighborhood semantics. This enlarged logical framework seems to capture some inconsistency-tolerant logics (like Belnap logic [8]). See for instance [29].

• Multisource logic. Not only can we attach certainty weights to propositional formulas, but we can attach to them sources (agents) that supply this information. So we can extend possibilistic formulas with labels describing groups of agents, and extend the corresponding inference machinery [30], so as to compute for each proposition which agents believe it and to what extent.

• Multiagent epistemic reasoning. Finally, it would be of interest to apply GPL to problems where an agent’s decisions are based on what agents mutually know about each other’s knowledge. It would mean extending GPL to nested modalities labelled by agents, and compare to the state of the art in multiagent modal logics [9]. A question to address is whether accessibility relations of usual epistemic logics are needed or not to solve such problems. This is a topic of interest, not explored yet.