Chapter 09 of 32

K-Maps with Don't-Care Conditions

So far every row of a truth table had a definite output, 0 or 1. Real circuits are often more relaxed. A BCD digit uses 4 bits but only 10 of the 16 patterns (0000 to 1001) are legal; the patterns 1010 to 1111 simply never arrive. If an input combination can never happen, why should we care what the circuit outputs for it? We don't, and that freedom can make the circuit much smaller.

These "free" entries are called don't-care conditions. This chapter shows how to mark them on a K-map, how to use them to build bigger groups, and how to avoid the classic mistakes. It builds directly on Karnaugh Maps: the grouping rules, prime implicants and essential prime implicants are all the same, with one small extension.

A don't-care condition is an input combination for which the output value does not matter, either because that input never occurs or because the output is ignored when it does. It is written X, d or – and may be treated as 0 or 1, whichever gives a simpler circuit.

A function with don't-cares is called an incompletely specified function. Every simplification and minterm list in this chapter was verified in Python by checking the answer on all the "care" rows, and cross-checked with the SOPform and POSform functions of the SymPy library.


Where Do Don't-Cares Come From?

Source

Example

Don't-care rows

Unused input codes

A 4-bit BCD input only carries 0–9

10–15 (1010 to 1111)

Physically impossible combinations

Two sensors that can never both be on, such as "tank empty" and "tank full"

The row where both are 1

One-hot or restricted codes

3 one-hot signals: exactly one is 1

000, 011, 101, 110, 111

Unused states of a state machine

A counter with 6 states stored in 3 flip-flops

The 2 unused state codes

Ignored outputs

A display output while the display is blanked

All rows where the blank signal is active

The function is then written with two lists:

F(A, B, C, D) = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15)
                 └─ must be 1 ─┘     └──── may be 0 or 1 ────┘
All other rows (0, 1, 2, 3, 4) must be 0.

In POS notation the same function is ΠM(0, 1, 2, 3, 4) · d(10, 11, 12, 13, 14, 15). The don't-care list is identical in both forms; only the 1s and 0s swap.


The Rules for Using Don't-Cares

  1. Mark don't-care cells with X on the map.

  2. An X may be included in a group if it makes the group larger (or makes a needed group possible). Treat it as a 1 for that purpose.

  3. An X does not need to be covered. Leave it out if it does not help. Treat it as a 0 for that purpose.

  4. Never make a group that contains only X cells. It would add a term that covers no required 1.

  5. When finding essential prime implicants, look only at the real 1s. A PI is essential if it is the only PI covering some 1; covering an X uniquely does not count.

In terms of the definitions from Karnaugh Maps: prime implicants are formed from the 1s and the Xs together, but the covering step only has to cover the 1s.


Worked Examples

Example 1: A Warm-Up with Three Variables

F(A, B, C) = Σm(1, 3, 5) + d(7).

          BC=00  BC=01  BC=11  BC=10
A=0   |   0   |   1   |   1   |   0   |
A=1   |   0   |   1   |   X   |   0   |

Without the X:  pairs (m1, m3) → A′C  and (m1, m5) → B′C
                F = A′C + B′C                    (2 terms, 4 literals)
With X = 1:     quad m1, m3, m5, m7 → C
                F = C                            (1 literal)

One don't-care turned two gates into a plain wire.

Example 2: Two Different Minimal Answers

F(A, B, C, D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

           CD=00  CD=01  CD=11  CD=10
AB=00   |   X   |   1   |   1   |   X   |
AB=01   |   0   |   X   |   1   |   0   |
AB=11   |   0   |   0   |   1   |   0   |
AB=10   |   0   |   0   |   1   |   0   |

Column CD = 11 (m3, m7, m15, m11)       → CD       essential (only PI for m11, m15)
m1 is still uncovered. Two prime implicants contain it:
   A′B′ = m0, m1, m2, m3  (uses X at 0 and 2)
   A′D  = m1, m3, m5, m7  (uses X at 5)

F = CD + A′B′      or      F = CD + A′D

Both answers have 2 terms and 4 literals, so both are minimal. Without the don't-cares, the best is CD + A′B′D (5 literals). Notice something important: the two answers are different functions. CD + A′B′ outputs 1 for rows 0 and 2 and 0 for row 5; CD + A′D does the opposite. Both are correct, because they agree on every row we care about.

Example 3: BCD Digit Greater Than or Equal to 5

A circuit receives a BCD digit ABCD (A is the MSB) and outputs 1 when the digit is 5 or more. This kind of signal is used, for example, in rounding logic.

F(A, B, C, D) = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15)

           CD=00  CD=01  CD=11  CD=10
AB=00   |   0   |   0   |   0   |   0   |
AB=01   |   0   |   1   |   1   |   1   |
AB=11   |   X   |   X   |   X   |   X   |
AB=10   |   1   |   1   |   X   |   X   |

Group 1 (8 cells): rows AB = 11 and 10 → m8 to m15           → A
Group 2 (4 cells): m5, m7, m13, m15 → B = 1, D = 1            → BD
Group 3 (4 cells): m6, m7, m14, m15 → B = 1, C = 1            → BC

F = A + BD + BC

Compare the two results:

Version

Minimal SOP

Terms

Literals

Don't-cares treated as 0

A′BD + A′BC + AB′C′

3

9

Don't-cares used

A + BD + BC

3

5

The single-literal term A works because every legal digit with A = 1 is 8 or 9, both of which are ≥ 5. The don't-cares let the map "know" that fact.

Example 4: Segment a of a Seven-Segment Display

A 7-segment display shows digits using segments a (top) to g (middle). Segment a is lit for every digit except 1 and 4. With a BCD input:

a(A, B, C, D) = Σm(0, 2, 3, 5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15)

           CD=00  CD=01  CD=11  CD=10
AB=00   |   1   |   0   |   1   |   1   |
AB=01   |   0   |   1   |   1   |   1   |
AB=11   |   X   |   X   |   X   |   X   |
AB=10   |   1   |   1   |   X   |   X   |

A      = rows 11 and 10 (m8 to m15)                      8 cells
C      = columns 11 and 10 (m2, m3, m6, m7, m10, m11, m14, m15)   8 cells
BD     = m5, m7, m13, m15                                4 cells
B′D′   = four corners m0, m2, m8, m10                    4 cells

a = A + C + BD + B′D′

All four are essential (m9 needs A, m3 needs C, m5 needs BD, m0 needs B′D′). Without don't-cares, the best answer has 4 terms and 11 literals, for example A′C + A′BD + AB′C′ + B′C′D′. With them, 6 literals. Notice that B′D′ + BD is the XNOR of B and D, so the circuit can be even cheaper with an XNOR gate: a = A + C + (B ⊕ D)′. The full seven-segment decoder is designed in Code Converters.

Example 5: POS with Don't-Cares

For POS, group the 0s together with any helpful Xs. Take the BCD ≥ 5 function again; its 0s are rows 0 to 4.

           CD=00  CD=01  CD=11  CD=10
AB=00   |   0   |   0   |   0   |   0   |
AB=01   |   0   |   1   |   1   |   1   |
AB=11   |   X   |   X   |   X   |   X   |
AB=10   |   1   |   1   |   X   |   X   |

Group of 0s: row AB = 00 (m0 to m3)     → F′ term A′B′
m4 is still uncovered. Two choices of the same size:
   m0, m4      → A′C′D′
   m4, m12     → BC′D′   (uses X at 12)

F′ = A′B′ + A′C′D′    →    F = (A + B)(A + C + D)
F′ = A′B′ + BC′D′     →    F = (A + B)(B′ + C + D)

Each POS has 5 literals, the same as the SOP A + BD + BC. Look at what happens to the don't-cares. The first POS uses no X at all, and since both factors contain A, it outputs 1 on rows 10 to 15, exactly like the SOP. The second POS groups X12 with the 0s, so that circuit outputs 0 for the input 1100, while the SOP outputs 1 there. Both are correct, as Example 2 showed, because they agree on every legal BCD digit.


Letting Software Do It

The SymPy library has functions that minimise SOP and POS forms and accept a don't-care list. This program reproduces Examples 3, 4 and 5 (SymPy 1.14):

from sympy import symbols
from sympy.logic.boolalg import SOPform, POSform

A, B, C, D = symbols("A B C D")
dc = list(range(10, 16))          # BCD inputs 1010..1111 never occur

# BCD digit >= 5
ones = [5, 6, 7, 8, 9]
print("Without don't-cares:", SOPform([A, B, C, D], ones))
print("With don't-cares   :", SOPform([A, B, C, D], ones, dc))
print("POS with don't-cares:", POSform([A, B, C, D], ones, dc))

# Segment 'a' of a 7-segment display (off only for digits 1 and 4)
seg_a = [0, 2, 3, 5, 6, 7, 8, 9]
print("Segment a:", SOPform([A, B, C, D], seg_a, dc))

Output:

Without don't-cares: (B & C & ~A) | (B & D & ~A) | (A & ~B & ~C)
With don't-cares   : A | (B & C) | (B & D)
POS with don't-cares: (A | B) & (A | C | D)
Segment a: A | C | (B & D) | (~B & ~D)

In SymPy, & is AND, | is OR and ~ is NOT, so the results match our hand answers exactly. Internally, SOPform merges terms that differ in one variable, the same idea that drives the Quine-McCluskey method in the next chapter.


A Word of Caution: Don't-Cares Become Real Values

Once a circuit is built, there are no Xs any more: every input produces some definite output. The value an X ends up with depends on the groups you chose. In Example 3, the circuit A + BD + BC outputs 1 for the illegal inputs 1010 to 1111.

Usually that is harmless, because those inputs never occur. But ask "never?" carefully:

  • During power-up, noise, or a fault, an "impossible" input can appear.

  • In a state machine, if the flip-flops land in an unused state, the don't-care choices decide the next state. A careless choice can trap the machine in unused states forever (a problem called lock-out, discussed with counters later in this tutorial).

  • For safety-critical outputs (a motor enable, a door unlock), designers often refuse to use don't-cares and force a safe value instead.

So: use don't-cares to save gates, but always know what value each X finally received.


Comparison: With and Without Don't-Cares

Function

Minimal SOP without don't-cares

Minimal SOP with don't-cares

Literals saved

Σm(1, 3, 5) + d(7)

A′C + B′C

C

3

Σm(1, 3, 7, 11, 15) + d(0, 2, 5)

CD + A′B′D

CD + A′B′ (or CD + A′D)

1

BCD ≥ 5

A′BD + A′BC + AB′C′

A + BD + BC

4

Segment a

A′C + A′BD + AB′C′ + B′C′D′

A + C + BD + B′D′

5

BCD digit is even

A′D′ + B′C′D′

D′

4


Common Mistakes

  • Covering every X. Don't-cares are optional. Including one that does not enlarge a group adds nothing; adding a separate group just for an X adds a useless term.

  • Groups made only of Xs. Such a group covers no required 1 and only increases cost.

  • Calling a PI essential because it is the only one covering an X. Essentiality is judged on real 1s only.

  • Forgetting the Xs in POS. Don't-cares help when grouping 0s too.

  • Expecting the SOP and POS answers to be the same function. They can assign different values to the X rows; both are correct.

  • Treating real 0s as don't-cares. Only rows that truly never occur (or are truly ignored) may be marked X. Getting this wrong produces a circuit that fails on a valid input.


Interview and GATE-Style Questions

Q1. Minimise F(A, B, C, D) = Σm(0, 2, 5, 8, 10, 13) + d(7, 15).

The four corners (0, 2, 8, 10) give B′D′. Cells 5, 7, 13, 15 form a quad using both don't-cares, giving BD. F = B′D′ + BD, which is the XNOR (B ⊕ D)′.

Q2. A BCD input ABCD should output 1 when the digit is prime (2, 3, 5, 7). Find the minimal SOP.

F = Σm(2, 3, 5, 7) + d(10–15). The quad 2, 3, 10, 11 gives B′C and the quad 5, 7, 13, 15 gives BD. F = B′C + BD. Without don't-cares it would be A′B′C + A′BD.

Q3. How many don't-care conditions does a 4-bit BCD input have?

Six: the codes 1010 to 1111 (decimal 10 to 15).

Q4. Can a minimal SOP and a minimal POS of the same incompletely specified function be logically different?

Yes. They only have to agree on the specified rows. For Σm(1, 3, 7, 11, 15) + d(0, 2, 5), the SOP CD + A′B′ gives 1 at rows 0 and 2, while the POS D(A′ + C) gives 0 there and 1 at row 5.

Q5. For a BCD input, find a minimal expression that is 1 for even digits.

Even digits 0, 2, 4, 6, 8 all have D = 0, and the odd ones have D = 1. With don't-cares 10–15, the eight cells with D = 0 form one group: F = D′.

Q6. Why is it wrong to circle a group that contains only don't-care cells?

The purpose of grouping is to cover the required 1s. A group of only Xs covers none, so it adds a gate without being needed.


Summary

  • A don't-care (X or d) is an input row whose output does not matter, usually because it never occurs. The function is written Σm(…) + d(…).

  • On a K-map, include an X in a group when it helps make the group larger; otherwise ignore it. Never group only Xs.

  • Prime implicants are formed from 1s and Xs together; essential PIs and the cover are decided by the 1s alone.

  • Don't-cares can save a lot: BCD ≥ 5 drops from 9 literals to 5, and the BCD even detector collapses to D′.

  • Different minimal answers may assign different values to the X rows. In the final circuit every X becomes a real 0 or 1, so check that this is safe.

  • For many variables, or to find every minimal cover systematically, use the tabular Quine-McCluskey Method, which handles don't-cares the same way.