karnaugh-maps

Karnaugh Maps

What is a Karnaugh map?

• In A Level Computer Science, a Karnaugh map is a tool that is used for simplifying Boolean algebra expressions

• It offers a visual method of grouping together expressions with common factors

• The format of the map makes it easy to identify and eliminate redundant terms

• They are used in digital logic design, such as simplifying the logic of digital circuits

Steps:

1. Create the Map: Each cell in the grid corresponds to a term in the Boolean expression. Fill cells with 1s and 0s corresponding to the output of that term

2. Grouping: Group the 1s in the grid. Each group must be a rectangle and the size of the group must be a power of 2. A cell can be part of multiple groups

3. Simplifying: Write down a simplified Boolean expression for each group. The simplified expression for a group consists of the variables that remain constant in all terms in the group

4. Final Expression: Combine the simplified expressions from each group using OR operations to get the final simplified Boolean expression

Creating Karnaugh Maps

• A Karnaugh Map (KMap) can be used to simplify a Boolean expression with 2 inputs

• Here is an example for the expression A V B (A OR B)

Step 1

• Add each variable starting with A at the top and B down the side

• Add each possible state for A and B

Step 2

• Take each expression in turn separated by the V (OR)

• First look at A on it’s own

• Find all cells where A is 1

• Add 1 to the cell

Step 3

• Repeat for B

Step 4

• This is now a completed KMap for the expression A V B (A OR B)

Simplifying Expressions Using Karnaugh Maps

Simplify ¬A^¬B^C v ¬A^B^¬C v A^¬B^C v A^B using a KMap.

In this example there will be 3 variables A,B and C so the empty KMap will look like this:

Step 1:

Split this long term at each OR giving 4 smaller expressions (subterms) to add to the table:

• ¬A^¬B^C

• ¬A^B^¬C

• A^¬B^C

• A^B

Step 2: 

• Take the first subterm ¬A^¬B^C

• Put a 1 in the map for every cell where this term would be TRUE (1)

• So if A and B were 0 and C was 1 this subterm would be 1

• So put a 1 in every cell in the KMap where A is 0, B is 0 and C is 1

Step 3:

• The next subterm is ¬A^B^¬C

• Put a 1 in the KMap where A is 0, B is 1 and C is 0

Step 4:

• The next subterm is A^¬B^C

• Put a 1 in the KMap where A is 1, B is 0 and C is 1

Step 5:

• The final subterm is A^B

• Put a 1 in the KMap where A is 1 and B is 1 (2 cells this time)