GATE CS 2001 Q1.11 — Minimization (K-Maps etc.)

To find the minimal Sum-of-Products (SOP) expression, we analyze the 3-variable Karnaugh map with variables $X$ (row) and $YZ$ (columns):

• The 1s are located at minterms $m_1 (001)$, $m_5 (101)$, $m_6 (110)$, and $m_7 (111)$.
• We group the adjacent 1s to find the prime implicants:
  • Group 1: Combining $m_1$ and $m_5$ gives the term $Y'Z$. Since $m_1$ has no other neighbors, this is an essential prime implicant.
  • Group 2: Combining $m_6$ and $m_7$ gives the term $XY$. Since $m_6$ has no other neighbors, this is also an essential prime implicant.
• The remaining adjacent pair $m_5$ and $m_7$ (which gives $XZ$) is redundant because both cells are already covered by the essential prime implicants.

Thus, the minimal SOP expression is:

$$\text{Minimal SOP} = XY + Y'Z$$