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) .
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:
Not surprisingly, de Morgan’s laws form an indispensable tool when simplifying digital circuits involving and, or, and not gates .
- 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|
|Date of creation||2013-03-22 12:24:49|
|Last modified on||2013-03-22 12:24:49|
|Last modified by||mathcam (2727)|