GATE CS 2015 Set 1 Q28 — Sets, Relations and Functions

The given truth table defines the standard Exclusive-OR (XOR) operator, commonly denoted as $\oplus$. Let us analyze its properties:

1. Commutativity

An operator $\neq$ is commutative if $p \neq q = q \neq p$ for all possible values of $p$ and $q$.

• $0 \neq 1 = 1$ and $1 \neq 0 = 1 \implies 0 \neq 1 = 1 \neq 0$
• $0 \neq 0 = 0$ and $1 \neq 1 = 0$

Since the output is symmetric with respect to the inputs, the operator is commutative.

2. Associativity

An operator $\neq$ is associative if $(p \neq q) \neq r = p \neq (q \neq r)$ for all $p, q, r \in \{0, 1\}$.

Since this operator is equivalent to the logical XOR ($\oplus$), we can verify associativity algebraically or by evaluating the truth values:

• For $p = 0, q = 1, r = 1$:
  • $(0 \neq 1) \neq 1 = 1 \neq 1 = 0$
  • $0 \neq (1 \neq 1) = 0 \neq 0 = 0$
• For $p = 1, q = 1, r = 1$:
  • $(1 \neq 1) \neq 1 = 0 \neq 1 = 1$
  • $1 \neq (1 \neq 1) = 1 \neq 0 = 1$

In general, $p \oplus q \oplus r$ is $1$ if and only if an odd number of variables are $1$. Since this condition is symmetric for any grouping, the operator is associative.

Therefore, the binary operator $\neq$ is both commutative and associative.