Logical Foundations of Evidential Reasoning with Contradictory Information

Abstract

Inconsistent or contradictory information is quite common in modern information technology such as the Web or unstructured databases. In this paper, we employ two levels of epistemic logics to provide logical foundations for evidential reasoning with this kind of information. The first-level logic is the well-known Belnap–Dunn four-valued logic. This logic provides a formalism for reasoning about both incomplete and contradictory information. In addition to the two standard Boolean truth values T and F, there are two new values: N and B. They are used to designate incomplete and contradictory information, respectively. The four-valued logic is externally epistemic in the sense that the truth values are intended to reflect what the agents may have been informed about and are passed over to the agents from the external environment. By using the semantics for this logic, we enrich Carnap’s universe for consistent information by replacing standard possible worlds with states, set-ups or situations where a proposition may be both true and false. We shall call such a universe a Belnap–Dunn universe. The second-level logic is epistemic logic S5. When the information is uncertain and imprecise, it usually fails to provide probability values for every subset of the Belnap–Dunn universe. Probabilities are defined only on those subsets which are known with certainty. We employ epistemic logic S5 to distinguish those known subsets and to characterize the notion that such known part of the information improves our knowledge by reducing the scope of possible valid states. S5 is internally epistemic in the sense that the knowledge is determined by the agents. Probabilistic reasoning with the combination of the four-valued logic and epistemic logic S5 is nothing but evidential reasoning over bilattices or de Morgan lattices.

Appendix A: Duality Theorem of de Morgan Lattices

In this part, we show that any finite de Morgan lattice can be represented as the concrete lattice of order ideals in some poset with an order-reversing involution and there is a one-to-one correspondence between de Morgan lattices and posets with order-reversing involutions. The following propositions are based on similar results in Białynicki-Birula and Rasiowa (1957), Dunn (1986), Urquhart (1979), Priestley (1970). Białynicki-Birula and Rasiowa (1957) and Dunn (1986) did not give a whole duality theory for de Morgan lattices; rather they proved representation theorems. Urquhart (1979) provided a duality theory for distributive lattices with a dual homomorphism operator instead for de Morgan lattices, which are distributive lattices with a dual homomorphism operator that is additionally an involution. Priestley (1970) presented a duality theory for distributive lattices by means of ordered Stone spaces, which is quite different from the form that we need to show the main theorems in this paper. So, according to our knowledge, our presentation of the duality theorem for finite de Morgan lattices here, which combines different techniques from the above mentioned papers, is the first one to represent de Morgan lattices in the same way as in Birkhoff (1967) and Stanley (1997) for distributive lattices. In this sense, this part of our paper is of independent interest.

Let $(P,\le ,g)$ be a poset with an order-reversing involution g, i.e., g is a function from P to P satisfying the following conditions: for any x and y in P,

• 1. $x\le y$   implies   $g(y)\le g(x)$;

• 2. $g(g(x))=x$.

It is easy to see that g is also one-to-one. J(P) is defined to be the lattice of order ideals in P with the usual set operations $\cap$ and $\cup$. It is easy to check that J(P) is a distributive lattice. According to g, we define ${\sim }$ as follows:

$${\sim }I:=P\setminus g(I)\,\,\text {for any order ideal}\,\, I\in J(P).$$

It is easy to check that ${\sim }I$ is also an order ideal in J(P). So ${\sim }$ is a unary operation on J(P). We further show that J(P) with this unary operation ${\sim }$ is a de Morgan lattice.

Theorem A.1

The above defined J(P) with the unary operation ${\sim }$ is a de Morgan lattice.

Proof

It suffices to show that g is an order-reversing involution on the set of order ideals of P.

• 1. First we show that it is order-reversing. Assume that $I_1\subseteq I_2$ and $x\in {\sim }I_2$. It follows that $g(x)\notin I_2$ and hence $g(x) \notin I_1$. So we have that $I_1\subseteq I_2$ implies ${\sim }I_2\subseteq {\sim }I_1$.

• 2. Next we show that ${\sim }$ is an involution by the following chain of equivalences.

  $$x\!\in \!{\sim }{\sim }I\;\!\Leftrightarrow \!\;\!x\!\in \!P\setminus g(P\setminus g(I))\;\!\Leftrightarrow \!\; \!g(x)\notin P\setminus g(I)\;\!\Leftrightarrow \!\;\!g(x)\!\in \!g(I)\;\!\Leftrightarrow \!\;\!x\!\in \!I$$

  So $I={\sim }{\sim }I$ for any order ideal in J(P). $\square$

Next we show the converse to the above theorem: any de Morgan lattice can be represented as the lattice of order ideals in some poset with an order-reversing involution. Given a de Morgan lattice $(D,\wedge ,\vee ,{\sim })$, $P_D$ is defined as the sub-poset of join-irreducibles in D. In addition, we define, for any $a\in P_D$,

$$g(a)=\bigwedge \{\,x\in D:x\in D\setminus {\sim }[a)\,\},\,\, \text {where}\,\,{\sim }[a)=\{\,{\sim }x:x\in [a)\,\}$$

We won’t distinguish the unary operation on D and the derived unary operation on $P_D$. The context will decide which we use. Similarly we have used the same notation $\sim$ for the unary operation on distributive lattices D and for the derived unary operation on J(P).

Proposition A.2

Let L be a finite distributive lattice. There is a one-to-one correspondence between join-irreducibles and prime filters in L in the following sense:

• 1. for any join-irreducible a in L, [a) is a prime filter;

• 2. for any prime filter F, $\bigwedge F$ is a join-irreducible in L.

Proof

For the first part, assume that a is join-irreducible in L and $a\le b \vee c$. It follows that $a\le b$ or $a\le c$. For the second part, assume that F is a prime filter and $a_F:=\bigwedge F=b\vee c$. It follows that $b\le a$ and $c\le a$ and $b\vee c\in F$. Since F is a prime filter, $b\in F$ or $c\in F$, i.e., $a_F\le b$ or $a_F\le c$. So $a_F = b$ or $a_F = c$. That is to say, $a_F$ is join-irreducible. $\square$

Lemma A.3

For any join-irreducible $a\in P_D$, $g(a)\in P_D$, i.e., g(a) is also join-irreducible.

Proof

Let a be join-irreducible in D. Assume that $g(a)=b\vee c$. We need to show that $g(a)=b$ or $g(a)=c$. Since a is join-irreducible in D. [a) is a prime filter in D. We can further show that $D\setminus {\sim }[a)$ is also a prime filter. So $g(a)=\bigwedge \{\,x\in D:x\in D\setminus {\sim }[a)\,\}$ is a join-irreducible element in D. $\square$

So the above defined g is a unary operation on $P_D$.

Theorem A.4

g is an order-reversing involution on $P_D$.

Proof

First we show that g is order-reversing. Let a and b be two join-irreducibles in $P_D$ such that $a\le b$. The next series of implications holds.

$$a\le b\;\!\Rightarrow \!\;[b)\!\subseteq [a)\;\!\Rightarrow \;\!{\sim }[b)\!\subseteq \!{\sim }[a) \;\!\Rightarrow \!\; D\setminus {\sim }[a)\subseteq D\setminus {\sim }[b)\;\Rightarrow \; g(b)\le g(a)$$

Next we show that g is an involution. It suffices to show, by the following equivalences, that for any $a\in P_D$, $[a)=D\setminus {\sim }[g(a))$.

$$\begin{aligned}&x\in [a)\;\Leftrightarrow \;{\sim }x\in {\sim }[a)\;\Leftrightarrow \;{\sim }x\notin D \setminus {\sim }[a)\;\Leftrightarrow \;g(a)\nleq {\sim }x\;\Leftrightarrow \;\\&\qquad \qquad \qquad \qquad {\sim }x\notin [g(a))\;\Leftrightarrow \;x\notin {\sim }[g(a)) \;\Leftrightarrow \; x\in D\setminus {\sim }[g(a))\quad \square \end{aligned}$$

Theorem A.5

Let P be a poset with an order-reversing involution g. Then P is isomorphic to the sub-poset $P_{J(P)}$ of join-irreducibles in J(P) which is the lattice of order ideals in P.

Proof

Let P be a poset with an order-reversing involution g. A function $h:P\rightarrow J(P)$ is defined as follows:

$$h(a)=(a]\,\,\text {for any}\,\, a\in P.$$

First we show that h is actually a function from P to $P_{J(P)}$, i.e., h(a) is join-irreducible in J(P) for any $a\in P$. Assume that $a\in P$ and $(a]=I_1\cup I_2$, where $I_1\in J(P)$ and $I_2\in J(P)$. It follows that $a\in I_1$ or $a\in I_2$. Either case implies that $I_1=(a]$ or $I_2= (a]$. So indeed h(a) is join-irreducible in J(P).

Next we show that h is one-to-one between P and $P_{J(P)}$. From the above, we only need to show that h is onto. Assume that $I\in P_{J(P)}$, i.e., I is join-irreducible in J(P). Now we need to show that I is actually a principal order ideal in P. We prove this by contraposition. Suppose that I is not a principal order ideal in P. Let $I_{max}=\{\,x\in I\!:\!x\! \,\;\mathrm{is\,maximal\,in}\, I\! \,\;\mathrm{in\,the\,sense\,that\,there\,are\,no\,other\,elements}\, y \,\mathrm{in}\, I\! \,\;\mathrm{such\,that}\, y\!\ge \! x\,\}$. It follows that $|I_{max}|\ge 2$. So $I_{max}=M_1\cup M_2$ for some non-empty subsets $M_1$ and $M_2$. We define:

$$I_1\!=\!\{\,x\!\in I:\!x\le y\text { for some }y\!\in M_1\,\},\qquad I_2=\{\,x\in I:x\le y\text { for some }y\in M_2\,\}.$$

It is easy to check that $I=I_1\cup I_2$ but $I_1\ne I$ and $I\ne I_2$. So I is not join-irreducible in J(P).

It remains to show that h preserves the order and the operation g. It is easy to see that it does for the order. Now we show that it preserves g. For any $a\in P$,

$$\begin{aligned} g(h(a))&=x\in \bigcap \{\,I\in J(P):I\in J(P)\setminus {\sim }[h(a)) \,\}\nonumber \\&=\bigcap \{\,I\in J(P):I\in J(P)\setminus {\sim }\{\,I\in J(P):a\in I\,\}\}\nonumber \\&=\bigcap \{\,I\in J(P):I\in J(P)\setminus \{\,P\setminus g(I):I\in J(P),a\in I\,\}\,\}\nonumber \\&=\bigcap \{\,I\in J(P):I\in J(P)\setminus \{\,J:a\in g(P\setminus J)\,\}\,\}\nonumber \\&=\bigcap \{\,I\in J(P):a\notin g(P\setminus I)\,\}\nonumber \\&=\bigcap \{\,I\in J(P):g(a)\notin P\setminus I\,\}\nonumber \\&=\bigcap \{\,I\in J(P):g(a)\in I\,\}\nonumber \\&=(g(a)]\nonumber \end{aligned}$$

That is to say, $h(g(a))=g(h(a))$. $\square$

Theorem A.6

Any finite de Morgan lattice D can be represented as the lattice $J(P_D)$ of order ideals in the sub-poset $P_D$ of join-irreducibles with an order-reversing involution g.

Proof

Let D be a finite de Morgan lattice and $P_D$ be its sub-poset of join-irreducibles with the order-reversing involution g. Now we need to show that D is isomorphic to the concrete de Morgan lattice $J(P_D)$. Define $h:D\rightarrow J(P_D)$ as $h(x)=\{\,y\in P_D:y\le x\,\}$ for any $x\in D$. From the proof of Theorem 3.4.1 in Stanley (1997), we only need to show that h preserves negation. In order to prove this, it suffices to show that, for any $a\in D$, $h({\sim }x)=P_D\setminus g(h(a))$. For any $x\in P_D$,

$$\begin{aligned}&x\in h({\sim }a)\;\Leftrightarrow \;x\le {\sim }a\; \Leftrightarrow \;{\sim }a\in [x) \;\Leftrightarrow \;a\in {\sim }[x) \;\Leftrightarrow \;a\notin D\setminus {\sim }[x) \;\Leftrightarrow \;\\&\qquad g(x)\!\nleq \!a \;\!\Leftrightarrow \;\!g(x)\!\notin h(a) \;\!\Leftrightarrow \;x\!\notin g(h(a)) \;\!\Leftrightarrow \;x\!\in \!P\setminus g(h(a)) \;\!\Leftrightarrow \;x\!\in \!{\sim }h(a) \end{aligned}$$

Note that the ${\sim }$ in the last line is the unary operation on $J(P_D)$. $\square$

Corollary A.7

There is a one-to-one correspondence between the class of de Morgan lattices and that of posets with order-reversing involutions.

Proof

This proposition follows from the above two theorems. This kind of correspondence is illustrated in the following diagram:

$\square$