What's the deal with De Morgan algebras and Kleene algebras?

Question

The notion of Boolean algebras, and the corresponding classical propositional logic, is very standard, and it is easy to find information about them (for example, among many other such works, there is a three volume book titled Handbook of Boolean Algebras). Heyting algebras (essentially “Boolean algebras without the law of excluded middle”), and intuitionistic propositional logic, are a bit more esoteric, but there are still a lot of references about this. However, the notions of De Morgan algebra and Kleene algebra seem very little discussed, and having learned about them I am left with many questions, the analogous answers to which I know for Boolean or Heyting algebras, but for which I don't know where to turn to for a discussion in the context of De Morgan and Kleene algebras.

To be clear, a De Morgan algebra is a distributive lattice with bottom and top endowed with an involution ‘$\neg$’ which satisfies De Morgan law $\neg(x\lor y) = \neg x \land \neg y$ (or equivalently, $\neg(x\land y) = \neg x \lor \neg y$ as either follows from the other by involutivity). A Kleene algebra is a De Morgan algebra which additionally satisfies $x\land\neg x \leq y\lor\neg y$. An example of a Kleene (hence De Morgan) algebra is $\{0,\ldots,n\}$ with the usual order (so $\land$ and $\lor$ are min and max), and involution $k \mapsto n-k$: this is not a Boolean algebra when $n\geq 2$. Of course, the unit interval $[0,1]$ is also a Kleene algebra. An example of a De Morgan algebra which is not a Kleene algebra is the “diamond” $\{0,1\}^2$ with product order and the involution $(x,y) \mapsto (1-y, 1-x)$ (note that it fixes $(0,1)$ and $(1,0)$ which are incomparable, refuting the axiom $x\land\neg x \leq y\lor\neg y$).

These algebras turn up, for example, when defining some varieties of cubical sets: see “Varieties of Cubical Sets” by Buchholtz and Morehouse for a discussion, but in summary, the category of De Morgan, resp. Kleene, resp. Boolean cubes is the category having an object $[n]$ for each $n\in\mathbb{N}$ and whose morphisms $[m] \to [n]$ are given by $n$ elements in the free De Morgan, resp. Kleene, resp. Boolean algebra in $m$ variables, with composition given by substitution (in more fancy terms, this is a full subcategory of the Kleisli category of the “free De Morgan algebra”, resp. Kleene, resp. Boolean, monad); and cubical sets are the presheaves of sets on the corresponding cube category. This suggests that understanding the free De Morgan algebra and free Kleene algebra is worthwhile (the free Boolean algebra on finitely many variables, of course, is well understood). But of course the notion occurs in other places, such as fuzzy logic.

Anyway, some examples of questions I have about De Morgan and Kleene algebras are:

• How can we describe the free De Morgan algebra (resp. the free Kleene algebra) on $r$ variables? Do its elements have a canonical form? How many are there (exactly or, failing that, asymptotically)?

• How can we (algorithmically, and if possible not too inefficiently) decide when two expressions in $x_1,\ldots,x_r$ (in $\land,\lor,\neg$) are equal in the free De Morgan (resp. Kleene) algebra?

• Regarding the last question, I have seen it stated without reference that, for Kleene algebras, this holds if and only if the equality holds for all $x_1,\ldots,x_r$ in $[0,1]$, or equivalently, for all $x_1,\ldots,x_r$ in $\{0,1,2\}$: is this correct? If so, what is a reference for this statement? Is there an analogous statement for De Morgan algebras? (Can we perhaps replace $\{0,1,2\}$ by the “diamond” here?)

• If we define “De Morgan logic”, resp. “Kleene logic”, to be such that $p \vdash q$, for $p,q$ in the free De Morgan (resp. Kleene) algebra of countably many variables, when $p\leq q$ in that algebra, can we formulate this logic as rules of inference that are at least remotely similar to some usual presentation of classical and intuitionistic propositional logic? (I realize that De Morgan and Kleene logic lack an $\Rightarrow$ connector, which does not bode well for making them into useful “logics”, but there may still be something interesting to be said among those lines.)

• Is there anything remotely similar to the Stone duality of Boolean algebras for De Morgan or Kleene algebras, that might help describe all of them?

• What about infinitary, and possibly complete De Morgan algebra (resp. Kleene) algebras: other than $[0,1]$, is there a context in which they naturally come up? (There was this question on the matter, but it just asked whether the De Morgan law automatically held infinitarily, not giving any context about where this was relevant.) Can we perhaps see them as kinds of functions on generalized spaces just like frames (which are closely related to complete Heyting algebras) can be seen as open sets of a kind of generalized space know as “locales”?

Note: some of these questions may be somewhat stupid. My point is that I know essentially nothing about such algebras, so I have many questions, and these are the ones which come most naturally to my mind. But while I'd be more than happy to have the answer to any or all of the above, this question is mostly a reference request: any suggestion as to where I might learn these sort of things is more than welcome.

Answer 1

Per request of the OP, I’m reposting my comments as an answer. This is a series of observations without any references; most of these things are well known/easily shown.

1. Normal forms.

   Using De Morgan’s laws, any term can be converted to a CNF: a $\bigwedge$ of a set of clauses, each of which is a $\bigvee$ of a set of literals (= variables and their negations; we specifically allow both $x$ and $\neg x$ to occur in the same clause). Moreover, you can make the CNF nonredundant (i.e., no clause is properly included in another). One can check easily that two different nonredundant CNF are inequivalent in the 4-element diamond algebra, hence each term has a unique nonredundant CNF over the theory of De Morgan algebras. Likewise, each term has a unique nonredundant DNF.

   [This follows from the more general fact that for any clauses $C_i$, $C'_j$, $\bigwedge_{i<n}C_i\le\bigwedge_{j<m}C'_j$ holds only if $\forall j<m\,\exists i<n\,C_i\subseteq C'_j$: otherwise, fix $j<m$ for which it fails, and find a set $S$ of literals such that $S\cap C'_j=\varnothing$ and $S\cap C_i\ne\varnothing$ for each $i<n$. Then define an assignment in the diamond $\{0,a,b,1\}$ that gives all elements of $S$ value $1$ or $a$, and all elements of $C'_j$ values $0$ or $b$.]

2. Generators.

   As a corollary, the argument above shows that an equation holds in all De Morgan algebras iff it holds in the diamond; i.e., the diamond generates the variety of De Morgan algebras. One can also show that the variety of Kleene algebras is generated by the 3-element algebra. (Which I will denote $\{0,*,1\}$ rather than the confusing $\{0,1,2\}$: just as in classical or intuitionistic logic, it is a general convention in this context that $1$ and $0$ denote the maximal and minimal element of the lattice, respectively. Common notations for the third value include $\frac12$.) One can, in fact, show that the class of De Morgan resp. Kleene algebras is the ISP of the diamond resp. the 3-element algebra, as subdirectly irreducible De Morgan resp. Kleene algebras are subalgebras of the diamond resp. $\{0,*,1\}$.

3. Complexity.

   Consequently, validity of equations in De Morgan resp. Kleene algebras is decidable in coNP, as it is enough to check all assignments in the diamond resp. $\{0,*,1\}$. It is, in fact, easy to see that it is coNP-complete, by reduction from classical equivalence between monotone formulas.

4. Free algebras.

   One way of describing free De Morgan algebras is using the nonredundant CNF from point 1. For Kleene algebras, the fact that the variety is generated by $\{0,*,1\}$ implies that the $n$-generated free Kleene algebra can be identified with a subalgebra of the Cartesian power $\{0,*,1\}^{\{0,*,1\}^n}$ consisting of term functions $f\colon\{0,*,1\}^n\to\{0,*,1\}$. It is not difficult to show that these functions can be characterized as follows: $f\colon\{0,*,1\}^n\to\{0,*,1\}$ is term-definable iff

   • $f$ maps $\{0,1\}^n$ to $\{0,1\}$;
   • $f$ is monotone w.r.t. the “information order” (the partial order given by ${*}\preceq0$, ${*}\preceq1$);
   • and, if you don’t include a constant $0$ or $1$ in the signature: $f(\vec{*})={*}$.

   Likewise, free De Morgan algebras are described by term functions of the diamond $\Diamond=\{0,a,b,1\}$. I haven’t seen this description before, but I believe they are characterized by

   • $f(\sigma(\vec x))=\sigma(f(\vec x))$, where $\sigma$ is the automorphism that exchanges $a$ and $b$; and
   • $f$ is monotone w.r.t. the partial order $a\preceq0\preceq b$, $a\preceq1\preceq b$.

   Again, if you don’t have $0$ or $1$ in the signature, you need to disallow the constant $0$ and constant $1$ functions.

   [These conditions are clearly necessary. For sufficience, let $f\colon\Diamond^n\to\Diamond$ satisfy the conditions. Let $L=\{x_i,\neg x_i:i<n\}$ be the set of literals. Put $A=\{\alpha\in\Diamond^n:f(\alpha)\ge a\}$ and $g=\bigvee\{h_\alpha:\alpha\in A\}$, where $h_\alpha=\bigwedge\{x\in L:\alpha(x)\ge a\}$; we will show $f=g$. Clearly, $\alpha(h_\alpha)\ge a$, thus $f(\alpha)\ge a\implies g(\alpha)\ge a$. Also, $f(\alpha)\ge b\implies f(\sigma(\alpha))\ge a\implies g(\sigma(\alpha))\ge a\implies g(\alpha)\ge b$. Thus, $g\ge f$. On the other hand, $h_\alpha\le f$ for all $\alpha\in A$, whence $g\le f$: we have $h_\alpha(\beta)\ge a\implies\beta\preceq\alpha\implies f(\beta)\preceq f(\alpha)\preceq1\implies f(\beta)\ge a$; consequently, $h_\alpha(\beta)\ge b\implies h_\alpha(\sigma(\beta))\ge a\implies f(\sigma(\beta))\ge a\implies f(\beta)\ge b$.]

5. Logic.

   The logic of De Morgan algebras as defined in the question is known as the Belnap–Dunn 4-valued logic, or first-degree entailment (FDE). Perhaps the simplest way to present it as a sequent calculus is to use a language that only allows formulas in NNF: i.e., formulas are built using monotone connectives from positive and negative literals $p$, $\overline p$, and negation is defined as an involutive operator on formulas that changes the polarity of all literals and replaces each monotone connective with its dual. In this setting, a sound and complete calculus for FDE is given by the usual structural rules and rules for monotone connective from classical LK (with no $\neg$ rules).

   If you want a calculus that works directly for formulas not necessarily in NNF, you have to add rules for negated connectives: e.g., $$\frac{\Gamma\vdash\neg\phi,\Delta\quad\Gamma\vdash\neg\psi,\Delta}{\Gamma\vdash\neg(\phi\lor\psi),\Delta}, \qquad\frac{\Gamma,\neg\phi,\neg\psi\vdash\Delta}{\Gamma,\neg(\phi\lor\psi)\vdash\Delta},$$ and the dual rules for $\neg(\land)$; moreover, the double negation rules $$\frac{\Gamma\vdash\phi,\Delta}{\Gamma\vdash\neg\neg\phi,\Delta},\qquad \frac{\Gamma,\phi\vdash\Delta}{\Gamma,\neg\neg\phi\vdash\Delta}.$$

   One way to see that this calculus is complete and enjoys cut elimination is to observe that the rules for connectives are invertible, which reduces it to the case of sequents consisting only of literals; it’s easy to see that such a sequent where the LHS and RHS do not intersect can be refuted in the diamond (giving also yet another proof that the diamond generates the variety of De Morgan algebras).

   You obtain a calculus for the logic of Kleene algebras by adding the axioms $$\phi,\neg\phi\vdash\psi,\neg\psi$$ that can be restricted to $\phi$ and $\psi$ being atoms. (Its completeness can be shown in much the same way as above, also providing a proof that $\{0,*,1\}$ generates the variety of Kleene algebras.)

   However, note that Kleene logic (denoted K or $\mathrm{K_3}$) is an established name for a stronger logic, viz. the logic of the 3-element algebra $\{0,*,1\}$ with designated value $1$ (i.e., a sequent $\Gamma\vdash\Delta$ is valid iff every assignment in $\{0,*,1\}$ that gives all formulas in $\Gamma$ value $1$ also gives some formula in $\Delta$ value $1$). The dual logic with designated values $\{1,*\}$ (i.o.w., $\Gamma\vdash\Delta$ is valid iff every assignment in $\{0,*,1\}$ that gives all formulas in $\Delta$ value $0$ also gives some formula in $\Gamma$ value $0$) is called the logic of paradox (LP), as it is one of the basic paraconsistent logics. Your logic of Kleene algebras is the intersection of K and LP. A calculus for K can be obtained from the calculus for FDE by adding the axioms $$\phi,\neg\phi\vdash{},$$ and a calculus for LP by adding the axioms $${}\vdash\phi,\neg\phi,$$ where, again, $\phi$ can be restricted to atoms.

   I should perhaps mention that the history here went the other way round: first, Kleene defined his 3-valued logic, and only later his name became attached to algebras from a variety generated by the underlying 3-element algebra of the logical matrix that defines the logic.

Answer 2

There are a lot of questions bundled together here. I will give some references for some of the questions.

An early paper on these topics is:

Lattices with involution
J. A. Kalman
Trans. Amer. Math. Soc. 87 (1958), 485-491.

What we now call a De Morgan algebra Kalman referred to as a 'distributive $i$-lattice', and what we now call a Kleene algebra Kalman referred to as a 'normal distributive $i$-lattice'. Changing to the modern language, Kalman proves in his Lemma 2 that, up to isomorphism, the subdirectly irreducible De Morgan algebras are exactly the subalgebras of the 'diamond' and in his Theorem 2 he proves that the subdirectly irreducible Kleene algebras are exactly the subalgebras of the 3-element chain. This answers the questions in your second and third bullet, since two expressions are equal in a variety iff they are equal in some subclass that generates the variety. Thus, two expressions are equal in a variety iff they are equal in all free algebras iff they are equal in all subdirectly irreducible algebras.

Addressing your fifth bullet, the paper

Coproducts of De Morgan algebras
William H. Cornish and Peter R. Fowler
BULL. AUSTRAL. MATH. SOC. v. 16, (1977), 1-13

develops a duality theory for De Morgan algebras in order to study coproducts. The abstract for their paper says:

The dual of the category of De Morgan algebras is described in terms of compact totally ordered-disconnected ordered topological spaces which possess an involutorial homeomorphism that is also a dual order-isomorphism. This description is used to study the coproduct of an arbitrary collection of De Morgan algebras and also to represent the coproduct of two De Morgan algebras in terms of the continuous order-preserving functions from the Priestley space of one algebra to the other algebra, endowed with the discrete topology. In addition, it is proved that the coproduct of a family of Kleene algebras in the category of De Morgan algebras is the same as the coproduct in the subcategory of Kleene algebras if and only if at most one of the algebras is not boolean.