Encyclopedia > De Morgan's Laws

  Article Content

De Morgan's laws

Redirected from De Morgan's Laws

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
1904

... - 21st century Decades: 1850s 1860s 1870s 1880s 1890s - 1900s - 1910s 1920s 1930s 1940s 1950s Years: 1899 1900 1901 1902 1903 - 1904 - 1905 1906 1907 1908 ...

 
 
 
This page was created in 72.8 ms