GATE CS 1992 Q02-i — Boolean Algebra

To determine which operation is commutative but not associative, let's analyze each option:

1. AND ($\cdot$):
   • Commutative: $A \cdot B = B \cdot A$ (True)
   • Associative: $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ (True)
2. OR ($+$):
   • Commutative: $A + B = B + A$ (True)
   • Associative: $(A + B) + C = A + (B + C)$ (True)
3. EX-OR ($\oplus$):
   • Commutative: $A \oplus B = B \oplus A$ (True)
   • Associative: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ (True)
4. NAND ($\uparrow$):
   • Commutative: $A \uparrow B = \overline{A \cdot B} = \overline{B \cdot A} = B \uparrow A$ (True)
   • Associative: Let's evaluate $(A \uparrow B) \uparrow C$ and $A \uparrow (B \uparrow C)$:
     $\text{LHS} = (A \uparrow B) \uparrow C = \overline{\overline{A \cdot B} \cdot C} = (A \cdot B) + \overline{C}$
     $\text{RHS} = A \uparrow (B \uparrow C) = \overline{A \cdot \overline{B \cdot C}} = \overline{A} + (B \cdot C)$
     Since $\text{LHS} \neq \text{RHS}$ (for instance, when $A = 1, B = 1, C = 0$, we get $\text{LHS} = 1 \cdot 1 + 1 = 1$ and $\text{RHS} = 0 + 1 \cdot 0 = 0$), the NAND operation is not associative.

Therefore, the NAND operation is commutative but not associative.