Tabular minimization and prime implicant covers
Two separate problems
Finding every useful group is not the same as choosing the groups needed to implement a function. The Quine–McCluskey tabular method first generates prime implicants, then selects a cover of required one-rows. We minimize a two-level SOP by number of product terms first and total literals second. This stated cost model does not guarantee minimum delay or minimum transistor count in an arbitrary technology.
Prerequisites: minterms, Boolean SOP, Gray-map grouping and don’t-cares. Variables are ordered A,B,C,D with A the most significant index bit. A dash in a cube such as 0-01 means that input can take either value; it is not a minus sign. The cube represents A′C′D and covers rows 1 and 5.
An implicant covers only required ones or allowed don’t-cares, never a required zero. A prime implicant cannot be enlarged by dropping another literal while retaining that property. An essential prime covers at least one required one that no other prime covers. “Prime” does not mean “essential”: many primes can be optional.
The combination rule
Start with every on-set minterm and any declared don’t-cares, grouped by number of 1 bits. Two cubes combine when their dash positions are identical and they differ in exactly one remaining fixed bit. Replace that differing position by a dash. For example 0010 and 0110 combine to 0-10. Later 0-10 and 1-10 combine to --10. But 0-10 and -010 cannot combine: their dash positions differ, even though some visible bits match.
Mark each cube used in a combination. Deduplicate resulting cubes while preserving which rows they cover. Continue until no further combination is possible. Every uncombined cube at any level is a prime. Keeping only the last level would lose smaller primes that could not combine earlier.
Worked four-variable example
Let F=Σm(0,1,2,5,6,7,8,9,10,14), with no don’t-cares. Group its binary minterms by one-count:
| Ones | Minterms |
|---|---|
| 0 | 0000 |
| 1 | 0001, 0010, 1000 |
| 2 | 0101, 0110, 1001, 1010 |
| 3 | 0111, 1110 |
The distinct first-round pairs are 000-, 00-0, -000, 0-01, -001, 0-10, -010, 100-, 10-0, 01-1, 011-, -110 and 1-10. Each covers two specified ones; check the missing fixed bit against the source pair.
The second round produces -00-, -0-0 and --10. For example, 000- with 100- yields -00-, and 0-10 with 1-10 yields --10. Different paths can generate the same cube, so duplicates must be merged. No two of these final cubes have the same dash positions with just one fixed-bit difference, so no third-round combination is possible.
The uncombined first-round cubes 0-01,01-1,011- remain prime as well. All six primes are:
| Name | Cube | Product | Required rows covered |
|---|---|---|---|
| P | -00- | B′C′ | 0,1,8,9 |
| Q | -0-0 | B′D′ | 0,2,8,10 |
| R | --10 | CD′ | 2,6,10,14 |
| S | 0-01 | A′C′D | 1,5 |
| T | 01-1 | A′BD | 5,7 |
| U | 011- | A′BC | 6,7 |
A coverage chart places required rows on one axis and primes on the other, marking membership. The table above is the same information in compact set form.
Select essentials then finish the cover
Row 9 is covered only by P, so P is essential. Row 14 is covered only by R, so R is essential. Together P and R cover {0,1,2,6,8,9,10,14}. Rows 5 and 7 remain. T covers both, while choosing S and U would require two additional terms. Thus the minimum cover is P+R+T=B′C′+CD′+A′BD.
Why is this optimal under our cost model? P and R are forced by unique rows. Neither covers row 5, so at least one more term is necessary. T supplies that one term and also covers row 7. Hence three terms are necessary and sufficient; the selected terms contain 2+2+3=7 literals. Verify the union of their rows equals the on-set exactly. A prime like Q can be valid but unnecessary in a minimum cover.
What if there are no essentials
For H(A,B,C)=Σm(0,1,2,5,6,7), every prime is a pair: P1=00-, P2=0-0, P3=11-, P4=1-1, P5=-01 and P6=-10. Each required row belongs to two primes, so no prime is essential. That does not mean the function cannot be minimized.
Introduce selection variables P1…P6, meaning “choose this prime.” To cover each row, write the OR of its available primes; AND these requirements. The cover condition is
(P1+P2)(P1+P5)(P2+P6)(P4+P5)(P3+P6)(P3+P4).
This is a Boolean expression over selection decisions, not the original input variables. Expand using X·X=X and absorption X+XY=X, or enumerate small candidate subsets. The smallest solutions are {P1,P4,P6} and {P2,P3,P5}. Each has three two-literal terms. Two pairs cover at most four distinct rows, so at least three terms are needed for six required rows. Multiple minimal covers can be equally valid. A systematic cover expression is often called Petrick's method.
Don't-cares and checking limits
Don't-cares may help generate larger primes, but only required ones become mandatory chart columns. A prime covering only don’t-cares need not be selected. Example: on-set {1,3}, don’t-cares {5,7} in three variables yield cube --1, or C. It covers all required ones and no required zero. If row 7 were instead a required zero, that cube would be invalid.
For a fully specified all-zero function, use F=0; no one-row cover is needed. For all-one output, the all-dash cube gives F=1. Keep variable order consistent and do not confuse a dash cube with a particular input assignment. Check all specified rows after minimization. The tabular method is exact for this two-level problem but may generate many cubes/cover candidates; a small worked example does not imply efficient scaling to arbitrarily many inputs.
Original practice
These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.
C01. Which pair of cubes can combine in one tabular step?
A. 0-10 and -010 B. 0010 and 0110 C. 0000 and 0011 D. 00-0 and 0-00
Answer: B
A is incorrect: dash positions differ.
B is correct: only B differs, producing 0-10.
C is incorrect: two fixed bits differ.
D is incorrect: dash positions differ.
C02. What makes a prime implicant essential?
A. It contains the fewest literals of all primes. B. It appears in the last combination round. C. It covers a required one-row covered by no other prime. D. It covers any don’t-care.
Answer: C
A is incorrect: size alone does not establish unique coverage.
B is incorrect: primes from earlier rounds can be essential.
C is correct: its unique required row forces selection in every prime cover.
D is incorrect: don’t-care rows do not require coverage.
C03. In the worked four-variable chart, row 9 is covered only by P and row 14 only by R. After choosing P,R, rows 5,7 remain, both covered by T. What minimum term count follows?
A. 3 B. 2 C. 6 D. 1
Answer: A
A is correct: P and R are forced, and one more term T is necessary and sufficient.
B is incorrect: P and R leave required rows uncovered.
C is incorrect: all six primes need not be selected.
D is incorrect: two distinct forced primes already exist.
C04. Why must uncombined cubes from earlier rounds be retained?
A. They always represent forbidden zeros. B. They are all redundant duplicates. C. They must all be chosen in the final cover. D. They are prime implicants even if other cubes combine further.
Answer: D
A is incorrect: valid cubes do not include required zeros.
B is incorrect: an uncombined cube may be a distinct necessary prime.
C is incorrect: prime generation and cover selection are separate decisions.
D is correct: being unable to enlarge is the prime condition.
C05. In a prime chart for an incompletely specified function, which rows must be covered?
A. Every don’t-care only B. Every required one-row C. Every required zero-row D. Every binary row
Answer: B
A is incorrect: don’t-cares may assist grouping but need not be covered.
B is correct: SOP must include all required ones and exclude required zeros.
C is incorrect: covering a required zero in SOP changes the function incorrectly.
D is incorrect: required zeros must stay zero.
C06. Six required rows are covered by pair-sized primes, with no larger implicant. A valid cover using three such primes exists. What is the minimum number of terms?
A. 2 B. 6 C. 3 D. Cannot be determined even with the stated cover
Answer: C
A is incorrect: two pairs cover at most four different rows.
B is incorrect: three terms already provide a valid cover.
C is correct: at least ceiling(6/2)=3 are needed and a three-term cover is available.
D is incorrect: the lower bound and matching construction prove the minimum.
Scope and sources
This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.
Sources checked 14 October 2026.
Sign in to keep your progress. Sign in