Matpic
mathematics, in pictures
Concept

Boolean function

A function taking a string of true-false values to a single true or false. There are 2^(2^n) of them on n inputs, they are the objects a truth table describes, and most questions about computation are questions about which ones are cheap to evaluate.

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

Also named here as exclusive-or — the same set of essays touches all of them, so they are one junction rather than several.

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.

logic · Truth functions 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.

logic · Truth functions

Named alongside it

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

Exclusive-orExhaustive searchHypercubeEigenvalueMajority ruleParitySensitivityThreshold functionTruth table

All concepts