# Kleene algebra

A lattice $L$ is said to be a Kleene algebra if it is a De Morgan algebra (with the associated unary operator $\sim$ on $L$) such that $(\sim a\wedge a)\leq(\sim b\vee b)$ for all $a,b\in L$.

Any Boolean algebra  $A$ is a Kleene algebra, if the complementation operator ${}^{\prime}$ is interpreted as $\sim$. This is true because $a^{\prime}\wedge a=0\leq 1=b^{\prime}\vee b$ for all $a,b\in A$. The converse  is not true. For example, consider the chain $\mathbf{n}=\{0,1,\ldots,n\}$, with the usual ordering  . Define $\sim$ by $\sim(k)=n-k$. Then it is easy to see that $\sim$ satisfies all the defining conditions of a De Morgan algebra. In addition, since every $a,b\in\mathbf{n}$ are comparable  , say $a\leq b$, then $(\sim a\wedge a)\leq a\leq b\leq(\sim b\vee b)$. And if $b\leq a$ on the other hand, then $\sim a\leq\ \sim b$ so that $(\sim a\wedge a)\leq\ \sim a\leq\ \sim b\leq(\sim b\vee b)$. But $\mathbf{n}$ is not Boolean, as $a\vee b$ is never $n$ unless one of them is.

Remark. As Boolean algebras are the algebraic realizations of the classical two-valued propositional logic  , Kleene algebras are the realizations of a three-valued propositional logic, where the three truth values can be described as true ($2$), false ($0$), and unknown ($1$). Just as $\{0,1\}$ is the simplest Boolean algebra (it is a simple algebra), $\{0,1,2\}$ is the simplest Kleene algebra, where $\sim$ is defined the same way as in the example above.

## References

• 1 G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)
Title Kleene algebra KleeneAlgebra1 2013-03-22 17:08:43 2013-03-22 17:08:43 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 06D30 KleeneAlgebra