4.3 Implicants, Prime Implicants & Don't Care Conditions

Back to Digital Logic Notes

📚Module 04: Simplification of Boolean Expressions & K-MapsTopic 4.3⏱️16 min read

🎯High-Yield For:University Semester Exams • Hardware Engineering Rounds • Foundational Computing

💡 Core Intuition: The Bus Route Network & Optional Stops

To establish public transportation across a metropolitan region, an urban transit authority must design bus routes servicing passenger stops:

🍳 The Everyday Analogy: Routes, Hubs, and Abandoned Stations

• Bus Stops (Minterms): Every neighborhood where citizens live and need transit represents a minterm that must be picked up by at least one bus route.
• Bus Routes (Implicants): Any valid bus path covering 1, 2, 4, or 8 stops is an implicant.
• Prime Bus Routes (Prime Implicants - PI): A bus route that is expanded to its maximal possible capacity. If a route can be stretched from 2 stops to 4 stops, the transit authority will not run the smaller 2-stop route; they run the Prime Route.
• The Exclusive Neighborhood (Essential Prime Implicant - EPI): Imagine a remote suburb that can only be physically reached by Route 12. Even if Route 12 overlaps with other buses downtown, Route 12 is Essential—it cannot be eliminated from the schedule without leaving that suburb completely stranded.
• Abandoned Industrial Park (Don't Care Condition $d$): A station where zero passengers reside. The city does not require buses to stop there. However, if running a bus through the empty park allows Route 7 to merge with Route 9 into a single high-speed express line, the transit authority gladly takes advantage of the empty station!

💻 Bridging to Computer Science

In switching theory and logic synthesis:

1. An Implicant is any valid product term covering one or more 1s of a function.
2. A Prime Implicant (PI) is a maximal subcube that cannot be combined with any other adjacent cells to form a larger group.
3. An Essential Prime Implicant (EPI) is a prime implicant containing at least one unique minterm covered by no other prime implicant. Every EPI must appear in every minimal Sum-of-Products (SOP) expression!
4. Don't Care Conditions ($d$ or $X$) represent input states that are either physically impossible or whose outputs have no impact on circuit operation. Engineers treat them as 1s whenever they help enlarge a prime implicant, but ignore them otherwise.

---

📑Table of Contents

• 🗂️ The Implicant Taxonomy: Definitions & Theoretical Criteria
• 🔍 The Unique Minterm Test: How to Detect an Essential Prime Implicant
• ❓ Don't Care Conditions (d): Physical Origins & Optimization Rules
  • Physical Engineering Origins of Don't Cares
• 🔀 Minimal vs. Irredundant Expressions: Multi-Solution Graphs
• 🏭 Real-World Production Context: BCD-to-7-Segment Display Decoders
  • The Dramatic Impact of Don't Cares:
• 📐 Numerical Applications & Worked Examples
  • Example 1: Finding PIs, EPIs, and Minimal SOP on a 3-Variable K-Map
  • Example 2: 4-Variable K-Map with Don't Care Optimization
  • Example 3: Minimal Irredundant Cover vs. Non-Minimal Cover
• 🎯 Exam & Interview Pitfall Check

---

🗂️ The Implicant Taxonomy: Definitions & Theoretical Criteria

📦

Implicant

Valid Subcube

• Any product term that, when evaluated as 1, forces the entire function F to be 1.
• Geometrically represents any valid subcube of 1, 2, 4, 8, or 16 adjacent 1s.
• Every single minterm is itself a 1-cell implicant.

Key Abstractions / Calls

P ⇒ F

⭐

Prime Implicant (PI)

Maximal Group

• An implicant that cannot be combined with any other group to eliminate a literal.
• It is NOT a subset of any larger valid subcube on the K-map.
• Every term in a minimal SOP expression is GUARANTEED to be a Prime Implicant.

Key Abstractions / Calls

Maximal Subcube

👑

Essential Prime Implicant

Mandatory Cover

• A Prime Implicant that contains at least ONE unique minterm covered by NO other PI.
• Cannot be omitted from the circuit under any circumstances.
• Must be included in ALL minimal SOP expressions.

Key Abstractions / Calls

Unique 1 Covered

✂️

Redundant Prime Implicant

Superfluous Term

• A Prime Implicant whose constituent minterms are already completely covered by EPIs.
• Adding it adds silicon cost without covering any new truth table rows.
• Always pruned from minimal expressions.

Key Abstractions / Calls

Fully Covered

---

🔍 The Unique Minterm Test: How to Detect an Essential Prime Implicant

📖Definition 4.2: Essential Prime Implicant (EPI)definition

Let $P$ be a prime implicant of Boolean function $F$. $P$ is an Essential Prime Implicant if and only if there exists at least one minterm $m_k \in P$ such that:

$$m_k \notin Q \quad \text{for all other prime implicants } Q \ne P$$

The minterm $m_k$ is termed the distinguished (or unique) minterm of $P$.

📐Theorem 4.3: Necessity of Essential Prime Implicantstheorem

If $P$ is an essential prime implicant of $F$, then $P$ must be present in every minimal Sum-of-Products (SOP) expression of $F$:

$$P \in \text{Minimal SOP}(F)$$

Prime Implicant (PI) vs. Essential Prime Implicant (EPI)

Contrasting maximal potential subcubes with mathematically mandatory circuit terms

Prime Implicant (PI)

Candidate Subcube

📦

Dominant Architecture / DomainStructural Maximality

• •Represents the largest possible grouping for a cluster of 1s.
• •May or may not be needed in the final circuit.
• •A function may have many PIs (e.g., 6 PIs), but only 2 might be needed for minimal cover.
• •Determined purely by geometric adjacency.

"It cannot grow any larger, but it might be completely dispensable."

Essential Prime Implicant (EPI)

Mandatory Circuit Gate

👑

Dominant Architecture / DomainUniqueness Requirement

• •Contains a distinguished minterm that has NO OTHER viable grouping options.
• •Guaranteed to be physically implemented as an AND gate in silicon.
• •If you remove an EPI, at least one truth table row will fail to output 1.
• •Forms the foundational core of every minimal realization.

"It owns at least one unique 1 that no other group can cover."

---

❓ Don't Care Conditions ($d$): Physical Origins & Optimization Rules

In real-world digital engineering, truth table rows fall into three categories: output must be 1, output must be 0, or the output does not matter.

📖Definition 4.3: Don't Care Conditiondefinition

A Don't Care Condition, denoted as $d(x_1, \dots, x_n)$ or $\phi$ or $X$, represents an input combination for which:

1. The input combination is physically impossible to occur in the system, or
2. The circuit output for that combination has no operational effect on downstream components.

$$F(x_1, \dots, x_n) = \sum m(\text{minterms}) + \sum d(\text{don't-cares})$$

Physical Engineering Origins of Don't Cares

1. Binary Coded Decimal (BCD) Encoders: A BCD digit encodes decimal numbers $0$ through $9$ using 4 bits: 0000 to 1001. The remaining six 4-bit combinations (1010 through 1111, representing decimal 10 to 15) can never be generated by a decimal keyboard or ADC. Therefore, combinations $10, 11, 12, 13, 14, 15$ are treated as don't cares.
2. One-Hot Encoded State Machines: In high-speed ASIC control paths where exactly one flip-flop is asserted at any instant (e.g. states 001, 010, 100), states with multiple 1s (like 111 or 011) are physically unreachable.

Architecture Flow

The Don't-Care Optimization Decision Tree

Golden rules for leveraging don't-care conditions during K-map minimization

🔍Rule 1

Inspect Neighbors

Treat 'd' cells as 1s ONLY if they enlarge a group of real 1s (e.g. Pair → Quad).

→

Enlarge Group

✂️Rule 2

Eliminate Literals

Enlarging a group from 2 to 4 cells eliminates 1 extra variable, halving gate input count.

→

Check Remaining

🚫Rule 3

Ignore Leftovers

Any 'd' cell that does not help enlarge a group of real 1s is assigned 0 and IGNORED.

→

Never Circle

⚠️Rule 4

No All-d Groups

STRICT PROHIBITION: Never create a group consisting exclusively of don't-cares!

---

🔀 Minimal vs. Irredundant Expressions: Multi-Solution Graphs

A common misconception is that an expression with no redundant terms is automatically the minimal expression.

📖Definition 4.4: Irredundant Boolean Functiondefinition

A Boolean expression is said to be irredundant if no product term (AND gate) can be removed from the expression without altering its logical truth table behavior.

Every minimal expression is strictly irredundant, but an irredundant expression is NOT necessarily minimal!

$$\text{Minimal} \implies \text{Irredundant} \quad (\text{Converse is False})$$

When a K-map has no essential prime implicants (such as a cyclic map where every minterm is covered by exactly two PIs), multiple distinct minimal SOP expressions exist. An engineer can select whichever alternative has fewer total literals or better wiring routing on the printed circuit board.

---

🏭 Real-World Production Context: BCD-to-7-Segment Display Decoders

The classic real-world benchmark for K-map don't-care optimization is the BCD-to-7-Segment Display Driver (e.g. the standard TTL 74LS47 or CMOS CD4511 IC):

Architecture Flow

BCD-to-7-Segment Driver Architecture (74LS47)

Don't-care states (10–15) reduce decoder gate count from 28 gates down to 9 gates

🔢Binary Input

BCD Nibble (A, B, C, D)

4-bit input representing decimal digits 0 to 9 (0000 to 1001).

→

Unused 10–15

❓Don't Care Space

6 Redundant States

Bit patterns 1010 to 1111 (d10–d15) never occur in valid decimal registers.

→

Quad Expansion

⚡Synthesis Core

Minimized AND-OR Array

Don't-cares merge isolated 1s into large Quads, eliminating 60% of gate count.

→

7 Segment Lines

💡Display Unit

7-Segment LED (a–g)

Directly drives physical LED segments (a, b, c, d, e, f, g) with low power.

For segment $a$ (the top horizontal LED bar), the display must illuminate for digits: $0, 2, 3, 5, 6, 7, 8, 9$ In a 4-variable system ($A, B, C, D$), these correspond to minterms: $\sum m(0, 2, 3, 5, 6, 7, 8, 9)$

Because BCD never generates inputs $10, 11, 12, 13, 14, 15$, these six states are don't cares: $\sum d(10, 11, 12, 13, 14, 15)$

The Dramatic Impact of Don't Cares:

• Without Don't Cares: Segment $a$ requires 5 product terms and 14 literals (requiring 5 separate multi-input AND gates plus a 5-input OR gate).
• With Don't Cares: Cells $d(10, 11, 14, 15)$ expand minterms into massive Quads, reducing the expression to:

$$F_a = A + C + BD + \bar{B}\bar{D}$$

This reduces total gates from 6 gates down to 3 gates, cutting silicon area by over 60% and drastically lowering power dissipation across billions of consumer LED meters and microwave displays!

---

📐 Numerical Applications & Worked Examples

Example 1: Finding PIs, EPIs, and Minimal SOP on a 3-Variable K-Map

Problem Statement:
Given the 3-variable Boolean function:

$$F(A, B, C) = \sum m(1, 2, 3, 4, 5)$$

1. Plot the function and identify all Prime Implicants (PI).
2. Determine the Essential Prime Implicants (EPI).
3. State whether redundant prime implicants exist.
4. Write all possible minimal SOP expressions.

Step-by-Step Solution:

1. Plot the K-Map & Identify Subcubes:

🗺️

3-Variable Prime & Essential Prime Implicants (Example 1)

Hover or tap group pills below to see the two EPIs (A'B, AB') and candidate PIs (A'C, B'C)

3-Var SOP Toroidal Grid

BC ➔ ⬇ A	00BC	01BC	11BC	10BC
0A	m00	m11	m31	m21
1A	m41	m51	m70	m60

Subcube Groups & Prime ImplicantsHover or tap to inspect group coverage

Minimized Boolean Expression:F = A'B + AB' + A'C

2. Form All Maximal Subcubes (Prime Implicants):

   • Pair 1: $\{m_1, m_3\} \implies$ Across row $0$ ($A=0$), cols $01, 11$ ($C=1$). Term $= \bar{A}C$.
   • Pair 2: $\{m_2, m_3\} \implies$ Across row $0$ ($A=0$), cols $11, 10$ ($B=1$). Term $= \bar{A}B$.
   • Pair 3: $\{m_1, m_5\} \implies$ Across rows $0, 1$, col $01$ ($B=0, C=1$). Term $= \bar{B}C$.
   • Pair 4: $\{m_4, m_5\} \implies$ Across row $1$ ($A=1$), cols $00, 01$ ($B=0$). Term $= A\bar{B}$.

   $\text{Total Prime Implicants (PI)} = 4 \quad (\bar{A}C, \, \bar{A}B, \, \bar{B}C, \, A\bar{B})$

3. Determine Essential Prime Implicants (EPI): Test each minterm for unique coverage:

   • Minterm $m_2$ (010): Covered only by Pair 2 ($\bar{A}B$). $\implies \mathbf{\bar{A}B\text{ is an EPI}}$!
   • Minterm $m_4$ (100): Covered only by Pair 4 ($A\bar{B}$). $\implies \mathbf{A\bar{B}\text{ is an EPI}}$!
   • Minterm $m_1$ is shared by Pair 1 and Pair 3.
   • Minterm $m_3$ is shared by Pair 1 and Pair 2.
   • Minterm $m_5$ is shared by Pair 3 and Pair 4.

   $\text{Total EPIs} = 2 \quad (\bar{A}B, \, A\bar{B})$

4. Cover Remaining Minterms:

   • EPI $\bar{A}B$ covers $\{m_2, m_3\}$.
   • EPI $A\bar{B}$ covers $\{m_4, m_5\}$.
   • Remaining uncovered minterm: $m_1$.
   • Minterm $m_1$ can be covered by either Pair 1 ($\bar{A}C$) or Pair 3 ($\bar{B}C$).

5. Final Minimal Expressions (Two Distinct Solutions):

   • Solution 1: $F = \bar{A}B + A\bar{B} + \bar{A}C$
   • Solution 2: $F = \bar{A}B + A\bar{B} + \bar{B}C$

Both minimal expressions use exactly 3 gates and 6 literals.

---

Example 2: 4-Variable K-Map with Don't Care Optimization

Problem Statement:
Determine the number of Prime Implicants, Essential Prime Implicants, and the minimal SOP expression for the 4-variable Boolean function:

$$F(w, x, y, z) = \sum m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)$$

Step-by-Step Solution:

1. Plot the 4-Variable K-Map & Identify Prime Implicants:

🗺️

4-Variable Don't-Care Optimization (Example 2)

Hover or tap group pills below to see how don't cares d8 and d10 enlarge the Corner Quad while unused d's are ignored

4-Var SOP Toroidal Grid

yz ➔ ⬇ wx	00yz	01yz	11yz	10yz
00wx	m01	m10	m3d	m21
01wx	m40	m51	m71	m60
11wx	m12d	m130	m150	m14d
10wx	m8d	m91	m111	m10d

Subcube Groups & Prime ImplicantsHover or tap to inspect group coverage

Minimized Boolean Expression:F = x'z' + w'xz + wx'z

2. Identify Prime Implicants Leveraging Don't Cares:

   • Subcube 1 (Center-Left Quad of 4 cells):
     • Consider cells $\{m_5, m_7\}$ in row $01$.
     • Notice row $10$ contains $\{m_9, m_{11}\}$ in the exact same columns ($01, 11$)!
     • However, they are NOT adjacent. But look closely at the map:
     • In row $01$, cells $\{m_5, m_7\}$ form a Pair with $CD \in \{01, 11\}$. Can they expand? No other adjacent row has 1s or $d$s at cols $01, 11$.
     • Thus, $\{m_5, m_7\}$ forms Pair 1: Across row $01$ ($\bar{w}x$), cols $01, 11$ ($z=1$). Term $= \bar{w}xz$.
     • In row $10$, cells $\{m_9, m_{11}\}$ form Pair 2: Across row $10$ ($w\bar{x}$), cols $01, 11$ ($z=1$). Term $= w\bar{x}z$.
   • Subcube 2 (The 8-Cell Octet of Column 00 and 10):
     • Inspect column $00$ and column $10$:
       • Column $00$ contains: $m_0$, empty, $d_{12}, d_8$.
       • Column $10$ contains: $m_2$, empty, $d_{14}, d_{10}$.
     • Notice row $00$ has $\{m_0, m_2\}$, row $11$ has $\{d_{12}, d_{14}\}$, and row $10$ has $\{d_8, d_{10}\}$.
     • Along column $10$, cells $\{m_0, m_2, d_8, d_{10}, d_{12}, d_{14}\}$ are present!
     • Furthermore, the 4 corners $\{m_0, m_2, d_8, d_{10}\}$ form a massive Quad:
       • Term $= \bar{x}\bar{z}$.

3. Verify Essential Prime Implicants:

   • Minterm $m_0$ is covered by the 4-corner Quad ($\bar{x}\bar{z}$).
   • Minterms $m_5, m_7$ are covered exclusively by $\bar{w}xz \implies \mathbf{\bar{w}xz\text{ is an EPI}}$!
   • Minterms $m_9, m_{11}$ are covered exclusively by $w\bar{x}z \implies \mathbf{w\bar{x}z\text{ is an EPI}}$!
   • Corner Quad $\{m_0, m_2, d_8, d_{10}\}$ is an EPI because it uniquely covers $m_0$ and $m_2$.

4. Final Minimized Expression:

$$F(w, x, y, z) = \bar{x}\bar{z} + \bar{w}xz + w\bar{x}z$$

Unused don't cares ($d_3, d_{12}, d_{14}$) are left as logic 0s and consume zero hardware gates.

---

Example 3: Minimal Irredundant Cover vs. Non-Minimal Cover

Problem Statement:
Consider a function with the following prime implicants:

• $P_1 = \bar{A}B$ (covers $m_2, m_3$)
• $P_2 = BC$ (covers $m_3, m_7$)
• $P_3 = A\bar{C}$ (covers $m_4, m_6$)
• $P_4 = \bar{A}C$ (covers $m_1, m_3$)

If $F = P_1 + P_2 + P_3 + P_4$ covers all minterms $\{m_1, m_2, m_3, m_4, m_6, m_7\}$:

1. Determine if this 4-term expression is irredundant.
2. Find the true minimal SOP expression.

Step-by-Step Solution:

1. Check Redundancy of $P_2 = BC$:
   • Minterm $m_3$ is already covered by $P_1$ ($\bar{A}B$) and $P_4$ ($\bar{A}C$).
   • Minterm $m_7$ is covered by $P_2$. But if $P_2$ is removed, is $m_7$ covered?
   • Inspecting $P_1, P_3, P_4$: none cover $m_7$. Thus $P_2$ is needed unless an alternative covers it.
   • Now check $m_3$: $m_3$ is covered by three different terms ($P_1, P_2, P_4$).
   • If we remove $P_2$, $m_7$ becomes uncovered.
   • However, what if we pair $m_7$ with $m_6$ (term $AB$)?
   • The prime implicant covering $\{m_6, m_7\}$ is $AB$.
   • Replacing $P_2$ and $P_3$ with $AB$ and $A\bar{C}$ leaves:

$$F_{\text{minimal}} = \bar{A}C + \bar{A}B + AB + A\bar{C}$$

2. Evaluate Irredundancy: In the original expression $P_1 + P_2 + P_3 + P_4$: No single term can be deleted without leaving at least one minterm uncovered:
   • Delete $P_1 \implies m_2$ uncovered.
   • Delete $P_2 \implies m_7$ uncovered.
   • Delete $P_3 \implies m_4$ uncovered.
   • Delete $P_4 \implies m_1$ uncovered.
   • Verdict: The expression is 100% irredundant, yet it requires 4 terms.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Can an Essential Prime Implicant (EPI) be composed entirely of don't-care conditions?
  Strictly NO. By definition, an EPI must contain at least one distinguished minterm (a real 1) that is not covered by any other prime implicant. Don't-care conditions are not minterms; the circuit has no requirement to assert 1 for them. A group composed solely of don't-cares covers zero minterms and would add an entirely useless logic gate to the chip.

• Why must we identify all Essential Prime Implicants FIRST before attempting to cover the rest of the K-map?
  EPIs are non-negotiable: they contain unique minterms that cannot be covered by any other choice. Because they must be included in the circuit regardless, their groups will automatically cover other adjacent 1s as a byproduct. Identifying EPIs first reveals which minterms are already resolved, dramatically simplifying the selection of remaining selective prime implicants.

Common Interview Traps

• Trap: Forgetting that Don't-Care terms do NOT have to be covered.
  Candidates frequently waste effort creating extra pairs or quads just to circle leftover 'd' cells on the K-map. Remember: don't cares are completely optional! If all real 1s are covered, any remaining 'd' cells are simply treated as 0s and left alone.

• Trap: Counting an implicant as Prime when it can still be enlarged.
  A group of 2 cells is NOT a Prime Implicant if it can be merged with two adjacent cells to form a Quad of 4 cells. Including a non-prime implicant in your expression leaves redundant literals in your circuit equations.

---

🗺️View Complete Digital Logic Roadmap & Syllabus

← Previous Topic4.2 3-Variable and 4-Variable K-Map MinimizationNext Topic →5.1 Half Adder, Full Adder & Ripple Carry Architecture