Why it matters: The core of the subject: simplify an expression, count minterms, minimise with a K-map or build everything from NAND. Several marks every year.
removes k variables, leaves a product of n − k literals
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Simplify an expression or find its minimal SOP/POS
K-map with don't cares, or algebra with absorption/consensus.
★★★
Count minterms, prime implicants or essential prime implicants
Fill the K-map and count groups; watch the wrap-around edges.
★★★
Which function does the given circuit/expression compute?
Write the truth table and match; recognise XOR, majority, parity.
★★★
Universal gates and functional completeness
How many NAND gates for XOR; which sets of gates are complete.
★★★
Number of distinct (self-dual) functions
2^(2ⁿ) and 2^(2ⁿ⁻¹).
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
27 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
27 questions · 0 correct of 0 attempted · marks 0 / 42
Year:
GATE 2025 CS1 · Q24MSQ1 mark
Let X be a 3-variable Boolean function that produces output '1' when at least two of the input variables are '1'. Which of the following statement(s) is/are CORRECT, where a, b, c, d, e are Boolean variables?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS2 · Q31MSQ1 mark
Consider the following logic circuit diagram with inputs X and Y: the top gate is a NAND of X and Y; the second gate is an inverter on X; the third gate is an AND of X and the inverted Y. The three gate outputs feed one 3-input OR gate with output F. Which is/are the CORRECT option(s) for the output function F?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q42MCQ2 marks
Consider the following four variable Boolean function in sum-of-product form F(b₃, b₂, b₁, b₀) = Σ(0, 2, 4, 8, 10, 11, 12), where the value of the function is computed by considering b₃b₂b₁b₀ as a 4-bit binary number, where b₃ denotes the most significant bit and b₀ denotes the least significant bit. Note that there are no don't care terms. Which ONE of the following options is the CORRECT minimized Boolean expression for F?
GATE 2025 CS2 · Q43MSQ2 marks
Given the following Karnaugh Map for a Boolean function F(w, x, y, z): rows wx = 00, 01, 11, 10 and columns yz = 00, 01, 11, 10. Row 00: 1 0 0 1. Row 01: 0 1 1 0. Row 11: 0 1 1 0. Row 10: 1 0 0 1. Which one or more of the following Boolean expression(s) represent(s) F?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS2 · Q50MSQ2 marks
Which of the following Boolean algebraic equation(s) is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q30MSQ1 mark
For a Boolean variable x, which of the following statements is/are FALSE?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q47MSQ2 marks
Consider a Boolean expression given by F(X, Y, Z) = Σ(3, 5, 6, 7). Which of the following statements is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q50MSQ2 marks
Consider 4-variable functions f₁, f₂, f₃, f₄ expressed in sum-of-minterms form as given below. f₁ = Σ(0, 2, 3, 5, 7, 8, 11, 13), f₂ = Σ(1, 3, 5, 7, 11, 13, 15), f₃ = Σ(0, 1, 4, 11), f₄ = Σ(0, 2, 6, 13). The circuit: f₁ and f₂ go into an AND gate, f₃ and f₄ go into an OR gate, and the outputs of the AND and the OR go into an XOR gate with output Y. Which of the following options is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q42MSQ2 marks
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)?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 2 · Q52NAT2 marks
Consider a Boolean function f(w, x, y, z) such that f(w, 0, 0, z) = 1, f(1, x, 1, z) = x + z, f(w, 1, y, z) = wz + y. The number of literals in the minimal sum-of-products expression of f is ______.
GATE 2020 · Q28MCQ2 marks
Consider the Boolean function z(a, b, c). The circuit: input b goes through an inverter into one input of an AND gate whose other input is c; the AND output and the input a go into an OR gate whose output is z. Which one of the following minterm lists represents the circuit given above?
GATE 2019 Set 2 · Q30MCQ2 marks
Consider three 4-variable functions f₁, f₂ and f₃, which are expressed in sum-of-minterms as f₁ = Σ(0, 2, 5, 8, 14), f₂ = Σ(2, 3, 6, 8, 14, 15), f₃ = Σ(2, 7, 11, 14). For the following circuit with one AND gate and one XOR gate (f₁ and f₂ go into the AND gate; the AND output and f₃ go into the XOR gate), the output function f can be expressed as:
GATE 2019 Set 2 · Q50NAT2 marks
What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer: ______.
GATE 2018 · Q4MCQ1 mark
Let ⊕ and ⊙ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?
GATE 2018 · Q49NAT2 marks
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 denotes a don't care term. The number of essential prime implicants of the function F is ______.
GATE 2017 Set 1 · Q21NAT1 mark
Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. Columns are ba = 00, 01, 11, 10 and rows are dc = 00, 01, 11, 10. Row dc = 00: blank, X, X, blank. Row dc = 01: 1, blank, blank, X. Row dc = 11: 1, blank, blank, 1. Row dc = 10: blank, X, X, blank. Assume for all inputs (a, b, c, d), the respective complements (a′, b′, c′, d′) are also available. The above logic is implemented using 2-input NOR gates only. The minimum number of gates required is ______.
GATE 2017 Set 2 · Q27MCQ2 marks
If w, x, y, z are Boolean variables, then which one of the following is INCORRECT?
GATE 2017 Set 2 · Q28MCQ2 marks
Given f(w, x, y, z) = Σm(0, 1, 2, 3, 7, 8, 10) + Σd(5, 6, 11, 15), where d represents the don't-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w, x, y, z)?
GATE 2016 Set 1 · Q6MCQ1 mark
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
GATE 2016 Set 2 · Q8MCQ1 mark
Let x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0 where x₁, x₂, x₃, x₄ are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE?
GATE 2014 Set 2 · Q6MCQ1 mark
The dual of a Boolean function F(x₁, x₂, …, xₙ, +, ·, ′), written as FD, is the same expression as that of F with + and · swapped. F is said to be self-dual if F = FD. The number of self-dual functions with n Boolean variables is
GATE 2014 Set 1 · Q7MCQ1 mark
Consider the following Boolean expression for F: F(P, Q, R, S) = PQ + P′QR + P′QR′S. The minimal sum-of-products form of F is
GATE 2014 Set 3 · Q7MCQ1 mark
Consider the following minterm expression for F: F(P, Q, R, S) = Σ(0, 2, 5, 7, 8, 10, 13, 15). The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sum-of-products form for F is
GATE 2014 Set 3 · Q55MCQ2 marks
Let ⊕ denote the Exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for F over two variables P and Q: F(P, Q) = ((1 ⊕ P) ⊕ (P ⊕ Q)) ⊕ ((P ⊕ Q) ⊕ (Q ⊕ 0)). The equivalent expression for F is
GATE 2013 Code A · Q21MCQ1 mark
Which one of the following expressions does NOT represent exclusive NOR of x and y?
GATE 2012 Code A · Q6MCQ1 mark
The truth table: X Y f(X, Y): 0 0 → 0, 0 1 → 0, 1 0 → 1, 1 1 → 1. It represents the Boolean function
GATE 2012 Code A · Q30MCQ2 marks
What is the minimal form of the Karnaugh map shown below? Assume that X denotes a don't care term. Columns are ab = 00, 01, 11, 10 and rows are cd = 00, 01, 11, 10. Row cd = 00: 1, X, X, 1. Row cd = 01: X, blank, blank, 1. Row cd = 11: all blank. Row cd = 10: 1, blank, blank, X.
Common traps
Distribution works both ways: A + BC = (A + B)(A + C). Beginners forget the second form.
K-map edges wrap: the four corners of a 4-variable map form one group.
A prime implicant need not be in the minimal cover; an essential one always is.
Don't-care cells are optional: use them to make groups bigger, never add them as required terms.