We begin with the language of logic to later build toward theoretical models, numerical and analytical computation, phenomenological approximation, and experimentation.
To as reasonable an extent as I've been able to manage, theorems follow from axioms and earlier theorems, models and algorithms from established mathematics, circuits from gates or simpler circuits. A mastery of logic is what
will enable us to check each of these steps, ensuring that our constructions behave as intended and mean what we intend.
Ideally, then, there are only three limitations to this book, beyond those of its author: the limits of logic itself (ch. 13), what measurement and
modelling cannot reach, and the places where a theory that works must be reinterpreted before it makes sense, such as
renormalization for quantum field theory (ch. 161).
This chapter asks:
What counts as a statement, and what does not?
How many ways are there to combine two statements, and how few suffice to build them all?
When do two formulas say the same thing, and what are the laws that let us replace one by the other?
Which questions cannot be asked at once, and why does that matter for quantum mechanics?
How do circuits perform arithmetic, and what happens when the circuits are wrong?
Can a circuit compute without forgetting, and what does that cost?
Statements
1.1Definition (informal). A statement is a
sentence that is either true or false. Its truth value is T if it is true and F if it is false.
This is not a definition in the strict sense. It explains “statement” using “true” and “false,” which are not explained. Every
subject has to start with something left undefined, and this is where this book starts. From 1.4 on, every
object is defined exactly.
1.2Assumption (bivalence). Every statement has
exactly one truth value, whether or not that value is known.
Before reading further, sort these. Which are statements?
Exercise 1.A
Is “This sentence has five words.” a statement? If so, what is its truth value, and why is it not a second liar?
Count the words.
Try giving it the value T, then F. Does either lead to a contradiction?
It has five words, so it is true. Giving it T is consistent; giving it F is not, because it does have five words. It refers to itself, as the liar does, but it does not deny its own truth, so nothing goes wrong.
Self-reference alone is harmless. The liar combines self-reference with negation of its own truth. Ch. 13 builds a sentence that refers to itself and denies its own provability: not a paradox, but a true statement that cannot be proved.
Two kinds of string are not statements even though they look like mathematics. An expression names an
object: “2 + 3 · 5” names the number 17 and claims nothing about it. A string is ill-formed when it names
nothing: in “0/0 = 1,” the symbol 0/0 is undefined, so the string is neither true nor false. An argument must
never contain an ill-formed string. Here is what happens when one slips in. Let a = b. Then
a² = ab, a² − b² = ab − b²,
(a + b)(a − b) = b(a − b),
a + b = b, 2b = b, 2 = 1.
The fourth step cancels the factor a − b. Cancelling means dividing both sides by it, and it is 0,
so the step silently writes b(a − b)/(a − b), which contains 0/0: an
ill-formed string. The fourth line does not follow from the third. Every other step is correct.
The liar, “This sentence is false,” is excluded by 1.2 alone: if it had the value T it would be false, and if F,
true. Why may mathematics simply set it aside? The answer, which is Tarski's, comes with the three kinds of
object below. The exclusion will not last. In ch. 5 the same structure, applied to collections, breaks the natural idea of a set.
In ch. 13, arithmetic builds a sentence that says of itself that it cannot be proved; that sentence is a genuine
statement, and if the system that proves things is consistent, it is true. The liar is postponed here, not
removed.
Combining statements
In ordinary speech, “she fell and broke her arm” suggests that one caused the other. In mathematics, “p
and q” asserts only that p is true and q is true. The truth value of the combination depends
on the truth values of the parts and on nothing else, so a way of combining statements is described completely
by a table.
1.3Definition. For statements p and
q: the negation ¬p (“not p”) is true exactly when p is false; the
conjunctionp ∧ q (“p and q”) is true exactly when both are true; the
disjunctionp ∨ q (“p or q”) is true exactly when at least one is true.
p
q
¬p
p ∧ q
p ∨ q
T
T
F
T
T
T
F
F
F
T
F
T
T
F
T
F
F
T
F
F
“Or” here is inclusive: p ∨ q is true when both are. The exclusive “or,” true when exactly one part
is true, is written p⊕q. It is a different rule, and it is the one a
computer uses to add.
Formulas
To prove things about every combination at once, such as “every combination built from ∧ and ∨ has property
X,” the combinations must be objects with an exact definition. They will be strings of symbols.
1.4Definition. The symbols are the
lettersp, q, r, …, the connectives ¬, ∧, ∨, and the parentheses ( and ). The
formulas are the strings built by three rules: (i) every letter is a formula; (ii) if φ is a formula, so is
¬φ; (iii) if φ and ψ are formulas, so are (φ ∧ ψ) and (φ ∨ ψ). Nothing else is a formula.
1.5Assumption (induction on formulas). If every
letter has a property, and rules (ii) and (iii) of 1.4 make formulas with the property only from formulas with
it, then every formula has the property. Equivalently, by induction on length: if a property holds for
each formula whenever it holds for all shorter formulas, it holds for every formula.
“Nothing else is a formula” is what makes 1.5 plausible: every formula is reached by finitely many uses of the
rules, so a property that survives every rule reaches it. Turning that argument into a proof needs the natural
numbers, which ch. 9 builds. Until then 1.5 is assumed, as 1.2 is, and every proof “by induction” in this
chapter rests on it.
The Greek letters are not symbols of the language. They stand for formulas, the way x stands for a
number. To give a formula a value we will work from its parts outward, so we need to know that a formula has only
one set of parts.
Worked example: reading a formula one way
Take ((p ∧ q) ∨ ¬r). Its first symbol is (, so only the third rule can have made it: it
is (α ∘ β) for some formulas α and β and a connective ∘. Where does α end? α starts right after the first (,
so it starts with (p. The candidates are the initial segments that are formulas: (p is not one
(its parentheses do not balance), (p ∧ is not, (p ∧ q is not, and (p ∧ q) is.
Could a longer string also be a formula and start the same way? 1.6 below says no: two formulas, one an initial
segment of the other, are equal. So α = (p ∧ q), ∘ = ∨, and β = ¬r, with no other choice.
Without parentheses the same question has two answers. In p ∧ q ∨ r, the first part could
be p or p ∧ q. Type it into the tree box below to see both trees.
1.6Lemma. If a formula is an initial segment
of another formula, the two are equal.
Let φ′ be a formula that is an initial segment of the formula φ. We argue by induction on the
length of φ, assuming the claim for all shorter formulas. Both begin with the first symbol of φ. If it is a letter,
φ is that letter alone, since only the first rule makes strings that begin with a letter, so φ′ = φ. If it is ¬,
then φ = ¬α and φ′ = ¬α′, where α′ is an initial segment of α; α is shorter than φ, so α′ = α. If it is (, then
φ = (α ∘ β) and φ′ = (α′ ∘′ β′) for connectives ∘, ∘′. The formulas α and α′ start at the same place, so one is an
initial segment of the other, and both are shorter than φ; by the assumption applied to the longer one, α = α′.
The next symbols are then ∘ and ∘′, so ∘ = ∘′. The same argument applied to β and β′ gives β = β′. So φ′ = φ.
1.7Theorem (unique readability). Every formula
is exactly one of: a letter; ¬α for exactly one formula α; (α ∧ β) or (α ∨ β) for exactly one choice of α, β and
connective.
The first symbol decides which rule made the formula. For ¬α, α is the rest of the string. If
(α ∘ β) = (α′ ∘′ β′), then α and α′ start at the same place, one is an initial segment of the other, and 1.6
gives α = α′; then ∘ = ∘′, and β, β′ are what remains before the last parenthesis, so β = β′.
1.8Notation. Formulas may be written with
fewer parentheses: the outermost pair is dropped, ¬ applies to the shortest formula after it, ∧ is applied before
∨, and repeated ∧ or repeated ∨ groups from the left. These are rules for writing, not new formulas: putting the
parentheses back in that order restores exactly one formula.
Type a formula. It is drawn as the tree of its parts: each formula branches into the formulas it was built from,
down to its letters. By 1.7 there is exactly one tree. Select a branch point to see the part that hangs from it.
Read by 1.8Read with “or” first
Exercise 1.B
Rule (iii) of 1.4 puts parentheses around every ∧ and ∨. Suppose it did not, so that φ ∧ ψ and φ ∨ ψ were formulas as written. Find a string with two readings that have different truth tables. Use the tree box above to check.
Mix ∧ and ∨ in one string of three letters.
p ∧ q ∨ r reads as (p ∧ q) ∨ r or as p ∧ (q ∨ r). Under the assignment p = F, r = T the first is T and the second is F. Without parentheses, 1.7 fails and “the value of a formula” stops meaning one thing.
Exercise 1.C
Prove that every formula has as many left parentheses as right ones.
Every formula is built by the three rules of 1.4. Check that each rule keeps the property.
For (φ ∧ ψ), count the parentheses of φ, of ψ, and the two new ones.
By induction on formulas. A letter has none of either. If φ has equally many, so does ¬φ, which adds no parentheses. If φ has l of each and ψ has m of each, then (φ ∧ ψ) and (φ ∨ ψ) have l + m + 1 of each. Every formula is built by these rules, so every formula has the property.
A complete proof checks the letters, checks each of the three rules, and says why that covers every formula.
1.9Definition. A truth assignment gives
each letter a truth value. The value of a formula under an assignment is found from its parts: a letter
has its assigned value, and ¬φ, (φ ∧ ψ) and (φ ∨ ψ) take the values the tables of 1.3 give from the values of
φ and ψ. By 1.7 each formula has only one set of parts, so it has exactly one value. A truth table
lists every assignment to the letters of a formula, one per row, with the value in each.
1.10Definition. A truth function of
n letters is a rule giving T or F for each assignment to those letters. Each formula determines a
truth function: the last column of its table.
Three kinds of object are now in play, and they should not be confused.
Example
What it is
Has a truth value?
Statement
7 is prime
A sentence of mathematics
Yes, by 1.2
Formula
(p ∧ ¬q)
A string of symbols, 1.4
Only under an assignment
Truth function
F T F F
A rule from rows to values, 1.10
No; it gives one per row
A formula becomes a statement when its letters are replaced by statements. Many formulas determine the same
truth function; that will be called equivalence, 1.14.
The table also separates two languages. Formulas are strings of a formal language. “True under an assignment”
is said about them in English, from outside. This is not a convenience.
showed in 1933 that a consistent language strong enough to
describe its own sentences, as arithmetic is, cannot define truth for those sentences within itself: “true” always has to be said one level up.
That is the real reason the liar can be set aside here. It is also exactly what ch. 13 exploits: arithmetic can
describe its own sentences, and can define “provable” for them, but not “true.”
Type a formula, using p, q, r, the words not, and, or, and parentheses.
1.11Proposition. A truth table for n
letters has 2n rows.
Each letter independently receives one of 2 values, giving 2 · 2 ⋯ 2 = 2n
assignments.
Try it: invent a truth function
A truth function of two letters is a choice of T or F for each of the four rows. Make one by clicking the last
column, or by choosing a corner of the figure. The page names the ones that have names.
Each corner of the figure is a truth function, drawn as its column of four rows, top row first; a filled square
is T. Two corners are joined when they differ in exactly one row, and going up a line turns one F into T. This is
a four-dimensional cube drawn flat: four rows, each with two values.
Worked example: finding your way on the cube
Find “and.” Its column is T F F F: one T. The corners are arranged by how many T's they have, from none at the
bottom to four at the top, so “and” is in the second row from the bottom, which holds the four truth functions
with exactly one T.
Now follow one line up from it. Going up turns one F into T. Turning the third row gives T F T F, which is
q: true exactly when q is. Turning the second row instead gives T T F F, which is p. So
“and” sits just below both p and q, and it is the highest corner below both, which is why it is
their ∧. Turning the last row gives T F F T, “same value.” Every line in the figure is one row changing its
mind.
Now take two corners and walk down from each, one line at a time, turning T into F only where the other corner
has F. The two walks meet at the highest corner below both, and that corner is their ∧. Walking up instead, they
meet at the lowest corner above both: their ∨.
1.12Proposition. There are exactly
22n truth functions of n letters.
By 1.11 there are 2n rows, and a truth function independently chooses one of
2 values for each, giving 22n.
For two letters, 16: the corners of the cube. Every rule for combining two statements that depends only on their
truth values is one of them. A rule such as “because” depends on more, and is not.
Exercise 1.D
How many truth functions of two letters do not change when p and q are exchanged?
Exchanging p and q swaps two of the four rows and leaves the other two alone. Which two?
8. Exchanging the letters swaps the rows (T, F) and (F, T), so the function must give them the same value. It then chooses freely for three things: the row (T, T), the pair of swapped rows, and the row (F, F), giving 2³ = 8. They are the corners of the cube whose second and third squares match.
Going further: for n letters, a function unchanged by every exchange of letters depends only on how many letters are T, a number from 0 to n, so there are 2n+1.
When two formulas say the same thing
1.13Definition. A formula is a tautology if
its value is T under every assignment, satisfiable if it is T under at least one, and a
contradiction if it is F under every assignment, that is, if it is not satisfiable.
p ∨ ¬p is a tautology, the law of excluded middle; p ∧ ¬p is a contradiction.
φ is a tautology exactly when ¬φ is not satisfiable, so either question answers the other. By 1.11 a truth table
settles both in 2n rows. Deciding satisfiability is the problem called SAT, and whether it can be
done in a number of steps that grows only as a power of n is the P versus NP question (ch. 23).
1.14Definition. Formulas φ and ψ are logically
equivalent, written φ ≡ ψ, if they determine the same truth function.
“φ ≡ ψ” is a statement about two formulas, not a formula; ≡ is not one of the symbols of 1.4. Try it: find a
formula equivalent to ¬(p ∧ q) that does not use “and.”
1.15Theorem. For letters p, q,
r:
Double negation
¬¬p ≡ p
Idempotence
p ∧ p ≡ p, p ∨ p ≡ p
Commutativity
p ∧ q ≡ q ∧ p, p ∨ q ≡ q ∨ p
Associativity
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r), (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Each line compares two columns of at most 8 rows; the box above checks any of them. For
distributivity, p ∧ (q ∨ r) is T exactly when p is T and at least one of q,
r is; (p ∧ q) ∨ (p ∧ r) is T exactly when p and q are both T or
p and r are both T. Both describe the same three rows: p = T with (q, r) =
(T, T), (T, F) or (F, T).
The laws are stated for letters but used for whole formulas, inside larger ones. Two results allow this.
1.16Theorem (substitution). Let φ be a tautology
in the letters p1, …, pn, and let φ* be the result of replacing each
pi, everywhere, by a formula ψi. Then φ* is a tautology. So every law of
1.15 holds with formulas in place of letters.
Fix an assignment to the letters of φ*. Under it each ψi has a value
vi. By induction on the formula φ, the value of φ* under this assignment equals the value
of φ under the assignment pi ↦ vi: this holds for each letter,
and each rule of 1.4 computes both values in the same way. That value is T. The same
induction shows that if φ ≡ ψ then φ* ≡ ψ*, with the same formula ψi put in place of
each pi in both: under any assignment, φ* and ψ* take the values of φ and ψ under
pi ↦ vi, which are equal.
1.17Theorem (replacement). If φ ≡ ψ, replacing
an occurrence of φ inside a formula χ by ψ gives a formula equivalent to χ.
Under every assignment φ and ψ have the same value, and the value of χ depends on that occurrence
only through its value, by induction on χ.
Worked example: simplifying with the laws
Simplify ¬(p ∧ ¬q), naming the law at each step.
¬(p ∧ ¬q)
≡ ¬p ∨ ¬¬q
De Morgan, with ¬q in place of q: allowed by substitution, 1.16
≡ ¬p ∨ q
double negation on the part ¬¬q: allowed by replacement, 1.17
No table was needed. The result has the column T F T T. Keep it in mind for the end of the chapter.
A second one: (p ∧ q) ∨ (p ∧ ¬q).
(p ∧ q) ∨ (p ∧ ¬q)
≡ p ∧ (q ∨ ¬q)
distributivity, read from right to left, with ¬q in place of r
≡ p
q ∨ ¬q is T in every row (excluded middle), so the whole has the value of p in every row
In words: “p, whether or not q” says no more than p.
Exercise 1.E
For a formula φ, let φd be φ with ∧ and ∨ exchanged everywhere. Prove that if φ ≡ ψ then φd ≡ ψd. So each law of 1.15 has a twin: the two distributive laws, the two De Morgan laws, the two absorption laws.
Try φ = p ∧ (q ∨ r). Compare ¬φ with φd.
Show by induction that ¬φ ≡ φd with every letter replaced by its negation.
If φ ≡ ψ then ¬φ ≡ ¬ψ. Now substitute ¬p for each letter p and use double negation.
Write φd[¬] for φd with each letter p replaced by ¬p. Claim: ¬φ ≡ φd[¬]. By induction: for a letter both sides are ¬p. For ¬α, (¬α)d[¬] = ¬(αd[¬]) ≡ ¬¬α by the hypothesis and 1.17. For α ∧ β, ¬(α ∧ β) ≡ ¬α ∨ ¬β ≡ αd[¬] ∨ βd[¬] = (α ∧ β)d[¬], by De Morgan and the hypothesis; ∨ is the same.
Now if φ ≡ ψ then ¬φ ≡ ¬ψ, so φd[¬] ≡ ψd[¬]. Substitute ¬p for every letter p (1.16 applies to equivalences, since φ ≡ ψ exactly when (φ ∧ ψ) ∨ (¬φ ∧ ¬ψ) is a tautology) and remove the double negations: φd ≡ ψd.
This is a symmetry of logic. Exchanging T and F everywhere exchanges ∧ and ∨, and in the cube it is the flip that turns the figure upside down. Symmetries that exchange two descriptions of the same structure will matter throughout the book.
Questions that cannot be asked at once
Distributivity looks like the dullest law on the list. Here is a structure in which it fails. It is worth
going through slowly, because the same failure sits at the centre of quantum mechanics. This section is a look
ahead: nothing later in this chapter depends on it, and ch. 28 and ch. 36 prove what it shows.
The objects. Draw a plane and mark its centre. The objects in this structure are of three kinds: the
centre point alone, a line through the centre, and the whole plane. They play the part that statements played
in the truth tables.
The centre pointA line through the centreThe whole plane
“And.” For two objects A and B, let A ∧ B be the points they share. A point is
in A ∧ B exactly when it is in A and in B, just as in the truth tables. Two different
lines through the centre share only the centre.
L₁ ∧ L₂ is the centre point.
“Or.” The obvious choice for A ∨ B is every point in A or in B. For two lines
that gives a cross, and a cross is not one of the objects: it is not a point, not a single line, and not the
whole plane. The reason is that the objects are exactly the nonempty sets you cannot leave by adding two of their points,
as arrows from the centre, or by stretching one. Add a point of L₁ to a point of L₂, arrow to arrow,
and the result lies on neither line, so the cross can be left. So A ∨ B is the smallest object that
contains both. A line holds only one line through the centre, so the smallest object containing two different
lines is the whole plane. Ch. 28 calls these objects subspaces, and the smallest one containing two of them their
sum.
This is where something new happens: L₁ ∨ L₂ contains points that are on neither line. In the
truth tables “or” never does that. A row makes p ∨ q true only if it makes p true or
q true. In the cube, too, ∧ and ∨ were the highest corner below both and the lowest corner above both,
the same rule used here, and there the lowest corner above both never added anything new.
“Not.” For a line L, let ¬L be the line through the centre at a right angle to it. Let ¬ of
the centre point be the whole plane, and ¬ of the whole plane the centre point. Then ¬¬A = A,
A ∧ ¬A is the centre point, and A ∨ ¬A is the whole plane: the centre point plays
the part of F and the whole plane the part of T, and double negation, excluded middle and non-contradiction all
survive. In the figures below, L₂ is ¬L₁.
Distributivity, step by step. Let L₁ be horizontal, L₂ vertical and L₃ diagonal.
Compute both sides of L₁ ∧ (L₂ ∨ L₃) = (L₁ ∧ L₂) ∨ (L₁ ∧ L₃).
Left:L₁ ∧ (L₂ ∨ L₃)Right: (L₁ ∧ L₂) ∨ (L₁ ∧ L₃)
Turn L₃. The slider sets the angle from L₁ to L₃, and both sides are
recomputed in full. They agree only when L₃ lies along L₁ or along L₂.
Asking a question. There is another way to read these objects. Treat a line as a yes-or-no question about a
point: is the point on the line? To ask it, drop the point onto the line: move it to the nearest point of the
line, which is where a path at a right angle to the line meets it. This is called projecting the point onto
the line. A point already on the line stays where it is; any other point moves. Now ask two questions, L₁ and L₃, one after the other, in both orders.
Solid: L₁ first, then L₃. Dashed: L₃ first, then L₁.
Preview, proved in ch. 36. Call two questions compatible when
they can be asked in either order with the same result. In any space of this kind, questions that are compatible in
pairs obey every law of 1.15, distributivity included: together they form a copy of the logic of this chapter.
Distributivity fails only between questions that are not compatible.
Seen this way, the logic of this chapter is the special case in which every question can be asked at once.
One warning for later. This plane uses real numbers. Quantum mechanics uses complex numbers (ch.
19, 34), and some of these pictures change there; ch. 35 shows what compatible questions look like for
a single qubit.
Exercise 1.F
Does the other distributive law, L₁ ∨ (L₂ ∧ L₃) = (L₁ ∨ L₂) ∧ (L₁ ∨ L₃), hold for three different lines?
Two different lines share only the centre point.
It fails. On the left, L₂ ∧ L₃ is the centre point, and L₁ ∨ (centre point) is L₁. On the right, each ∨ of two different lines is the whole plane, and plane ∧ plane is the plane. A line on one side, the plane on the other.
Not every law fails. Absorption holds: A ∧ (A ∨ B) = A for any two of these objects. Which laws survive is worked out in ch. 28 and ch. 36. In place of distributivity a weaker law survives. For the subspaces of this plane, and of any space of finite
dimension, it is the modular law (ch. 28). Quantum field theory needs spaces of infinite dimension, where
even the modular law fails for the subspaces quantum mechanics uses, and what survives is weaker still: the
orthomodular law, which involves ¬ (ch. 36).
How few connectives are needed?
Some connectives can be written with others: by De Morgan, p ∨ q ≡ ¬(¬p ∧ ¬q).
Every formula determines a truth function. The reverse question decides how many connectives we need: is every
truth function determined by some formula? The button “Rebuild it from its table” above already answered it, by
a method that works for any table.
Worked example: exclusive or, rebuilt by hand
Exclusive or has the column F T T F. It is T in two rows: p = T, q = F, and p = F,
q = T. For each, write the conjunction that is T in that row and nowhere else:
Row
Conjunction
T only in this row because
T, F
p ∧ ¬q
it needs p true and q false
F, T
¬p ∧ q
it needs p false and q true
Join them with ∨: (p ∧ ¬q) ∨ (¬p ∧ q). In the two rows where exclusive or is T, one of
the conjunctions is T; in the other two rows both are F. So the formula has the column F T T F. The proof below
is this, done for every table at once.
1.18Theorem (normal form). Every truth function
of n ≥ 1 letters is determined by a formula using only ¬, ∧ and ∨.
For each row where the function gives T, form the conjunction of the letters that are T in that
row and the negations of those that are F. That conjunction is T in its own row, since each of its parts is, and F
in every other row, since some letter differs there and makes its part F. Join these conjunctions with ∨. The
result is T in a row exactly when one of its conjunctions is, that is, in exactly the rows where the function
gives T. If there are no such rows, use p ∧ ¬p.
1.19Corollary. ¬ and ∧ alone suffice; so do ¬ and
∨ alone.
Replace each (φ ∨ ψ) by ¬(¬φ ∧ ¬ψ), which is equivalent by De Morgan and double negation (1.15,
1.16); by 1.17 the whole formula determines the same truth function. Exchange ∧ and ∨ for the other case.
Exercise 1.G
The normal form of 1.18 can be long. Let parity of n letters be T when an odd number of them are T. Prove that any disjunction of conjunctions of letters and negated letters that determines parity has at least 2n−1 conjunctions.
Each conjunction must be F in every row where parity is F.
Suppose a conjunction leaves out some letter x. In a row where it is T, flip x.
Every conjunction that is T somewhere must be T only in rows where parity is T. Suppose one leaves out a letter x, and is T in some row. Flipping x leaves it T, since it does not mention x, but changes the parity. So it is T in a row where parity is F, which is impossible. Hence every useful conjunction mentions all n letters and is T in exactly one row. Parity is T in 2n−1 rows, so at least that many conjunctions are needed.
Research note. For formulas of this one shape, parity needs exponential length. Allow any nesting and parity needs only about n² symbols, and Khrapchenko proved in 1971 that about n² are necessary. As a circuit, which may reuse results (1.22), parity
takes only a number of gates proportional to n. Longer formulas are not rare; they are the rule. Shannon's counting argument of 1949 shows that almost every truth function of n letters needs formulas of length exponential in n: there are 22n truth functions, and far fewer short formulas. What is open is to name one. No explicit function, even one in NP, is known to need formulas of more than polynomial length; the best bound for an explicit function is about n³, due to Andreev, Håstad and Tal. Ch. 23 explains the gap between “most” and “this one.”
Push this as far as it goes. The connective p ↑ q, called NAND, is “not both”: F only when
p and q are both T. To add it to the language, give 1.4 a fourth rule: if φ and ψ are formulas, so
is (φ ↑ ψ), with the table of NAND. The proofs of 1.6, 1.7 and 1.15–1.17 go through unchanged, since they treat
each connective only through its table. ↑ is not associative, so 1.8 does not apply to it: its parentheses must
be written. Using only ↑, letters and parentheses, build each target. Type p nand q or
p ↑ q.
1.20Theorem. ↑ alone suffices.
By 1.19 it is enough to build ¬ and ∧. ¬p ≡ p ↑ p, by idempotence, and
p ∧ q ≡ (p ↑ q) ↑ (p ↑ q), the negation of p ↑ q.
Exercise 1.H
NOR, written p ↓ q, is “neither”: T only when both are F. Build each target from ↓ alone. Type p nor q or p ↓ q. Then prove that ↓ alone suffices.
¬p comes the same way it did for ↑.
p ∨ q is the negation of p ↓ q. For ∧, use De Morgan.
¬p ≡ p ↓ p; p ∨ q ≡ (p ↓ q) ↓ (p ↓ q); p ∧ q ≡ (p ↓ p) ↓ (q ↓ q), which is ¬p ↓ ¬q, “neither not-p nor not-q.” Since ¬ and ∨ suffice by 1.19, so does ↓.
The answers are the answers for ↑ with ∧ and ∨ exchanged: Exercise 1.E at work.
Not every collection of connectives suffices. Try to build ¬p using only ∧, ∨, letters and parentheses.
Your attempts so far, each as a column of four values, top row first. Filled means T.
Worked example: one formula in the all-T row
Take (p ∨ q) ∧ (p ∧ (q ∨ p)), and the row where p and q are
both T. Work from the inside out:
Part
Value
Why
p, q
T, T
this is the all-T row
p ∨ q
T
T ∨ T
q ∨ p
T
T ∨ T
p ∧ (q ∨ p)
T
T ∧ T
the whole formula
T
T ∧ T
Every step combined two T's with ∧ or ∨, and both give T. Nothing in a formula built this way can produce an
F in this row, however large it is. The proof below says “however large it is” precisely: that is the
induction.
1.21Proposition. No formula built from letters
with ∧ and ∨ is equivalent to ¬p.
Take the assignment that makes every letter T. Every letter has value T under it, and if φ and ψ
do, so do (φ ∧ ψ) and (φ ∨ ψ). By induction on formulas, every formula built with ∧ and ∨ has value T there.
¬p has value F there.
Exercise 1.I
Now the reverse kind of question. Using only ⊕ and ¬ (type xor and not), try to build p ∧ q. When you believe it cannot be done, prove it.
How many different truth functions have your attempts produced? The strip counts them.
Look at how many rows each of your attempts makes T.
Show by induction that every such formula equals either an exclusive or of some of the letters, or the negation of one. How many rows can such a function make T?
Call a truth function affine if it equals an exclusive or of some of the letters, possibly negated (the empty exclusive or is the constant F). Letters are affine; the negation of an affine function is affine; and the exclusive or of two affine functions is affine, since ⊕ is associative and commutative and x ⊕ x is F. By induction on formulas, every formula built with ⊕ and ¬ is affine. For two letters there are exactly 8 affine functions, and each is T in 0, 2 or 4 rows. p ∧ q is T in exactly one row.
The same invariant method as 1.21, with a different invariant. Adding the constant T and ∧ makes the set complete: ¬p ≡ p ⊕ T, and ¬ with ∧ suffices by 1.19. Formulas in ⊕ and ∧ are the algebra of ch. 27 and ch. 31.
Truth functions as machines
Let a wire carry 1 for T and 0 for F. A gate is a device whose output wire carries the value of a truth
function of its input wires.
1.22Definition. A circuit on input wires
x1, …, xn is a finite list of gates in which each gate takes its
inputs from the input wires or from gates earlier in the list, with some wires marked as outputs. Its
size is the number of gates. Its depth is the largest number of gates on any path from an input
wire to an output.
“Earlier in the list” is what rules out a wire feeding back into its own past: drawn as dots and arrows, a circuit
has no cycles. A formula is the special case in which each gate's output is used exactly once, so its picture is a
tree, the tree of 1.7. A circuit may use one gate's output many times. That is the whole difference, and it can be
large: parity of n letters needs formulas of about n² symbols but circuits of only about n
gates (Exercise 1.G). Size measures how much hardware a circuit needs; depth, how long its answer takes when every
gate is equally fast.
1.23Theorem. Every truth function of n bits
is computed by a circuit of NAND gates.
By 1.18 and 1.20 it is determined by a formula using only ↑. Build one gate for each ↑ in the
formula, and wire its inputs to the gates or input wires of its two parts, which 1.7 makes unique. A part used
twice is computed once and its wire split to feed both places: in an ordinary circuit, copying a value is
free.
Arithmetic is the first thing to build. Adding digits a and b of one column, with a carry c
from the column to the right, gives a sum digit and a new carry:
sum = a⊕b⊕c, carry =
(a ∧ b) ∨ (c ∧ (a⊕b)).
One such column is a full adder. Chain four, each passing its carry left; the rightmost column has no
carry coming in, so its c is 0. Set the bits of two numbers and watch the carry travel.
Worked example: 6 + 5, column by column
6 is 0110 and 5 is 0101. Number the columns from 0 on the right. In each column the full adder turns
a + b + c into a sum digit and a carry, with a + b + c = sum + 2 · carry:
Column
a + b + c
= sum + 2 · carry
both sides × 2column
0
0 + 1 + 0 = 1
1 + 2 · 0
1 = 1
1
1 + 0 + 0 = 1
1 + 2 · 0
2 = 2
2
1 + 1 + 0 = 2
0 + 2 · 1
8 = 0 + 8 (carry out)
3
0 + 0 + 1 = 1
1 + 2 · 0
8 (carry in) = 8
The sum digits, from column 3 down, are 1011, which is 11. To see why this must be right, add the four weighted equations. On the right: 1 + 2 + 0 + 8 = 11 from the sum digits, plus 8 from the carry out of
column 2. On the left: the a's and b's give 6 + 5, plus 8 from that same carry coming into
column 3. The two 8's are the same carry counted once on each side, so they cancel, leaving 6 + 5 = 11. The
proof below does this for any numbers.
1.24Proposition. A chain of n full adders
outputs the binary digits of A + B.
In each column, a + b + c = sum + 2 · carry, as the eight rows of the full
adder confirm. Number the columns from 0 on the right, so that the carry into column 0 is 0. Multiply column
k's equation by 2k and add over all columns. Each carry
appears once as 2 · carry from column k and once as the incoming c of column k + 1, with the
same weight 2k+1, so the carries cancel except the last one out and the first one in, which is
0, leaving A + B =
Σ sumk 2k + carryn 2n. Binary numerals and
these sums are made exact in ch. 9.
Exercise 1.J
In the chain, the last carry waits for every column: with 64-bit numbers, 64 full adders in a row. But the last carry is a truth function of the 128 input bits, so by 1.18 it has a formula with one layer of ∧ and one of ∨, two steps deep. Why is that not used? Propose something in between, and say what it costs.
Count: about how many rows make the last carry T? The normal form has one conjunction for each.
Column kgenerates a carry if a ∧ b, and propagates one if a ⊕ b. When is the last carry 1, in those terms?
Combine pairs of columns, then pairs of pairs.
The normal form is hopeless: the last carry is T in about half of the 2128 rows, and the method needs a conjunction for each.
In between: with gk = ak ∧ bk and pk = ak ⊕ bk, the last carry is T exactly when some column generates and every column to its left propagates: g63 ∨ (p63 ∧ g62) ∨ (p63 ∧ p62 ∧ g61) ∨ ⋯. A block of columns can be summarized by its own “generate” and “propagate,” and blocks combine in pairs, so about log₂ 64 = 6 rounds suffice, using on the order of a thousand gates instead of a few hundred. This is the carry-lookahead adder, in the parallel form published by Kogge and Stone in 1973.
The trade between depth (time) and size (gates) is the subject of ch. 22 and ch. 25. There is no single right answer, which is why this exercise has none.
Gates that fail
Real gates are sometimes wrong. Take the four-gate circuit for exclusive or,
n = a ↑ b, output = (a ↑ n) ↑ (b ↑ n), and let each gate give the
wrong output once in a while, at random. Run it 400 times on random inputs. Then build it three times and let a
vote decide.
One circuitThree circuits and a vote
Each square is one run. White means the answer was wrong.
1.25Definition. The majority of three bits
is maj(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z), which
is 1 exactly when at least two of the three are 1.
1.26Proposition. If at least two of x,
y, z equal v, then maj(x, y, z) = v. So if at most one of three
copies of a circuit is wrong, the vote is right.
If v = 1, the conjunction of the two copies equal to 1 is 1. If v = 0, every pair
includes one of the two copies equal to 0, so every conjunction is 0.
1.26 says nothing about how often two copies fail together; that needs probability, defined in ch. 72. There it
will follow that if each whole copy is wrong with chance q, independently, a perfect vote is wrong with
chance 3q² − 2q³, which is smaller than q exactly when q < 1/2. Here q is a
copy's failure rate, not a gate's: with each gate wrong 1 in 20, a copy of the four-gate circuit is wrong about
14.5% of the time. And the 1/2 assumes the vote never fails. Switch on “The vote can fail too” and try the
higher rates: Exercise 1.K asks where voting stops paying.
Exercise 1.K
With “The vote can fail too” switched on, at what gate failure rate does three circuits and a vote stop beating one circuit? Run the experiment at each rate above, more than once, and decide.
400 runs is noisy: differences of a few percent can flip between runs. Look for where the vote is consistently no better.
The crossing lies between two of the buttons.
Between 1 in 7 and 1 in 6: the vote stops paying at a gate failure rate of about 0.156, roughly 1 in 6.4. Computed exactly for this circuit, with a voter that fails at the same rate as the gates:
Each gate wrong
One circuit
Vote
Vote that can fail
1 in 100
3.2%
0.3%
1.3%
1 in 20
14.5%
5.7%
10.1%
1 in 7
33.1%
25.6%
32.6%
1 in 6
36.4%
30.1%
36.8%
1 in 5
40.3%
35.6%
41.4%
1 in 4
44.5%
41.8%
45.9%
Notice what the experiment could and could not tell you. Near the crossing, at 1 in 7 and 1 in 6, the difference is under one percentage point, smaller than the run-to-run noise of 400 trials: an experiment can suggest a crossing, and only the calculation of ch. 72 locates it. Also prove: the majority of five copies is right whenever at most two are wrong. (Each wrong pair still leaves three right.)
One vote is not von Neumann's answer. In a long computation errors pile up stage after stage, and a single vote
at the end comes too late. Chain twenty of these circuits, each adding one more input bit to a running exclusive
or, and compare three ways of running the chain.
One chainThree chains, one vote at the endThree chains, a vote after every stage
In the last, each of the three lines gets its own voter after every stage, so a voter that fails spoils one
line, and the next round of voting repairs it. Von Neumann called this a restoring organ. Errors still
accumulate, but far more slowly: each stage leaks a little, when two of the three lines fail at once. At 1 in 100
the restored chain is wrong about 5% of the time after twenty stages, or about 10% if the voters can fail, while
the other two are wrong about a third of the time. Stopping even that slow leak, for computations of any length,
is what von Neumann's full scheme, with many copies of every line, was for. From 1 in 20 up, all three are wrong
close to half the time, barely better than guessing: the gates fail too often for this scheme to keep up. A failure
rate below which repeated voting wins is what ch. 144 calls a threshold. Von Neumann's own estimates of it were
far below 1/2.
Gates that forget nothing
NAND forgets. Its output is 1 for three different inputs, so the output alone does not say what went in. The full
adder forgets too: two bits out from three in. This will matter. The gates of a quantum computer, in ch. 39, must
lose no information at all. Can computation be done without forgetting?
The Toffoli gate takes three bits a, b, c and returns a, b,
c⊕ (a ∧ b): it flips c exactly when a and b
are both 1. Find a setting of c that makes the third output a ↑ b. Then send the output back
through the gate.
Here is the whole gate. Each input is paired with exactly one output; only two rows change.
1.27Proposition. A gate with n input bits and
n output bits can be run backwards exactly when it pairs its 2n inputs with its
2n outputs one to one.
If two inputs give the same output, that output does not determine its input. If no two inputs
share an output, the 2n outputs are all different, so each of the 2n possible
outputs occurs exactly once and comes from exactly one input, which is the reverse.
1.28Theorem. The Toffoli gate is its own reverse.
Given extra input bits set in advance, circuits of Toffoli gates compute every truth function; in general they
also leave extra output bits holding values nobody asked for, called garbage.
Applying the gate twice flips c by a ∧ b twice, which leaves it unchanged.
With c set to 1 the third output is a ↑ b; with a set to 1 and c to 0 the
outputs are 1, b, b, a copy of b that lets one value feed two gates. In a reversible circuit
every gate has as many wires out as in, so a wire cannot simply be split as in 1.23: copying takes a gate and a
wire set to 0. NAND and copying build every circuit, by 1.23. Each NAND made this way keeps its inputs, so every intermediate value stays on some
wire.
Garbage is the price of not forgetting, and it can be paid back. This circuit computes a ∧ b ∧
c with two extra wires set to 0. Set the inputs and apply the gates one at a time.
Worked example: the general method in one picture
Every circuit can be cleaned up the same way, in three stages. Written on each wire is what it holds between stages.
First C computes, leaving the answer f(x) on one of its wires and garbage on the others.
Then a single gate copies the answer onto a new wire that started at 0. Then the gates of C run in
reverse order. Each Toffoli gate is its own reverse, so this undoes C step by step, returning every wire
of C to where it started. Only the copy survives. The circuit above is a small case where the last stage
is short. 1.29 states this for every circuit.
1.29Theorem. Suppose a circuit C of
g Toffoli gates takes an input x, with extra bits set to 0, to outputs that include f(x)
on one wire. Then a circuit of 2g + 1 Toffoli gates, with two more extra bits, takes x with its
extra bits to x, all extra bits back at their starting values, and f(x) on one new wire.
Add a wire set to 1 and a wire set to 0. Run C. Copy the answer wire onto the new 0 wire
with one Toffoli gate controlled by the 1 wire and the answer wire. Then run the gates of C in reverse
order. Each gate is its own reverse by 1.28, so this undoes C, provided nothing C uses was changed
in between; the copy only read the answer wire and wrote to a wire C never touches.
The cost is time and space: twice the gates, and extra wires that must exist while the computation runs. In
return nothing is erased. The circuit above is a small case of the same method. Its last gate already writes the
answer onto a fresh wire, out, that nothing else uses, so no copy is needed, and only the gate that made
garbage has to be undone: 3 gates rather than the 2 · 2 + 1 = 5 that 1.29 allows.
Exercise 1.L
How many different reversible gates are there on 3 bits? Compare with the number of gates that take 3 bits to 3 bits, reversible or not.
By 1.27 a reversible gate pairs the 8 inputs with the 8 outputs one to one.
8! = 40,320 reversible gates. A gate from 3 bits to 3 bits chooses one of 8 outputs for each of 8 inputs: 88 = 16,777,216. Fewer than one in four hundred can be run backwards.
On n bits there are (2n)! reversible gates. Ch. 39 meets the quantum version: not a finite list but a continuous family.
Exercise 1.M
The Toffoli gate with its first control set to 1 is called CNOT: it sends b, c to b, c ⊕ b. Prove that no circuit of CNOT gates, with any extra wires set to 0, computes a ∧ b.
Compare Exercise 1.I.
What does each wire carry, as a function of the inputs, after each gate?
By induction over the gates, every wire carries an exclusive or of some of the inputs: true at the start, since inputs carry themselves and extra wires carry the empty exclusive or, 0; and a CNOT replaces c by c ⊕ b, an exclusive or of two such sums, which is again one. a ∧ b is T in one of four rows, and no exclusive or of inputs is.
So the Toffoli gate is universal only because of its second control: the ∧ inside it. In ch. 39 and ch. 46 the quantum CNOT returns, and the same kind of argument shows why circuits of certain quantum gates can be simulated quickly on an ordinary computer.
Where this chapter goes
Every idea above returns. Select a place to see what carries over.
The unnamed truth function
Every truth function of two letters on this page has been given a name except one, which appears twice: T F T T,
and the same truth function with p and q exchanged, T T F T. Nothing about it is hidden. By 1.18 it is
¬p ∨ q, and you can type it into any box above. What is missing is why it deserves the name ordinary
language gives it, a name that every proof in this book will lean on.