GATE CS 2019 Q6 — Boolean Algebra

To find which identity is NOT valid, let us analyze each option systematically:

• Option A: $(x \oplus y) \oplus z = x \oplus (y \oplus z)$
  This is valid because the Exclusive-OR (XOR) operation is associative.


• Option B: $(x + y) \oplus z = x \oplus (y+z)$
  We can verify this using a counterexample. Let $x = 1$, $y = 1$, and $z = 0$: $$\text{LHS} = (1 + 1) \oplus 0 = 1 \oplus 0 = 1$$ $$\text{RHS} = 1 \oplus (1 + 0) = 1 \oplus 1 = 0$$ Since $\text{LHS} \neq \text{RHS}$, this identity is NOT valid.


• Option C: $x \oplus y = x+y, \text{ if } xy=0$
  The condition $xy = 0$ means $x$ and $y$ cannot both be $1$ simultaneously.
  • If $x=0, y=0$: $0 \oplus 0 = 0$ and $0+0 = 0$ (Equal)
  • If $x=1, y=0$: $1 \oplus 0 = 1$ and $1+0 = 1$ (Equal)
  • If $x=0, y=1$: $0 \oplus 1 = 1$ and $0+1 = 1$ (Equal)
  Thus, this identity is valid.


• Option D: $x \oplus y = (xy+x’y’)’$
  The expression $xy + x'y'$ represents the XNOR operation ($x \odot y$). Since XOR is the complement of XNOR: $$(xy + x'y')' = (x \odot y)' = x \oplus y$$ Thus, this identity is valid.