Foundations — Karnaugh map simplification (2,3,4 variables)

Before you can group cells on a K-map, you must be fluent in the alphabet the map is written in. This page introduces every symbol the parent topic uses, one at a time, each anchored to a picture, each built on the one before it. Nothing is assumed.

1. A variable and its two values (0 and 1)

The picture: think of a light switch. It is either OFF or ON — no half-way. We write OFF as $0$ and ON as $1$.

• $1$ means true / yes / on / high.
• $0$ means false / no / off / low.

We will meet these in Truth Tables as the entries of a table, and on the K-map as the contents of each cell.

2. The bar — NOT (the opposite)

The picture: a see-saw. Push one side down ($A=1$) and the other side ($\bar{A}$) goes up ($=0$). They are always opposite.

3. AND (·) and OR (+) — the two ways to combine

We stack single variables into rules using two operators.

The picture (figure above): AND is two switches in series — current flows only if both are closed. OR is two switches in parallel — current flows if either is closed.

4. A product term and Sum-of-Products

5. Binary numbers and bits

The picture: columns worth $8,4,2,1$. To read 1011: $8+0+2+1=11$.

$\underset{8}{\underbrace{1}}\underset{4}{\underbrace{0}}\underset{2}{\underbrace{1}}\underset{1}{\underbrace{1}}=8+2+1=11$

6. Minterm and the $\sum m(\dots )$ notation

For 3 variables $ABC$:

7. Gray code — the special ordering

The picture (figure above): watch the single bit that flips at each step. Ordinary binary counting 00 → 01 → 10 flips two bits going from 01 to 10. Gray code 01 → 11 → 10 flips only one bit at every step — that is the whole reason the K-map uses it.

8. The cell, adjacency, and wrap-around

The picture (figure above): the left and right edges of the grid are actually touching, and so are the top and bottom. Roll the paper into a tube (left meets right), then bend the tube into a ring (top meets bottom) — that donut is the true shape of a K-map. The two orange corner cells look far apart on the flat map but are neighbours on the donut.

9. The don't-care symbol $\times$ (or $d$)

The combining theorem (the engine you're building toward)

Everything above exists so this single law can be applied visually:

Now every symbol in that formula is defined: $X,Y$ are variables (§1), $\bar{Y}$ is NOT (§2), juxtaposition is AND and $+$ is OR (§3), and "adjacent cells differ in one bit" (§7–8) is exactly the condition that makes $Y$ the one varying variable you get to drop. This law is proven in Boolean Algebra Laws.

How these foundations feed the topic

Equipment checklist

Test yourself — you are ready for the parent topic only if you can answer each without peeking.