Keywords

Mathematics Subject Classification (2000)

1 Introduction

The fusion of pieces of information coming from different sources and the handling of inconsistency have motivated works in logic [11, 2] as well as in artificial intelligence (see, e.g. [7]). The issues are then the appropriate representation of the information provided by each source, and the handling of conflicts between sources, and possibly inside sources. However, it is usually assumed that the information provided by each source is consistent. In the following short discussion, we allow for the inconsistency of information provided by individual sources in a propositional format, and show that it leads to interesting pending questions.

2 Background on the Handling of Possibly Inconsistent Propositional Knowledge Bases

By a knowledge base K here, we mean a finite set of propositional formulas \(K=\{\varphi_{i}\ |\ i=1,\ldots,m\}\). Then, given two knowledge bases K and \(K^{\prime}=\{\psi_{j}\ |\ j=1,\ldots,n\}\), one can define their conjunctive and disjunctive combinations, respectively, in a syntactic manner as

$$\begin{aligned}\displaystyle K\otimes K^{\prime}&\displaystyle=\{\varphi_{i}\wedge\psi_{j}\ |\ i=1,\ldots,m,\text{ and }j=1,\ldots,n\}\,,\\ \displaystyle K\oplus K^{\prime}&\displaystyle=\{\varphi_{i}\vee\psi_{j}\ |\ i=1,\ldots,m,\text{ and }j=1,\ldots,n\}\,.\end{aligned}$$

Note that \(K\otimes K\) and \(K\oplus K\) have the same semantic content as K. Moreover, \(K\otimes K^{\prime}\) has the same set of models (possibly empty) as the mere union \(K\cup K^{\prime}\) of K and \(K^{\prime}\). When K and \(K^{\prime}\) are consistent, but not \(K\otimes K^{\prime}\), classical inference from \(K\otimes K^{\prime}\), or \(K\cup K^{\prime}\), becomes trivial, and the disjunctive combination \(K\oplus K^{\prime}\) is of interest. It tacitly assumes that one source is right but we do not know which source [8]. This idea may be refined by considering the maximal consistent bases of \(K\cup K^{\prime}\) and then combining them disjunctively. Or yet it has been proposed for a long time to compute the intersection of the sets of consequences of each maximal consistent bases of \(K\cup K^{\prime}\) (it was first proposed by Rescher and Manor already in 1970 [12]). In that case, we are back to the problem of non-trivial inference from a single inconsistent knowledge base.

So consider the case when a single base K is inconsistent. Let \(S_{1},\ldots,S_{k}\) be the maximal consistent subbases of K, and let \(C(S)\) denote the deductive closure of a consistent propositional base S. It is easy to see that \(C(S_{1}\oplus\cdots\oplus S_{k})\subseteq C(S_{1})\ \cap\ \cdots\ \cap\ C(S_{k})\). Note that in order to obtain an equality instead of this inclusion, one should replace \(\oplus\) by a richer disjunction, where we not only perform disjunctions of the form \(\psi^{1}\vee\cdots\vee\psi^{k}\) with \(\psi^{i}\in S_{i}\) for \(i=1,\ldots,k\), but also all the disjunctions of this kind where now \(\psi^{i}\) is any conjunction \(\psi^{i}_{1}\wedge\cdots\wedge\psi^{i}_{j}\) of propositions taken in S i (where j ranges between 1 and \(\mathrm{card}(S_{i})\)).

Several other approaches exist to obviate the explosive nature of classical inference.

In [4, 5], it has been proposed to associate an inconsistent propositional logic base \(K=\{\varphi_{i}\ |\ i=1,\ldots,m\}\) with its so-called paraconsistent completion K o, defined as \(K^{o}=\{(\varphi_{i},1,x_{i})\ |\ i=1,\ldots,m\}\) where \(x_{i}=1\) if \(\exists A\leavevmode\nobreak\ \subseteq K,A\leavevmode\nobreak\ \text{ consistent},A\leavevmode\nobreak\ \vdash\neg\varphi_{i}\), and where \(x_{i}=0\) otherwise.

This method partitions K o into the inconsistency-free part \(K_{\text{fr}}^{o}\) and the paraconsistent part \(K_{\text{par}}^{o}\) of K o, respectively, defined by

$$\begin{aligned}\displaystyle K_{\text{fr}}^{o}&\displaystyle=\{\varphi_{i}\ |\ (\varphi_{i},1,0)\in K^{o},i=1,\ldots,m\}\\ \displaystyle K_{\text{par}}^{o}&\displaystyle=\{\varphi_{i}\ |\ (\varphi_{i},1,1)\in K^{o},i=1,\ldots,m\}\,.\end{aligned}$$

However, reducing K to \(K_{\text{fr}}^{o}\), which is consistent, is quite conservative, since while every consequence from \(K_{\text{fr}}^{o}\) is also a consequence of all maximal consistent subbases of K, the converse is false, as shown by the following counter-example [4]:

Example 25.2.1

Let \(K=\{\alpha,\neg\alpha\vee\neg\beta,\beta,\neg\alpha\vee\gamma,\neg\beta\vee\gamma\}\). Then it can be verified that

  • K has three maximal consistent subbases \(\{\neg\alpha\vee\neg\beta,\beta,\neg\alpha\vee\gamma,\neg\beta\vee\gamma\}\), \(\{\alpha,\beta,\neg\alpha\vee\gamma,\neg\beta\vee\gamma\}\), \(\{\alpha,\neg\alpha\vee\neg\beta,\neg\alpha\vee\gamma,\neg\beta\vee\gamma\}\);

  • \(K_{\text{fr}}^{o}=\{\neg\alpha\vee\gamma,\neg\beta\vee\gamma\}\) is the intersection of these three bases (this is always true);

  • \(K_{\text{fr}}^{o}\) does not entail γ;

  • γ is entailed by each maximal consistent subbase of K.

Besides, the ‘‘paraconsistent completion’’ can be extended to layered knowledge bases in the setting of possibilistic logic [5, 9], taking into account the levels of certainty of the pieces of information.

A bolder inference mechanism that produces a set of consequences larger than \(C(S_{1})\cap\cdots\cap C(S_{k})\) is provided by the so-called argued inference, which is defined as follows: ψ is an argued consequence of a (possibly inconsistent) base K if there is a consistent subset of K that entails ψ and none that entails \(\neg\psi\). A set of two argued consequences is always consistent, but it is no longer the case for larger sets of argued consequences [4]. This contrasts with the fact that \(C(S_{1})\cap\cdots\cap C(S_{k})\) is clearly consistent.

These approaches can be encompassed by extending the paraconsistent completion \(\mathcal{L}^{o}\) to the whole language \(\mathcal{L}\) of K, in the spirit of the proposal by Arieli [1]: \(\forall\phi\in\mathcal{L}\):

  • \(\phi\in\mathcal{L}_{T}\) if and only if there is a consistent subset of K that entails ϕ and none that entails \(\neg\phi\); and we can write \((\phi,1,0)\in\mathcal{L}^{o}\).

  • \(\phi\in\mathcal{L}_{F}\) if and only if there is a consistent subset of K that entails \(\neg\phi\) and none that entails ϕ; and we can write \((\phi,0,1)\in\mathcal{L}^{o}\).

  • \(\phi\in\mathcal{L}_{U}\) if and only if there is no consistent subset of K that entails ϕ nor any that entails \(\neg\phi\); and we can write \((\phi,0,0)\in\mathcal{L}^{o}\).

  • \(\phi\in\mathcal{L}_{I}\) if and only if there is a consistent subset of K that entails ϕ and another one that entails \(\neg\phi\); and we can write \((\phi,1,1)\in\mathcal{L}^{o}\).

In the above definition, one can restrict to maximal consistent subbases of K. These four sets of formulas \(\mathcal{L}_{T},\mathcal{L}_{F},\mathcal{L}_{U},\mathcal{L}_{I}\) partition the language. It can be checked that \(K^{o}\subset\mathcal{L}^{o}\) (in particular, \(K_{\text{fr}}^{o}\subset\mathcal{L}_{T}^{o}\) and \(K^{o}_{\text{par}}\subset\mathcal{L}^{o}_{I}\)), and that \(\mathcal{L}_{T}\) is the set of argued consequences. One can view the four annotations by pairs of Boolean values as akin to Belnap [2] epistemic truth-values, TRUE, FALSE, NONE, and BOTH, respectively. However, Belnap logic comes down to computing epistemic statuses of atomic propositions based on information from various sources, then obtaining the epistemic status of other formulas via truth-tables extending the usual ones to four values.

The paraconsistent completion and its extension also stem from possibilistic logic [9], since it comes down to computing degrees of necessity \(N_{i}(\phi)\), and \(N_{i}(\neg\phi)\) whereby \(N_{i}(\phi)=1\) if and only if \(S_{i}\vdash\phi\); otherwise \(N_{i}(\phi)=0\). Necessity measures N i are \(\wedge\)-decomposable functions (\(N_{i}(\phi\wedge\psi)=\min(N_{i}(\phi),N_{i}(\psi))\)) akin to KD modalities. The extended paraconsistent completion can be formally defined as

$$\displaystyle\mathcal{L}^{o}=\left\{\left(\phi,\max_{i=1}^{k}N_{i}(\phi),\max_{i=1}^{k}N_{i}(\neg\phi)\right):\phi\in\mathcal{L}\right\}\,.$$

Note that \(\max_{i=1}^{k}N_{i}\) is just a general monotonic Boolean set-function (and conversely any such set function is of this form for some integer k), and the annotated formulas can be encoded in a non-regular modal logic [10].

It is easy to see that for the cautious approach using intersection, it holds that \(C(S_{1})\ \cap\ \cdots\ \cap\ C(S_{k})=\{\phi:\min_{i=1}^{k}N_{i}(\phi)=1\}\). The companion completion of \(\mathcal{L}^{o}\) of the form \(\mathcal{L}^{\text{cautious}}=\{(\phi,\min_{i=1}^{k}N_{i}(\phi),\min_{i=1}^{k}N_{i}(\neg\phi)):\phi\in\mathcal{L}\}\) only contains triples of the form \((\phi,1,0),(\phi,0,1),(\phi,0,0)\), with \((\phi,1,0)\in\mathcal{L}^{\text{cautious}}\) if and only if \((\neg\phi,0,1)\in\mathcal{L}^{\text{cautious}}\). The set \(\mathcal{L}_{T}^{\text{cautious}}=\{\phi:(\phi,1,0)\in\mathcal{L}^{\text{cautious}}\}\) is consistent, deductively closed, and equal to \(C(S_{1})\ \cap\ \cdots\ \cap\ C(S_{k})\). Indeed, \(\min_{i=1}^{k}N_{i}\) is again a necessity measure.

3 Toward Fusing Inconsistent Knowledge Bases

In this section, we turn to the case when the source bases are already inconsistent.

3.1 A Misleadingly Simple Problem

Let us consider the simple case of the fusion of the two atomic knowledge bases \(K=\{p,\neg q,q\}\) and \(K^{\prime}=\{p,\neg p,q\}\). There are at least four ways of envisaging their fusion:

  • A first idea is to merely perform the set-union \(K\cup K^{\prime}=\{p,\neg p,q,\neg q\}\); we get a state of contradiction both about p and about q, which is not appealing, as one may feel that some information has been lost in the process (the same result would obtain by merging \(\{p,\neg p\}\) and \(\{q,\neg q\}\)).

  • However, we can observe that all the maximal consistent subbases of K (resp. \(K^{\prime}\)) entail p (resp. q). So if we apply an inconsistency-tolerant inference to each of K and \(K^{\prime}\) prior to merging, we may feel to be entitled to derive \(p\land q\) in the end.

  • Alternatively, consider \(K\oplus K^{\prime}=\{p,p\vee\neg p,p\vee q,p\vee\neg q,\neg p\vee\neg q,\neg q\vee q,\neg p\vee q,q\}\). It may be reduced to \((K\oplus K^{\prime})^{d}=\{p,\neg p\vee\neg q,q\}\) if we delete each formula which is subsumed by another one. Although \((K\oplus K^{\prime})^{d}\) is inconsistent, it is syntactically different from \(K\cup K^{\prime}\), and now all consistent subbases of \((K\oplus K^{\prime})^{d}\) only entail \(p\vee q\).

  • Finally, note that p (resp. q) is inconsistency-free in K (resp. \(K^{\prime}\)). This may suggest to view K as a tentative representation of a situation where the associated source asserts p, and states that it has contradictory information about q, in the sense that \((q,1,1)\in K_{\text{par}}^{o}\), which we shall denote by \(\bot_{q}\). Similarly, \(K^{\prime}\) corresponds to a situation where the associated source asserts q, and states that it has contradictory information about p, namely \(\bot_{p}\). It may be considered reasonable to assume that \(p\vee\bot_{p}=p\) (since \(p\vee(\neg p\wedge p)=p\), and it agrees with the truth-table of disjunction for Belnap logic), we get

    $$\displaystyle\{p,\bot_{q}\}\oplus\{q,\bot_{p}\}=\{p,q,p\vee q,\bot_{p}\vee\bot_{q}\}\,,$$

    which may be reduced to \(\{p,q,\bot_{p}\vee\bot_{q}\}\). It expresses that p and q can be asserted, and that we have contradictory information about p or about q.

The latter approach that uses a reification of local inconsistencies does not sound counterintuitive; it is just an optimistic way of fusing the information coming from the two sources stating, respectively, that p is true and information about q is conflicting (paraconsistent) and that q is true and information about p is conflicting. It is less pessimistic than the second approach which throws away much information to restore consistency of source information prior to merging.

The basic elements of the calculus implicitly underlying this latter view may be nicely pictured on Fig. 25.1, where three squares in solid lines (which are not squares of opposition, at least in the classical sense) are displayed. The middle of the side of a square is always the conjunct of its edges, and the vertices of the isosceles triangles are the disjunction of the edges of their opposite side.

Fig. 25.1
figure 1

Conjunctions and disjunctions in squares

Full size image

3.2 Elements for a Discussion

Two basic issues, in order to make sense of the problem from an artificial intelligence point of view, are certainly (i) to have a proper representation of what has to be fused (which requires a clear understanding of what is supposed to be stated); and (ii) to lay bare what are the principles underlying the merging process or the conjoint exploitation of the knowledge bases reflecting the sources of information.

As it may be expected, one observes that if information is modeled by an inconsistent set of atomic formulas, one may be in one of the four states of information p, \(\neg p\), \(\bot_{p}\), and \(\top_{p}\) regarding a propositional variable p. Here the symbol \(\top_{p}\) would encode a local tautology \(p\lor\neg p\) in a symmetric way as does \(\bot_{p}\) for the contradiction. One may then be tempted to complete the three squares by vertices of the form \(\top_{p}\lor q\), etc. (see the external square in dotted lines). But it is hard to defend the idea that \((\top_{p}\lor q)\land(\top_{q}\lor p)=p\lor q\), as, strictly speaking, it is just a tautology. However, just as the inconsistency-tolerant approaches try to confine the contradiction to a local feature not destroying knowledge bases, one could similarly, as a topic of further thought, try to have a local approach to tautologies that would avoid the opposite form of trivialization (nothing follows from a tautology).

The possibility of defining four statuses for formulas with respect to an inconsistent knowledge base may suggest to try either a multiple-valued logic approach (as in [2]), or a modal logic approach (as in [3]), or an argumentative approach (as in [1]).

The multiple-valued logic view may be considered misleading as one may argue that truth-tables are a clumsy way of handling states of information attached to atomic formulas [6]. In fact, the symbol p in the above attempt is ambiguous when put along with \(\bot_{p}\), as writing p in the knowledge base here refers to the fact of consistently asserting p, without its being contradicted by other assertions: in the annotation framework outlined in the previous section, it really stands for \((p,1,0)\), while \(\bot_{p}\) stands for \((p,1,1)\).

If we understand the four states of formulas induced by an inconsistent knowledge base K as encoded by the paraconsistent completion of the language, we see that it may lead us to questioning the edges of the second inner square (even though they look safe), namely we can doubt whether, in an inconsistent framework, the conjunction of p and q is \(p\wedge q\) at all. Indeed if instead of p, \(\neg p\), \(\bot_{p}\), and \(\top_{p}\), we write \((p,1,0)\), \((p,0,1)\), \((p,1,1)\), and \((p,0,0)\in\mathcal{L}^{o}\), then it is easy to check that \((p,1,0)\in\mathcal{L}^{o},(q,1,0)\in\mathcal{L}^{o}\) do not imply \((p\land q,1,0)\in\mathcal{L}^{o}\), if we work with an inconsistent knowledge base [6]. This is consistent with the fact that the modal approach to capacities [10], set-functions that provide a general approach to uncertainty, is not regular (axioms K and D do not hold). This is as well at odds with Belnap logic, which assumes that the four-valued logic truth-tables extend the ones of Boolean logic. So the proposed set of squares should not be taken for granted under all approaches to inconsistency.

4 Conclusion

The aim of the above discussion (tentative) is only to draw attention on basic difficulties in the problem of handling, and more particularly fusing and inferring from propositional bases in the presence of inconsistency, whereby the syntactic framework of propositional logic seems to be ambiguous and insufficient to express what is going on.

Clearly, even if many works have been published on inconsistency and what to do with it, a number of questions remain, and one of the ambitions of this note is to make preliminary steps in the way to a general picture, relating some natural attempts. The only other purpose is to seize the occasion of this Festschrift for Jean-Yves Béziau to heartily wish him a happy birthday.