CS 220 - Appendix C - Logic Design Solutions

• C.5: Prove that the NOR gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NOR gate

  The logic equation for a NOR gate is $\overline{A+B}$.

  • To implement a NOT gate using only a NOR gate tie the two inputs together; then $A = B$ and $\overline{A+A} = \overline{A}$ which is the same as a NOT gate.
  • To implement an OR gate using only NOR gates we take a NOR gate and not the output using the construction above. By DeMorgan's $A+B=\overline{\overline{A+B}}$
  • To implement an AND gate using NOR gates we take a NOR gate and negate each input with another NOR gate. By DeMorgan's $AB=\overline{\overline{A}+\overline{B}}$
• C.6: Prove that the NAND gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NAND gate

  Very similar to answer above. remind me in class and I'll do this one in class.

• C.7: Construct the truth table for a four-input odd-parity func- tion (see page C-65 for a description of parity).

  The table is below. The inputs are labeled A3 to A0 with the output labeled F.

  
• C.8: Implement the four-input odd-parity function with AND and OR gates using bubbled inputs and outputs.

  The circuit is below, without any minimization. It is just a pure implementation of the sum-of-products form. This circuit doesn't need any bubbled outputs, and instead of the bubbled inputs it uses an explicit not gate. MMLogic doesn't allow us to draw circuit using a bubbled input, which a commercial product might support.