You are here
Home ›de 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 and are subsets of a set , de Morgan’s laws state that
Here, denotes the union, denotes the intersection, and denotes the set complement of in , i.e., .
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 is not in and not in . It also states that an elements not in and not in is not in .
For an arbitrary collection of subsets, de Morgan’s laws are as follows:
Theorem. Let be a set with subsets for , where is an arbitrary index-set. In other words, can be finite, countable, or uncountable. Then
(proof)
de Morgan’s laws in a Boolean algebra
For Boolean variables and in a Boolean algebra,
de Morgan’s laws state that
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 Axiomatics of classical set theory and its fragments- 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
Recent Activity
new question: pure subgroups by lvoyster
new correction: Typo in M\"obius function? by Aleph Zero
new collection: analytic number theory by Aleph Zero
May 20
new question: Taylor's Series Query! by unlord
new question: Laplace transform by J
new question: Residue Calculus by J
May 19
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden


