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