Discrete Mathematics and Proof

Modus tollens, ruling out, and a common fallacy

You know that if one thing is true, a second thing is true, or that at least one of two things is true. Then something gets ruled out. What are you entitled to conclude, and what only looks as if it follows?

You need

A conditional and its contrapositiveDiscrete Mathematics and Proof Valid and sound argumentsDiscrete Mathematics and Proof And and or: conjunction and disjunctionDiscrete 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

Why this exists

Picture a claim you already believe: if the alarm goes off, the building empties. You walk past the building and it is nowhere near empty; people are still at their desks. You did not hear an alarm, and you do not need to have heard one to know it did not go off. If it had, the building would be empty, and it is not.

That step, going from “if P then Q” together with “Q is false” to “P is false”, is used every time something gets ruled out because what it would force to happen did not happen. A doctor rules out a diagnosis because a symptom it demands is missing. A number gets ruled out as prime because it has a divisor it should not have. A whole proof technique is built from this one move, used once, deliberately. The move has a name, modus tollens, and together with modus ponens it is one of the two rules of deduction that proofs use most.

Ruling things out has a second shape, built on “or” instead of “if”. Your keys are in your coat or in your bag; they are not in the coat; so they are in the bag. An equation has two solutions, x = 5 or x = -2; the problem asks for a length, and a length is not negative; so x = 5. Here one fact says at least one of the possibilities holds and the other crosses one possibility off. Neither settles anything alone, since an “or” statement, a disjunction, never says which part is true, and ruling one possibility out says nothing about the rest; together they force a conclusion. That move is the disjunctive syllogism.

There is also a step that looks like ruling out and is not. “If you have a ticket, you may board the train” sounds as if nobody without a ticket may board. The sentence never said that: a child under five may ride free and board with no ticket at all. A conditional speaks only about the cases where its “if” part holds and stays silent about the rest. Reading that silence as a “no” has a name, so that it can be caught on sight: denying the antecedent. This lesson teaches the two valid moves, the one invalid look-alike, and how to tell them apart.

Definition

Modus tollens

Given two statements P and Q, modus tollens is the argument form

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

Read aloud: if P then Q; Q is false; therefore P is false. An argument is valid when its conclusion cannot fail to hold whenever its premises hold, and modus tollens is valid: there is no way for P \to Q and \neg Q to both be true while P is also true (see “Why it is true” below).

In a conditional P \to Q, the statement P is the antecedent (the “if” part) and Q is the consequent (the “then” part). To deny a statement is to assert its negation. So P \to Q is the conditional premise and \neg Q is the denial of the consequent, which is exactly what “tollens” (Latin for “taking away”) names. Only \neg P follows. Nothing here says why P is false, only that it is.

Denying the antecedent, a fallacy

Denying the antecedent is the argument form

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

It is a formal fallacy: an argument form that is not valid, so that some choice of statements for P and Q makes both premises true and the conclusion false. The fault is in the pattern itself, not in any one sentence put into it.

Written as a single conditional, the move treats P \to Q as though it also asserted \neg P \to \neg Q, the inverse of P \to Q. The inverse is a different statement, and a true conditional can have a false inverse. Its partner, affirming the consequent, misuses the same conditional from the other end.

Disjunctive syllogism

The disjunctive syllogism is the argument with two premises, an “or” statement and the denial of one of its parts, whose conclusion is the other part:

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

Read it as: “P or Q. Not P. Therefore Q.” The line separates what is given from what is concluded, and \therefore is read “therefore”. A syllogism is an argument with two premises and a conclusion; this one is called disjunctive because its first premise is a disjunction.

The part that is denied does not have to be the first one. Since P \lor Q and Q \lor P say the same thing, the mirror form is the same rule:

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

The rule is also called elimination: of the two possibilities, one is eliminated and the other is what is left.

Intuition

Modus tollens: outside the bigger region

Think of every possible situation as a point, and of the situations where P holds as a region. A true conditional P \to Q says that region sits entirely inside the region where Q holds: there is no situation with P and without Q.

Figure 1P \to Q puts P inside Q. Both A and B are outside P, but only B is outside Q.

Modus ponens starts inside the P region and concludes you are inside Q. Modus tollens starts from the other end. You are told you are outside the Q region, like point B, and since the whole P region lies inside Q, you cannot be in P either. Where exactly outside Q you are does not matter.

The rule works no matter what P and Q actually mean. It only cares about the shape of the two premises, never about alarms, primes, or anything else that fills P and Q in. That is what makes it safe to use on a claim you have never checked by hand: the argument form is valid for every choice of P and Q, so if the premises are true the conclusion is guaranteed, not merely likely.

Denying the antecedent: the ring between the regions

Now run the picture the wrong way. The premise \neg P says only that the case is somewhere outside the shaded circle. Point B is outside Q altogether, and there the conclusion \neg Q is right. Point A is in the ring that belongs to Q but not to P, and there the conclusion is wrong. Knowing you are outside P does not tell you which of the two you are in.

Denying the antecedent would be safe only if that ring were empty, which happens exactly when Q \to P is also true. That is an extra fact about a particular P and Q, and the conditional P \to Q on its own never supplies it.

Disjunctive syllogism: crossing a region off

Picture each statement as a region again. The circle P holds every situation in which P is true, and the circle Q every situation in which Q is true. Knowing P \lor Q tells you that you are somewhere in the shaded area of the left panel below, though not where.

Figure 2Knowing P \lor Q puts you somewhere in the shading. Ruling out P leaves only shading that lies inside Q.

Now learn \neg P. Every situation inside circle P is ruled out, and that includes the overlap. What is still shaded, in the right panel, is the part of Q outside P. It sits wholly inside circle Q, so wherever you are, Q is true.

Notice what the picture does not say. It does not say P and Q were exclusive, and it does not matter that the overlap was shaded to begin with. Denying P removes the overlap along with the rest of circle P.

Results

Modus tollens. For any statements P and Q,

P \to Q, \ \ \neg Q \ \ \therefore \ \ \neg P

is a valid argument form. Whenever a true conditional and the denial of its consequent are both available, the denial of its antecedent follows, with no further information needed about P or Q.

The table lists every combination of truth values for a conditional, with a column for each line of the two arguments that add a negation to it.

Row	P	Q	P \to Q	\neg P	\neg Q
1	T	T	T	F	F
2	T	F	F	F	T
3	F	T	T	T	F
4	F	F	T	T	T

Denying the antecedent is invalid. In row 3 both premises, P \to Q and \neg P, are true, and the conclusion \neg Q is false.

From P \to Q and \neg P, nothing follows about Q. The premises are both true in rows 3 and 4 and in no others. In row 3 Q is true; in row 4 Q is false.

Denying the antecedent fails exactly where affirming the consequent fails. The inverse \neg P \to \neg Q is logically equivalent to the converse Q \to P (each is the contrapositive of the other; see contrapositive equivalence), so both fallacies go wrong on precisely the cases with Q true and P false.

Set side by side, the four ways to add a second premise to P \to Q come out like this:

given	concluded	the move
P	Q	modus ponens, valid
\neg Q	\neg P	modus tollens, valid
Q	P	affirming the consequent, invalid
\neg P	\neg Q	denying the antecedent, invalid

Disjunctive syllogism. From P \lor Q and \neg P, the conclusion Q follows. From P \lor Q and \neg Q, the conclusion P follows. The argument is valid: whenever both premises are true, the conclusion is true.

Denying a negated part. The denial of \neg P is P. So from \neg P \lor Q and P, the conclusion Q follows. The rule is the same; only the part being denied is itself a negation.

More than two parts. From P \lor Q \lor R and \neg P, the conclusion is Q \lor R, not Q. Each denial removes one part. From P \lor Q \lor R, \neg P and \neg Q, the conclusion is R.

Why it is true

Why modus tollens is valid

Every row of P and Q can be checked directly, using the table in Results. The two premises, P \to Q and \neg Q, are both true only in row 4, and in that row P is false. So whenever both premises hold, P is false, which is exactly the claim P \to Q,\ \neg Q \ \therefore \ \neg P makes. Checking a whole argument this way, row by row, is its own skill: testing an argument with a truth table.

There is a second route, using the contrapositive instead of a table. P \to Q is true, so its contrapositive \neg Q \to \neg P is true as well, since the two are logically equivalent. Now apply modus ponens to \neg Q \to \neg P together with the given \neg Q: the hypothesis of that conditional holds, so its conclusion, \neg P, holds too. Seen this way, modus tollens is modus ponens aimed at the contrapositive. Both routes reach the same place: one checks every row, the other reuses a rule already known to be valid.

Why denying the antecedent is not

An argument form is valid when every row that makes all its premises true also makes the conclusion true, so a single row that breaks this makes the form invalid. Row 3 is that row: P false, Q true, and P \to Q true, because a conditional is false only when its antecedent is true and its consequent false.

In words, every counterexample has the same shape: a case where Q holds for some other reason than P. The small child boards without a ticket; 35 is a multiple of 5 without being a multiple of 10.

Both fallacies borrow the same unproved conditional Q \to P: denying the antecedent uses it by modus tollens (from \neg P get \neg Q), affirming the consequent by modus ponens (from Q get P), and row 3 breaks both.

Why disjunctive syllogism is valid

Suppose both premises, P \lor Q and \neg P, are true, and ask what Q can be. The first premise says at least one of P and Q is true. The second says P is false. If Q were also false, then both parts of P \lor Q would be false, and by the definition of “or” a disjunction with both parts false is false. That contradicts the first premise. So Q is true.

The same fact shows up when the four cases are listed:

Row	P	Q	P \lor Q	\neg P	Q
1	T	T	T	F	T
2	T	F	T	F	F
3	F	T	T	T	T
4	F	F	F	T	F

Both premises are true in the third row only, and in that row the conclusion Q is true.

For more parts, the same reasoning applies. If P \lor Q \lor R is true and P is false, then one of Q and R must be the true part, which is the statement Q \lor R. Deny Q as well and the two-part rule gives R.

Worked examples

Example 1

An everyday instance

If the pool is open, a lifeguard is on duty. Right now no lifeguard is on duty. What follows?

Solution

Let P be “the pool is open” and Q be “a lifeguard is on duty.” The claim is P \to Q, and what you see gives \neg Q. The second premise denies the consequent, which is exactly the shape modus tollens needs, so \neg P follows: the pool is not open.

Example 2

When the parts are themselves negations

If the café is not open, its sign does not light up. Tonight the sign is lit. What follows?

Solution

Take the parts exactly as written. P is “the café is not open” and Q is “the sign does not light up.” The conditional is P \to Q. The sign being lit makes Q false, so \neg Q holds. By modus tollens, \neg P holds, and \neg P says “it is not the case that the café is not open.” Two denials cancel, so the café is open. The rule never cares that P or Q contains a “not”; it only needs the second premise to deny whatever the consequent says.

Example 3

A fact about numbers

It is true that if a whole number is a multiple of 6, then it is even. The number 15 is odd, not even. What follows about 15 and multiples of 6?

Solution

Let P be “n is a multiple of 6” and Q be “n is even.” The known fact is P \to Q, true for every whole number n. For n = 15, Q is false, so \neg Q holds. By modus tollens, \neg P: 15 is not a multiple of 6.

Example 4

Ruling out a root

It is true that if x^2 - 5x + 6 = 0, then x = 2 or x = 3. Take x = 7, for which neither is true. What follows, and check it directly?

Solution

Let P be “x^2 - 5x + 6 = 0” and Q be “x = 2 or x = 3.” The fact given is P \to Q. At x = 7, Q is false, since 7 \ne 2 and 7 \ne 3, so \neg Q holds. By modus tollens, \neg P: x^2 - 5x + 6 \ne 0 when x = 7.

Check. 7^2 - 5(7) + 6 = 49 - 35 + 6 = 20, and 20 \ne 0, confirming the conclusion directly.

Example 5

Which side is denied?

Every multiple of 10 is a multiple of 5. Which of these two arguments is modus tollens? (a) 37 is not a multiple of 5, so 37 is not a multiple of 10. (b) 35 is not a multiple of 10, so 35 is not a multiple of 5. For the one that is not, check whether its premises and its conclusion are true.

Solution

Let P be “n is a multiple of 10” and Q be “n is a multiple of 5,” so the premise is P \to Q. Argument (a) denies the consequent Q and concludes \neg P: that is modus tollens, and it is valid. Its second premise is true, since 37 = 7 \times 5 + 2 leaves remainder 2.

Argument (b) denies the antecedent P instead and concludes \neg Q, which modus tollens never licenses: it has the form of denying the antecedent. Both of its premises are true. Every multiple of 10 is a multiple of 5, since 10 = 2 \times 5. And 35 \div 10 = 3.5 is not a whole number, so 35 is not a multiple of 10. The conclusion is false: 35 = 5 \times 7. This is row 3 of the table in Results, with P false and Q true.

Example 6

Walking back along a chain

If a shape is a square, then it is a rectangle. If a shape is a rectangle, then it has four right angles. A certain shape does not have four right angles. What follows about the shape being a rectangle, and about it being a square?

Solution

Let P be “the shape is a square,” Q be “the shape is a rectangle,” and R be “the shape has four right angles.” The two facts are P \to Q and Q \to R, and the observation is \neg R.

Apply modus tollens to Q \to R and \neg R: \neg Q, the shape is not a rectangle. That conclusion is now a denial of the consequent of the first fact, P \to Q, so modus tollens applies a second time: \neg P, the shape is not a square. Each use steps one link back along the chain. The same result comes from first chaining the conditionals into P \to R and then applying modus tollens once.

Example 7

Denying the antecedent: a geometric version

“If a quadrilateral is a square, then its two diagonals have equal length. So a quadrilateral that is not a square has diagonals of unequal length.” Find a quadrilateral that breaks the argument.

Solution

With P: “the quadrilateral is a square” and Q: “its diagonals have equal length”, the argument goes from P \to Q and \neg P to \neg Q. A counterexample needs row 3: a quadrilateral that is not a square but still has equal diagonals.

Take a rectangle 3 units by 4 units. It is not a square, since 3 \ne 4. Each diagonal is the hypotenuse of a right triangle with legs 3 and 4, so by the Pythagorean theorem each has length

\sqrt{3^2 + 4^2} = \sqrt{25} = 5.

Both diagonals measure 5, so they are equal, and the conclusion fails.

Example 8

Every counterexample on a number line

“If x > 3, then x^2 > 9. Suppose x \le 3. Then x^2 \le 9.” Find every real number x for which this reasoning reaches a false conclusion.

Solution

The conditional is true: if x > 3 then x^2 > 3x > 9. The reasoning is denying the antecedent, so it goes wrong exactly in row 3, where P is false and Q is true:

x \le 3 \qquad\text{and}\qquad x^2 > 9.

x^2 > 9 holds when x > 3 or x < -3. Of these, only x < -3 also satisfies x \le 3. So the conclusion is false for every x < -3. For example, x = -4 gives x^2 = 16 > 9.

For every x from -3 to 3 the conclusion happens to be true, but the form that reached it is the same one that fails at x = -4, so it guarantees nothing.

Example 9

Four second premises, one conditional

Take the true conditional “if a whole number n ends in the digit 0, then it is divisible by 5”. What follows from it together with each of these? (a) n ends in 0. (b) n is divisible by 5. (c) n does not end in 0. (d) n is not divisible by 5.

Solution

Let P be “n ends in 0” and Q be “n is divisible by 5”. In (a) modus ponens gives Q, and in (d) modus tollens gives \neg P. Case (b) is affirming the consequent, and n = 15 breaks it.

Case (c) is denying the antecedent, and nothing follows about Q in either direction. The number n = 15 does not end in 0 and is divisible by 5, so \neg Q fails; n = 13 does not end in 0 and is not divisible by 5, so Q fails too. The same 15 breaks both invalid moves because it has Q true and P false, the one kind of case where the converse fails.

Example 10

When the “if” is a definition

A textbook defines: “A triangle is isosceles if it has at least two sides of equal length.” Triangle T has sides 4, 6 and 7. Is it correct to conclude that T is not isosceles?

Solution

Let P be “T has at least two equal sides” and Q be “T is isosceles”. Read as a bare conditional P \to Q, the step from \neg P to \neg Q is denying the antecedent and proves nothing.

But a definition is not a one-way promise. It fixes what the word means, so it is used in both directions: a definition is a biconditional, even when it is written with a plain “if”. Its converse Q \to P, “an isosceles triangle has two equal sides”, is part of what the definition says. Modus tollens on Q \to P now settles it: if T were isosceles it would have two equal sides; its sides 4, 6 and 7 are all different (and do form a triangle, since 4 + 6 = 10 > 7); so T is not isosceles.

A theorem carries no such converse. “If a triangle is equilateral, then it is isosceles” is true, yet the triangle with sides 5, 5 and 6 is not equilateral and is isosceles. The same step, from “not the ‘if’ part” to “not the ‘then’ part”, is valid for the definition and fails for the theorem, and the difference lies wholly in the extra premise Q \to P.

Example 11

Counting the counterexamples

Take the conditional “if n is a multiple of 6, then n is a multiple of 3” for the whole numbers n = 1, 2, \ldots, 30. For how many of these numbers does denying the antecedent reach a false conclusion? For how many does affirming the consequent?

Solution

Denying the antecedent goes wrong exactly when P is false and Q is true: n is a multiple of 3 but not of 6. Those are the odd multiples of 3:

3,\ 9,\ 15,\ 21,\ 27.

There are 10 multiples of 3 up to 30 and 5 multiples of 6, and 10 - 5 = 5. So of the 30 - 5 = 25 numbers that are not multiples of 6, denying the antecedent gets 20 right and 5 wrong.

Affirming the consequent is applied to the 10 multiples of 3, and it goes wrong when Q is true and P is false: the same condition, so the same 5 numbers. These five are exactly where the missing conditional Q \to P is false.

Example 12

Disjunctive syllogism: drawing the conclusion

Each pair of statements is given as true. Say what follows from them.

(a) The ticket is in the red envelope or in the blue envelope. It is not in the red envelope.

(b) x = 9 or x = -9. Also, x > 0.

Solution

Each is a disjunctive syllogism once the denied part is found.

(a) The first statement is an “or” with parts “red envelope” and “blue envelope”. The second denies the first part. So the ticket is in the blue envelope.

(b) The second statement is not written as a denial, so read what it rules out. A number greater than 0 is not -9, so x > 0 denies the part x = -9. The conclusion is x = 9.

(c) Here the second part is denied, so the first part is the conclusion: \displaystyle \sqrt{30} lies between 5 and 6. The premises are true, too: 5^2 = 25 and 6^2 = 36, so 25 < 30 < 36.

Example 13

Reading an “or” in symbols

For each pair of premises, give the conclusion of the disjunctive syllogism.

(a) A \lor B and \neg B. (b) \neg C \lor D and C. (c) E \lor \neg F and F.

Solution

In each, find which part of the “or” the second premise denies, then conclude the other part.

(a) \neg B denies the second part, so the conclusion is A.

(b) The first part is \neg C. The second premise, C, says \neg C is false, so it denies the first part. The conclusion is D.

A denial is whatever makes that part false. Of a part \neg C, the denial is C itself.

Example 14

Throwing out a candidate

Solve \dfrac{x^2 + 3}{x - 1} = \dfrac{4x}{x - 1}.

Solution

Suppose x is a solution. Multiplying both sides by x - 1 clears the fractions:

\begin{aligned} x^2 + 3 &= 4x \\ x^2 - 4x + 3 &= 0 \\ (x - 1)(x - 3) &= 0 \end{aligned}

By the zero product property, x = 1 or x = 3. Be exact about what this proves: if x is a solution, then x = 1 or x = 3. The two numbers are candidates, not yet solutions, because the working only runs from the original equation to the “or”.

Now test x = 1 in the original. Both denominators become 1 - 1 = 0, so neither side is defined and 1 is not a solution. For a solution x, then, the part x = 1 is false.

By disjunctive syllogism, a solution can only be x = 3. That rules out every other number; it does not yet show that 3 works, so substitute: the left side is \displaystyle \frac{9 + 3}{3 - 1} = 6 and the right side is \displaystyle \frac{12}{3 - 1} = 6. The solution is x = 3. A candidate that the cleared equation lets in and the original rejects is an extraneous solution, and throwing it out is this rule at work.

Example 15

Two eliminations in a row

Let M be “the class meets on Monday”, W be “the class meets on Wednesday” and S be “the class meets in room 7”. Given the three premises

M \lor W, \qquad \neg M, \qquad \neg W \lor S

what can you conclude?

Solution

Look for a disjunction together with the denial of one of its parts. The first two premises are exactly that: \neg M denies the first part of M \lor W. So W is true.

Now W is a new fact, and it denies the first part of \neg W \lor S, since that part is \neg W. A second disjunctive syllogism gives S.

The conclusion is W and S: the class meets on Wednesday, in room 7. The first conclusion became a premise of the second, which is how longer arguments are built from short valid steps.

The third premise reads “the class does not meet on Wednesday, or it meets in room 7”, which is the conditional “if the class meets on Wednesday, it meets in room 7” said with “or” (a conditional said with or). So the second step is modus ponens in other clothes: denying a part \neg W by asserting W is exactly using a conditional forwards.

Example 16

Eliminating two of three

A number x satisfies x^3 - 2x^2 - 5x + 6 = 0. You are also told that x is odd and that x^2 > 1. Find x.

Solution

First turn the equation into an “or”. The cubic factors as

x^3 - 2x^2 - 5x + 6 = (x - 1)(x + 2)(x - 3)

which can be checked by multiplying out. A product is zero when at least one factor is zero, so

x = 1 \ \lor\ x = -2 \ \lor\ x = 3

x is odd, and -2 is even, so the part x = -2 is denied. What remains is x = 1 \lor x = 3.

x^2 > 1, and 1^2 = 1 is not greater than 1, so the part x = 1 is denied. What remains is x = 3.

Check. 27 - 18 - 15 + 6 = 0, 3 is odd, and 3^2 = 9 > 1. With three parts, one denial left an “or” of two, and only the second denial left a single answer.

Example 17

A proof by elimination

Prove that if n is an integer and n^2 is a multiple of 3, then n is a multiple of 3.

Solution

Divide n by 3. The remainder is 0, 1 or 2, so for some integer k,

n = 3k \ \lor\ n = 3k + 1 \ \lor\ n = 3k + 2

The plan is to rule out the last two parts.

If n = 3k + 1, then

n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1

which is one more than a multiple of 3, so it is not a multiple of 3. That contradicts what we were told about n^2, so this part is denied.

If n = 3k + 2, then

n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1

which is again one more than a multiple of 3. This part is denied too.

The only part left is n = 3k, so n is a multiple of 3. Each denial here needed a short argument of its own; that pattern, splitting on an “or” and closing off every case but one, is common in proofs by cases.

Boundaries

Modus tollens denies the consequent, not the antecedent. From P \to Q and \neg P, nothing at all follows about Q: that is denying the antecedent. A square is a rectangle, but plenty of non-squares are rectangles too, so knowing a shape is not a square says nothing about whether it is a rectangle.

Each rule gives its conclusion and nothing more. Modus tollens does not say why P is false, and it says nothing about statements that were not part of the two premises.

Invalidity belongs to the form. Row 3 shows that denying the antecedent never guarantees its conclusion, whatever P and Q stand for. A particular instance can still land on a true conclusion, as every x from -3 to 3 does in Example 8, but that truth comes from facts outside the argument. And it proves nothing in either direction: rows 3 and 4 both keep the premises true, with opposite values of Q, so neither \neg Q nor Q follows.

Valid is not the same as true. Validity and truth are different questions. Modus tollens guarantees that if P \to Q and \neg Q are both true, then \neg P is true. If P \to Q is false, the conclusion is not guaranteed. This matters most with everyday conditionals that carry unstated exceptions: “if it rains, the game is canceled” is false when there is an indoor backup, and then the game going ahead tells you nothing about the weather. The same holds for elimination. “Every whole number is positive or negative; 0 is not positive; so 0 is negative” is valid in form, but its “or” leaves out 0, so the argument is not sound. An “or” used for elimination has to cover every possibility.

A converse, when it holds, is a separate premise. If the real relationship is P \leftrightarrow Q, or Q \to P has been proved, or comes with a definition as in Example 10, then \neg Q follows from \neg P by modus tollens on Q \to P. Denying the antecedent has not become valid; a different premise is doing the work. Modus tollens on the forward direction alone is still correct, but it uses only half of what a biconditional says. Affirming the consequent shows the same rescue from the other side.

The quantified version fails the same way. “For every x, if P(x) then Q(x)” does not give “for every x, if not P(x) then not Q(x)”. The second statement is false as soon as one x has Q(x) without P(x), and that x is a counterexample to the converse.

Affirming one part of an “or” proves nothing about the other. From P \lor Q and P, nothing follows about Q, because the “or” is inclusive and both parts may be true. “12 is even or 12 is a multiple of 4” is true, and 12 is even, yet 12 is also a multiple of 4. The pattern P \lor Q,\ P,\ \therefore \neg Q is not valid. It becomes valid only when the premise is the stronger “P or Q, but not both”.

The denial must be of a part, exactly. From x = 2 \lor x > 5 and x \ne 3, nothing follows, since x \ne 3 denies neither part. A denial has to make one whole part false.

With more parts, one denial is not enough. From P \lor Q \lor R and \neg P, the conclusion is Q \lor R. Reaching a single part takes a denial of every part but one.

Where this goes next

Modus tollens turns directly into a way of proving things: to show P \to Q, assume \neg Q and argue your way to \neg P, which is exactly proof by contraposition. The one-step deduction becomes the engine of an entire proof. The swap has to be done exactly, since proving \neg P \to \neg Q in its place would prove the converse, not the statement. In geometry the same care is needed every time a theorem is turned around: a theorem and its converse need separate proofs.

Modus tollens has two tempting and invalid twins. Swapping which side gets denied gives denying the antecedent, and affirming the consequent instead of denying it gives affirming the consequent; both look like reasonable shortcuts and neither is one. Telling modus tollens apart from those two, on sight, is most of what it takes to read an argument correctly. The bad row was found here by looking at a four-row table; testing an argument with a truth table makes that search routine for arguments with more statements and more premises, where the bad row is harder to spot.

The disjunctive syllogism sits beside the other short valid forms in what an argument is: modus ponens, modus tollens and the hypothetical syllogism. It is closer to modus ponens than it looks: once “if P then Q” is written as \neg P \lor Q, modus ponens is a disjunctive syllogism, as the second step of Example 15 showed. In proof, elimination is everywhere. A proof by contradiction starts from “P or not P”, shows that “not P” leads somewhere impossible, and concludes P. A proof that lists every case and closes all but one, as in Example 17, is the rule applied to a longer “or”.

In algebra it is how solutions are chosen. Factoring, squaring or clearing fractions produces an “or” of candidates, and the conditions of the problem, a length that must be positive, a denominator that cannot be zero, a square root that cannot be negative, deny the ones that do not belong.

Exercises

Naming the parts

“If the library is open, the lights are on. The lights are off.” Name P and Q, and state the conclusion modus tollens gives.
“If Priya is at soccer practice, her cleats are not in the hall closet. Her cleats are in the hall closet.” Name P and Q (let Q be the statement about the cleats, exactly as written), and state the conclusion.
“If a number is a perfect square, then it is not negative. -9 is negative.” Name P and Q, and state the conclusion.

Valid move or fallacy?

If a number is divisible by 4, then it is divisible by 2. The number 15 is not divisible by 2. Therefore 15 is not divisible by 4. Is this valid? If so, name the rule.
If a number is divisible by 4, then it is divisible by 2. The number 15 is not divisible by 4. Therefore 15 is not divisible by 2. Is this valid?
If a shape is a square, then it has four sides. Shape S has four sides. Therefore S is a square. Is this valid?
If today is a holiday, the mail does not run. The mail ran today. Therefore today is not a holiday. Is this valid? If so, name the rule.
If it is not raining, the game proceeds as scheduled. The game was canceled (it did not proceed as scheduled). Therefore it is raining. Is this valid? If so, name the rule.
If Maria lives in Texas, then Maria lives in the United States. Maria lives in the United States. Therefore Maria lives in Texas. Is this valid?
Each argument starts from “if it snows, school is canceled”. Name the form of each and say whether it is valid. (a) It snowed, so school is canceled. (b) School is canceled, so it snowed. (c) It did not snow, so school is not canceled. (d) School is not canceled, so it did not snow.

Recognizing denying the antecedent

“If a figure is a square, then it is a rhombus. This figure is not a square. Therefore it is not a rhombus.” Name P and Q, write the argument in symbols, and name a figure that breaks it.
Denying the antecedent behaves as though P \to Q also asserted a second conditional. Write that conditional in symbols and give its name.
“Everyone who lives in Paris lives in France. Ana does not live in Paris. So Ana does not live in France.” Name P and Q, name the form, and describe a person who breaks it.

Modus tollens with numbers

If a whole number is a perfect square, then its last digit is 0, 1, 4, 5, 6 or 9. Compute 38 \times 41, and say what follows about whether it is a perfect square.
If a whole number is divisible by 9, then its digit sum is divisible by 9. Find the digit sum of 2023, and say what follows about whether 2023 is divisible by 9.
If a triangle with sides a, b and longest side c is right-angled, then a^2 + b^2 = c^2. A triangle has sides 5, 6 and 8. Compute 5^2 + 6^2 and 8^2, and say what follows about whether the triangle is right-angled.
The number 51 satisfies 51 = 3 \times 17. If a whole number greater than 1 is prime, then it has no divisor other than 1 and itself. What follows about whether 51 is prime?

Chaining two conditionals

If a number is a multiple of 12, then it is a multiple of 4. If a number is a multiple of 4, then it is even. The number 37 is odd. What follows about 37 being a multiple of 4, and about it being a multiple of 12?
If an animal is a robin, it is a bird. If an animal is a bird, it has feathers. A certain animal has no feathers. What two things follow about the animal?

Finding a counterexample

“If n is a multiple of 8, then n is a multiple of 4. 12 is not a multiple of 8. Therefore 12 is not a multiple of 4.” Show that both premises are true and the conclusion is false.
“If a number is a prime greater than 2, then it is odd. 9 is not a prime greater than 2. Therefore 9 is not odd.” Is the conclusion true?
“If a triangle is equilateral, then it is isosceles. The triangle with sides 5, 5 and 8 is not equilateral. Therefore it is not isosceles.” Show that the conclusion is false.
“If today is a weekday, the museum is open. Today is Saturday. Therefore the museum is closed.” Describe a situation in which both premises are true and the conclusion is false.
“If x = 4, then x^2 = 16. We know x \ne 4. Therefore x^2 \ne 16.” Give a value of x that breaks the argument.

Denying the antecedent in algebra and geometry

“If x > 5, then x > 2. Suppose x \le 5. Then x \le 2.” Find every real x for which the conclusion is false.
The conditional “if 0 < x < 1, then x^2 < x” is true. Find every real x for which P is false and Q is true. What does your answer say about denying the antecedent here?
Take the conditional “if n is a multiple of 4, then n is even” for n = 1, 2, \ldots, 50. For how many of these numbers does denying the antecedent reach a false conclusion?
“If a quadrilateral is a rectangle, then both pairs of its opposite sides are parallel. Quadrilateral ABCD with A(0, 0), B(4, 0), C(5, 2) and D(1, 2) is not a rectangle. Therefore its opposite sides are not both parallel.” Show that ABCD is not a rectangle and that the conclusion is false.
“If a rectangle measures 3 by 8, then its area is 24. This rectangle does not measure 3 by 8. Therefore its area is not 24.” Give a rectangle that breaks the argument.

Arguments with more than one step

“If a number is a multiple of 6, then it is a multiple of 3. If a number is a multiple of 3, then the sum of its digits is a multiple of 3. 20 is not a multiple of 6. Therefore the sum of the digits of 20 is not a multiple of 3.” Which step is valid, which step is denying the antecedent, and is the conclusion true? Give a number that shows the form fails.
“If x = 1 or x = 2, then (x - 1)(x - 2) = 0. We know x \ne 1 and x \ne 2. Therefore (x - 1)(x - 2) \ne 0.” Is the conclusion justified? If so, say what justifies it.
Given P \to Q, Q \to R and \neg P, which of Q, \neg Q, R and \neg R can be concluded?

Disjunctive syllogism: drawing the conclusion

Each pair of statements is given as true. Say what follows by disjunctive syllogism.

The book is on the shelf or on the desk. The book is not on the shelf.
x = 6 or x = -6. Also, x > 0.
The light is out because the bulb has failed or because the switch is off. The switch is on.
\displaystyle \sqrt{50} lies between 6 and 7 or between 7 and 8. \displaystyle \sqrt{50} does not lie between 6 and 7.
The number m is negative, zero or positive. m is not zero, and m is not negative.

An “or” in symbols

Give the conclusion that follows from each pair of premises, or say that nothing follows about the remaining part.

P \lor Q and \neg Q
\neg A \lor B and A
\neg(P \lor Q) \lor R and P
P \lor Q \lor R and \neg Q
P \lor Q and P
(P \land Q) \lor R and \neg R
\neg P \lor \neg Q and Q

Choosing among solutions

Solve x^2 - 2x - 15 = 0, given that x < 0.
Solve \dfrac{x^2 + 2x}{x - 2} = \dfrac{8}{x - 2}.
A rectangle is 2 cm longer than it is wide, and its area is 48\ \text{cm}^2. If its width is w, then w(w + 2) = 48. Find w.
A number x satisfies x^3 - x^2 - 6x = 0. It is not 0, and x^2 > 4. Find x.
The integer n leaves remainder 0, 1, 2 or 3 when divided by 4. You are told that n is odd and that n + 1 is not a multiple of 4. Find the remainder.

Reasoning

Explain, without drawing a truth table, why modus tollens is valid. (Use the contrapositive.)
Give your own example of a modus tollens argument, different from any above, and name P and Q.
Prove modus tollens a third way, by contradiction: assume P \to Q and \neg Q, suppose P were true, and show that something impossible follows.
A detective argues: “If the gardener did it, there is mud on his boots. There is no mud on his boots. So the gardener did not do it.” The argument is valid. Explain what would still have to be checked before accepting the conclusion, and why validity alone does not settle it.
Using the truth table for P \to Q, explain why row 3 is the only row that breaks denying the antecedent.
Explain why, applied to the same conditional P \to Q, denying the antecedent and affirming the consequent are broken by exactly the same cases.
Modus tollens and denying the antecedent both have a negated statement as their second premise. Explain why one is valid and the other is not.
Explain why the argument “P \lor Q, P, therefore \neg Q” is not valid. Give a true statement of the form P \lor Q, with P true, for which \neg Q is false.
The premises are x < 1 \lor x > 4 and x \ne 0. Explain why neither part follows. Then replace x \ne 0 with a premise that lets disjunctive syllogism conclude x > 4.
You know P \lor Q \lor R and \neg P. Explain why you cannot conclude Q, and say what you can conclude.
Prove that if n is an integer and n^2 is even, then n is even, by writing “n is even or n is odd” and eliminating one part.
Show that if x^2 = x and x \ne 0, then x = 1, naming the “or” statement you use and the part you deny.

Answers

P: “the library is open.” Q: “the lights are on.” The lights are off, so \neg Q. Modus tollens gives \neg P: the library is not open.
P: “Priya is at soccer practice.” Q: “her cleats are not in the hall closet.” The cleats are in the hall closet, so Q is false: \neg Q. Modus tollens gives \neg P: Priya is not at soccer practice.
P: “a number is a perfect square.” Q: “it is not negative.” -9 is negative, so Q is false: \neg Q. Modus tollens gives \neg P: -9 is not a perfect square.
Valid, by modus tollens: the form is P \to Q, \neg Q, therefore \neg P.
Invalid. This denies the antecedent instead of the consequent. The form P \to Q, \neg P therefore \neg Q can fail: 6 is divisible by 2 but not by 4, so a number can satisfy \neg P while Q is still true. The conclusion about 15 happens to be true, but the premises do not force it.
Invalid. This affirms the consequent. An ordinary rectangle that is not a square has four sides too, so Q being true does not force P.
Valid, by modus tollens. Here Q is “the mail does not run,” and the mail running means Q is false, giving \neg Q; the conclusion \neg P is that today is not a holiday.
Valid, by modus tollens. Here P is “it is not raining,” and the game not proceeding gives \neg Q; the conclusion \neg P is “not (not raining),” which is “it is raining.”
Invalid. This affirms the consequent: living in the United States does not force living in Texas, since someone could live in any other state.
(a) Modus ponens, valid. (b) Affirming the consequent, invalid: school can close for a storm or a holiday. (c) Denying the antecedent, invalid, for the same reason. (d) Modus tollens, valid.
P: “the figure is a square”, Q: “the figure is a rhombus”. The form is P \to Q, \neg P, \therefore\ \neg Q. A rhombus with angles of 60^\circ and 120^\circ is not a square but is a rhombus, so it breaks the argument.
\neg P \to \neg Q, the inverse of P \to Q.
P: “Ana lives in Paris”, Q: “Ana lives in France”. The form is denying the antecedent. Anyone who lives in Lyon breaks it: not in Paris, but in France.
38 \times 41 = 1558, whose last digit is 8, not one of the listed digits, so \neg Q holds. By modus tollens, 1558 is not a perfect square. (Indeed 39^2 = 1521 and 40^2 = 1600.)
2 + 0 + 2 + 3 = 7, and 7 is not divisible by 9, so \neg Q holds. By modus tollens, 2023 is not divisible by 9.
5^2 + 6^2 = 25 + 36 = 61 and 8^2 = 64. Since 61 \ne 64, \neg Q holds. By modus tollens, the triangle is not right-angled.
51 = 3 \times 17, so 51 has a divisor, namely 3, other than 1 and itself: \neg Q holds. By modus tollens, 51 is not prime.
37 is odd, so it is not even: \neg R. Modus tollens on “multiple of 4 \to even” gives 37 is not a multiple of 4. Modus tollens again, on “multiple of 12 \to multiple of 4,” gives 37 is not a multiple of 12 either.
The animal is not a bird (modus tollens on “bird \to feathers”) and not a robin (modus tollens again, on “robin \to bird,” using the first conclusion).
12 \div 8 = 1.5, so 12 is not a multiple of 8; every multiple of 8 is a multiple of 4 since 8 = 2 \times 4. But 12 = 3 \times 4, so 12 is a multiple of 4 and the conclusion is false.
No. 9 = 3 \times 3 is not prime, so the second premise is true, but 9 = 2 \times 4 + 1 is odd, so the conclusion “9 is not odd” is false.
5 + 5 = 10 > 8, so the triangle exists, and it is not equilateral since 5 \ne 8. It has two equal sides, so it is isosceles and the conclusion is false.
The museum is open every day of the week, weekends included. Then “if today is a weekday, the museum is open” is true, today is Saturday, and the museum is open, not closed.
x = -4. Then x \ne 4, but (-4)^2 = 16.
2 < x \le 5. The conclusion x \le 2 is false when x > 2, and the premise requires x \le 5.
There is none. x^2 < x means x(x - 1) < 0, which holds exactly when 0 < x < 1. So here Q \to P is also true, and the conclusion of denying the antecedent is always true. It is justified by that converse, not by the form.
13. The conclusion is false when n is even but not a multiple of 4: 2, 6, 10, \ldots, 50, which is (50 - 2) \div 4 + 1 = 13 numbers.
AB and DC both have slope 0, and BC and AD both have slope 2, so both pairs of opposite sides are parallel and the conclusion is false. At A the sides run along (4, 0) and (1, 2), whose dot product is 4 \ne 0, so the angle at A is not a right angle and ABCD is not a rectangle.
A 4 by 6 rectangle. It does not measure 3 by 8, and its area is 4 \times 6 = 24.
Chaining the two conditionals into “if a number is a multiple of 6, its digit sum is a multiple of 3” is valid, by hypothetical syllogism. Going from “20 is not a multiple of 6” to the conclusion is denying the antecedent. The conclusion is true, since 2 + 0 = 2, but only by luck: 21 is not a multiple of 6 (21 \div 6 = 3.5), yet its digit sum 2 + 1 = 3 is a multiple of 3.
Yes, but not by the form of the argument, which is denying the antecedent. The zero product property gives the converse: if (x - 1)(x - 2) = 0, then x = 1 or x = 2. Modus tollens on that converse gives the conclusion.
None of them. With P false, Q true and R true, all three premises are true; with P, Q and R all false, they are all true again. So Q, \neg Q, R and \neg R can each fail.
The book is on the desk. The second statement denies the first part of the “or”.
x = 6. A number greater than 0 is not -6, so the part x = -6 is denied.
The bulb has failed. “The switch is on” denies the part “the switch is off”.
\displaystyle \sqrt{50} lies between 7 and 8. The first part is denied, so the second remains. Indeed 49 < 50 < 64.
m is positive. Denying “zero” leaves “negative or positive”, and denying “negative” leaves “positive”.
P. \neg Q denies the second part.
B. A makes the part \neg A false.
R. With P true, P \lor Q is true, so the part \neg(P \lor Q) is false. The second premise denies that part without naming it.
P \lor R. One denial removes one part; the other two remain as an “or”.
Nothing follows about Q. With P true the disjunction is true whether Q is true or false.
P \land Q, so P is true and Q is true. \neg R denies the second part, and the first part is the conjunction.
\neg P. Q makes the part \neg Q false, so the other part, \neg P, remains.
x = -3. Factoring, (x - 5)(x + 3) = 0, so x = 5 or x = -3. The condition x < 0 denies x = 5.
x = -4. For a solution, multiplying by x - 2 gives x^2 + 2x = 8, so (x + 4)(x - 2) = 0: x = -4 or x = 2. At x = 2 both denominators are 0, so that part is denied. Check: at x = -4 both sides equal \displaystyle \frac{8}{-6} = -\frac{4}{3}.
w = 6. w^2 + 2w - 48 = 0 factors as (w - 6)(w + 8) = 0, so w = 6 or w = -8. A width is not negative, which denies w = -8. Check: 6 \cdot 8 = 48.
x = 3. x^3 - x^2 - 6x = x(x - 3)(x + 2), so x = 0 or x = 3 or x = -2. The first part is denied outright. (-2)^2 = 4 is not greater than 4, which denies x = -2. Check: 3^2 = 9 > 4.
Remainder 1. Remainders 0 and 2 make n even, so n odd denies both. Remainder 3 makes n + 1 a multiple of 4, so that part is denied too.
P \to Q being true means its contrapositive \neg Q \to \neg P is also true, since a conditional and its contrapositive always match in truth value. Given \neg Q, modus ponens applied to \neg Q \to \neg P gives \neg P directly, with no table needed.
Answers will vary. A valid example names two statements P, Q, states P \to Q as a claim the reader would accept as true, denies Q, and concludes \neg P; for example, “if the kettle has boiled, the water in it is hot; the water is cold; so the kettle has not boiled.”
Suppose P were true. With P \to Q, modus ponens gives Q. But \neg Q is a premise, so Q and \neg Q would both hold, which is impossible. The supposition must be wrong, so P is false: \neg P.
Both premises. The conditional may be false: the gardener could have cleaned his boots or worn other shoes, and then “if he did it, there is mud on his boots” fails. The observation may be wrong too, if the boots checked were not the ones he wore. Validity only promises that the conclusion is true when both premises are; whether they are is a question about the world, and a valid argument with a false premise is not sound.
The premises P \to Q and \neg P are both true only in rows 3 and 4, because \neg P needs P false and P \to Q is true whenever P is false. In row 4 Q is false, so \neg Q is true. In row 3 Q is true, so \neg Q is false. Row 3 is the only row with true premises and a false conclusion.
Denying the antecedent draws \neg Q from \neg P, so it goes wrong exactly when P is false and Q is true. Affirming the consequent draws P from Q, so it goes wrong exactly when Q is true and P is false. These are the same cases, the ones where the converse Q \to P is false (and P \to Q is automatically true there, since P is false).
Modus tollens negates the consequent. If Q is false, P cannot be true, because P true with Q false is the one row where P \to Q is false; so \neg P follows. Denying the antecedent negates P, and P \to Q puts no limit on Q when P is false, so both values of Q remain possible.
Both parts of a true disjunction can be true, so knowing one is true says nothing about the other. For example, “10 is even or 10 is a multiple of 5” is true and its first part is true, but “10 is not a multiple of 5” is false.
x \ne 0 makes neither part false. Both premises hold at x = -1, where the first part is true, and at x = 5, where the second is, so neither part is forced. A premise that denies the first part works, for example x \ge 1: it makes x < 1 false, and x > 4 follows.
\neg P removes only the part P. Knowing that Q or R is true does not say which, so the conclusion is Q \lor R and no more. With Q false and R true, both premises hold and Q fails.
Every integer is even or odd. Suppose n^2 is even. If n were odd, n = 2k + 1 for an integer k, and n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 would be odd, which it is not. So the part saying n is odd is denied, and by disjunctive syllogism n is even.
x^2 = x gives x^2 - x = 0, so x(x - 1) = 0, and by the zero product property x = 0 or x = 1. The premise x \ne 0 denies the first part, so x = 1.