GATE CS 1998 Q2.8 — Boolean Algebra

An operation $*$ is defined as:

• Commutative if $A * B = B * A$
• Associative if $(A * B) * C = A * (B * C)$

Let's evaluate the given operations:

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. NAND ($\uparrow$):
   • Commutative: $A \uparrow B = \overline{A \cdot B} = \overline{B \cdot A} = B \uparrow A$ (True)
   • Associative: Let's compare the left-hand side (LHS) and right-hand side (RHS):
     • $\text{LHS} = (A \uparrow B) \uparrow C = \overline{\overline{AB} \cdot C} = AB + \overline{C}$
     • $\text{RHS} = A \uparrow (B \uparrow C) = \overline{A \cdot \overline{BC}} = \overline{A} + BC$
     Since $\text{LHS} \neq \text{RHS}$ (for instance, with $A=1, B=1, C=0$, we get $\text{LHS} = 1$ and $\text{RHS} = 0$), NAND is not associative.
4. EXOR ($\oplus$):
   • Commutative: $A \oplus B = B \oplus A$ (True)
   • Associative: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ (True)

Thus, NAND is commutative but not associative.