← Quantum Field Theory

1 · Propositional logic and Boolean circuits

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:

  1. What counts as a statement, and what does not?
  2. How many ways are there to combine two statements, and how few suffice to build them all?
  3. When do two formulas say the same thing, and what are the laws that let us replace one by the other?
  4. Which questions cannot be asked at once, and why does that matter for quantum mechanics?
  5. How do circuits perform arithmetic, and what happens when the circuits are wrong?
  6. 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?

    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 conjunction p ∧ q (“p and q”) is true exactly when both are true; the disjunction p ∨ q (“p or q”) is true exactly when at least one is true.
    pq¬pp ∧ qp ∨ q
    TTFTT
    TFFFT
    FTTFT
    FFTFF

    “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 letters p, 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.8

    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.
    Exercise 1.C
    Prove that every formula has as many left parentheses as right ones.
    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.

    ExampleWhat it isHas a truth value?
    Statement7 is primeA sentence of mathematicsYes, by 1.2
    Formula(p ∧ ¬q)A string of symbols, 1.4Only under an assignment
    Truth functionF T F FA rule from rows to values, 1.10No; 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 ∨.

    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
    Idempotencep ∧ p ≡ p,   p ∨ p ≡ p
    Commutativityp ∧ q ≡ q ∧ p,   p ∨ q ≡ q ∨ p
    Associativity(p ∧ q) ∧ r ≡ p ∧ (q ∧ r),   (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
    Distributivityp ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r),   p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
    De Morgan¬(p ∧ q) ≡ ¬p ∨ ¬q,   ¬(p ∨ q) ≡ ¬p ∧ ¬q
    Absorptionp ∧ (p ∨ q) ≡ p,   p ∨ (p ∧ q) ≡ p
    Excluded middlep ∨ ¬p is a tautology
    Non-contradictionp ∧ ¬p is a contradiction

    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 ∨ ¬¬qDe Morgan, with ¬q in place of q: allowed by substitution, 1.16
    ≡ ¬p ∨ qdouble 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
    ≡ pq ∨ ¬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.

    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 point
    A line through the centre
    The 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?

    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:

    RowConjunctionT only in this row because
    T, Fp ∧ ¬qit needs p true and q false
    F, T¬p ∧ qit 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.

    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.

    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:

    PartValueWhy
    p, qT, Tthis is the all-T row
    p ∨ qTT ∨ T
    q ∨ pTT ∨ T
    p ∧ (q ∨ p)TT ∧ T
    the whole formulaTT ∧ 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.

    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:

    Columna + b + c= sum + 2 · carryboth sides × 2column
    00 + 1 + 0 = 11 + 2 · 01 = 1
    11 + 0 + 0 = 11 + 2 · 02 = 2
    21 + 1 + 0 = 20 + 2 · 18 = 0 + 8 (carry out)
    30 + 0 + 1 = 11 + 2 · 08 (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.

    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 circuit
    Three 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.

    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 chain
    Three chains, one vote at the end
    Three 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.

    inputextranew wire C copy C runbackwards x00xgarbage, f(x)0xgarbage, f(x)f(x)x0f(x)

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

    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.

    Decide whether this is true.

    If 2 + 2 = 5, then 7 is not prime.