De Morgan algebra

A bounded distributive lattice $L$ is called a De Morgan algebra if there exists a unary operator $\sim :L\to L$ such that

1. $\sim (\sim a)=a$ and

2. $\sim (a\vee b)=(\sim a)\wedge (\sim b)$.

From the definition, we have the following properties:

• $\sim$ is a bijection, since for any $a\in L$, $a=\sim (\sim a)$.

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

• $\sim 0=\sim (0\wedge (\sim a))=(\sim 0)\vee a$ for all $a\in L$, so $\sim 0=1$. Dually, $\sim 1=0$. As a result, a De Morgan algebra is an Ockham algebra.

• $a\le b$ iff $b=a\vee b$ iff $\sim b=\sim (a\vee b)=(\sim a)\wedge (\sim b)$ iff $\sim b\le \sim a$.

• A Boolean algebra is always a De Morgan algebra, where the $\sim$ is the complementation operator ${}^{\prime }$. The converse is not true. In general, $\sim a$ is not a complement of $a$ (that is, $(\sim a)\wedge a\ne 0$ and $(\sim a)\vee a\ne 1$). 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=𝐧\times 𝐧$, where $𝐧=\{0,1,\mathrm{\dots },n\}$ is a chain with the usual ordering. Define $\sim$ on $L$ by $\sim (a,b)=(n-b,n-a)$. Then ${\sim }^2(a,b)=(a,b)$. The De Morgan’s laws follow from the identity $n-(a\vee b)=(n-a)\wedge (n-b)$ applied to each of the two components. But $L$ is not Kleene in general. Take $n=3$, then $\sim (1,2)=(1,2)$ and $\sim (2,1)=(2,1)$. But $(1,2)=\sim (1,2)\wedge (1,2)$ and $(2,1)=\sim (2,1)\vee (2,1)$ are not comparable.

Next, for any $a,b\in L$, define $a-b:=a\wedge (\sim b)$. Then $-$ is a binary operator. It has the following properties:

• $a-0=a\wedge (\sim 0)=a\wedge 1=a$.

• $0-a=0\wedge (\sim a)=0$.

• $a-1=a\wedge (\sim 1)=a\wedge 0=0$.

• $1-a=1\wedge (\sim a)=\sim a$.

• $(a-b)-c=(a\wedge (\sim b))\wedge (\sim c)=a\wedge (\sim (b\vee c))=a-(b\vee c)$.

Finally, we define for $a,b\in L$, $a+b=(a-b)\vee (b-a)$. This is again a binary operator, with the following properties:

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

• $a+0=a$. We have $a+0=(a-0)\vee (0-a)=a\vee 0=a$.

• $a+1=\sim a$, since $a+1=(a-1)\vee (1-a)=0\vee (\sim a)=\sim a$. In particular $1+1=0$.

• $a+a=(a-a)\vee (a-a)=a-a=a\wedge (\sim a)$. If we define $2a:=a+a$, then $a+2a=(a-2a)\vee (2a-a)=(a\wedge (a\vee (\sim a))\vee ((a\wedge (\sim a)\wedge (\sim a))=a\vee ((a\wedge (\sim a))=a$.

• More generally, we have

  $a+(a+b)$ $=$ $(a-(a+b))\vee ((a+b)-a)$

  $=$ $(a-((a-b)\vee (b-a)))\vee (((a-b)\vee (b-a))-a)$

  $=$ $(a\wedge (\sim a\vee b)\wedge (\sim b\vee a))\vee (((\sim b\wedge a)\vee (\sim a\wedge b))\wedge (\sim a))$

  $=$ $(a\wedge (\sim a\vee b))\vee (((\sim b\wedge a)\wedge (\sim a))\vee (\sim a\wedge b))$

  $=$ $((a\wedge (\sim a\vee b))\vee (\sim a\wedge b))\vee (\sim b\wedge (\sim a\wedge a))$

  $=$ $((\sim a\wedge a)\vee (a\wedge b)\vee (\sim a\wedge b))\vee (\sim b\wedge 2a)$

  $=$ $(2a\vee ((\sim a\wedge a)\vee b))\vee (\sim b\wedge 2a)$

  $=$ $(2a\vee (2a\vee b))\vee (\sim b\wedge 2a)$

  $=$ $(2a\vee b)\vee (\sim b\wedge 2a)$

  $=$ $2a\vee (\sim b\wedge 2a)\vee b$

  $=$ $2a\vee b.$

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 homomorphism: it preserves $\sim$.

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