This entry concerns a Kleene algebra that is defined as a lattice satisfying certain conditions. There is another type 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.

A lattice is said to be a Kleene algebra if it is a De Morgan algebra (with the associated unary operator on ) such that for all .

Any Boolean algebra is a Kleene algebra, if the complementation operator is interpreted as . This is true because for all . The converse is not true. For example, consider the chain , with the usual ordering. Define by . Then it is easy to see that satisfies all the defining conditions of a De Morgan algebra. In addition, since every are comparable, say , then . And if on the other hand, then so that . But is not Boolean, as is never unless one of them is.

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

Bibliography

1

G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)