Matpic
mathematics, in pictures
Concept

Exclusive-or

The logical operation that is true when exactly one of two inputs is true — addition of bits with no carry. It is the operation linear codes are built from, it cannot be computed by any single threshold, and that failure is the standard example of what one layer of a network cannot do.

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

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.

Boolean functionExhaustive searchHypercubeEigenvalueMajority ruleParitySensitivityThreshold functionTruth table

All concepts