Karnaugh maps and canonical Boolean forms
Why rearrange a truth table
A truth table tells us a function's value on every input. A Karnaugh map places the same rows in an order that makes one-bit changes visible, helping combine product terms. We use ideal, steady-state Boolean logic: + is OR, juxtaposition is AND and a prime is NOT. Variable order is A,B,C or A,B,C,D, with A the most significant bit in every numerical row index.
Prerequisites: Boolean identities, minterms and binary indexing. Goals: translate on-set and off-set notation, form valid map groups, explain which literals disappear, and check a small simplification. The scope is three-variable maps plus a four-variable wraparound example, not tabular minimization, hazard removal or general minimum-cost circuit synthesis.
Minterms describe ones and maxterms describe zeros
A minterm m_i is 1 only at row i. For row 101, m_5=AB′C. Complement a variable whose row bit is 0, then AND all variables. F=Σm(0,2,3,6,7) means F is 1 on exactly those rows and 0 elsewhere, unless don’t-cares are separately declared. The Σ symbol here denotes OR of minterms, not arithmetic addition of row numbers.
A maxterm M_i is 0 only at row i. For row 101, M_5=A′+B+C′: each literal is 0 at that row, so their OR is 0. To form a maxterm, complement a variable whose row bit is 1. This is the opposite bit-to-literal convention from a minterm.
For a fully specified three-variable function, the above on-set has off-set {1,4,5}. Therefore F=ΠM(1,4,5)=(A+B+C′)(A′+B+C)(A′+B+C′). The Π denotes AND of maxterms. Each off-set row makes one factor zero; at an on-set row every factor is one. Canonical SOP and canonical POS encode the same function, but need not have the same number of written terms.
Lay out a three-variable map
Use rows A=0,1 and columns BC in Gray order 00,01,11,10. Adjacent labels differ in exactly one bit. Ordinary binary order 00,01,10,11 does not have that property between its middle columns and would invite invalid combinations. The first and last columns are also adjacent because 00 and 10 differ only in B.
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | m_0 | m_1 | m_3 | m_2 |
| 1 | m_4 | m_5 | m_7 | m_6 |
Write each output into its indexed cell; do not simply copy the truth-table output list left to right. For F=Σm(0,2,3,6,7), the map becomes:
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
Valid groups and the reason variables disappear
For an SOP, group cells containing 1, optionally using declared don’t-cares. A group is a rectangle with power-of-two side lengths, covering 1,2,4,8,… cells. It may wrap across an edge, but may not include a specified 0. Diagonal contact alone is not adjacency. Groups may overlap and every required 1 must be covered. A single-cell group is allowed if no larger useful group is possible.
Within a group, retain a variable if it is constant: write it uncomplemented when its value is 1, and complemented when its value is 0. Omit a variable that takes both values. For example m_0+m_2=A′B′C′+A′BC′=A′C′(B′+B)=A′C′. The two cells differ only in B, so B disappears. A valid group of 2^k cells in an n-variable map eliminates k literals.
The map is a structured way to apply that reduction, not permission to erase arbitrary literals. A group of three cells is not a single product term. A larger group removes more literals, but choosing locally large groups without checking complete coverage is not a proof of global optimality.
Worked example 1 with a wraparound pair
In the map for F, group {2,3,6,7}. It is the two rightmost columns across both rows. A and C vary, while B=1, so this group gives B.
Cell 0 remains uncovered. Pair {0,2} across the left/right boundary of the top row. A=0 and C=0 remain constant while B changes, so it gives A′C′. Thus F=B+A′C′. Overlap at cell 2 is permitted; ORing a term twice does not change its value.
Check both directions: B covers exactly rows 2,3,6,7; A′C′ covers exactly rows 0,2. Their union is the stated on-set, with no extra zero row. Under a two-level SOP cost model minimizing number of product terms and then literals, this cover is minimal: cell 0 can combine only with cell 2 among the 1s, requiring the prime term A′C′; the remaining 1s need another term, and B covers all of them with one literal. That is two terms and three literals. This proof is specific to this function and cost model.
Worked example 2 from zero groups to POS
For the same F, group zeros {1,5}: B=0 and C=1 are fixed. A sum term that is zero throughout that group is B+C′. Group zeros {4,5}: A=1 and B=0 are fixed, giving A′+B. The simplified POS is (B+C′)(A′+B), which equals B+A′C′ by the Boolean distributive identity (X+Y)(X+Z)=X+YZ.
For zero grouping, a fixed 0 variable appears uncomplemented in the sum term, and a fixed 1 variable appears complemented. This reversal is necessary because a sum term must be zero on the chosen group. Do not read zero groups with the one-group literal rule.
Don't-cares are permission, not obligations
A don’t-care cell marked X means the specification permits either output on that input. It does not mean an electrical unknown that must propagate, and it does not authorize ignoring any row you dislike. For SOP minimization you may use an X as 1 when it enlarges a useful group, or leave it unused. There is no requirement to cover every X.
Worked example 3: required ones {1,3}, don’t-cares {5,7}, required zeros {0,2,4,6}. A four-cell group {1,3,5,7} gives F=C. On required ones, C=1; on required zeros, C=0. The implementation happens to output 1 on both X rows, which is allowed. If either row 5 or 7 were a required zero instead, this grouping would be invalid. Verify only the required assignments, while documenting choices on don’t-cares.
Four-variable corners and a checking routine
For four variables use Gray order 00,01,11,10 on both axes, rows AB and columns CD. The four corner cells are 0,2,8,10. They form a valid wrapped rectangle: A and C vary while B=0,D=0, so their term is B′D′. They are not four isolated cells. Top/bottom edges are adjacent just as left/right edges are.
Key points: state the variable order; place values by index; distinguish on-set, off-set and don’t-cares; label every group by its cells; derive its constant literals; check the resulting expression on all required rows. Never group diagonally, include a required zero in an SOP group, demand disjoint groups, or confuse an equivalent expression with a proved hardware optimum.
Original practice
These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.
C01. For variable order A,B,C, which maxterm is zero only at row 101?
A. AB′C B. A+B′+C C. A′+B+C′ D. A′BC′
Answer: C
A is incorrect: this is minterm m_5, which is one, not zero, only at 101.
B is incorrect: this sum is zero at 010, not 101.
C is correct: at 101 all three literals A′,B,C′ are zero; any other row makes at least one literal one.
D is incorrect: this is a product term, not a maxterm.
C02. Which BC column order makes each neighboring pair, including the first and last columns, differ in one bit?
A. 00,01,10,11 B. 00,01,11,10 C. 00,11,01,10 D. 01,10,00,11
Answer: B
A is incorrect: 01 to 10 changes both bits.
B is correct: consecutive labels and the wraparound pair each differ in exactly one bit.
C is incorrect: 00 to 11 changes both bits.
D is incorrect: 01 to 10 changes both bits.
C03. In a three-variable map, what product term corresponds to the pair of cells {0,2}?
A. A′C′ B. A′B′ C. B′C′ D. AC′
Answer: A
A is correct: rows 000 and 010 fix A=0,C=0 while B changes.
B is incorrect: B is not constant; A′B′ instead covers rows 0 and 1.
C is incorrect: B is not constant and A is fixed; B′C′ covers 0 and 4.
D is incorrect: A=0 in both cells, so the literal must be A′.
C04. Which expression equals F(A,B,C)=Σm(0,2,3,6,7), with all other rows zero?
A. B+C′ B. A′+B C. B+AC′ D. B+A′C′
Answer: D
A is incorrect: it wrongly includes row 4=100, where C′=1 but F=0.
B is incorrect: it wrongly includes row 1=001, where A′=1 but F=0.
C is incorrect: it misses row 0 and wrongly includes row 4.
D is correct: B covers 2,3,6,7 and A′C′ adds 0,2, yielding exactly the specified set.
C05. Required ones are {1,3}, don’t-cares are {5,7}, and required zeros are {0,2,4,6}. Which statement is correct?
A. Every don’t-care must become zero. B. F=1 is valid because some rows are don’t-cares. C. F=C is valid because it satisfies every required row. D. F=B is valid because it covers row 3.
Answer: C
A is incorrect: don’t-cares may be assigned either output; zero is not compulsory.
B is incorrect: constant 1 violates all required zero rows.
C is correct: C is 1 on required rows 1,3 and 0 on 0,2,4,6; its choices at 5,7 are allowed.
D is incorrect: B misses required row 1 and includes required-zero rows 2 and 6.
C06. In a four-variable map with Gray-ordered AB rows and CD columns, which term covers exactly the four corners {0,2,8,10}?
A. A′C′ B. B′D′ C. BD D. A′B′C′D′
Answer: B
A is incorrect: A and C vary among these corners; they are not fixed zeros.
B is correct: B=0,D=0 are fixed, while A and C each take both values.
C is incorrect: B and D are both zero, so their literals must be complemented.
D is incorrect: this minterm covers only cell 0, not all four corners.
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