De Morgan's laws
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.
The rules can be expressed in English as:
- The negation of "A and B" is the same as "not A or not B".
- The negation of "A or B" is the same as "not A and not B".
or
- The complement of the union of two sets is the same as the intersection of their complements
- The complement of the intersection of two sets is the same as the union of their complements
or
- not (A or B) = (not A) and (not B)
- not (A and B) = (not A) or (not B)
where "A or B" is an "inclusive or" meaning at least one of A or B rather than an "exclusive or" that means exactly one of A or B.
Another form of De Morgan's law is:
Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan's laws are an example of a more general concept of mathematical duality.