GATE CS 2025 Set 1 | Question 24

MSQ · 1 mark

Let \(X\) be a 3-variable Boolean function that produces output as ‘1’ when at least two of the input variables are ‘1’. Which of the following statement(s) is/are CORRECT, where \(a, b, c, d, e\) are Boolean variables?

  1. Option A: \(X(a, b, X(c, d, e)) = X(X(a, b, c), d, e)\)
  2. Option B: \(X(a, b, X(a, b, c)) = X(a, b, c)\) (correct)
  3. Option C: \(X(a, b, X(a, c, d)) = (X(a, b, a) \text{ AND } X(c, d, c))\)
  4. Option D: \(X(a, b, c) = X(a, X(a, b, c), X(a, c, c))\) (correct)

Answer

(B), (D)

Explanation

\(X\) is the majority function. Two quick rules: \(X(p, p, r) = p\), and if two arguments differ, \(X\) equals the remaining one.

  • (A) False: with \(a = b = 1\), \(c = d = e = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is \(X(1, 0, 0) = 0\).
  • (B) True: if \(a = b\), both sides equal \(a\); if \(a \ne b\), the left side equals its third argument, \(X(a, b, c)\).
  • (C) False: the right side is \(a \cdot c\); with \(a = b = 1\), \(c = d = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is 0.
  • (D) True: \(X(a, c, c) = c\), so the right side is \(X(a, X(a, b, c), c)\); if \(a = c\) it equals \(a = X(a, b, c)\), and if \(a \ne c\) it equals the middle argument \(X(a, b, c)\).

Answer: B, D