# Karnaugh Maps

concept

The Karnaugh map is a useful tool for simplifying boolean expressions without having to do a whole bunch of boolean algebra, which is often tedious.
The Karnaugh map is a table of output values for given inputs, a lot like a multiplication table but instead of the numbers 1 to 12 on the top and left you have just 0 and 1 (or some more when you have three or more input variables).
Once you have the Karnaugh map for a boolean expression we have a fairly simple method to create the simplified expression from the map.
So we can go from a complex boolean expression to its simplified form all without having to do any actual boolean algebra.

fact

The Karnaugh map for a boolean expression is essentially a multiplication table for the inputs.

example

Create the Karnaugh map for the expression \(A + B\)

First we'll set up the map ready for us to fill in. Along the left side we'll list the values \(A\) can take (0, 1) and across the top we'll list the values \(B\) can take (0, 1) like so:\(_A\)\\(\!^B\) | 0 | 1 |

0 | ||

1 |

\(_A\)\\(\!^B\) | 0 | 1 |

0 | 0 | |

1 |

\(_A\)\\(\!^B\) | 0 | 1 |

0 | 0 | 1 |

1 |

\(_A\)\\(\!^B\) | 0 | 1 |

0 | 0 | 1 |

1 | 1 | 1 |

To use the Karnaugh map to simplify an expression (which is its purpose after all), we want to find "groups" of 1s in the map. Ideally we'll have pairs of 1s next to each other or forming a rectangle.
A single "1" could be part of two or more groups, there's no problem with overlapping groups.
Once we've found the groups (a group could be a single '1' if it's sitting by itself) we find a rule to describe each one (like \(A\) or \(AB\)) and then sum all of these rules to get our final answer.
An example will be clearer

example

Use a Karnaugh map to simplify \(A+AB\)

First we need to write out the Karnaugh map:\(_A\)\\(\!^B\) | 0 | 1 |

0 | 0 | 1 |

1 | 1 | 1 |

practice problems