Karnaugh Maps for Simplifying Expressions

1) Why are K-maps arranged in Gray code order?

To make the map symmetrical

To ensure adjacent cells differ by only one variable

To reduce the number of rows

To match decimal ordering

Gray code ordering makes adjacent cells differ in exactly one bit, enabling valid grouping.

Explanation

Gray code ordering makes adjacent cells differ in exactly one bit, enabling valid grouping.

2) For a 2-variable function F(A,B) with minterms m(1,3), the minimal SOP is:

AAA

BBB

A‾\overline{A}A

B‾\overline{B}B

m(1,3)m(1,3)m(1,3) are cells where B=1B=1B=1 (A changes). One group of 2 → F=BF=BF=B.

Explanation

m(1,3)m(1,3)m(1,3) are cells where B=1B=1B=1 (A changes). One group of 2 → F=BF=BF=B.

3) In a 3-variable K-map, which pair of cells is NOT adjacent?

000 and 001

011 and 111

010 and 110

100 and 011

Adjacency means one bit differs. 100 vs 011 differs in all three bits → not adjacent.

Explanation

Adjacency means one bit differs. 100 vs 011 differs in all three bits → not adjacent.

4) F(A,B,C)=Σm(1,3,5,7)F(A,B,C)=\Sigma m(1,3,5,7)F(A,B,C)=Σm(1,3,5,7). Minimal SOP is:

A+CA + CA+C

B+CB + CB+C

A+BA + BA+B

A′+B′A' + B'A′+B′

Ones at all odd indices (where A=1A=1A=1 or C=1C=1C=1 across groupings). K-map groups give F=A+CF=A + CF=A+C.

Explanation

Ones at all odd indices (where A=1A=1A=1 or C=1C=1C=1 across groupings). K-map groups give F=A+CF=A + CF=A+C.

5) A group of 8 on a 4-variable K-map collapses to a single literal.

True

False

Each doubling in group size removes one variable. Group of 8 removes 3 variables → one literal remains.

Explanation

Each doubling in group size removes one variable. Group of 8 removes 3 variables → one literal remains.

6) Why include don’t-care cells (X) in groups?

They must be 0

They are ignored

They can be treated as 1 to form larger groups

They are errors

Treat X as 1 only if it helps make a bigger power-of-two group, yielding simpler expressions.

Explanation

Treat X as 1 only if it helps make a bigger power-of-two group, yielding simpler expressions.

7) Which statement is correct about wrap-around adjacency?

Only corners wrap

Only top and bottom rows wrap

Edges wrap horizontally and vertically

Wrap not allowed

K-maps are toroidal: top–bottom and left–right edges wrap.

Explanation

K-maps are toroidal: top–bottom and left–right edges wrap.

8) F(A,B,C)=Σm(0,2,3,6,7)F(A,B,C)=\Sigma m(0,2,3,6,7)F(A,B,C)=Σm(0,2,3,6,7). Minimal SOP is:

A′B′+ACA'B' + ACA′B′+AC

A′B′+AC′A'B' + A C'A′B′+AC′

B′C′+ACB'C' + ACB′C′+AC

A′C′+BCA' C' + B CA′C′+BC

K-map grouping: a 2-cell group for A′B′A'B'A′B′ (00x) and a 4-cell group for ACACAC (1x1).

Explanation

K-map grouping: a 2-cell group for A′B′A'B'A′B′ (00x) and a 4-cell group for ACACAC (1x1).

9) A prime implicant is:

Any single minterm

A group that can’t be combined into a larger valid group

A group covering only one 1

Any product with all variables

Prime implicants are maximal groups (powers of two) that can’t be expanded further while remaining valid.

Explanation

Prime implicants are maximal groups (powers of two) that can’t be expanded further while remaining valid.

10) An essential prime implicant is one that:

Minimizes literal count

Covers at least one 1 not covered by others

Has the largest size

Has fewest variables

If a minterm is covered by only one PI, that PI is essential.

Explanation

If a minterm is covered by only one PI, that PI is essential.

11) If a function has many 1’s, which form often simplifies more directly from a K-map?

SOP

POS

Both same

Neither

With many 1’s, it’s often easier to group 0’s to get a simpler POS (sum of maxterms).

Explanation

With many 1’s, it’s often easier to group 0’s to get a simpler POS (sum of maxterms).

12) F(A,B)=Σm(0,1)F(A,B)=\Sigma m(0,1)F(A,B)=Σm(0,1). Minimal SOP is:

A‾\overline{A}A

B‾\overline{B}B

AAA

BBB

Minterms 0 and 1 share A=0A=0A=0 → F=A‾F=\overline{A}F=A.

Explanation

Minterms 0 and 1 share A=0A=0A=0 → F=A‾F=\overline{A}F=A.

13) F(A,B,C)=Σm(1,3,7)F(A,B,C)=\Sigma m(1,3,7)F(A,B,C)=Σm(1,3,7), d={5}d=\{5\}d={5}. Minimal SOP:

A′C+ACA'C + ACA′C+AC

BCB CBC

CCC

A′B+ACA'B + ACA′B+AC

Using don’t-care at 5 lets you make a 4-group where C=1C=1C=1 → F=CF=CF=C.

Explanation

Using don’t-care at 5 lets you make a 4-group where C=1C=1C=1 → F=CF=CF=C.

14) Every optimal grouping in a K-map is unique.

True

False

There can be multiple minimal solutions with the same cost (different but equivalent groupings).

Explanation

There can be multiple minimal solutions with the same cost (different but equivalent groupings).

15) A student groups four 1’s that are not adjacent powers of 2. What’s wrong?

Groups must be horizontal only

Groups must be vertical only

Groups must be powers of 2 and adjacent

Groups must include all 1’s

Valid groups are 1,2,4,8,… and each cell in the group must be mutually adjacent via Gray adjacency.

Explanation

Valid groups are 1,2,4,8,… and each cell in the group must be mutually adjacent via Gray adjacency.