Section 1.6: Problem 2 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
Define a literal to be a wff which is either a sentence symbol or the negation of a sentence symbol. An implicant of
is a conjunction
of literals (using distinct sentence symbols) such that
. We showed in Section 1.5 (cf. Corollary 15C) that any satisfiable wff
is tautologically equivalent to a disjunction
where each
is an implicant of
. An implicant
of
is prime iff it ceases to be an implicant upon the deletion of any of its literals. Any disjunction of implicants equivalent to
clearly must, if it is to be of minimum length, consist only of prime implicants.
(a) Find all prime implicants of
.
(b) Which disjunctions of prime implicants enjoy the property of being tautologically equivalent to the formula in part (a)?
(a) Let us call the formula
. Then,
is assigned
iff both terms are assigned
iff
implies
and
implies
. This is the conditional ternary connective. 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 four same values (
or
) in some column (corresponding to four possible values of the other variables), which is not the case. Now, columns
and
have a submatrix
such that values in each column are the same (the first two rows). These two rows correspond to all the possible values of the other variable
. Since the values are
and
in the two columns of the submatrix,
is a prime implicant. Similarly,
is another prime implicant (the last two rows of the columns
and
). Finally,
is also a prime implicant (the first and last rows of the columns
and
). Now, other implicants would necessary consist of at least three literals, corresponding to each single row of the matrix, but since we have already found an implicant corresponding to each row, those implicants would not be prime. Overall, the prime implicants of
are
,
and
.
(b) Those that cover all rows of the matrix, namely,
, and the disjunction of all three.