A Karnaugh map is a graphical representation of a Boolean function that makes opportunities for logical simplification visible as groups of adjacent cells. Each cell represents one combination of binary input values, and its entry records the corresponding output. The cells are arranged so that neighboring positions differ in exactly one input variable. Grouping suitable neighboring cells therefore identifies variables that can be eliminated from an expression without changing its specified behavior.
Introduced by Maurice Karnaugh in 1953, the method became a standard technique for designing small digital logic circuits. It translates relationships that can be difficult to recognize in an algebraic expression or an ordinary truth table into spatial patterns. Its principal uses are minimizing two-level logic, exploiting incompletely specified inputs, and identifying certain timing hazards. Karnaugh maps are especially practical for functions of two to four variables; larger maps remain possible, but their size and increasingly complicated adjacency relationships limit manual use.
Historical development and place in switching theory
Karnaugh maps emerged from the application of symbolic logic to electrical switching circuits. In this setting, a variable can represent whether a switch is open or closed, whether a relay is energized, or whether an electrical signal has logical value 0 or 1. Series and parallel connections can implement operations corresponding to AND and OR, while complementary contacts or inverting devices implement NOT. Simplifying a logical expression could therefore reduce the number of components or connections required for a circuit.
An important foundation was Claude Shannon’s 1938 paper “A Symbolic Analysis of Relay and Switching Circuits,” which systematically connected switching networks with Boolean algebra. Once a circuit’s behavior had been expressed symbolically, algebraic identities could be used to find an equivalent implementation. The difficulty was not establishing that simplification was possible, but making the process systematic and manageable. An expression involving several variables may admit many different transformations, and a locally useful simplification does not necessarily reveal a globally economical circuit.
Edward W. Veitch presented a graphical simplification method in 1952. Maurice Karnaugh, working at Bell Telephone Laboratories, published “The Map Method for Synthesis of Combinational Logic Circuits” in 1953. Karnaugh’s arrangement made adjacency among combinations of input values particularly convenient for visual grouping. The names Veitch diagram, Karnaugh map, and Veitch–Karnaugh map reflect this closely connected development, although historical diagrams and later textbook conventions do not always use identical layouts.
The map method developed alongside tabular approaches to logic minimization. Work by Willard V. Quine in the early 1950s and Edward J. McCluskey in 1956 led to the Quine–McCluskey algorithm, which expresses the same underlying combination and covering operations in a form suitable for systematic computation. Karnaugh maps emphasize visual recognition; tabular methods explicitly enumerate combinable terms and candidate covers. Both depend on the fact that a variable can disappear when two otherwise identical terms contain it in complementary forms.
Karnaugh maps became prominent in the teaching and practice of combinational circuit design because they connect several levels of description: a specification, a truth table, a simplified expression, and a gate network. Their historical importance does not mean that large modern circuits are normally minimized by drawing maps. Automated synthesis has largely displaced manual mapping for substantial designs. The method nevertheless remains useful for small control functions, checking derived expressions, understanding redundancy, and explaining why some Boolean transformations preserve logical behavior but alter timing behavior.
Boolean functions, cells, and coordinate conventions
A Boolean function of inputs is a function
Its truth table contains input combinations. A Karnaugh map contains exactly the same information, but rearranges the combinations to expose relationships among them. A two-variable map has four cells, a three-variable map has eight, and a four-variable map has sixteen. Unlike an ordinary numerical matrix, the arrangement is chosen for logical adjacency rather than for arithmetic operations on rows and columns.
For a four-variable function , a common convention assigns to the rows and to the columns. Each axis is labeled in the order , rather than ordinary binary counting order. This is a Gray-code sequence: consecutive labels differ in only one bit, including the last and first labels when the sequence is treated cyclically. Reversing an axis or interchanging variables produces an equally valid map, provided all cell labels and adjacency relationships are interpreted consistently.
Each fully specified input combination corresponds to a minterm, a conjunction containing every variable exactly once, either complemented or uncomplemented. With as the most significant bit, the input has decimal index 10 and minterm
Here a prime denotes logical complementation, juxtaposition denotes AND, and denotes OR. A minterm is 1 at exactly one input combination. Consequently, a function can be specified by listing the indices of the cells containing 1:
This notation is a compact specification of the function, not yet a simplified implementation. The corresponding map is:
| 00 | 01 | 11 | 10 | |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 |
| 01 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 1 | 1 |
| 10 | 1 | 1 | 1 | 1 |
A literal is a variable or its complement. A product term is an AND of literals, and a sum-of-products expression is an OR of product terms. The canonical sum of minterms uses literals in every term. Map simplification replaces collections of minterms with broader product terms containing fewer literals. Complementary terminology applies to maxterms, which are OR terms that equal 0 at one specified input combination.
The input ordering must remain fixed throughout a calculation. A cell number depends on the declared order of the variables, whereas its physical position depends on the chosen map layout. Confusing these conventions can produce a plausible-looking expression for the wrong function. Explicit axis labels are therefore part of the mathematical specification of a map, not merely drawing aids.
Gray-code adjacency and Boolean geometry
The essential relation in a Karnaugh map is logical adjacency: two input combinations are adjacent when they differ in exactly one coordinate. In terms of Hamming distance, adjacent combinations have distance 1. Thus and are adjacent because only changes, while and are not adjacent because two coordinates change. The map’s layout makes many of these relationships appear as shared cell edges.
Ordinary binary ordering would obscure the relationship. For example, the consecutive binary labels and differ in both positions. Gray ordering replaces that transition with to , followed by to , so that each step changes only one bit. It also makes adjacent to across the edge of the drawing. The left and right boundaries of a standard four-variable map are therefore adjacent, as are its top and bottom boundaries.
This wraparound convention has several consequences. The four corner cells form a valid four-cell group: the first and last rows are adjacent, and the first and last columns are adjacent. A group can also consist of two cells at opposite ends of a row or column. Diagonally touching cells, however, are not adjacent merely because their corners meet. In a standard two-dimensional map, a diagonal move normally changes one row variable and one column variable.
A more general description comes from graph theory. The input combinations are the vertices of the -dimensional hypercube graph, and edges join combinations differing in one bit. A product term that fixes variables and leaves the other variables free identifies a subcube containing vertices. Karnaugh-map groups are graphical representations of these subcubes. This explains both the allowed group sizes and the algebraic meaning of grouping.
For four variables, identifying opposite boundaries gives the familiar grid a toroidal adjacency structure, a connection with topology. This description concerns which cells are neighbors, not a claim that the function itself has a physical doughnut shape. For more variables, a single rectangular display becomes less faithful to the full adjacency structure. Five-variable maps are commonly drawn as two corresponding four-variable panels, and six-variable maps as four panels arranged in Gray order.
The subcube interpretation is more general than the rule “draw rectangles.” An acceptable group must contain every combination of its free variables, while all other variables remain fixed. In a standard map with at most four variables, permitted groups appear as power-of-two rectangles, including wrapped rectangles. In larger maps, a visually rectangular region is not automatically a valid Boolean subcube; the actual bit labels determine whether the proposed grouping is legitimate.
Grouping rules and algebraic elimination
For a sum-of-products simplification, groups are formed from cells containing 1. Each group must contain cells and must correspond to a Boolean subcube. A group cannot contain a specified 0. Every required 1 must be covered by at least one selected group, but groups may overlap. A cell containing 1 may therefore participate in several terms of the final expression.
The algebraic basis is the complement identity , together with distributivity. Two adjacent minterms that differ only in combine as
The value of is irrelevant inside the combined region. A four-cell group eliminates two variables, an eight-cell group eliminates three, and a group containing cells eliminates variables. For an -variable function, its corresponding product term therefore contains literals.
To read a term from a group, retain only variables that stay constant throughout it. A variable fixed at 1 appears uncomplemented, and one fixed at 0 appears complemented. A variable that changes is omitted. For example, a four-cell region with and , while and vary through all possibilities, represents . Its location or orientation on the page is secondary to those constant coordinate values.
Larger groups yield terms with fewer literals, but this does not justify indiscriminately selecting every large group. A large group may cover only cells already covered by other necessary terms, adding hardware without completing the specification. Conversely, overlapping groups can be indispensable. The task is to choose a collection whose union covers all required 1s at an acceptable cost, rather than to divide the map into nonoverlapping regions.
A group that cannot be enlarged without including a forbidden cell corresponds to a prime implicant. More generally, an implicant is a product term whose 1-set lies within the function’s 1-set. Any nonprime implicant can be enlarged to a prime implicant, removing literals without losing covered 1s. Thus, for ordinary two-level term-and-literal minimization, attention can be restricted to prime implicants.
Several boundary cases clarify the rules. An isolated 1 produces a minterm containing all variables. If every cell is 1, the entire map forms one group and the function is the constant 1, interpreted as an empty product. If no cell is 1, the function is the constant 0 and no product terms are required. Groups of three or six cells do not directly produce single product terms, even if the cells form an apparently convenient shape.
Minimum covers and a worked four-variable example
Grouping identifies candidate terms; selecting terms is a separate optimization problem. An essential prime implicant covers at least one required 1 that no other prime implicant covers. Such a term must appear in any cover restricted to prime implicants. After essential prime implicants are selected, some functions still contain uncovered cells that can be covered in alternative ways. The remaining choice determines whether a proposed expression is genuinely minimum.
Consider the four-variable map introduced earlier:
The top and bottom rows together form an eight-cell wrapped group. Their row labels are and , so throughout while vary. This group contributes . A second group contains cells , occupying rows and columns . Here and remain fixed, yielding .
The resulting expression is
The groups overlap at cells 10 and 11, which is entirely permissible. The first group is essential because, for example, cell 0 belongs to no other prime implicant. The second is essential because cell 14 belongs to no other prime implicant. The expression contains two product terms and three literals, compared with ten four-literal minterms in the canonical expression. A direct truth-table check confirms that accounts for all inputs with , while supplies the remaining required inputs.
Not every function has such a forced cover. For a three-variable example,
the six 1-cells form a cycle in which each can be paired with two neighbors. There are no four-cell implicants and no essential prime implicants. Two different minimum expressions are
and
Each uses three two-literal terms. This illustrates why “take the largest groups” does not uniquely determine an answer: all six candidate groups have the same size, and an appropriate subset must still be selected.
The remaining selection problem can be represented by a prime-implicant chart. Columns represent required minterms, rows represent prime implicants, and marks indicate coverage. Choosing rows to cover every column is a form of the set cover problem. Petrick’s method expresses the alternatives as a Boolean product of sums and expands or simplifies it to identify covers.
The meaning of “minimum” must also be specified. A common textbook convention minimizes the number of product terms first and the total number of literals second. Other objectives may assign costs to gate inputs, complemented signals, or particular library cells. A map exposes valid logical reductions, but the chosen cost function determines which equivalent expression is preferred.
Product-of-sums forms and incompletely specified functions
A Karnaugh map can be simplified by grouping 0s rather than 1s. The result is a product-of-sums expression: an AND of OR terms. This is the dual of sum-of-products minimization. A zero group identifies a region in which the corresponding sum term must equal 0. Variables fixed at 0 appear uncomplemented in that sum term, while variables fixed at 1 appear complemented—the reverse of the rule for a 1-group.
For the four-variable example, the zero cells are . The full row is a four-cell zero group, giving the sum term . A second four-cell group occupies rows and columns . Throughout this region and , giving . Therefore,
The identity verifies its equivalence to . The two forms may have different implementation costs even though both are compact.
The duality can also be understood through De Morgan’s laws. Grouping the zeros of is equivalent to grouping the ones of . Complementing a sum-of-products expression for then gives a product-of-sums expression for . This provides an algebraic check on the polarity of each literal and is particularly useful when a circuit is to be implemented with NOR rather than NAND structures.
Many practical specifications leave some input combinations unspecified. Such cells are marked , a dash, or another declared symbol and are called don’t-care conditions. They may represent input combinations excluded by an external encoding, unused states, or outputs that are irrelevant under a stated condition. Formally, the input space is partitioned into an on-set, an off-set, and a don’t-care set. A valid implementation must output 1 on the on-set and 0 on the off-set, but may choose either value on the don’t-care set.
For example, let
The four cells all have . Treating cell 5 as 1 permits a four-cell group and gives . Without that don’t-care permission, cells 1 and 3 yield , while cells 3 and 7 yield , producing . Don’t-care cells need not all be used, and their selected values need not be consistent between independently derived alternative implementations.
An unspecified value is not automatically a physically impossible value. An unused state may become reachable during startup or after a fault, and an input combination excluded by a protocol may occur transiently. Simplifying with don’t-cares therefore produces behavior outside the specified domain that is logically permitted but not otherwise constrained. The distinction belongs to the specification: a Karnaugh map cannot establish whether an assumed exclusion is valid for the surrounding system.
Timing hazards and redundant coverage
Boolean equivalence describes steady-state input-output behavior. It does not imply identical behavior during transitions, because physical gates have nonzero and unequal propagation delays. A circuit may briefly produce the wrong output even though its expression is logically correct before and after an input change. A logic hazard is a structural susceptibility to such an unwanted transient; a realized transient pulse is commonly called a glitch.
Karnaugh maps provide a particularly clear test for static hazards under a single-input-change model. A static-1 hazard occurs when the output should remain 1 but may briefly fall to 0. In a two-level AND–OR implementation, the risk arises when adjacent 1-cells are covered by different product terms and no implemented term covers both cells. The changing input can cause the old active term to switch off before the new one switches on.
A standard example is
With , changing should leave . Yet one product term depends on and the other on its complement. Because the inverter and gate paths may have different delays, both products can momentarily be 0. On the map, the two states and are adjacent, but the displayed two-term cover does not contain a common group spanning their shared edge.
Adding the term covers that transition:
The added term remains 1 while changes and . It does not alter the Boolean function because the consensus theorem gives
Thus a term that is redundant for steady-state logic can be necessary for a hazard-free realization under the assumed gate model. Minimization and hazard removal can impose opposing requirements.
For a two-level sum-of-products network, covering every adjacency between required 1-cells with at least one common product term removes static-1 hazards for single-input transitions under the usual delay assumptions. The dual rule applies to static-0 hazards in two-level product-of-sums networks: adjacent zero states should share a zero group corresponding to an implemented sum term. A minimal expression may already meet these conditions, or additional redundant terms may be required.
The guarantee is limited. Multiple inputs changing together can pass through intermediate states whose outputs differ from the intended endpoint behavior. Multilevel networks can exhibit dynamic hazards, in which the output changes more than once when only one final transition is expected. Map-based static coverage does not by itself solve these problems or model analog effects, pulse filtering, clock-domain crossings, and loading. In asynchronous circuits, where behavior may depend directly on transitions rather than on a clocked sampling instant, these distinctions are especially consequential.
Circuit realization, computational limits, and modern use
A sum-of-products expression naturally corresponds to a two-level AND–OR circuit: one AND gate for each product term, followed by an OR gate combining them. A product-of-sums expression similarly corresponds to OR gates feeding an AND gate. Inversions may require additional circuitry unless complementary signals are already available. Through De Morgan transformations, sum-of-products forms can also map naturally to NAND–NAND implementations, while product-of-sums forms can map to NOR–NOR implementations.
For , a direct realization uses an inverter on , an AND operation on , and an OR operation combining the results. But this logical description is not a complete physical design. Gate libraries differ in available fan-in, drive strength, delay, area, and power characteristics. A compound gate may implement an AND–OR function more efficiently than separate gates, while a factored expression may reduce duplicated logic. Consequently, the smallest two-level expression need not yield the smallest or fastest circuit.
The distinction is even clearer in programmable technologies. A programmable logic array can share product terms among several outputs, so minimizing each output separately may miss a cheaper joint implementation. A lookup table in a field-programmable gate array can implement any function within its input capacity; reducing the literal count of a function already fitting one table does not necessarily reduce the number of tables. Map simplification remains logically valid, but its physical benefit depends on the target architecture.
The principal scaling problem is exponential growth. An -variable map has cells: 16 for four variables, 64 for six, 256 for eight, and 1,024 for ten. Larger displays require cross-panel relationships that are harder to track than ordinary neighboring edges. The number of candidate implicants and alternative covers can also grow sharply. The map does not remove the combinatorial difficulty of exact minimization; it makes small instances accessible to human pattern recognition.
Automated methods address different parts of this problem. Quine–McCluskey systematically generates prime implicants and then solves a covering problem, but can require large intermediate representations. The Espresso logic minimizer, developed in the 1980s, uses heuristic operations on implicant covers to obtain compact two-level implementations without generally guaranteeing a global minimum. Modern logic synthesis also uses multilevel factoring, decomposition, technology mapping, timing analysis, and other representations rather than relying solely on two-level minimization.
Functions with strong exclusive-OR structure illustrate another limitation. The parity function on variables is 1 when an odd number of inputs are 1. Changing any one input reverses its output, so every 1-cell is isolated from all other 1-cells under Karnaugh adjacency. Its ordinary sum-of-products form therefore requires full minterms, yet a chain of two-input XOR gates computes it compactly. A map correctly identifies the lack of ordinary product-term grouping, but the appropriate implementation uses a different operator structure.