Truth functions — the series

1. 

   A formula is a corner of a cube

   A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

   part 1 · logic
2. 

   One connective is enough

   Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.

   part 2 · logic
3. 

   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.

   part 3 · logic
4. 

   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.

   part 4 · logic
5. 

   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.

   part 5 · logic
6. 

   How many gates a truth table needs

   Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.

   part 6 · logic
7. 

   The formula that cannot share

   A circuit computes the parity of n letters with a chain of n − 1 exclusive-or gates. A formula in and, or and not, which may use each result only once, needs n² letters at least — a bound Khrapchenko proved by counting the cube's edges between true and false — and exhaustive search over every formula of four letters finds parity sitting exactly on it.

   part 7 · logic
8. 

   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³.

   part 8 · logic
9. 

   Truth tables up to renaming

   There are 256 truth functions of three letters, but many differ only in which letter is called what, or whether a letter or the answer is negated. Counted up to such renamings there are fourteen. For four letters there are 222, for five 616,126 — and almost every function of many letters is changed by every renaming, so the count settles into a simple division.

   part 9 · logic
10. 

    What an incomplete set of connectives can say

    Nand alone can express every truth function, and Post's five properties say exactly which sets of connectives can. That answers the question at the top. Below it lies a whole landscape: and alone expresses 7 of the 256 functions of three letters, xor 8, implication 38, and the sixty-four sets that can be drawn from and, or, not, xor and the two constants fall into just 22 different classes of expressible functions. The classes fit together into Emil Post's lattice of 1941 — countably infinite, completely described, and on three letters small enough to draw.

    part 10 · logic
11. 

    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.

    part 11 · logic
12. 

    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.

    part 12 · logic

All series