V22.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, 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).