Kleene algebra

This entry concerns a Kleene algebra that is defined as a latticeMathworldPlanetmath satisfying certain conditions. There is another of Kleene algebra, which is the abstraction of the algebra of regular expressionsMathworldPlanetmath in the theory of computations. The two conceptsMathworldPlanetmath 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 on L) such that (aa)(bb) for all a,bL.

Any Boolean algebraMathworldPlanetmath A is a Kleene algebra, if the complementation operator is interpreted as . This is true because aa=01=bb for all a,bA. The converseMathworldPlanetmath is not true. For example, consider the chain 𝐧={0,1,,n}, with the usual orderingMathworldPlanetmath. Define by (k)=n-k. Then it is easy to see that satisfies all the defining conditions of a De Morgan algebra. In addition, since every a,b𝐧 are comparablePlanetmathPlanetmath, say ab, then (aa)ab(bb). And if ba on the other hand, then ab so that (aa)ab(bb). But 𝐧 is not Boolean, as ab is never n unless one of them is.

Remark. As Boolean algebras are the algebraic realizations of the classical two-valued propositional logicPlanetmathPlanetmath, 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 is defined the same way as in the example above.


  • 1 G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)
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