GATE CS 2015 Set 3 Q43 — Boolean Algebra

To find the total number of prime implicants for the function $f(w, x, y, z) = \sum (0, 2, 4, 5, 6, 10)$, we can group the minterms using a Karnaugh map (K-map) or the tabular method.

Let's list the minterms and group them by the number of 1s in their binary representation:

• Group 0: $0$ ($0000$)
• Group 1: $2$ ($0010$), $4$ ($0100$)
• Group 2: $5$ ($0101$), $6$ ($0110$), $10$ ($1010$)

Combining adjacent minterms to form larger groups:

1. Size-4 Group:
   Combining $(0, 2)$ and $(4, 6)$ gives the group $(0, 2, 4, 6)$, which corresponds to the term $w'z'$ ($0--0$). This cannot be combined further, so it is a prime implicant.
2. Size-2 Groups:
   
   • $(4, 5)$ corresponds to $w'xy'$ ($010-$). It cannot be combined with any other group, so it is a prime implicant.
   • $(2, 10)$ corresponds to $x'yz'$ ($-010$). It cannot be combined with any other group, so it is a prime implicant.

All other size-2 groups like $(0,2)$, $(0,4)$, $(2,6)$, and $(4,6)$ are completely contained within the larger group $(0,2,4,6)$ and are therefore not prime implicants.

Thus, the total number of prime implicants is 3 (namely, $w'z'$, $w'xy'$, and $x'yz'$).