Homework 2
Boolean Algebra and Digital Logic

Due: Tuesday, November 7, 2006 at 9am

Outcomes

• construct a logic diagram from a truth table, and vice versa
• minimize a circuit using a Karnaugh map
• explain the difference between combinational and sequential circuits
• show how logic gates are combined to form a simple ALU
• show how logic gates are combined to form a simple memory
• draw a state diagram for a simple finite state machine

Before Starting

Format and Submission of Assignment

Problems

1. (10 points) Use a Karnaugh map to minimize the function F on 3 variables given by:

   F(a,b,c) = abc' + ab'c' + a'bc + a'bc'
   

   Make sure your Karnaugh map is clearly labelled. (You don't have to draw the circuit, just use the Karnaugh map to come up with an equivalent minimal Boolean equation.)

2. (10 points) Minimize the function F from problem 1, but this time do it by applying the postulates and theorems of Boolean Algebra (the postulates (P1 through P6) and theorems (Th1 through Th16) are listed on pages 44 and 45 of this pdf file). Here are the first couple of steps to get you started. Don't combine any steps (each step should follow from a single application of one of the postulates or theorems).

              step                             reason
              ----                             ------
   
   F(a,b,c) = abc' + ab'c' + a'bc + a'bc'      given
   F(a,b,c) = a(bc' + b'c') + a'bc + a'bc'     P4 (distributive law)
   .                                           .
   .                                           .
   .                                           .        
   

3. (5 points) Do problem 3.12 from the textbook.

4. (10 points) Do problem 3.24 from the textbook.

5. (10 points) A 4-bit comparator is a component that takes two four-bit words as inputs and produces a single bit of output. The output is 0 if the words are identical, and is a 1 otherwise. Design a 4-bit comparator using AND, OR, and NOT gates. (Hint: Think of the 4-bit comparator as four 1-bit comparators combined in some fashion.)

6. (10 points) Draw the logic diagram of a 2-bit demultiplexer, a circuit whose single input line is steered to one of the four output lines depending upon the state of the two control lines.

7. (30 points) People have any one of four blood types - A, B, AB, and O. Type O can donate blood to any type but receive only from O. Type AB can receive blood from any type but can donate only to AB. A can donate to A or AB and receive from A or O. B can donate to B or AB and receive from B or O. You will design a logic circuit that will accept as inputs the blood types of a desired donor-receiver pair and will output 1 if the transfusion is permissible by these rules.

   To get you started, note that you need 2 bits to be able to uniquely identify each of the four blood types. Use the following table to define the blood types:

   0	0	O
   0	1	B
   1	0	A
   1	1	AB

   • a). Construct a truth table for the transfusion function that represents each possible donor-receiver pair (your table will have four inputs and one output).
   • b). Construct a Karnaugh map for the truth table in part (a). Make sure your Karnaugh map is clearly labelled.
   • c). Write a minimal sum-of-products expression for the function.
   • d). Draw a circuit to implement the expression from part (c).

8. (5 points) The 4 x 3 memory pictured in Figure 3.21 in the textbook uses 20 AND gates and 3 OR gates. If the memory were to be expanded to 256 x 8, how many of each kind of gate would be needed?

9. (10 points) Do problem 3.42 from the textbook.