The GATE Grind

GATE 2025 CS (CS1) – Question 24

Digital Logic · Boolean Algebra and Minimization · 1 mark · Multiple select

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. $X(a,b,X(c,d,e)) = X(X(a,b,c),d,e)$
  2. $X(a,b,X(a,b,c)) = X(a,b,c)$
  3. $X(a,b,X(a,c,d)) = (X(a,b,a)\ \text{AND}\ X(c,d,c))$
  4. $X(a,b,c) = X(a,X(a,b,c),X(a,c,c))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $X(a,b,X(a,b,c)) = X(a,b,c)$; (D) $X(a,b,c) = X(a,X(a,b,c),X(a,c,c))$

Explanation

X is the majority function. (A) fails for a=b=1, c=d=e=0 (LHS 1, RHS 0). (C) reduces to X(a,b,X(a,c,d)) = a·c, which fails for a=0, b=c=d=1. (B) and (D) hold for all inputs when checked case by case.