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
${(A\cup B)}^{\mathrm{\complement}}$ | $=$ | ${A}^{\mathrm{\complement}}\cap {B}^{\mathrm{\complement}},$ | ||
${(A\cap B)}^{\mathrm{\complement}}$ | $=$ | ${A}^{\mathrm{\complement}}\cup {B}^{\mathrm{\complement}}.$ |
Here, $\cup $ denotes the union, $\cap $ denotes the intersection, and ${A}^{\mathrm{\complement}}$ denotes the set complement of $A$ in $X$, i.e., ${A}^{\mathrm{\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
${\left({\displaystyle \bigcup _{i\in I}}{A}_{i}\right)}^{\mathrm{\complement}}$ | $=$ | $\bigcap _{i\in I}}{A}_{i}^{\mathrm{\complement}},$ | ||
${\left({\displaystyle \bigcap _{i\in I}}{A}_{i}\right)}^{\mathrm{\complement}}$ | $=$ | $\bigcup _{i\in I}}{A}_{i}^{\mathrm{\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
${(x\wedge y)}^{\prime}$ | $=$ | ${x}^{\prime}\vee {y}^{\prime},$ | ||
${(x\vee y)}^{\prime}$ | $=$ | ${x}^{\prime}\wedge {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 |