Boolean algebra and Karnaugh maps are the load-bearing skills of a digital electronics paper: get simplification and minimal SOP or POS right and the combinational-circuit questions later become almost free. Yet this is exactly where aspirants lose marks, misapplying a law, forgetting that duality swaps AND with OR, or grouping a K-map without folding in the don't-care cells. Every question below appeared in a GATE paper and carries the year it was set. Attempt one before you read the answer, then open the linked full solution when you want every step spelled out. If a rule itself still feels shaky, the theory behind it sits in the Digital Electronics learn module.
Boolean algebra laws, duality and DeMorgan
Q1. Which one of the following is not a property of Boolean algebra? Here + denotes OR, . denotes AND, and ′ denotes NOT. (GATE 2026)
(a) a + b = b + a
(b) a . a′ = 1
(c) a + a′ = 1
(d) a . b = b . a
Answer: (b) a . a′ = 1. The complement law says a variable ANDed with its own complement is 0, not 1, because a and a′ can never both be true. Options (a) and (d) are the commutative law, and (c) is the correct OR form of the complement law. This is a definition-check question, and the trap is the near-symmetry between a + a′ = 1 and a . a′ = 0 (see the full solution).
Q2. The dual of a Boolean function is the same expression with + and . swapped, and F is self-dual if F equals its dual. The number of self-dual functions of n Boolean variables is (GATE 2014)
(a) 2^n
(b) 2^(n-1)
(c) 2^(2^n)
(d) 2^(2^(n-1))
Answer: (d) 2^(2^(n-1)). Duality pairs every input with its bitwise complement, splitting the 2^n input rows into 2^(n-1) complementary pairs. Self-duality forces the output on one member of a pair to fix the other, so you freely choose only 2^(n-1) output bits, giving 2^(2^(n-1)) functions. A corollary worth carrying into the exam: each pair contributes one 1 and one 0, so a self-dual function is true on exactly half of its 2^n rows (see the full solution).
Q3. Let the operation ∗ be defined as x ∗ y = x′ + y. If z = x ∗ y, the value of z ∗ x is (GATE 1997)
(a) x′ + y
(b) x
(c) 0
(d) 1
Answer: (b) x. The operation is just implication, x′ + y. Substitute z = x′ + y into z ∗ x = z′ + x, so it becomes (x′ + y)′ + x. By DeMorgan (x′ + y)′ = x . y′, and x . y′ + x absorbs to x. Recognising a disguised standard operator is half the battle in these algebra questions (see the full solution).
Expression simplification
Q4. The Boolean function x′y′ + xy + x′y is equivalent to (GATE 2004)
(a) x′ + y′
(b) x + y
(c) x + y′
(d) x′ + y
Answer: (d) x′ + y. Factor x′ out of the first and third terms: x′(y′ + y) = x′, leaving x′ + xy. Now apply the absorption identity x′ + xy = x′ + y. Pulling out a common literal before reaching for a K-map is usually the quickest path on three-term expressions (see the full solution).
Q5. The function AB′C + A′BC + ABC′ + A′B′C + AB′C′ is equivalent to (GATE 2004)
(a) AC′ + AB + A′C
(b) AB′ + AC′ + A′C
(c) A′B + AC′ + AB′
(d) A′B + AC + AB′
Answer: (b) AB′ + AC′ + A′C. Combine the two C′ terms, ABC′ + AB′C′ = AC′, then group the three C terms, AB′C + A′BC + A′B′C = C(AB′ + A′), which expands to AB′C + A′C. Bringing AC′ back in, AC′ + AB′C = A(C′ + B′C) = AC′ + AB′, so the whole expression is AB′ + AC′ + A′C. On a three-variable map (A most significant) the answer falls out by sight: the ON-cells m1, m3, m4, m5 and m6 are covered by three pairs, m1 with m3 giving A′C, m4 with m5 giving AB′, and m4 with m6 giving AC′ (see the full solution).
Q6. For Boolean variables P, Q, R, the expression (P + Q′)(PQ′ + PR)(P′R′ + Q′) simplifies to (GATE 2008)
(a) PQ′
(b) PR′
(c) PQ′ + R
(d) PR′ + Q
Answer: (a) PQ′. Factor the middle bracket: PQ′ + PR = P(Q′ + R). Absorption gives (P + Q′) . P = P, so the product becomes P . (Q′ + R) . (P′R′ + Q′). Distributing P kills the P′R′ term (P . P′R′ = 0) and leaves P(Q′ + R)Q′ = PQ′. Watch for terms that vanish against their own complement (see the full solution).
SOP, POS and canonical forms
Q7. The minterm expansion of f(P, Q, R) = PQ + QR′ + PR′ is (GATE 2010)
(a) m2 + m4 + m6 + m7
(b) m0 + m1 + m3 + m5
(c) m0 + m1 + m6 + m7
(d) m2 + m3 + m4 + m5
Answer: (a) m2 + m4 + m6 + m7. Evaluate f for both values of R. With R = 0 the function is P + Q, true at 010, 100, 110, that is m2, m4, m6. With R = 1 only PQ survives, true at 111, that is m7. Collecting the ON-set gives m2 + m4 + m6 + m7. Splitting on one variable is faster than filling a full truth table (see the full solution).
Q8. The simplified SOP form of the POS expression (P + Q′ + R′)(P + Q′ + R)(P + Q + R′) is (GATE 2011)
(a) P′Q + R′
(b) P + Q′R′
(c) P′Q + R
(d) PQ + R
Answer: (b) P + Q′R′. Use the identity (X + Y)(X + Y′) = X on the first two factors with X = P + Q′, collapsing them to P + Q′. Apply the same distributive identity again to (P + Q′)(P + Q + R′): the common part is P, and Q′(Q + R′) = Q′R′, so the result is P + Q′R′. POS to SOP is cleanest when you spot repeated sum terms (see the full solution).
Q9. For F(P, Q, R, S) = PQ + P′QR + P′QR′S, the minimal sum-of-products form is (GATE 2014)
(a) PQ + QR + QS
(b) P + Q + R + S
(c) P′ + Q′ + R′ + S′
(d) P′R + R′P′S + P
Answer: (a) PQ + QR + QS. Every term contains Q, so factor it: F = Q(P + P′R + P′R′S). Apply X + X′Y = X + Y twice inside the bracket to reduce P + P′R + P′R′S to P + R + S. Multiplying Q back in gives PQ + QR + QS. Factoring a common literal before minimizing shrinks the K-map you actually have to draw (see the full solution).
K-maps and NAND/NOR realization
Q10. For f(w, x, y, z) = Σm(0,1,2,3,7,8,10) + Σd(5,6,11,15), where d marks don't-care cells, a minimum POS form is (GATE 2017)
(a) (w′ + z′)(x′ + z)
(b) (w′ + z)(x + z)
(c) (w + z)(x′ + z)
(d) (w + z′)(x′ + z)
Answer: (a) (w′ + z′)(x′ + z). For a POS you group the zeros, and each group becomes one sum term in complemented literals. The zeros here are cells 4, 9, 12, 13 and 14. Take 9 and 13 with the don't-cares 11 and 15: all four have w = 1 and z = 1, a quad that gives the sum term (w′ + z′). Take 4, 12 and 14 with the don't-care 6: all four have x = 1 and z = 0, a quad that gives (x′ + z). Two quads cover every zero and neither touches a minterm of f, so the minimum POS is (w′ + z′)(x′ + z) (see the full solution).
Q11. The minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function, using no other gate, is (GATE 2004)
(a) 3
(b) 4
(c) 5
(d) 6
Answer: (b) 4. Since NAND is functionally complete, XOR can be built from it alone, and the minimal network uses four gates: one computes A NAND B, two more combine it with A and with B, and a final NAND merges those. XNOR costs five: the same four-gate network plus one more NAND with its inputs tied together, acting as an inverter (see the full solution).
Q12. The minimum number of 2-input NOR gates required to implement the function AB + C is (GATE 2009)
(a) 2
(b) 3
(c) 4
(d) 5
Answer: (b) 3. Rewrite AB + C in product form using (A + C)(B + C) = AB + C. A NOR of A and C gives (A + C)′, a NOR of B and C gives (B + C)′, and a final NOR of those two outputs returns (A + C)(B + C), which is exactly AB + C. Reshaping the function to suit the available gate is the trick behind every NAND-only and NOR-only question (see the full solution).
How this set is examined
GATE keeps returning to four moves here: catching a misquoted law, absorbing a term with X + X′Y = X + Y, reading a grouping off a map, and re-shaping a function so a single universal gate can build it. The don't-care cells are where marks move most often, and the failure is quiet: skipping one still leaves a correct expression, just a larger one, so nothing looks wrong until none of the four printed options matches what you wrote. Complements are the other steady trap, since a . a′ = 0 while a + a′ = 1, and duality swaps the operators without complementing the variables, which is what separates a dual from a DeMorgan complement. The same functions get built out of MUXes and decoders in the Combinational circuits MCQs.
If minimization still feels slow, the full step-by-step derivations sit in our Boolean algebra and K-map minimization deep dive, which walks through simplification and grouping from scratch. GATE aspirants get the full digital electronics sequence inside GATE Guidance by Sanchit Sir, and you can place the subject in the wider syllabus on the GATE CS Exam page. Solve, review the ones you missed, and come back a week later; the second pass is where the marks get locked in.
