Concept

Karnaugh map

A grid of a formula's truth values laid out so that squares which touch differ in exactly one variable. Adjacent squares differ in one variable, so a block of them is a single simplified term and minimising a formula becomes covering a picture.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

((p ∧ q) ∨ (r ∧ s)) ∨ (¬p ∧ ¬r), covered by 3 rectangles. A grid of the assignments arranged so that neighbouring squares differ in one variable.

The map that puts neighbours side by side

Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.

logic · Truth functions

A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

discrete · Hamiltonian cycles

Named alongside it

The objects these essays reach for when they reach for this one.

Gray code Hypercube Parity Binary Complete graph Counting argument Covering Graph Hamming distance Minimality Normal form Prime implicant

All concepts