Karnaugh Maps and Logic Minimisation

A Karnaugh map (K-map) is a visual way to minimise a Boolean function of up to four or five variables without grinding through algebra. It lays the truth table out in a grid arranged in Gray-code order, so adjacent cells differ in exactly one variable — and adjacent 1s can be grouped to eliminate that variable.

How grouping works

Fill the map with the output for each input combination. Then circle the 1s in rectangular groups whose size is a power of two (1, 2, 4, 8…), making each group as large as possible. Every group becomes one product term; a variable that changes within a group drops out of that term. Overlap is allowed and often helpful; groups may wrap around the edges because the first and last columns/rows are also Gray-adjacent.

For the function below (1 where the 2-bit input AB has an odd number of 1s — i.e. XOR), the two single-cell diagonal groups cannot merge, confirming XOR does not simplify — it genuinely needs both terms A·B' + A'·B:

        B=0   B=1
A=0 |   0  |   1  |
A=1 |   1  |   0  |     ->  F = A'B + AB'  (= A XOR B)

K-maps also expose don’t-care conditions (inputs that can never occur): mark them X and include them in a group only when doing so makes the group bigger. The result is the same minimal sum-of-products a synthesis tool would compute — the K-map just makes the reasoning visible for small functions.