Chapter 4: K-Maps & Boolean Algebra

§ 4.1

Prerequisites — What You Need to Know First

Before diving into K-Maps, let's make sure we're all on the same page. Think of it as packing your bag before a journey. If you have all these items, you're ready!

✅ Your Learning Checklist

✓
Binary Numbers (0 and 1) — You should know what 0 and 1 mean in digital systems.
✓
Logic Gates (AND, OR, NOT) — Basic understanding of how logic gates work.
✓
Truth Tables — Ability to read and fill a truth table.
✓
Boolean Algebra — Basic rules like A+A'=1 and A·A'=0.
✓
Minterms & Maxterms — Expressing functions in standard forms.

💡 Do Not Worry!

If you don't know some of these yet, this chapter will teach everything from scratch — starting with Section 4.2. We explain each concept with daily life examples first.

§ 4.2

Binary Numbers — The Language of Computers

We use 10 digits (0–9) every day. But computers only understand TWO states: ON and OFF. These are written as 1 (ON/True/High) and 0 (OFF/False/Low). This is called the Binary Number System.

💡 Real Life Example: Light Switch

Switch ON → Electricity flows → Binary: 1

Switch OFF → No electricity → Binary: 0

A computer does billions of these ON/OFF decisions every second!

Decimal to Binary Conversion

To convert a decimal number to binary, keep dividing by 2 and collect the remainders from bottom to top:

Decimal	Operation	Quotient	Remainder
13	13 ÷ 2	6	1 ← (LSB — Write last)
	6 ÷ 2	3	0
	3 ÷ 2	1	1
	1 ÷ 2	0	1 ← (MSB — Write first)
Result: 13₁₀ = 1101₂		Read remainders BOTTOM to TOP

🧠 Memory Trick for Conversion

"Dead Rabbits Bring Trouble" → D·R·B·T → Divide, Remainder, Bottom, Top
Always read the remainders from Bottom to Top to get your binary number!

§ 4.3

Logic Gates — The Building Blocks

A Logic Gate is an electronic device that takes one or more inputs (0 or 1) and gives exactly one output. Think of a gate like a decision machine — it makes a yes/no decision based on what comes in.

🔒

AND Gate

Y = A · B

🚪 Door lock with TWO keys — you need BOTH Key A AND Key B to open. If either is missing, the door stays locked.

A	B	Y = A AND B
0	0	0
0	1	0
1	0	0
1	1	1 ✓

💡

OR Gate

Y = A + B

💡 Room light with TWO switches — the light turns ON if EITHER Switch A OR Switch B is pressed. It only stays OFF if BOTH are off.

A	B	Y = A OR B
0	0	0
0	1	1 ✓
1	0	1 ✓
1	1	1 ✓

🔄

NOT Gate

Y = A'

🔄 A "Reverse" button — When AC is ON → output is OFF. When AC is OFF → output is ON. It simply INVERTS the input!

A	Y = NOT A
0	1 ✓
1	0

🚨

NAND Gate

Y = (A·B)'

🚨 Alarm system — quiet ONLY when both sensors are triggered simultaneously. In all other cases, the alarm GOES OFF. Also called a Universal Gate!

A	B	Y = (A·B)'
0	0	1 ✓
0	1	1 ✓
1	0	1 ✓
1	1	0

🛑

NOR Gate

Y = (A+B)'

🛑 Output is 1 ONLY when ALL inputs are 0. Also a Universal Gate — you can build ANY gate using only NOR gates!

A	B	Y = (A+B)'
0	0	1 ✓
0	1	0
1	0	0
1	1	0

⚡

XOR Gate

Y = A ⊕ B

⚡ Staircase switching — a room with TWO switches where flipping EITHER switch toggles the light. Output is 1 only when inputs are DIFFERENT.

A	B	Y = A ⊕ B
0	0	0
0	1	1 ✓
1	0	1 ✓
1	1	0

🏆 Universal Gates Summary

NAND and NOR are called Universal Gates because you can build ANY other gate (AND, OR, NOT, XOR, XNOR) using only NAND gates, or only NOR gates. This is very useful in chip manufacturing — only one type of gate needs to be fabricated!

§ 4.4

Boolean Algebra — Simplifying Logic with Math

Boolean Algebra is a set of mathematical rules for simplifying logic expressions. We only work with 0 and 1. Simplifying means building a cheaper, smaller circuit that does the same job!

Basic Laws of Boolean Algebra

Think of these as the 'grammar rules' of logic. Learn these and simplification becomes easy!

Identity Law

A · 1 = AA + 0 = A

Multiplying by 1 or adding 0 doesn't change anything.

Null / Dominance Law

A · 0 = 0A + 1 = 1

If one switch is always OFF, the whole circuit is OFF.

Idempotent Law

A · A = AA + A = A

You + You = You. Adding the same thing twice gives the same result.

Complement Law

A · A' = 0A + A' = 1

A door can't be both open AND closed at the same time.

Double Complement

A'' = A

Flipping a switch twice returns to the original position.

Commutative Law

A·B = B·AA+B = B+A

3×5 = 5×3. Order doesn't matter for AND/OR.

Associative Law

(AB)C = A(BC)

Grouping doesn't matter: (2×3)×4 = 2×(3×4).

Distributive Law

A(B+C) = AB+AC

Like factoring in algebra: a(b+c) = ab+ac.

Absorption Law

A+AB = AA(A+B) = A

If you already have A, adding more of it changes nothing.

De Morgan's Theorems ⚠️

(AB)' = A'+B'(A+B)' = A'·B'

The most important law — see detailed explanation below!

De Morgan's Theorems — The Most Important!

⚠️ De Morgan's First Theorem

 (A · B)' = A' + B' 

In words: The complement of a product = the sum of complements.

Real Life: You CANNOT get a coffee AND a tea if EITHER the coffee machine OR the tea machine is broken.

⚠️ De Morgan's Second Theorem

 (A + B)' = A' · B' 

In words: The complement of a sum = the product of complements.

Real Life: The only way NEITHER of you gets into the party is if BOTH of you are denied.

🧠 Easy Memory Trick for De Morgan's

BREAK → COMPLEMENT → CHANGE

BREAK the bar over the whole expression
COMPLEMENT each individual variable
CHANGE the operator: · becomes +, and + becomes ·

Step-by-Step Simplification Example

Problem: Simplify Y = AB + AB'

Step	Expression	Rule Applied	Explanation
Start	`Y = AB + AB'`	—	Given expression
Step 1	`Y = A(B + B')`	Distributive Law	Factor out A from both terms
Step 2	`Y = A(1)`	Complement: B+B' = 1	Anything OR its complement = 1
Step 3	`Y = A` ✓	Identity: A·1 = A	Final simplified result!

✅ Result

The complex expression AB + AB' simplifies to just A! We went from needing 2 AND gates + 1 NOT gate + 1 OR gate → to just a wire. That's huge savings in hardware!

§ 4.5

Minterms & Maxterms — Standard Forms

When we have a truth table, we need a standard way to write the Boolean expression from it. Minterms and maxterms give us exactly that.

🧠 The Easy Rule

Minterm: Where output = 1 → variable value 1 means write as-is (A), value 0 means write complement (A')

Maxterm: Opposite — variable value 0 means write as-is, value 1 means complement

Minterm Table for 3 Variables (A, B, C)

Row (m#)	A	B	C	Minterm	Maxterm
m₀	0	0	0	`A'B'C'`	`A+B+C`
m₁	0	0	1	`A'B'C`	`A+B+C'`
m₂	0	1	0	`A'BC'`	`A+B'+C`
m₃	0	1	1	`A'BC`	`A+B'+C'`
m₄	1	0	0	`AB'C'`	`A'+B+C`
m₅	1	0	1	`AB'C`	`A'+B+C'`
m₆	1	1	0	`ABC'`	`A'+B'+C`
m₇	1	1	1	`ABC`	`A'+B'+C'`

Writing SOP from a Truth Table

📖 3-Step Method

Find all rows where output Y = 1

These rows give us our minterms.

Write the minterm for each such row

1 → variable as-is, 0 → complemented variable.

OR all the minterms together

This gives the final SOP expression.

Example: Y at rows 1,3,4,6 → Y = A'B'C + A'BC + AB'C' + ABC' → also written as Y = Σm(1,3,4,6)

§ 4.6

Karnaugh Maps — The Star of this Chapter

A Karnaugh Map (K-Map) is a visual method to simplify Boolean expressions. Instead of using complex algebra rules, you literally draw a grid, fill in 0s and 1s, and circle groups. It's like solving a puzzle!

🎯 Why do we use K-Maps?

Faster — Much quicker than Boolean algebra for 2–6 variable problems.
Visual — You can see the simplification by eye.
Systematic — Less chance of making errors.
Exam essential — Almost every digital logic exam includes a K-Map question!

🚨 KEY CONCEPT: Gray Code Ordering

🚨 CRITICAL — The Most Important Thing About K-Maps!

Columns and rows in a K-Map are NOT in normal binary order. They use Gray Code: 00, 01, 11, 10. Adjacent cells differ by EXACTLY ONE bit. This is what allows grouping to work!

❌ WRONG ORDER

00 → 01 → 10 → 11

✅ CORRECT (Gray Code)

00 → 01 → 11 → 10

Memory trick: "Go On, I Love You" → G=00, O=01, I=11, L=10

2-Variable K-Map

A 2-variable K-Map has 4 cells in a 2×2 grid:

2-VARIABLE K-MAP (Variables: A, B)

A \ B	B=0	B=1
A=0	m₀	m₁
A=1	m₂	m₃

3-Variable K-Map

A 3-variable K-Map has 8 cells in a 2×4 grid. Notice the Gray Code column order:

3-VARIABLE K-MAP (Variables: A, B, C)

A \ BC	BC=00	BC=01	BC=11	BC=10
A=0	m₀	m₁	m₃	m₂
A=1	m₄	m₅	m₇	m₆

⚠️ Notice: m₂ and m₃ are SWAPPED compared to binary order. This is INTENTIONAL!

4-Variable K-Map — The Most Common in Exams!

A 4-variable K-Map has 16 cells in a 4×4 grid:

4-VARIABLE K-MAP (Variables: A, B, C, D)

AB \ CD	CD=00	CD=01	CD=11	CD=10
AB=00	0	1	3	2
AB=01	4	5	7	6
AB=11	12	13	15	14
AB=10	8	9	11	10

💡 The corners (0, 2, 8, 10) can form a group of 4 — they wrap around and are adjacent!

§ 4.7

Grouping Rules — The Heart of K-Map Simplification

Grouping (circling) 1s in the K-Map is how we find the simplified expression. Follow these rules strictly:

#	Rule	Why it Matters
1	Groups must contain ONLY 1s (never mix 0s and 1s)	Mixing would give a wrong expression
2	Group size must be a power of 2: 1, 2, 4, 8, 16	Only powers of 2 lead to variable cancellation
3	Make groups as LARGE as possible	Larger groups = fewer variables = simpler expression
4	Every 1 MUST be covered by at least one group	Uncovered 1s would be missing from the output
5	Groups can WRAP AROUND edges (top↔bottom, left↔right)	K-Map is like a donut (torus) shape!
6	Groups can OVERLAP (a 1 can be in more than one group)	Overlapping allows maximum grouping
7	Use MINIMUM number of groups to cover all 1s	Fewer groups = simpler final expression
8	Every group must have at least one essential 1 (Essential Prime Implicants)	Ensures all groups are necessary

How to Read a Group (Extract the Term)

📖 Reading a Group — Step by Step

Look at ALL cells in the group

For each variable, check if it stays CONSTANT across all cells

If a variable CHANGES → ELIMINATE it from the term

If a variable is ALWAYS 1 → include it as-is (e.g., A)

If a variable is ALWAYS 0 → include its complement (e.g., A')

CHANGE = CANCEL | CONSTANT = KEEP

Complete Worked Example — 4-Variable K-Map

Problem: Simplify F(A,B,C,D) = Σm(0,1,2,3,4,5,6,7,8,10)

FILLED K-MAP — 1s highlighted, groups shown

AB \ CD	CD=00	CD=01	CD=11	CD=10
AB=00	1	1	1	1
AB=01	1	1	1	1
AB=11	0	0	0	0
AB=10	1	0	0	1

Group 1 (8 cells) → term: A' Group 2 (wraps) → term: B'C'D' Group 3 (wraps) → term: B'CD'

✅ Final Result

F = A' + B'C'D' + B'CD'

Reduced from 10 minterms to just 3 terms — that's a massive simplification in circuit complexity!

§ 4.8

Don't-Care Conditions — Bonus Simplification!

Sometimes, certain input combinations can never occur in practice. For these inputs, the output can be anything — 0 or 1 — we don't care! These are called Don't-Care conditions, written as X or d in the K-Map.

📺 Real Life: BCD to 7-Segment Display

BCD represents digits 0–9. But 4 bits can represent 0–15. The inputs 10–15 NEVER appear in BCD, so we don't care what the output is for those inputs → they become Don't-Care conditions (X)!

Rules for Don't-Care Conditions

📋 The Golden Rules

Rule 1: Treat X as 1 if it HELPS make a larger group. Otherwise treat as 0.
Rule 2: NEVER make a group that contains ONLY X cells (no actual 1s).
Rule 3: Don't-Cares don't need to be covered — only actual 1s must be covered.
Rule 4: Use X to your advantage to get a simpler result!

Worked Example with Don't-Cares

Problem: F(A,B,C,D) = Σm(1,3,7,11,15) + d(0,2,5)

K-MAP WITH DON'T-CARE CONDITIONS (X)

AB \ CD	CD=00	CD=01	CD=11	CD=10
AB=00	X	1	1	X
AB=01	0	X	1	0
AB=11	0	0	1	0
AB=10	0	0	1	0

X cells (orange) = don't-care. We USE X at positions 0,2 to form a group of 4 with minterms 1,3.

✅ Solution

F = A'D + CD

Without don't-cares we might need 3+ terms. Using X to our advantage gives us just 2 terms!

§ 4.9

Common Mistakes — & How to Avoid Them

📝 Dr. Sohel Rana's Note

After marking thousands of exam papers, here are the mistakes I see most often. Read these carefully — avoiding them is worth several marks!

1

Wrong K-Map Column Order

❌ COMMON ERROR

Writing columns as 00, 01, 10, 11 instead of Gray Code 00, 01, 11, 10

✅ HOW TO FIX

Always label your K-Map axes FIRST before filling values. Write "00 01 11 10" and repeat it like a mantra.

2

Groups Not Power of 2

❌ COMMON ERROR

Making a group of 3, 5, or 6 cells instead of valid sizes: 1, 2, 4, 8, 16.

✅ HOW TO FIX

If you have 3 cells, make a group of 4 by including an extra 1 or don't-care. Only 1, 2, 4, 8, 16 are valid!

3

Leaving 1s Uncovered

❌ COMMON ERROR

Forgetting to include some 1s in any group — they remain uncovered.

✅ HOW TO FIX

After completing groups, tick off every 1 in the K-Map and verify each appears in at least one group.

4

Not Maximizing Group Size

❌ COMMON ERROR

Using small groups (pairs) when a larger valid group (quad/octet) exists.

✅ HOW TO FIX

Always try to make each group as big as possible FIRST, then handle remaining 1s with smaller groups.

5

Forgetting Wrap-Around

❌ COMMON ERROR

Not seeing that top row and bottom row, or left and right edges, can form a group.

✅ HOW TO FIX

Think of the K-Map as a cylinder/torus (donut). The edges touch! Check for wrap-around groups explicitly.

6

Wrong Variable Elimination

❌ COMMON ERROR

Keeping a variable that CHANGES in the group, or eliminating one that stays constant.

✅ HOW TO FIX

For each group: list all variable values for all cells. If any variable changes → CROSS IT OUT. If constant → KEEP IT.

7

X-Only Groups (Don't-Care)

❌ COMMON ERROR

Making groups that contain ONLY X (don't-care) cells with no actual 1s.

✅ HOW TO FIX

Don't-cares are HELPERS, not requirements. Every group must contain at least one actual minterm.

8

Grouping 0s Instead of 1s for SOP

❌ COMMON ERROR

Grouping the 0s in the K-Map when asked for SOP (minimum sum of products).

✅ HOW TO FIX

For SOP: group 1s. For POS: group 0s. Always confirm which form the question is asking for!

§ 4.10

Exam Practice Questions — with Solutions

📚 How to Use This Section

First: Try each question yourself before looking at the solution.
Then: Compare your answer with the worked solution.
Focus: Understand WHY each step is done, not just WHAT is done.
Repeat: Do each problem at least twice without notes before your exam.

Question 1 — Boolean Algebra Proof

⭐ Easy

Prove using Boolean algebra that A + A'B = A + B

▶ WORKED SOLUTION

Step	Expression	Rule Applied
Start	`A + A'B`	Given
Step 1	`(A + A')(A + B)`	Distributive: X+YZ = (X+Y)(X+Z)
Step 2	`(1)(A + B)`	Complement: A + A' = 1
Step 3	`A + B ✓`	Identity: 1 × X = X (QED)

Result: A + A'B = A + B (Proved!)

💡 Tip: When proving identities, work on ONE side only and simplify it to match the other side.

Question 2 — De Morgan's Theorem

⭐ Easy

Apply De Morgan's theorem to: (A'B + C'D)'

▶ WORKED SOLUTION

Step	Expression	Rule
Start	`(A'B + C'D)'`	Given
Step 1	`(A'B)' · (C'D)'`	De Morgan's 2nd: (X+Y)' = X'·Y'
Step 2	`(A'' + B')(C'' + D')`	De Morgan's 1st: (XY)' = X'+Y'
Step 3	`(A + B')(C + D')`	Double Complement: A'' = A

Result: (A + B')(C + D')

Question 3 — 3-Variable K-Map

⭐⭐ Medium

Minimize using K-Map: F(A,B,C) = Σm(1,2,3,5,7)

▶ WORKED SOLUTION

Step 1: Fill the K-Map

A \ BC	BC=00	BC=01	BC=11	BC=10
A=0	0	1	1	1
A=1	0	1	1	0

Step 2: Identify groups:

Group	Cells	Variable Analysis	Term
Group 1 (4 cells)	m₁, m₃, m₅, m₇	A changes, B changes, C=1 always → only C constant	`C`
Group 2 (2 cells)	m₂, m₃	A=0 always, B=1 always, C changes → A and B constant	`A'B`

F = C + A'B

✅ Verify: m₁(C=1✓) m₂(A'B✓) m₃(both✓) m₅(C=1✓) m₇(C=1✓) — All 5 minterms covered!

Question 4 — 4-Variable K-Map with Don't-Cares

⭐⭐⭐ Hard

Simplify: F(A,B,C,D) = Σm(0,1,2,4,5,6,8,9,10) + d(3,7,11,15)

▶ WORKED SOLUTION

AB \ CD	CD=00	CD=01	CD=11	CD=10
AB=00	1	1	X	1
AB=01	1	1	X	1
AB=11	0	0	X	0
AB=10	1	1	X	1

Groups:

Group 1 (12 cells + X): All of AB=00, AB=01, AB=10 rows with CD=00, CD=01, CD=10 (and X at CD=11 helps) → D' covers CD=00 and CD=10 across 3 rows
Group 2 (rows AB=00,01,10): Using the 3 rows with B'→ B is 0 for AB=00 and AB=10 (wrap)

F = D' + B'

💡 The don't-cares at CD=11 let us form larger groups. Without them we'd need more terms!

Additional Practice Questions (Self-Study)

Q#	Difficulty	Problem	Hint
Q5	⭐	Prove: `AB + A'C + BC = AB + A'C`	This is the Consensus Theorem. Expand BC = BC(A+A').
Q6	⭐⭐	K-Map: `F = Σm(2,3,6,7,10,11,14,15)`	All minterms have C=1. Group of 8 → Answer: just C!
Q7	⭐⭐	Convert `(A+B)(A+C)(B'+C')` into SOP	Expand brackets. Use Distributive + Absorption Laws. Answer: AC + AB'
Q8	⭐⭐⭐	Implement `F = Σm(0,1,3,6,7)` using only NAND gates	Simplify with K-Map first, then apply De Morgan's to convert AND-OR to NAND-NAND form.

§ 4.11

Quick Reference — Cheat Sheet

Dr. Sohel Rana's final summary — everything you need for your exam in one place!

K-Map Simplification — Complete Process

📋 8-Step K-Map Procedure

Write the truth table or identify the minterms

Draw K-Map with correct GRAY CODE axes (00, 01, 11, 10)

Fill in 1s for minterms, 0s for maxterms, X for don't-cares

Circle groups — must be power-of-2 sized, maximum size first

Allow wrap-around and overlaps for larger groups

For each group: CHANGE = CANCEL, CONSTANT = KEEP

OR all group terms together for the final SOP expression

Verify: every 1 is covered by at least one group

Boolean Laws Quick Ref

Identity: A·1=A, A+0=A

Null: A·0=0, A+1=1

Idempotent: A·A=A, A+A=A

Complement: A·A'=0, A+A'=1

Absorption: A+AB=A

De Morgan: (AB)'=A'+B'

Valid Group Sizes

1 2 4 8 16

If your group size is NOT in this list, it's WRONG. Always powers of 2 only.

K-Map Sizes

2 variables → 4 cells (2×2)

3 variables → 8 cells (2×4)

4 variables → 16 cells (4×4)

5 variables → 32 cells (4×8)

6 variables → 64 cells (8×8)

Gates Summary

AND: output 1 when ALL inputs = 1

OR: output 1 when ANY input = 1

NOT: inverts the input

NAND & NOR: Universal Gates

XOR: output 1 when inputs DIFFER

🧠 Dr. Sohel Rana's Top 5 Memory Tricks

🔢

Gray Code Order

"Go On, I Love You"

G=00 O=01 I=11 L=10

⚗️

De Morgan's Theorem

Break, Complement, Change

BREAK bar → COMPLEMENT vars → CHANGE operator

📏

Valid Group Sizes

Powers of 2 ONLY — if not in the list, it's wrong!

1 2 4 8 16 32 64

🎯

Variable Elimination

Simple rule — no exceptions!

CHANGE = CANCEL | CONSTANT = KEEP

📊

SOP vs POS

Remember which to group!

SOP → group 1s | POS → group 0s