GATE CS 2000 Q2.11 — Minimization (K-Maps etc.)

To find which function does not implement the given Karnaugh map, let us simplify each of the algebraic expressions in the options:

1. Option A: $(w + x)y = wy + xy$
2. Option B: $xy + yw = (x + w)y = (w + x)y$
3. Option C: $(w + x)(\bar{w} + y)(\bar{x} + y)$
   First, expand the first two terms: $$(w + x)(\bar{w} + y) = w\bar{w} + wy + \bar{w}x + xy = wy + \bar{w}x + xy$$ Now, multiply this result with the third term $(\bar{x} + y)$: $$(wy + \bar{w}x + xy)(\bar{x} + y) = wy\bar{x} + wyy + \bar{w}x\bar{x} + \bar{w}xy + xy\bar{x} + xyy$$ Since $x\bar{x} = 0$ and $yy = y$: $$= w\bar{x}y + wy + \bar{w}xy + xy$$ Factoring out $wy$ and $xy$: $$= wy(\bar{x} + 1) + xy(\bar{w} + 1) = wy + xy = (w + x)y$$

Since all three expressions A, B, and C are algebraically equivalent to $(w + x)y$, they all represent the exact same Boolean function. Therefore, none of them fails to implement the K-map.