BOOLEAN LOGIC EXERCISES

READING 
-------
Notes for lecture 11

EXERCISES
---------

 1. Draw a Boolean circuit using AND, OR, and NOT gates that implements
    the function X(Y + Z).


 2. Draw a Boolean circuit using AND, OR, and NOT gates that implements
    the function XY + XZ.


 3. Draw a Boolean circuit using AND, OR, and NOT gates that implements
    the function of three variables that is 1 if precisely two of the
    variables have the same value, 0 otherwise.


 4. Draw a Boolean circuit using AND, OR, and NOT gates that implements
    the function of four variables that is 1 if precisely two of the
    variables have the same value, 0 otherwise.


 5. A NOR gate is a logic element with two inputs that produces 1 if the
    inputs are both 0, 0 otherwise. Logic circuits can be built 
    using NOR gates (no other kind of gate).  Show how to implement
    a NOR gate with two transistors.


 6. Draw a logic circuit that uses NOR gates to implement an
    AND circuit (output 1 if both inputs are 1, 0 otherwise). 




























.
.
.
		  ANSWERS TO BOOLEAN LOGIC EXERCISES

 1. 



 2. 



 3. Unless all three are 0 or all three are 1, exactly
    two must be the same.  It's simpler to compute (NOT f), as follows:
 
       x y z  f ~f
       0 0 0  0  1      ~f = ~x~y~z + xyz
       0 0 1  1  0
       0 1 0  1  0
       0 1 1  1  0
       1 0 0  1  0
       1 0 1  1  0
       1 1 0  1  0
       1 1 1  0  1
 
 4. 
       x y z w  f       x y z w  f
       0 0 0 0  0       1 0 0 0  0
       0 0 0 1  0       1 0 0 1  1
       0 0 1 0  0       1 0 1 0  1
       0 0 1 1  1       1 0 1 1  0
       0 1 0 0  0       1 1 0 0  1
       0 1 0 1  1       1 1 0 1  0
       0 1 1 0  1       1 1 1 0  0
       0 1 1 1  0       1 1 1 1  0

  f = ~x~yzw + ~xy~zw + ~xyz~w + x~y~zw + x~yz~w + xy~z~w

 5. 





 6.