Exercises — Don't-care conditions in K-maps

A 4-bit number runs $0$ to $15$. BCD only uses $0$–$9$. The combinations $1010,1011,1100,1101,1110,1111$ — that is $m_{10},m_{11},m_{12},m_{13},m_{14},m_{15}$ — are never produced by a valid BCD source, so their outputs are unspecified. Don't-cares: $10,11,12,13,14,15$ (six of them). See BCD - Binary Coded Decimal.

False. The rule "every 1 must be covered" applies only to real 1s. A don't-care is optional — you cover it only if doing so enlarges a group that already covers a real 1. Covering an $X$ for its own sake would add a wasted term (breaks Rule 2).

Build the map (rows $A$, cols $BC$ in Gray order $00,01,11,10$):

The 1s are at $BC=01$ and $BC=11$; the $X$ is at $A=1,BC=01$. All four cells in columns $BC=01$ and $BC=11$ have $C=1$. They are $\{m_1,m_3,m_5,m_7\}$. Read $m_5$ as 1 and we get one size-4 group covering all $C=1$ cells → this group cancels $A$ and $B$, leaving just $C$. $\boxed{F=C}$ — 1 literal. (Look at the green box in

The only real 1s are $m_0=000$ and $m_2=010$; everything else is $X$.

We only need to cover $m_0$ and $m_2$. The cheapest cover: absorb enough $X$'s to make a group of $A=0$? No — the whole map has $m_0,m_2$ as 1s and $X$ elsewhere. The biggest legal group that covers a real 1 and drops the most variables is all 8 cells ($1=$ everything). That group is the constant $F=1$. $\boxed{F=1}$ — 0 literals (a constant HIGH wire). Note we did not build any group of only-$X$'s: the size-8 group contains the real 1s $m_0,m_2$, so Rule 2 is satisfied.

Map (rows $AB$, cols $CD$ in Gray order):

Group A (green): every cell with $A=1$ is the bottom half — rows $AB=11$ and $AB=10$ = cells $\{8,9,10,11,12,13,14,15\}$. The 1s $m_8,m_9$ are real; the rest are $X$. Reading those $X$'s as 1 makes an 8-cell group covering all of $A=1$ → simplifies to just $\mathbf{A}$. Group B (yellow): cells with $B=1,C=1$ are $\{6,7,14,15\}$ ($m_6,m_7$ real, $m_{14},m_{15}$ are $X$) → size-4 → $\mathbf{BC}$. Group C (red): cells with $B=1,D=1$ are $\{5,7,13,15\}$ ($m_5,m_7$ real, $m_{13},m_{15}$ are $X$) → size-4 → $\mathbf{BD}$. All real 1s ($5,6,7,8,9$) are now covered: $\boxed{F=A+BC+BD}$ Check: digit $9=1001$: $A=1\Rightarrow F=1$ ✅ ($9\ge 5$). Digit $4=0100$: $A=0,BC=0,BD=0\Rightarrow F=0$ ✅ ($4<5$). See

$G=1$ at $m_2,m_3,m_5,m_7$. Map:

• $\{2,3\}$: $A=0,B=0,C=1$ → $\bar{A}\bar{B}C$. Can we grow it? Neighbours $m_{10},m_{11}$ are $X$, giving $\{2,3,10,11\}$ = $B=0,C=1$ → $\bar{B}C$ (drops $A$). ✅ Absorb them.
• $\{5,7\}$: $A=0,B=1,D=1$ → $\bar{A}BD$. Grow with $X$'s $m_{13},m_{15}$ → $\{5,7,13,15\}$ = $B=1,D=1$ → $BD$ (drops $A$). ✅
• $\{3,7\}$: $A=0,C=1,D=1$ → $\bar{A}CD$. Grow with $X$'s $m_{11},m_{15}$ → $\{3,7,11,15\}$ = $C=1,D=1$ → $CD$. This covers $m_3$ and $m_7$ again but as a cheaper 2-literal term — however $m_3$ is already in $\bar{B}C$ and $m_7$ in $BD$, so $CD$ is not needed.

Minimal cover using only the two size-4 groups that each catch a unique real 1: $\boxed{G=\bar{B}C+BD}$ Check: $m_2=0010$: $\bar{B}C=1\cdot 1=1$ ✅. $m_5=0101$: $BD=1\cdot 1=1$ ✅. $m_4=0100$: $\bar{B}C=0$, $BD=1\cdot 0=0\Rightarrow G=0$ ✅ (4 not prime). $m_0=0000\Rightarrow 0$ ✅.

$F=0$ only at $m_1$ and $m_4$; $F=1$ at $\{0,2,3,5,6,7,8,9\}$; $X$ at $10$–$15$.

Cover the 1s cheaply, absorbing $X$'s:

• $A=1$ block $\{8,9,10,11,12,13,14,15\}$ (reads $m_{10}$–$m_{15}$ as 1) → term $\mathbf{A}$. Covers $m_8,m_9$.
• $C=1$ block — cells with $C=1$ are columns $CD=11,10$: $\{2,3,6,7,10,11,14,15\}$, all 1 or $X$ → 8-cell group → term $\mathbf{C}$. Covers $m_2,m_3,m_6,m_7$.
• $BD$ block $\{5,7,13,15\}$ (reads $m_{13},m_{15}$ as 1) → $\mathbf{BD}$. Covers $m_5$ (and $m_7$ again).
• Remaining uncovered 1: $m_0=0000$. Its live neighbours: $m_8$ (in $A$ already), $m_2$ (in $C$), $m_1$ is a 0 (cannot join). So pair $\{0,2\}$ = $\bar{A}\bar{B}\bar{D}$? Let's grow: $\{0,2,8,10\}$ = $B=0,D=0$ → $\bar{\mathbf{B}}\bar{\mathbf{D}}$ ($m_8$ real, $m_{10}$ is $X$). This covers $m_0$. ✅

$\boxed{F=A+C+BD+\bar{B}\bar{D}}$ Check the two zeros: $m_1=0001$: $A=0,C=0,BD=0\cdot 1=0,\bar{B}\bar{D}=1\cdot 0=0\Rightarrow F=0$ ✅. $m_4=0100$: $A=0,C=0,BD=1\cdot 0=0,\bar{B}\bar{D}=0\cdot 1=0\Rightarrow F=0$ ✅. And e.g. $m_0=0000$: $\bar{B}\bar{D}=1\Rightarrow F=1$ ✅.

Map:

Real 1s: $1,3,7,11,15$.

• Column $CD=11$ ($m_3,m_7,m_{15},m_{11}$) — all four are real 1s → size-4 group with $C=1,D=1$ → term $\mathbf{C}\mathbf{D}$. Covers $3,7,11,15$.
• Remaining 1: $m_1=0001$. Neighbours: $m_0$ ($X$), $m_3$ (already covered), $m_5$ ($X$), $m_9$ (0). Grow $\{1,3,0,2\}$ = $A=0,B=0$ → $\bar{A}\bar{B}$ (reads $m_0,m_2$ as 1) — but that is a size-4 group covering $m_1,m_3$ (real) plus 2 $X$'s → term $\bar{\mathbf{A}}\bar{\mathbf{B}}$, 2 literals. Alternatively $\{1,3,5,7\}$ = $A=0,D=1$ → $\bar{A}D$, also 2 literals, covers $m_1,m_3,m_7$ ($m_5$ is $X$). Both are 2-literal.

Pick $\bar{A}D$ (it also re-covers $m_7$, harmless) or $\bar{A}\bar{B}$; both give a 2-literal second term: $\boxed{F=CD+\bar{A}D}\text{(equally: }F=CD+\bar{A}\bar{B}\text{)}$ Why no cheaper cover exists: $m_1$ is a real 1 whose entire neighbourhood of 1s/$X$'s is confined to the $A=0$ region — there is no size-8 group through it (all $A=1$ neighbours are forced 0s). So $m_1$ needs at least a 2-literal term. And $CD$ is the unique 4-cell group covering $m_{11},m_{15}$ (both surrounded by 0s except along $CD=11$), so $CD$ is essential. Two essential terms of 2 literals each ⇒ 4 literals is the floor. Check: $m_{11}=1011$: $CD=1\cdot 1=1$ ✅. $m_1=0001$: $\bar{A}D=1\cdot 1=1$ ✅. $m_9=1001$: $CD=0\cdot 1=0,\bar{A}D=0\cdot 1=0\Rightarrow 0$ ✅ ($m_9$ is a genuine 0). $m_5=0101$ is $X$: $\bar{A}D=1\Rightarrow$ we read it as 1 — allowed, it's a don't-care.

Neither is wrong. In 5.1 we saw $F=CD+\bar{A}D$ and $F=CD+\bar{A}\bar{B}$ are both valid minimal SOPs (both 4 literals). This happens because a don't-care ($m_5$, $m_0$, $m_2$) can be assigned differently in each solution — one engineer read $m_5=1$ (so $\bar{A}D$ works), the other read $m_5=0$ but $m_0,m_2=1$ (so $\bar{A}\bar{B}$ works). Both satisfy every specified output; they only disagree on inputs that never occur / nobody cares about. Minimal SOP is not always unique — see Quine-McCluskey Method for how the algorithm enumerates all minimal covers, and Boolean Simplification for the algebra behind why they're equivalent on the care set.

Which exercise gave $F=C$? ::: Exercise 2.1 BCD "$\ge 5$" minimal SOP? ::: $F=A+BC+BD$ (Exercise 3.1) BCD "prime digit" minimal SOP? ::: $G=\bar{B}C+BD$ (Exercise 3.2) Can two different SOPs both be minimal on a don't-care map? ::: Yes — $X$'s create ties (Exercise 5.2).