Overview
A Karnaugh map (K-map) is a visual method for simplifying boolean expressions developed by Maurice Karnaugh in 1953. It arranges a truth table into a two-dimensional grid where adjacent cells differ by exactly one variable (Gray code ordering). This spatial arrangement makes it easy to spot groups of 1-cells that correspond to simplified product terms.
K-maps are the most widely taught method for boolean minimisation in digital logic courses. For expressions with 2, 3, or 4 variables, K-maps are faster and less error-prone than algebraic simplification. For 5 or 6 variables, two-map (2×K-map) techniques extend the approach.
The key insight: adjacent cells in a K-map (horizontally, vertically, or wrapping around edges) that all contain 1s can be grouped together. Larger groups simplify to fewer literals. Groups must be powers of 2 in size (1, 2, 4, 8, 16...).
How It Works
To solve a K-map: 1. Convert your truth table to a K-map by placing each output value in the appropriate cell. Cell coordinates use Gray code: for 2 variables (AB), columns are 00, 01, 11, 10. 2. Identify all 1-cells. These are the minterms to be covered. 3. Group adjacent 1-cells into the largest possible power-of-2 groups. Groups can wrap around edges. A cell can belong to multiple groups. 4. For each group, identify which variables are constant across all cells in the group — these form one product term. Variables that change within the group are eliminated. 5. OR all product terms together to get the minimised SOP expression.
The resulting expression uses fewer gates than the unsimplified version. Always check your result against the original truth table.
Real-World Applications
K-maps minimise the gate count for combinational circuits before implementation, reducing chip area and power.
K-map problems are standard in digital logic exams at every level, from introductory to advanced courses.
Programmable logic arrays use minimised SOP expressions to configure internal AND-OR planes efficiently.
K-maps reveal static hazards (brief glitches) in combinational circuits by identifying groups that don't share a common cover.
Next-state and output logic for FSMs is minimised using K-maps to reduce the flip-flop and gate requirements.
Try It in the Interactive Simulator
Build Karnaugh Map Solver circuits in real time — drag gates, connect wires, toggle inputs, and see outputs update instantly.
Frequently Asked Questions
- What is a Karnaugh map?
A Karnaugh map (K-map) is a grid-based method for simplifying boolean expressions. It arranges truth table values in a 2D grid where adjacent cells differ by one variable, making it easy to identify simplification groups.
- How do you read a K-map?
The rows and columns are labelled with variable combinations in Gray code order (00, 01, 11, 10). Each cell holds the output value for that input combination. Groups of adjacent 1-cells correspond to simplified product terms.
- What are the rules for grouping in a K-map?
Groups must be rectangular (or L-shapes are NOT allowed), contain only 1s, have a size that is a power of 2 (1,2,4,8,16...), and be as large as possible. Groups can wrap around edges. Overlapping groups are allowed and encouraged for maximal simplification.
- What is a don't-care condition in a K-map?
Don't-care cells (marked X) represent input combinations that can never occur or whose output doesn't matter. You can treat X as either 0 or 1 — choose whichever creates larger groups for better simplification.
- How many variables can a K-map handle?
K-maps work well for 2, 3, and 4 variables. For 5-6 variables, paired K-maps or a computer-based Quine-McCluskey algorithm is more practical.