GATE CS 2007 Q9 — Minimization (K-Maps etc.)

To find which variables the Boolean function $f(w, x, y, z)$ depends on, we can simplify the expression using a Karnaugh Map (K-map) or algebraic grouping.

The given minterms are: $$\Sigma(1, 3, 4, 6, 9, 11, 12, 14)$$

Let's represent the minterms in their 4-bit binary form $(w, x, y, z)$:

• $1 = 0001$
• $3 = 0011$
• $4 = 0100$
• $6 = 0110$
• $9 = 1001$
• $11 = 1011$
• $12 = 1100$
• $14 = 1110$

Grouping the Minterms:

1. Group 1: Combine minterms $1, 3, 9, \text{ and } 11$ $$\begin{aligned} 1 &= 0001 \\ 3 &= 0011 \\ 9 &= 1001 \\ 11 &= 1011 \end{aligned}$$ Comparing these, the first bit ($w$) and the third bit ($y$) vary, while the second bit ($x = 0$) and the fourth bit ($z = 1$) remain constant. $$\text{Group 1} = x'z$$


2. Group 2: Combine minterms $4, 6, 12, \text{ and } 14$ $$\begin{aligned} 4 &= 0100 \\ 6 &= 0110 \\ 12 &= 1100 \\ 14 &= 1110 \end{aligned}$$ Comparing these, the first bit ($w$) and the third bit ($y$) vary, while the second bit ($x = 1$) and the fourth bit ($z = 0$) remain constant. $$\text{Group 2} = xz'$$

Simplified Expression:

$$f(w, x, y, z) = x'z + xz' = x \oplus z$$

The simplified function depends only on the variables $x$ and $z$. Therefore, it is completely independent of the other two variables, $w$ and $y$.

Thus, the function is independent of two variables.