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 (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
Canonical name	DeMorgansLaws
Date of creation	2013-03-22 12:24:49
Last modified on	2013-03-22 12:24:49
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	15
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 03E30
Related topic	Set
Related topic	Complement