# Section 1.6: Problem 3 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Repeat (a) and (b) of Exercise 2, but for the formula

We need to (a) find all prime implicants of the formula, and (b) find all disjunctions of prime implicants that are tautologically equivalent to the formula.

(a) Let us call the formula
. We consider when
is assigned
. If
, then the right hand side is
, and the left hand side should be
as well, but its first term is
, meaning that the second term should be false, i.e.
and
. Now, assume
. We need the left hand side to be
or the right hand side to be
. If
, then the left hand side is
. Assume
. The expression we have so far is
, which is tautologically equivalent to
,
,
, i.e.
. Hence, here are the values for
,
,
and
for which
is true:

If an implicant
of
consists of some literals, then
must be true when each literal is true, regardless of the values of other variables. And a prime implicant is such that there is no proper sub-implicant. In our case, a single literal would be an implicant iff there would be eight same values (
or
) in some column (corresponding to eight possible values of the other variables), which is not the case. Now, in order for there to be a literal using
and
only, columns
and
must have a submatrix
such that values in each column are the same. We see, that there is such a submatrix, namely, the rows 5-8. These four rows correspond to all the possible values of the other variables
and
. The values in the two columns of the submatrix are
and
, therefore, the corresponding prime literal is
(5,6,7,8). Here, in parentheses we list rows used to construct the implicant, as we will need this later and in (b). Similarly,
(1,2,5,6),
(1,3,5,7) and
(2,4,6,9) are the other prime implicants that use two literals only. Now, other implicants would necessary consist of at least three literals, corresponding to
submatrices having same values in each column. Here, to find prime implicants, we should not consider submatrices that correspond to the values already found before. For example, since
is an implicant, so is
etc. But these are not prime. Another way of doing this is as follows. Suppose we are looking for implicants involving
,
and
. Then we look at the previously found implicants that involve some of these literals. Namely, we have two such implicants,
and
. These implicants have already covered all rows except for 3, 4 and 9. Therefore, our only possibility to find a prime implicant would be in these rows. But they don’t have a new one. Similarly, it is easy to see that there are no new prime implicants consisting of three literals. Finally, the prime implicants involving all four literals correspond to
submatrices in the rows that were not covered so far. There are no such rows. Overall, the prime implicants of
are
(5,6,7,8),
(1,2,5,6),
(1,3,5,7) and
(2,4,6,9).

Note, how these implicants correspond to what we said. Suppose
is true. If
then only the last implicant can be true, but then
should be true. Now, assume
. Then, either
(the first implicant), or
is true.

(b) Again, as in the previous exercise, those combinations of prime implicants that cover all rows of the matrix, are the ones that are tautologically equivalent to
. In particular, we need the first one as the only one that contains row
, the third one containing row 3, and the fourth one containing rows 4 and 9. Therefore, the only two disjunctions of prime implicants that are tautologically equivalent to
are
, and the disjunction of all four prime implicants.