### 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 20th.

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 should be handed in, in hard copy, in class, next Wednesday (late homeworks must be brought to 715 B'way, 7th Floor).