GATE CS 2007 Q32 — Boolean Algebra

To determine which expressions are not equivalent to $f(w, x, y, z) = \sum (0, 4, 5, 7, 8, 9, 13, 15)$, we can find the set of minterms covered by each expression:

• P: $x'y'z' + w'xy' + wy'z + xz$
  • $x'y'z'$ covers: $0, 8$
  • $w'xy'$ covers: $4, 5$
  • $wy'z$ covers: $9, 13$
  • $xz$ covers: $5, 7, 13, 15$
  • Union of minterms = $\{0, 4, 5, 7, 8, 9, 13, 15\} = f$. (Equivalent)
• Q: $w'y'z' + wx'y' + xz$
  • $w'y'z'$ covers: $0, 4$
  • $wx'y'$ covers: $8, 9$
  • $xz$ covers: $5, 7, 13, 15$
  • Union of minterms = $\{0, 4, 5, 7, 8, 9, 13, 15\} = f$. (Equivalent)
• R: $w'y'z' + wx'y' + xyz + xy'z$
  • Simplifying the last two terms: $xyz + xy'z = xz(y + y') = xz$.
  • This reduces exactly to expression Q, which is equivalent to $f$. (Equivalent)
• S: $x'y'z' + wx'y' + w'y$
  • The term $w'y$ covers minterms $2, 3, 6, 7$.
  • Since $2, 3, 6$ are not in the minterm list of $f$, expression S is not equivalent to $f$.

Thus, only expression S is NOT equivalent to $f$.