GATE CS 2025 Set 2 Q21 — Combinational Circuits

The output function of the given logic circuit is the NAND operation, $F = \overline{XY}$. We can determine the correct options by simplifying each Boolean expression to see if it is equivalent to $\overline{XY}$:

• Option A: $\overline{XY}$ is directly the target function. (Correct)
• Option B: $\overline{X} + \overline{Y} + X\overline{Y}$
  Using the absorption law, $\overline{Y} + X\overline{Y} = \overline{Y}(1 + X) = \overline{Y}$.
  Thus, the expression simplifies to $\overline{X} + \overline{Y} = \overline{XY}$. (Correct)
• Option C: $\overline{XY} + \overline{X} + X\overline{Y}$
  Applying De Morgan's law to the first term gives $(\overline{X} + \overline{Y}) + \overline{X} + X\overline{Y}$.
  Since $\overline{X} + \overline{X} = \overline{X}$, this simplifies to $\overline{X} + \overline{Y} + X\overline{Y} = \overline{X} + \overline{Y} = \overline{XY}$. (Correct)
• Option D: $X + \overline{Y} \neq \overline{XY}$. (Incorrect)

Thus, options A, B, and C are mathematically equivalent to the circuit's output.