Building a truth table for a compound statement
A statement mixes several letters and several connectives at once. How do you find its truth value in every possible case, without getting lost?
Where you are 3 in Truth tables
When you reach for it
And, or and not each have a table of their own, four rows or two, small enough to hold in your head. A real statement is rarely just one of them. It joins several smaller statements with several connectives at once, sometimes the same connective more than once, sometimes one connective sitting inside another.
There is no table to memorize for a statement like that, because there are infinitely many such statements. What there is instead is a way to build the table for any one of them, out of the small tables you already have, one column at a time.
Reach for this whenever a statement mixes more than one connective, or uses more than two letters, and you want to know exactly when it is true: not by guessing, and not by working it out fresh for every situation, but by listing every situation once and filling it in.
The procedure
Count the letters, and that fixes the number of rows. Call the number of distinct simple statements in the formula n. Each one can independently be true or false, so there are 2^n combinations to account for, and the table needs exactly 2^n rows: no more, since nothing rules a combination out in advance, and no fewer, since leaving one out is a case the table never covers.
Generate the rows in a fixed order, the same way every time. With two letters, P and Q, the four rows are TT, TF, FT, FF: P is true for the top half and false for the bottom half, and within each half Q alternates. A third letter doubles that to eight rows by splitting every existing row into two, once with the new letter true and once false, so P is true for the top four rows and false for the bottom four, Q alternates in blocks of two, and R alternates every single row:
| Row | P | Q | R |
|---|---|---|---|
| 1 | T | T | T |
| 2 | T | T | F |
| 3 | T | F | T |
| 4 | T | F | F |
| 5 | F | T | T |
| 6 | F | T | F |
| 7 | F | F | T |
| 8 | F | F | F |
A fourth letter would split each of those eight rows again, giving sixteen, and alternating even faster. The order itself is only a convention, but keeping to the same one every time is what lets two tables over the same letters be compared row by row.
Give every sub-formula its own column, and fill them from the inside out. Read the statement the way its parentheses group it: whatever sits inside the most parentheses is built first, because nothing further out can be filled until it exists. A negation needs only the column of what it negates; \wedge and \vee each need the two columns of what they join. Every column after the letters is filled by looking sideways at columns already on the page and reading off the small table for whichever connective made it, never by reasoning about the whole statement at once. One reading rule decides what “inside” means when there are no parentheses: a \neg applies only to the single letter, or the single bracket, written straight after it. So \neg P \wedge Q means (\neg P) \wedge Q, and the negation belongs to P alone; to deny the whole conjunction you must write \neg(P \wedge Q), and the two have different tables. A statement that mixes \wedge with \vee always carries parentheses to say which is done first, since (P \wedge Q) \vee R and P \wedge (Q \vee R) are different statements.
If the same sub-formula appears twice, build its column once. Nothing says a piece can only be used where it is first written down; a repeated piece is filled in once and read twice, which is faster and cannot disagree with itself.
The last column is the answer. Once every sub-formula, down to the whole statement, has a column, the rightmost one lists the statement’s truth value in every case there is, and there is no further case left unaccounted for.
Worked examples
Two letters, one negation
Build a table for \neg P \wedge Q.
SolutionTwo letters give 2^2 = 4 rows: TT, TF, FT, FF. The statement has one sub-formula that is not a letter, \neg P, so it gets its own column, built from the P column alone using the table for not. The final column then combines \neg P with Q using the table for and, true only where both are true.
| Row | P | Q | \neg P | {\neg P \wedge Q} |
|---|---|---|---|---|
| 1 | T | T | F | F |
| 2 | T | F | F | F |
| 3 | F | T | T | T |
| 4 | F | F | T | F |
Two connectives, two columns before the last
Build a table for (P \vee Q) \wedge \neg Q.
SolutionTwo sub-formulas here depend on nothing but the letters: P \vee Q, from the table for or, and \neg Q, from the table for not. Neither needs the other, so they can be built in either order. Only once both exist can the last column combine them with the table for and.
| Row | P | Q | {P \vee Q} | \neg Q | {(P \vee Q) \wedge \neg Q} |
|---|---|---|---|---|---|
| 1 | T | T | T | F | F |
| 2 | T | F | T | T | T |
| 3 | F | T | T | F | F |
| 4 | F | F | F | T | F |
Three letters, the block pattern in full
Build a table for (P \wedge Q) \vee \neg R.
SolutionThree letters give 2^3 = 8 rows, generated as in the procedure: P true for the top four and false for the bottom four, Q alternating every two rows, R alternating every row. P \wedge Q needs only the P and Q columns; \neg R needs only the R column. Once both exist, the last column is their disjunction.
| Row | P | Q | R | {P \wedge Q} | \neg R | {(P \wedge Q) \vee \neg R} |
|---|---|---|---|---|---|---|
| 1 | T | T | T | T | F | T |
| 2 | T | T | F | T | T | T |
| 3 | T | F | T | F | F | F |
| 4 | T | F | F | F | T | T |
| 5 | F | T | T | F | F | F |
| 6 | F | T | F | F | T | T |
| 7 | F | F | T | F | F | F |
| 8 | F | F | F | F | T | T |
Translating words before building
A vending machine dispenses a snack when a coin is inserted and a valid selection is made, or when the manager uses the override key. Build a table for when it dispenses.
SolutionLet P be “a coin is inserted”, Q be “a valid selection is made”, and R be “the manager uses the override key”. The rule reads directly as (P \wedge Q) \vee R: translating comes first, and once it is done the table is built exactly as in the previous example, from the letters inward.
| Row | P | Q | R | {P \wedge Q} | {(P \wedge Q) \vee R} |
|---|---|---|---|---|---|
| 1 | T | T | T | T | T |
| 2 | T | T | F | T | T |
| 3 | T | F | T | F | T |
| 4 | T | F | F | F | F |
| 5 | F | T | T | F | T |
| 6 | F | T | F | F | F |
| 7 | F | F | T | F | T |
| 8 | F | F | F | F | F |
A repeated sub-formula
Build a table for (P \wedge Q) \vee \neg(P \wedge Q).
SolutionP \wedge Q appears twice, once on its own and once inside a negation. Its column is built once, from P and Q, and read both times: once directly, and once as the input to not.
| Row | P | Q | {P \wedge Q} | {\neg(P \wedge Q)} | {(P \wedge Q) \vee \neg(P \wedge Q)} |
|---|---|---|---|---|---|
| 1 | T | T | T | F | T |
| 2 | T | F | F | T | T |
| 3 | F | T | F | T | T |
| 4 | F | F | F | T | T |
The last column is true on every row, however P and Q are chosen. The procedure did nothing special to produce that; it simply shows up as a column of all T’s once the table is finished. A statement with that property has a name of its own, a tautology.
A negation wrapped around a disjunction
Build a table for \neg(P \vee \neg Q) \wedge R.
SolutionWork from the innermost parentheses out. \neg Q comes first, from Q alone. Next is P \vee \neg Q, which needs the P column and the \neg Q column just built. Then the whole of that is negated, giving \neg(P \vee \neg Q), a column built from a single column, the one just before it. Only at the end is that combined with R.
| Row | P | Q | R | \neg Q | {P \vee \neg Q} | {\neg(P \vee \neg Q)} | {\neg(P \vee \neg Q) \wedge R} |
|---|---|---|---|---|---|---|---|
| 1 | T | T | T | F | T | F | F |
| 2 | T | T | F | F | T | F | F |
| 3 | T | F | T | T | T | F | F |
| 4 | T | F | F | T | T | F | F |
| 5 | F | T | T | F | F | T | T |
| 6 | F | T | F | F | F | T | F |
| 7 | F | F | T | T | T | F | F |
| 8 | F | F | F | T | T | F | F |
Three columns stood between the letters and the answer, and each one, like the answer itself, used only columns already on the page.
Boundaries
The method only works for finitely many letters, each with just two values. Building a table lists every combination there is, and the count doubles with every extra letter, 2^n for n letters, so the table only makes sense while n is small enough to write out in full. A statement about every real number, or every object in some collection, has no such letter to begin with, and no table lists infinitely many rows.
Every connective used needs a settled table before its column can be filled. The method is only ever a lookup: it says nothing about where the tables for \wedge, \vee, \neg, or any other connective, came from. A new symbol with no agreed table has nothing to look up.
A letter that never appears in the formula still doubles the rows. To compare a statement in P and Q with one in P, Q and R, both tables must run over the same eight rows, so the first is built on three letters even though it uses two. Nothing breaks: the unused letter R changes fastest, so its column only makes the final column repeat in consecutive matching pairs. The row count depends on how many letters the table is built on, not on how many the formula uses.
Where this goes next
A table built this way answers, in one pass, every question that can be asked about a compound statement from its rows. Two of those questions get their own name: a statement whose last column is true on every row is a tautology, and one whose last column is false on every row is a contradiction. The repeated sub-formula in Example 5 was the first kind.
The same table also settles whether an argument holds: testing an argument is this same table with a use pinned onto it, checking whether the conclusion’s column is ever false while every premise’s column is true.
And the doubling itself, one more letter always doubling the rows, is counting at its plainest: each of n independent yes-or-no choices multiplies the number of possibilities by two.
Exercises
Build the table
Build a table for each statement, two letters.
- P \vee \neg Q
- \neg P \vee (P \wedge Q)
- (P \wedge Q) \vee P
- P \wedge (Q \vee \neg P)
- \neg(\neg P \wedge \neg Q)
- (P \vee Q) \wedge (P \vee \neg Q)
Three letters
Build a table for each statement, three letters, eight rows.
- P \wedge (Q \vee R)
- (P \wedge \neg Q) \vee R
- \neg(P \vee Q) \wedge R
- (P \wedge Q) \wedge (Q \vee R)
- (P \vee R) \wedge \neg(Q \wedge R)
Translate, then build
Choose letters for the simple statements, write the rule in symbols, then build its table.
- “The door opens when the badge is scanned or the code is entered, and the manager has unlocked the panel.”
- “The oven is off and the timer has not gone off.”
- “Neither the smoke alarm nor the carbon monoxide alarm is sounding, and someone is home.”
How many rows
- A statement uses five different letters. How many rows does its table need, and why?
- A statement uses the letters P, Q, R, S. How many rows does its table need, and what does the S column look like, read top to bottom in the fixed order?
Reasoning
- Two people build tables for the same statement but list the rows in a different order from each other. Explain why their final columns still agree on exactly which situations make the statement true, even though the two tables do not look alike side by side.
- Without listing any rows, explain why the column for Q \wedge P must be identical to the column for P \wedge Q, given the same rows in the same order.
- Explain why the column for \neg(P \wedge Q) cannot be filled in before the column for P \wedge Q exists.
- A table is built for three letters, P, Q and R, but the formula being evaluated only uses P and Q. Explain why the table still needs eight rows, and describe the pattern that the final column shows across the rows that agree on P and Q.
Answers
- Rows TT, TF, FT, FF give T, T, F, T. \neg Q is F, T, F, T, and \vee needs at least one true.
- T, F, T, T. \neg P is F, F, T, T and P \wedge Q is T, F, F, F, so at least one of them is true in every row except row 2.
- T, T, F, F. P \wedge Q adds nothing once P is already there; the column matches P’s own.
- T, F, F, F. Q \vee \neg P is T, F, T, T, and P must also be true.
- T, T, T, F. \neg P \wedge \neg Q is true only in the last row, so its negation is false only there.
- T, T, F, F. Both P \vee Q and P \vee \neg Q must be true, which only happens when P itself is true.
- T, T, T, F, F, F, F, F. P is false in rows 5 to 8, which rules them all out; of rows 1 to 4, Q \vee R fails only in row 4, where Q and R are both false.
- T, F, T, T, T, F, T, F. R makes rows 1, 3, 5, 7 true on its own; P \wedge \neg Q is true in rows 3 and 4, which adds row 4.
- F, F, F, F, F, F, T, F. \neg(P \vee Q) is true only in the last two rows, and of those only row 7 also has R true.
- T, T, F, F, F, F, F, F. P \wedge Q already limits it to the first two rows, and Q \vee R holds in both.
- F, T, T, T, F, F, T, F. \neg(Q \wedge R) is false only where Q and R are both true, rows 1 and 5; P \vee R is false in rows 6 and 8. Those four rows are F.
- P: badge scanned, Q: code entered, R: manager has unlocked. The comma puts the “or” inside, so (P \vee Q) \wedge R: T, F, T, F, T, F, F, F.
- P: oven is off, Q: timer has gone off. P \wedge \neg Q: F, T, F, F.
- P: smoke alarm sounding, Q: carbon monoxide alarm sounding, R: someone is home. “Neither ... nor” is \neg P \wedge \neg Q, so (\neg P \wedge \neg Q) \wedge R: F, F, F, F, F, F, T, F.
- 32 rows. Five letters, each doubling the count on its own, give 2^5 = 32: the same doubling argument behind counting independent choices.
- 16 rows. The S column reads T, F, T, F, T, F, T, F, T, F, T, F, T, F, T, F, alternating every single row, the fastest-changing column of all, the way Q did in the two-letter tables and R did in the three-letter ones.
- A row is only a label for one combination of truth values, not part of what the statement means. Whatever order the rows are listed in, the set of combinations making the statement true is the same set; only the order in which it is written down differs, and reading a table row by row never depends on which order came first.
- Q \wedge P and P \wedge Q are filled in from the same two columns, P’s and Q’s, using the same table for \wedge, which only asks whether both inputs are true and does not care which one is named first. Swapping the names changes nothing that table looks at.
- A column for \neg X is built by reading the column for X and reversing every entry, so there is nothing to reverse until X’s own column has been filled in first. Here X is P \wedge Q.
- The table’s row count comes from how many letters are declared, three, not from how many the formula uses, two: 2^3 = 8 rows either way. Since R plays no part in the formula, two rows that agree on P and Q and differ only in R get the same final value. In the fixed order those pairs are rows 1 and 2, 3 and 4, 5 and 6, 7 and 8, so the final column comes in consecutive matching pairs: the four-row column with each entry written twice.