Karnaugh Map (K-Map)

A K-map is a truth table redrawn as a grid so that terms which can be merged sit next to each other. Fill the map, circle groups of 1s, and read off the shortest sum of products.

    Load

    What you are looking at

    The layout

    A 3 input map has 8 cells, one per truth table row. A picks the row, BC the column. The columns run 00, 01, 11, 10: Gray code order, so moving one column changes exactly one bit. The 00 and 10 columns also differ in one bit, so the left and right edges are neighbours. The map wraps.

    The merging rule

    AB + AB' = A(B + B') = A

    Two product terms that differ in exactly one variable merge into one term, and that variable drops out. A K-map places every such pair side by side.

    Legal groups

    1. Only 1s.
    2. 1, 2, 4 or 8 cells.
    3. A rectangle, where the wrap between 00 and 10 counts.

    Make each group as large as possible, use as few as possible, and cover every 1. Groups may overlap.

    Reading a group

    Look at each variable across the group. If it keeps the same value it stays: plain for 1, complemented for 0. If it changes, it drops out.

    2k cells → 3 − k literals

    Why not more groups?

    In Σm(0, 1, 5, 7), m1 and m5 also form a legal pair, B'C. Both cells are already covered by A'B' and AC, so it adds a term and removes nothing.

    Examples

    Σm(1, 3). A = 0, B changes, C = 1. Term A'C.

    Σm(0, 2, 4, 6). Only C stays, at 0. The group wraps. Term C'.

    Σm(0, 1, 5, 7). Two pairs. A'B' + AC.

    Try it

    Write the minimal sum of products. Use A B C, ' for NOT, + for OR, and write AND terms next to each other, for example A'B + C.

    1. Simplify F = Σm(2, 3, 6, 7).

    2. Simplify F = Σm(0, 2, 5, 7).

    3. Simplify F = Σm(1, 3, 4, 5, 6, 7).

    4. Simplify F = Σm(0, 1, 2, 4).