Wikipedia: De Morgan's laws

De Morgan's laws
From Wikipedia, the free encyclopedia.

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.