GATE CS 2026 Set 1 Q11 — Boolean Algebra

To find the equivalent expressions for the given Boolean function $F(P, Q) = (\bar{P}+Q) \oplus (\bar{P} Q)$, we can simplify the expression algebraically.

Method 1: Algebraic Simplification

Let $X = \bar{P}+Q$ and $Y = \bar{P} Q$.

Using the definition of the XOR ($\{ \oplus \}$) operation, $X \oplus Y = X\bar{Y} + \bar{X}Y$.

First, let's find the complements of $X$ and $Y$:

• $\bar{X} = \overline{\bar{P}+Q} = P\bar{Q}$
• $\bar{Y} = \overline{\bar{P}Q} = P+\bar{Q}$

Now, substitute these into the XOR formula:

Combining these, we get:

Evaluating the Options

• Option A: $\overline{P \oplus Q}$
  By definition, the complement of XOR is XNOR:
  $\overline{P \oplus Q} = P \odot Q$.
  (Correct)
• Option B: $P \oplus Q$
  This is the complement of $F(P, Q)$.
  (Incorrect)
• Option C: $\bar{P} \oplus Q$
  Complementing one input of an XOR gate complements the entire output:
  $\bar{P} \oplus Q = \overline{P \oplus Q} = P \odot Q$.
  (Correct)
• Option D: $\bar{P} \oplus \bar{Q}$
  Complementing both inputs of an XOR gate leaves the output unchanged:
  $\bar{P} \oplus \bar{Q} = P \oplus Q$.
  (Incorrect)