Karnaugh Maps

Overview

Recall questions on Karnaugh maps for two, three and four variables, Gray code labelling, filling a map, grouping rules, reading terms from groups, wrapping edges and corners, worked simplifications, and the advantages and limits of the method.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a Karnaugh map, and what is it for?

   Model answer

   A grid representation of a truth table, arranged so that logically adjacent combinations of inputs sit in physically adjacent cells. Each cell holds the output for one combination of inputs. It is used to simplify a Boolean expression by grouping the 1s: the groupings read off directly as a minimal sum-of-products expression, giving the same answer as algebraic manipulation but with far less chance of missing a step.

2. 2

   Describe the layout of a two-variable and a three-variable Karnaugh map.

   Model answer

   A two-variable map is a 2 by 2 grid: the rows are labelled A = 0 and A = 1, the columns B = 0 and B = 1, giving four cells for the four input combinations. A three-variable map is a 2 by 4 grid: the two rows are labelled with the single variable A as 0 then 1, and the four columns are labelled with the pair BC in the order 00, 01, 11, 10.

3. 3

   Describe the layout of a four-variable Karnaugh map.

   Model answer

   It is a 4 by 4 grid of sixteen cells, one for each input combination. The four rows are labelled with the pair AB in the order 00, 01, 11, 10 down the side, and the four columns with the pair CD in the same order 00, 01, 11, 10 along the top. Each cell is identified by reading its row label and then its column label, so the cell in row 01 and column 10 stands for A=0, B=1, C=1, D=0.

4. 4

   Why are the labels ordered 00, 01, 11, 10 rather than 00, 01, 10, 11?

   Model answer

   Because that ordering is Gray code, in which only one bit changes between any two neighbouring labels. It means neighbouring cells in the map differ in exactly one variable, so a pair of adjacent 1s must be a case where that one variable can take either value while the output stays 1 - which is precisely the condition for eliminating it. The ordering is what makes the grouping trick work at all.

5. 5

   What would go wrong if you labelled a Karnaugh map in plain binary counting order?

   Model answer

   The columns 01 and 10 would then be neighbours, and those two combinations differ in both variables, not one. Grouping them would be invalid, because there is no single variable you could cancel, and any term read off such a group would be wrong. Meanwhile genuinely adjacent combinations would be separated, so real simplifications would be invisible. Getting the Gray code labelling right is the first thing to check on any map.

6. 6

   How do you fill in a Karnaugh map?

   Model answer

   Take each row of the truth table where the output is 1, or each product term of the sum-of-products expression, and find the cell whose row and column labels match that combination of input values. Write a 1 in it. All remaining cells hold 0. If a product term omits a variable, it corresponds to more than one cell - for example A.B in a four-variable map fills all four cells of the AB = 11 row - and every one of them gets a 1.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.