Boolean function
Named by 6 essays across one field — each of them below, with the objects they name alongside it.
A plane through the cube
Some truth functions are weighted votes: give each letter a weight, add the weights of the true letters, and say yes when the total passes a threshold. On the cube of assignments, such a function is a plane cutting the true corners from the false. Majority is one. Exclusive-or is not, and never can be — and of the 65,536 functions of four letters, only 1,882 are. The ones that are are exactly what a single artificial neuron can compute.
Half the cube and √n neighbours
Choose more than half the corners of an n-dimensional cube, any way at all, and some chosen corner has at least √n chosen neighbours. That statement about a cube settled a thirty-year question about how sensitive a truth function must be to its inputs, and its proof is a matrix of plus and minus ones whose square is n times the identity. A search over every choice for the 4-cube finds the bound exactly: nine corners, and some corner always has two chosen neighbours.
The conclusion is what survives the erasing
Lewis Carroll's puzzles give three premises about four classes — babies, logical people, the despised, crocodile-managers — and ask what follows. Draw all four, shade what the premises rule out, then erase the classes the conclusion is not about: a region survives as empty only if everything above it was. What is left is the conclusion, and erasing a class turns out to be exactly one step of resolution.
What a formula keeps when letters are fixed
Fix half the letters of a formula at random and most of its leaves become irrelevant: on the sixteen-leaf formula for the parity of four letters, two fixings leave four. How fast formulas shrink under random fixings is the whole engine behind the best lower bounds anyone has proved for formula size — Subbotovskaya's 3/2 in 1961, Håstad's 2 in 1998 — and the reason that engine stops at n³.
Functions that only go up
Of the 256 logical functions of three letters, only twenty never turn off when a letter is turned on. Dedekind asked in 1897 how many such monotone functions there are for n letters. Computing the count is hard enough that the answer has advanced one letter every twenty-five years or so, and the ninth arrived in 2023, from two groups in the same month, at forty-two digits. Almost everything about the number comes from a single layer of the cube.
The order of the questions
Decide a Boolean function by asking about its variables one at a time, and share every state that behaves alike. For a₁b₁ + a₂b₂ + … the result has 2n + 2 nodes if partners are asked together and 2ⁿ⁺¹ if they are apart. All 40,320 orders of eight variables give anything from 10 to 32 nodes, while multiplication's middle bit grows fast in the best order of all.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchHypercubeExclusive-orLower boundParityTruth tableAntichainCounting argumentDynamic programmingEigenvalueFormula sizeImplication