🟩 K-map Simplification (Made Easy)

Visual shortcut for simplifying Boolean expressions

1. Why do we need K-map?

Boolean algebra can be simplified using rules (De Morgan, distributive, etc.), but it gets long and confusing for big equations.

K-map (Karnaugh Map) is a visual shortcut that makes simplification easier.

It's like a puzzle grid where you group 1s (for SOP form) or 0s (for POS form) to get a minimal Boolean expression.

👉 Real-life connection:

Imagine you're wiring a circuit for a vending machine. Instead of using 10 gates, if you simplify with K-map, maybe you only need 6 gates → cheaper, faster, and less power-hungry.

2. Basics of K-map

K-map is like a truth table but drawn as a grid of boxes.

Each cell = one possible combination of input values (0s and 1s).

The number of cells = 2ⁿ, where n = number of variables.

Variables No. of Cells Shape of K-map
2 4 2×2 grid
3 8 2×4 grid
4 16 4×4 grid
5 32 Bigger grid (usually handled by Quine-McCluskey method)

3. Steps to Solve with K-map

  1. Draw the grid (based on number of variables).
  2. Fill the K-map with 1s (for SOP → minterms) or 0s (for POS → maxterms).
  3. Group the 1s/0s: Make groups of 1, 2, 4, 8... (powers of 2). Groups can wrap around edges!
  4. Write expression for each group:
    • If a variable changes inside the group → eliminate it.
    • If a variable stays the same → keep it.
  5. Combine all groups → Final simplified Boolean expression.

Minterms and Maxterms Explained

1️⃣ Minterm (Sum of Products – SOP)

👉 A minterm is a product (AND) of all input variables in either true or complement form.

It represents exactly one row of the truth table where the output is 1.

✅ Example with 2 variables (A, B):

A B Minterm (AND form)
0 0 A′B′
0 1 A′B
1 0 AB′
1 1 AB
So:
m0 = A′B′
m1 = A′B
m2 = AB′
m3 = AB
⚡ In general:
Minterm = AND of variables.
Use when output = 1.
Expression = Sum of minterms (OR of all minterms where output = 1).
2️⃣ Maxterm (Product of Sums – POS)

👉 A maxterm is a sum (OR) of all input variables in either true or complement form.

It represents exactly one row of the truth table where the output is 0.

✅ Example with 2 variables (A, B):

A B Maxterm (OR form)
0 0 A + B
0 1 A + B′
1 0 A′ + B
1 1 A′ + B′
So:
M0 = A + B
M1 = A + B′
M2 = A′ + B
M3 = A′ + B′
⚡ In general:
Maxterm = OR of variables.
Use when output = 0.
Expression = Product of maxterms (AND of all maxterms where output = 0).
3️⃣ Quick Difference
Feature Minterm (m) Maxterm (M)
Form Product (AND) of literals Sum (OR) of literals
Output Row 1 0
Expression Sum of Products (SOP) Product of Sums (POS)
Example (A=0,B=1) A′B → m1 A + B′ → M1
✅ Example Problem:

Say we have a truth table output:

A B | F
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

From minterms (1s):

F = m1 + m2 = A′B + AB′

From maxterms (0s):

F = M0 · M3 = (A + B)(A′ + B′)

👉 Both are the same function, just written differently.

4. Complete Example with 2 Variables

Let's practice grouping in a K-map with 2 variables.

🔹 Example: Function F(A, B)
A B F
0 0 0
0 1 1
1 0 1
1 1 1
🔹 Step 1: Put into K-map

K-map layout for 2 variables:

A\B  0  1
0    0  1
1    1  1
🔹 Step 2: Grouping

Rules: groups must be 1, 2, or 4 cells (powers of 2) and rectangular.

Group 1 → Take the two 1s in column B=1 (Row A=0,1 → vertical group).

Here, B=1 always, A changes.

So group = B.

Group 2 → Take the two 1s in row A=1 (Column B=0,1 → horizontal group).

Here, A=1 always, B changes.

So group = A.

🔹 Step 3: Write simplified expression

Combine the groups:

👉 F = A + B
✅ Final Answer: The simplified Boolean expression is F = A + B.
🔹 Another Example: Complete Flow

Example using 2 variables (A, B). I'll show you truth table → minterms → maxterms → K-map → simplified expression.

Example: Function F(A, B)

Suppose the output is defined as:

Row A B F
0 0 0 1
1 0 1 1
2 1 0 0
3 1 1 1
🔹 Step 1: Minterms (SOP → sum of products)

Take rows where F = 1.

Row 0: A=0, B=0 → A′B′

Row 1: A=0, B=1 → A′B

Row 3: A=1, B=1 → AB

👉 SOP form: F = A′B′ + A′B + AB
🔹 Step 2: Maxterms (POS → product of sums)

Take rows where F = 0.

Row 2: A=1, B=0 → A′ + B

👉 POS form: F = (A′ + B)
🔹 Step 3: K-map (2 variables)

K-map grid for 2 variables:

A\B  0  1
0    1  1
1    0  1

(We placed the F values directly from truth table.)

🔹 Step 4: Grouping

Group (Row 0 & Row 1 → A=0 fixed) → A′

Group (Row 3 alone → A=1, B=1) → AB

👉 Simplified expression: F = A′ + AB
✅ Final simplified Boolean expression: F = A′ + AB

5. Example 2: 3-Variable K-map

Variables: A, B, C → 2³ = 8 cells.

Suppose F = Σ(1,3,5,7) (ones at minterms 1,3,5,7).

K-map (2×4 grid):

C=0
C=1
AB=00
0
1
AB=01
0
1
AB=11
0
1
AB=10
0
1

All 1s are in column where C=1.

👉 Expression = C
✅ Simplified Expression: F = C

6. Example 3: 4-Variable K-map

Variables: A, B, C, D → 2⁴ = 16 cells.

Suppose F = Σ(0,1,2,3,8,9,10,11).

This is a big rectangle covering half the map.

👉 Result = A′
✅ Simplified Expression: F = A′

7. Don't Care Conditions (X)

Sometimes, certain input combinations never happen or we don't care about them.

Mark them as X in the K-map.

We can treat X as 1 if it helps form a bigger group (to simplify further).

👉 Example:

If F = Σ(1,2,5) + d(6,7), where d = don't care.

Group 1s and Xs together → bigger rectangles → smaller expression.

8. Essential Prime Implicants

A prime implicant = a group of 1s.

Essential prime implicant = a group that covers a 1 that no other group covers.

These are must-have terms in the final simplified expression.

👉 Example:

If one lonely 1 exists in a cell, any group that covers it = essential.

9. Why K-map Matters in COA (Computer Organization & Architecture)

Every Boolean expression turns into a logic circuit.

Simplifying with K-map reduces number of gates →

👉 Example:

A memory decoder circuit might need 10 gates, but after K-map simplification, only 6 gates. This matters when billions of circuits are built into CPUs.

10. Summary for Students

✅ K-map = shortcut for simplifying Boolean equations.

✅ Fill the grid with 1s → group → eliminate variables → final expression.

✅ Don't care (X) helps you simplify more.

✅ Essential prime implicants are the must-have groups.

✅ Used in real computer hardware design to save cost, power, and speed.