Activity 2.2.1 — Karnaugh Maps (K-Maps)

---

Learning Objectives

By the end of this lesson, students will be able to:

1. Explain why Karnaugh maps are useful for simplifying Boolean expressions
2. Construct and interpret 2-variable, 3-variable, and 4-variable K-maps
3. Apply K-map grouping rules to simplify Boolean expressions
4. 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.

flowchart LR
    A["Truth Table"] --> B["Fill K-map"]
    B --> C["Group adjacent 1s"]
    C --> D["Read simplified<br/>expression"]
    style A fill:#C9A227,color:#1a1a2e
    style D fill:#C9A227,color:#1a1a2e

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 (2x2 grid)

Notice: Going from any cell to an adjacent cell (horizontally or vertically), only ONE variable changes.

3-Variable K-Map (2x4 grid)

4-Variable K-Map (4x4 grid)

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:

---

Part 4: Grouping Rules

To simplify using K-maps, group adjacent 1s according to these rules:

Grouping Rules Summary

1. Shape: Groups must be rectangular
2. Size: Groups must contain 1, 2, 4, 8, or 16 cells (powers of 2)
3. Maximize: Groups should be as large as possible
4. Coverage: Every 1 must be in at least one group
5. Overlap: Groups may overlap
6. 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:

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: $\overline{B}$

Key insight: Grouping adjacent 1s that differ in one variable eliminates that variable because the theorem A + \overline{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:

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

Step 2: Group 1s

• Group 1: Top row, first three cells → \overline{A}=0, C stays same, eliminated B → $\overline{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 = \overline{A}C + C

Applying absorption: Y = C(\overline{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

Step 2: Group 1s

• Group 1: Four corner cells → \overline{A}\overline{B} + B\overline{D} (wrapping) → $\overline{B}\overline{D}$
• Group 2: Middle rows, first two columns → \overline{A}\overline{C} → $\overline{A}\overline{C}$
• Group 3: Bottom two rows, middle two columns → CD → CD

Step 3: Write simplified expression

F = \overline{B}\overline{D} + \overline{A}\overline{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 → \overline{A}=0 eliminated, B=0 stays → $\overline{B}$
• Group 2: Left column → \overline{B}=0 eliminated, A changes → $\overline{B}$ (already covered)
• Group 3: Four cells in bottom left → C eliminated, AB changes → $\overline{A}\overline{B}$ or $\overline{B}\overline{C}$

Actually, let’s group better:

• Group 1: Four cells (0,1,4,5) → \overline{B}=0 → $\overline{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 → $\overline{B}$
• Group of 2: m3,m7 → C=1, A stays 0 → $\overline{A}C$
• Group of 2: m6,m7 → C=1, B stays 1 → BC

Step 3: Simplified expression

F = \overline{B} + \overline{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 → \overline{A}=0, C=1 → $\overline{A}C$
• Group 2: m5,m7(X) → A=1, C=1 → AC
• Group 3: m0(X),m1 → \overline{B}=0, C changes → $\overline{B}$ (using don’t care)

Step 3: Simplified expression

F = \overline{A}C + AC + \overline{B}

Using \overline{A}C + AC = C(\overline{A} + A) = C: F = C + \overline{B}

Final simplified expression: F = C + \overline{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