Truth tables

A truth table settles a question about formulas by checking every possible case, one row per case. It grows quickly with the number of sentence letters, but it never gets an answer wrong, and it shows exactly what the connectives mean. If the connectives are new to you, read the basics guide first.

Rows are valuations

Each row gives every sentence letter a truth value, T or F. Such an assignment is called a valuation. A truth table has one row for each valuation, so together its rows cover every case there is.

One letter gives 2 rows. Each new letter doubles the count, because every row splits in two: one where the new letter is T and one where it is F. So n letters give 2ⁿ rows (2 multiplied by itself n times): 4 rows for two letters, 8 for three, 16 for four and 1,024 for ten.

The app lists the letters in alphabetical order and the rows in a fixed order, as forall x does. The first row makes every letter true, and the rightmost letter changes fastest. With P and Q, the rows are TT, TF, FT and FF.

Reading a column

To the right of the letters come the formulas. Each connective in each formula gets a column. The value in that column is the value of the connective’s scope, the part of the formula that it governs. So the column under the main connective gives the value of the whole formula. The app writes each value under its connective’s symbol, and shows the main connective’s column in bold.

Read row 2: P is T and Q is F. So ¬P is F, and ¬P ∨ Q has two false disjuncts, so it is F. In every other row it is T.

Four kinds of question

Above the input, you choose what you are entering. Each choice asks a different question, and the table answers it by looking for particular rows:

• Formula. Is it a tautology (true in every row), a contradiction (false in every row), or contingent (some of each)? The app also says whether it is satisfiable (true in at least one row).
• Two formulas. Are they equivalent, with the same value in every row? Any row where their values differ shows that they are not.
• Set. Is it consistent? It is if at least one row makes every formula in it true.
• Argument. Is it valid? It is if no row makes every premise true and the conclusion false. A row that does is a counterexample, and makes the argument invalid.

The basics guide explains these words more fully.

Solve and Practice

The toolbar switches between two modes.

In Solve, the default, the app fills in the whole table and lists its verdicts under Properties. When particular rows show a verdict, such as the counterexamples of an invalid argument, select the verdict’s card to highlight them.

In Practice, the app fills in the sentence letters and you fill in the columns under the connectives. Click a cell to cycle through T, F and empty, or type T or F to fill it and move down. Then answer the questions under Your verdict and press Check. The app counts your mistakes and marks the wrong cells, without giving the right values away. Exercises open in Practice.

Worked example: an invalid argument

Consider this argument: “If it rained, the street is wet. The street is wet. So it rained.” With P for “it rained” and Q for “the street is wet”, it is P → Q, Q ∴ P. Is it valid?

1. List the sentence letters. The argument uses P and Q. Give each a column, in alphabetical order.
2. Fill in the rows. Two letters give 2² = 4 rows. Under the last letter, Q, alternate T and F. Under P, write T twice and then F twice. Each letter further left changes half as often, so no combination is missed or repeated.
3. Work out the formulas, inside out. The first premise, P → Q, is the only formula with a connective. By the table for →, it is F in row 2, where P is T and Q is F, and T in the other rows. The second premise and the conclusion are single letters, so their columns repeat the columns of Q and P.
4. Mark the premises and the conclusion. The premises are P → Q and Q; the conclusion is P. The app puts ∴ before the conclusion’s column.
5. Look for a counterexample. Go row by row and ask: are both premises T while the conclusion is F? Row 1: the conclusion is T, so no. Row 2: the first premise is F, so no. Row 3: both premises are T and the conclusion is F, so yes. Row 4: the second premise is F, so no.
6. State the verdict. Row 3 is a counterexample, so the argument is invalid.

Row 3 makes P false and Q true: the street is wet, but it did not rain. Perhaps a street cleaner went by. The premises leave that case open, so they do not guarantee the conclusion. This mistake is common enough to have a name: affirming the consequent.

In Solve, the app shows the verdict Invalid; select its card to highlight row 3.

A valid argument

Now take P → Q, Q → R ∴ P → R: “If it rained, the street is wet. If the street is wet, it is slippery. So if it rained, it is slippery.” Three letters give 2³ = 8 rows, and this time the conclusion has a connective of its own.

Only rows 1, 5, 7 and 8 make both premises true, and the conclusion is true in each of them. No row is a counterexample, so the argument is valid. This pattern is called hypothetical syllogism.

Notice the shortcut: a row in which some premise is false can never be a counterexample. So you only need to check the conclusion in the rows where every premise is true.

Short truth tables

A full table doubles with every letter. A short truth table (also called a reverse or partial truth table) works backwards instead: it assumes there is a counterexample and tries to build one. Here it is for the valid argument above.

1. Assume the opposite. Suppose the argument has a counterexample: P → Q and Q → R are T, and P → R is F.
2. Force values. A conditional is F only when its antecedent is T and its consequent is F. So P → R being F forces P to be T and R to be F.
3. Keep going. P → Q is T and P is T, so Q must be T. But Q → R is T and R is F, so Q must be F.
4. Spot the clash. Q cannot be both T and F. The assumption fails: there is no counterexample, and the argument is valid.

For an invalid argument, the same method finds a counterexample. Assume P → Q, Q ∴ P has one: Q is T and P is F. Then P → Q is already T, because its antecedent is F. Every value fits, and the counterexample is P false, Q true: row 3 of the full table.

Sometimes nothing is forced. If P ∨ Q must be T and neither letter has a value yet, there are two ways on: P true, or P false with Q true. You must try each way, and the assumption fails only if every way ends in a clash. So a short table can still take long, when it has many ways to try.

To use it in the app, choose Short table above the input. In Solve, the app runs the search and shows the verdict with a short explanation, and under How the search went, what it assumed. If it found a row, it also shows that row and the steps that led to it, each marked assumed, forced or chosen. If every branch ended in a clash, it says how many branches closed instead: for the valid argument above, “Every branch ends in a conflict (1 branch closed).”

In Practice, you choose a value for each letter and press Check, and the app tells you whether your row is a counterexample. Show solution switches to Solve.

The other questions work the same way. For a formula, the short table assumes the formula is false, so it says only whether the formula is a tautology. For a set, it assumes every formula is true. For two formulas, it tries twice: the first true and the second false, then the other way round.

Common mistakes

• Too few rows. n letters need 2ⁿ rows: three letters need 8, not 6. Fill the letter columns in the fixed pattern and no row will be missed or repeated.
• Working from the outside in. You cannot know the value of ¬(P ∧ Q) before you know the value of P ∧ Q. Fill in the smallest parts first.
• Misreading →. P → Q is true in every row where P is false.
• Checking the wrong rows. A counterexample needs every premise true and the conclusion false. A row where some premise is false does not count, whatever the conclusion is.
• Deciding from one row. One row with true premises and a true conclusion does not make an argument valid. Validity is about every row.
• Reading the wrong column. The value of a formula is under its main connective, not under its first or last symbol.

Precise definitions

Textbooks state these ideas with a little notation. Below, A and B are formulas, Γ (the Greek capital gamma) is a set of formulas, and “iff” is short for “if and only if”.

• A valuation v assigns T or F to every sentence letter. It extends to every formula through the truth tables: v(¬A) = T iff v(A) = F; v(A ∧ B) = T iff v(A) = T and v(B) = T; and so on for the other connectives, with v(⊥) = F.
• v satisfies A if v(A) = T, and satisfies Γ if it satisfies every formula in Γ. Γ is satisfiable, or consistent, if some valuation satisfies it.
• Γ entails A, written Γ ⊨ A, if every valuation that satisfies Γ also satisfies A. An argument with premises Γ and conclusion A is valid iff Γ ⊨ A. A formula A is a tautology iff ⊨ A, that is, iff the empty set entails it.
• A and B are equivalent iff v(A) = v(B) for every valuation v, that is, iff A ⊨ B and B ⊨ A.

One link matters most: Γ ⊨ A iff Γ ∪ {¬A} is unsatisfiable. (Γ ∪ {¬A} is Γ with ¬A added.) A valuation that satisfies Γ ∪ {¬A} makes every formula in Γ true and A false: it is exactly a counterexample. So “there is no counterexample” and “Γ ∪ {¬A} is unsatisfiable” say the same thing. Short tables and tableaux both test validity this way.

Only the letters that occur in the formulas matter: two valuations that agree on those letters give the formulas the same values. That is why a table needs one row for each combination of those letters, and no more.

A decision procedure, and its cost

A decision procedure is a mechanical method that always stops and always gives the right yes-or-no answer. Truth tables are one for every question above: the table is finite, each row can be worked out, and the rows cover every valuation that matters.

The price is size. Each extra letter doubles the table: 20 letters give 1,048,576 rows, and 30 give over a billion. Short tables and tableaux often finish much sooner, because one forced value can settle many rows at once, but in the worst case they too can take exponential time. Whether some method is fast on every input is an open question: deciding whether a formula is satisfiable is NP-complete, which means it is as hard as any problem whose solutions can be checked quickly. So a method that always ran in polynomial time would settle the famous P versus NP problem.

The app’s limits

• Up to 12 sentence letters, the app draws the full table: at most 2¹² = 4,096 rows. A long table draws only the rows on screen as you scroll.
• With 13 to 20 letters, it skips the drawing but still checks every valuation, up to 2²⁰ = 1,048,576 of them, and gives the verdicts. Where a verdict comes with a row, such as a counterexample, it shows that valuation instead.
• Above 20 letters, it checks no rows at all, and suggests a short table or a tableau instead.
• The short table gives up after closing 4,096 branches, with the verdict Undecided.

Truth-functional completeness

For any truth table at all, some formula built from these connectives has exactly that table. To find one, pick the rows where the table has T, and describe each one by a conjunction: P ∧ ¬Q describes “P true, Q false”. The disjunction of these descriptions is true in exactly the rows you picked. (If no row has T, use P ∧ ¬P.) So the connectives are truth-functionally complete: they can express every truth table.

For example, “exactly one of P and Q” is true in rows 2 and 3, which gives (P ∧ ¬Q) ∨ (¬P ∧ Q). It is equivalent to ¬(P ↔ Q).

Fewer connectives would do. ¬ and ∧ alone are enough, because the others can be rewritten with them: A ∨ B is equivalent to ¬(¬A ∧ ¬B), and A → B to ¬(A ∧ ¬B). A disjunction of conjunctions like the one above is a disjunctive normal form, and the normal forms guide returns to it.

Further reading

forall x: Calgary, the free textbook whose proof rules the app uses, covers this material in its part on truth tables: complete truth tables, the ideas defined above, and shortcuts that avoid writing out every row. The tableaux guide shows a second way to answer the same questions.