GATE CS 2021 Set 1 Q42 — Boolean Algebra

Given the Boolean expression:

$$F = (X+Y+Z)(\overline X +Y)(\overline Y +Z)$$

Applying De Morgan's Law to find the complement $\overline F$:

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

$$\overline F = \overline X \overline Y \overline Z + X \overline Y + Y \overline Z$$

This directly matches Option D.

Now, let's simplify this expression by grouping terms:

$$\overline F = X \overline Y + \overline X \overline Y \overline Z + Y \overline Z$$

$$\overline F = \overline Y(X + \overline X \overline Z) + Y \overline Z$$

Using the distributive property $A + \overline A B = A + B$:

$$\overline F = \overline Y(X + \overline Z) + Y \overline Z = X \overline Y + \overline Y \overline Z + Y \overline Z$$

$$\overline F = X \overline Y + (\overline Y + Y)\overline Z = X \overline Y + \overline Z$$

This matches Option B.

Next, expanding Option 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(X + \overline Y + 1) = X \overline Y + \overline Z$$

Since this is equivalent to Option B, Option C is also correct.