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 two powerful rules of boolean algebra and set theory:
- not (P and Q) = (not P) or (not Q)
- not (P or Q) = (not P) and (not Q)
This law can be expressed using analogous set notation: this was done first by Charles Peirce:
De Morgan's laws, using logical operators, can be written:
De Morgan's theorem has profound applications in electrical engineering and discrete mathematics.
These can be proved simply: either carefully following the process of taking complements with a Venn diagram suffices or using a truth table like this:
p q | not(p or q) | not(p) and not(q)
+--------------+------------------
T T | F | F
T F | F | F
F T | F | F
F F | T | T
p q | not(p and q) | not(p) or not(q)
+--------------+------------------
T T | F | F
T F | T | T
F T | T | T
F F | T | T
This simple fact is used extensively in digital circuit design for manipulating the types of logic gates used by the circuit.
A propositional expression P(p, q, ...) depending on elementary propositions p, q, ... has a De Morgan dual in which, roughly speaking, conjunction and disjunction are interchanged. We can write it as
 .
This idea can be generalised, to include the universal quantifier and existential quantifier in classical logic as De Morgan duals.
Referenced By
Digital Circuit | List of basic discrete mathematics topics | List of mathematical topics (D-F) | List of mathematical topics (F-Z) | List of topics in logic | Universal set | Universe (math) | Universe (mathematics) | Universe (set) | Universe (set theory) | Universe (sets) | Universe set
|
