Logic

Before we set off for Athens, here is a sentence of the kind you might hear on the news. A politician declares:

“The presumption of innocence applies. For an ordinary citizen it is sacred and inviolable. For a politician, however, the presumption of guilt applies.”

Is that one statement? Which parts are claims whose truth can be decided, and which only express a judgement or give an order?

The word logic itself comes from the Greek logos – word, speech, reason, reckoning. So logic began as rules for speech. That is the first clue as to why linguists later enter its story.

The whole chapter in one sentence: logic began as the rules of correct speech, the Stoics turned it into calculating with truth, Boole turned truth into the number 1 and falsehood into 0, and Shannon built circuits out of it. At each stop you will see where you meet the idea in code today.

“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.”— Lewis Carroll, Through the Looking-Glass, 1871

How can you tell that a conclusion really follows, and doesn’t merely sound convincing?

In Athens in the 5th and 4th centuries BCE, everything was decided by speech: in the popular assembly, in court, where people defended themselves, and in the agora. The Sophists taught for money how to win an argument, not how to be right. Plato reproached them for it, and his student Aristotle asked a more precise question: are there rules by which one can mechanically tell that an argument is valid, regardless of who makes it and how nicely?

Aristotle (384–322 BCE) wrote down his answer in works that his students later called the Organon – “the tool”. For him logic was not a science about the world but a tool for all the other sciences. That is exactly how a programmer uses it today.

Aristotle’s discovery: whether an argument is valid does not depend on what we are talking about, but on its form. So he began writing letters instead of words – the very first use of variables in the history of logic, two thousand years before algebra.

// first premise: the rule
  if (human(x)) mortal(x) = true;
  // second premise: the data
  human("Socrates") == true;
  // conclusion
  mortal("Socrates") == true;

The flying cat: truth is not the same as validity

All cats can fly. Felix is a cat. ⟹ Felix can fly. The premise and the conclusion are nonsense, and yet the argument is logically valid: its form is the same as with Socrates. If the premises held, the conclusion would have to hold. Logic does not check whether the input words are true, but whether the inner logical structure works.

Garbage in, garbage out: a correct program with bad data gives a bad result. And conversely, a correct result does not yet mean that the program is correct:

The laws Aristotle considered the firmest

In the Metaphysics (Book IV) Aristotle argues that the most certain of all principles is the law of non-contradiction: nothing can both be and not be in the same sense. Right next to it he formulates the law of the excluded middle: of any thing, one must either affirm something or deny it; there is nothing in between. These two laws are the root of two-valued logic – and so of the boolean type, which has exactly two values and nothing in between.

A curiosity: in On Interpretation Aristotle himself hesitated over whether the law of the excluded middle also applies to the future. Is the statement “There will be a sea battle tomorrow” already true or false today?

“It is raining.” – “Is it raining?” – “Let it rain!” Three sentences about the same thing. Of which of them does it make sense to ask whether it holds?

Aristotle worked with terms (humans, mortals). The Stoics in the 3rd century BCE, above all Chrysippus of Soli (c. 279–206 BCE), began working with whole sentences. They introduced the concept of the axíōma, which corresponds to our “statement”, and defined it precisely by truth: a statement is something that is either true or false.

The Stoics also studied how the truth of a compound sentence depends on the truth of its parts: “and”, “or”, “if… then”. They argued so fiercely about implication that the poet Callimachus is said to have written that even the crows on the roofs were cawing about which implication was the right one. The winner was the definition of Philo of Megara: the sentence “if A, then B” is false only when A holds and B does not. That is exactly the third column of today’s table, 2200 years older than the table itself.

We know the remark about Callimachus’s crows only from later authors (Sextus Empiricus). The Stoic logical works have not survived; we know about Chrysippus mainly from Diogenes Laertius (Lives of the Eminent Philosophers, Book VII).

Chrysippus also set down five basic rules of inference. The most famous of them we know today as modus ponens: If A, then B. A holds. ⟹ B holds.

The liar paradox: when a statement has no truth value

As early as the 4th century BCE, the paradox “This statement is false” was attributed to Eubulides of Miletus. If it is true, it is false; if it is false, it is true. Chrysippus is said to have written several works about it. The paradox shows the limit of the definition of a statement: not every declarative sentence is a statement.

function liar() {
    if (halts(liar)) while (true) {}  // should I finish? then I won’t
    else return;                      // should I not finish? then I will
  }

Can the laws of correct reasoning be written down as algebra?

Gottfried Wilhelm Leibniz (1646–1716) dreamed of a characteristica universalis, a language in which concepts would be written as signs, and of a calculus ratiocinator, a calculus of reasoning. Disputes would then no longer be settled by quarrelling: two scholars would sit down and say Calculemus! – “let us calculate!”. Leibniz also described the binary system in detail (1703), with its two digits 0 and 1. But he did not yet connect logic and the binary system. That was done a century and a half later by a self-taught man from Lincoln.

George Boole (1815–1864) was the son of a shoemaker from Lincoln; he taught himself mathematics and from the age of 16 worked as a teacher to support his family. Without a university degree he became a professor in Cork, Ireland. In 1847 he published a slim book, The Mathematical Analysis of Logic, and in 1854 his main work, An Investigation of the Laws of Thought. Hence the year 1854 for this chapter.

Boole’s aim was not to build a computer. He wanted to describe how people think as precisely as Newton described motion. He found that arguments can be written down and manipulated like equations.

George Boole 1815–1864, Lincoln – Cork

1. 1815Born in Lincoln into a shoemaker’s family.
2. 1831At 16 he begins teaching to support his family.
3. 1847The Mathematical Analysis of Logic.
4. 1849Professor of mathematics at Queen's College, Cork.
5. 1854An Investigation of the Laws of Thought.
6. 1864Dies of pneumonia at the age of 49.

Alongside Boole worked Augustus De Morgan (1806–1871), who gave his name to the laws ¬(A ∧ B) ⇔ (¬A ∨ ¬B) and ¬(A ∨ B) ⇔ (¬A ∧ ¬B) – the ones a programmer uses every time they rewrite !(a && b) as !a || !b.

Boole did not reason about statements but about classes of things. For him the letter x might mean “white things”, y “sheep”. The product xy was then the intersection: “white sheep”. 1 was the whole universe of discourse, everything we are talking about, and 0 the empty class, nothing.

Then he noticed something odd. White white things are still just white things, so xx = x, that is

x² = x.

In ordinary algebra this equation has only two solutions: x = 0 and x = 1. From this Boole drew a conclusion that changed history: the algebra of thought is ordinary algebra restricted to the numbers 0 and 1. In his second book he then interpreted 1 as “always”, that is truth, and 0 as “never”, that is falsehood.

From the same equation Boole also derived Aristotle’s law of non-contradiction: x − x² = 0, or x(1 − x) = 0. In words: nothing can both have the property x and not have it (1 − x). The oldest law of logic fell out of algebra as a by-product.

If truth is 1 and falsehood 0, can the tables for “not”, “and”, “or” and “if” be calculated instead of learned by heart?

Boole did not draw tables; he calculated with equations. The table as a method arrived only several decades later.

• Gottlob Frege (1879, Begriffsschrift) described precisely when an implication is true by listing all four cases – still in words.
• Charles S. Peirce drew, around 1893 in an unpublished manuscript, a matrix that is today’s truth table for implication. It turned up only among his papers after his death.
• Ludwig Wittgenstein (Tractatus, 1921) and, independently, Emil Post (1921) published the tables and showed that with them one can decide for any propositional formula whether it is a tautology. Wittgenstein in effect defined a tautology as a formula whose result column is all truths.

Frege distrusted natural language: he considered it imprecise and ambiguous, and so he created a language of his own. How logic and language carried on is told on the separate page Language and logic.

Once truth is 1 and falsehood 0, we can look at connectives as arithmetic operations: we put in two numbers, 0 or 1, and get 0 or 1 back. The task: find a formula that gives 1 exactly in those rows where the compound statement is true. Step by step:

1. Negation. We need an operation that turns 1 into 0 and 0 into 1. Subtracting from one does it: 1 − 1 = 0 and 1 − 0 = 1. So ¬p = 1 − p.
2. Conjunction “p and q”. It should hold only when both parts hold. Let’s try the product: 1 · 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 · 0 = 0. A single zero wipes out the whole product, just as a single false part brings down the whole “and”. So p ∧ q = p · q.
3. Disjunction “p or q”. It should hold when at least one part holds. The first idea is the sum p + q. It works in three rows, but for p = q = 1 it gives 2, and there is no 2 in our world. We fix it by subtracting the common part once: p + q − pq. (Boole himself wrote just x + y and meant the exclusive “or”; the inclusive version was championed mainly by W. S. Jevons.)
4. Implication “if p, then q”. According to Philo it is false in a single case: p = 1 and q = 0. We write this “forbidden” case as the product p(1 − q), which is 1 only when p = 1 and at the same time q = 0. The implication holds when the forbidden case has not occurred, so we negate it: p ⇒ q = 1 − p(1 − q).
5. Equivalence “p if and only if q”. It should hold when p and q have the same value. The difference p − q is 0 when they agree and +1 or −1 when they disagree. Squaring removes the sign: (p − q)² is 0 when they agree and 1 when they disagree. All that remains is to flip the result: p ⇔ q = 1 − (p − q)².

Out comes exactly the familiar truth table, this time not learned but calculated. So the table is an algorithm: go through all 2ⁿ combinations and look. It is the first decision procedure in logic – and brute force in its purest form.

For eighty years Boolean algebra was a curiosity for philosophers. Can you build a machine out of it?

In 1937 the twenty-one-year-old Claude Shannon wrote his master’s thesis at MIT, A Symbolic Analysis of Relay and Switching Circuits. He showed that switches connected in series behave like ∧, and switches connected in parallel like ∨. On = 1, off = 0. From that moment any logical argument could be built from wires. Every processor is a pile of Boolean equations.