Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC173: Homework 5.3

Karnaugh Maps

1. Draw a Karnaugh map for the Boolean function given by the following truth table and use it to find an optimal sum-of-products expression for the function. Does your expression make sense?

ANSWER:

Expression for this (only) prime implicant: p¯q¯. This is the NOR function, so this expression makes sense. Neither p nor q can be true.

2. Draw a Karnaugh map for the NAND function and use it to find an optimal sum-of-products expression for the function. Does your expression make sense?

ANSWER:

Expression for horizontal implicant: p¯. Vertical implicant: q¯. (Both implicants are prime.) Total expression: p¯ + ¯q ⌘ pq. This makes sense for the NAND function: Either p is false or q is false. In other words, it is not the case that p and q are both true.

3. Draw a Karnaugh map for the Boolean function of three variables, p, q, and r, that is TRUE if exactly two of the three variables are TRUE. Use it to find an optimal sum-of-products expression for the function.

ANSWER:

Expression with the prime implicants from the table in left-to-right order: p¯ qr + ¯pqr+ pqr¯. This is what you would expect for “two of three,” and is also the expression you would get from the minterms technique.

4. Draw a Karnaugh map for the Boolean function of three variables, x, y, and z, that is TRUE if exactly one or two of the three variables are TRUE. Use it to find an optimal sum-of-products expression for the function.

ANSWER:

Prime implicants: xy¯ (bottom left), ¯yz (left vertical), ¯xz (left top), ¯xy (right top), yz¯ (right vertical), and xz¯ (wraparound bottom). Any set of implicants that covers all the 1’s in the table can be summed to form an equivalent expression. For example: xy¯ + ¯xz + yz¯.

12.6.1 Draw a Karnaugh map for the Boolean function of four variables, p, q, r, and s, that is TRUE if one, two, or three of the variables are TRUE but not if zero or all four are TRUE. Find the prime implicants for the map and use them to find an optimal sum-of-products expression for the function.

ANSWER:

The function is only false (0) if none of the variables are true (1) or if all of them are. So of the sixteen entries in the truth table, only the first and the last are 0. So you can write out the truth table first, as below, or just create the Karnaugh map from the specification since it’s so easy.

The Karnaugh map has only two 0’s: for 0000 and for 1111:

Per FOCS Section 12.6 (p. 667), implicants for a four-variable Karnaugh map are:

(a) Any point

(b) Any two adjacent points (2x1, horizontally or vertically, including wraparound)

(c) Any row or column (1x4 or 4x1)

(d) Any 2x2 square, including wraparound, and note: “As an important special case, the four corner points form a 2x2 rectangle.”

(e) Any 2x4 or 4x2 rectangle (half the map), including wraparound

(f) The entire 4x4 map

Prime implicants correspond to those regions that cannot be extended to larger region (less specific and therefore smaller expression). So for this example:

(a) There are single point implicants, but they do not correspond to prime impli-cants since they can all be extended to larger regions that cover no 0’s.

(b) There are 2x1 rectangles, but they can all be extended to 2x2 squares so they are also not prime.

(c) There are four rows or columns (4x1 or 1x4). They are shown below with their equivalent expressions. None of them can be extended to a 2x4 or 4x2 rectangle, so they are all prime.

(d) There are four 2x2 squares that do not wrap around and four more that do wrap around. They are also shown below. None of them can be extended to a 2x4 or 4x2 rectangle, so they are also all prime.

(e) There are no 2x4 or 4x2 rectangles that cover no 0’s.

(f) The entire map is not 1’s.

Therefore the set of twelve prime implicants for this four-variable Karnaugh map is:

Any sum of these that covers all the 1’s is an equivalent expression for the function.

For example: qr¯ + ¯ps + pq¯+ rs¯.