GATE loves a question that looks like minimization but is really counting: given F(A, B, C, D) as a sum of minterms, how many prime implicants does the function have, and how many of them are essential? Students who can find a minimal expression still get this wrong, because minimizing lets you skip groups while counting forbids it. The count needs its own procedure, one that enumerates every maximal group before any of them is judged essential. On a busy map, visual grouping quietly drops prime implicants, and the Quine-McCluskey prime implicant chart takes over: a column holding a single cross names an essential prime implicant outright.
Prime implicants and essential prime implicants: definitions first
An implicant of a Boolean function is a product term that is 1 only where the function is 1. On a K-map, every valid group of 1s (of size 1, 2, 4, 8, always a power of two) is an implicant.
A prime implicant (PI) is an implicant that cannot be grown any further. If doubling the group in any direction still covers only 1s, the smaller group was not prime.
An essential prime implicant (EPI) is a prime implicant that covers at least one minterm no other prime implicant covers. That minterm forces the PI into every minimal expression, which is what "essential" means.
Three different numbers live in this topic, and GATE deliberately makes you separate them: the number of prime implicants, the number of essential prime implicants, and the number of product terms in a minimal sum of products. They can all be different for the same function, and Example 3 below is exactly such a case.
A five-step procedure to count essential prime implicants
Run these steps in order on any map, without shortcuts:
Plot the minterms on the K-map.
List every maximal group, not just the groups you would pick for minimization. Take each 1 and grow it in all directions until it cannot double again; record each distinct maximal group once. This list is the complete set of prime implicants.
Under each minterm, write down which prime implicants from step 2 cover it.
Scan the minterms. Wherever a minterm is covered by exactly one prime implicant, mark that prime implicant essential.
Count the distinct marked PIs. That count is the number of essential prime implicants. Everything unmarked is a non-essential PI, even if it would appear in some minimal expression.
The classic mistake sits in step 2. If you list only the groups your eye picks for a minimal cover, you undercount PIs and then miscount EPIs, because step 4 depends on knowing every PI that touches each minterm. Counting questions punish good minimization habits, so slow down and enumerate.
Solved example 1: corners and centre, every prime implicant essential
Take F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
Step 2 gives exactly two maximal groups. The four corners wrap into a single quad, B'D', covering minterms 0, 2, 8, 10. The centre 2x2 block is the quad BD, covering 5, 7, 13, 15. No other group survives the grow test.
Step 3 and 4: every minterm in B'D' is covered only by B'D', and every minterm in BD only by BD. Both PIs get marked.
Count: 2 prime implicants, 2 essential prime implicants. The minimal expression is BD + B'D', and here all three numbers coincide at 2.
Solved example 2: three prime implicants, only two essential
Now F(A, B, C, D) = Σm(2, 3, 6, 7, 8, 10, 12, 14).
Step 2, enumerated honestly, produces three maximal quads:
A'C, covering minterms 2, 3, 6, 7 (the top-right 2x2 block)
AD', covering minterms 8, 10, 12, 14 (the bottom two rows on the D = 0 columns, wrapped)
CD', covering minterms 2, 6, 10, 14 (the entire rightmost column)
The third one is the group students miss, because a minimal cover never needs it. But it is maximal, so it is a prime implicant and it must be on the list.
Step 3 and 4, minterm by minterm: 3 and 7 are covered only by A'C, so A'C is essential. 8 and 12 are covered only by AD', so AD' is essential. Every cell of CD' (2, 6, 10, 14) is also covered by A'C or AD', so CD' never gets a unique minterm.
Count: 3 prime implicants, 2 essential prime implicants. The two EPIs already cover all eight minterms, so the minimal expression is A'C + AD' and CD' is fully redundant. If the question asks "how many prime implicants" and you answer 2, you have answered a different question.
Solved example 3: Quine-McCluskey and the prime implicant chart
For F(A, B, C, D) = Σm(2, 3, 4, 5, 6, 7, 9, 11, 12, 13), the map is busy enough that visual grouping starts dropping PIs. This is where the Quine-McCluskey method earns its place: group the minterms by the number of 1s in their binary form, repeatedly combine terms differing in exactly one bit, and the terms that never combine further are the prime implicants. It is the same grow-until-you-cannot rule, run as a table.
Group the ten minterms by how many 1s they carry: one for 2 and 4, two for 3, 5, 6, 9 and 12, three for 7, 11 and 13. Pairing terms from adjacent groups that differ in exactly one bit gives thirteen size-2 terms, each written with a dash where the differing bit vanished. Pair those again, matching dash position and one differing bit, and three size-4 terms fall out.
Size-4 term | Formed from | Covers |
|---|---|---|
A'C (0-1-) | (2,3) + (6,7), or (2,6) + (3,7) | 2, 3, 6, 7 |
A'B (01--) | (4,5) + (6,7), or (4,6) + (5,7) | 4, 5, 6, 7 |
BC' (-10-) | (4,5) + (12,13), or (4,12) + (5,13) | 4, 5, 12, 13 |
Nothing pairs a third time, because those three carry their dashes in different positions. And three of the size-2 terms never combined at all: (3, 11) = B'CD, (9, 11) = AB'D and (9, 13) = AC'D. A term that never combines is prime by definition, so the six prime implicants are A'C, A'B, BC', B'CD, AB'D and AC'D.
Now build the prime implicant chart: one row per prime implicant, one column per minterm, a cross where the PI covers the minterm.
PI | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|
A'C (2,3,6,7) | X | X |
|
| X | X |
|
|
|
|
A'B (4,5,6,7) |
|
| X | X | X | X |
|
|
|
|
BC' (4,5,12,13) |
|
| X | X |
|
|
|
| X | X |
AC'D (9,13) |
|
|
|
|
|
| X |
|
| X |
AB'D (9,11) |
|
|
|
|
|
| X | X |
|
|
B'CD (3,11) |
| X |
|
|
|
|
| X |
|
|
A column with a single cross marks an essential prime implicant. Column 2 has one cross, on A'C. Column 12 has one cross, on BC'. Every other column has two or more crosses. So the EPIs are exactly A'C and BC'.
Count: 6 prime implicants, 2 essential prime implicants. And a third number hides here: after A'C and BC' cover minterms 2, 3, 4, 5, 6, 7, 12, 13, the leftovers 9 and 11 are both covered by AB'D, so a minimal expression is A'C + BC' + AB'D, three terms. Six PIs, two EPIs, three terms in the minimal SOP.
Prime implicant questions in GATE: what the paper actually asks
The topic shows up in three shapes: a numerical answer asking for the number of PIs or EPIs, a multiple-select asking which listed terms are essential, and an expression question asking for the minimal SOP. All three are the same five-step procedure with different final lines. Exam structure details like marks per question and negative marking change by cycle, so confirm those on the official GATE 2026 portal and in its information brochure.
For drilling, KnowledgeGate's question bank carries over 1,500 Digital Electronics questions, and more than 130 of them sit in the K-map structure and prime implicants subtopic alone. You can work through them, with full solutions, on the Boolean Minimization learn module. To see how much weight Digital Logic pulls relative to the rest of the paper, read our breakdown of GATE CS subject weightage before you decide how many hours this topic deserves.
The short version
Counting prime implicants is a procedure, not an art. Plot the minterms, list every maximal group, map each minterm to its covering PIs, mark the PIs that own a minterm alone, and count. Keep the three numbers (PIs, EPIs, minimal-SOP terms) separate in your head, because the examiner will not.
Once the procedure feels mechanical on paper, test it under a clock. The GATE Test Series runs 46 tests, 39 subject-wise grand tests (three of them on Digital Electronics) plus 7 full-length mocks, with rank lists and per-topic reports that will tell you whether K-map counting is still leaking marks. If you are earlier in your preparation, start from the GATE category page and build the subject first; the counting questions will still be waiting when you are ready.
