Truth tables¶
Logic and puzzles · level 4, lesson 2 of 6
A question to start¶
Here are two ways to describe a dry, calm day:
- "It is not the case that it is rainy or windy."
- "It is not rainy and it is not windy."
Do they always mean the same thing, on every possible day? You could argue about it with words for a long time. Or you could check every kind of day there could be. With two things (rainy or not, windy or not) there are only four kinds of day, so you can check them all in a minute.
That is what a truth table does. It is a short, complete list of every possible case, and it settles questions like this one for certain. By the end of the lesson you will be able to build one for any statement made with \(\neg\), \(\land\) and \(\lor\), even with three letters and eight cases.
The idea¶
One row for each possible case¶
Each letter in a statement can be T or F. A row of a truth table is one choice of T or F for every letter. The table has one row for each possible choice, so that no case is left out.
- One letter, \(p\): 2 rows (T, F).
- Two letters, \(p\) and \(q\): each of the 2 choices for \(p\) goes with each of the 2 choices for \(q\): \(2 \times 2 = 4\) rows.
- Three letters: \(2 \times 2 \times 2 = 8\) rows.
A tree shows why the number doubles with each new letter. Each branch splits in two.
With \(n\) letters there are \(2^n\) rows: 16 for four letters, 32 for five, and 1024 for ten. (Powers of 2 are in Numbers.)
A standard order¶
To be sure you have every row exactly once, write them in the same order every time. Read the tree from top to bottom:
- The first letter's column: half T, then half F. (For three letters: T T T T F F F F.)
- The second letter: halves of that: T T F F T T F F.
- The last letter: T F T F T F T F, changing every row.
If you count T as 1 and F as 0, the rows count down in binary from 111 to 000. That is a neat check: no row repeated, none missed.
Build it one column at a time¶
To find the truth table of a big statement, break it into pieces, smallest first, and give each piece its own column. Work out each column from earlier columns using the rules from lesson 1:
- \(\neg\): flip.
- \(\land\): T only if both are T.
- \(\lor\): F only if both are F.
Example: the question to start. Let \(p\): "rainy" and \(q\): "windy". We compare \(\neg(p \lor q)\) with \(\neg p \land \neg q\).
| \(p\) | \(q\) | \(p \lor q\) | \(\neg(p \lor q)\) | \(\neg p\) | \(\neg q\) | \(\neg p \land \neg q\) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
The two bold columns agree in every row. So in every possible kind of day, the two sentences are both true or both false. They say the same thing.
Logically equivalent¶
Two statements whose truth tables agree in every row are called logically equivalent. We write \(\equiv\):
A truth table is a proof of an equivalence, because it checks every case there is. Nothing is left to chance. Compare that with checking examples in arithmetic: testing \(n = 1, 2, 3\) does not check every whole number, because there are infinitely many. Here there are only four cases, and we checked all of them.
This equivalence, and its partner \(\neg(p \land q) \equiv \neg p \lor \neg q\), are De Morgan's laws, after the 19th-century mathematician Augustus De Morgan. You will use them a lot in level 5.
Always true, always false¶
Some statements come out T in every row. They are called tautologies. The simplest is \(p \lor \neg p\): "it is raining or it is not raining". Whatever the weather, it is true.
| \(p\) | \(\neg p\) | \(p \lor \neg p\) | \(p \land \neg p\) |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
Statements that are F in every row, like \(p \land \neg p\) ("it is raining and it is not raining"), are called contradictions. A contradiction can never be true. When a knights-and-knaves case led to "A is a knight and A is not a knight", that was a contradiction, and that is why we crossed the case off.
When two statements are not equivalent¶
To show two statements are not equivalent, you only need one row where they differ. Compare \(p \land (q \lor r)\) with \((p \land q) \lor r\):
| row | \(p\) | \(q\) | \(r\) | \(q \lor r\) | \(p \land (q \lor r)\) | \(p \land q\) | \((p \land q) \lor r\) |
|---|---|---|---|---|---|---|---|
| 1 | T | T | T | T | T | T | T |
| 2 | T | T | F | T | T | T | T |
| 3 | T | F | T | T | T | F | T |
| 4 | T | F | F | F | F | F | F |
| 5 | F | T | T | T | F | F | T |
| 6 | F | T | F | T | F | F | F |
| 7 | F | F | T | T | F | F | T |
| 8 | F | F | F | F | F | F | F |
Rows 5 and 7 differ. So they are not equivalent: here the brackets change the meaning. (In row 5, say \(p\): "I finish my homework", \(q\): "it is sunny", \(r\): "it is my birthday". With \(p\) false and \(r\) true, "I finish my homework and it is sunny or my birthday" is false, but "I finish my homework and it is sunny, or it is my birthday" is true.)
Worked examples¶
1. "Or, but not both." Build the table for \((p \lor q) \land \neg(p \land q)\).
| \(p\) | \(q\) | \(p \lor q\) | \(p \land q\) | \(\neg(p \land q)\) | \((p \lor q) \land \neg(p \land q)\) |
|---|---|---|---|---|---|
| T | T | T | T | F | F |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| F | F | F | F | T | F |
It is true exactly when one of \(p\), \(q\) is true. This is the "menu" meaning of or, called exclusive or.
2. A distributive law. Show \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\).
From the big table above, the column \(p \land (q \lor r)\) reads T T T F F F F F. Now \(p \land r\) reads T F T F F F F F (T only when \(p\) and \(r\) are both T: rows 1 and 3). So \((p \land q) \lor (p \land r)\) is T when either \(p \land q\) (rows 1, 2) or \(p \land r\) (rows 1, 3) is T: rows 1, 2, 3. It reads T T T F F F F F. The columns match, so the two are equivalent. This is just like \(a \times (b + c) = a \times b + a \times c\) in arithmetic, with \(\land\) for \(\times\) and \(\lor\) for \(+\).
3. A knights-and-knaves puzzle by table. A says: "At least one of us is a knave." Let \(a\): "A is a knight" and \(b\): "B is a knight". A's statement is \(\neg a \lor \neg b\). A knight's statement must be true and a knave's false, so we need the statement's truth value to match \(a\).
| \(a\) | \(b\) | \(\neg a \lor \neg b\) | matches \(a\)? |
|---|---|---|---|
| T | T | F | no |
| T | F | T | yes |
| F | T | T | no |
| F | F | T | no |
Only one row fits: A is a knight and B is a knave, the same answer as in level 3. The truth table did all the case-trying at once.
Try it¶
- How many rows does a truth table with 4 letters have? With 6?
- Write the first column (\(p\)), second (\(q\)) and third (\(r\)) of a three-letter table in the standard order.
- Build the truth table for \(\neg p \land q\).
- Build the truth table for \(\neg(p \land q)\) and for \(\neg p \lor \neg q\). Are they equivalent?
- Is \(p \lor (p \land q)\) equivalent to \(p\)? Use a table.
- Is \(p \land \neg p\) a tautology, a contradiction, or neither? What about \((p \land q) \lor \neg p\)?
- Find the row (truth values of \(p\), \(q\), \(r\)) where \(p \lor (q \land r)\) and \((p \lor q) \land r\) differ, if there is one.
- Use a truth table to solve: A says "B is a knight", and B says "A is a knave". (Use \(a\) and \(b\) as in worked example 3; this time both statements must match their speakers.)
Answers
- \(2^4 = 16\) rows; \(2^6 = 64\) rows.
- \(p\): T T T T F F F F. \(q\): T T F F T T F F. \(r\): T F T F T F T F.
- Rows (\(p\), \(q\)): TT gives F, TF gives F, FT gives T, FF gives F. It is true only when \(p\) is false and \(q\) is true.
- \(\neg(p \land q)\): the column \(p \land q\) reads T F F F, so \(\neg(p \land q)\) reads F T T T. \(\neg p \lor \neg q\): \(\neg p\) reads F F T T and \(\neg q\) reads F T F T, and "or" gives F T T T. The same, so they are equivalent (De Morgan's other law).
- \(p \land q\) reads T F F F. Then \(p \lor (p \land q)\) reads T T F F (TT: T; TF: T; FT: F or F = F; FF: F). And \(p\) reads T T F F. Equivalent. (In words: "\(p\), or \(p\) and \(q\)" adds nothing beyond \(p\).)
- \(p \land \neg p\) is a contradiction (F in both rows). For \((p \land q) \lor \neg p\): TT gives T or F = T; TF gives F or F = F; FT gives F or T = T; FF gives T. It has one F and three T, so it is neither.
- Look for a row where one is T and the other F. Try \(p\) T, \(r\) F: \(p \lor (q \land r)\) is T (because \(p\) is T), but \((p \lor q) \land r\) is F (because \(r\) is F). So rows \(p\) T, \(q\) T, \(r\) F and \(p\) T, \(q\) F, \(r\) F both differ. Not equivalent.
- A's statement is \(b\); it must match \(a\), so \(a\) and \(b\) must be equal. B's statement is \(\neg a\); it must match \(b\), so \(b\) must be the opposite of \(a\). Row TT: B's fails. TF: A's fails. FT: A's fails. FF: B's statement \(\neg a\) is T but \(b\) is F, fails. No row fits, so these two statements cannot both be said on the island, as we found in level 3.
Common mistake¶
Missing or repeating a row. If you write rows in a random order, it is easy to have two rows the same and miss another. Always use the standard order (halves, then quarters, then alternating), and count: you need \(2^n\) rows.
Doing too much in one step. Working out \(\neg(p \lor q) \land r\) in your head is how mistakes slip in. Give every piece its own column, smallest pieces first, and each step is easy.
Where it leads¶
- Back: Statements and letters · Next: The conditional, the connective with the surprising table.
- Level 4 page · Logic topic page
- The \(2 \times 2 \times 2\) rule for counting rows is the multiplication principle of Counting.
- Truth tables become circuits: AND, OR and NOT gates inside computers, in level 6.
- The distributive law in arithmetic and algebra: Algebra.