📚 Lesson: Karnaugh Maps (K-Maps)
🎯 Learning Objectives
By the end of this lesson, students will be able to:
- Understand the structure and purpose of Karnaugh Maps
- Apply Gray code to organize variables
- Minimize Boolean expressions using SOP and POS techniques
- Handle “don’t care” conditions effectively
1️⃣ What is a Karnaugh Map?
-
A Karnaugh Map (K-Map) is a grid-based tool that simplifies Boolean expressions by grouping adjacent 1s (or 0s for POS) into rectangles.
-
Each cell represents a minterm (SOP) or maxterm (POS) from the truth table.
2️⃣ Steps for SOP Minimization
- Build the K-Map using Gray code for row and column headers.
- Fill in the output values from the truth table.
- Group adjacent 1s in rectangles of 1, 2, 4, or 8 cells.
- Extract simplified terms by identifying variables that remain constant within each group.
Example: 4-Variable K-Map
Given a truth table for inputs A, B, C, D and output Z:
| A | B | C | D | Z |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 |
After grouping and simplifying:
✅ Final SOP Expression:
Z = $\overline{A} \cdot B + A \cdot \overline{B} \cdot \overline{C} + A \cdot \overline{B} \cdot \overline{D}$
Exercise: 3-Variable K-Map
Given a truth table for inputs A, B, C, and output Z:
| A | B | C | Z |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
✅ Simplified SOP:
Z = B
Exercise: OR Gate K-Map
Build a truth table for a 2-input OR gate and verify using a K-Map that:
✅ Z = A + B
Don’t Care Conditions
- Some input combinations may never occur.
- These are marked as ‘x’ in the truth table and can be treated as 1s or 0s—whichever helps simplify the expression.
Exercise: SOP with Don’t Cares
Given a truth table for inputs A, B, C, D and output Z:
| A | B | C | D | Z |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | x |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | x |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | x |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | x |
| 1 | 1 | 1 | 1 | 1 |
✅ Simplified SOP: Z = $\overline{B} + A \cdot C + A \cdot \overline{C} \cdot \overline{D}$
3️⃣ Steps for SOP Minimization
When the truth table has more 1s than 0s, use Product of Sums (POS) mapping:
- Identify 0s in the truth table.
- Group adjacent 0s in rectangles.
- For each group, write a sum of complemented variables that remain constant.
- Multiply all groups together.
Exercise: POS Minimization
Given a truth table for inputs A, B, C, D and output Z:
| A | B | C | D | Z |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
✅ Simplified POS: Z = $(A + B + \overline{C} + \overline{D}) \cdot (\overline{A} + \overline{C} + D)$