Let # be the binary operator defined as X # Y = X' + Y' where X and Y are Boolean variables. Consider the following two statements. (S1) (P # Q) # R = P # (Q # R) (S2) Q # R = (R # Q). Which of the following is/are true for the Boolean variables P, Q and R? A. Only S1 is true B. Only S2 is true C. Both S1 and S2 are true D. Neither S1 nor S2 are true

GATE 2015 · Discrete Mathematics · Binary Operation · medium

Answer: B. Only S2 is true

1. Identify the operator: By De Morgan, X' + Y' is the complement of X AND Y, so # is NAND.
2. Check S2 (commutativity): OR is symmetric, so Q' + R' = R' + Q'. Hence S2 is TRUE.
3. Check S1 (associativity) with a counterexample: Take P=Q=R=1. P#Q = 1#1 = 0, so (P#Q)#R = 0#1 = 0' + 1' = 1 + 0 = 1. Q#R = 1#1 = 0, so P#(Q#R) = 1#0 = 1' + 0' = 0 + 1 = 1... try P=1,Q=0,R=1: (1#0)#1 = (1+1)#1 = 1#1 = 0; 1#(0#1) = 1#(1+0) = 1#1 = 0; try P=0,Q=1,R=1: (0#1)#1 = (1+0)#1 = 1#1 = 0; 0#(1#1) = 0#0 = 1+1 = 1. Here 0 != 1, so S1 is FALSE.
4. Select the option: S1 false, S2 true means 'Only S2 is true', which is option B.