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:

$(A\cap B)^{C}=A^{C}\cup B^{C}$

$(A\cup B)^{C}=A^{C}\cap B^{C}$

De Morgan's laws, using logical operators, can be written:

$\sim (P\wedge Q)=(\sim P)\vee (\sim Q)$

$\sim (P\vee Q)=(\sim P)\wedge (\sim Q)$

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

$\sim P(\sim p,\sim q,...)$.

This idea can be generalised, to include the universal quantifier and existential quantifier in classical logic as De Morgan duals.