Encyclopedia > DeMorgans Law

  Article Content

De Morgan's laws

Redirected from DeMorgans 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
Islip Terrace, New York

... 96.9 males. For every 100 females age 18 and over, there are 93.6 males. The median income for a household in the town is $66,644, and the median income for a family is ...

 
 
 
This page was created in 172.5 ms