GATE CS 2025 Set 2 | Question 31

MSQ · 1 mark

Consider the following logic circuit diagram.

Logic circuit with inputs Y and X. A NAND gate takes Y and X, a NOT gate takes X, and an AND gate takes X and Y passed through a NOT gate; the outputs of these three gates are the inputs of an OR gate whose output is F.

Which is/are the CORRECT option(s) for the output function \(F\)?

  1. Option A: \(\overline{X\,Y}\) (correct)
  2. Option B: \(\overline{X} + \overline{Y} + X\overline{Y}\) (correct)
  3. Option C: \(\overline{X\,Y} + \overline{X} + X\overline{Y}\) (correct)
  4. Option D: \(X + \overline{Y}\)

Answer

(A), (B), (C)

Explanation

Reading the three gates that feed the OR gate:

  • the NAND gate gives \(\overline{XY}\);
  • the NOT gate on \(X\) gives \(\overline{X}\);
  • the AND gate gives \(X\overline{Y}\).

So \(F = \overline{XY} + \overline{X} + X\overline{Y}\), which is option C as written. By De Morgan's law \(\overline{XY} = \overline{X} + \overline{Y}\); the term \(\overline{X}\) repeats part of this and \(X\overline{Y}\) is absorbed by \(\overline{Y}\), so \(F = \overline{X} + \overline{Y} = \overline{XY}\). That is option A, and option B reduces to it the same way.

D is wrong: at \(X = Y = 1\), \(F = 0\) but \(X + \overline{Y} = 1\).

Answer: A, B, C