GATE CS 2025 Set 1 Q14 — Boolean Algebra

The function $X(x, y, z)$ represents the 3-variable majority function, defined as $X(x, y, z) = xy + yz + zx$.

• Option A: Let $a=1, b=1, c=0, d=0, e=0$. Then $\text{LHS} = X(1, 1, X(0,0,0)) = X(1, 1, 0) = 1$, while $\text{RHS} = X(X(1, 1, 0), 0, 0) = X(1, 0, 0) = 0$. Since $\text{LHS} \neq \text{RHS}$, Option A is incorrect.
• Option B: Let $M = X(a, b, c) = ab + bc + ca$. Then $X(a, b, M) = ab + (a+b)M = ab + (a+b)(ab + bc + ca) = ab + bc + ca = X(a, b, c)$. Thus, Option B is correct.
• Option C: Since $X(a, b, a) = a$ and $X(c, d, c) = c$, the $\text{RHS} = ac$. For $a=1, b=1, c=0, d=0$, we have $\text{LHS} = X(1, 1, 0) = 1$ but $\text{RHS} = 0$. Since $\text{LHS} \neq \text{RHS}$, Option C is incorrect.
• Option D: Note that $X(a, c, c) = c$. Let $M = X(a, b, c)$. Then $\text{RHS} = X(a, M, c) = aM + Mc + ca = (a+c)M + ac = (a+c)(ab + bc + ca) + ac = ab + bc + ca = X(a, b, c)$. Thus, Option D is correct.