Matpic
mathematics, in pictures
Series

Truth functions — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. (p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments. The assignments as corners of a cube, joined when they differ in one variable, with the satisfying corners filled.

    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. Post's five classes, and which connectives escape them. A table of connectives against the five closed classes, with the completeness verdict for each.

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

    part 3 · logic
  4. Weighted votes: two functions with a cut, and parity without one. For three functions of three letters, the eight assignments placed on a line by a weighted count, with true assignments filled and the threshold marked where one exists.

    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. 9 corners of the 4-cube: some corner always has 2 chosen neighbours. The 4-dimensional cube with 9 of its corners chosen so that no chosen corner has more than 2 chosen neighbours, the fewest possible, with the edges between chosen corners drawn heavy.

    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

All series