# de Morgan’s laws

In set theory, de Morgan’s laws relate the three basic set operations to each other; the union, the intersection, and the complement. de Morgan’s laws are named after the Indian-born British mathematician and logician Augustus De Morgan (1806-1871) [1].

If $A$ and $B$ are subsets of a set $X$, de Morgan’s laws state that

 $\displaystyle(A\cup B)^{\complement}$ $\displaystyle=$ $\displaystyle A^{\complement}\cap B^{\complement},$ $\displaystyle(A\cap B)^{\complement}$ $\displaystyle=$ $\displaystyle A^{\complement}\cup B^{\complement}.$

Here, $\cup$ denotes the union, $\cap$ denotes the intersection, and $A^{\complement}$ denotes the set complement of $A$ in $X$, i.e., $A^{\complement}=X\setminus A$.

Above, de Morgan’s laws are written for two sets. In this form, they are intuitively quite clear. For instance, the first claim states that an element that is not in $A\cup B$ is not in $A$ and not in $B$. It also states that an elements not in $A$ and not in $B$ is not in $A\cup B$.

For an arbitrary collection of subsets, de Morgan’s laws are as follows:

Let $X$ be a set with subsets $A_{i}\subset X$ for $i\in I$, where $I$ is an arbitrary index-set. In other words, $I$ can be finite, countable, or uncountable. Then

 $\displaystyle\Big{(}\bigcup_{i\in I}A_{i}\Big{)}^{\complement}$ $\displaystyle=$ $\displaystyle\bigcap_{i\in I}A_{i}^{\complement},$ $\displaystyle\Big{(}\bigcap_{i\in I}A_{i}\Big{)}^{\complement}$ $\displaystyle=$ $\displaystyle\bigcup_{i\in I}A_{i}^{\complement}.$

(proof (http://planetmath.org/DeMorgansLawsProof))

de Morgan’s laws in a
For Boolean variables $x$ and $y$ in a Boolean algebra, de Morgan’s laws state that

 $\displaystyle(x\land y)^{\prime}$ $\displaystyle=$ $\displaystyle x^{\prime}\lor y^{\prime},$ $\displaystyle(x\lor y)^{\prime}$ $\displaystyle=$ $\displaystyle x^{\prime}\land y^{\prime}.$

Not surprisingly, de Morgan’s laws form an indispensable tool when simplifying digital circuits involving and, or, and not gates [2].

## References

• 1 Wikipedia’s http://www.wikipedia.org/wiki/Augustus_De_Morganentry on de Morgan, 4/2003.
• 2 M.M. Mano, Computer Engineering: Hardware Design, Prentice Hall, 1988.
Title de Morgan’s laws DeMorgansLaws 2013-03-22 12:24:49 2013-03-22 12:24:49 mathcam (2727) mathcam (2727) 15 mathcam (2727) Theorem msc 03E30 Set Complement