# 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. 1.

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

2. 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\leq b$ iff $b=a\vee b$ iff $\sim b=\ \sim(a\vee b)=(\sim a)\wedge(\sim b)$ iff $\sim b\leq\ \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\neq 0$ and $(\sim a)\vee a\neq 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=\mathbf{n}\times\mathbf{n}$, where $\mathbf{n}=\{0,1,\ldots,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

 $\displaystyle a+(a+b)$ $\displaystyle=$ $\displaystyle(a-(a+b))\vee((a+b)-a)$ $\displaystyle=$ $\displaystyle(a-((a-b)\vee(b-a)))\vee(((a-b)\vee(b-a))-a)$ $\displaystyle=$ $\displaystyle(a\wedge(\sim a\vee b)\wedge(\sim b\vee a))\vee(((\sim b\wedge a)% \vee(\sim a\wedge b))\wedge(\sim a))$ $\displaystyle=$ $\displaystyle(a\wedge(\sim a\vee b))\vee(((\sim b\wedge a)\wedge(\sim a))\vee(% \sim a\wedge b))$ $\displaystyle=$ $\displaystyle((a\wedge(\sim a\vee b))\vee(\sim a\wedge b))\vee(\sim b\wedge(% \sim a\wedge a))$ $\displaystyle=$ $\displaystyle((\sim a\wedge a)\vee(a\wedge b)\vee(\sim a\wedge b))\vee(\sim b% \wedge 2a)$ $\displaystyle=$ $\displaystyle(2a\vee((\sim a\wedge a)\vee b))\vee(\sim b\wedge 2a)$ $\displaystyle=$ $\displaystyle(2a\vee(2a\vee b))\vee(\sim b\wedge 2a)$ $\displaystyle=$ $\displaystyle(2a\vee b)\vee(\sim b\wedge 2a)$ $\displaystyle=$ $\displaystyle 2a\vee(\sim b\wedge 2a)\vee b$ $\displaystyle=$ $\displaystyle 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$.

## References

• 1 G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)
Title De Morgan algebra DeMorganAlgebra 2013-03-22 16:09:25 2013-03-22 16:09:25 CWoo (3771) CWoo (3771) 13 CWoo (3771) Definition msc 06D30 msc 03G10