# De Morgan algebra

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:

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.$

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