nLab Kleene algebra

Kleene algebra

This page is about de Morgan algebras satisfying an extra condition. For Kleene star algebras in relation to regular expressions?, see there.

Kleene algebra


A Kleene algebra is a de Morgan algebra DD satisfying x¬xy¬yx \wedge \neg x \le y \vee \neg y for all x,yDx,y\in D. Since the order is definable in terms of the lattice operators, this can be stated as the equation

x¬x(y¬y)=x¬x. x \wedge \neg x \wedge (y \vee \neg y) = x \wedge \neg x.


  • Any Boolean algebra is a Kleene algebra, with ¬\neg the logical negation.
  • The unit interval [0,1][0,1] is a Kleene algebra, with ¬x=(1x)\neg x = (1-x).

Created on January 17, 2019 at 14:26:42. See the history of this page for a list of all contributions to it.