CSE370 Assignment 2

Distributed: April 7, 2010
Due: April 14, 2010


Reading:

  1. Katz/Borriello, Contemporary Logic Design 2e, review Chapter 2 section 4 and 5 (pp. 56-76).
  2. Katz/Borriello, Contemporary Logic Design 2e, Chapter 3 section 1 and 2 (pp. 93-114).

 

Exercises:

1)      Show that an n-input AND gate can be replaced by n-1 2-input AND gates.  Can the same statement be made for NAND gates?  Justify your answer.

2)      A self-dual logic function is a function F such that F = FD.  Which of the following functions are self-dual?

a)      F = A

b)      F = AB’ + A’B

c)      F(A,B,C) = ∑ (0, 3, 5, 6)

d)     Majority function (function of any odd number of variables where more than half are 1 – also known as the voting function)

3)      Write the canonical sum and product for:

a)      F(A,B,C) = ∑ (2, 4, 6, 7)

b)      F = A + B’C’

4)      Find the minimal sum-of-products and minimal product-of-sums expressions for each of the following logic functions:

a)      F(A,B,C) = ∑(1, 3, 5, 6, 7)

b)      F(A,B,C,D) = ∑(1, 4, 5, 7, 12, 14, 15)

5)      Can you find a cheaper expression for 4b using more than 2 levels of logic?

6)      Show that there may be more than one minimal sum-of-products expression for a given Boolean expression.

7)      CLD-II, Chapter 2, problem 2.21

8)      CLD-II, Chapter 2, problem 2.26, part c.

9)      CLD-II, Chapter 3, problems 3.1, part b.

10)   CLD-II, Chapter 3, problems 3.3/3.4, part c.

11)   [Extra credit] Prove the general deMorgan’s law using finite induction.

 

Rationale:

  • To practice and gain facility with Boolean algebra.
  • To appreciate canonical representations of Boolean functions.
  • To begin applying minimization techniques using Karnaugh maps.

 

Comments to: cse370-webmaster@cs.washington.edu