15.2 Boolean Algebra and Logic Circuits – Karnaugh Maps (K‑maps)
Learning Objective
Demonstrate a clear understanding of Karnaugh maps and how they are used to simplify Boolean expressions for logic circuit design.
Why Karnaugh Maps?
K‑maps provide a visual method for minimising Boolean functions without resorting to algebraic manipulation. They are especially useful for:
Identifying groups of 1’s (or 0’s) that correspond to product‑terms (or sum‑terms).
Reducing the number of literals and gates in a circuit.
Handling “don’t‑care” conditions efficiently.
Basic Concepts
Cell layout – each cell represents a unique combination of variable states.
Adjacency – cells that differ in only one variable are adjacent (including wrap‑around).
Grouping – groups must contain 1, 2, 4, 8 … cells (powers of two).
Don’t‑care cells – may be used in groups if it leads to a larger simplification.
Steps to Simplify a Boolean Function Using a K‑map
Write the truth table for the function and note the output column (1’s, 0’s, and X for don’t‑care).
Choose the appropriate K‑map size:
2 variables → 2×2 grid
3 variables → 2×4 grid
4 variables → 4×4 grid
More variables → combine multiple 4‑variable maps.
Transfer the output values into the K‑map cells, preserving the Gray‑code ordering of columns and rows.
Identify the largest possible groups of 1’s (or 0’s for POS) including don’t‑care cells if beneficial.
For each group, write the product term (SOP) or sum term (POS) by omitting the variables that change within the group.
Combine all terms with logical OR (for SOP) or AND (for POS) to obtain the minimal expression.
Example: 4‑Variable Function
Given the truth table below, minimise the function \$F(A,B,C,D)\$.
Decimal
\$A\$
\$B\$
\$C\$
\$D\$
\$F\$
0
0
0
0
0
0
1
0
0
0
1
1
2
0
0
1
0
1
3
0
0
1
1
0
4
0
1
0
0
1
5
0
1
0
1
1
6
0
1
1
0
0
7
0
1
1
1
0
8
1
0
0
0
1
9
1
0
0
1
0
10
1
0
1
0
1
11
1
0
1
1
0
12
1
1
0
0
0
13
1
1
0
1
1
14
1
1
1
0
0
15
1
1
1
1
0
Transfer the 1’s into a 4×4 K‑map (variables \$AB\$ for rows, \$CD\$ for columns, both in Gray code order).
Suggested diagram: 4‑variable K‑map with cells filled according to the table above.
After grouping, the following prime implicants are identified:
Group 1 (four 1’s covering \$A' C\$): \$A' C\$
Group 2 (four 1’s covering \$B' D\$): \$B' D\$
Group 3 (two 1’s covering \$A D'\$): \$A D'\$
The minimal sum‑of‑products (SOP) expression is therefore
\$F = A' C \;+\; B' D \;+\; A D'\$
Don’t‑Care Conditions
When a minterm is “X” (don’t‑care), it can be treated as either 0 or 1 to achieve larger groups. Example:
Suppose \$F\$ has don’t‑care at minterms 3 and 12. Including them in groups may reduce the number of literals.
Always verify that the chosen grouping does not change the required output for the defined minterms.
Common Pitfalls
Incorrect Gray‑code ordering – leads to wrong adjacency.
Forgetting wrap‑around adjacency (edges of the map are adjacent).
Using a smaller group when a larger one is possible – results in a non‑minimal expression.
Including a don’t‑care cell in a group that forces an unwanted 1 in the final truth table.
Practice Questions
Construct a 3‑variable K‑map for \$G(A,B,C)=\Sigma m(1,3,5,7)\$ and obtain the minimal SOP.
Given \$H(A,B,C,D)=\Pi M(0,2,5,7,8,10,13,15)\$, draw the K‑map, treat the maxterms as 0’s, and find the minimal POS.
For the function in the example above, assume minterms 9 and 14 are don’t‑care. Redraw the K‑map and determine if a simpler expression than \$F = A' C + B' D + A D'\$ is possible.
Summary
Karnaugh maps translate truth‑table data into a spatial format that makes the identification of common literals straightforward. Mastery of K‑maps enables rapid minimisation of Boolean functions, a skill essential for designing efficient logic circuits in the Cambridge A‑Level Computer Science syllabus.