GATE CS 2016 Set 2 Q08 — Boolean Algebra

We are given the Boolean equation:

Using the properties of the XOR ($\oplus$) operator, let us analyze the options.

Step 1: Simplify the given equation

Since XOR is commutative and associative, we can rearrange the terms:

For any two Boolean expressions $A$ and $B$, if $A \oplus B = 0$, then $A = B$. Thus, we have:

Step 2: Analyze Option C

Option C states: $\bar{x}_1 \oplus \bar{x}_3 = \bar{x}_2 \oplus \bar{x}_4$.

Recall the complement property of XOR: $\bar{A} = A \oplus 1$. Therefore:

Similarly, for the right-hand side:

Substituting these back into Option C gives:

This is identical to Equation 1, which is derived directly from the given condition. Hence, Option C must always be TRUE.

Step 3: Eliminate other options using a counterexample

Let $x_1 = 1, x_2 = 1, x_3 = 1, x_4 = 1$.

• Check condition: $1 \oplus 1 \oplus 1 \oplus 1 = 0 \oplus 0 = 0$ (Satisfied).
• Option A: $x_1 x_2 x_3 x_4 = 1 \cdot 1 \cdot 1 \cdot 1 = 1 \neq 0$ (False).
• Option B: $x_1 x_3 + x_2 = (1 \cdot 1) + 1 = 1 \neq 0$ (False).
• Option D: $x_1 + x_2 + x_3 + x_4 = 1 + 1 + 1 + 1 = 1 \neq 0$ (False).