Discrete Mathematics and Proof

Testing an argument with a truth table

An argument sounds convincing. How can you be certain that its conclusion really follows from what it assumes, and does not just sound as if it does?

You need

Building a truth table for a compound statementDiscrete Mathematics and Proof Valid and sound argumentsDiscrete Mathematics and Proof

Where you are 4 in What an argument is

Logic, proof and discrete math6

Logic9

What an argument is4

Modus ponens, chaining, and a common fallacy

Testing an argument with a truth table

Valid and sound arguments Modus tollens, ruling out, and a common fallacy

When you reach for it

An argument is a list of premises followed by a conclusion, and it is valid when the conclusion cannot be false while every premise is true. Reading a persuasive argument again rarely tells you whether its conclusion is forced or only sounds nearby.

A truth table settles the question mechanically. Give each simple statement a letter, and the table lists every way those letters can be true or false: every situation the argument can tell apart. Validity is a claim about every situation, so a table that lists them all checks it completely.

Reach for it when an argument is built from whole statements joined by “and”, “or”, “not”, “if ... then” and “if and only if”: to test a pattern of reasoning before relying on it, or to find the concrete situation that breaks one.

The procedure

Take the argument: “If the heater is on, the room is warm. The room is not warm. Therefore the heater is not on.”

Give each simple statement a letter. Let P be “the heater is on” and Q be “the room is warm”. The premise “the room is not warm” is the denial of Q, so it is written \neg Q, not given a new letter. A separate letter would let the table contain rows in which the room is both warm and not warm, situations that cannot happen, and one of them could pass for a counterexample. In symbols the argument is

\begin{array}{l} P \rightarrow Q \\ \neg Q \\ \hline \therefore\ \neg P \end{array}

where the premises sit above the line and \therefore, read “therefore”, marks the conclusion.

Build a table in which every premise and the conclusion can be read. Two letters give 2^2 = 4 rows, one for each way of making them true (T) or false (F), in the usual order with the first letter changing slowest. Each premise and the conclusion gets a column, filled in as in building a compound truth table, using the table for the conditional. Two kinds need no new column: a single letter is already a column, and the denial of a single letter is true exactly where that letter’s column says F. They are written out here; later tables leave them to be read off the letters.

Row	P	Q	{P \rightarrow Q}	\neg Q	\neg P
1	T	T	T	F	F
2	T	F	F	T	F
3	F	T	T	F	T
4	F	F	T	T	T

Find the critical rows, the rows in which every premise is true. The premises are P \rightarrow Q and \neg Q, and both are true only in row 4, set in bold. Only critical rows count. A valid argument promises something only about situations in which all its premises hold, so a row with a false premise is one it never made a claim about.

Read the conclusion in the critical rows. In row 4 the conclusion \neg P is true. So there is no row with every premise true and the conclusion false, and the argument is valid. This particular form has a name of its own, modus tollens.

Had the conclusion been false in even one critical row, that row would be a situation in which every premise holds and the conclusion fails, which is exactly what “not valid” means. One such row, a counterexample, is a complete proof of invalidity. Showing validity is a different job: every critical row has to be checked, because the one you skip could be the one that breaks it.

The same test, from the other side. You can instead list the rows where the conclusion is false and ask whether any of them has every premise true. Both searches look for the same thing, a row with true premises and a false conclusion, so they always agree. Use whichever list is shorter.

Worked examples

Example 1

An invalid argument, and its counterexample

Test the argument: “The shop is not open on both Saturday and Sunday. It is not open on Saturday. Therefore it is open on Sunday.”

Solution

Let P be “the shop is open on Saturday” and Q be “the shop is open on Sunday”. “Not both” is the denial of “and”, so the first premise is \neg(P \land Q), false in row 1 alone:

\begin{array}{l} \neg(P \land Q) \\ \neg P \\ \hline \therefore\ Q \end{array}

Row	P	Q	{\neg(P \land Q)}	\neg P
1	T	T	F	F
2	T	F	T	F
3	F	T	T	T
4	F	F	T	T

Both premises are true in rows 3 and 4. The conclusion Q is true in row 3 but false in row 4, so the argument is not valid, and row 4 is the counterexample: the shop is shut on both days, so both premises hold and it is not open on Sunday. Row 3 does not rescue the argument, since the conclusion must be true in every critical row.

Change one premise and the verdict changes. With P (“it is open on Saturday”) as the second premise and \neg Q as the conclusion, the only critical row is row 2, where Q is false, so that argument is valid.

Example 2

Three letters, eight rows

Test the argument: “If the battery is charged and the switch is on, the lamp lights. The battery is charged. The lamp does not light. Therefore the switch is not on.”

Solution

Let P be “the battery is charged”, Q be “the switch is on” and R be “the lamp lights”:

\begin{array}{l} (P \land Q) \rightarrow R \\ P \\ \neg R \\ \hline \therefore\ \neg Q \end{array}

Three letters give 2^3 = 8 rows, since each new letter doubles the number of combinations. Only the first premise needs a new column: P is a letter, and \neg R and \neg Q are true exactly where R and Q are false.

Row	P	Q	R	{(P \land Q) \rightarrow R}
1	T	T	T	T
2	T	T	F	F
3	T	F	T	T
4	T	F	F	T
5	F	T	T	T
6	F	T	F	T
7	F	F	T	T
8	F	F	F	T

Narrow the rows one premise at a time. P is true in rows 1 to 4. Of these, \neg R is true (that is, R is false) in rows 2 and 4. In row 2 the first premise is false, because P and Q are both true while R is false. That leaves row 4 as the only critical row. There Q is false, so \neg Q is true, and the argument is valid: with the battery charged and the lamp dark, the first premise can hold only if the switch is off.

Example 3

Three letters, one bad row

Test the argument: “Lena takes the train or the bus. If she takes the bus, she will be late. Therefore she will be late.”

Solution

Let P be “Lena takes the train”, Q be “Lena takes the bus” and R be “Lena is late”:

\begin{array}{l} P \lor Q \\ Q \rightarrow R \\ \hline \therefore\ R \end{array}

Row	P	Q	R	{P \lor Q}	{Q \rightarrow R}
1	T	T	T	T	T
2	T	T	F	T	F
3	T	F	T	T	T
4	T	F	F	T	T
5	F	T	T	T	T
6	F	T	F	T	F
7	F	F	T	F	T
8	F	F	F	F	T

The conclusion R is a letter, so it is read from the third column. The critical rows are 1, 3, 4 and 5, and R is true in three of them but false in row 4. So the argument is not valid. Row 4 says: Lena takes the train and not the bus, and she is not late. Both premises are true in that situation and the conclusion is false; three good rows count for nothing against it. (Row 1, in which she takes both, is allowed because “or” is inclusive.)

Example 4

Searching from the conclusion

Test the argument

\begin{array}{l} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore\ P \rightarrow R \end{array}

Solution

The full table has eight rows, but the conclusion is false in only two of them. A conditional is false only when its “if” part is true and its “then” part is false, so P \rightarrow R is false exactly when P is true and R is false. In the usual order those are rows 2 and 4, and only those two need writing:

Row	P	Q	R	{P \rightarrow Q}	{Q \rightarrow R}
2	T	T	F	T	F
4	T	F	F	F	T

In row 2 the premise Q \rightarrow R is false, and in row 4 the premise P \rightarrow Q is false. Neither row has both premises true, so no row anywhere in the table has true premises and a false conclusion. The argument is valid. Two rows instead of eight, and the check is still complete, because every row with a false conclusion was examined. This form is the hypothetical syllogism.

Example 5

Finding what follows

“At least one of Ana and Ben went to the concert. If Ana went, Cal went. If Ben went, Cal went.” Which of these follow from the three statements?

(a) Cal went. \qquad (b) Ana went. \qquad (c) If Ben went, then Ana went.

Solution

Let A, B and C be “Ana went”, “Ben went” and “Cal went”. The premises are A \lor B, A \rightarrow C and B \rightarrow C. There is one set of premises, so one table serves all three candidates: find the critical rows once, then read each candidate against them.

Row	A	B	C	{A \lor B}	{A \rightarrow C}	{B \rightarrow C}
1	T	T	T	T	T	T
2	T	T	F	T	F	F
3	T	F	T	T	T	T
4	T	F	F	T	F	T
5	F	T	T	T	T	T
6	F	T	F	T	T	F
7	F	F	T	F	T	T
8	F	F	F	F	T	T

A \lor B rules out rows 7 and 8, and of rows 1 to 6 both conditionals are true only in rows 1, 3 and 5. The critical rows are 1, 3 and 5.

(a) C is true in all three, so Cal went follows.

(b) A is false in row 5, so “Ana went” does not follow. Row 5 is the situation where Ben and Cal went and Ana stayed home, and every premise is true in it.

The critical rows are a complete list of the situations the premises allow, and a statement follows exactly when it is true everywhere on that list.

Boundaries

The table tests form, not truth. It answers whether the conclusion would have to be true if the premises were. Whether the premises actually are true is a separate question, the one that separates a sound argument from a merely valid one. “If the moon is made of cheese, then 2 + 2 = 5. The moon is made of cheese. Therefore 2 + 2 = 5” passes the test.

It sees only whole statements and connectives. “Every square is a rectangle. Every rectangle is a parallelogram. Therefore every square is a parallelogram” is valid, but its three sentences share no whole statement. In letters it becomes P, Q, therefore R, and the table finds a counterexample in the row where P and Q are true and R is false. The argument’s force lies in the word “every”, which needs quantifiers. So “valid” from a table is final, while “not valid” means not valid as far as the connectives go.

The verdict is about the translation. The same statement must get the same letter every time it appears, and a denial must be written with \neg, not with a fresh letter. A misread “or”, “unless” or “only if” tests a different argument from the one that was given.

The table doubles with every letter. n letters give 2^n rows: 16 for four letters, 1024 for ten. Past a handful of letters it is quicker to chain rules already known to be valid than to write every row.

Premises that can never all be true leave no critical rows. Then there is no counterexample, and the argument counts as valid whatever its conclusion says. Such an argument can never be sound, since its premises cannot all be true at once (Exercise 21).

Where this goes next

Every form that passes the test once becomes a rule you may use from then on without drawing the table again: modus ponens, modus tollens, the hypothetical syllogism and the disjunctive syllogism. Every form that fails becomes a named trap, such as affirming the consequent and denying the antecedent.

Join the premises with “and” and make that the “if” part of a conditional whose “then” part is the conclusion. The argument is valid exactly when this conditional is a tautology (Exercise 23), so testing arguments and recognizing tautologies are one skill, and logical equivalence is the same test run in both directions.

The last boundary above becomes a method of its own: add the denial of the conclusion to the premises, and if that leaves no critical rows, the conclusion follows. That is the idea behind proof by contradiction. A direct proof is a chain of steps, each an instance of a form that has already passed this test, which is why a long proof never needs a table of its own.

Exercises

Two letters

Decide whether each argument is valid. If it is not, give a row that shows it.

P \rightarrow Q, Q, therefore P
P \rightarrow Q, \neg P, therefore \neg Q
P \lor Q, P, therefore \neg Q
P \leftrightarrow Q, \neg P, therefore \neg Q
P \rightarrow \neg Q, Q, therefore \neg P
\neg P \rightarrow Q, \neg Q, therefore P
P \rightarrow Q, therefore Q \rightarrow P

Three letters

Decide whether each argument is valid. If it is not, give a row that shows it.

P \rightarrow Q, Q \rightarrow R, P, therefore R
P \rightarrow Q, P \rightarrow R, therefore Q \land R
(P \lor Q) \rightarrow R, \neg R, therefore \neg P
P \lor Q, Q \lor R, therefore P \lor R
P \rightarrow (Q \lor R), P, \neg Q, therefore R
An argument uses the five letters P, Q, R, S and T. How many rows does its truth table have?

Arguments in words

Choose letters, write the argument in symbols, and test it.

“If Priya wins the race, she gets a medal. If she gets a medal, her photo goes on the poster. Her photo is not on the poster. Therefore Priya did not win the race.”
“The number n is odd or n is prime. n is prime. Therefore n is not odd.”
“If it snows, the school closes. If the school closes, the exam is moved. The exam was moved. Therefore it snowed.”
“Nadia is in Paris or in Rome. If she is in Rome, she is in Italy. She is not in Italy. Therefore she is in Paris.”

Finding what follows

The premises are P \lor Q, P \rightarrow R and \neg R. Find the critical rows, then say which of Q, \neg P and P \lor R follow.
The premises are P \rightarrow Q and Q \rightarrow P. Does P \leftrightarrow Q follow? Does P follow?

Reasoning

Explain why the rows in which some premise is false play no part in the test.
Test the argument P, \neg P, therefore Q. Explain why the table calls it valid, and why it can never be sound.
Explain why a single row can show that an argument is not valid, while showing that it is valid means checking every critical row.
Use a truth table to show that \big((P \rightarrow Q) \land \neg Q\big) \rightarrow \neg P is true in every row. Then explain why, for any valid argument, the conditional whose “if” part joins the premises with “and” and whose “then” part is the conclusion is true in every row.

Answers

Not valid. In the row with P false and Q true, both premises are true and the conclusion P is false. This is affirming the consequent.
Not valid. In the row with P false and Q true, P \rightarrow Q and \neg P are true but \neg Q is false. This is denying the antecedent.
Not valid. In the row with P true and Q true, both premises are true and \neg Q is false. An “or” can have both parts true.
Valid. \neg P is true in the two rows with P false, and P \leftrightarrow Q is true in only one of them, the row with Q false as well. There \neg Q is true.
Valid. Q is true in two rows. In the one with P true, P \rightarrow \neg Q is false. The only critical row has P false and Q true, and there \neg P is true.
Valid. \neg Q is true in the two rows with Q false. In the one with P false, \neg P is true and Q is false, so \neg P \rightarrow Q is false. The only critical row has P true and Q false, and there P is true.
Not valid. In the row with P false and Q true, P \rightarrow Q is true and Q \rightarrow P is false. A conditional does not carry its converse.
Valid. P true and P \rightarrow Q true force Q true; then Q \rightarrow R true forces R true. The only critical row has all three letters true, and there R is true.
Not valid. For example, in the row with P, Q and R all false, both conditionals are true (their “if” part is false) and Q \land R is false.
Valid. \neg R makes R false, and then (P \lor Q) \rightarrow R is true only if P \lor Q is false. The only critical row has all three letters false, and there \neg P is true.
Not valid. In the row with P false, Q true and R false, P \lor Q and Q \lor R are true and P \lor R is false.
Valid. P true and Q false leave P \rightarrow (Q \lor R) true only if R is true. The only critical row has P true, Q false and R true, and there R is true.
32 rows. Each letter doubles the number of combinations: 2^5 = 32.
Valid. With W “Priya wins”, M “she gets a medal” and H “her photo is on the poster”, the argument is W \rightarrow M, M \rightarrow H, \neg H, therefore \neg W. \neg H makes H false, then M \rightarrow H forces M false, then W \rightarrow M forces W false. The only critical row has all three false, and there \neg W is true.
Not valid. With O “n is odd” and R “n is prime”, the argument is O \lor R, R, therefore \neg O. In the row with O true and R true, both premises are true and \neg O is false. A real case: n = 3 is odd and prime.
Not valid. With S “it snows”, C “the school closes” and E “the exam is moved”, the argument is S \rightarrow C, C \rightarrow E, E, therefore S. In the row with S false, C true and E true, every premise is true and S is false: the school closed for some other reason.
Valid. With A “Nadia is in Paris”, B “she is in Rome” and I “she is in Italy”, the argument is A \lor B, B \rightarrow I, \neg I, therefore A. \neg I makes I false, B \rightarrow I then forces B false, and A \lor B then forces A true. The only critical row has A true, B false and I false, and there A is true.
The only critical row has P false, Q true and R false. Q and \neg P are true there, so both follow. P \lor R is false there, so it does not follow.
P \leftrightarrow Q follows; P does not. The critical rows are the row with P and Q both true and the row with both false. P \leftrightarrow Q is true in both, but P is false in the second.
Valid means the conclusion cannot be false while every premise is true. A row with a false premise is not a situation in which every premise is true, so the argument makes no claim about it, and nothing the conclusion does there can break that claim.
P and \neg P are never true in the same row, so there are no critical rows. Then no row has true premises and a false conclusion, which is all that valid requires. Sound needs every premise to be actually true as well, and P and \neg P cannot both be true.
Not valid is the claim that some situation has true premises and a false conclusion, so one such row proves it. Valid is a claim about every situation with true premises, so every critical row must be checked: any one left out could be the counterexample.
With P and Q both false, the “if” part is true (both P \rightarrow Q and \neg Q hold) and \neg P is true, so the conditional is true. In each of the other three rows, either Q is true, so \neg Q is false, or P is true and Q false, so P \rightarrow Q is false; the “if” part is false and the conditional is true. This is the modus tollens form tested in the procedure. In general, such a conditional is false only in a row where its “if” part is true, meaning every premise is true, and its “then” part, the conclusion, is false. That row would be a counterexample, and a valid argument has none.