## You are here

Homede Morgan's laws

## Primary tabs

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

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

$\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)

de Morgan’s laws in a Boolean algebra

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 entry on de Morgan, 4/2003.
- 2
M.M. Mano,
*Computer Engineering: Hardware Design*, Prentice Hall, 1988.

## Mathematics Subject Classification

03E30*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections