Manipulate Boolean expressions, including the use of Karnaugh maps

Manipulate Boolean expressions, including the use of Karnaugh maps to simplify Boolean expressions.

1.4.3 Boolean Algebra

Boolean Algebra — Note 2 of 5

Candidates should have an understanding that Boolean expressions can be simplified and should have experience of simplifying expressions using Karnaugh maps. Candidates should be able to create, complete and interpret Karnaugh maps to simplify Boolean expressions.

What you need to know

Boolean expressions can often be simplified so that the same logic needs fewer gates. Karnaugh maps (K-maps) provide a visual method of simplifying expressions with up to four variables.

What to know

Rows and columns are labelled in Gray code order (00, 01, 11, 10) so only one bit changes between neighbouring cells.
Step 1: fill the map with the outputs from the truth table or expression.
Step 2: group the 1s into rectangles whose sizes are powers of 2 (1, 2, 4, 8). Groups should be as large as possible and as few as possible.
Step 3: groups can overlap and can wrap around the edges of the map.
Step 4: for each group, keep only the variables that do NOT change within the group; combine the groups with OR.

Key terms

Karnaugh map: A grid showing the output of a Boolean expression for each combination of inputs, arranged so that neighbouring cells differ by only one variable.

Exam technique

Tip:Check your simplified expression by testing a few input combinations against the original truth table.
Mistake:Making groups of 3 or 6. Groups must contain 1, 2, 4, 8 or 16 cells.

Code examples

K-map example: simplifying a 3-variable expression

text

Outputs are 1 for: A=0 B=1 C=0, A=0 B=1 C=1, A=1 B=1 C=0, A=1 B=1 C=1

            BC
         00   01   11   10
A = 0     0    0    1    1
A = 1     0    0    1    1

One group of four (columns 11 and 10): only B stays the same (B = 1)
Simplified: Q = B