Computers: Defining Logical Operations

Date: 05/21/98 at 09:40:34
From: Towella
Subject: AND, OR, XOR, NAND, NOR, NOT

Hi. I was referred to your site and while here tried to find an 
explanation for the terms:

   AND, OR, XOR, NAND, NOR, NOT

but was unsuccessful. If there is a any way that I could get a brief 
definition or even an example of what these do, I would be eternally 
grateful!  

Thanks, 
Towella

Date: 05/22/98 at 13:12:29
From: Doctor Jeremiah
Subject: Re: AND, OR, XOR, NAND, NOR, NOT

Hi Towella:

I am a computer engineer and these logical operations are basically 
all a computer knows how to do at the very lowest level. Everything 
else is made from these operations.

   AND is a multi-input operation that returns true when all the 
       inputs are true and returns false the rest of the time.

   OR  is a multi-input operation that returns true when at least one  
       or even more than one input is true and returns false the rest 
       of the time.

   NOT is a single input operation that returns the opposite of the 
       input.

A truth table can be used to show all the combinations of inputs 
and outputs. For these truth tables A and B are the inputs and Y is 
the output:

           AND                        OR                     NOT      

      A     B   |   Y           A     B   |   Y           A   |   Y   
   -------------+-------     -------------+-------     -------+-------
    False False | False       False False | False       False | True 
    False True  | False       False True  | True        True  | False  
    True  False | False       True  False | True                  
    True  True  | True        True  True  | True                  

See how AND is only true when all the inputs are true and how OR is 
true whenever any of the inputs are true?

   NAND is a NOT on the output of an AND. So it has the exact opposite 
        output as an AND would have.

   NOR  is a NOT on the output of an OR.  So it has the exact opposite 
        output as an OR would have.

          NAND                          NOR          

      A     B   |   Y              A     B   |   Y   
   -------------+-------        -------------+-------
    False False | True           False False | True  
    False True  | True           False True  | False 
    True  False | True           True  False | False 
    True  True  | False          True  True  | False 

See how the NAND is true unless all the output are true and how NOR is 
true whenever all the outputs are false.

   XOR  is true whenever an odd number of inputs is true.
   XNOR is the opposite output from XOR.

           XOR                         XNOR          

      A     B   |   Y              A     B   |   Y   
   -------------+-------        -------------+-------
    False False | False          False False | True  
    False True  | True           False True  | False 
    True  False | True           True  False | False 
    True  True  | False          True  True  | True  

There is such a thing as boolean algebra where you can solve equations 
made up of logical operations. It looks a lot like regular algebra. 
It is used by computer engineers when designing circuits.

   AND is expressed the same as multiplication would be.
   OR  is expressed the same as addition would be (with a plus sign).
   NOT is expressed with an apostrophe.
   XOR is expressed as a plus sign with a circle around it.

And like regular algebra has multiplication set to a higher precedence 
than addition, boolean algebra does the same with the AND function.

So Y = AB' + A'B is:

   A ANDed with the inverse (NOT) of B and then ORed to the output of  
   the NOT of A ANDed with B.

This means that:

   Y is true if A = true and B' = true. 
   Y would also be true if A' = true and B = true.

The reason that there are two independent cases is because of the OR. 
Remember that A' is the NOT (inverse) of A and B' is the NOT of B.
If we take that into account we can change it to:

   Y is true if A = true and B = false. 
   Y would also be true if A = false and B = true.

If you look carefully at the truth table of XOR you will notice that 
the previous statement IS the definition of XOR.

XNOR would be Y = (AB' + A'B)' 

See the NOT around the whole expression?

I hope that helps. If you need more details please write back.

-Doctor Jeremiah,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/