Truth tables: and, or, not as calculation
The word "or" has two meanings in English. Truth tables fix one, and turn questions about what sentences mean into finite calculations you can check row by row.
A restaurant menu says that the set lunch comes with soup or salad. The manual of a fire alarm says that it sounds if it detects smoke or heat. Now let both things happen at once. Ask the waiter for soup and salad, and you will be told to choose one. Fill the kitchen with smoke and heat together, and nobody expects the alarm to stay quiet on the grounds that it was only promised one of them.
The same two-letter word did opposite jobs. On the menu, “or” ruled out having both, and in the manual it allowed both. English leaves the choice to context, and most of the time context is enough. It stops being enough when the sentence gets long (“the valve opens if the pressure is high and the pump is off or the override is set”), or when the sentence is a step in a proof and the wrong reading makes the proof false.
Logic repairs this in the bluntest way available. It lists every situation that could arise and records, for each one, whether the compound sentence counts as true. The list is called a truth table. Once sentences have tables, a question such as “do these two sentences say the same thing?” is settled by a finite calculation, and the ear is no longer consulted.
Statements, and the two meanings of “or”
First we have to say which sentences are allowed in.
“7 is a prime number” is a statement, with truth value T, and “London is in France” is one with truth value F. “Every even number greater than 2 is a sum of two primes” is a statement even though nobody knows its truth value, because it has one. “Close the door” and “Is it raining?” are not statements. Neither is “$x > 3$”, since whether it is true depends on an $x$ we have not been given; sentences with a free variable are handled later in this series, with quantifiers.
Now take the alarm. Write $S$ for “there is smoke” and $H$ for “there is heat”. At a given moment each is true or false, so there are four possible situations: both, smoke only, heat only, neither. What the alarm does is a decision in each of the four. Do the same for the menu, with “you take soup” and “you take salad”, and put the two side by side.
The alarm’s column is true in three rows and the menu’s in two. They differ only in the first row, where both parts are true. Mathematicians had to pick one meaning for the bare word, and they picked the alarm’s: in mathematics “or” always means “one or the other or both”. This is the inclusive or. The menu’s meaning is the exclusive or, and we will build it out of other pieces in a moment.
Two more small words get the same treatment. “There is smoke and there is heat” is true in the first row only. “There is no smoke” is true exactly when $S$ is false.
The table is the definition. It makes no appeal to what “and” means in conversation, and that has a cost you should see clearly. A connective defined by a table can see only the truth values of its parts. “It is smoky but not hot” becomes $S \land \lnot H$: the note of surprise in “but” is dropped, because it has no effect on whether the sentence is true. And “because” cannot be given a table at all: knowing that $S$ and $H$ are both true does not tell you whether one caused the other.
Pause and try
Using only $\land$, $\lor$ and $\lnot$, write a formula in $P$ and $Q$ that has the menu’s column: true when exactly one of $P$, $Q$ is true. Check it in all four rows.
Show answerHide answer
One answer is $(P \lor Q) \land \lnot(P \land Q)$, “at least one, and not both”. In the row T, T it is $\text{T} \land \lnot \text{T}$, which is F. In the rows T, F and F, T it is $\text{T} \land \lnot \text{F}$, which is T. In the row F, F the first part is already F. Another answer is $(P \land \lnot Q) \lor (\lnot P \land Q)$, “the first without the second, or the second without the first”. Both are right, and we will soon say what that means.
Switches: a machine that computes the tables
The animation at the top of the page is these definitions built out of wire. A switch is closed or open, and the lamp is lit exactly when there is an unbroken path from the battery through the lamp and back. Let $P$ be the statement “switch $P$ is closed”, and likewise $Q$.
When the switches are in series, the current must pass through both, so the lamp is lit exactly when $P \land Q$ is true. When they are in parallel, either branch will carry the current, so the lamp is lit exactly when $P \lor Q$ is true. Compare the tiles under each circuit with the columns of the definition. For $\lnot P$, use a switch that is sprung the other way round, so that it is closed when its button is not pressed.
The circuit is a model of the table: a system with one part for each statement, two states for each part, and a behavior that agrees with the table in every row. Nothing about electricity enters the logic. What the model gives us is a second way to compute. In 1937 Claude Shannon observed that relay circuits obey exactly these tables, and digital circuits have been designed by this algebra ever since.
The table of a compound statement
Connectives can be nested, with parentheses to show the order, as in $\lnot(P \land Q)$. By convention $\lnot$ applies to the shortest thing after it, so $\lnot P \lor Q$ means $(\lnot P) \lor Q$. Between $\land$ and $\lor$ I will always write the parentheses.
A formula with $n$ different letters has a table with $2^n$ rows, because each letter is independently T or F: 4 rows for two letters, 8 for three. To fill in the table, work from the inside out, one column at a time, each new column computed from columns already there.
Here is a case that matters. An inspector reports of the kitchen: “it is not the case that there is both smoke and heat”. That is $\lnot(S \land H)$. What does it tell us about smoke and heat separately?
Pause and try
Which of these is the same as $\lnot(P \land Q)$: (a) $\lnot P \land \lnot Q$, or (b) $\lnot P \lor \lnot Q$? Before computing whole tables, test both in the single row where $P$ is true and $Q$ is false.
Show answerHide answer
In that row $P \land Q$ is F, so $\lnot(P \land Q)$ is T. Formula (a) gives $\text{F} \land \text{T}$, which is F, so (a) is not the same. Formula (b) gives $\text{F} \lor \text{T}$, which is T. One row can rule a candidate out but cannot rule one in; the figure checks (b) in the other three rows.
The natural guess is to push the “not” inside the way a minus sign goes through a sum, and it fails. In words: “not both smoky and hot” does not say that the kitchen is neither. It says that at least one of the two is missing, and when a $\lnot$ moves inside the parentheses the $\land$ has to turn into $\lor$.
Logical equivalence
We have now twice met two formulas with the same column: the two formulas for the menu’s “or”, and the pair in the figure. That relationship deserves a name.
For example $P \lor \lnot P$ is a tautology and $P \land \lnot P$ is a contradiction; each has only two rows to check. Note that $\equiv$ is not a fourth connective. $A \equiv B$ is a claim about two formulas, and it is either established by comparing tables or refuted by a single row. Because a connective sees only truth values, a part of a formula may always be replaced by an equivalent part without changing the table of the whole. That is what makes the following laws usable as rules of algebra.
A table is a proof because it is exhaustive: the rows cover every case there is, and each entry follows from the definitions.
The first distributive law has the shape of $a(b + c) = ab + ac$, with $\land$ as multiplication and $\lor$ as addition. The second has no counterpart in arithmetic, where $a + bc$ is not $(a + b)(a + c)$.
The switch model shows the first law as a fact about wiring. Build one circuit for each side and try all eight switch positions.
To an engineer the equivalence says the two circuits are interchangeable, and the left one is cheaper, with three switches where the right one needs four.
Venn diagrams are truth tables too
There is a third way to see these laws, and it is the one most people meet first. Draw a box for all the situations under discussion, a circle enclosing those in which $P$ is true, and a second circle enclosing those in which $Q$ is true. Then $P \land Q$ is the overlap of the circles, $P \lor Q$ is everything inside at least one of them, and $\lnot P$ is everything outside the circle for $P$.
The picture is a proof, provided you see why. The four regions are the four rows, and shading a region is writing T in that row. A Venn argument is a truth table drawn in the plane, so it can be trusted exactly when the drawing contains a region for every combination of truth values. Two overlapping circles give all 4 combinations, and three in the usual arrangement give all 8. Four circles cannot give all 16, because four circles divide the plane into at most 14 regions, so for four letters the circle picture breaks down while the table carries on.
Worked examples
Every truth table has a formula
We have three connectives. The number of possible tables is much larger: a table on two letters has 4 rows, each of which may be T or F, so there are $2^4 = 16$ different columns, and on three letters there are $2^8 = 256$. Are some of them out of reach of $\land$, $\lor$ and $\lnot$?
The exclusive or shows what to do. Its column is true in the rows (T, F) and (F, T). The formula $P \land \lnot Q$ is true in the row (T, F) and in no other row. The formula $\lnot P \land Q$ is true in the row (F, T) and in no other. Join them with “or” and the result is true in exactly those two rows. The same recipe works on any column whatever. Here it is on a column with three letters: a vote among three sensors, true when at least two of them fire.
The formula produced by this proof is called the disjunctive normal form of the table. For the vote it is
The theorem promises a formula and makes no promise of a short one. The vote is also given by $(P \land Q) \lor (P \land R) \lor (Q \land R)$, which is less than half as long. A set of connectives that can express every truth table is called functionally complete, and the theorem says that $\{\land, \lor, \lnot\}$ is such a set.
Pause and try
Write the disjunctive normal form for the table on $P$, $Q$ whose column, in the usual order of rows, is T, F, T, T. Then find a shorter formula with the same column.
Show answerHide answer
The true rows are (T, T), (F, T) and (F, F), so the normal form is $(P \land Q) \lor (\lnot P \land Q) \lor (\lnot P \land \lnot Q)$. For something shorter, look at the single false row instead: the column is false exactly when $P$ is true and $Q$ is false, so it is $\lnot(P \land \lnot Q)$, which by De Morgan and double negation is $\lnot P \lor Q$. This column belongs to “if $P$ then $Q$”, the subject of the next lesson.
One connective is enough
Three connectives suffice, and fewer will do. De Morgan’s second law, negated on both sides, gives $P \lor Q \equiv \lnot(\lnot P \land \lnot Q)$, so every $\lor$ can be traded for $\land$ and $\lnot$, and the pair $\{\land, \lnot\}$ is already complete. We cannot drop $\lnot$ and keep going (a problem below asks you to prove it), but we can fuse the two survivors into one. Define a new connective, written $P \uparrow Q$ and called NAND for “not and”, by
Its column is F, T, T, T: false only when both parts are true.
Chip designers care, because one kind of gate is the easiest thing to manufacture in bulk. The Apollo guidance computer was built entirely from a three-input relative of NAND called NOR, which a problem below investigates.
Where truth tables stop
A sentence must have a truth value before it can enter a table. “This sentence is false” has none that is consistent, since if it is true then it is false, and if it is false then it is true. And words such as “because” or “probably” are not connectives of this kind at all.
Tables grow fast. Twenty letters need $2^{20} = 1{,}048{,}576$ rows, and 300 letters need more rows than there are atoms in the observable universe. For formulas of that size, equivalences are established by algebra with the laws above.
Stepping back
The hard part of this subject is at the very start: agreeing to let a table, and nothing else, say what a connective means. After that everything was computation. Equivalence became “same column”, proof became “check every row”, and De Morgan’s laws became facts about small tables that can be used as algebra on large formulas. The reusable idea is that a claim about finitely many cases can be settled by listing the cases, and that a circuit or a Venn diagram proves something exactly when it is such a list in disguise. The next lesson applies the same method to the connective that people most often get wrong: “if ... then”.
Check yourself
Which formula is logically equivalent to $\lnot(P \lor Q)$?
Problems
Problems 1 and 2 repeat the moves of the lesson. Problems 3 and 4 ask you to combine them. Problems 5 and 6 go further.
Problem 1
Compute the truth table of $P \land (\lnot P \lor Q)$ and find a shorter equivalent formula. Then get the same answer with the distributive law.
Show solutionHide solution
In the rows (T, T), (T, F), (F, T), (F, F) the column of $\lnot P \lor Q$ is T, F, T, T. Taking “and” with the column of $P$, which is T, T, F, F, gives T, F, F, F. That is the column of $P \land Q$. By the distributive law, $P \land (\lnot P \lor Q) \equiv (P \land \lnot P) \lor (P \land Q)$; the first bracket is a contradiction, and “F or $X$” has the value of $X$, leaving $P \land Q$.
Problem 2
Use De Morgan’s laws to write the negation of each without a “not” in front of the whole thing. (a) “$n$ is even and $n$ is greater than 10.” (b) “I will take the bus or I will walk.” (c) $\lnot P \lor Q$.
Show solutionHide solution
(a) $\lnot(E \land G) \equiv \lnot E \lor \lnot G$: “$n$ is odd or $n$ is at most 10”. (b) $\lnot(B \lor W) \equiv \lnot B \land \lnot W$: “I will not take the bus and I will not walk”. (c) $\lnot(\lnot P \lor Q) \equiv \lnot\lnot P \land \lnot Q \equiv P \land \lnot Q$, using De Morgan and then double negation. Check (c) in the row $P$ true, $Q$ false: $\lnot P \lor Q$ is F, so its negation is T, and $P \land \lnot Q$ is $\text{T} \land \text{T}$, which is T.
Problem 3
A column on $P$, $Q$, $R$ is true exactly when an odd number of the three letters are true. Write its disjunctive normal form, and verify it in the rows (T, F, F) and (T, T, F).
Show solutionHide solution
The rows with an odd number of T’s are (T, T, T), (T, F, F), (F, T, F) and (F, F, T). So the normal form is
In the row (T, F, F) the second conjunction is $\text{T} \land \text{T} \land \text{T}$, so the formula is T, as wanted. In the row (T, T, F) the first conjunction fails at $R$, the second at $\lnot Q$, and the third and fourth at $\lnot P$, so the formula is F, as wanted.
Problem 4
The connective NOR is defined by $P \downarrow Q = \lnot(P \lor Q)$. Express $\lnot P$, $P \lor Q$ and $P \land Q$ using $\downarrow$ alone, and conclude that NOR by itself is functionally complete.
Show solutionHide solution
Not: $P \downarrow P = \lnot(P \lor P) \equiv \lnot P$, because $P \lor P$ has the value of $P$. Or: $(P \downarrow Q) \downarrow (P \downarrow Q) \equiv \lnot(P \downarrow Q) = \lnot\lnot(P \lor Q) \equiv P \lor Q$. And: $(P \downarrow P) \downarrow (Q \downarrow Q) \equiv \lnot P \downarrow \lnot Q = \lnot(\lnot P \lor \lnot Q) \equiv \lnot\lnot P \land \lnot\lnot Q \equiv P \land Q$, by De Morgan and double negation. Since every truth table has a formula in $\land$, $\lor$, $\lnot$, and each of those can be rewritten with $\downarrow$, every truth table has a formula in $\downarrow$ alone.
Problem 5
Find the error. “Claim: $P \lor (Q \land R) \equiv (P \lor Q) \land R$. Proof: when all three letters are true both sides are true, and when all three are false both sides are false. So the two sides agree.” Give a row in which the two sides differ, and state the correct law.
Show solutionHide solution
The proof checks two rows out of eight. Take $P$ true, $Q$ false, $R$ false. The left side is $\text{T} \lor (\text{F} \land \text{F})$, which is T. The right side is $(\text{T} \lor \text{F}) \land \text{F}$, which is F. So the claim is false. The correct law distributes $P$ to both parts: $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$. In the same row the right side of that is $\text{T} \land \text{T}$, which is T.
Problem 6
Prove that $\{\land, \lor\}$ without $\lnot$ is not functionally complete. (Hint: what is the truth value of a formula built from letters with only $\land$ and $\lor$ in the row where every letter is true?)
Show solutionHide solution
We show that every formula built from letters using only $\land$ and $\lor$ is true in the row where all letters are true. Argue by induction on the number of connectives: prove it for formulas with none, and show that if it holds for all formulas with fewer than $k$ connectives then it holds for those with $k$. A formula with no connectives is a single letter, which is true in that row. A formula with $k \ge 1$ connectives is $A \land B$ or $A \lor B$, where $A$ and $B$ have fewer connectives, so both are true in that row, and then $A \land B$ and $A \lor B$ are true there too. Now the column of $\lnot P$ has F in the row where $P$ is true. No formula in $\land$ and $\lor$ alone has an F in the all-true row, so none has the table of $\lnot P$.