Encyclopedia > De Morgan's law

  Article Content

De Morgan's laws

Redirected from De Morgan's law

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
David McReynolds

... by Paul Buhle: Nonviolent Activist. 1999, May 01 - "Annual Dinner And Peace Award Ceremony: A Celebration Of David McReynolds" - Pamphlet: War Resisters League. ...

 
 
 
This page was created in 38.8 ms