The GATE Grind

GATE Digital Logic: Boolean Algebra and Minimization – Previous Year Questions

49 GATE previous year questions on Boolean Algebra and Minimization (Digital Logic, Computer Science) with answers and explanations, from every paper.

49 questions worth 75 marks in all (23 1-mark, 26 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q3 (1 mark, Multiple choice) – What maximum number of different Boolean functions involve n Boolean variables?
  2. GATE 2007 CS Q9 (1 mark, Multiple choice) – For f(w,x,y,z)=(1,3,4,6,9,11,12,14), the function is
  3. GATE 2007 CS Q32 (2 marks, Multiple choice) – Let f(w,x,y,z)=(0,4,5,7,8,9,13,15). Which expressions are NOT equivalent to f? P. x y z+w xy+wy z+xz Q. w y z+wx y+xz R. w y z+wx y+xyz+xy z S. x y…
  4. GATE 2007 CS Q33 (2 marks, Multiple choice) – Define X*Y=XY+X Y. Let Z=X*Y. Which are valid? P: X=Y*Z; Q: Y=X*Z; R: X*Y*Z=1.
  5. GATE 2008 CS Q5 (1 mark, Multiple choice) – In the shown Karnaugh map, X denotes a don’t-care. Find the minimal function.
  6. GATE 2008 CS Q8 (1 mark, Multiple choice) – For the circuit shown, f 1= m(4,5,6,7,8), f 3= m(1,6,15) and f= m(1,6,8,15). What is f 2?
  7. GATE 2008 CS Q26 (2 marks, Multiple choice) – Simplify (P+ Q)(P Q+PR)( P R+ Q).
  8. GATE 2009 CS Q6 (1 mark, Multiple choice) – What is the minimum number of gates required to implement the Boolean function AB+C if we have to use only 2-input NOR gates?
  9. GATE 2021 CS (CS2) Q62 (2 marks, Numerical answer) – Boolean f(w,x,y,z) satisfies f(w,0,0,z)=1, f(1,x,1,z)=x+z, f(w,1,y,z)=wz+y. Find the number of literals in a minimal sum-of-products expression.
  10. GATE 2015 CS (CS3) Q16 (1 mark, Multiple choice) – Define X\#Y=X+Y on Boolean variables. S1: (P#Q)#R=P#(Q#R). S2: Q#R=R#Q. Which hold?
  11. GATE 2015 CS (CS3) Q40 (2 marks, Multiple choice) – For F=P+QR, consider S1 F=(4,5,6); S2 F=(0,1,2,3,7); S3 F=(4,5,6); S4 F=(0,1,2,3,7). Which truth-value pattern applies?
  12. GATE 2015 CS (CS3) Q62 (2 marks, Numerical answer) – Find the number of prime implicants of f(w,x,y,z)=Σ(0,2,4,5,6,10).
  13. GATE 2015 CS (CS2) Q55 (2 marks, Numerical answer) – How many minterms remain after minimizing [D+AB+A C+AC D+A C D]?
  14. GATE 2010 CS Q16 (1 mark, Multiple choice) – Find the minterm expansion of f(P,Q,R)=PQ+Q R+P R.
  15. GATE 2010 CS Q41 (2 marks, Multiple choice) – Find the output of the NOR-gate network shown.
  16. GATE 2011 CS Q23 (1 mark, Multiple choice) – Which shown circuit is NOT equivalent to a two-input XNOR gate?
  17. GATE 2011 CS Q24 (1 mark, Multiple choice) – Simplify (P+ Q+ R)(P+ Q+R)(P+Q+ R) to SOP.
  18. GATE 2013 CS Q31 (1 mark, Multiple choice) – Which does NOT represent XNOR of x,y?
  19. GATE 2012 CS Q16 (1 mark, Multiple choice) – A truth table gives f(0,0)=0, f(0,1)=0, f(1,0)=1, f(1,1)=1. Which Boolean function is it?
  20. GATE 2012 CS Q40 (2 marks, Multiple choice) – Minimize the shown four-variable Karnaugh map. X marks don’t-care cells; blank cells are zeros.
  21. GATE 2017 CS (CS2) Q37 (2 marks, Multiple choice) – For Boolean variables w,x,y,z, which identity is INCORRECT?
  22. GATE 2017 CS (CS2) Q38 (2 marks, Multiple choice) – f(w,x,y,z)= m(0,1,2,3,7,8,10)+ d(5,6,11,15), with d denoting Karnaugh-map don’t-cares. Find a minimum product of sums.
  23. GATE 2016 CS (CS2) Q18 (1 mark, Multiple choice) – Boolean variables satisfy x 1 x 2 x 3 x 4=0. Which must hold?
  24. GATE 2014 CS (CS3) Q17 (1 mark, Multiple choice) – F(P,Q,R,S)= m(0,2,5,7,8,10,13,15), with minterms 2,7,8,13 treated as don’t-cares. Find the minimal sum-of-products form.
  25. GATE 2014 CS (CS3) Q65 (2 marks, Multiple choice) – With XOR denoted and binary constants 1,0, simplify F(P,Q)=((1 P)(P Q))((P Q)(Q0)).
  26. GATE 2014 CS (CS2) Q16 (1 mark, Multiple choice) – The dual FD of Boolean function F(x 1,,x n,+,,) swaps + and ·. F is self-dual when F=FD. How many self-dual functions of n Boolean variables exist?
  27. GATE 2014 CS (CS1) Q17 (1 mark, Multiple choice) – Find the minimal sum-of-products form of F(P,Q,R,S)=PQ+ PQR+ PQ RS.
  28. GATE 2017 CS (CS1) Q31 (1 mark, Numerical answer) – Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. [Karnaugh map with columns ba = 00, 01, 11, 10 and rows…
  29. GATE 2016 CS (CS1) Q16 (1 mark, Multiple choice) – Consider the Boolean operator \# with the following properties: x \# 0 = x, x \# 1 = x, x \# x = 0 and x \# x = 1. Then x \# y is equivalent to
  30. GATE 2015 CS (CS1) Q40 (2 marks, Multiple choice) – The binary operator is defined by the following truth table. p q p q --- --- --- 0 0 0 0 1 1 1 0 1 1 1 0 Which one of the following is true about the…
  31. GATE 2015 CS (CS1) Q43 (2 marks, Multiple choice) – Consider the operations f(X, Y, Z) = X'YZ + XY' + Y'Z' and g(X, Y, Z) = X'YZ + X'YZ' + XY. Which one of the following is correct?
  32. GATE 2018 CS Q14 (1 mark, Multiple choice) – Let and denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?
  33. GATE 2018 CS Q59 (2 marks, Numerical answer) – Consider the minterm list form of a Boolean function F given below. F(P,Q,R,S)= m(0,2,5,7,9,11)+d(3,8,10,12,14) Here, m denotes a minterm and d…
  34. GATE 2019 CS Q16 (1 mark, Multiple choice) – Which one of the following is NOT a valid identity?
  35. GATE 2019 CS Q60 (2 marks, Numerical answer) – What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as…
  36. GATE 2026 CS (CS2) Q16 (1 mark, Multiple choice) – Which one of the following options is not a property of Boolean algebra? Note: + is OR, is AND, and ' is NOT.
  37. GATE 2026 CS (CS2) Q40 (2 marks, Multiple choice) – Consider the 4-variable Boolean function F(A,B,C,D)= m(0,1,2,3,8,9,10,11). Taking A as MSB and D as LSB, which one of the following represents the…
  38. GATE 2026 CS (CS1) Q21 (1 mark, Multiple select) – Consider the following Boolean expression of a function F: F(P, Q) = (P + Q) (PQ) Which of the following expressions is/are equivalent to F?
  39. GATE 2026 CS (CS1) Q48 (2 marks, Multiple select) – Consider a Boolean function F with the following minterm expression: F(P, Q, R, S) = m(1, 2, 3, 4, 5, 7, 10, 12, 13, 14) Which of the following…
  40. GATE 2025 CS (CS2) Q43 (2 marks, Multiple select) – Given the following Karnaugh Map for a Boolean function F(w,x,y,z) (rows wx = 00, 01, 11, 10; columns yz = 00, 01, 11, 10): wx yz 00 01 11 10 --- ---…
  41. GATE 2025 CS (CS2) Q50 (2 marks, Multiple select) – Which of the following Boolean algebraic equation(s) is/are CORRECT?
  42. GATE 2025 CS (CS1) Q24 (1 mark, Multiple select) – Let X be a 3-variable Boolean function that produces output as '1' when at least two of the input variables are '1'. Which of the following…
  43. GATE 2025 CS (CS1) Q42 (2 marks, Multiple choice) – Consider the following four variable Boolean function in sum-of-product form F(b 3,b 2,b 1,b 0) = (0,2,4,8,10,11,12). where the value of the function…
  44. GATE 2025 CS (CS1) Q59 (2 marks, Numerical answer) – Consider a finite state machine (FSM) with one input X and one output f, represented by the given state transition table. The minimum number of states…
  45. GATE 2024 CS (CS2) Q30 (1 mark, Multiple select) – For a Boolean variable x, which of the following statements is/are FALSE?
  46. GATE 2024 CS (CS2) Q50 (2 marks, Multiple select) – Consider 4-variable functions f1 = Σ(0,2,3,5,7,8,11,13), f2 = Σ(1,3,5,7,11,13,15), f3 = Σ(0,1,4,11), f4 = Σ(0,2,6,13). The circuit computes Y = (f1…
  47. GATE 2024 CS (CS1) Q47 (2 marks, Multiple select) – Consider a Boolean expression given by F(X,Y,Z)=(3,5,6,7). Which of the following statements is/are CORRECT?
  48. GATE 2021 CS (CS1) Q52 (2 marks, Multiple select) – Consider the following Boolean expression. F = (X+Y+Z)(X+Y)(Y+Z) Which of the following Boolean expressions is/are equivalent to F (complement of F)?
  49. GATE 2020 CS Q38 (2 marks, Multiple choice) – Consider the Boolean function z(a,b,c). Which one of the following minterm lists represents the circuit given above?