E15: Fundamentals of Digital Systems - Fall 2015 - HOMEWORK 6
1. Use the axioms and theorems of Boolean algebra to prove several identities involving the NAND function. Please show that for any binary value a:
a. a NAND 0 = (a0)' = 1
b. a NAND 1 = (a1)' = a
c. a NAND a = (aa)' = a
d. a NAND a' = (aa')' = 1
2. We will show using Boolean algebra that the output of a D latch (pictured below) converges to the value of the D input when the EN line is set to 1.
At time t = 0, we observe that D = 0, EN = 0, S = 1, R = 1, Q = 0, and Q' = 1. We can manually verify that this state is stable by examining the inputs and outputs of each NAND gate. Then, at t = 10 the D input is set to the binary value a. Next, at t = 20, the EN input is set to 1.
a. Finish the table by continuing to propagate the changes throughout the circuit like we did on the board in class until all variables converge, and then indicate convergence with a checkmark. You will need to use the NAND identities from the previous problem.
b. Complete a similar table for the scenario when the circuit starts out in a state with D = 0, EN = 0, S = 1, R = 1, Q = 1, and Q' = 0.
3. On a recent trip to a lab in the nation of Lower Slobbovia, Dale the digital circuit designer was shocked to find out that the lab didn't stock traditional AND and OR gates. Instead, all Dale found were NOT gates, along with an unfamiliar new gate: the SCHMAND gate.
Looking through the lab's scant documentation, Dale was able to ascertain the mathematical notion used to denote SCHMAND, as well as a truth table for the gate and the symbol used in gate diagrams:
Notice that in general, x / y ≠ y / x.
a. Does the lab have sufficient gates to implement any possible Boolean function as a circuit? If so, show that the set {NOT, SCHMAND} is logically complete by implementing AND and OR gates using only NOT and SCHMAND gates.
b. Dale needs help implementing the function
F(a, b, c) = a'b' + bc'
Draw a gate diagram for the function using only NOT and SCHMAND gates, using the fewest possible gates.