Karnaugh Map Solver

Minimal expressions

Each outlined group is a block of 1, 2, 4, 8 or 16 cells whose variables that change drop out of the term. Groups may use X cells and may wrap round the edges.

Quine–McCluskey working

For the sum of products (the 1s and X cells)

For the product of sums (the 0s and X cells)

The product of sums is found by minimising the opposite function (where the output is 0) and then applying De Morgan's laws to each term.

How to Use the Karnaugh Map Solver

1. 1. Choose the number of variables. The variables are A, B, C and D, with A as the leading (most significant) bit, so for three variables ABC = 101 is minterm 5.
2. 2. Enter the function. List the minterms (the outputs that are 1) and, optionally, the don't-cares; or click each output of the truth table to cycle 0, 1 and X; or type a formula such as A′B + AC.
3. 3. Read the two answers. The minimal sum of products (SOP) groups the 1s; the minimal product of sums (POS) groups the 0s. Both are shown with the number of literals.
4. 4. Check the maps and the steps. Each map has its groups outlined in colour. The Quine–McCluskey section shows how the groups were found and proved minimal.

How a Karnaugh Map Works

A Karnaugh map is a truth table folded into a grid so that cells next to each other differ in exactly one variable. To make that true, the rows and columns are numbered in Gray code — 00, 01, 11, 10 — rather than in counting order. Two adjacent 1s can then be merged: the variable that changes drops out of the product term. The map wraps around, so the first and last rows are neighbours, the first and last columns are neighbours, and the four corners of a four-variable map form one group. Maurice Karnaugh introduced the method in 1953 as a refinement of Edward Veitch's 1952 chart.

• Groups are rectangles whose size is a power of two: 1, 2, 4, 8 or 16 cells.
• Make each group as large as possible, and use as few groups as will cover every 1.
• Groups may overlap and may wrap around the edges.
• A don't-care (X) may be used inside a group if that makes the group larger, and may be ignored otherwise.

Worked Example With Don't-Cares

Take four variables with required minterms 1, 3, 7, 11, 15 and don't-cares 0, 2, 5. The group A′B′ covers cells 0, 1, 2 and 3 (using the don't-cares 0 and 2), and the group CD covers 3, 7, 11 and 15. Together they cover every required 1, so the minimal sum of products is A′B′ + CD — four literals. Minterm 1 could equally be covered by A′D, which gives A′D + CD, also four literals; the solver reports the tie.

For the product of sums, group the 0s instead. That gives the inverse function, and De Morgan's laws turn each product term into a sum of the opposite literals. Here it gives (A′ + C)D — three literals.

Corners and Wrap-Around

The function with minterms 0, 2, 8 and 10 has 1s in the four corners of the map. They are all neighbours across the edges, so one group of four covers them, and the whole function is B′D′: B and D are 0 in every one of those cells, while A and C change.

Quine–McCluskey and Petrick's Method

The map is a drawing aid; the Quine–McCluskey algorithm does the same job systematically. It writes each minterm as a bit pattern, merges patterns that differ in one place (the changing place becomes a dash), and repeats until nothing merges. What cannot be merged further is a prime implicant. A chart then shows which required minterms each prime implicant covers. A prime implicant that is the only cover for some minterm is essential and must be in every answer.

Sometimes essentials do not cover everything. Petrick's method (Stanley Petrick, 1956) then writes “each uncovered minterm needs at least one of its implicants” as a product of sums, multiplies it out, removes any term that contains a smaller one, and the smallest products are the minimal covers. The solver picks the one with the fewest terms and then the fewest literals. For minterms 0, 1, 2, 5, 6 and 7 of three variables there is no essential implicant, six prime implicants, and two equally good covers of three terms and six literals each: A′B′ + BC′ + AC and A′C′ + AB + B′C. A minimal expression is therefore not always unique.

Common Mistakes

• Numbering rows in counting order. The axes must be 00, 01, 11, 10, or neighbours stop differing in one variable.
• Grouping three or six cells. Only 1, 2, 4, 8 and 16 work; split other blocks into legal groups.
• Forgetting the wrap-around. Cells at opposite edges are adjacent and can share a group.
• Stopping at the first cover. Use the largest groups, or the expression will have more literals than it needs.
• Treating X as 1 everywhere. Use a don't-care only where it enlarges a group; it never has to be covered.
• Mixing up SOP and POS. SOP groups the 1s and reads the groups as products added together; POS groups the 0s and reads each group, complemented, as a sum.

Frequently Asked Questions

What is a Karnaugh map used for?

It simplifies Boolean expressions by hand, reducing the number of gates in a digital circuit. Cells are arranged so that neighbours differ in one variable, which lets you see which terms can be merged and which variables cancel.

Why does a Karnaugh map use Gray code?

Gray code, 00, 01, 11, 10, changes one bit at a time, so any two adjacent cells differ in exactly one variable. That property is what makes grouping work: two adjacent 1s can be merged because the changing variable cancels.

How do you handle don't-care conditions?

Mark them X. Include an X in a group when it makes the group bigger, and leave it out when it does not help. Don't-cares never have to be covered, and they can be treated as 1 in one group and 0 elsewhere.

How do you get product of sums from a Karnaugh map?

Group the 0s instead of the 1s. That gives the minimal sum of products for the inverse function; applying De Morgan's laws to each product term gives a sum of the opposite literals, and the product of those sums is the POS for the original function.

Why must groups be a power of two?

A group of 2^k cells is a subcube in which k variables take both values, so those k variables cancel and the term has n − k literals. A block of three or six cells is not a subcube, so its cells cannot be described by one product term.

Is the minimal expression unique?

Not always. Cyclic functions can have several covers with the same number of terms and literals, and don't-cares can open alternatives. The solver lists how many equally minimal covers there are and shows one of them.

What if the function has more than four variables?

A flat map becomes hard to read beyond four variables, and this solver stops at four. The Quine–McCluskey method it uses scales to any number of variables, and the Truth Table Generator can help you list minterms from a formula first.