Karnaugh Maps, Prime Implicants & Don't Cares
“Gray code adjacency, essential prime implicants, minimal SOP/POS, and 5-variable K-map partitions.”
1.Karnaugh Map Topology & Implicant Hierarchy
§ 1.1.A Karnaugh Map (K-map) provides a systematic visual method for Boolean minimization up to 4 or 5 variables without algebraic trial-and-error.
Topological Wrap-Around: A 4-variable K-map represents a torus: the top edge is adjacent to the bottom edge, and the left edge is adjacent to the right edge. The four corner cells m_0 (0000), m_2 (0010), m_8 (1000), and m_{10} (1010) are all mutually adjacent and form a single group of 4.
Terminology Hierarchy:
1. Implicant: Any product term that implies the function (any single '1' or group of '1's).
2. Prime Implicant (PI): An implicant obtained by combining the maximum possible number of adjacent squares. A PI cannot be subsumed by any larger group.
3. Essential Prime Implicant (EPI): A PI that covers at least one minterm that is not covered by any other PI.
4. Redundant Prime Implicant: A PI whose minterms are completely covered by the set of chosen EPIs.
Look for any minterm '1' that has only ONE valid grouping opportunity. The prime implicant covering that unique 1 is immediately an Essential Prime Implicant.
2. Worked Analysis: Counting PIs and EPIs with Don't Cares
Don't cares (d) can help form PIs, but an EPI must cover an original minterm (1), not merely a don't-care condition.
Problem Statement (Modeled on GATE Pattern):
Find the number of Prime Implicants (PI) and Essential Prime Implicants (EPI) for:
f(A, B, C, D) = Sigma m(0, 2, 5, 7, 8, 10, 15) + d(3, 13)
Step 1: Plot on 4x4 K-map:
Row 00 (A'B'): m0=1, m2=1, d3=X
Row 01 (A'B): m5=1, m7=1
Row 11 (AB): d13=X, m15=1
Row 10 (AB'): m8=1, m10=1
Step 2: Identify maximal groups (PIs):
- Group 1: Corners (0, 2, 8, 10). All four are minterms '1'. Size = 4 -> B'D'. (PI 1)
- Group 2: Cells (2, 3, 0... wait: 2, 3 is size 2 A'B'C). But minterm 2 is already in Group 1.
- Group 3: Cells (5, 7, 13, 15). Notice m5=1, m7=1, d13=X, m15=1. Group of size 4 in column 01 and 11 -> BD. (PI 2)
- Group 4: Row A'B minterms m5, m7 with d3: (3, 7) or (5, 7)? (5, 7, 13, 15) covers 5 and 7 already.
- Can m0 combine with m8? Covered by Group 1.
- Can d3 combine with m2? Group of 2: (2, 3) -> A'B'C. (PI 3)
- Can d3 combine with m7? Group of 2: (3, 7) -> A'CD. (PI 4)
- Total PIs = {B'D', BD, A'B'C, A'CD}.
Step 3: Test Essentiality of PIs:
- Minterm 0: covered ONLY by B'D' -> B'D' is an EPI.
- Minterm 5: covered ONLY by BD -> BD is an EPI.
- Minterm 8, 10: covered ONLY by B'D'.
- Minterm 15: covered ONLY by BD.
- Notice that all minterms {0, 2, 5, 7, 8, 10, 15} are FULLY covered by the two EPIs: B'D' and BD!
- B'D' covers {0, 2, 8, 10}. BD covers {5, 7, 15} (and d13).
- Neither A'B'C nor A'CD covers any uncovered minterm.
Total PIs = 4, Total EPIs = 2 (B'D' and BD).
Minimal SOP expression = B'D' + BD.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
The most thorough digital logic series — textbook quality at no cost.
GATE-focused digital logic with exam-style numericals.