CSE 370 Solution Set #3
Spring 1999
Total Points 20

Problem 1 - 6 points - 1 each for b-g

    a. F = ((A + B)C + ABC)

    b. The truth table is shown below 
A B C (A+B') (A+B')C A'BC' ((A + B)C + ABC)
             
0 0 0 1 0 0 1
0 0 1 1 1 0 0
0 1 0 0 0 1 0
0 1 1 0 0 0 1
1 0 0 1 0 0 1
1 0 1 1 1 0 0
1 1 0 1 0 0 1
1 1 1 1 1 0 0
    c. F(A,B,C) = Sigma m(0,3,4,6)

    d. It is much easier to reduce this when starting with the SOP expression you derived with the truth table. Because of the regular order of terms associated with SOP form it is often the case that it's easier to reduce

    F(A,B,C) = A'B'C' + A'BC + AB'C' + ABC'
                 = A'B'C' + A'BC + AB'C' + ABC' + AB'C'    Idempotent
                 = A'B'C' + AB'C' + A'BC + ABC' + AB'C'     Commutative
                 = (A'+ A)B'C' + A'BC + AC'(B + B')              Distrubutive
                 = (1)B'C' + A'BC + AC'(1)                       Complementarity
                 = B'C' + A'BC + AC'                              Identity

    e. f = AC' + A'BC + B'C'
hw3_1e.gif (2052 bytes)

    f. After switching the 1's and 0's in the K-map : f = AC + A'BC' + B'C
hw3_1f.gif (2052 bytes)

    g. 



Problem 2 - 0 points - Katz 2.19a

    f(w,x,y,z) = w'x' + x'y'
hw3_2.gif (2052 bytes)



Problem 3 - 4 points - Katz 2.20c,d

    It's important to notice here that the question ask for the Product-of-Sums expression. Many of you didn't do this. To get obtain the product of sums expression from a k-map circle the rectangles of either the minterm 0's or the maxterm 1's (same set), then read their inverted values from the k-map, This is just an automatic way of applying Demorgans law. This problem asked you to use the K-map method, so if you just converted the SOP form you lost points. I didn't mark off for taking the complement of the SOP form and then apply demorgans by hand, this is the same thing you do from the K-map, it just involves an extra unnecessary step.

    f(a,b,c,d) = d(a'+ c') (notice I circled the minterm 0's)
hw3_2.gif (2052 bytes)

    f(a,b,c,d) = (a + b' + c')(a + b + c) (notice I circled the maxterm 1's)
hw3_2.gif (2052 bytes)



Problem 4 - 2 points - Katz 2.24

    It was not okay to use K-maps with don't cares in them. The problem asked for two different expressions for the same k-map, but when don't cares are used, the actual k-map changes depending on how the don't cares are used. In the k-map below the vertical rectangle can be located so it covers either the upper horizontal rectangle, resulting in diffent expressions for the SAME k-map. This was the correct approach to the problem.
hw3_4.gif (2052 bytes)



Problem 5 - 2 points - Katz 2.27

    a) Truth Table
A B C D 08  04  02  01 
               
0 0 0 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1
0 0 1 1 0 1 0 0
0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0
0 1 1 0 0 1 1 1
0 1 1 1 1 0 0 0
1 0 0 0 1 0 0 1
1 0 0 1 1 0 1 0
1 0 1 0 1 0 1 1
1 0 1 1 1 1 0 0
1 1 0 0 1 1 0 1
1 1 0 1 1 1 1 0
1 1 1 0 1 1 1 1
1 1 1 1 0 0 0 0



hw3_5a.gif (2052 bytes)

    O8 SOP- f(a,b,c,d) = ab' + ac' + ad' + a'bcd'

    O8 POS- f(a,b,c,d) = (a+b)(a+c)(a+d)(a'+b'+c'+d')


hw3_5b.gif (2052 bytes)

    O4 SOP- f(a,b,c,d) = bc' + bd' + b'cd

    O4 POS- f(a,b,c,d) = (b+c)(b+d)(b'+c'+d')


hw3_5c.gif (2052 bytes)

    O2 SOP- f(a,b,c,d) = c'd + cd'

    O2 POS- f(a,b,c,d) = (c+d)(c'+d')


hw3_5c.gif (2052 bytes)

    O1 SOP- f(a,b,c,d) = d'

    O1 POS- f(a,b,c,d) = d'


    c. They both have the same number of literals (22).



Problem 6 - 4 points - Katz 2.29 Except for an even number of 1'

    a. Truth Table:
A B C D
         
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1


hw3_6.gif (2052 bytes)

    f(a,b,c,d) = a'b'c'd' + a'b'cd + a'bc'd +a'bcd' + abc'd' + ab'cd' + ab'c'd + abcd

    Because each of these minterm differs by at least 2 bits from its nearest neighbor it cannot be simplified using a k-map. Spacing like this results from the XOR function and is a good clue that XOR's can be used to make a cheap implemetation.

    c. f = (a XOR b XOR c XOR d)' == a XOR b XOR c XOR d XOR 1 



Problem 7 - 2 points

    a. Truth Table:
A B C D X
         
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1


    F = a'b+a+c'+d' = ((a'b)'a'bc)'

See picture below.
    



Problem 8 - 0 points

 
  This was the most popular solution, but the most optimal solution is 0 (must be a misprint in the book - the ciruit goes to 0)