Matpic
mathematics, in pictures
Generator

The truth table of p → (q → p)

A generator in the logic library, called 22 times across 9 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

truth-table is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

The truth table of p → (q → p). A grid with one row per assignment of truth values, and the value of the formula beside it.

(p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments

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

Weighted votes: two functions with a cut, and parity without one

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.

Weighted votes among all functions: 4, 14, 104, 1,882

Weighted votes among all functions: 4, 14, 104, 1,882. A table giving, for one to four letters, the number of all Boolean functions, the number that are threshold functions, and the fraction.

The perceptron rule on majority and on parity

The perceptron rule on majority and on parity. Mistakes per pass of the perceptron learning rule over the eight inputs of three letters, for majority, where they fall to zero, and for parity, where they never do.

Sensitivity at each corner, for three functions

Sensitivity at each corner, for three functions. Three cubes of assignments to three letters, one per function, with each corner filled if the function is true there and labelled with the number of neighbouring corners where it has the other value.

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Logic

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.

 Logic

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

A proof with one rule

Two clauses that disagree about exactly one variable can be combined into a third that forgets it; repeat, and if the clauses cannot all be true the empty clause eventually appears — a complete proof system with a single move.

 Logic

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

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.

 Logic

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.

 Logic

The middle that is not excluded

Either it is raining or it is not. Drop that as an axiom and what is left is still a logic — one with models made of open sets and of stages of knowledge, in which a set and its negation between them miss the boundary.

 Logic

The sentence that says it has no proof

Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.

 Logic

The tree that closes

To prove a formula, assume it false and take it apart. Every branch ends in a contradiction, or one of them describes exactly how it could have been false — and either way the tree is the answer, drawn.

The whole library · What the figures prove