De Morgan's laws
In
logic,
De Morgan's laws (or De Morgan's theorem), named for nineteenth century logician and mathematician
Augustus De Morgan, are the two rules of
propositional logic,
boolean algebra and
set theory
- not (P and Q) = (not P) or (not Q)
- not (P or Q) = (not P) and (not Q)
which allow to move a negation over a conjunction or a disjunction.
In formal logic the laws are usually written
and in set theory
Common uses of De Morgan's rules are in
digital circuit design, where it is used to manipulate the types of logic gates, and in formal logic, where it is one of the rules used to transform logical formulae into
negation normal form, a prerequisite for
conjunctive or
disjunctive normal form. They are also often useful in computations in elementary
probability theory.
Each propositional expression P(p, q, ...) depending on elementary propositions p, q, ... has a De Morgan dual in which each elementary proposition is replaced by its negation and conjunction and disjunction are interchanged. It can be written as
This idea can be generalised to include the
universal and existential quantifiers in classical logic as De Morgan duals.