Reasoning about ignorance and contradiction: many-valued logics versus epistemic logic

Abstract

This paper tries to reinterpret three- and four-valued logics of partial ignorance and contradiction in the light of epistemic logic. First, we try to cast Kleene three-valued logic in the setting of a simplified form of epistemic logic. It is a two-tiered logic that embeds propositional logic into another propositional setting. The use of modalities enables Kleene truth values to be expressed at the syntactic level. Kleene logic is then a fragment of the simplified epistemic logic where modalities are in front of literals only. Kleene truth-tables can then be retrieved, while preserving tautologies of classical logic. Kleene logic connectives can be seen as set-valued extensions of Boolean logic ones, but the compositionality of Kleene logic leads to a lack of expressiveness and inferential power compared to the proposed epistemic logic. This methodology is then extended to Belnap four-valued logic, which is tailored to the handling of inconsistent information from various sources. A non-regular modal setting for reasoning about contradiction is obtained, where the adjunction law does not hold. It is a special case of a fragment of the monotonic modal logic EMN.

1 Introduction

In many works dealing with imperfect knowledge representation, there is a temptation to handle ignorance and/or contradiction by augmenting the usual two-valued truth-set with more truth values. In fact, from the inception of many-valued logics, logicians have tried to attach an epistemic flavor to truth degrees. In three-valued logics, the truth value lying between true and false is often interpreted as expressing a form of ignorance or partial information (less often, the idea of contradiction), and noticeably:

• Łukasiewicz (1970) calls the third truth value of his logic “possible”;

• Kleene (1952) hesitates between undefined and unknown and he provides different truth-tables (so-called weak and strong, respectively) for each view.

Kleene’s view of handling ignorance in a three-valued setting has been influential and many authors take it for granted. For instance, partial logic (Blamey 1998) is an implementation of Kleene strong tables replacing interpretations by partial interpretations. However, multiple-valued logics are generally truth-functional. The trouble here is that, when trying to capture the epistemic status of any unknown proposition by means of a truth value, the very assumption of truth-functionality (building truth-tables for all connectives) is debatable. Combining two Boolean propositions whose truth value is unknown sometimes results in tautological or contradictory statements. Their truth value can be asserted from the start, even without any prior knowledge, but for the laws of propositional logic. As long as $p$ can only be either true or false, even if this truth value cannot be computed or prescribed as of to-day, the proposition $p \wedge \neg p$ can be unmistakably at any time predicted as being false and $p \vee \neg p$ as being true while $p \wedge p$ and $p \vee p$ remain contingent. So there is no way of defining a sensible truth-table that universally accounts for the idea of possible: belief is never truth-functional (Dubois and Prade 1994; Hájek 1998).

The other prominent approach to incomplete information is modal logic, and more precisely epistemic logics (Hintikka 1962; Halpern et al. 2003). This approach enriches the propositional language with symbols standing for knowledge or belief, $\square p$ meaning that the agent knows or believes $p.$ However while being syntactically powerful, epistemic logics often use Kripke semantics based on accessibility relations. The latter looks artificially too complicated for a simple representation of plain incomplete information. An epistemic state is just a non-empty subset of interpretations, representing possible worlds, one and only one of which is the real one. It can be viewed as a very special case of accessibility relation, but there is no need to resort to Kripke semantics. Recently, a simple fragment of the modal logic KD has been devised, that is sufficient to provide a sound and complete account of reasoning under incomplete information represented by epistemic states (Banerjee and Dubois 2009). This semantics is arguably in the spirit of founders of epistemic logic (Hintikka 1962). However, to our knowledge, there has been no attempt to formally relate Kleene logic and epistemic logic, although they both claim to model reasoning about incomplete information.

The four-valued logic of Belnap (Belnap 1977a, b) further extends the truth-functional line of Kleene logic adding a special truth value representing contradiction (reflecting the presence of conflicting sources of information). Its truth tables rely on Kleene’s for handling unknown and likewise for contradictory, plus rules for combining the two latter values. In fact, the problems with these three- and four-valued calculi are as follows

• 1. They act on propositional symbols that are basically Boolean (the two truth values $T$ and $F$ are often called ontological truth values) but Boolean tautologies are lost: they are systems weaker than propositional logic; so they cannot derive false conclusions, but they are in some sense incomplete.

• 2. Their semantics is overloaded (there are ontological truth values plus epistemic ones in Belnap logic) while the syntax is the one of (or very similar to) classical logic. Hence the language is insufficient to express the underlying epistemic construction.

• 3. There is a gap between the algebraic structure of the truth value set, which is mathematically interesting on its own (e.g. bilattices for Belnap), and the application serving as a motivation. As shown previously (Dubois 2008), Kleene tables do not handle unknown adequately in the case of related Boolean propositions. Belnap bilattices seem to mishandle the notion of contradiction in that same situation.

So, these many-valued logic approaches to handling uncertainty and contradiction are questionable. In this paper, we first show that Kleene truth-tables are captured by set-valued extensions of classical connectives. In Sect. 3, we show how the intuitions behind Kleene logic can be better captured by an elementary modal epistemic logic, a fragment of the logic KD formerly introduced as Meta-Epistemic Logic (Banerjee and Dubois 2009), dedicated to reasoning about epistemic information coming from a witness. It comes down to encapsulating propositional logic into another higher level propositional logic expressing information states about the propositions expressed in the lower level language. A simple semantics in terms of epistemic states over the set of interpretations of the lower level language is sufficient, in place of more general Kripke models. This semantics can also be expressed in terms of Boolean possibility theory. This setting can account for Kleene truth values and tables at the syntactic level, restricting modal formulas. In Sect. 4, this reification approach is tentatively extended to Belnap logic, for which the semantics is described in terms of pairs of (possibly conflicting) epistemic states. The corresponding modal logic is a monotonic one that does not satisfy axioms K and D.

2 Kleene logic as interval-valued Boolean logic

In the following we consider a propositional language ${\mathcal{L}}$ with usual connectives of negation $\neg,$ conjunction $\wedge,$ disjunction $\vee,$ and implication →. Atomic formulas are denoted by $a, b, c, \ldots$ and form the set ${\mathcal{A}};$ composite propositions are denoted by $p, q,\ldots$ In the case of Boolean logic we denote by $T$ and $F$ the truth values true and false respectively. They form the truth value set ${\mathbb{V}}_{2}.$ The set of models of a formula $p$ is denoted by $[p],$ and the set of interpretations of the language is denoted by $\Upomega.$

Kleene (1952) logic uses a propositional language ${\mathcal{L}}_{K}$ based on the same set of letters ${\mathcal{A}}$ as propositional logic. However, each proposition is a three-valued entity. Let the Kleene truth set be ${\mathbb{V}}_{3} = \{{\mathbf{T, F, U}}\},$ where T means (Kleene’s) true, F means (Kleene’s) false and U is a third truth value.¹ Denote by t a propositional truth-assignment ${\mathcal{L}} \to {\mathbb{V}}_{3},$ while $t$ stands for a standard Boolean truth assignment ranging on $\{F, T\}.$ The ordering on ${\mathbb{V}}_{3}$ is ${\mathbf F} < {\mathbf{U}} < {\mathbf{T}}.$ Connectives of Kleene logic² are as follows:

• Negation: ${\mathbf t}(\sim p) = n({\mathbf t}(p)),$ where $n( {\mathbf{T}}) = {\mathbf{F}},n( {\mathbf{F}}) = {\mathbf{T}}$ and $n( {\mathbf{U}}) = {\mathbf{U}};$

• Conjunction: ${\mathbf t}(p \odot q) = \min({\mathbf t}(p), {\mathbf t}(q));$

Disjunction is simply defined as ${\mathbf t}(p \oplus q) = \max({\mathbf t}(p),{\mathbf t}(q)),$ by De Morgan laws, and implication by ${\mathbf t}(p \Rightarrow q) = \max(1- {\mathbf t}(p), {\mathbf t}(q)))$ (using $p \Rightarrow q \equiv \sim p \oplus p$). It is obvious and well-known that this logic has no tautologies, that is, there is no propositional formula $p$ such that ${\mathbf t}(p) = {\mathbf T}$ whatever the truth value of its components.

The set ${\mathbb{V}}_{3} = \{{\mathbf {T, F, U}} \}$ is often (misleadingly, as we shall see) presented as being the usual truth value set ${\mathbb{V}}_{2} =\{F, T\}$ augmented with the value U, whereby T is identified with $T,$ and F is identified with $F.$ Actually, in his book, Kleene (1952) explicitly interprets the third truth value U as unknown, namely (p. 64):

We further conclude from the introductory discussion that, for the definitions of partial recursive operations, $\{{\mathbf {T, F, U}}\}$ must be susceptible of another meaning besides (i) ‘true’, ‘false’, ‘undefined’, namely (ii) ‘true’, ‘false’, ‘unknown’ (or value immaterial). Here, ‘unknown’ is a category into which we regard any proposition as falling, whose value we either do not know or choose for the moment to disregard; and it does not exclude the two other possibilities ‘true’ and ‘false’.

However, we may notice that in a truth value set as $\{{\mathbf {T, F, U}}\},$ each value excludes the other, which does not sound in agreement with the above statement. We have argued elsewhere (Dubois and Prade 1994, 2001), following scholars like De Finetti (1936), that the concept of unknown, being epistemic in nature is an information state, not a truth value, the latter being the prototype of an ontic notion. More specifically:

• The choice of the set of truth degrees defines the nature of an atomic proposition $a,$ it is part of its definition (in this sense truth is ontic). Namely:

  • 1. The choice of the truth-set is a matter of convention (we can define $a$ as susceptible of being only true or false, but we can change this convention to more truth values)

  • 2. A truth value evaluates the extent to which a proposition $p$ applies to a precise situation. So, the truth-degree of $p$ is an abstract notion that measures the “$p$-ness” of a situation.

  • 3. The truth value set is just the assumed range of propositional variables or logical functions.

• Epistemic notions (like knowledge, or belief) measure the extent to which a proposition is compatible with an agent’s information about the situation (Hintikka 1962)

  • 1. The lack of knowledge is not a matter of convention; it has to be coped with.

  • 2. Degrees of belief, quality of knowledge, reliability of a report are meta-notions with respect to truth (De Finetti 1936).

  • 3. Elementary models of epistemic notions on Boolean propositions are basically ternary: one may either be informed that $p,$ or that $\neg p,$ or not be informed (Dubois and Prade 2001).

So if the truth value U is viewed as ontological, it cannot mean but half-true (like a bottle can be half-full), thus interpreting Kleene three-valued logic as a fuzzy logic. However, the interpretation of U as unknown makes it an epistemic valuation expressing the hesitation between true and false. In this view, propositions can only be true or false, and the value U should be identified with the set ${\mathbb{V}}_{2}= \{F, T\}$ itself, understood as a disjunction either T or F, that is, any of the two usual truth values is possible. So, T should be identified not with the element $T$ of ${\mathbb{V}}_{2},$ but with the singleton $\{T\}$ (that is, only $T$ is possible) and F should be identified with the singleton $\{F\}$ (that is, only $F$ is possible).

A natural way of extending the truth-tables of classical logic to the totally ordered set ${\mathbb{V}} = \{{\mathbf {T, F, U}}\}$ is then to apply interval calculus to the Boolean connectives (De Cooman 1999): if $*$ is a Boolean connective, $A, B \subseteq \{F, T\}$ non-empty subsets of ontological truth values, $A*B$ is defined as the canonical extension of operation $*$ to set-valued arguments. In other words, if ${\mathbf t} (p)= A$ and ${\mathbf t}(q) = B,$ then

$$ {\mathbf t}(p*q) = \{t(p*q) = t(p)*t(q): t(p) \in A, t(q) \in B\}. $$

Consider U as the set ${\mathbb{V}}_{2}$ (understood as an interval such that $F < T$), the other intervals being the singletons $\{F\}$ and $\{T\}.$ It comes down to computing the following cases (Dubois 2010b):

• For conjunction: $\{F\}\wedge \{F, T\} = \{F\wedge F, F\wedge T\} = \{F\}; \{T\}\wedge \{F, T\} = \{F\wedge T, T\wedge T\} = \{F, T\},$ etc.

• For disjunction: $\{F\}\vee \{F, T\} = \{F\vee F, F\vee T\} = \{F, T\} ; \{T\}\vee \{F, T\} = \{T\vee F, T\vee T\} = \{ T\},$ etc.

• For negation: $\neg \{F, T\} = \{ \neg F, \neg T \} = \{F, T\},$ etc.

It yields truth-tables on Tables 1 and 2 for extended connectives $\vee$ and $\wedge.$ We already explained elsewhere (Dubois 2010b) that

• This local uncertainty propagation process yields the truth tables of strong Kleene logic on ${\mathbb{V}}_{3} = \{{\mathbf {T, F, U}}\}$ for three-valued negation $\sim,$ conjunction $\odot,$ disjunction $\oplus$ and implication $\Rightarrow$.

• The algebra underlying Kleene-like three-valued logic is thus isomorphic to the set of non-empty intervals on $\{F, T\},$ equipped with the interval extension of classical connectives.

• The interval truth-calculus neglects possible logical links between Boolean formulas. For instance, in the light of the set-valued interpretation of Kleene truth values, one should not compute ${\mathbf t}(p\odot q)$ as $\min({\mathbf t}(p), {\mathbf t}(q))$ if $p = \neg q$ and ${\mathbf t}(q) = n({\mathbf t}(p)).$ Indeed $\{t(p\wedge \neg p): t(p) \in \{F, T\}\} = \{F\}.$ So, even if $t(p)$ is unknown $( {\mathbf t}(p) = {\mathbf U}),t(p\wedge \neg p) = F$ (i.e. ${\mathbf t}(p\wedge \neg p) = {\mathbf F}$), while in Kleene logic, ${\mathbf t}(p\odot \sim p) = \min({\mathbf t}(p), n({\mathbf t}(p)) = {\mathbf U}.$

Table 1 Disjunction for interval-valued Boolean propositions

Table 2 Conjunction for interval-valued Boolean propositions

More generally, if $p$ is a propositional tautology, then the strong Kleene truth-tables do not yield ${\mathbf t}(p) = {\mathbf T}$ as is well-known. This is because if all atoms in $p$ have (epistemic) truth value U, then Kleene truth tables enforce ${\mathbf t}(p) = {\mathbf U}.$ So this logic loses all tautologies of propositional logic for no good reason (just like Partial Logic, Blamey 1998, that semantically relies on Kleene’s intuitions of modeling ignorance; see the critique in Dubois 2008). In the following, we cast Kleene logic into a modal framework and we manage to lay bare the meaning of the Kleene truth-tables.

Note that interval-valued fuzzy logics (Van Gasse et al. 2008) fall into the same trap of confusing truth values with intervals thereof, assuming interval arithmetics can generate well-behaved connectives for handling intervals of truth values. One can view them as non-Boolean counterparts of Kleene strong logic, replacing the non-empty subsets of $\{T, F\}$ by sub-intervals of the the initial truth value set (the unit interval). This approach to handling ill-known truth values is again too weak. It loses some properties of the original algebra equipping the unit interval (see Dubois 2010b, 2011 for more discussions). Similar difficulties can be laid bare regarding the use of Łukasiewicz three-valued logic for capturing the algebras of rough sets (Ciucci and Dubois 2010).

3 Expressing Kleene Logic in epistemic logic

It is clear that in a propositional language ${\mathcal{L}},$ we cannot express that we do not know a proposition $p.$ A set $B$ of propositions, viewed as a knowledge base, can only represents what an agent knows or believes. In particular, supposing $p\in B$ means that an agent knows that $p,$ then $\neg p\in B$ can only mean that the agent knows that $p$ is false, not that $p$ is unknown. In the literature, epistemic logics (Hintikka 1962; Halpern et al. 2003) have been devised to account for this distinction in a modal setting. In the following we propose a simplified modal formalism that explicitly encodes the notion of ignorance and avoids losing tautologies of the propositional calculus, while accounting for the intuition behind the epistemic valuation U, and the truth-tables of Kleene logic.

We show how to bridge the gap between the two approaches, while solving the paradox of losing tautologies.

3.1 A modal formalism based on possibility theory for handling partial ignorance

The simplest representation of partial ignorance for an agent is made of a subset of possible worlds $E$ one of which is the real one. In the setting of a Boolean language, $E$ is a non-empty subset of interpretations understood as a disjunction thereof, and is typically the set of models of a formula $p$ expressible in the language. If $E$ reflects what is known about the world, the truth status of another proposition $q$ may or not fail to be known (Dubois and Prade 2001):

• either $E \subseteq [q]$ and then, $q$ is surely true; in terms of Kleene’s truth values, ${\mathbf t}(q) = {\mathbf T};$

• or $E \subseteq [\neg q]$ and then, $q$ is surely false; in terms of Kleene’s truth values, ${\mathbf t}(q) = {\mathbf F};$

• or none of $q$ and $\neg q$ can be derived from $E$ and then the truth-status of $q$ is unknown, i.e. ${\mathbf t}(q) = {\mathbf U}$

Viewing the characteristic function of $E$ as a possibility distribution (Dubois and Prade 1988), $q$ is said to be possible if $E \cap [q] \neq \emptyset,$ and necessary or certain if $E \subseteq [q].$ We can use a set function $\Uppi: 2^{\Upomega} \to \{0, 1\}$ whereby $\Uppi([q]) = 1$ if and only if $q$ is possible. The dual set function $N([q]) = 1 - \Uppi([\neg q])$ takes value one if and only if $q$ is certain. It is clear that ${\mathbf t}(q) = {\mathbf T}$ if and only if $N([q]) = 1,{\mathbf t}(q) = {\mathbf F}$ if and only if $\Uppi([q]) = 0$ and ${\mathbf t}(q) = {\mathbf U}$ if and only if $\Uppi([q]) = \Uppi([\neg q]) = 1,$ thus bridging the gap between Kleene logic and possibility theory (see De Cooman 1999 for more details).

However, contrary to Kleene logic valuations, functions $\Uppi$ and $N$ are not compositional, since while $N([q_{1}\wedge q_{2}]) = \min(N([q_{1}]), N([q_{2}])$ for conjunction, $N([q_{1}\vee q_{2}])$ cannot be obtained from $N([q_{1}])$ and $N([q_{2}]).$ If $q_{1}\vee q_{2}$ is a Boolean tautology then $N([q_{1}\vee q_{2}]) = 1,$ even if $N([q_{1}]) = 0$ or $N([q_{2}]) = 0.$ Likewise, $\Uppi$ is compositional for disjunction and not for conjunction. Possibility theory thus preserves the axioms of propositional logic.

It is clear that in general, Kleene truth-tables may disagree with the rules of possibility theory due to possible logical dependencies between $q_{1}$ and $q_{2}.$ But there are cases when Kleene truth-tables compute the right epistemic truth values, and no information is lost (De Cooman 1999).

Reasoning about ignorance based on possibility theory can be captured by a modal formalism, recently suggested by Banerjee and the author (Banerjee and Dubois 2009), called Meta-Epistemic Logic (MEL). In agreement with epistemic logic, we thus consider that the proper handling of ignorance requires a more powerful language than propositional logic. However our treatment differs from usual epistemic logics (Hintikka 1962; Halpern et al. 2003) on several points:

• We do not consider augmenting the propositional language, but encapsulating it in a higher order language, so as to avoid mixing ontological and epistemic propositions: the original basic language is not part of the modal one.

• We adopt a very simple semantics of partial knowledge based on subsets of propositional ontological valuations (it is actually more in line with the intuitions of the founding fathers of epistemic logic).

• We totally avoid the problem of introspection and nested modalities that cause specific difficulties. We consider the case of collecting and reasoning about epistemic information coming from an external source.

Suppose the epistemic state of an agent is $E.$ Using a modal formalism, we can encode $E \subseteq [p]$ (the agent believes $p$) as $E \models \square p$ instead of $N([p]) = 1,$ and $E \cap [q] \neq \emptyset$ as $E \models \lozenge p,$ instead of $\Uppi([p]) = 1.$ The usual duality applies: $E \models \lozenge p$ if and only if $E \models \neg \square \neg p.$

The language of MEL denoted by ${\mathcal{M}}_{{\mathcal{L}}}$ uses the syntax of a regular modal logic, handling atomic formulas of the form $\phi = \square p,$ where $p$ is a propositional wff in a propositional language ${\mathcal{L}},$ and their combinations by Boolean conjunction, negation and disjunction. No nesting of modal sentences is allowed, nor are allowed mixed sentences such as $p \vee \square q$ combining sentences in ${\mathcal{L}}$ and modal ones.

The axioms of MEL are those of a basic doxastic logic:

• (PL): (i) $\phi \to (\psi \to \phi);$

  (ii) $(\phi \to (\psi \to \mu)) \to ((\phi \to \psi) \to (\phi \to \mu));$

  (iii) $(\neg \phi \to \neg \psi) \to (\psi \to \phi).$

• (RM): $\square p\to \square q,$ whenever $\vdash p\to q.$

• (M): $\square(p\wedge q ) \to (\square p\wedge \square q ).$

• (C): $(\square p\wedge \square q ) \to \square(p\wedge q ).$

• (N): $\square \top.$

• (D): $\square p\to \lozenge p.$

• (MP): If $\phi, \phi \to \psi$ then $\psi.$

It is obvious that MEL is the subjective fragment of the modal logic KD without nesting (equivalently, the subjective part of S5). Note that (M) is a consequence of (RM); (M) and (C) lay bare the equivalence between $\square(p\wedge q)$ and $\square p\wedge \square q$ as in possibility theory. (M) and (C) can be replaced by axiom (K):

$$ {\rm (K)}\!\!:\;\square (p\to q) \to ( \square p \to \square q). $$

As to the semantics, epistemic states serve as interpretations of modal formulas, as hinted above: the set of interpretations of ${\mathcal{M}}_{{\mathcal{L}}}$ is identified with the set of non-empty subsets of interpretations of ${\mathcal{L}}$ (they can be viewed as “meta-models”). Note that we do not need accessibility relations here, because there are no nesting of modalities, nor mixed objective and modal formulas. Yet we follow Hintikka’s definition of the truth of $\square p$ (Hintikka 1962): “in all possible worlds compatible with what the agent believes, it is the case that $p$”. However, we just denote by $E$ “all possible worlds compatible with what the agent believes” instead of interpreting them as being “accessible from the possible world which the agent is currently in”, this particular possible world sounding quite elusive. Apart from the use of ‘meta-models" for modal formulas, the latter are evaluated classically, as they belong to a standard propositional language whose atoms are of the form $\square p$ for $p \in {\mathcal{L}}.$

Formally, satisfiability in MEL is defined in a standard way, granted the idea that the set of valuations of ${\mathcal{M}}_{{\mathcal{L}}}$ is ${\mathbb{I}}_{{\mathcal{M}}_{{\mathcal{L}}}} =\{ E \subseteq \Upomega, E\neq \emptyset\}$ (recall that due to axiom (D), the agent is supposed to have a consistent epistemic state). In details:

• $E \models_{\rm MEL} \square p$ if and only if $\forall v \in E, v \models p$ (Hintikka’s definition);

• $E \models_{\rm MEL} \neg \phi$ if and only if $E \not\models_{\rm MEL} \phi;$

• $E \models_{\rm MEL} \phi\wedge \psi$ if and only if $E \models_{\rm MEL} \phi$ and $E \models_{\rm MEL} \psi;$

• $E \models_{\rm MEL} \phi\vee \psi$ if and only if $E \models_{\rm MEL} \phi$ or $E \models_{\rm MEL} \psi.$

MEL is easily proved sound and complete with respect to the proposed semantics (Banerjee and Dubois 2009). This is not surprising as MEL is also a fragment of S5 and epistemic states can be viewed as trivial equivalence relations. Actually, the set of MEL formulas quotiented by semantic equivalence is isomorphic to the set of families of non-empty subsets of interpretations of ${\mathcal{L}},$ each such family representing a meta-epistemic state (epistemic state over epistemic states); see details in Banerjee and Dubois (2009).

3.2 The reification of epistemic valuations

Kleene logic truth values can be interpreted in an information collection setting involving two agents, one receiving a testimony from the other. The agent providing information is called the source. The source provides knowledge interpreted by the other agent by attaching epistemic valuations to Boolean propositions in ${\mathcal{L}}$ using an epistemic language ${\mathcal{E}}_{{\mathcal{L}}}\!\!:$

• Assigning T to $p$ means the source claims to know that $p$ is true; this is denoted by $(p, {\mathbf T}).$

• Assigning F to $p$ means the source claims to know that $p$ is false; this is denoted by $(p, {\mathbf F}).$

• Assigning U to $p$ means the source claims to ignore if $p$ is true or false; this is denoted by $(p, {\mathbf U}).$

It is possible to capture this setting using the simple epistemic logic outlined above, where the use of a KD modality encapsulating propositional formulas reflects the distinction between the source of information and the agent that reasons about what is known or not by the source. The agent would like to figure out what the source knows and what it does not know. So, a possible world for the agent is an epistemic state $E$ for the source.

Namely, it is clear from the above discussions that we can identify $(p, {\mathbf T})$ to $\square p$ in ${\mathcal{M}}_{{\mathcal{L}}}.$ As for the other Kleene truth values, they can be captured in the MEL syntax as follows:

• In agreement with Kleene negation, $(p, {\mathbf F})$ should stand for $(\neg p, {\mathbf T}),$ that is $\square \neg p$ in MEL. The idea is that if the source claims that $p$ is true, it is equivalent to claim that $\neg p$ is false.

• The epistemic valuation unknown is explicitly modelled as ignorance about truth or falsity of $p.$ Hence $(p, {\mathbf U})$ stands for $\neg ( p, {\mathbf T})\wedge \neg (p, {\mathbf F}),$ which writes $\lozenge p \wedge \lozenge \neg p$ in MEL. Note that while assigning U to $p$ is not incompatible with $p$ being eventually true or false, the three epistemic values ${\mathbf {T, F,U}}$ are mutually incompatible.

Another propositional language ${\mathcal{E}}_{{\mathcal{L}}}$ can then be introduced for reasoning about unknown information, which is a simple rewriting of MEL. Atoms of the language ${\mathcal{E}}_{{\mathcal{L}}}$ form the set $\{(p, {\mathbf T}),p \in {\mathcal{L}}\}.$ A formula $\phi \in {\mathcal{E}}_{{\mathcal{L}}}$ is either of the form $(p, {\mathbf T}),$ or $\neg\phi$ or $\phi \wedge\psi.$ So ${\mathcal{E}}_{{\mathcal{L}}}$ is a propositional language handling propositions epistemically labelled by Kleene truth values, and encapsulating another standard propositional language.

Axioms of this propositional meta-logic are obtained by rewriting MEL axioms as follows (where $\to$ denotes material implication):

• (PL): (i) $\phi \to (\psi \to \phi);$

  (ii) $(\phi \to (\psi \to \mu)) \to ((\phi \to \psi) \to (\phi \to \mu));$

  (iii) $(\neg \phi \to \neg \psi) \to (\psi \to \phi).\,(\hbox{where}\,\phi, \psi \,\hbox{denote} \,{\mathcal{E}}_{{\mathcal{L}}} \,\hbox{formulas})$

• (A1): $(p, {\mathbf T})\to (q, {\mathbf T}) ,$ whenever $\vdash p\to q.$

• (A2): $(p\wedge q, {\mathbf T} ) \to (p, {\mathbf T})\wedge (q, {\mathbf T}).$

• (A3): $(p, {\mathbf T})\wedge (q, {\mathbf T}) \to (p\wedge q, {\mathbf T} ).$

• (A4): $(\top, {\mathbf T}).$

• (A5): $(p, {\mathbf T})\to \neg (p, {\mathbf F}).$

• (MP): If $\phi, \phi \to \psi$ then $\psi.$

The first collection of axioms assumes that the agent reasons in propositional logic about the knowledge provided by the source. The second axiom enforces coherence of the epistemic valuation T with respect to the logical inference of propositions in the lower language. Axioms (A2) and (A3) mean that, for the source, asserting the truth of a conjunction of propositions in $\mathcal {L}$ is the same as asserting the truth of the conjuncts. Axiom (A4) assumes the source considers all classical tautologies as true. Axiom (A5) forbids the source from claiming simultaneously the truth of $p$ and its falsity. It means the knowledge possessed by the source is consistent.

We can call this logic, based on language ${\mathcal{E}}_{{\mathcal{L}}},$ KEL for Kleene-style Epistemic Logic.

Using this language, the source is allowed to testify of its knowledge in a more refined way than just assigning epistemic valuations to propositions. For instance, the formula $(p, {\mathbf T})\vee (p, {\mathbf F})$ is well-formed, and the source can be allowed to assert such sentences. This formula means that the source knows the truth value of $p$ but that the agent does not. Note that such a sentence may be problematic if the meta-logic is used for introspection: indeed, if the source is the agent itself then this sentence means “I know that either I know that $p$ is true or that $p$ is false, but I ignore which of the two”. This is questionable because, you cannot at the same time claim to yourself that you know the truth value of $p$ without knowing which one. Such sentences have been considered dishonest from an introspective point of view (Halpern and Moses 1985). However, in the context of a source testifying to another agent, such sentences become more natural.

This approach makes a difference between information that is explicitly said to be unknown and plain unknown information. However, contrary to the logic of Levesque (1984), this distinction is not related to the problem of logical omniscience (whereby a proposition is implicitly unknown because requiring too long inference chains to be told true or false). This distinction does not pertain either to the difference between axioms ((p, U) is assumed, because the source declared it) and theorems ((p, U) can be inferred in KEL). It refers to the difference between propositions $p$ for which (p, U) can be proved from a meta-knowledge base ${\mathcal{K}} \subset {\mathcal{E}}_{{\mathcal{L}}}$ and propositions $p$ for which neither (p, U) nor (p, T), nor (p, F) can be proved from ${\mathcal{K}}.$ Among the latter, there are those for which ${\mathcal{K}}$ only entails $(p, {\mathbf T})\vee(p, {\mathbf F}),$ whose truth status the agent ignores, but he knows that the source knows and did not reveal.

3.3 The limited expressiveness of Kleene three-valued logic

MEL (or equivalently KEL) seems to be the proper logic for capturing Kleene logic, while preserving all tautologies of propositional logic. However, once cast into the language of MEL, it becomes clear that apparent paradoxes of Kleene logic are due to a lack of expressiveness of the latter. First of all, the following results are easily obtained, expressed in the KEL syntax:

Proposition 1

The excluded fourth holds in KEL that is

$$ \vdash_{KEL} (p, {\varvec {T}}) \vee (p, {\varvec {U}})\vee (p, {\varvec {F}}). $$

Proof

$(p, {\mathbf T}) \vee (p, {\mathbf U})\vee (p, {\mathbf F})$ stands for $\square p \vee (\neg \square p\wedge \neg\square \neg p)\vee \square \neg p \equiv (\square p \vee \neg \square p)\wedge (\neg\square \neg p\vee \square \neg p),$ a conjunction of tautologies in MEL.

In fact, KEL atoms of the formula $(p, {\mathbf T}) \vee (p, {\mathbf U})\vee (p, {\mathbf F})$ are mutually exclusive with each other, and they cover all possibilities. But note that $(p,{\mathbf T})\vee (\neg p, {\mathbf T})$ is not a tautology. Nevertheless:

Proposition 2

If p is a propositional tautology then $\vdash_{KEL} (p, {\varvec {T}})$ holds. In particular, the law of excluded middle $\vdash_{KEL} (p\vee \neg p, {\varvec {T}})$ and the law of non-contradiction $\vdash_{KEL} (\neg(p\wedge \neg p), {\varvec {T}})$ are preserved in the lower language.

Proof

Due to axiom (N).

The next question is whether we can relate Kleene logic connectives and the corresponding Boolean connectives in the propositional logic encapsulated into MEL:

Proposition 3

If p, q are logically independent propositions, and t stands for the epistemic valuation function ${\mathcal{L}}\to {\mathbb{V}}_{3},$ and function $f_{\odot}$ interprets conjunction according to Kleene logic truth-tables, then,

$$ \{(p, x), (q, y) \}\vdash_{KEL} (p \wedge q, f_{\odot}(x, y)). $$

except if $x = y = {\mathbf{U}}.$

Proof

It is obvious that $\{(p, {\mathbf{T}}), (q, {\mathbf{T}}) \}\vdash_{KEL} (p \wedge q,{\mathbf{T}})$ from axiom (A3). Consider $\{(p, {\mathbf{T}}), (q, {\mathbf{U}}) \}\vdash_{KEL} (p \wedge q,{\mathbf{U}})\!\!:$ It comes down to proving $\lozenge (p\wedge q)$ and $\lozenge (\neg p\vee \neg q)$ from $\square p, \lozenge q, \lozenge\neg q$ in MEL. Of course, $\lozenge\neg q$ clearly implies $\lozenge (\neg p\vee \neg q).$ Now, $\square p$ is equivalent to $\neg \lozenge\neg p,$ which implies $\neg \lozenge (\neg p\wedge q).$ Since $\lozenge q \equiv \lozenge (p\wedge q) \vee \lozenge (\neg p\wedge q)$ and $p\wedge q \neq \bot,\lozenge (p\wedge q)$ then derives from $\lozenge (p\wedge q) \vee \lozenge (\neg p\wedge q)$ and $\neg \lozenge ( \neg p\wedge q).$ We can prove likewise that $\{(p, {\mathbf{T}}), (q, {\mathbf{F}})\} \vdash_{KEL} (p \wedge q,{\mathbf{F}})$ and that $\{(p, {\mathbf{F}}), (q, {\mathbf{F}})\}\vdash_{KEL}(p \wedge q,{\mathbf{F}}).$

The interesting case is the fact that $\{(p, {\mathbf{U}}), (q, {\mathbf{U}}) \}$ does not (always) entail $(p \wedge q, {\mathbf{U}})$ in KEL, even if $p$ and $q$ are independent. Indeed, let us reason at the semantic level due to completeness. Take for instance $E = [(p\wedge\neg q)\vee (\neg p\wedge q)] \neq \emptyset$ since $p$ and $q$ are independent. Note that $E\cap [p] \neq \emptyset, E\cap [p]^{c} \neq \emptyset, E\cap [q] \neq \emptyset$ and $E\cap [q]^{c} \neq \emptyset.$ Then it is clear that $E \models_{KEL} (p, {\mathbf{U}})\wedge (q, {\mathbf{U}}),$ and $E\models_{KEL} (p \wedge q,{\mathbf{F}}).$ We can also reason inside MEL, where $\{(p, {\mathbf{U}}), (q, {\mathbf{U}})) \}$ reads $\{ \lozenge p,\lozenge q, \lozenge \neg p,\lozenge \neg q\}$ from which $\lozenge (p\wedge q)$ does not follow in general.

Let us try to express in MEL or KEL pieces of information that can be expressed in Kleene logic. A formula in Kleene logic can be expressed in MEL by formulas involving only possibility and necessity of literals (it is a specific fragment). Indeed, let $\Upphi(p)$ be the translation of a Kleene logic formula $p$ into MEL. If $p = a$ is an atom, stating its Kleene-style truth reads $\square a$ in MEL, and its Kleene falsity by $\square \neg a$ ($(a, {\mathbf F})$ in KEL). Then recursively $\Upphi(p \odot q) = \Upphi(p) \wedge \Upphi(q)$ and $\Upphi(p \oplus q) = \Upphi(p) \vee \Upphi(q).$ It corresponds to a very specific sublanguage of MEL. Regarding the lack of tautologies, noticing that, for instance, $a \oplus \neg a$ in Kleene logic reads $\square a \vee \square \neg a$ in MEL, the latter is indeed not a tautology, and in fact the tautology $\square (a \vee \neg a)$ is not expressible in Kleene logic at all.

A model (valuation) t comes down to attaching Kleene truth values to atoms. In other words, it is possible to partition the set ${\mathcal{A}}$ of atoms into true (${\mathbf t}(a) = {\mathbf T}$ if $a\in {\mathcal{A}}_{T}$), false (${\mathbf t}(a) = {\mathbf F}$ if $a\in{\mathcal{A}}_{F}$) and unknown ones (${\mathbf t}(a) = {\mathbf U}$ if $a\in{\mathcal{A}} \setminus({\mathcal{A}}_{T} \cup {\mathcal{A}}_{F}$)). This is typically the case for relational databases with Boolean attributes where unknown is understood as a null value. The corresponding epistemic state is $E_{\mathbf t} = [\bigwedge\nolimits_{a \in {\mathcal{A}}_{T}} a \wedge \bigwedge\nolimits_{a \in {\mathcal{A}}_{F}} \neg a]$ induced by a conjunction of propositional literals, that is a partial interpretation. In fact such epistemic states are very specific ones, while in the possibility theory setting, an epistemic state can be the set of models of any formula. The expressive power of Kleene logic for representing epistemic states is thus limited to those encoded by conjunctions of literals. For instance, asserting the truth of excluded or of propositional atoms as shown above, cannot be captured by partial models (Dubois 2008).

In KEL, Kleene logic valuations ${\mathbf t}$ can be expressed by knowledge bases of the form

$$ {\mathcal{K}}_{\mathbf t} = \{(a, {\mathbf T}), a \in {\mathcal{A}}_{T}\} \cup \{(a, {\mathbf F}), a \in {\mathcal{A}}_{F}\} \cup \{(a, {\mathbf U}), a \not\in {\mathcal{A}}_{T}\cup{\mathcal{A}}_{F}\}. $$

The meta-models of such a set of KEL formulas include more than those corresponding to a partial interpretation. Any subset of $E_{\mathbf t}$ that makes no atomic proposition $a \in{\mathcal{A}} \setminus({\mathcal{A}}_{T} \cup {\mathcal{A}}_{F})$ true or false will do.

Given a Kleene valuation ${\mathbf t},$ queries $q$ of the form: find the epistemic status of a conjunction of independent literals $\{b \in {\mathcal{B}}_{T}\} \cup\{ \neg b : b \in {\mathcal{B}}_{F}\} ,$ where ${\mathcal{B}}_{T}\cap {\mathcal{B}}_{F} = \emptyset,$ are handled using Kleene conjunction as

$$ {\mathbf t}(q) = {\mathbf t}((\odot_{b \in {\mathcal{B}}_{T}} b) \odot (\odot_{b \in {\mathcal{B}}_{F}} \sim b)) = \min\left(\min_{b \in {\mathcal{B}}_{T}} {\mathbf t}(b),\min_{b \in {\mathcal{B}}_{F}} {\mathbf t}(\neg b)\right). $$

This is a typical query in relational data bases. It corresponds to the following tests on literals:

• ${\mathbf t}(q) = {\mathbf T}$ if ${\mathcal{B}}_{T} \subseteq {\mathcal{A}}_{T}$ and ${\mathcal{B}}_{F} \subseteq {\mathcal{A}}_{F};$

• ${\mathbf t}(q) = {\mathbf F}$ if ${\mathcal{A}}_{T} \cap {\mathcal{B}}_{F} \neq \emptyset$ or ${\mathcal{A}}_{F} \cap {\mathcal{B}}_{T} \neq \emptyset;$

• Otherwise, ${\mathbf t}(q) = {\mathbf U}$

As shown in Proposition 3 :

• ${\mathbf t}(q) = {\mathbf T}$ if ${\mathcal{K}}_{\mathbf t} \vdash_{KEL} (\bigwedge\nolimits_{b \in {\mathcal{B}}_{T}} b \wedge \bigwedge\nolimits_{b \in {\mathcal{B}}_{F}} \neg b, {\mathbf T})$

• ${\mathbf t}(q) = {\mathbf F}$ if ${\mathcal{K}}_{\mathbf t} \vdash_{KEL} (\bigwedge\nolimits_{b \in {\mathcal{B}}_{T}} b \wedge \bigwedge\nolimits_{b \in {\mathcal{B}}_{F}} \neg b, {\mathbf F}).$

However, the inference ${\mathcal{K}}_{\mathbf t} \vdash_{KEL} (\bigwedge\nolimits_{b \in {\mathcal{B}}_{T}} b \wedge \bigwedge\nolimits_{b \in {\mathcal{B}}_{F}} \neg b, {\mathbf U})$ cannot be obtained in MEL nor KEL from the base ${\mathcal{K}}_{\mathbf t}$ in the third situation because meta-models of ${\mathcal{K}}_{\mathbf t}$ contain more than the one expressed by partial valuation $E_{\mathbf t}.$ Some meta-models of ${\mathcal{K}}_{\mathbf t}$ correspond to formulas involving exclusive disjunction of literals (see the counter example to Kleene truth table for conjunction in Proposition 3).

Example

Suppose $A = \{a, b, c, d\}, {\mathcal{K}}_{\mathbf t} = \{(a, {\mathbf T}), ( b, {\mathbf F}), (c, {\mathbf U}), (d, {\mathbf U})\},$ and the query $c\wedge d.$ Consider $E = [a\wedge \neg b \wedge( (c\wedge \neg d)\vee (d\wedge \neg c))].$ Clearly $E\models {\mathcal{K}}_{\mathbf t}$ and $E\models (c\wedge d,{\mathbf F}).$ So ${\mathcal{K}}_{\mathbf t} \not \models (c\wedge d,{\mathbf U}),$ even if using Kleene logic ${\mathbf t}(c\odot d) = {\mathbf U}.$ In fact, it is also impossible to express the statement $(c\wedge d,{\mathbf U})$ in Kleene logic: indeed writing ${\mathbf t}(c\odot d) ={\mathbf U}$ is equivalent to “$(({\mathbf t}(c) ={\mathbf U})$ and $({\mathbf t}(d) \geq{\mathbf U}))$ or $(({\mathbf t}(d) ={\mathbf U})$ and $({\mathbf t}(c) \geq{\mathbf U}))$”. It reads in KEL: $((c,{\mathbf U})\wedge \neg(d, {\mathbf F}))\vee ((d,{\mathbf U})\wedge \neg(c, {\mathbf F})),$ which is weaker than $(c\wedge d,{\mathbf U})$ and obviously follows from ${\mathcal{K}}_{\mathbf t}.$

What is patent from the above discussion is that Kleene logic is far less expressive than KEL since statements such as ${\mathbf t}(c \odot d) = {\mathbf U}$ are not at all equivalent to KEL formulas of the form $(c\wedge d, {\mathbf U}).$ Any statement of the form ${\mathbf t}(p) = x$ where $p$ is a formula in Kleene logic and $x$ is a Kleene truth value will be translated by a formula in KEL with Kleene truth values attached to propositional literals only, not to propositional formulas at large.

These results enable Kleene logic to be better situated with respect to a full-fledged logic of incomplete information. While the interpretation of the truth-tables in terms of set-valued extensions of Boolean connectives indicates that Kleene logic is sound and will not produce wrong results (false propositions, where classical logic would predict true ones), it is clearly insufficient to propagate incomplete knowledge and to reason about ignorance in an optimal way and in a general setting. Kleene logic and its truth-tables can be captured by MEL, but they appear like obvious inferences (as in the above example) that are much less informative than what MEL can derive. The embedding of Kleene logic inside MEL indicates its limited expressiveness: Kleene logic can be viewed as a fragment of an epistemic logic, that presupposes specific restrictions regarding the forms of ignorance allowed, the type of knowledge that can be expressed and the kind of queries to be addressed.

3.4 Related works

There are other examples of what can be called encapsulated (or embedded) logics. For instance, possibilistic logic (Dubois et al. 1994) explicitly handles degrees of beliefs attached to Boolean propositions. At the syntactic level, it uses pairs $(p, \alpha)$ made of a Boolean proposition and a weight, where $\alpha$ is a lower bound of the degree of belief of proposition $p$ (understood as a necessity measure). It stands for a graded necessity modality. While $p$ is Boolean, $(p, \alpha)$ is not, as its set of models is fuzzy. However, contrary to epistemic logics, and the above proposal, the only possible connective used to combine beliefs $(p, \alpha)$ and $(q, \beta)$ is the conjunction (combining fuzzy sets of models by minimum). Possibilistic logics can be viewed as propositional logic encapsulated in a fragment of Gödel logic. More general forms of possibilistic logics according to such an embedding are proposed by Boldrin and Sossai (1999), using Gödel disjunction, negation and implication. More recently, in Dubois and Prade (2011) a generalized possibilistic logic is outlined. It extends MEL to graded possibility and necessity modalities, following a line initiated in Dubois et al. (1994). Hájek et al. (1995) use this method for both probability and possibility theories, thus understanding the probability or the necessity of a classical formula as the truth degree of another formula in the higher order language. This kind of embedding inside a fuzzy logic works for other uncertainty logics as well (see Sect. 4.5 of Dubois et al. 2007).

Another early example of encapsulated logics is Pavelka-style rendering of fuzzy logic, by means of formulas in Łukasiewicz logic to which weights are attached by a reification process (Hájek 1998) (a formula $\alpha \to p$ is true if the truth value of $p$ is at least $\alpha \in [0, 1]$). More generally, signed multiple-valued logics (Haehnle 1997) attach intervals $I_{p}$ of truth values to multiple-valued formulas, and a signed formula then expresses the requirement that the truth degree of the formula lies in the prescribed interval. It can be viewed as a multiple-valued logic encapsulated in Boolean propositional logic (with atoms that mean $t(p) \in I_{p}$). This approach is likely to handle interval-valued fuzzy sets in a more faithful way than the use of truth-functional interval-valued connectives. The most general approach to a labelled logic is by Lehmke (2001) who considers many-valued formulas to which fuzzy sets of truth values are attached (expressing fuzzy restrictions on the truth degrees of the embedded formulas).

4 A modal approach to reasoning with inconsistent testimonies

Belnap (1977a, b) logic can be viewed, from the point of view of its truth tables, as an augmented Kleene logic: on top of ignorance modelled by the epistemic value ${\mathbf{U}},$ that Belnap denoted by ${\mathbf{NONE}},$ there is another value expressing conflicting information, we shall denote by ${\mathbf{C}},$ and that Belnap denotes by ${\mathbf{BOTH}}.$ This logic is very important as it has led to a new algebraic structure called a bilattice, that has been extensively studied and used for non-monotonic reasoning and logic programming (Ginsberg 1988; Fitting 1991; Marquis et al. 2008). In Belnap setting, sources provide information about atomic propositions only, which means, in the non-conflicting case, working with partial models like in Kleene logic. Belnap epistemic states are partial models extended to accept conflicting opinions about some atoms. However, being truth-functional, it suffers from the same limitations as Kleene logic, if interpreted as a calculus of incomplete and contradictory knowledge over propositional logic.³ These limitations were discussed in Dubois (2008) (see Wansing and Belnap 2010 for Belnap’s reply and Dubois 2010a for a response). Here, we try to remedy them by the same approach as in the previous section, in a modal setting extending MEL to the handling of contradictions.

4.1 Belnap logic

Belnap (1977a, b) considers an artificial information processor, fed from a variety of sources, and capable of answering queries on propositions of interest. In this context, inconsistency threatens, all the more so as the information processor is supposed never to subtract information. The basic assumption is that the computer receives information about atomic propositions in a cumulative way from outside sources, each asserting for each atomic proposition whether it is true, false, or being silent about it. The notion of epistemic set-up is defined as an assignment, of one of four values denoted by ${\mathbf {T,F, BOTH, NONE}},$ to each atomic proposition $a, b,\dots :$

• 1. Assigning ${\mathbf T}$ to $a$ means the computer has only been told that $a$ is true.

• 2. Assigning ${\mathbf F}$ to $a$ means the computer has only been told that $a$ is false.

• 3. Assigning ${\mathbf {BOTH}}$ to $a$ means the computer has been told at least that $a$ is true by one source and false by another.

• 4. Assigning ${\mathbf {NONE}}$ to $a$ means the computer has been told nothing about $a.$

In view of the previous discussion, the set $\{{\mathbf {T,F, BOTH, NONE}} \}$ of epistemic truth values coincides with the whole power set of $\{F, T\},$ still letting ${\mathbf T} = \{T\},{\mathbf F} = \{F\},$ but the Belnap convention for other subsets of $\{F, T\}$ is not the same as in the previous section. According to these conventions (actually borrowed from Dunn (1976)), ${\mathbf {NONE}}$ represents the empty set and corresponds to no information received, while ${\mathbf {BOTH}}= \{F, T\}$ represents the presence of conflicting sources, some claiming the truth of $a$ some its falsity. ${\mathbf {BOTH}}$ expresses in Belnap setting an excess of truth values, the set $\{F, T\}$ being viewed as expressing T and F at the same time. Our convention in the previous section is opposite, as the set $\{F, T\},$ represents the hesitation between true and false and means T or F. So Belnap’s ${\mathbf {NONE}}$ corresponds to Kleene’s ${\mathbf U} .$

For the sake of clarity, we shall stick to the Kleene convention, leading to interpret ignorance as the disjunction between T and F, i.e. the set $\{F, T\}$ is denoted by ${\mathbf{U}}$ (instead of ${\mathbf {NONE}}$), while conflict is expressed by the empty set of truth values (reflecting the fact that a conflicting knowledge base has no model), and denoted by ${\mathbf C}$ (instead of ${\mathbf {BOTH}}$). Subsets of $\{F, T\}$ represent constraints on mutually exclusive truth values. Note that the latter conventions are in agreement with possibility theory (Dubois and Prade 1988; De Cooman 1999). Denoting by $\pi$ a possibility distribution valued on the unit interval, ${\mathbf U}$ can be encoded by $\pi(F) = \pi(T) = 1$ (it is a Boolean possibility distribution on $\{F, T\}$ representing ignorance), ${\mathbf C}$ by $\pi(F) = \pi(T) = 0$ representing the contradiction (this is the empty set, corresponding to no possible truth value left).

Belnap’s approach relies on two orderings in ${\mathbb{V}}_{4} = \{{\mathbf {T, F, C, U}} \}\!\!:$

• The information ordering, $\sqsubset$ whose meaning is “less informative than”, such that ${\mathbf U} \sqsubset {\mathbf T} \sqsubset {\mathbf C} ; {\mathbf U} \sqsubset {\mathbf F} \sqsubset {\mathbf C}.$ This ordering reflects the opposite of the inclusion relation of the sets $\emptyset,$ $\{F\}, \{T\},$ and $\{F, T\}.$ In fact it coincides with the specificity ordering of possibility theory (Dubois and Prade 1988). It intends to reflect the amount of (possibly conflicting) data provided by the sources. ${\mathbf U}$ is at the bottom because (to quote) “it gives no information at all”. ${\mathbf C}$ is at the top because (following Belnap) it gives too much information.

• The logical ordering, $\prec,$ representing “more true than” according to which ${\mathbf F} \prec {\mathbf C} \prec {\mathbf T}$ and ${\mathbf F} \prec {\mathbf U} \prec {\mathbf T},$ each chain reflecting the truth-set of Kleene’s logic. In other words, ignorance and conflict play the same role with respect to F and T according to this ordering.

The set ${\mathbb{V}}_{4}$ is isomorphic to $2^{\{F, T\}}$ equipped with two lattice structures:

• the information lattice, a Scott approximation lattice based on the information ordering, and with join and meet defined by union and intersection of sets of truth values (in this lattice, the maximum of ${\mathbf T}$ and ${\mathbf F}$ is C);

• the logical lattice, based on the logical ordering, and the interval extension of $\wedge,\vee$ and $\neg$ from ${\{F, T\}}$ to $2^{\{F,T\}}\setminus\{\emptyset\}$ like for Kleene logic regarding U; the same holds for C (if interpreted as the conjunctive set $\{F, T\}$). In this lattice, the maximum of ${\mathbf U}$ and ${\mathbf C}$ is T.

Then, connectives of negation, conjunction and disjunction are defined truth-functionally, following the rules of the bilattice (see Tables 3, 4).

Table 3 Belnap disjunction

Table 4 Belnap conjunction

In Belnap’s epistemic setting, the role of the computer is not to interpret the information provided by the sources, but just to store it. In particular, any piece of information supplied is viewed as a logical atom to which an epistemic qualifier is attached depending on the presence or not of sources claiming its truth or falsity. The computer is not supposed to be logically sophisticated and to behave like a propositional logic reasoner.

This minimal use of the information is at odds with usual approaches to reasoning about knowledge. Namely, this logic does not preserve tautologies since the epistemic values just register what the source said without interpreting these pieces of information. However, in the following, we shall assume information sources are propositional reasoners, and so is the agent receiving information from them. This assumption enables us to reinterpret Belnap truth-tables in the scope of epistemic logic.

4.2 Relating Belnap and Kleene epistemic values

In Belnap setting, a source is supposed to say whether an information item is considered as true, false or is unknown. However, like in the previous section on incomplete information, and unlike Belnap, we do not restrict ourselves to information supplied as logical atoms. Sources can provide information on Boolean formulas (which is more general than providing information on atoms). We consider sources as propositional reasoners declaring what they know or believe. For instance, they would never admit that $p\wedge \neg p$ is anything but false.

In Belnap setting, as we must represent the possibility of conflict, we need at least two sources of information, but not more. The assignment of ${\mathbf T}$ (resp. ${\mathbf F}$) to a proposition corresponds to at most two groups of sources, some saying ${\mathbf T}$ (resp. ${\mathbf F}$) the other ones expressing ignorance. The assignment of ${\mathbf U}$ corresponds to unanimity among sources that ignore if the proposition is true or not. So, it is easy to see that the number of agreeing sources is immaterial. As a consequence, we suggest a reinterpretation of this Belnap-style setting as an extension of the emitter/receiver paradigm of the KEL logic as follows.

• We assume two sources $\hbox{A}_{1}$ and $\hbox{A}_{2}$ conjointly expressing their knowledge about propositions in the syntax of KEL : For a number of propositions $p$ in ${\mathcal{L}},$ each source $\hbox{A}_{i}$ declares whether it is known [then $(p, {\mathbf T}_{i})$ is asserted] or its negation is known [then $(\neg p, {\mathbf T}_{i})$ is asserted], or the source declares ignorance (then $(p, {\mathbf U}_{i})$ is asserted). A difference can be made between a source being silent about $p$ and a source declaring its ignorance about $p,$ as we can express the latter in KEL, while the former corresponds to not writing anything in KEL about $p.$

• For each agent separately, the $KEL$ calculus applies. We then have two triplets of epistemic values $({\mathbf{{T_{1}}, {F_{1}}, {U_{1}}}})$ and $({\mathbf{{T_{2}}, {F_{2}}, {U_{2}}}}),$ one for each source.

• We can define (global) Belnap-like epistemic values as resulting from an aggregation of Kleene truth values as follows using KEL-like syntax:

  • $(p, {\mathbf T})$ stands for “at least one source asserts $p,$ but none denies it”, which corresponds to any of the pairs $({\mathbf T}_{1}, {\mathbf T}_{2}),({\mathbf T}_{1},{\mathbf U}_{2}),$ or $({\mathbf U}_{1}, {\mathbf T}_{2}).$

  • $(p, {\mathbf F})$ stands for “at least one source denies $p,$ but none asserts it”, which corresponds to any of the pairs $({\mathbf F}_{1}, {\mathbf F}_{2}),({\mathbf F}_{1}, {\mathbf U}_{2}),({\mathbf U}_{1}, {\mathbf F}_{2}).$

  • $(p, {\mathbf U})$ stands for “the two sources (declare to) ignore $p$”, which corresponds to $({\mathbf U}_{1}, {\mathbf U}_{2})$

  • $(p, {\mathbf C})$ stands for “one source asserts $p,$ and the other denies it”, which corresponds to any of the pairs $({\mathbf T}_{1}, {\mathbf F}_{2}),({\mathbf F}_{1}, {\mathbf T}_{2})$

In the above definitions, a pair $(x, y)$ of Kleene truth values stands for the pair of KEL statements $((p, x), (p, y)).$ These definitions are summarized on Table 5.

Table 5 Belnap Epistemic values from two Kleenean sources

4.3 A modal account of Belnap epistemic truth values

On this basis, we can extend modalities $\square$ and $\lozenge$ defined in the previous section from the single source case to the two sources situation, so as to account for the presence of conflicting statements. Define $\square_{i} p$ to stand for the agent $\hbox{A}_{i}$ asserting $p.$ Then $\square_{i}$ is a MEL modality in the usual sense, albeit referring to source $i.$ Now we define the global modal symbol $\square,$ where $\square p$ means “at least one source asserts $p$”, formally as $\square p\equiv \square_{1} p\vee \square_{2} p;$ on Table 5, it is the union of the first line and the first column. As usual, $\lozenge p \equiv \neg \square\neg p,$ that is $\lozenge p\equiv \lozenge_{1} p\wedge \lozenge_{2} p,$ that is “no source asserts $\neg p$”; on Table 5 it is made of the four slots containing ${\mathbf T}$ and ${\mathbf U}.$ Note that if $\square p$ holds, nothing is said about the opinion of the source that does not assert $p,$ if any. Likewise, if $\lozenge p$ holds, nothing is said about the opinion of the sources apart from their not denying $p.$

Belnap epistemic values can then be encoded as follows in terms of the global modalities $\square$ and $\lozenge$ (this can be checked by intersecting the subparts of the matrix corresponding to these modalities on Table 5):

• $(p, {\mathbf T})$ can be encoded as $\square p\wedge \lozenge p;$

• $(p, {\mathbf F})$ can be encoded as $\square \neg p\wedge \lozenge \neg p;$

• $(p, {\mathbf U})$ can be encoded as $\lozenge p\wedge \lozenge \neg p$ (as usual);

• $(p, {\mathbf C})$ can be encoded as $\square p\wedge \square\neg p.$

The choice of defining $\square p$ as a disjunction of necessity modalities is motivated by the attempt to conform with Belnap’s epistemic truth values. It is obvious other choices are possible, like defining a strong necessity $\blacksquare p\equiv \square_{1} p\wedge \square_{2} p$ requiring unanimity of sources declaring $p$ true prior to considering it so. We could even think of building a language involving both modalities.

4.4 A modal epistemic logic of conflicting testimonies

It is clear that the syntax of the elementary epistemic logic MEL is enough to account for Belnap epistemic truth values. However, the axiom system must be changed so that formulas like $\square p\wedge \square\neg p,$ even if expressing a contradiction between sources, are not a contradiction in the modal system. The axiom system for this conflict logic will be weaker than the axiom system for MEL: we must delete axioms (D) and (C).

• For (D), note that $\square p$ no longer implies $\lozenge p.$ This is clear from reading the ranges of $\square$ and $\lozenge$ on Table 5. It corresponds to the fact that the case $(p, {\mathbf C})$ exists.

• For the failure of (C), consider $\square p \wedge \square q \equiv (\square_{1} p \vee \square_{2} p) \wedge (\square_{1} q \vee \square_{2} q).$ It develops as

  $$ \square_{1} (p\wedge q)\vee \square_{2} (p\wedge q)\vee (\square_{1} p\wedge \square_{2} q)\vee (\square_{2} p\wedge \square_{1} q) $$

  i.e., $\square (p\wedge q)\vee (\square_{1} p\wedge \square_{2} q)\vee (\square_{2} p\wedge \square_{1} q)\not \models \square (p\wedge q).$

According to the above semantics, we should let axiom RM hold since both $\square_{1}$ and $\square_{2}$ satisfy it. It implies that axiom (M) holds too. However, we need to require $\lozenge \top$ should hold (since it is true for both $\lozenge_{1}$ and $\lozenge_{2}$): it cannot be a consequence of (N) because of the failure of (D). It should be clear that axiom K also fails since $\square p$ is expressed by a disjunction of modalities. If $\square p$ holds because $\square_{1} p$ holds, and $\square (p\to q)$ holds because $\square_{2} (p\to q)$ holds, then there is no way to conclude that either $\square_{1} q$ or $\square_{2} q$ holds.

Finally, we can expect the following property to hold:

Proposition 4

For any three propositions p, q, r, if each of $\square p, \square q, \square r$ holds then the proposition $\square (p\wedge r)\vee\square (p\wedge q)\vee\square (q\wedge r)$ holds as well.

Proof

It can be verified by developing $\square p \wedge \square q \wedge \square r$ in terms of $\square_{1}$ and $\square_{2}.$ This is a conjunction of three terms of the form $\square_{1} x \vee \square_{2} x, x = p, q, r.$ Equivalently it can be written as a disjunction of 8 conjunctions of three terms such as $\square_{i} p\wedge \square_{j} q\wedge \square_{k} r,$ where $i, j, k \in \{1, 2\}.$ Because $\square_{1}$ and $\square_{2}$ are KD modalities, enforcing the equality of two indices among the three leads to conjunctions of the form $\square_{i} x\wedge \square_{i} y$ in all the terms of the disjunction. Each conjunction of modal formulas thus obtained is equivalent to $\square_{i} (x\wedge y)$ which implies the disjunction of $\square (p\wedge r), \square (p\wedge q),\square (q\wedge r).$

So we propose the following axiom system for the extended two-source MEL logic with conflict (MELC):

• (PL): (i) $\phi \to (\psi \to \phi);$

  (ii) $(\phi \to (\psi \to \mu)) \to ((\phi \to \psi) \to (\phi \to \mu));$

  (iii) $(\neg \phi \to \neg \psi) \to (\psi \to \phi).$

• (RM): $\square p\to \square q ,$ whenever $\vdash p\to q.$

• 3-C: $\square p\wedge \square q\wedge \square r \to \square (p\wedge r)\vee\square (p\wedge q)\vee\square (q\wedge r)$

• (N): $\square \top.$

• (P): $\lozenge \top$

• (MP): If $\phi, \phi \to \psi$ then $\psi.$

The semantic account of this syntactic construction is as follows. Each source has its own epistemic state $E_{i},$ partially unknown to the receiver agent. Hence the set of (meta) interpretations for the new logic will be

$$ {\mathbb{I}}_{12} = \{(E_{1}, E_{2}): E_{i} \neq \emptyset, E_{i} \subseteq \Upomega, i = 1, 2\} $$

where $\Upomega$ is the set of interpretations of ${\mathcal{L}}.$ Moreover we define satisfaction of $\square p$ as follows:

$$ (E_{1}, E_{2}) \models \square p \quad \iff \quad E_{1}\subseteq [p] \quad {or} \quad E_{2}\subseteq [p]. $$

It is easy to prove that all axioms are verified by this semantics in terms of pairs of epistemic states, in agreement with Belnap epistemic values defined by Table 5. For instance, let us check (3-C): if $E_{i} \subseteq A, E_{j} \subseteq B, E_{k} \subseteq C$ for $i, j, k \in \{1, 2\}$ then if, without loss of generality, $i = j = 1,$ then $E_{i} \subseteq A\cap B,$ hence $\square (p\wedge q)$ holds for $[p] = A, [q] = B.$ Note that axiom (3-C) is a relaxation of axiom C: $\square p\wedge \square q \to \square (p\wedge q),$ valid in the regular logic KD.

A consequence of the system is

(CONS-3): if $p, q, r$ are mutually inconsistent, then $\vdash \neg (\square p \wedge \square q \wedge \square r).$

It can be shown that if $p, q, r$ are mutually inconsistent, then $\square p \wedge \square q \wedge \square r$ can never be true. Indeed, if $p, q, r$ are mutually inconsistent, then all MELC atomic formulas $\square (p\wedge r), \square (p\wedge q),\square (q\wedge r)$ are false ($\vdash \neg \square (p\wedge q)$ is a consequence of axiom (P), assuming that $\neg p \vee \neg q$ is a tautology). So that $\vdash \neg (\square p \wedge \square q \wedge \square r)$ follows from (3-C) by modus tollens. But note that $\square p \wedge \square\neg p$ is satisfiable in MELC (since we may have $E_{1} \cap E_{2} = \emptyset$).

MELC thus coincides with a fragment of bimodal $\hbox{KD}_{2}$ logic, where all formulas are Boolean combinations of formulas of the form $\square p,$ an abbreviation of $\square_{1}p \vee \square_{2} p$ for non-modal formulas $p.$

4.5 Reified Belnap truth values

It is possible to translate the MELC language into an extension of KEL that properly accounts for conflict using Belnap truth values as follows, as can be checked from Table 5:

• $\square p$ should stand for $(p, {\mathbf T})\vee (p, {\mathbf C});$

• $\lozenge p$ should stand for $(p, {\mathbf T})\vee (p, {\mathbf U}).$

Indeed, for $\square p,$ the fact that one source claims $p$ does not prevent the other one from claiming its negation. We still have that $(p, {\mathbf F})$ stands for $(\neg p, {\mathbf T}),$ like in KEL, while now $\neg (p, {\mathbf F})\wedge \neg (p, {\mathbf T})$ is equivalent to $(p, {\mathbf C}) \vee (p, {\mathbf U}).$ So, now, $(p, {\mathbf T})$ and $(p, {\mathbf C})$ need to be introduced as primitive symbols, along with the requirement that they are inconsistent with each other. Then $(p, {\mathbf U})$ is short for $\neg (p, {\mathbf T})\wedge\neg (p, {\mathbf F})\wedge\neg (p, {\mathbf C}).$

All axioms of KEL still make sense for $(p, {\mathbf{T}}),$ except for (A3) since axiom (C) does not hold in MELC. We can keep (A5): indeed, (A5) in the extended KEL no longer translates into axiom (D) in the modal setting, as the definition of $(p, {\mathbf{T}})$ in terms of modalities is not the same as in KEL. Besides, (A4) accounts for both (N) and (P). Properties of label ${\mathbf{C}}$ should be separately defined in the extension of the KEL language. Namely, the following formulas should be taken as axioms for KEL-2:

• All KEL axioms but for (A3);

• $(p, {\mathbf{T}}) \to \neg (p, {\mathbf{C}})$ since the two epistemic values are mutually exclusive qualifiers. It implies, using (A4) and modus ponens, that $\neg (\top, {\mathbf{C}})$ holds (sources will be unanimous for tautologies).

• $(p, {\mathbf{C}})\equiv (\neg p, {\mathbf{C}}) ,$ to emphasize the stability of ${\mathbf{C}}$ with respect to negation. It implies $\neg (\bot, {\mathbf{C}})$ (sources will be unanimous for ever false propositions);

• A counterpart to axiom (3-C), replacing $\square p$ by $(p, {\mathbf{T}}) \vee (p, {\mathbf{C}}).$

The above proposed axioms also hold for ${\mathbf{U}},$ but for the counterpart of (3-C). The latter is the only axiom that distinguishes between ${\mathbf{C}}$ and ${\mathbf{U}},$ which reminds of the fact that both epistemic values play the same role with respect to ${\mathbf{T}}$ and ${\mathbf{F}}$ in Belnap truth tables.

In contrast, in MELC, the difference between ${\mathbf{C}}$ and ${\mathbf{U}}$ is more patent as they are characterized by distinct modal expressions.

The above setting enables Belnap logic (as per its truth-tables and motivating example) to be positioned with respect to modal logic, addressing a question we raised in Dubois (2008).

Like Kleene truth-tables can be partially internalized inside MEL, part of Belnap truth-tables can be justified in MELC when combining logically independent propositions (especially, independent literals). Noticeably, it is possible to account for the result of the conjunction of ${\mathbf{C}}$ and ${\mathbf{U}},$ that yields ${\mathbf{F}}$ in Belnap truth tables, using classical conjunction. To do it, one must derive $(p \wedge q, {\mathbf{F}})$ from $(p, {\mathbf{C}})$ and $(q, {\mathbf{U}}).$ In other words, in MELC, we must prove that if $p$ and $q$ are logically independent:

$$ \square p \wedge \square \neg p\wedge\lozenge q\wedge\lozenge \neg q\vdash_{MELC} \lozenge \neg(p\wedge q) \wedge\square \neg(p\wedge q). $$

This result is clear using (RM) and noticing that $\neg p \vdash \neg (p\wedge q)$ (axiom (RM) clearly works changing $\square$ into $\lozenge$).

Of course, this reasoning does not work if $p\models q$ or $q\models p$ (as then we could not have both $(p, {\mathbf{C}})$ and $(q, {\mathbf{U}})$ as premises since they become contradictory). If $p\models q,$ then suppose source 1 says $p$ is true and source 2 says it is false; then source 1 must say $q$ is true, hence $(q, {\mathbf{U}})$ is impossible. Likewise if $q\models p,$ suppose source 2 says $p$ is false; then it should say that $q$ is false too. Hence $(q, {\mathbf{U}})$ is again impossible. But other parts of the truth table cannot be retrieved using classical connectives inside modalities. For instance, we cannot derive $(p \wedge q, {\mathbf{T}})$ from $(p, {\mathbf{T}})$ and $(q, {\mathbf{T}})$ in KEL-2, since the adjunction property (C) does not hold in MELC.

However, like for Kleene logic, a translation of Belnap logic proper into MELC would again yield formulas where modalities are attached to literals only, as Belnap setting assumes that sources inform about atoms only. For instance, using Belnap conjunction, ${\mathbf t} (a \cap b) = {\mathbf T}$ writes $\square a\wedge \lozenge a \wedge \square b\wedge \lozenge b$ in MELC, not $\square (a\wedge b)\wedge \lozenge (a\wedge b).$ All Belnap truth-tables can be recovered in a trivial way, but internalizing the four-valued connectives down to the propositional logic inside MELC is generally not possible. This translation deserves a more careful study.

4.6 Connections with monotonic modal logics

The MELC logic is a non-regular modal logic. It is a fragment of a special case of the monotonic logic EMN (Chellas 1980), where modalities only apply to propositions, not to modal formulas. The basic axiom is:

$$ (\hbox{RE})\!\!:\square p \equiv \square q\quad\hbox{whenever} \vdash p \equiv q $$

common to all so-called classical modal logics. EMN is obtained by adding axioms (M) and (N) to (RE). (RE) is redundant with (RM), and (RM) is redundant with (M) in EMN. MELC thus comes down to adding axioms (P) and (3-C) to EMN.

Our proposed semantics is easily related to the so-called neighborhood semantics that accounts for EMN and various modal logics not satisfying axiom K. A so-called minimal model according to Chellas (1980) relies on a pair formed of a set $\Upomega$ of possible worlds that are propositional valuations, and a multimapping $\Upgamma$ from $\Upomega$ to $2^{2^{\Upomega}}.$ So, $\Upgamma(\omega)$ is a family of subsets of possible worlds. Just like in the case of MEL, we only need a constant $\Upgamma,$ such that $\Upgamma(\omega) = {\mathcal{N}}, \forall \omega \in \Upomega,$ because we do not consider nested modalities. A family of subsets ${\mathcal{N}}\subseteq 2^{\Upomega}$ is called a neighborhood. According to the neighborhood semantics, we can define satisfiability of elementary modal formulas as follows:

• ${\mathcal{N}} \models \square p$ if and only if $[p] \in {\mathcal{N}}$

• ${\mathcal{N}} \models \lozenge p$ if and only if $[\neg p] \not\in {\mathcal{N}}$

Chellas indicates that EMN is sound and complete with respect to this neighborhood semantics, provided that the involved subsets ${\mathcal{N}}$ are closed under inclusion and are not empty (hence contain $\Upomega$). Interestingly, it is easy to prove that, in the finite case:

Lemma 1

Any non-empty family ${\mathcal{N}}$ of subsets of a finite set $\Upomega$ that is closed under inclusion is a union of filters.

Proof

A filter is a non-empty family of subsets closed under inclusions and intersections. Now ${\mathcal{N}}$ has minimal elements under inclusion, and it contains them. Let $A \subseteq \Upomega$ be one of these minimal elements. If $A = \emptyset,$ then ${\mathcal{N}} = 2^{\Upomega}$ and this is the trivial improper filter. Now suppose $A \neq \emptyset.$ Then, $\forall B\subseteq \Upomega,$ if $A\subseteq B$ then $B \in {\mathcal{N}}.$ Hence ${\mathcal{N}}$ contains ${\mathcal{F}}(A) =\{B: A\subseteq B\}$ the filter with minimal element $A.$ Conversely, if $B \in {\mathcal{N}},$ $B$ contains at least one minimal element $A\in {\mathcal{N}},$ hence $B \in{\mathcal{F}}(A).$

Let $E_{1}, \ldots, E_{n}$ be the collection of minimal elements in the neighborhood ${\mathcal{N}},$ then ${\mathcal{N}} = \bigcup\nolimits_{i =1}^{n}{\mathcal{F}}(E_{i}),$ so that the $n$-tuple $(E_{1}, \ldots, E_{n})$ of sets entirely determines the neighborhood. When a non-empty neighborhood ${\mathcal{N}}$ is closed under inclusion and does not contain the empty set, it is called a proper filter.

Lemma 2

In the finite setting, the set of neighborhoods that are models of EMN without nesting and the axiom (P) are finite unions of proper filters.

Proof

Indeed, models ${\mathcal{N}}$ of EMN are not-empty [they contain $\Upomega$ due to (N)]. Axiom (P) is equivalent to requiring that $\emptyset \not \in {\mathcal{N}},$ i.e. ${\mathcal{N}}$ is not the trivial filter. Hence the filters ${\mathcal{F}}(E_{i})$ included in ${\mathcal{N}}$ are proper, and the sets $E_{i}$ are not empty.

For a monotonic modal logic on a finite propositional language, and a neighborhood that is the finite union of proper filters ${\mathcal{F}}(E_{i}),$

$$ [p] \in {\mathcal{N}} \neq \emptyset \quad\hbox{ if and only if } \exists i, E_{i} \subseteq [p] . $$

Suppose we interpret the inclusion $E_{i} \subseteq [p]$ as a modal formula $\square_{i} p,$ it is clear that if $\square$ is a modal operator of the EMN logic plus (P), $\square p$ can be expressed as the disjunction $\bigvee\nolimits_{i =1,n}\square_{i} p,$ for a sufficiently large value of $n$ ($n < 2^{|\Upomega|}$ in any case) where the $\square_{i}$’s are KD modalities.

Now the connection between the semantics of MELC and neighborhood semantics is clear: given the epistemic states of the two agents $E_{1}$ and $E_{2},$ the associated neighborhood is ${\mathcal{N}}_{12} = {\mathcal{F}}(E_{1}) \cup {\mathcal{F}}(E_{2})$ and we have

$$ (E_{1}, E_{2}) \models \square p \quad \iff \quad {\mathcal{N}}_{12} \models \square p. $$

$$ (E_{1}, E_{2}) \models \lozenge p \quad \iff \quad {\mathcal{N}}_{12} \models \lozenge p. $$

So, it is easy to position MELC with regard to the EMN monotonic modal logic: it is a fragment of EMN containing only modal formulas without nested modalities, and whose neighborhood semantics accounts for unions of two proper filters. The restriction to the union of two proper filters is captured by axiom (3-C).

Proposition 5

The set of neighborhoods that are models of MELC are of the form ${\mathcal{N}} = {\mathcal{F}}(E_{1})\cup {\mathcal{F}}(E_{2})$ for two non-empty subsets $E_{1}$ and $E_{2}$ of models of the underlying propositional language.

Proof

MELC is EML plus axioms (P) and (3-C). The set of neighborhoods that can serve as models of EML plus axiom (P) are of the form ${\mathcal{N}} = \bigcup\nolimits_{i =1}^{n}{\mathcal{F}}(E_{i}),$ for arbitrary $n$ and $E_{i} \neq \emptyset.$ Suppose ${\mathcal{N}}$ is a model of MELC, where $n > 2.$ Then it is possible to find three subsets $A_{1}, A_{2}, A_{3} \in {\mathcal{N}}$ such that none of $A_{i}\cap A_{j} \in {\mathcal{N}}, i\neq j.$ It suffices to choose $A_{i} = E_{i}, i = 1, 2, 3.$ Clearly if $p_{i}, i= 1, 2, 3$ are propositions such that $[p_{i}] = E_{i},$ axiom (3-C) is violated by these propositions, that is: ${\mathcal{N}} \not\models \square p_{1}\wedge \square p_{2}\wedge \square p_{3} \to \square (p_{1}\wedge p_{2})\vee\square (p_{2}\wedge p_{3})\vee\square (p_{1}\wedge p_{3}).$

The completeness of MELC is thus a consequence of the known completeness of EMN with respect to neighborhoods that are closed under inclusion and are not empty. Our additional axioms restrict these neighborhoods to be representable by the union of two proper filters that are induced by a pair of non-empty subsets of valuations. A detailed self-contained proof is left for further research.

4.7 Links with some modal probabilistic logics

A similar logic is also retrieved when modeling acceptance as high probability using a threshold: $\square p$ is then interpreted as $Prob(p) \geq \theta > 0.5{:}$ this is a logic of probably proposed by Hamblin (1959) and discussed by Walley and Fine (1979) in their survey. It is again a special case of monotonic modal logic EMN. It should not be too surprising, as the (C) axiom ensuring the possibility of deriving $\square (p\wedge q)$ from $\square p$ and $\square q$ clearly does not work with probabilities: $Prob(p) \geq \theta$ and $Prob(q) \geq \theta$ do not entail $Prob(p\wedge q) \geq \theta.$ But one can view frequentist probabilities as a matter of counting the pros and the cons, which comes close to the idea of handling testimonies from conflicting sources. However the logic of probably needs one axiom that is precisely not present in MELC:

$$ (\hbox{CONS-})\!\!: \;\vdash \neg (\square p \wedge \square\neg p) $$

This is a strengthening of axiom (CONS-3) which, added to MELC, forbids pairs of disjoint epistemic states $(E_{1}, E_{2}).$ It is actually equivalent to axiom (D). Note that the reason why it is not obtained from Belnap setting is that in the multiple source environment, Belnap truth values do not account for the number of sources supporting an atomic proposition. A proposition and its negation can be asserted as true by distinct sources, and that is enough to fail axiom (D). It would be different if the meaning of $\square p$ would be : $p$ is asserted by a majority of sources (also in that case we could not reduce the $n$-source problem to a 2-source one). In this sense, Belnap logic sounds like the poor man probability calculus (see also Dubois 2008).

This kind of modal probabilistic logic is also studied in details by Burgess (1969). But this author considers a modal logic where the modal probably is handled along with other more classical epistemic modalities, and the nesting of modal formulae is allowed. This concern is foreign to this paper. The logic of risky knowledge of Kyburg and Teng (2002) is a revival of Hamblin’s in connection with imprecise statistics and is again based on EMN.

5 Conclusion

When representing knowledge in a logical setting, it is important to separate truth values from epistemic values expressing a state of knowledge: the former are supposed to be compositional, the latter are not. It is recalled that Kleene logic comes down to defining connectives of a set-valued logic lifting the usual binary connectives to set-valued arguments. This lifting process loses Boolean properties on the way, just as interval arithmetic on the reals loses the group structure of addition and product. In this sense Kleene logic is to Boolean logic what interval-valued fuzzy sets are to fuzzy sets (Dubois 2010b). The logic of Belnap belongs to the same family as Kleene’s, augmenting it with an additional value for contradiction, and suffers from the same limitation, if built on top of classical logic.

This discussion paper suggests epistemic values representing ignorance and contradiction can be represented at the syntactic level, encapsulating propositional logic in another higher level logic. It allows to distinguish between the fact that propositions can just be true or false and the fact that their truth or falsity can be explicitly unknown, or even be a matter of conflicting opinions. This approach then comes close to some well-known modal logics, which is not surprizing. However, we preserve a very simple semantics of incomplete knowledge in terms of subsets of interpretations rather than genuine accessibility relations, because only a sub-language of modal logic where nesting is not allowed is needed.

The main results of the paper may be formulated as follows: Kleene truth values and truth-tables can be captured by a simple fragment of the modal logic KD where modalities only precede literals. Kleene logic is a poor man handling of incomplete propositional information, in the sense that it can model only a special form of incompleteness, namely knowledge about literals, and can properly address a limited number of queries. Belnap truth values and truth-tables can be captured by a special case of the EMN monotonic modal logic and Belnap setting stands as a qualitative form of the logic of the frequentist probable (where one does not count yet), with again a restriction to knowledge about literals.

This paper has no ambition to solve technical problems (like proof theory and its complexity) posed by such incomplete knowledge and contradiction logics. It is clear that much work is needed to figure out their potential in terms of reasoning power. Possible links with paraconsistent logics, possibilistic logic, logic programming and information fusion logics are worth investigating as well. Our framework seems to be the most elementary one for reasoning about Boolean information stemming from one or several sources, while being more expressive than Kleene or Belnap logics for the representation of incomplete information. Note that the construction proposed here for MEL and MELC could be iterated by encapsulating MEL or MELC inside a higher order modal logic (considering that the agent receiving information from sources forwards this information to another agent, Cholvy 2010). A similar iteration was already described within Belnap setting, leading to a 16-valued logic (Wansing and Belnap 2010).