Submit via Moodle as digital-logic.pdf.
You may work with a partner on these problems.
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".
Proofs of Boolean algebra identities can be quite mechanical. For example, consider the absorption law:
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:
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).
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.
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, 1, 0, 1) is 0 because thirteen is not divisible by 3.