CS 208: Computer Organization & Architecture

A bit (pardon me) of digital logic

You may work with a partner on these problems.

Submit via Moodle as a PDF file.

For the problems that ask you to draw a circuit, you may find it helpful to use one of the many freely available digital logic simulators to create and test your circuit. If you do, feel free to include a screenshot of each circuit in your write-up. Some of the simulators I've encountered are logic.ly, Logisim, and this one from Academo.

You may, if you wish, write A as A' for this assignment. A' is easier to type, and is a reasonably common ASCII notation for "not A".

  1. Proofs of Boolean algebra identities can be quite mechanical. For example, consider the absorbtion law x + xy = x. To prove this identity, you could 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 x + xy. Just by filling in the columns and comparing the x and x + xy column values, you can draw your conclusions about the truth of the identity.

    For this exercise, use a chart of this sort to prove both versions of De Morgan's Laws:

    • (A + B) = A B
    • A B = A + B.

  2. Draw a digital logic circut with three inputs A, B, and C and two outputs D1 and D0 such that D1 D0 considered as a two-bit binary number shows the number of input bits that are 1. For example, if A=0, B=1, and C=1, then D1 D0 = 1 0 (i.e. there are two 1's in the input, so the D's show the binary for two).

  3. We showed in class 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.

  4. Consider a boolean-valued function DivisibleByThree(A, B, C, D) that treats its inputs A B C D as a four-bit non-negative binary number and outputs 1 if that number is divisible by 3, and 0 if not. For example, DivisibleByThree(1, 0, 1, 1) is 0 because eleven is not divisible by 3.

    • Write a boolean algebraic formula for DivisibleByThree(A, B, C, D). Make your formula as simple as possible.
    • Explain how you derived your formula. There are multiple approaches to this question, so just explain yours.
    • Draw your formula as a circuit.
  5. 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 strictly greater than 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 "strictly greater than" for the inputs A2, A1, A0, B2, B1, B0.