De Morgan algebra

A boundedPlanetmathPlanetmathPlanetmathPlanetmath distributive latticeMathworldPlanetmath L is called a De Morgan algebra if there exists a unary operator :LL such that

  1. 1.

    (a)=a and

  2. 2.


From the definition, we have the following properties:

  • is a bijection, since for any aL, a=(a).

  • (ab)=[((a))((b))]=[((a)(b))]=(a)(b), which is the dual statement of (2) above. This, together with condition (2), are commonly known as the De Morgan’s laws.

  • 0=(0(a))=(0)a for all aL, so 0=1. Dually, 1=0. As a result, a De Morgan algebra is an Ockham algebra.

  • ab iff b=ab iff b=(ab)=(a)(b) iff ba.

  • A Boolean algebraMathworldPlanetmath is always a De Morgan algebra, where the is the complementation operator . The converseMathworldPlanetmath is not true. In general, a is not a complementPlanetmathPlanetmath of a (that is, (a)a0 and (a)a1). Otherwise, L is a complemented lattice and consequently a Boolean algebra.

Furthermore, a Kleene algebra is, by definition, a De Morgan algebra. But the converse is false. For example, consider L=𝐧×𝐧, where 𝐧={0,1,,n} is a chain with the usual ordering. Define on L by (a,b)=(n-b,n-a). Then 2(a,b)=(a,b). The De Morgan’s laws follow from the identityPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath n-(ab)=(n-a)(n-b) applied to each of the two components. But L is not Kleene in general. Take n=3, then (1,2)=(1,2) and (2,1)=(2,1). But (1,2)=(1,2)(1,2) and (2,1)=(2,1)(2,1) are not comparablePlanetmathPlanetmath.

Next, for any a,bL, define a-b:=a(b). Then - is a binary operator. It has the following properties:

  • a-0=a(0)=a1=a.

  • 0-a=0(a)=0.

  • a-1=a(1)=a0=0.

  • 1-a=1(a)=a.

  • (a-b)-c=(a(b))(c)=a((bc))=a-(bc).

Finally, we define for a,bL, a+b=(a-b)(b-a). This is again a binary operator, with the following properties:

  • a+b=b+a. This is obvious by the symmetryPlanetmathPlanetmath in the definition of +.

  • a+0=a. We have a+0=(a-0)(0-a)=a0=a.

  • a+1=a, since a+1=(a-1)(1-a)=0(a)=a. In particular 1+1=0.

  • a+a=(a-a)(a-a)=a-a=a(a). If we define 2a:=a+a, then a+2a=(a-2a)(2a-a)=(a(a(a))((a(a)(a))=a((a(a))=a.

  • More generally, we have

    a+(a+b) = (a-(a+b))((a+b)-a)
    = (a-((a-b)(b-a)))(((a-b)(b-a))-a)
    = (a(ab)(ba))(((ba)(ab))(a))
    = (a(ab))(((ba)(a))(ab))
    = ((a(ab))(ab))(b(aa))
    = ((aa)(ab)(ab))(b2a)
    = (2a((aa)b))(b2a)
    = (2a(2ab))(b2a)
    = (2ab)(b2a)
    = 2a(b2a)b
    = 2ab.

Remark. Since a De Morgan algebra is an Ockham algebra, a morphism between any two objects in the category of De Morgan algebras behaves just like an Ockham algebra homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath: it preserves .


  • 1 G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)
Title De Morgan algebra
Canonical name DeMorganAlgebra
Date of creation 2013-03-22 16:09:25
Last modified on 2013-03-22 16:09:25
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Definition
Classification msc 06D30
Classification msc 03G10