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 $\phi$ . We consider when $\phi$ is assigned $T$ . If $B=F$ , then the right hand side is $F$ , and the left hand side should be $F$ as well, but its first term is $T$ , meaning that the second term should be false, i.e. $C=T$ and $D=F$ . Now, assume $B=T$ . We need the left hand side to be $F$ or the right hand side to be $T$ . If $A=F$ , then the left hand side is $F$ . Assume $A=T$ . The expression we have so far is $(\neg C\vee D)\rightarrow C\vee(\neg C\wedge D)$ , which is tautologically equivalent to $\neg(\neg C\vee D)\vee C\vee(\neg C\wedge D)$ , $(C\wedge\neg D)\vee C\vee(\neg C\wedge D)$ , $(C\wedge\neg D)\vee C\vee D$ , i.e. $C\vee D$ . Hence, here are the values for $A$ , $B$ , $C$ and $D$ for which $\phi$ is true:

$$\begin{eqnarray*} A & B & C\, D\\ T & T & T\, T\\ T & T & T\, F\\ T & T & F\, T\\ T & F & T\, F\\ F & T & T\, T\\ F & T & T\, F\\ F & T & F\, T\\ F & T & F\, F\\ F & F & T\, F \end{eqnarray*}$$

If an implicant $\alpha$ of $\phi$ consists of some literals, then $\phi$ 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 ($T$ or $F$ ) 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 $A$ and $B$ only, columns $A$ and $B$ must have a submatrix $4\times2$ 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 $C$ and $D$ . The values in the two columns of the submatrix are $F$ and $T$ , therefore, the corresponding prime literal is $\neg A\wedge B$ (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, $B\wedge C$ (1,2,5,6), $B\wedge D$ (1,3,5,7) and $C\wedge\neg D$ (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 $2\times3$ 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 $\neg A\wedge B$ is an implicant, so is $\neg A\wedge B\wedge C$ etc. But these are not prime. Another way of doing this is as follows. Suppose we are looking for implicants involving $A$ , $B$ and $C$ . Then we look at the previously found implicants that involve some of these literals. Namely, we have two such implicants, $\neg A\wedge B$ and $B\wedge C$ . 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 $1\times4$ submatrices in the rows that were not covered so far. There are no such rows. Overall, the prime implicants of $\phi$ are $\neg A\wedge B$ (5,6,7,8), $B\wedge C$ (1,2,5,6), $B\wedge D$ (1,3,5,7) and $C\wedge\neg D$ (2,4,6,9).

Note, how these implicants correspond to what we said. Suppose $\phi$ is true. If $B=F$ then only the last implicant can be true, but then $C\wedge\neg D$ should be true. Now, assume $B=T$ . Then, either $A=F$ (the first implicant), or $C\vee D$ 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 $\phi$ . In particular, we need the first one as the only one that contains row $8$ , 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 $\phi$ are $(\neg A\wedge B)\vee(B\wedge D)\vee(C\wedge\neg D)$ , and the disjunction of all four prime implicants.