4.3.3
Karnaugh Maps
Karnaugh Maps
Karnaugh Maps
Karnaugh maps are diagrams used to simplify boolean expressions.
Drawing Karnaugh maps
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'.
Example
Example
- Simplify the expression:
- We start by splitting it into three sets of brackets using the associative rule:
Fill in the table
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).
Group
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 .
Karnaugh Maps
Karnaugh Maps
We can also construct Karnaugh maps to simplify expressions with 3 or 4 variables.
Three variables
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.
Four variables
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.
Simplification
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:
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.3Software Development
3Exchanging Data
3.1Compression, Encryption & Hashing
3.3Networks
4Data Types, Data Structures & Algorithms
4.1Data Types
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Procedurally
6.3Thinking Logically
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
Jump to other topics
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.3Software Development
3Exchanging Data
3.1Compression, Encryption & Hashing
3.3Networks
4Data Types, Data Structures & Algorithms
4.1Data Types
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Procedurally
6.3Thinking Logically
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
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