De Morgan's Laws

Date: 09/21/2000 at 19:40:51
From: Brandan Placke
Subject: De Morgan's Law

What is "De Morgan's Law"?

Date: 09/22/2000 at 09:41:34
From: Doctor Twe
Subject: Re: De Morgan's Law

Hi Brandan - thanks for writing to Dr. Math.

DeMorgan's Laws (a.k.a. DeMorgan's Theorems) have several variations, 
depending on what branch of mathematics you're studying. They state a 
relation between the set operations intersection, union, and 
complement, or a relation between the logic operations AND, OR and NOT 
(or complement); or a relation between the digital electronics 
circuits AND gates, OR gates, NAND gates, NOR gates, and inverters.

As Set Theorems, they state:

     ~(AUB) = ~A^~B 
     ~(A^B) = ~AU~B 

where ~A means "the complement of A," A^B means "A intersect B," and 
AUB means "A union B."


Similarly, as Logic Theorems, they state:

     ~(A+B) = ~A.~B 
     ~(A.B) = ~A+~B 

where ~A means "not A," A.B means "A and B," and A+B means "A or B."

This allows us to "distribute" the not function and get rid of the 
parenthesis (but note that the operation inside the parenthesis - the 
AND or OR - changes.)

Essentially, we have just changed the complement function to the NOT 
function, intersection to AND, and union to OR. These are equivalent 
operations on different data types.

Finally, in Digital Electronics, they define the equivalence for the 
NAND and NOR gates. (The Boolean expressions would be written as 
above.) The first one states that a NOR gate can be replaced with an 
AND gate with inverters on each input or vice-versa:
         ______                    _____
     A __\     \             A --o|     \
     B __ )     >o-- X   =        |      )-- X
         /_____/             B --o|_____/

The second one states that a NAND gate can be replaced with an OR gate 
with inverters on each input or vice-versa:
          _____                   ______
     A __|     \             A --o\     \
     B __|      )o-- X   =         )     >-- X
         |_____/             B --o/_____/

These are useful replacements, especially when simplifying a circuit 
design.

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/