Kleene algebra

This entry concerns a Kleene algebra that is defined as a lattice satisfying certain conditions. There is another of Kleene algebra, which is the abstraction of the algebra of regular expressions in the theory of computations. The two concepts are different. For Kleene algebras of the second kind, please see this link (http://planetmath.org/KleeneAlgebra).

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)\le (\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\le 1=b^{\prime }\vee b$ for all $a,b\in A$. The converse is not true. For example, consider the chain $𝐧=\{0,1,\mathrm{\dots },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 𝐧$ are comparable, say $a\le b$, then $(\sim a\wedge a)\le a\le b\le (\sim b\vee b)$. And if $b\le a$ on the other hand, then $\sim a\le \sim b$ so that $(\sim a\wedge a)\le \sim a\le \sim b\le (\sim b\vee b)$. But $𝐧$ 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.

Title	Kleene algebra
Canonical name	KleeneAlgebra1
Date of creation	2013-03-22 17:08:43
Last modified on	2013-03-22 17:08:43
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 06D30
Related topic	KleeneAlgebra