GATE 2026 CS (CS1) – Question 21

Correct answer: (A) $\overline{\overline{P} \oplus \overline{Q}}$; (C) $\overline{P} \oplus Q$; (D) $P \oplus \overline{Q}$

Explanation

Let us simplify the Boolean expression for $F(P, Q)$:
Recall that for any Boolean expressions $A$ and $B$, if $B \implies A$ (meaning $B \cdot \overline{A} = 0$), then $A \oplus B = A \cdot \overline{B}$.
Here, $A = \overline{P} + Q$ and $B = \overline{P}Q$. Since $\overline{P}Q \le \overline{P} + Q$, we have:
$$F(P, Q) = (\overline{P} + Q) \cdot \overline{(\overline{P}Q)} = (\overline{P} + Q)(P + \overline{Q}) = \overline{P}P + \overline{P}\overline{Q} + QP + Q\overline{Q} = PQ + \overline{P}\overline{Q} = P \odot Q$$
This is the XNOR (equivalence) function of $P$ and $Q$.

Now test each option:
- (A) $\overline{\overline{P} \oplus \overline{Q}} = \overline{P \oplus Q} = P \odot Q$. (Equivalent!)
- (B) $P \oplus Q$ is the XOR function. (Not equivalent).
- (C) $\overline{P} \oplus Q = \overline{P \oplus Q} = P \odot Q$. (Equivalent!)
- (D) $P \oplus \overline{Q} = \overline{P \oplus Q} = P \odot Q$. (Equivalent!)

Therefore, options (A), (C), and (D) are equivalent to $F$.