Famous Circuits

There are 6 standard logic gates :

                                       
     or        nor       xor       not       and      nand  

Here are the truth tables for these gates -  0 means false, 1 means true:

The  and , or , not , xor  gates represents standard logic concepts.
They can be built into microprocessors using transistors and other bipolar devices.

The  nand , nor  gates are not really "standard" logic - people don't think this way.
But these are very simple to construct, makeing cheap and efficient circuits.  
You may have seen advertisements for memory devices, saying they use
"nand" logic.  That means the cirucuits are built from nand gates.  
This is very efficient and saves money.

== NAND Gates ==

It is a fact that any circuit can be constructed using only nand gates.
To prove this fact, we show how or , and , not , xor can be constructed
from nand's.  Here are the famous circuits that prove this:  

 A  or  B           A and B     

   not A            A xor B 

The xor gate has been constructed from and, or, not.  Since those could
in turn be constructed from nand gates, it is possible to construct xor
from nand gates.  But that would be quite complex.  

== DeMorgan's Laws ==

The or circuit above is based on DeMorgan's law, which states:

      not(A or B)  =   (not A)  and  (not B)

By applying not to both sides, we get:
                                
       A or B  =  not( not A   and   not B  )  =  (not A)  nand  (not B)

Since  A nand A = not A, this is equivalent to the circuit above.

DeMorgan's other law says something similar for or (and nor):
                                  __      __        __        __
     not(A and B)  =   A  or  B    =   A   or  B
                                     __      __         __         __
         A and B  =  not( A  or  B  )  =   A   nor  B

That means the  and  gate can be consructed using nor gates,
like this:
                       A and B  

== Equivalent Expressions ==

Two Boolean Expressions are equivalent if they always produce
the same result, for any values of the variables.  
Decide whether each of the following equivalences are CORRECT.  
Recall that  AB = A and B ,  A+B = A or B.

    A nor A    =  not A     right   

    A nand B  =  (not A) and (not B)   wrong  

    (not A) or (not B)  =  not(A and B)    right  
    _____     __  __
    A + B  =  A  B        right    
                   _____
    (A + B ) ( A B )   =  A ⊕ B = A xor B    right   
                             __
    (A+B)B  =  A + B      wrong    
    __ 
    A  (A + B)  =   B      right  

== Equivalent Circuits ==

Two circuits are equivalent if they have the same truth-table -
that means they produce the same output from the same input.

There are 4 circuits below.  By "tracing" each circuit for various
values of A and B (switches), decide which two are equivalent.

== Changing Circuits to Formulas ==

If you have a drawing of a circuit (like those above)
you can write a boolean expression that means the same thing.
                              __
    Top left :  AB + B             Top right : not(not A  or  B)
                           __                                          __
 Bottom left:  A . B             Bottom right : A + B

== Truth Tables ==

Another way to represent a circuit or Boolean expression is
in a truth table.  For all possible value of the inputs, write
a line showing the corresponding output.  Here are the truth
tables for the expressions and formulas above.  

== More NAND Gates ==

It is possible to create a circuit using only nands that is
equivalent to xor.  The circuit above will be very complex,
so a simpler one is desirable.

For each of the following, decide whether it is equivalent to xor.
It might help to start by looking at the truth table for xor.

         
  no, not equivalent to xor               no, it's equivalent to nor   
 

        
      yes, this is equivalent to xor                  YES, this is equivalent to xor