What Is a Bilattice? Belnap-Dunn Logic and the Two Orders

What Is a Bilattice? Belnap-Dunn Logic and the Two Orders

A bilattice is a set equipped with two lattice orders: one ranks elements by how true they are, the other by how much information they carry. Its smallest nontrivial example, FOUR, has the values neither, true only, false only and both, and it is the algebra behind Belnap-Dunn four-valued logic. The bilattice explains why "both true and false" can be a legitimate state of a database: it is the top of the information order, not the top of the truth order.

This article takes the algebraic angle. For the logic itself (connectives, consequence, caveats, open problems) see Belnap four-valued logic.

What is a bilattice?

A lattice is a partially ordered set in which every two elements have a greatest lower bound (meet) and a least upper bound (join). A bilattice is one set with two such orders, a truth order $\leq_t$ and a knowledge order $\leq_k$, each with its own meet and join. Matthew Ginsberg introduced the structure for artificial intelligence (Ginsberg 1986; Ginsberg 1988)¹¹ Matthew L. Ginsberg. Multi-valued logics. AAAI Press, 1986.²² Matthew L. Ginsberg. "Multivalued logics: a uniform approach to reasoning in artificial intelligence." Computational Intelligence 4, no. 3 (1988): 265-316., where default reasoning, truth maintenance and theorem proving all need to separate "more true" from "more informed". Melvin Fitting developed it for logic programming (Fitting 1991)³³ Melvin Fitting. "Bilattices and the semantics of logic programming." Journal of Logic Programming 11, no. 1-2 (1991): 91-116..

The operations are conventionally named:

In a bilattice a truth value is not a point on a line from false to true. It can encode evidence for and evidence against a sentence, and the two can vary independently.

What is the four-element bilattice FOUR?

Take the two classical markers $\mathsf{T}$ and $\mathsf{F}$ and form the four subsets of $\{\mathsf{T},\mathsf{F}\}$:

The knowledge order is subset inclusion, so $x \leq_k y$ iff $x \subseteq y$. The truth order says $x\leq_t y$ iff ($\mathsf{T}\in x$ implies $\mathsf{T}\in y$) and ($\mathsf{F}\in y$ implies $\mathsf{F}\in x$): more truth support and less falsity support. Hence $\mathbf{f}$ is least and $\mathbf{t}$ greatest in truth, while $\bot$ and $\top$ are incomparable middles. In knowledge, $\bot$ is least, $\top$ greatest, and $\mathbf{t}$, $\mathbf{f}$ are incomparable.

This is the central bilattice insight: one can be more informed without being truer.

Negation swaps $\mathbf{t}$ and $\mathbf{f}$ and fixes $\bot$ and $\top$. The knowledge operations give

$$\mathbf{t}\oplus\mathbf{f}=\top, \qquad \mathbf{t}\otimes\mathbf{f}=\bot.$$

If one source says true and another says false, pooling everything yields "both"; the consensus common to the two reports is no shared information. These are two different, deliberately separable policies.

The pair (positive, negative) view

FOUR is also the set of pairs $(a,b)\in\{0,1\}^2$, with $a$ recording positive evidence and $b$ negative: $\bot=(0,0)$, $\mathbf{t}=(1,0)$, $\mathbf{f}=(0,1)$, $\top=(1,1)$. This is the twist product $\mathbf{2}\otimes\mathbf{2}$, a construction Kalman introduced for lattices with involution (Kalman 1958)⁴⁴ J. A. Kalman. "Lattices with involution." Transactions of the American Mathematical Society 87, no. 2 (1958): 485-491. and Fitting extended to bilattices (Fitting 1991)⁵⁵ Melvin Fitting. "Bilattices and the semantics of logic programming." Journal of Logic Programming 11, no. 1-2 (1991): 91-116.. The pair representation is what lets the same construction be run over lattices larger than $\{0,1\}$, giving bilattices that track degrees of evidence. In the working notes behind this article, a representation result attributed to Avron states that bounded interlaced bilattices (those whose operations are monotone in both orders) arise as twist products of this kind; this article does not reprove it.

Why is "both true and false" not an error?

The value $\top$ is an informational state rather than an error, for five reasons.

1. It has a precise meaning. $\top=\{\mathsf{T},\mathsf{F}\}$ records that both truth and falsity have been supplied.
2. It is structurally regular. Negation, conjunction, disjunction, consensus and accumulation are all defined on it, with the same laws as for the other values.
3. It is epistemic. In Belnap's reading the values describe what a system has been told (Belnap 1977)⁶⁶ Nuel D. Belnap. "A useful four-valued logic." In Modern Uses of Multiple-Valued Logic, ed. J. Michael Dunn and George Epstein, 5-37, D. Reidel, 1977.. Dunn's relational semantics (Dunn 1976; Dunn 2019)⁷⁷ J. Michael Dunn. "Intuitive semantics for first-degree entailments and 'coupled trees'." Philosophical Studies 29, no. 3 (1976): 149-168.⁸⁸ J. Michael Dunn. "Two, three, four, infinity: the path to the four-valued logic and beyond." In New Essays on Belnap-Dunn Logic, ed. Hitoshi Omori and Heinrich Wansing, 77-97, Springer, 2019. likewise models contradictory suppositions or assertions, not necessarily contradictions in the world. Dunn explicitly warns against reading the semantics as claiming that some sentence is really both true and false.
4. It is paraconsistent. $\top$ is designated (it counts as truth-supporting), yet it does not make every formula designated. Take $v(p)=\top$ and $v(q)=\mathbf{f}$: then $v(p\wedge\neg p)=\top$ is designated and $v(q)$ is not, so $p\wedge\neg p\not\models q$. Explosion fails and the conflict is stored locally.
5. It preserves diagnostic information. Treating $\top$ as an error would erase the fact that two evidential streams disagree. As a value, it lets the system answer, inspect, revise or defer while keeping the conflict as data.

The name matters here. Because $\top$ is the top of the knowledge order, calling it "maximally true" is a category mistake; it is maximally informed in the specific sense of containing both a positive and a negative report.

What does Dunn's relational semantics add?

Dunn replaced the classical valuation function with a relation between sentences and the markers $\mathsf{T}$ and $\mathsf{F}$; equivalently each sentence $A$ receives a set $V^*(A)\subseteq\{\mathsf{T},\mathsf{F}\}$. The clauses are two-sided:

$$\mathsf{T}\in V^(\neg A)\iff\mathsf{F}\in V^(A),\qquad \mathsf{F}\in V^(\neg A)\iff\mathsf{T}\in V^(A),$$

$$\mathsf{T}\in V^(A\wedge B)\iff \mathsf{T}\in V^(A)\text{ and }\mathsf{T}\in V^*(B),$$

$$\mathsf{F}\in V^(A\wedge B)\iff \mathsf{F}\in V^(A)\text{ or }\mathsf{F}\in V^*(B),$$

with dual clauses for disjunction. Truth conditions and falsity conditions are tracked independently. The four-valued algebra above is exactly what results.

How do bilattices help with logic programming?

Fitting's observation is a division of labour between the two orders. The connectives $\wedge$, $\vee$, $\neg$ evaluate formulas according to the truth order. Fixed-point semantics for programs, by contrast, can be taken in the knowledge order, where the least fixed point is the interpretation containing no extraneous information.

A computation can therefore start at $\bot$, add positive information, add negative information, and, if both arrive for the same atom, reach $\top$. Arriving at $\top$ means the program has acquired conflicting reports; it does not mean the semantic machinery has broken. Truth operations evaluate; knowledge operations govern informational growth.

Where else does this structure matter?

Ginsberg's motivation was inference systems that need to compare how true a sentence is against how well informed the system is. The same split recurs in the 561 Group's research on predication over bilattice-valued fibers, where fibers of subject-predicate-object assertions carry FOUR-valued charges, and in paraconsistent settling, where closure runs in the knowledge order. Those pages build on, and do not replace, the standard bilattice theory sketched here.

Limits and open problems

• Scope of the claim. This is a memorandum-level synthesis of Belnap, Dunn, Ginsberg and Fitting. It states the orders, operations and the five-part argument; it contains no new theorem.
• Epistemic, not metaphysical. The argument that $\top$ is a state of information does not settle whether any true contradictions exist; the sources deliberately do not take that position.
• Conditionals. The bilattice operations above do not include a canonical implication. Residuated implications on twist products exist, and choosing among them is discussed in the adjoint-structure paper; the base logic has no unique conditional (Belnap four-valued logic).
• Provenance and degrees. FOUR forgets who said what and how strongly. Richer bilattices can track degrees; tracking sources is an open design question.

Related

• Belnap four-valued logic: reasoning with gaps and gluts
• Paraconsistent settling and comprehension
• The adjoint structure of predication on bilattice fibers
• The Nelson identity on four-valued truth
• Sibling sites: 561.group, engineering.561.group, operations.561.group, services.561.group, market.561.group