BOOLEAN LOGIC EXERCISES



 1. Give a Boolean formula using only AND, OR, and NOT for the function
    of two Boolean variables x and y that is true if and only if x = y.
    Give the corresponding truth table and draw the circuit.

 2.  (a) Draw a Boolean circuit using AND, OR, and NOT gates that implements
         the function x(y + z).

     (b) 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 all three inputs are 
    the same, and 0 otherwise.

 4. Draw a Boolean circuit using AND, OR, and NOT gates that implements
    the function of three variables that is 0 if all three inputs are
    the same, and 1 otherwise.

 5. 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.

 6. A NOR gate is a logic element with two inputs that produces 1 if the
    inputs are both 0, and 0 otherwise. Show that the NOR gates is unversal,
    i.e., and logic circuit can be built using only NOR gates (and no other
    kind of gate). The logic values 0 and 1 are available as possible inputs.

     (a) Show how to implement a  NOT circuit using 1 NOR gate.
     (b) Show how to implement an  OR circuit using 2 NOR gates.
     (c) Show how to implement an AND circuit using 3 NOR gates.

 7. Assume that x = x2x1x0 consists of 3 bits.  Write a logical function
    that is true if and only if
 
     (a) x contains only one 1
     (b) when interpreted as an unsigned binary number, x is less than 3
     (c) when interpreted as a signed (two's complement) binary number, x
         is less than -1

 8. Suppose that you are given access to a n-bit decoder, and you are asked
    to implement one or more Boolean functions of n inputs. What other component(s)
    do you need?

 9. Implement a switching network that has two data inputs (A and B), two data
    outputs (C and D) and a control input (S). If S = 1, the network is in pass-
    through mode, and C should equal A, and D should equal B. If S = 0, the network
    is in crossing mode and C should equal B and D should equal A.

10. Implement a circuit that takes 16 inputs x15 to x0 and has two outputs A and B.
    Output A should be 1 if and only if x is a positive when interpreted as a 2's
    complement 16-bit integer; output B should be 1 if and only if x is equal to zero.