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. Below are 12 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE problem with the year marked. Attempt each before reading the explanation, which stays short on purpose. Every question here links its exact solved page; if a rule feels shaky, the full theory 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 solved page).
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. This is the DeMorgan-style symmetry between AND and OR made countable (see the solved page).
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 solved page).
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 solved page).
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′). The inner part simplifies to AB′ + A′C, and together with AC′ the whole expression is AB′ + AC′ + A′C. A five-minterm function almost always collapses to three product terms (see the solved page).
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 solved page).
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 solved page).
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 solved page).
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 minimising shrinks the K-map you actually have to draw (see the solved page).
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 from a K-map you group the zeros, and the don't-cares are yours to include in whichever grouping makes the largest rectangle. Here the zeros sit at 4, 9, 12, 13, 14; pulling in the useful don't-cares lets those zeros merge into two clean sum terms, (w′ + z′) and (x′ + z). Ignoring the don't-cares is the single most common K-map error (see the solved page).
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. Memorise the count of 4 for XOR and 5 for XNOR; both are staple exam facts (see the solved page).
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 solved page).
How this set is examined
The 12 questions above cover the full minimisation toolkit: the algebra laws and duality (Q1 to Q3), pure simplification (Q4 to Q6), moving between SOP, POS and canonical minterm forms (Q7 to Q9), and K-map grouping with universal-gate realisation (Q10 to Q12). The recurring lesson is that a smart algebraic factor, or a correctly used don't-care, beats brute-force expansion every time. These skills feed directly into the Combinational circuits MCQs, where the same functions get built out of MUXes and decoders.
If minimisation 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.
