Assignment 3

 

Reading Assignment: Notes for Week 3. Chapter 2 of Brown and Vranesic.
Notes: For all exercises using Boolean algebra in the following, show all the steps and state explicitly all axioms/theorems/properties that you used. 

 

 

  1. (12 points) Consider the circuit below.

 

 

(a)    Write a truth table for the circuit.

(b)   Write a logic expression for the circuit.

 

  1. (18 points) Prove the equality (a+b).a' + c.b = (a'+c).b using

 

(a)    Truth Table;

(b)   Boolean algebra;

(c)    Its dual theorem in Boolean algebra.

 

  1. (20 points) Consider the logic function f (a, b, c) = a'bc' + a'b'c + a'bc + ab'c + a’b’c’.

(a)    Draw the logic circuit for the function f given above.

(b)   Let the cost of a logic circuit be the total number of gates plus the total number of inputs to all gates in the circuit. What is the cost of the circuit in (a)?

(c)    Simplify f using Boolean algebra as much as possible.

(d)   Draw the logic circuit for the simplified version of f in (c).

(e)    What is the cost of the circuit in (d)?

  1. (28 points) A function f has four inputs a, b, c, d and one output such that the output is a 1 if and only if the number of 1s in the inputs is even.

(a)    Derive the truth table for f.

(b)   Write the canonical sum-of-products expression for f. Do not use the shorthand notation.

(c)    Write the canonical sum-of-products expression for f in shorthand notation.

(d)   Write the canonical product-of-sums expression for f. Do not use the shorthand notation.

(e)    Write the canonical product-of-sums expression for f in shorthand notation.

(f)     Write the canonical sum-of-products expression for f' in shorthand notation.

(g)    Write the canonical product-of-sums expression for f' in shorthand notation.

  1. (12 points) Let f (a, b, c) = a + b' + c'.

(a)    What is the canonical sum-of-products expression for f? Explain how you get the answer.

(b)   Write a simplest sum-of-products expression (not necessary to be canonical) for f?

(c)    What is the canonical product-of-sums expression for f? Explain how you get the answer.

  1. (10 points) Implement the function for the three-way light control (Figure 2.24):

(a)    using only NAND gates.

(b)   using only NOR gates.