Karnaugh maps

ACompressed recap

🧾

K-map: Gray order, wrap-around edges and corners; groups of 2ᵏ 1s drop k variables; read the constant variables. PI = maximal group; EPI = sole cover of some 1; minimal SOP = EPIs + fewest extra PIs (no redundant big groups). POS: group the 0s, literal primed where the variable is 1. Don't-cares are optional 1s; 5 variables = two 4-variable maps.

BMerged rule card

4.1.1 Karnaugh maps for 2, 3 and 4 variables: adjacency and grouping

• K-map rows and columns in Gray order (00, 01, 11, 10); adjacent cells differ in one variable; edges and corners wrap.
• Groups: rectangles of 2ᵏ cells containing only 1s; a 2ᵏ group drops k variables.
• Term of a group: the variables that stay constant (1 → plain, 0 → primed).
• Minimise: largest possible groups, fewest groups, every 1 covered; overlaps allowed.

4.1.2 Prime implicants, essential prime implicants, minimal SOP and POS

• Implicant ⊂ prime implicant (maximal group) ⊂ essential PI (sole cover of some 1).
• Minimal SOP: all EPIs + fewest extra PIs for the remaining 1s; only PIs are used.
• Redundant PIs (like a centre square fully covered by EPIs) are left out. Cyclic functions have no EPIs and several minimal answers.
• POS: group 0s; clause literal plain if the variable is 0 in the group, primed if 1.

4.1.3 Don't-care conditions and 5-variable maps

• Don't-cares (d or X): may be used as 1s to enlarge groups; need not be covered; never group only Xs.
• PIs computed with Xs as 1s; essentiality judged on the real 1s.
• 5-variable map: two 4-variable maps (A = 0, A = 1); same position in both halves is adjacent; a group in both halves drops A.

CInterleaved GATE-style questions

Q1MCQ1 markReading

In a 4-variable K-map, the group of cells 4, 5, 6, 7 (row AB = 01) is:

• (A) A'B
• (B) A'B'
• (C) B
• (D) AB'

Q2NAT1 markGroup size

A group in a 4-variable K-map has the term A'D. How many cells does it cover?

Numerical answer: ________

Q3MCQ2 marksMinimise

F(A, B, C, D) = Σm(0, 1, 2, 3, 4, 6, 8, 9, 10, 11). The minimal SOP is:

• (A) B'C' + A'D'
• (B) A'B' + B'D'
• (C) B' + A'D'
• (D) B' + D'

Q4NAT2 marksEPIs

F(A, B, C, D) = Σm(0, 4, 5, 7, 8, 9, 13, 15). How many essential prime implicants does it have?

Numerical answer: ________

Q5NAT2 marksPIs

F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). How many prime implicants?

Numerical answer: ________

Q6MCQ1 markPOS literal

A group of 0s in a 3-variable map covers cells 6 and 7 (A = 1, B = 1, C changes). The POS clause is:

• (A) AB
• (B) (A' + B')
• (C) (A + B)
• (D) (A' + B)

Q7NAT1 markDon't-care

F(A, B, C) = Σm(1, 3) + d(5, 7). How many literals in the minimal SOP?

Numerical answer: ________

Q8MCQ1 markFive variables

In a 5-variable map made of two halves (A = 0 and A = 1), cell 9 is adjacent to:

• (A) cell 10
• (B) cell 18
• (C) cell 25
• (D) cell 31

DAnswer Vault