Activity 2.2.1 — Karnaugh Maps (K-Maps)¶
Learning Objectives¶
By the end of this lesson, students will be able to:
- Explain why Karnaugh maps are useful for simplifying Boolean expressions
- Construct and interpret 2-variable, 3-variable, and 4-variable K-maps
- Apply K-map grouping rules to simplify Boolean expressions
- Use don't care conditions (X) to maximize simplification
Vocabulary¶
Vocabulary (click to expand)
| Term | Definition |
|---|---|
| Karnaugh Map (K-map) | A visual grid representation of a truth table that shows adjacent cells differing by only one bit, used to simplify Boolean expressions |
| Gray Code | A binary number system where adjacent values differ by only one bit |
| Minterm | A product term that produces a 1 output; each minterm corresponds to a row where the output is 1 |
| Grouping | Combining adjacent 1s in a K-map to eliminate variables that change |
| Don't Care (X) | A condition that can be treated as either 0 or 1 to maximize group size |
Part 1: Introduction to Karnaugh Maps¶
Boolean algebra simplification using theorems and postulates can be time-consuming and sometimes confusing. Karnaugh maps (K-maps) provide a visual method for simplifying Boolean expressions that is often faster and more intuitive than algebraic manipulation.
Why Use K-Maps?¶
- Visual intuition: You can "see" the simplification by grouping adjacent cells
- Systematic approach: No need to memorize many theorems
- Reduces errors: Visual grouping is less prone to mistakes than algebraic manipulation
- Faster simplification: Particularly effective for expressions with 2-4 variables
Part 2: K-Map Structure¶
K-maps are grids where each cell represents a minterm. The key feature is Gray code ordering — adjacent cells differ by only one bit.
2-Variable K-Map (2×2 grid)¶
| B=0 | B=1 | |
|---|---|---|
| A=0 | m0 (00) | m1 (01) |
| A=1 | m2 (10) | m3 (11) |
Notice: Going from any cell to an adjacent cell (horizontally or vertically), only ONE variable changes.
3-Variable K-Map (2×4 grid)¶
| BC=00 | BC=01 | BC=11 | BC=10 | |
|---|---|---|---|---|
| A=0 | m0 | m1 | m3 | m2 |
| A=1 | m4 | m5 | m7 | m6 |
4-Variable K-Map (4×4 grid)¶
| CD=00 | CD=01 | CD=11 | CD=10 | |
|---|---|---|---|---|
| AB=00 | m0 | m1 | m3 | m2 |
| AB=01 | m4 | m5 | m7 | m6 |
| AB=11 | m12 | m13 | m15 | m14 |
| AB=10 | m8 | m9 | m11 | m10 |
Key insight: The Gray code ordering (00, 01, 11, 10) ensures adjacent cells differ by only one bit, allowing proper grouping of terms that differ by one variable.
Part 3: Filling a K-Map from a Truth Table¶
To fill a K-map: 1. Identify all rows where the output is 1 (the minterms) 2. Place a 1 in each cell corresponding to those minterms 3. Leave all other cells as 0
Example: Given the truth table:
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The minterms where Y=1 are: m0 (A=0, B=0), m2 (A=1, B=0), m3 (A=1, B=1)
K-map filled:
| B=0 | B=1 | |
|---|---|---|
| A=0 | 1 | 0 |
| A=1 | 1 | 1 |
Part 4: Grouping Rules¶
To simplify using K-maps, group adjacent 1s according to these rules:
Grouping Rules Summary¶
- Shape: Groups must be rectangular
- Size: Groups must contain 1, 2, 4, 8, or 16 cells (powers of 2)
- Maximize: Groups should be as large as possible
- Coverage: Every 1 must be in at least one group
- Overlap: Groups may overlap
- Wrap-around: Groups may wrap around edges and corners
Reading Groups¶
When you have a group, determine the simplified term: - Variables that STAY CONSTANT in the group are kept - Variables that CHANGE are eliminated
Example from 2-variable K-map:
| B=0 | B=1 | |
|---|---|---|
| A=0 | 1 | 0 |
| A=1 | 1 | 1 |
Group the two 1s in the left column (A=0 row and A=1 row): - A changes (0→1), so A is eliminated - B stays constant (0), so B is kept - Simplified term: B'
Key insight: Grouping adjacent 1s that differ in one variable eliminates that variable because the theorem A + A' = 1 applies.
Part 5: Don't Care Conditions¶
Don't care conditions (marked with X) can be treated as either 0 or 1, whichever helps create larger groups.
Example:
| B=0 | B=1 | |
|---|---|---|
| A=0 | 1 | X |
| A=1 | 1 | 0 |
Treat the X as 1 to group all four cells: - This creates one group of 4 - All variables change, so result is 1 (always HIGH)
If we didn't use the X, we'd need two groups of 1 each, giving us a more complex expression.
Key insight: Don't care conditions give you flexibility — use them strategically to maximize your groups, but never include a 1 if doing so would make the logic incorrect.
Part 6: Worked Examples¶
Example 1: 3-Variable Simplification¶
Truth Table:
| A | B | C | Y |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Step 1: Fill K-map
| BC=00 | BC=01 | BC=11 | BC=10 | |
|---|---|---|---|---|
| A=0 | 1 | 1 | 1 | 0 |
| A=1 | 0 | 0 | 1 | 1 |
Step 2: Group 1s
- Group 1: Top row, first three cells → A'=0, C stays same, eliminated B → A'C
- Group 2: Right column, both rows → C=1, B changes, eliminated A → C
- Group 3: Bottom right cell (already covered)
Step 3: Write simplified expression
Y = A'C + C
Applying absorption: Y = C(A' + 1) = C(1) = C
Final simplified expression: Y = C
Example 2: 4-Variable Simplification¶
Expression: F(A,B,C,D) = Σm(0,2,4,5,6,8,10,12,13,14)
Step 1: Fill K-map
| CD=00 | CD=01 | CD=11 | CD=10 | |
|---|---|---|---|---|
| AB=00 | 1 | 0 | 0 | 1 |
| AB=01 | 1 | 1 | 0 | 1 |
| AB=11 | 1 | 1 | 1 | 1 |
| AB=10 | 1 | 0 | 0 | 1 |
Step 2: Group 1s
- Group 1: Four corner cells → A'B' + BD' (wrapping) → B'D'
- Group 2: Middle rows, first two columns → A'C' → A'C'
- Group 3: Bottom two rows, middle two columns → CD → CD
Step 3: Write simplified expression
F = B'D' + A'C' + CD
Practice Problem — K-Map Simplification¶
Problem 1: Simplify the Boolean expression using a K-map: F(A,B,C) = Σm(0,1,3,4,5,6)
Fill the K-map, group the 1s, and write the simplified expression.
Show Solution
Step 1: Fill K-map
| BC=00 | BC=01 | BC=11 | BC=10 | |
|---|---|---|---|---|
| A=0 | 1 | 1 | 1 | 0 |
| A=1 | 1 | 1 | 0 | 1 |
Step 2: Group 1s
- Group 1: Top row → A'=0 eliminated, B=0 stays → B'
- Group 2: Left column → B'=0 eliminated, A changes → B' (already covered)
- Group 3: Four cells in bottom left → C eliminated, AB changes → A'B' or B'C'
Actually, let's group better: - Group 1: Four cells (0,1,4,5) → B'=0 → B' - Group 2: Three cells (2,3,6) can't group with anything else...
Wait, let me redo: - Group of 4: m0,m1,m4,m5 → B' - Group of 2: m3,m7 → C=1, A stays 0 → A'C - Group of 2: m6,m7 → C=1, B stays 1 → BC
Step 3: Simplified expression
F = B' + A'C + BC
Using consensus theorem to check: This is already simplified.
Problem 2: Simplify using don't cares: F(A,B,C) = Σm(1,3,5) + d(0,7)
Use the Xs to create the largest possible groups.
Show Solution
Step 1: Fill K-map with don't cares
| BC=00 | BC=01 | BC=11 | BC=10 | |
|---|---|---|---|---|
| A=0 | X | 0 | 1 | 0 |
| A=1 | 0 | 1 | 0 | 1 |
Step 2: Group 1s using Xs
- Group 1: m1,m3 → A'=0, C=1 → A'C
- Group 2: m5,m7(X) → A=1, C=1 → AC
- Group 3: m0(X),m1 → B'=0, C changes → B' (using don't care)
Step 3: Simplified expression
F = A'C + AC + B'
Using A'C + AC = C(A' + A) = C: F = C + B'
Final simplified expression: F = C + B'
Summary¶
- Karnaugh maps provide a visual method for simplifying Boolean expressions
- Gray code ordering ensures adjacent cells differ by only one bit
- Grouping rules: rectangular groups of 1, 2, 4, 8, or 16 cells; maximize group size; every 1 covered; groups can wrap around edges
- Reading groups: variables that stay constant are kept; variables that change are eliminated
- Don't care conditions (X) can be used as 0 or 1 to maximize simplification
Key Reminders¶
- Always use Gray code ordering (00, 01, 11, 10) when labeling K-map edges
- Groups must be powers of 2 in size
- Don't cares are optional — use them when they help, but never force a group that makes logic incorrect
- After grouping, write the simplified expression by ORing all group terms together
Custom activity — adapted from PLTW Digital Electronics