###
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-34 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.3) 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.4) 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.5) 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: February 3rd.

*Reminder: late assignment are penalized, 5% after noon, 10% per day
late.*
*Spring 1999*