Question 31

Tracing the three inputs to the final 3-input OR gate:

1. Top 2-input NAND gate receives $Y$ and $X$, producing $\overline{XY}$.
2. Middle NOT gate receives $X$, producing $\bar{X}$.
3. Bottom 2-input AND gate receives $X$ and $\bar{Y}$ (from the inverter on $Y$), producing $X\bar{Y}$.

Combining these at the OR gate gives:

• $F = \overline{XY} + \bar{X} + X\bar{Y}$, which is Option (C).
• By De Morgan's law ($\overline{XY} = \bar{X} + \bar{Y}$) and idempotence ($\bar{X} + \bar{X} = \bar{X}$), $F = \bar{X} + \bar{Y} + X\bar{Y}$, which is Option (B).
• By absorption ($\bar{Y} + X\bar{Y} = \bar{Y}$), $F = \bar{X} + \bar{Y} = \overline{XY}$, which is Option (A).
• Option (D) $X + \bar{Y}$ evaluates to $1$ when $(X, Y) = (1, 1)$, whereas $F(1, 1) = 0$.