You may work with a partner on these problems.
Submit via Moodle as a zip file containing one PDF file with all your written answers, and one Logisim file (e.g. assignment4.circ) containing all the Logisim circuits requested in the assignment.
Note: 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".
As we discussed in class Friday, 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:
Get a copy of Logisim, or work in one of the CS labs on the 3rd floor of the CMC. Using Logisim, 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 Friday 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. Show your solutions in Logisim.
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.