Discrete Mathematics and Proof

Valid and sound arguments

An argument’s conclusion follows from its premises by the rules of logic. Does that make the conclusion true?

Unlocks

Modus ponens, chaining, and a common fallacyDiscrete Mathematics and Proof Testing an argument with a truth tableDiscrete Mathematics and Proof Modus tollens, ruling out, and a common fallacyDiscrete 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

An argument offers some statements as reasons for a final one. Some arguments force their conclusion; others only look as if they do. And even an argument whose logic is airtight can start from a false statement. “Does the conclusion follow?” and “are the starting statements true?” are two separate questions, and a reader who runs them together can be taken in by either kind of bad argument. The two words in this lesson keep them apart: valid answers the first question, sound answers both.

Definition

An argument is a list of statements, the premises, followed by one more statement, the conclusion, which the premises are offered to support. Arguments are usually written with the premises stacked, a line, and the conclusion marked \therefore (“therefore”):

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

Every premise and the conclusion must be a statement: a sentence that is definitely true or definitely false, never both and never neither.

An argument is valid when there is no way for every premise to be true and the conclusion false at the same time. Equivalently: whenever all the premises are true, the conclusion is forced to be true along with them. Validity says nothing about whether the premises actually are true; it only says what would happen if they were.

An argument is sound when it is valid and every one of its premises is actually true.

Intuition

Think of an argument as a machine: premises go in, the conclusion comes out. A valid argument is a machine built correctly: feed it true statements and it only ever produces a true one. You can judge that from how the machine is put together, without running it, which is why validity is a question about the argument’s form. A sound argument is a valid machine that has actually been loaded with true premises. Whether they are true is a separate question, which logic alone cannot answer. Only when both hold can you trust the output.

Results

Theorem (a sound argument’s conclusion is true). If an argument is sound, its conclusion is true.

Fact (validity is about form, not subject). Whether an argument built from connectives such as \to, \land, \lor and \lnot is valid depends only on its form: which letters sit where, joined by which connectives. It never depends on what the letters stand for. Replace P, Q and R throughout a valid argument with any statements, about any subject, and the result is still valid; the same holds for an invalid one. Arguments about “all” and “some” have a form too, and the same is true of them.

Why it is true

Suppose an argument is sound. By the first half of “sound,” it is valid: whenever all its premises are true, its conclusion is true. By the second half, every one of its premises is true, in the one situation the argument is actually about. So validity’s “whenever” applies to that very situation, and the conclusion is true there too. Soundness hands validity the one case it needs, and validity does the rest.

Read the theorem’s contrapositive and you get a second useful fact: if a valid argument has a false conclusion, at least one of its premises is false. A false conclusion from a valid argument is not a flaw in the logic; it is news about the premises.

The fact about form follows from the definition of valid. “No assignment of true and false makes every premise true and the conclusion false” mentions only the truth values the letters can take and how the connectives combine them, never what the letters mean. New statements with the same structure take the same truth values in the same combinations, so the verdict cannot change.

Worked examples

Example 1

A valid, sound argument

All squares are rectangles. This shape is a square. Therefore, this shape is a rectangle.

Solution

Let P be “this shape is a square” and Q be “this shape is a rectangle.” The argument has the form

P \to Q, \qquad P, \qquad \therefore\ Q

If P \to Q and P are both true, Q cannot be false, since a true P with a false Q would make P \to Q false. So the argument is valid; this form is modus ponens. Both premises are also actually true: every square satisfies the definition of a rectangle, and the shape is given to be a square. Valid with true premises makes it sound, so by the theorem its conclusion is true.

Example 2

A valid argument that is not sound

All prime numbers are odd. The number 2 is a prime number. Therefore, 2 is odd.

Solution

With P = “2 is prime” and Q = “2 is odd,” this has the same form as Example 1, P \to Q, P, \therefore\ Q, so the argument is valid.

But the first premise is false: 2 is prime and even, a counterexample to “all prime numbers are odd.” With a false premise the argument is not sound, even though it is valid. Its conclusion is false as well (2 is not odd), which the theorem allows: it promises a true conclusion only from a sound argument.

Example 3

An invalid argument

Today is Saturday or today is a holiday. Today is Saturday. Therefore, today is not a holiday.

Solution

Let P = “today is Saturday” and Q = “today is a holiday.” The premises are P \lor Q and P; the conclusion is \lnot Q.

To show an argument invalid, find one assignment of true and false that makes every premise true and the conclusion false. Try P true and Q also true: a Saturday that happens to be a holiday. Then P \lor Q is true and P is true, so both premises hold, but \lnot Q is false. That single case is a counterexample, so the argument is invalid.

The argument treats “P or Q” as if it ruled Q out once P is confirmed. It does not: “or” allows both, so knowing P tells you nothing about Q.

Example 4

An invalid argument that looks plausible

If P is true, so is R. If Q is true, so is R. R is true. Therefore, P or Q is true. (Adapted from Levin, Discrete Mathematics: An Open Introduction, Example 3.1.7.)

Solution

The premises are P \to R, Q \to R and R; the conclusion is P \lor Q. A counterexample must make the conclusion false, so start there. P \lor Q is false only when P and Q are both false. Now try to make the premises true as well. With P false, P \to R is true whatever R is, and likewise Q \to R; the third premise just needs R true. So P false, Q false, R true makes all three premises true and the conclusion false. That assignment is a counterexample, and the argument is invalid.

Read aloud it sounds convincing: both roads lead to R, we ended up at R, so we must have taken one of them. But R can have a third cause. If P is “it rained,” Q is “the sprinkler ran” and R is “the grass is wet,” someone may simply have spilled a bucket.

Swap the third premise and the conclusion, and the pattern becomes valid: from P \to R, Q \to R and P \lor Q, conclude R. Search for a counterexample the same way. For R to be false while P \to R is true, P must be false; for Q \to R to be true, Q must be false too; and then P \lor Q is false. No assignment makes all three premises true with R false, so this argument is valid. A full truth table reaches both verdicts row by row; searching from a false conclusion is quicker because it looks only at the cases that could be counterexamples, and it still covers every one of them.

Example 5

An invalid argument in which every statement is true

All squares are quadrilaterals. All rectangles are quadrilaterals. Therefore, all squares are rectangles.

Solution

Every statement here is true, the conclusion included, so it is tempting to call the argument good. Validity asks something else: can an argument of this form carry true premises to a false conclusion?

The form is: all A are C; all B are C; therefore all A are B. These are statements about “all” (a universal quantifier), not single statements joined by connectives, so a truth table of T and F values is not the tool for them. Invalidity is shown instead by a counterexample interpretation: new categories put in the same places, making both premises true and the conclusion false. Take A = cats, B = dogs, C = mammals:

All cats are mammals. All dogs are mammals. Therefore, all cats are dogs.

Both premises are true and the conclusion is false. Since validity depends only on the form, and this form can carry true premises to a false conclusion, the original argument is invalid too. Its conclusion is true for a reason the premises never mention, the definition of a rectangle. Sharing a larger category C never places A inside B.

Boundaries

One counterexample settles invalidity; agreeing cases settle validity only if they are all of them. An argument built from connectives has finitely many assignments, so checking every one (a full truth table, or a search that covers every case with a false conclusion, as in Example 4) settles validity. Checking some of them never does. An argument about “all” has endlessly many interpretations, so no list of them proves it valid; that takes a proof. A single counterexample interpretation, as in Example 5, still proves it invalid.

Validity is silent about truth outside the argument. A valid argument with a false premise can have a true conclusion or a false one; the theorem only constrains sound arguments.

Soundness is not something logic alone can settle. Whether a premise is actually true is a fact about the world (arithmetic, geometry, the weather), not about the argument’s shape.

The premises must be genuine statements. A question or a command has no truth value, so “valid” and “sound” do not apply to an argument built from one.

Where this goes next

A handful of forms are valid whatever statements fill in P, Q and R, which makes them worth knowing by name: modus ponens, modus tollens, hypothetical syllogism and disjunctive syllogism. Just as useful are two patterns that look like those but are invalid, affirming the consequent and denying the antecedent. For an argument with no familiar shape, testing it with a truth table settles the question mechanically. And every geometric proof is, underneath its diagram, a chain of valid steps from premises already accepted as true, which is what makes its conclusion sound.

Exercises

Reading an argument

“All whales are mammals. Whales live in the ocean. Therefore, some mammals live in the ocean.” Identify the premises and the conclusion.
True or false: “In a valid argument, every premise must be true.” Explain.

Testing validity

For each argument, decide whether it is valid. If it is invalid, give one assignment of true and false to the letters that makes every premise true and the conclusion false.

P \to Q, \ Q \to R, \ \lnot R \ \therefore\ \lnot P
P \lor Q, \ Q \ \therefore\ \lnot P
P \to Q, \ P \to R \ \therefore\ Q \to R
P \land Q \ \therefore\ P \lor Q
\lnot(P \land Q) \ \therefore\ \lnot P \lor \lnot Q
P \to Q, \ R \to Q, \ P \lor R \ \therefore\ Q

Soundness

“If a number is divisible by 6, then it is divisible by 3. 18 is divisible by 6. Therefore, 18 is divisible by 3.” Is this argument valid? Is it sound?
“If a number is divisible by 6, then it is divisible by 2. If a number is divisible by 4, then it is divisible by 2. Therefore, if a number is divisible by 6, then it is divisible by 4.” Show this argument is invalid by naming one number that makes both premises true and the conclusion false.
“If a number is divisible by 4, then it is divisible by 8. 12 is divisible by 4. Therefore, 12 is divisible by 8.” Is this argument valid? Is it sound? Is its conclusion true?
Give an argument that is valid but not sound.
Can an unsound argument have a true conclusion? Give an example or explain why not.

Building arguments

Write an argument with the form P \to Q, P \therefore\ Q using real statements about even numbers, and check that it is both valid and sound.
Write an argument, using any statements you like, that is invalid even though every statement in it is true. (Example 5 is one template to copy.)
Explain why listing an argument’s premises in a different order never changes whether the argument is valid.

Reasoning

Explain why a single counterexample is enough to prove an argument invalid, but checking many cases in which the premises and the conclusion are all true does not prove it valid unless the cases checked are all the cases there are.
An argument has all-true premises, and its conclusion also happens to be true. Must the argument be valid? Use one of the worked examples to justify your answer.
Prove: if an argument is valid and its conclusion is false, then at least one of its premises must be false.

Answers

Premises: “All whales are mammals” and “Whales live in the ocean.” Conclusion: “Some mammals live in the ocean.”
False. Validity only says what happens if the premises are true. Example 2 is valid, yet its first premise, “all prime numbers are odd,” is false. Truth of the premises is what soundness adds, not what validity requires.
Valid. \lnot R true makes R false, which forces Q false (from Q \to R), and Q false then forces P false (from P \to Q), so no assignment makes all three premises true with \lnot P false.
Invalid. P true, Q true is a counterexample: P \lor Q is true, Q is true, but \lnot P is false.
Invalid. P false, Q true, R false is a counterexample: P \to Q and P \to R are both true because P is false, but Q \to R is false, since Q is true and R is false.
Valid. If P \land Q is true then both P and Q are true, so P \lor Q, which needs only one of them, is true too.
Valid. \lnot(P \land Q) true means P and Q are not both true, so at least one of them is false, which is exactly \lnot P \lor \lnot Q.
Valid. If P \lor R is true, at least one of P, R is true. If P is true, P \to Q forces Q true; if R is true, R \to Q forces Q true. Either way Q is true.
Valid: it has the form P \to Q, P \therefore\ Q. Sound: both premises are true (18 = 6 \cdot 3, and every multiple of 6 is a multiple of 3), so it is sound as well.
n = 6. The first premise holds for 6, since 6 is divisible by 6 and by 2. The second holds because its “if” part is false: 6 is not divisible by 4. The conclusion fails: 6 is divisible by 6 but not by 4, since 6 \div 4 = 1.5. (Any multiple of 6 that is not a multiple of 4, such as 18 or 30, works as well.)
Valid: same form as Exercise 9. Not sound: the first premise is false, since 4 is divisible by 4 but not by 8. The conclusion is also false: 12 \div 8 = 1.5 is not a whole number.
Many are possible, for example: “All multiples of 10 are even. 15 is a multiple of 10. Therefore, 15 is even.” This has the valid form P \to Q, P \therefore\ Q, but the second premise is false (15 \div 10 = 1.5), so it is not sound.
Yes. An argument is unsound when it is invalid, or valid with a false premise, and neither stops the conclusion from being true by coincidence. Example 5 is invalid, yet every statement in it, the conclusion included, is true.
For example: “If a number ends in 0, 2, 4, 6 or 8, it is even. 14 ends in 4. Therefore, 14 is even.” The form is P \to Q, P \therefore\ Q and both premises are true, so the argument is valid and sound.
For example, Example 5’s form with numbers: “All multiples of 4 are even. All multiples of 2 are even. Therefore, all multiples of 4 are multiples of 2.” All three statements are true, but the form (all A are C, all B are C, therefore all A are B) is invalid, as the cats, dogs and mammals interpretation in Example 5 shows.
Validity asks only whether some assignment makes all the premises true at once with the conclusion false. “P \to Q is true and R is true” is the same condition as “R is true and P \to Q is true,” so reordering the premises changes nothing the definition checks.
A counterexample is one case with every premise true and the conclusion false, and “invalid” means exactly that such a case exists, so one settles it. “Valid” is a claim about every case, so any case left unchecked could be the one that fails. In Example 4 only one of the eight assignments of P, Q, R is a counterexample, so checking the other seven would have found nothing wrong.
No. Example 5 has true premises and a true conclusion, yet it is invalid: the cats, dogs and mammals argument has the same form, true premises and a false conclusion. Validity is about the form, so what happens to be true in one case cannot make an argument valid.
Suppose the argument is valid and its conclusion is false. If every premise were true, this situation would have all premises true and the conclusion false, which validity rules out. So not every premise is true: at least one is false.