CS 14 -- Problem set 1

Combinational Logic and Their Circuits

Answer the questions below clearly and completely. This assignment is due Monday, February 13^th at 10:00 am.

1. For each of the Boolean functions described by the truth table below:

   1. Use Karnaugh maps to derive a simplified form of the function.
   2. Draw the circuit implied by the simplified function.
   3. Draw the ROM-based circuit that would implement this function.

   a.
   	A   B   C   Output
   	------------------
   	0   0   0        1
   	0   0   1        1
   	0   1   0        0
   	0   1   1        0
   	1   0   0        1
   	1   0   1        1
   	1   1   0        0
   	1   1   1        1
   
   b.
   	A   B   C   D   Output
   	----------------------
   	0   0   0   0        1
   	0   0   0   1        1
   	0   0   1   0        1
   	0   0   1   1        0
   	0   1   0   0        0
   	0   1   0   1        0
   	0   1   1   0        1
   	0   1   1   1        0
   	1   0   0   0        1
   	1   0   0   1        1
   	1   0   1   0        1
   	1   0   1   1        0
   	1   1   0   0        1
   	1   1   0   1        1
   	1   1   1   0        0
   	1   1   1   1        1
   	

2. Convert the following formula from DNF (sum-of-products) to CNF (product-of-sums) form:

         _ _       _ _
     Y = A B C + A B C
   	

3. Prove using only algebraic manipulation that the following two expressions are equivalent:

     _     _
     A B + A C
     _     _ _
     A B + A B C