G22.2233 - Prof. Grishman

Assignment 1:  Combinational Circuits and Universality

1. Prove DeMorgan's theorems using a truth table (text problem B.6, page B-46;  see the text for a fuller explanation).

2. Demonstrate that the NAND gate is universal by constructing AND, OR, and NOT gates from two-input NANDs.

You will be provided with a version of the simulator which includes Nand2, a 2-input NAND, as a primitive (see link below).  You are to define classes And2, Or2, and Not:
        Not (Wire out, Wire in)
    And2 (Wire out, Wire in0, Wire in1)
    Or2 (Wire out, Wire in0, Wire in1)
3. Using AND, OR, NOT, and NAND, create Modules for exclusive-OR, a 2-input multiplexer, and a full adder.
You are to define additional classes Xor2, Mpxr2, and FullAdder:
     Xor2 (Wire out, Wire in0, Wire in1)
     Mpxr2 (Wire out, Wire in0, Wire in1, Wire sel)
          [here if sel=0 then out=in0;  if sel=1 then out=in1]
     FullAdder (Wire Cout, Wire S, Wire A, Wire B, Wire Cin)
You should send email to grishman@cs.nyu.edu which contains the proof of DeMorgan's theorem in the body of the message and a single attachment containing the definitions of the 6 Java classes. The subject line of the message should be "Assignment 1".  It will be easier for me if the attachment file name is yourname.java.

This assignment is due February 25th, and is worth 7 points towards your final grade.  There is a penalty of 1/2 point for each school day the assignment is late.

Extra credit (2 points):  suppose you are given only Mpxr2 as a primitive.  Show how Not, And2, and Or2 can be built from this primitive.  You must write the Mpxr2 Primitive class definition (modeled on the Nand2 Primitive in the supplied simulator) and class definitions for Not, And2, and Or2 using this primitive.  If you do the extra credit, send it as a separate mail message, with subject line 'Assignment 1 - extra credit' and a single attachment with file name yournameX.java containing the four class definitions.

Simulator for Assignment 1release 1.0