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 \begin{eqnarray*} (A \cup B)^\complement &=& A^\complement \cap B^\complement, \\ (A \cap B)^\complement &=& A^\complement \cup B^\complement. \end{eqnarray*}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:

Theorem. 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 \begin{eqnarray*} \Big( \bigcup_{i\in I} A_i \Big)^\complement &=& \bigcap_{i\in I} A_i^\complement, \\ \Big( \bigcap_{i\in I} A_i \Big)^\complement &=& \bigcup_{i\in I} A_i^\complement. \end{eqnarray*}(proof)

de Morgan's laws in a Boolean algebra
For Boolean variables $x$ and $y$ in a Boolean algebra, de Morgan's laws state that \begin{eqnarray*} (x \land y)' &=& x' \lor y', \\ (x \lor y)' &=& x' \land y'. \end{eqnarray*}Not surprisingly, de Morgan's laws form an indispensable tool when simplifying digital circuits involving and, or, and not gates [2].

Bibliography

1

Wikipedia's entry on de Morgan, 4/2003.

2

M.M. Mano, Computer Engineering: Hardware Design, Prentice Hall, 1988.