### Assignment 1: Using Logisim

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, exclusive-OR, and inverter gates in your circuit.

3.    DeMorgan's Theorem (text, In More Depth 14-1)

not ( and ( x , y ) ) = or ( not ( x ), not ( y ) )
not ( or ( x, y ) ) = and ( not ( x ), not ( y ) )

Prove DeMorgan's Theorem by setting up a truth table of the form

 x y not(x) not(y) not ( and ( x , y ) ) or ( not ( x ), not ( y ) ) not ( or ( x, y ) ) and ( not ( x ), not ( y ) ) 0 0 0 1 1 0 1 1

4. 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 16th.

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