GATE CS 2015 Set 3 Q2 — Sets, Relations and Functions

The binary operator $\#$ is defined as $X \# Y = X' + Y'$, which represents the logical NAND operation.

Let us analyze the two statements:

Statement $S_1$: Associativity

We need to check if $(P \# Q) \# R = P \# (Q \# R)$.

• Left-Hand Side (LHS): $$\begin{align*} (P \# Q) \# R &= (P' + Q') \# R \\ &= (P' + Q')' + R' \\ &= (P \cdot Q) + R' \quad \text{(using De Morgan's Law)} \end{align*}$$
• Right-Hand Side (RHS): $$\begin{align*} P \# (Q \# R) &= P \# (Q' + R') \\ &= P' + (Q' + R')' \\ &= P' + (Q \cdot R) \quad \text{(using De Morgan's Law)} \end{align*}$$

Since $PQ + R' \neq P' + QR$ in general (for example, if $P=1, Q=1, R=0$, LHS $= 1 \cdot 1 + 1 = 1$ while RHS $= 0 + 1 \cdot 0 = 0$), the operator is not associative. Thus, $S_1$ is false.

Statement $S_2$: Commutativity

We need to check if $Q \# R = R \# Q$.

• LHS: $Q \# R = Q' + R'$
• RHS: $R \# Q = R' + Q'$

Since Boolean addition is commutative ($Q' + R' = R' + Q'$), we have $Q \# R = R \# Q$. Thus, the operator is commutative, and $S_2$ is true.

Therefore, only $S_2$ is true.