Question 24

The function $X(x, y, z) = xy + yz + zx$ is the 3-variable majority function. Note that for any $u, v, w$:

• $X(u, v, v) = uv + v + uv = v$.
• If $a = b$, then $X(a, b, w) = a$; if $a \ne b$ (one is $0$ and the other is $1$), then $X(a, b, w) = w$.

Checking each option:

• (A) False: Majority is not associative. For $(a, b, c, d, e) = (1, 1, 0, 0, 0)$, $\text{LHS} = X(1, 1, X(0,0,0)) = X(1,1,0) = 1$, whereas $\text{RHS} = X(X(1,1,0), 0, 0) = X(1,0,0) = 0$.
• (B) True: In $X(a, b, X(a, b, c))$, if $a = b$ then both sides equal $a$; if $a \ne b$ then $X(a, b, w) = w$, so $\text{LHS} = X(a, b, c)$.
• (C) False: For $(a, b, c, d) = (0, 1, 1, 1)$, $\text{LHS} = X(0, 1, X(0, 1, 1)) = X(0, 1, 1) = 1$, whereas $\text{RHS} = X(0, 1, 0) \cdot X(1, 1, 1) = 0 \cdot 1 = 0$.
• (D) True: Since $X(a, c, c) = c$ and $X$ is symmetric in its three arguments, $\text{RHS} = X(a, X(a, b, c), c) = X(a, c, X(a, b, c)) = X(a, b, c)$ by property (B).