CS 208: Computer Organization and Architecture

A little digital logic

You may work together on these problems, but please hand in your work (on paper) individually.

  1. Proofs of Boolean algebra identities can be quite mechanical. For example, consider the absorbtion law x + xy = x. You can set up a chart whose rows correspond to all the possible combinations of the variables x and y (x=0, y=0 is the first row; x=0, y=1 is the second row; etc.). Then add a column to your chart for xy, then a column for x + xy. Fill in the columns and draw your conclusions. Use a chart of this sort to prove both this absorbtion law and the other one: x(x + y) = x.
  2. We showed in class the other day that you can implement any boolean function using a collection of AND, OR, and NOT gates. That is to say, the collection of AND, OR, and NOT is universal. Show that NAND is, all on its own, universal. You can do this by showing how to build an AND gate, an OR gate, and a NOT gate using combinations of NAND gates.
  3. Draw a digital logic circut with three inputs A, B, and C and one output D such that D is 1 if an odd number of the inputs are 1, and D is 0 otherwise.
  4. Suppose you have two three-digit binary numbers A2 A1 A0 and B2 B1 B0 (treated as ordinary non-negative numbers, not two's complement). The function "A is less than or equal to B" is a 1-bit boolean-valued function of six inputs. Therefore, you could use the technique we used in class to implement this function: create a chart showing the output for all the possible inputs, make the input lines and their NOTs vertical lines on the left, then wire those input lines to AND gates appropriately, and finally dump all the AND outputs into a big OR. If you followed this procedure:
    • How many rows would your chart need to have?
    • How many AND gates would your chart have?
    • How many inputs would each AND gate have?
    • How many inputs would the OR gate have?
    • And finally: instead of creating this big chart and circuit, write out a boolean algebraic formula that represents "less than or equal to" for the inputs A2, A1, A0, B2, B1, B0.