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.