12. Introduction to Karnaugh Maps (K-Maps)
Karnaugh Maps (K-Maps) provide a systematic, visual method for simplifying Boolean expressions without relying strictly on Boolean algebra theorems. It's especially effective for functions with 2, 3, or 4 variables.
What is a K-Map?
A K-Map is a grid where each cell corresponds to one row in the truth table (one minterm). The arrangement of the cells is critical: adjacent cells differ by only one variable (Gray code sequence).
The Concept of Adjacency
The simplification process relies on grouping adjacent '1's (for SOP minimization) or adjacent '0's (for POS minimization). Adjacency is defined by shared boundaries (horizontal or vertical, wrapping around the edges).
2-Variable K-Map Structure
| $\overline{B}$ (0) | B (1) | |
|---|---|---|
| $\overline{A}$ (0) | $m_0$ | $m_1$ |
| A (1) | $m_2$ | $m_3$ |
If we have $F = \Sigma(1, 3)$, we place 1s in cells $m_1$ and $m_3$. Since these are adjacent, they can be grouped, leading to simplification.
Why K-Maps are Useful
K-Maps eliminate the guesswork involved in algebraic simplification, guaranteeing the minimal SOP or POS form (the minimal number of logic gates needed).