# 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 $\mathbf{n}=\{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 \mathbf{n}$ 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 $\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 |
---|---|

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 |