Four imprints of Belnap’s useful four-valued logic in computer science

Tomáš Jakl · 2025

Read Four imprints of Belnap’s useful four-valued logic in computer science by Tomáš Jakl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20679.txt.

Introduction

Tomáš Jakl reviews four areas of computing that echo a four-valued logic from the 1970s, in work from 2025. That logic lets a claim be true, false, both, or neither. It was built to handle messy, partial data in a clean way.

Only one of the four areas openly credits the link, a branch of frame theory. The other three cover linear logic, a blame system for program parts, and shared mutable values. A product trick for pairing values connects all of them behind the scenes. Jakl argues the hidden debt should be named and studied. Naming it could let each field borrow proofs and tools from the others.

Catalog record

CREATORTomáš Jakl
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20679

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Four imprints of Belnap’s useful four-valued logic in computer science Tomáš Jakl Abstract We review four areas of theoretical computer science which share technical or philosophical ideas with the work of Belnap on his useful four-valued logic. Perhaps surprisingly, the inspiration by Belnap–Dunn logic is acknowledged only in the study of d-frames. The connections of Belnap’s work and linear logic, Blame Calculus or the study of LVars are not openly admitted. The key to three of these connections with Belnap’s work go via the twist-product representation of bilattices. On the one hand, it allows us to view a large class of models of linear logic as based on Belnap–Dunn logic. On the other hand, d-frames admit two twist-product representation theorems and, also, the key theorem in Blame Calculus is essentially a twist-product representation theorem too, albeit with a strong proof-theoretic flavour. keywords Belnap–Dunn logic, twist-construction, twist-product representation, d-frames, Blame Calculus, LVars In memory of Nuel Belnap. 1 Introduction Belnap’s four-valued logic Belnap (1976) ; Belnap (1977) , following Dunn Dunn (1976) , is an extension of the classical two-valued logic to encompass phenomena arising in computer-based reasoning systems. On top of the classical two values ‘True’ and ‘False’ it adds ‘None’ representing the lack of any information and ‘Both’ representing the inconsistency of claiming both ‘True’ and ‘False’. One of the key ideas in Belnap’s approach is to distinguish between two orders of the four-valued lattice, the usual ‘logical order’ \mathrel{\ThisStyle{\hbox{\hskip 3.8889pt\hskip-3.8889pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.8889pt\hskip-4.7222pt\raisebox{1.07777pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-4.7222pt\hskip 3.8889pt}}} and the ‘information/knowledge order’ \sqsubseteq . The latter order is inspired by domain theory, initiated by Scott Scott (1970) . Domains were introduced to give semantics to (abstract) programming languages such as the lambda calculus. The tradition of using “Four Logical Alternatives,” known as catuṣkoṭi, goes back to the 6th century Indian logic. These four alternatives precisely correspond to the aforementioned four values Robinson (1957) ; Jayatilleke (1967) ; Garfield (2019) . However, undoubtedly, Belnap was the first to identify the two orders and to emphasise the usefulness of the four values for computer reasoning. Both None False True logical order \mathrel{\ThisStyle{\hbox{\hskip 3.3056pt\hskip-3.3056pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.3056pt\hskip-3.97226pt\raisebox{0.9736pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-3.97226pt\hskip 3.3056pt}}} information order \sqsubseteq Figure 1: Belnap’s four-valued lattice \mathcal{FOUR} . Later on Ginsberg Ginsberg (1988) introduced bilattices as an algebraic description of the connectives introduced by Belnap. As his primary examples he used world-based bilattices, that is, structures consisting of pairs (A_{+},A_{-}) of subsets of a chosen set of worlds. Then, intuitively, A_{+} is a set of worlds where a given property holds and A_{-} are the worlds where it fails. Under this interpretation four-valued connectives are calculated as simple set-theoretic operations. For example, the negation and logical conjunction are give by \neg(A_{+},A_{-})=(A_{-},A_{+}) and (A_{+},A_{-})\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}}(B_{+},B_{-})=(A_{+}\cap B_{+},A_{-}\cup A_{-}) , respectively. Then Fitting Fitting (1991) observed that the construction of Ginsberg holds more generally. That is, not only that the square products of a (powerset) lattice yields a bilattice but, in fact, this holds true for any lattice. It is a remarkable result of Rivieccio, from his Ph.D. thesis Rivieccio (2010) , that every bilattice is obtained this way. Philosophically speaking, this means that, even in this more general algebraic approach of Ginsberg Ginsberg (1988) , every bilattice-valued proposition can be decomposed into two parts, its positive and negative parts. In this paper we discuss three different examples from theoretical computer science where this tension between positive and negative parts is crucial. Firstly, in Section 3 , we observe that the famous Chu construction of models of linear logic is exactly the twist-construction of bilattices, with most connectives being our well-known four-valued connectives of Belnap and Ginsberg. Secondly, in Section 4 , we discuss the author’s own work on d-frames, which came from considerations in denotation semantics of programming languages and domain theory. On the one hand, d-frames provide a relaxation which encodes properties of topological models of Belnap–Dunn logic. Our approach reopens some of Belnap’s original questions that have to do with computability in the information order. After d-frames we turn to Blame Calculus (Section 5 ). This is a type system for programming languages that allows to construct types from other types with set comprehension. The attentive reader might notice that the title of this paper speaks of four imprints of Belnap’s work, and not merely three. Indeed, the final section (Section 6 ) is about a very practical application of ideas similar to Belnap’s, in an implementation of special type of variables (called LVars) for programming purposes Kuper and Newton (2013) ; Kuper (2015) . LVars were introduced to solve a particular problem in the theory distributed and parallel programs. Perhaps surprisingly, the core of the solution lies in adding the information order as part of the structure, which is very much in the spirit of Belnap who added the information order (and extra new values and connectives) to the usual two-valued logical lattice. 2 Review of bilattices The algebraic properties of \mathcal{FOUR} (from Figure 1 ) are encapsulated by structures called bilattices . These are the tuples (B,\sqcap,\sqcup,\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\neg,\mathsf{f},\mathsf{t},\bot,\top) where (BI-1) (B,\sqcap,\sqcup,\bot,\top) and (B,\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathsf{f},\mathsf{t}) are (bounded) lattices 1 1 1 Throughout this text we always implicitly assume that our lattices are bounded. , (BI-2) x\sqsubseteq y implies \neg x\sqsubseteq\neg y , (BI-3) x\mathrel{\ThisStyle{\hbox{\hskip 3.8889pt\hskip-3.8889pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.8889pt\hskip-4.7222pt\raisebox{1.07777pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-4.7222pt\hskip 3.8889pt}}}y implies \neg y\mathrel{\ThisStyle{\hbox{\hskip 3.8889pt\hskip-3.8889pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.8889pt\hskip-4.7222pt\raisebox{1.07777pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-4.7222pt\hskip 3.8889pt}}}\neg x , and (BI-4) a=\neg\neg a . We denote by \sqsubseteq the order induced by the lattice operations \sqcap,\sqcup and, similarly, we denote \mathrel{\ThisStyle{\hbox{\hskip 3.8889pt\hskip-3.8889pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.8889pt\hskip-4.7222pt\raisebox{1.07777pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-4.7222pt\hskip 3.8889pt}}} the order induced by \mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}} . Note that the constants \mathsf{f},\mathsf{t},\bot,\top correspond to the four values ‘False’, ‘True’, ‘None’, and ‘Both’, respectively. Furthermore, to not get lost in the intricate details concerning weak versions of bilattices, we always assume that our bilattices are distributive , i.e. that any combination of pairs of operations from \sqcap,\sqcup,\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}} distributes over each other. In fact, the variety of (distributive) bilattices is generated by \mathcal{FOUR} , i.e. the bilattice on the set \{\mathsf{f},\mathsf{t},\bot,\top\} , with \sqcap,\sqcup,\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}} as in Figure 1 and with negation given by \neg\top=\top , \neg\bot=\bot and \neg\mathsf{t}=\mathsf{f} ( Rivieccio, 2010 , Theorem 2.4.1) . Twist-construction In the following lines we describe a simple construction, that goes back to Kalman Kalman (1958) and which found its place not only in the theory of bilattices but also e.g. in the algebraic approach to relevance logic Tsinakis and Wille (2006) ; Fussner and Galatos (2019) , albeit in a slightly different form. Let L_{+} and L_{-} be distributive lattices, the twist-structure L_{+}\bowtie L_{-} is the algebra (L_{+}\times L_{-},\,\sqcap,\sqcup,\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}},\mathsf{f},\mathsf{t},\bot,\top) where \displaystyle(a_{+},a_{-})\sqcap(b_{+},b_{-}) \displaystyle=(a_{+}\land b_{+},a_{-}\land b_{-}), \displaystyle(a_{+},a_{-})\sqcup(b_{+},b_{-}) \displaystyle=(a_{+}\lor b_{+},a_{-}\lor b_{-}), \displaystyle(a_{+},a_{-})\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\wedge$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{-1.24445pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}}(b_{+},b_{-}) \displaystyle=(a_{+}\land b_{+},a_{-}\lor b_{-}), \displaystyle(a_{+},a_{-})\mathbin{\ThisStyle{\hbox{\hskip 3.33334pt\hskip-3.33334pt\hbox{$\hbox{$\SavedStyle\vee$}$}\hskip-3.33334pt\hskip-1.38889pt\raisebox{1.85556pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\lx@scalerel@obj{\cdot}$}$}}\hskip-1.38889pt\hskip 3.33334pt}}}(b_{+},b_{-}) \displaystyle=(a_{+}\lor b_{+},a_{-}\land b_{-}), \displaystyle\mathsf{f}=(0,1),\quad\mathsf{t}=(1,0), \displaystyle\quad\bot=(0,0),\kern 5.0pt\text{and}\kern 5.0pt\top=(1,1). The induced orders \sqsubseteq and \mathrel{\ThisStyle{\hbox{\hskip 3.8889pt\hskip-3.8889pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.8889pt\hskip-4.7222pt\raisebox{1.07777pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-4.7222pt\hskip 3.8889pt}}} are then given as follows. \displaystyle(a_{+},a_{-})\sqsubseteq(b_{+},b_{-}) \displaystyle\iff a_{+}\leq b_{+}\kern 5.0pt\text{and}\kern 5.0pta_{-}\leq b_{-} \displaystyle(a_{+},a_{-})\mathrel{\ThisStyle{\hbox{\hskip 3.8889pt\hskip-3.8889pt\hbox{$\hbox{$\SavedStyle\leq$}$}\hskip-3.8889pt\hskip-4.7222pt\raisebox{1.07777pt}{\hbox{$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\hbox{$\SavedStyle\ \,\lx@scalerel@obj{\cdot}$}$}}\hskip-4.7222pt\hskip 3.8889pt}}}(b_{+},b_{-}) \displaystyle\iff a_{+}\leq b_{+}\kern 5.0pt\text{and}\kern 5.0ptb_{-}\leq a_{-} In case we use the same lattice twice, instead of writing L\bowtie L we simply write L^{{\bowtie}} . Then, L^{{\bowtie}} can be extended to a bilattice by interpreting negation as \neg(a_{+},a_{-})=(a_{-},a_{+}). If, moreover, L is a Heyting algebra, we can view L^{{\bowtie}} as an implicative bilattice.

Read the complete text