GATE2025_CS1_Q24

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?

Note: This is a Multiple Select Question (MSQ). One or more options may be correct.

✅ Final Answer:

The correct options are (B) and (D).

🔹 Short Answer:

The function X(a, b, c) is the Boolean Majority function, which equals ab + bc + ac. Options (B) and (D) represent known identities of the majority/median function. Option (A) fails because the majority function is not associative. Option (C) fails because the identity does not hold for all inputs; for example, it fails for a=1, b=1, c=0, d=1.

🔸 Long Answer:

The function X(a, b, c) is true if at least two inputs are true. This is the 3-variable Majority function, commonly used in digital logic (e.g., the carry-out of a full adder). Its Boolean expression is:

X(a, b, c) = ab + bc + ac

Truth Table for X(a, b, c)

a	b	c	X(a, b, c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Let's analyze each statement:

(A) X(a, b, X(c, d, e)) = X(X(a, b, c), d, e)

This suggests associativity. The majority function is not associative. We can find a counterexample.

• Let a=1, b=1, c=0, d=0, e=0.
• LHS: X(c, d, e) = X(0,0,0) = 0.
  X(a, b, X(c,d,e)) = X(1, 1, 0) = 1.
• RHS: X(a, b, c) = X(1,1,0) = 1.
  X(X(a,b,c), d, e) = X(1, 0, 0) = 0.

Since LHS (1) ≠ RHS (0), the statement is FALSE.

(B) X(a, b, X(a, b, c)) = X(a, b, c)

This is a known identity of the median function. Let's verify. Let M = X(a, b, c).

• If a=1, b=1, then M = X(1,1,c) = 1.
  LHS = X(1, 1, M) = X(1, 1, 1) = 1. RHS = M = 1. (Holds)
• If a=0, b=0, then M = X(0,0,c) = 0.
  LHS = X(0, 0, M) = X(0, 0, 0) = 0. RHS = M = 0. (Holds)
• If a=1, b=0, then M = X(1,0,c) = c.
  LHS = X(1, 0, M) = X(1, 0, c) = c. RHS = M = c. (Holds)

The identity holds for all cases. The statement is TRUE.

(C) X(a, b, X(a, c, d)) = (X(a, b, a) AND X(c, d, c))

Let's simplify the RHS first. The majority of three variables where two are the same is just that variable. So, X(x, y, x) = x.

• X(a, b, a) = a
• X(c, d, c) = c

So the RHS simplifies to a AND c (or ac). The equation becomes X(a, b, X(a, c, d)) = ac. Let's find a counterexample.

• Let a=1, b=1, c=0, d=1.
• RHS: a AND c = 1 AND 0 = 0.
• LHS: X(a, c, d) = X(1, 0, 1) = 1.
  X(a, b, X(a,c,d)) = X(1, 1, 1) = 1.

Since LHS (1) ≠ RHS (0), the statement is FALSE.

(D) X(a, b, c) = X(a, X(a, b, c), X(a, c, c))

This is another known identity. Let's simplify and verify.

• From (C), we know X(a, c, c) = c.
• Let M = X(a, b, c).
• The statement becomes M = X(a, M, c).

We can prove this by cases for a.

• Case a=0:
  M = X(0, b, c) = bc.
  RHS = X(0, M, c) = X(0, bc, c) = 0(bc) + (bc)c + 0(c) = bc.
  LHS = RHS. (Holds)
• Case a=1:
  M = X(1, b, c) = b + c.
  RHS = X(1, M, c) = X(1, b+c, c) = 1(b+c) + (b+c)c + 1c = (b+c) + (bc+c) + c = b+c.
  LHS = RHS. (Holds)

The identity holds. The statement is TRUE.

Bibliography:
- Mano, M. M., & Ciletti, M. D. (2017). Digital Design. Pearson. (Chapter on Boolean Algebra and Logic Gates).
- Knuth, D. E. (2008). The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. Addison-Wesley.

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.