Truth function
Named by 9 essays across one field — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
![Six formulas on the interval of truth values. Graphs on [0, 1] of six one-variable formulas of Łukasiewicz logic, each a zigzag of whole-number slopes with values 0 or 1 at the ends.](/f/six-formulas-on-the-interval-of-truth-values-01818ee4.svg)
The zigzags a formula can draw
Let truth be any number from 0 to 1, and Łukasiewicz's connectives turn every formula in one variable into a graph. Every graph that appears is a zigzag of straight pieces with whole-number slopes, ending at 0 or 1 — and McNaughton proved in 1951 that every such zigzag appears. A logic of degrees of truth turns out to be a theory of piecewise-linear functions with integer coefficients.
A contradiction that stays where it is
In classical logic one contradiction proves everything: from p and not-p, any q at all. Add a third truth value — both true and false — and count it as holding, and the explosion stops. The classical laws all survive as laws; what goes is exactly the reasoning that carries a contradiction somewhere it was not. Run the other way, the same three tables make a logic of gaps instead of gluts.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchHypercubeNormal formTruth tableConnectiveCounting argumentDualityFunctional completenessMany valued logicParityAffine functionAlgebra