Encyclopedia > DeMorgan's Law

  Article Content

De Morgan's laws

Redirected from DeMorgan'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
Urethra

... clitoris and the vaginal opening. In the human male, the urethra is about 8 inches (200 mm) long and opens at the end of the penis. Medical problems of ...

 
 
 
This page was created in 27 ms