Boolean Algebra and K-Map Simplification with Worked Examples

Boolean algebra is the mathematics of variables that can only be 0 or 1. Every logic circuit implements a Boolean expression, and a simpler expression means fewer gates, less area, lower power and often a faster circuit. In this tutorial you will learn the laws that let you simplify expressions by hand, the standard SOP and POS forms, and the Karnaugh map (K-map) method that makes minimisation of up to four variables almost mechanical. Each step is shown with a worked example you can verify with a truth table.

Boolean Laws You Will Use Constantly

In the notation below, A' means NOT A, a dot or juxtaposition means AND, and + means OR. Most laws come in dual pairs: swap AND with OR and 0 with 1 and the law still holds.

Law	AND form	OR form
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(A + B) = A	A + AB = A
Distributive	A(B + C) = AB + AC	A + BC = (A + B)(A + C)
De Morgan	(AB)' = A' + B'	(A + B)' = A'B'
Consensus	AB + A'C + BC = AB + A'C	(A + B)(A' + C)(B + C) = (A + B)(A' + C)

The second distributive law, A + BC = (A + B)(A + C), has no equivalent in ordinary algebra and surprises many students. Verify it with a truth table once and you will trust it. De Morgan's theorem is the most important of all: it lets you convert between AND and OR forms and is the basis for building any circuit from only NAND or only NOR gates.

Worked algebraic simplification

F = AB + A(B + C) + B(B + C)
  = AB + AB + AC + BB + BC       (distribute)
  = AB + AC + B + BC             (idempotent: AB + AB = AB, BB = B)
  = B + AC                       (absorption: B + AB = B, B + BC = B)

Result: 2 gates (one AND, one OR) instead of 6.

SOP, POS, Minterms and Maxterms

A minterm is an AND term containing every variable once, true or complemented, and it is 1 for exactly one row of the truth table. For three variables, minterm m5 is AB'C because 101 in binary is 5. A Sum of Products (SOP) is an OR of minterms and is written compactly as F = Σm(...). A maxterm is an OR term that is 0 for exactly one row; M5 is (A' + B + C'). A Product of Sums (POS) is written F = ΠM(...) and lists the rows where F is 0.

The two lists are complementary. If F = Σm(1, 3, 5, 7) for three variables, then F = ΠM(0, 2, 4, 6). SOP maps directly to an AND-OR circuit, which is equivalent to NAND-NAND, while POS maps to OR-AND, equivalent to NOR-NOR.

How a Karnaugh Map Works

A K-map is a truth table redrawn as a grid where neighbouring cells differ in exactly one variable. Rows and columns follow Gray code order (00, 01, 11, 10), not binary order. Because adjacent cells differ by one variable, grouping two adjacent 1s eliminates that variable using A + A' = 1. The map also wraps around: the left edge is adjacent to the right edge and the top to the bottom, so the four corners form one group.

Fill the map with 1s for each minterm, 0s elsewhere, and X for don't-care conditions.
Form groups of 1, 2, 4, 8 or 16 cells, always rectangular and a power of two in size.
Make each group as large as possible, since bigger groups give terms with fewer literals.
Use as few groups as possible while covering every 1. Groups may overlap.
Include an X in a group only when it makes the group larger; never cover an X on its own.
Write each group as a product of the variables that stay constant across it.

Example 1: four variables with corner and centre groups

F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)

          CD=00  01   11   10
AB=00  |   1    0    0    1   |  m0  m1  m3  m2
AB=01  |   0    1    1    0   |  m4  m5  m7  m6
AB=11  |   0    1    1    0   |  m12 m13 m15 m14
AB=10  |   1    0    0    1   |  m8  m9  m11 m10

Group 1: four corners  m0, m2, m8, m10   -> B = 0, D = 0 -> B'D'
Group 2: centre quad   m5, m7, m13, m15  -> B = 1, D = 1 -> BD

F = B'D' + BD   (this is B XNOR D)

Without the map, the canonical SOP has eight 4-literal terms. The minimal form needs one XNOR gate. Noticing that the corners are adjacent is the key step that beginners often miss.

Example 2: using don't-care conditions

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

          CD=00  01   11   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   |

Column CD=11 (m3, m7, m15, m11)        -> CD
Top row AB=00 (m0, m1, m3, m2) using X  -> A'B'

F = CD + A'B'

Don't-cares arise when certain input combinations can never occur, for example BCD inputs 1010 to 1111. Here the X cells at m0 and m2 let m1 join a quad instead of a pair. An equally minimal answer is F = CD + A'D, using m5 instead of m0 and m2, which shows that a minimal expression is not always unique.

Common Mistakes

Labelling rows or columns in binary order (00, 01, 10, 11) instead of Gray order, which breaks adjacency.
Forming groups of three or six cells. Group sizes must be powers of two.
Missing wrap-around groups along the edges and corners.
Adding a group that only covers 1s already covered by other groups, producing a redundant term.
Writing a POS answer by grouping 1s. For POS, group the 0s and write complemented sum terms.

Summary

Boolean laws, especially absorption and De Morgan's theorem, let you simplify small expressions algebraically. For anything with three or four variables, the K-map is faster and less error-prone: fill in the minterms in Gray-code order, form the largest power-of-two groups including wrap-around, and use don't-cares to grow groups. Beyond five or six variables the map becomes awkward, and tools use the Quine-McCluskey method or heuristic minimisers such as Espresso. Always check your final answer against the original truth table for at least a few rows.