### 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.*