De Morgan's laws

DeMorgan's Law, named for nineteenth century logician and mathematician Augustus DeMorgan, is a powerful rule of Boolean algebra and Set Theory. It can be expressed as a pair of equations:

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

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

Equivalently, in set notation:

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

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

These can be proved simply: carefully following the process of taking complements with a Venn diagram suffices.

This simple fact is used extensively in digital circuit design for manipulating the types of logic gates used by the circuit.