GATE 2021 CS (CS1) – Question 52
Consider the following Boolean expression.
$F = (X+Y+Z)(\overline{X}+Y)(\overline{Y}+Z)$
Which of the following Boolean expressions is/are equivalent to $\overline{F}$ (complement of $F$)?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $X\overline{Y}+\overline{Z}$; (C) $(X+\overline{Z})(\overline{Y}+\overline{Z})$; (D) $X\overline{Y}+Y\overline{Z}+\overline{X}\,\overline{Y}\,\overline{Z}$
Explanation
Build the truth table of $F=(X+Y+Z)(\overline X+Y)(\overline Y+Z)$:
| XYZ | $X+Y+Z$ | $\overline X+Y$ | $\overline Y+Z$ | F |
|---|---|---|---|---|
| 000 | 0 | 1 | 1 | 0 |
| 001 | 1 | 1 | 1 | 1 |
| 010 | 1 | 1 | 0 | 0 |
| 011 | 1 | 1 | 1 | 1 |
| 100 | 1 | 0 | 1 | 0 |
| 101 | 1 | 0 | 1 | 0 |
| 110 | 1 | 1 | 0 | 0 |
| 111 | 1 | 1 | 1 | 1 |
So $F=1$ for $001,011,111$ and $\overline F=1$ for $000,010,100,101,110$, giving $\overline F=\overline Z+X\overline Y$.
- **(A)** $(\overline X+\overline Y+\overline Z)(X+\overline Y)(Y+\overline Z)$ gives 0 at $010$ where $\overline F=1$. Not equal.
- **(B)** $X\overline Y+\overline Z$: equals $\overline F$.
- **(C)** $(X+\overline Z)(\overline Y+\overline Z)=X\overline Y+X\overline Z+\overline Y\overline Z+\overline Z=X\overline Y+\overline Z$. Equal.
- **(D)** $X\overline Y+Y\overline Z+\overline X\,\overline Y\,\overline Z$ is 1 exactly at $000,010,100,101,110$. Equal.
Answer: B, C, D.