GATE CS 2021 Set 1 Q.52 (CS Q.42): Boolean Algebra and Logic Minimization

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$ )?

$(\overline{X} + \overline{Y} + \overline{Z})(X + \overline{Y})(Y + \overline{Z})$

$X\overline{Y} + \overline{Z}$

$(X + \overline{Z})(\overline{Y} + \overline{Z})$

$X\overline{Y} + Y\overline{Z} + \overline{X}\overline{Y}\overline{Z}$

Official answer and solution

Solution

Apply De Morgan's laws to find the complement of F in SOP form, then simplify using boolean algebra and factor into POS form.

The given expression is:

F = (X + Y + Z)(\overline{X} + Y)(\overline{Y} + Z)

Step 1: Apply De Morgan's law to find $\overline{F}$ :

\overline{F} = (X + Y + Z)' + (\overline{X} + Y)' + (\overline{Y} + Z)'

\overline{F} = \overline{X}\overline{Y}\overline{Z} + X\overline{Y} + Y\overline{Z}

Rearranging the terms yields:

\overline{F} = X\overline{Y} + Y\overline{Z} + \overline{X}\overline{Y}\overline{Z}

This is precisely Option D.

Step 2: Simplify Option D:

X\overline{Y} + \overline{X}\overline{Y}\overline{Z} = \overline{Y}(X + \overline{X}\overline{Z}) = \overline{Y}(X + \overline{Z}) = X\overline{Y} + \overline{Y}\overline{Z}

Now combine with the remaining term $Y\overline{Z}$ :

\overline{F} = X\overline{Y} + \overline{Y}\overline{Z} + Y\overline{Z} = X\overline{Y} + (\overline{Y} + Y)\overline{Z} = X\overline{Y} + \overline{Z}

This is precisely Option B.

Step 3: Convert Option B into POS (Product of Sums) form using the distributive law $(A + BC = (A + B)(A + C))$ :

X\overline{Y} + \overline{Z} = (X + \overline{Z})(\overline{Y} + \overline{Z})

This is precisely Option C.

Thus, options B, C, and D are all equivalent to $\overline{F}$ .

Final answer

B, C, D

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.