De Morgan's laws

De Morgan's Laws, named for nineteenth century logician and mathematician Augustus De Morgan, are two powerful rules of Boolean algebra and Set Theory:

P and Q = not((not P) or (not Q))

P or Q = not((not P) and (not Q))

In Boolean algebra notation:

P ∧ Q = ¬((¬ P) ∨ (¬ Q))

P ∨ Q = ¬((¬ P) ∧ (¬ Q))

Equivalently, in set notation:

A ∩ B = ( A' ∪ B')'

A ∪ B = ( A' ∩ B')'

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.

Charles Peirce showed that this result appled to logical and for intersect, logical or for union, and logical negation for complement.