V22.0436 - Prof. Grishman

Assignment 1: Combinational Circuits and Universality

1. Construct the truth table for a 3-input odd-parity circuit: a circuit with three inputs and one output, where the output is 1 if and only if an odd number of the inputs are 1. (See page B-33 of the text for a discussion of the role of parity.)

2. Draw a schematic of a 3-input odd-parity circuit. You may use AND, NAND, OR, NOR, exclusive-OR, and inverter gates in your circuit.

3. (text, B.6) Prove DeMorgan's theorems using a truth table (see the text for a fuller explanation).

4. (text, B.10) Prove that the NOR gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NOR gate.

Hint: first build an inverter from a NOR gate. Then use inverters and NOR gates to construct an OR gate and to construct an AND gate. You will need DeMorgan's theorem to build the AND gate.

5. (text, B.11) Prove that the NAND gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NAND gate.

Extra credit

(text, B.12) Prove that a two-input multiplexer is also universal by showing how to build the AND, OR, and NOT functions using a multiplexer.

Due in one week: September 17th.

Reminder: late assignment are penalized 10% per day late.