PYQs / GATE CS / 2021 / Set 1 / Q52 GATE CS 2021 Set 1 — Question 52 Go beyond PYQs with Success Tracker AI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply. MSQ +2 / -0 Medium De Morgan's Theorems Boolean Algebra & Logic Gates Digital Logic Boolean Laws & Theorems
Digital Logic → Boolean Algebra & Logic Gates → Boolean Laws & Theorems
Last updated 5 September 2026
Question Consider the following Boolean expression.
F = ( X + Y + Z ) ( X ‾ + Y ) ( Y ‾ + Z ) F = (X + Y + Z)(\overline{X} + Y)(\overline{Y} + Z) F = ( X + Y + Z ) ( X + Y ) ( Y + Z ) Which of the following Boolean expressions is/are equivalent to
F ‾ \overline{F} F (complement of
F F F )?
Correct answer (B) XY + Z; (C) (X + Z)(Y + Z); (D) XY + YZ + XYZ
Solution Given the Boolean expression:
F = ( X + Y + Z ) ( X ‾ + Y ) ( Y ‾ + Z ) F = (X + Y + Z)(\overline{X} + Y)(\overline{Y} + Z) F = ( X + Y + Z ) ( X + Y ) ( Y + Z ) Step 1: Simplify the expression for F F F Using the distributive law
( A + B ) ( A + C ) = A + B C (A + B)(A + C) = A + BC ( A + B ) ( A + C ) = A + B C :
F = ( Y + ( X + Z ) ) ( Y + X ‾ ) ( Y ‾ + Z ) F = (Y + (X + Z)) (Y + \overline{X}) (\overline{Y} + Z) F = ( Y + ( X + Z )) ( Y + X ) ( Y + Z ) F = ( Y + ( X + Z ) X ‾ ) ( Y ‾ + Z ) F = (Y + (X + Z)\overline{X}) (\overline{Y} + Z) F = ( Y + ( X + Z ) X ) ( Y + Z ) Since
X X ‾ = 0 X\overline{X} = 0 X X = 0 :
F = ( Y + X ‾ Z ) ( Y ‾ + Z ) F = (Y + \overline{X}Z) (\overline{Y} + Z) F = ( Y + X Z ) ( Y + Z ) Expanding the product:
F = Y Y ‾ + Y Z + X ‾ Z Y ‾ + X ‾ Z Z F = Y\overline{Y} + YZ + \overline{X}Z\overline{Y} + \overline{X}ZZ F = Y Y + Y Z + X Z Y + X Z Z Since
Y Y ‾ = 0 Y\overline{Y} = 0 Y Y = 0 and
Z Z = Z ZZ = Z Z Z = Z :
F = Y Z + X ‾ Y ‾ Z + X ‾ Z F = YZ + \overline{X}\overline{Y}Z + \overline{X}Z F = Y Z + X Y Z + X Z Factoring out
X ‾ Z \overline{X}Z X Z :
F = Y Z + X ‾ Z ( 1 + Y ‾ ) F = YZ + \overline{X}Z(1 + \overline{Y}) F = Y Z + X Z ( 1 + Y ) Since
1 + Y ‾ = 1 1 + \overline{Y} = 1 1 + Y = 1 :
F = Y Z + X ‾ Z = Z ( Y + X ‾ ) F = YZ + \overline{X}Z = Z(Y + \overline{X}) F = Y Z + X Z = Z ( Y + X ) Step 2: Find the complement F ‾ \overline{F} F Using De Morgan's laws:
F ‾ = Z ( Y + X ‾ ) ‾ \overline{F} = \overline{Z(Y + \overline{X})} F = Z ( Y + X ) F ‾ = Z ‾ + ( Y + X ‾ ) ‾ \overline{F} = \overline{Z} + \overline{(Y + \overline{X})} F = Z + ( Y + X ) F ‾ = Z ‾ + Y ‾ X = X Y ‾ + Z ‾ \overline{F} = \overline{Z} + \overline{Y}X = X\overline{Y} + \overline{Z} F = Z + Y X = X Y + Z Step 3: Evaluate the given options
Option (A): ( X ‾ + Y ‾ + Z ‾ ) ( X + Y ‾ ) ( Y + Z ‾ ) (\overline{X} + \overline{Y} + \overline{Z})(X + \overline{Y})(Y + \overline{Z}) ( X + Y + Z ) ( X + Y ) ( Y + Z ) F F F X Y ‾ + Z ‾ X\overline{Y} + \overline{Z} X Y + Z Option (B): X Y ‾ + Z ‾ X\overline{Y} + \overline{Z} X Y + Z F ‾ \overline{F} F correct .Option (C): ( X + Z ‾ ) ( Y ‾ + Z ‾ ) = X Y ‾ + X Z ‾ + Z ‾ Y ‾ + Z ‾ = X Y ‾ + Z ‾ ( X + Y ‾ + 1 ) = X Y ‾ + Z ‾ (X + \overline{Z})(\overline{Y} + \overline{Z}) = X\overline{Y} + X\overline{Z} + \overline{Z}\overline{Y} + \overline{Z} = X\overline{Y} + \overline{Z}(X + \overline{Y} + 1) = X\overline{Y} + \overline{Z} ( X + Z ) ( Y + Z ) = X Y + X Z + Z Y + Z = X Y + Z ( X + Y + 1 ) = X Y + Z correct .Option (D): X Y ‾ + Y Z ‾ + X ‾ Y ‾ Z ‾ = X Y ‾ + X ‾ Y ‾ Z ‾ + Y Z ‾ = Y ‾ ( X + X ‾ Z ‾ ) + Y Z ‾ = Y ‾ ( X + Z ‾ ) + Y Z ‾ = X Y ‾ + Y ‾ Z ‾ + Y Z ‾ = X Y ‾ + Z ‾ ( Y ‾ + Y ) = X Y ‾ + Z ‾ X\overline{Y} + Y\overline{Z} + \overline{X}\overline{Y}\overline{Z} = X\overline{Y} + \overline{X}\overline{Y}\overline{Z} + Y\overline{Z} = \overline{Y}(X + \overline{X}\overline{Z}) + Y\overline{Z} = \overline{Y}(X + \overline{Z}) + Y\overline{Z} = X\overline{Y} + \overline{Y}\overline{Z} + Y\overline{Z} = X\overline{Y} + \overline{Z}(\overline{Y} + Y) = X\overline{Y} + \overline{Z} X Y + Y Z + X Y Z = X Y + X Y Z + Y Z = Y ( X + X Z ) + Y Z = Y ( X + Z ) + Y Z = X Y + Y Z + Y Z = X Y + Z ( Y + Y ) = X Y + Z correct .
Therefore, options (B), (C), and (D) are equivalent to
F ‾ \overline{F} F .
Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker. Review answer and solution without JavaScript Interactive answer checking needs JavaScript. The published solution is available below.
Correct answer (B) XY + Z; (C) (X + Z)(Y + Z); (D) XY + YZ + XYZ
Solution Given the Boolean expression:
F = ( X + Y + Z ) ( X ‾ + Y ) ( Y ‾ + Z ) F = (X + Y + Z)(\overline{X} + Y)(\overline{Y} + Z) F = ( X + Y + Z ) ( X + Y ) ( Y + Z ) Step 1: Simplify the expression for F F F Using the distributive law
( A + B ) ( A + C ) = A + B C (A + B)(A + C) = A + BC ( A + B ) ( A + C ) = A + B C :
F = ( Y + ( X + Z ) ) ( Y + X ‾ ) ( Y ‾ + Z ) F = (Y + (X + Z)) (Y + \overline{X}) (\overline{Y} + Z) F = ( Y + ( X + Z )) ( Y + X ) ( Y + Z ) F = ( Y + ( X + Z ) X ‾ ) ( Y ‾ + Z ) F = (Y + (X + Z)\overline{X}) (\overline{Y} + Z) F = ( Y + ( X + Z ) X ) ( Y + Z ) Since
X X ‾ = 0 X\overline{X} = 0 X X = 0 :
F = ( Y + X ‾ Z ) ( Y ‾ + Z ) F = (Y + \overline{X}Z) (\overline{Y} + Z) F = ( Y + X Z ) ( Y + Z ) Expanding the product:
F = Y Y ‾ + Y Z + X ‾ Z Y ‾ + X ‾ Z Z F = Y\overline{Y} + YZ + \overline{X}Z\overline{Y} + \overline{X}ZZ F = Y Y + Y Z + X Z Y + X Z Z Since
Y Y ‾ = 0 Y\overline{Y} = 0 Y Y = 0 and
Z Z = Z ZZ = Z Z Z = Z :
F = Y Z + X ‾ Y ‾ Z + X ‾ Z F = YZ + \overline{X}\overline{Y}Z + \overline{X}Z F = Y Z + X Y Z + X Z Factoring out
X ‾ Z \overline{X}Z X Z :
F = Y Z + X ‾ Z ( 1 + Y ‾ ) F = YZ + \overline{X}Z(1 + \overline{Y}) F = Y Z + X Z ( 1 + Y ) Since
1 + Y ‾ = 1 1 + \overline{Y} = 1 1 + Y = 1 :
F = Y Z + X ‾ Z = Z ( Y + X ‾ ) F = YZ + \overline{X}Z = Z(Y + \overline{X}) F = Y Z + X Z = Z ( Y + X ) Step 2: Find the complement F ‾ \overline{F} F Using De Morgan's laws:
F ‾ = Z ( Y + X ‾ ) ‾ \overline{F} = \overline{Z(Y + \overline{X})} F = Z ( Y + X ) F ‾ = Z ‾ + ( Y + X ‾ ) ‾ \overline{F} = \overline{Z} + \overline{(Y + \overline{X})} F = Z + ( Y + X ) F ‾ = Z ‾ + Y ‾ X = X Y ‾ + Z ‾ \overline{F} = \overline{Z} + \overline{Y}X = X\overline{Y} + \overline{Z} F = Z + Y X = X Y + Z Step 3: Evaluate the given options
Option (A): ( X ‾ + Y ‾ + Z ‾ ) ( X + Y ‾ ) ( Y + Z ‾ ) (\overline{X} + \overline{Y} + \overline{Z})(X + \overline{Y})(Y + \overline{Z}) ( X + Y + Z ) ( X + Y ) ( Y + Z ) F F F X Y ‾ + Z ‾ X\overline{Y} + \overline{Z} X Y + Z Option (B): X Y ‾ + Z ‾ X\overline{Y} + \overline{Z} X Y + Z F ‾ \overline{F} F correct .Option (C): ( X + Z ‾ ) ( Y ‾ + Z ‾ ) = X Y ‾ + X Z ‾ + Z ‾ Y ‾ + Z ‾ = X Y ‾ + Z ‾ ( X + Y ‾ + 1 ) = X Y ‾ + Z ‾ (X + \overline{Z})(\overline{Y} + \overline{Z}) = X\overline{Y} + X\overline{Z} + \overline{Z}\overline{Y} + \overline{Z} = X\overline{Y} + \overline{Z}(X + \overline{Y} + 1) = X\overline{Y} + \overline{Z} ( X + Z ) ( Y + Z ) = X Y + X Z + Z Y + Z = X Y + Z ( X + Y + 1 ) = X Y + Z correct .Option (D): X Y ‾ + Y Z ‾ + X ‾ Y ‾ Z ‾ = X Y ‾ + X ‾ Y ‾ Z ‾ + Y Z ‾ = Y ‾ ( X + X ‾ Z ‾ ) + Y Z ‾ = Y ‾ ( X + Z ‾ ) + Y Z ‾ = X Y ‾ + Y ‾ Z ‾ + Y Z ‾ = X Y ‾ + Z ‾ ( Y ‾ + Y ) = X Y ‾ + Z ‾ X\overline{Y} + Y\overline{Z} + \overline{X}\overline{Y}\overline{Z} = X\overline{Y} + \overline{X}\overline{Y}\overline{Z} + Y\overline{Z} = \overline{Y}(X + \overline{X}\overline{Z}) + Y\overline{Z} = \overline{Y}(X + \overline{Z}) + Y\overline{Z} = X\overline{Y} + \overline{Y}\overline{Z} + Y\overline{Z} = X\overline{Y} + \overline{Z}(\overline{Y} + Y) = X\overline{Y} + \overline{Z} X Y + Y Z + X Y Z = X Y + X Y Z + Y Z = Y ( X + X Z ) + Y Z = Y ( X + Z ) + Y Z = X Y + Y Z + Y Z = X Y + Z ( Y + Y ) = X Y + Z correct .
Therefore, options (B), (C), and (D) are equivalent to
F ‾ \overline{F} F .
Understand the concept, then try another question Revisit Digital Logic with concept notes, common mistakes and an original worked example before your next attempt.
More questions on Boolean Algebra & Logic Gates ← Q51 Full paper Q53 → 