The zigzags a formula can draw

Classical logic has two truth values, and every formula in it is a truth table: a function from the truth values of its variables to a truth value. With two values and one variable there are only four such functions, and all four are definable. Jan Łukasiewicz, in Warsaw in 1920, added a third value for statements about the future that are not yet settled, and by 1930, with Alfred Tarski, he had a logic in which a truth value could be any real number from $0$ to $1$.

The connectives of that logic are arithmetic. Negation sends $p$ to $1 - p$. Strong disjunction, $p \oplus q$, adds the two values and caps the sum at $1$. Strong conjunction, $p \odot q$, adds them, subtracts one, and floors the result at $0$. The weak connectives $p \wedge q$ and $p \vee q$ are the minimum and the maximum. Implication, $p \to q$, is $\min(1, 1 - p + q)$, which the essay on Gödel’s chains drew beside Gödel’s own rule on the same square. Every one of these is a formula in the logic, and with negation and strong disjunction alone the others can be written.

So a formula in one variable $p$ is a function on the interval: put in the truth value of $p$, get out the truth value of the formula. The question this essay answers is which functions occur. The answer is a theorem of Robert McNaughton’s from 1951, and it is one of the cleanest characterisations in logic: exactly the continuous functions made of finitely many straight pieces, each piece a line with whole-number coefficients.

A gallery of zigzags #

The six graphs show what the connectives do to shapes. Negation reflects a graph top to bottom. Strong disjunction of a formula with itself doubles its slope and cuts it off at one; strong conjunction doubles its slope and cuts it off at nought. Weak conjunction and disjunction take the lower or upper of two graphs, which creates corners where they cross. Starting from the diagonal line $p$ and applying these operations, every graph is built from straight pieces, and every slope is a whole number — doubling a slope of one gives two, never one and a half.

Two of the graphs deserve a closer look. The tent $(p \oplus p) \odot \neg(p \odot p)$ is $0$ at both ends and $1$ in the middle: it says “$p$ is about half true”, in the sense that it is fully true exactly when $p$ is exactly half true and falls away linearly on either side. The weak conjunction $p \wedge \neg p$ — “$p$ and not $p$” — is classically a contradiction, always false. Here it reaches one half at $p = \tfrac12$. In Łukasiewicz’s logic a contradiction is not always fully false, and the law of excluded middle, $p \vee \neg p$, is not always fully true: at $p = \tfrac12$ it is one half.

Every function a small formula draws #

To see what McNaughton’s theorem says, the figure below enumerates every formula up to a size and keeps every function it finds.

The census builds formulas from $p$ by applying the five connectives in every possible way, computes each one’s values exactly at every multiple of $1/2520$ — the values stay whole numbers over $2520$ under every connective, so no rounding enters — and discards a formula whose function has been seen before. With nine connectives there are 3,002 different functions.

Every one of them has the same two properties. Each straight piece of its graph has a whole-number slope, and the line containing the piece crosses the vertical axis at a whole number. That second condition is the less obvious one and the more important. It is what forces every formula to be $0$ or $1$ at $p = 0$ and $p = 1$: a line with whole-number slope and intercept takes whole-number values at whole-number inputs. And it is what rules out the function $p/2$, whose slope is a half, and the constant function $\tfrac12$, whose intercept is a half.

McNaughton’s theorem says these conditions are not only necessary but sufficient. A function on the interval is defined by some formula of Łukasiewicz’s logic exactly when it is continuous, made of finitely many straight pieces, and each piece lies on a line with whole-number coefficients. In several variables the statement is the same, with planes in place of lines. The census confirms the easy direction on 3,002 examples; the hard direction, that every such function is reached, is McNaughton’s construction.

Why nothing else can appear #

The easy half of McNaughton’s theorem is an induction, and it is short enough to give in full, because it explains why the conditions are exactly these. The variable $p$ is the line $x$, with slope one and intercept nought. Negation turns a function $f$ into $1 - f$, which negates every slope and turns every intercept $c$ into $1 - c$ — whole numbers stay whole. Weak conjunction and disjunction take the minimum or maximum of two functions, which creates new corners where the graphs cross but uses only pieces already present. Strong disjunction takes $\min(1, f + g)$: on each region where both are straight, $f + g$ is straight with slope and intercept the sums of theirs, and capping at one adds the constant piece $1$. Strong conjunction does the same with $\max(0, f + g - 1)$.

Every operation sends pieces with whole-number coefficients to pieces with whole-number coefficients, so every formula’s graph has them. Continuity is preserved in the same way, since every operation is continuous. The induction is the whole proof of the easy direction, and it shows that the conditions are not a coincidence of the connectives chosen: they are what the arithmetic of adding, subtracting and capping at whole numbers preserves.

That is also why the logic differs so sharply from the two logics this subject looked at before. The constructive logic gives up excluded middle by changing what truth is — a statement is true when there is evidence for it — and keeps two-valued arithmetic at every stage of knowledge. Łukasiewicz’s logic keeps excluded middle as a formula and lets it be partly true. The two answer the same complaint about classical logic in incompatible ways, and the constructive system’s disjunction property has no counterpart here: a disjunction in Łukasiewicz’s logic is a value rather than a choice, and even $p \vee \neg p$ is not always fully true, so there is no side to pick.

What a formula can say at a fraction #

The integer condition has a consequence that can be checked point by point.

At $p = \tfrac12$, every formula takes one of the values $0$, $\tfrac12$ or $1$. At $p = \tfrac13$, one of $0$, $\tfrac13$, $\tfrac23$, $1$. At $p = \tfrac25$, a multiple of $\tfrac15$. The reason is the integer condition again: a line $mx + c$ with whole $m$ and $c$, evaluated at $x = a/b$, gives $(ma + cb)/b$, a whole number of $b$-ths. So the truth values a formula can produce from a given input are fixed by that input’s denominator.

That gives the logic a curious economy of expression. There is no formula that means “half as true as $p$”. There is no constant formula that is half true — the logic has names for falsehood and truth and for nothing in between, so every intermediate truth value has to come from a variable. And the values a formula can reach from $p = \tfrac12$ are exactly $0$, $\tfrac12$ and $1$, which is the reason the three-valued logic Łukasiewicz began with in 1920 sits inside the infinite-valued one as the formulas’ behaviour on the points $0$, $\tfrac12$, $1$.

Building a tent #

The hard direction of McNaughton’s theorem is a construction, and its building blocks are tents.

A tent at a rational point $a/b$ is the function $\max(0, 1 - |bp - a|)$: nought away from $a/b$, rising with slope $b$ to $1$ at $a/b$, falling with slope $b$ beyond. It satisfies McNaughton’s conditions, so some formula must define it, and the search finds the smallest. The tent at one half needs four connectives, $(p \oplus p) \odot \neg(p \odot p)$. The tent at one third needs eight:

$$\big(p \oplus (p \oplus p)\big) \odot \neg\Big(\big(p \oplus p\big) \odot \big(p \oplus (p \odot p)\big)\Big).$$

McNaughton’s proof shows that every allowed zigzag is a sum of tents of this kind at suitable points — a decomposition familiar from approximation theory, where such tents are called Schauder hats — and that the sums and truncations of tents can all be expressed with $\oplus$, $\odot$ and $\neg$. The search shows what the construction costs in small cases. The tent at one third, though simple to describe, is beyond any formula of seven or fewer connectives; the formulas known for tents at points with larger denominators are larger still, and their size is the price of saying “exactly a third true” in a language that has no fractions.

Two variables: a surface of flat pieces #

In two variables the formulas become surfaces over the square of truth-value pairs, and the theorem’s planes become visible.

The implication is fully true in the upper-left half, where $p \le q$, and below the diagonal it is a tilted plane, $1 - p + q$. The strong equivalence of $p$ and $q$ is a roof along the diagonal: fully true when $p = q$ and falling linearly with their difference. It is $1 - |p - q|$, one minus the distance between the two truth values. The logic carries its own measure of how nearly two statements agree, and that measure is the ordinary distance on the line.

That observation is the start of the modern understanding of the logic. In 1958 Alan Rose and J. Barkley Rosser proved that Łukasiewicz’s axioms capture exactly the formulas that are fully true at every point of the interval, and Chen Chung Chang gave an algebraic proof the next year through MV-algebras, which he had just introduced — the structures that stand to Łukasiewicz’s logic as Boolean algebras stand to classical logic. Daniele Mundici showed in 1986 that MV-algebras are the same thing, in disguise, as ordered groups of real-valued functions with a distinguished positive element — which is why the formulas are piecewise linear with integer coefficients: they are the functions such an ordered group can produce from its generators.

Three ways to conjoin degrees of truth #

Łukasiewicz’s strong conjunction is one of three natural ways to combine two degrees of truth into the degree of their conjunction, and the comparison clarifies what is special about it. Gödel’s way takes the minimum, so a conjunction is exactly as true as its weaker part; the chains of truth values that refuted every finite table were Gödel’s. The product way multiplies, as if the two degrees were independent probabilities. Łukasiewicz’s way adds and subtracts one, so two statements each four-fifths true make a conjunction three-fifths true: the shortfalls from full truth add up.

Each choice has its own implication — the largest value whose conjunction with $p$ stays below $q$ — and its own logic, and Petr Hájek showed in 1998 that all three are extensions of one basic logic of continuous conjunctions. Among the three, only Łukasiewicz’s has a negation that undoes itself, $\neg\neg p = p$, and only Łukasiewicz’s makes every formula a continuous function; Gödel’s implication jumps along the diagonal. Lotfi Zadeh’s fuzzy sets of 1965 brought all three into engineering, where they are used to blend rules stated in words, and the debate over which conjunction is right for which purpose is a debate about which accounting of partial truth fits the application.

The surprising connection: a guessing game with lies #

The most unexpected place this logic turns up is a parlour game. Stanisław Ulam asked in his autobiography of 1976 how many yes-or-no questions are needed to find a number between one and a million if the answerer may lie once, or twice. With no lies the answer is twenty, by halving. With lies, each answer must be treated as provisional, and the questioner has to keep track not of which numbers are possible but of how many answers each number would have to have been lied about.

Mundici showed in 1992 that the questioner’s state of knowledge in Ulam’s game with $k$ lies is exactly a valuation in Łukasiewicz’s logic with $k + 2$ truth values. Each number carries a truth value measuring how many lies it would require — nought lies is fully true, too many is fully false, and in between the values step down by $1/(k + 1)$ — and each answer updates every number’s value by a strong conjunction with the answer’s truth function. The rules of the logic, which look like an arbitrary choice of arithmetic for an arbitrary choice of connective, are the bookkeeping of a game in which information arrives with a bounded amount of error. The strong conjunction, adding and subtracting one, is exactly the act of charging a number one more lie.

So a logic invented to give future contingents a third truth value, extended by Łukasiewicz and Tarski to a continuum for no reason except that it could be, turns out to be the native logic of searching with errors — and the reason its connectives are what they are is the reason a sum of lies is a sum.

The easy half of McNaughton’s theorem, checked on 3,002 functions #

The census reaches nine connectives; McNaughton’s theorem is about all formulas. Every one of the 3,002 functions satisfies the integer conditions, which confirms the easy half of the theorem on examples. The hard half — that every function satisfying the conditions is reached by some formula — is visible only for the two tents the search found, and for the rest it is the construction in McNaughton’s paper, not anything a finite search can show.

The functions are sampled at multiples of $1/2520$. Formulas with up to nine connectives have their corners at rational points with small denominators, and the sampling grid catches all of them that matter for the census, but a corner at a point like $1/11$ falls between grid points. The census treats such a corner as a one-step transition and checks the straight pieces on either side; a reader wanting certainty about every corner would compute the breakpoints exactly, as the theorem does.

A truth value between nought and one is not a probability. The interval of truth values invites the reading that a statement half true is a statement with a fifty per cent chance of being true. Łukasiewicz’s logic is not a theory of chance: the truth value of $p \wedge \neg p$ at one half is one half, whereas the probability of a statement and its negation both holding is always nought. The pictures draw degrees of truth, and the arithmetic of degrees is not the arithmetic of probabilities.

Still open: what the formulas cost #

McNaughton’s theorem settles which functions are definable. It does not settle how large the defining formulas must be, and that question is still being worked out. The search found that the tent at one third needs eight connectives where the tent at one half needs four; for a tent at a point with denominator $b$, the smallest formula’s size is not known exactly, and the known constructions use formulas whose size grows with $b$ in ways that are not known to be optimal. More generally, given a zigzag with many pieces, the smallest formula that defines it — the logic’s version of the circuit-size questions of classical logic — has no formula of its own, and good bounds are known only for special families. It is the many-valued counterpart of asking how many gates a truth table needs, and like that question it is far easier to pose than to answer.

There is also a question one level up. Łukasiewicz’s logic is decidable, and deciding whether a formula is always fully true is a hard problem in the sense of complexity — Mundici proved in 1987 that it is exactly as hard as the classical question of whether a formula is a tautology — a harder problem in principle than its two-valued look suggests, and no harder than the search through finite algebras that decides constructive logic. What lies between this logic and classical logic is a family of intermediate logics, each a class of MV-algebras, and while those between Łukasiewicz’s and classical logic are classified, the full picture of how the many-valued logics fit around the constructive and classical ones has not been drawn.