Homework 2
Boolean Algebra and Digital Logic

Due: Tuesday, November 9, 2010 at 9am


After successfully completing this assignment, you will be able to...

Before Starting

Read Chapter 3.

Format and Submission of Assignment

The solution for this assignment must be submitted as hard-copy at the beginning of class (9am) on November 9. All papers must be stapled together, and your name and login name must appear at the top of every sheet. Handwriting must be legible - if we can't read it, the grade is zero.


  1. (10 points) Draw the truth table for the circuit pictured here:

  2. (10 points) A function F on 3 variables is given by:
    F(a,b,c) = a'b'c + a'bc + abc + abc'
    This function can be minimized to two terms. Determine a minimal function Fmin that produces the same output (i.e. is equivalent to) the function F (you should be able to determine a minimal function by inspection).

  3. (10 points) Start with the same function F again, as defined in Problem 2. Show how to obtain the minimized function Fmin by applying the postulates and theorems of Boolean Algebra (the postulates (P1 through P6) and theorems (Th1 through Th16) are listed on pages 2 and 3 of this .pdf file; the numbers on the bottom of the pages are 44 and 45). Here are the first couple of steps to get you started. Don't combine any steps (each step should follow from a single application of one of the postulates or theorems).
               step                             reason
               ----                             ------
    F(a,b,c) = a'b'c + a'bc + abc + abc'        given
    F(a,b,c) = a'(b'c + bc) + abc + abc'        P4 (distributive law)
    .                                           .
    .                                           .
    .                                           .                                .

  4. (10 points) In class we showed that AND and NOT are functionally complete. We then showed that NAND is also functionally complete, by designing the functions AND and NOT using only NAND gates.

    Draw a logic diagram for a circuit that computes A OR B. Your circuit may use only NAND gates.

  5. (10 points) In class we saw how to construct a black box representation of a 4-to-1 MUX built from three 2-to-1 MUXes. Suppose you want a MUX where you select 2 bits at a time, instead of 1 bit. For example, you might want to select either of the inputs x1x0 or y1y0. Since you're only selecting one of two inputs, you should still use only one control bit, but now instead of 1 output bit, you will have 2.

    Draw a black box representation of a 2-to-1 two-bit MUX that is implemented using two 2-to-1 one-bit MUXes. Follow the conventions we used in class for representing black boxes.

  6. (15 points) Do problem 3.24 from the textbook.

  7. (15 points)

  8. (20 points) The Muller C-Element is a sequential circuit that behaves as follows: the output of the circuit reflects the inputs when the states of all inputs match. The output remains in this state until the inputs all transition to the other state. Here is a characteristic table for a two-input Muller C-Element:
          A  B  |  Q(t+)
          0  0  |  0
          0  1  |  Q(t)
          1  0  |  Q(t)
          1  1  |  1