4.3.3

Karnaugh Maps

Test yourself

Karnaugh Maps

Karnaugh maps are diagrams used to simplify boolean expressions.

Illustrative background for Drawing Karnaugh mapsIllustrative background for Drawing Karnaugh maps ?? "content

Drawing Karnaugh maps

  • Solving a two-variable problem using a Karnaugh map involves creating a grid as shown:
    • The ‘0’ and ‘1’ down the left of the grid refer to ‘not A’ and 'A'.
    • The the ‘0’ and ‘1’ along the top of the grid refer to ‘not B' and 'B'.
Illustrative background for ExampleIllustrative background for Example ?? "content

Example

  • Simplify the expression:
    • A.B+A.B+A.BA.\overline{B}+\overline{A}.B+A.B
  • We start by splitting it into three sets of brackets using the associative rule:
    • (A.B)+(A.B)+(A.B)(A.\overline{B})+(\overline{A}.B)+(A.B)
Illustrative background for Fill in the tableIllustrative background for Fill in the table ?? "content

Fill in the table

  • The first of these brackets refers to ‘A AND NOT B’.
  • That means we put a ‘1’ in the box with the coordinates (A1, B0) as shown.
  • The second bracket refers to ‘NOT A AND B’ .
  • That means we put a '1' in the box with coordinates (A0, B1).
  • The third bracket means ‘A AND B’, so we put a one in the box with coordinates (A1, B1).
Illustrative background for Group Illustrative background for Group  ?? "content

Group

  • The final stage involves grouping the '1's into sets of either 2, 4 or 8.
  • In this example, there are only three '1's in total, but they can be grouped into two pairs as shown.
  • The green pair both have the same value for A (1) and the blue pair have the same value for B (1).
  • So our original expression simplifies to A+BA + B.

Karnaugh Maps

We can also construct Karnaugh maps to simplify expressions with 3 or 4 variables.

Illustrative background for Three variablesIllustrative background for Three variables ?? "content

Three variables

  • With a three-variable problem, the grid is expanded by adding variable C to the top.
  • This means each column represents a combination of the variables B and C.
    • In the second column of the map shown, labelled 01.
    • The 0 refers to B and the 1 refers to C.
  • The order of these combinations follows the rules of Gray code.
  • This means that each combination is only a single bit different from the combinations either side of it.
Illustrative background for Four variablesIllustrative background for Four variables ?? "content

Four variables

  • For four variable Karnaugh maps, we do the same as for three variable but the rows now come to represent another combination of variables.
  • Each row is labelled using the Gray code as before.
Illustrative background for SimplificationIllustrative background for Simplification ?? "content

Simplification

  • In this example, the ‘1’s have been grouped into a pair (green) and a set of four (blue).
  • This is interpreted as (A AND B AND NOT C) OR (C AND NOT D) with the expression:
    • (A.B.C)+(C.D)(A.B.\overline{C})+(C.\overline{D})

Jump to other topics

1Components of a Computer

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

5Legal, Moral, Cultural & Ethical Issues

6Elements of Computational Thinking

6.1Thinking Abstractly

6.2Thinking Procedurally

6.3Thinking Logically

7Problem Solving & Programming

8Algorithms

Go student ad image

Unlock your full potential with GoStudent tutoring

  • Affordable 1:1 tutoring from the comfort of your home

  • Tutors are matched to your specific learning needs

  • 30+ school subjects covered

Book a free trial lesson