###
CSCI-UA.0436 - Prof. Grishman

###
Assignment 1: Using Logisim

0. Download Logisim and go through the tutorial.

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.

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

3. If each gate in the circuit (from question 2) has a
delay
of 2 ns, what is the delay of your circuit?

4. Design a circuit which takes as input a 4-bit unsigned
integer X_{3}X_{2}X_{1}X_{0} and
outputs a 1 if and only if X > 11. You may draw the
circuit
using Logisim or by hand. (Hint: what do all the input
patterns which produce a 1 output have in common?)

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.

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.

#### Extra credit

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 19^{st} (until midnight)

How to hand this in: For part 2, email the Logisim circuit as
an
attachment. Mail your homework to grishman@cs.nyu.edu and smj340@cs.nyu.edu;
mark
the mail CompArch -- Asgn 1
. The remaining parts may be sent electronically or may be
handed
in, in hard copy, in
class, next Wednesday (late homeworks in hard copy must be brought
to 715
B'way, 7th
Floor).