Proofs

Some arguments proceed in stages. Rather than making a single inference from the premises to the conclusion, a complex argument may involve a series of simpler inferences. The conclusions of the first few inferences are then used as premises in a final inference to support the main conclusion. A complex argument like that is called a proof when each inference within the argument is justified by citing a specific inference rule or equivalence rule.

Proofs can be used to show that an argument is valid. Compared to other methods of demonstrating validity, proofs more closely resemble the way in which people ordinarily reason. By breaking down a complex argument into simple steps that are easy to follow, a proof can help us to understand why the argument is valid, rather than merely enabling us to recognize that it is valid. In other words, a proof can make it easier to see how the premises entail the conclusion. For this reason, constructing a proof can be a very effective means of understanding or explaining a complex argument.

Consider the following argument, for example:

If philosophers ponder profound problems, their quandaries quell quotidian quibbles. Their quandaries don’t quell quotidian quibbles, unless right reasoning reveals reality. Philosophers do ponder profound problems. Therefore, right reasoning reveals reality.

That is a valid argument: if its premises are true, the conclusion must be true as well. However, even if we assume that the premises are true, it’s not easy to see why the conclusion must be true too. We could construct a truth table or use the truth assignment method to confirm that the premises do entail the conclusion, but that wouldn’t necessarily help us to understand the argument.

To see how the argument really works, we can break it down into simple steps, using the inference and equivalence rules with which we’re already familiar. Notice that the first premise is a conditional: (P ⊃ Q). The third premise is the antecedent of that conditional: P. So, we can conclude that Q is true by modus ponens. The second premise is a disjunction: (~Q ∨ R). But ~Q is false, since we’ve already concluded that Q is true (and, of course, Q is equivalent to ~~Q by double negation). So, R must be true, by disjunctive syllogism.

I’ve explained why the argument is valid—that is, I’ve explained why the conclusion must be true, assuming that the premises are true. Since each step of my explanation was justified by citing an inference rule or equivalence rule, my explanation is a proof.

The above proof was presented informally, in plain English. To see the structure of an argument even more clearly, it is sometimes useful to construct a formal proof (also called a derivation). In a formal proof, each proposition used in the argument is numbered, beginning with the premises. The preliminary conclusions are listed after the premises, in the order that they are inferred (or derived) from the preceding propositions, and the last line of the proof is the main conclusion. Here is a formal presentation of the proof that was given above:

1.	(P ⊃ Q)	Premise
2.	(~Q ∨ R)	Premise
3.	P	Premise
4.	Q	MP 1,3
5.	~~Q	DN 4
6.	R	DS 2,5

Notice that the premises are labelled as such, and all subsequent propositions are justified with the (abbreviated) name of the inference or equivalence rule used to derive that proposition from the lines above it. The line numbers used in each inference are also indicated. For example, line 4 was derived by modus ponens from lines 1 and 3, so it is labelled with the justification “MP 1,3.”

A proof shows that an argument is valid. If you are unable to construct a proof, however, this doesn’t necessarily mean that the argument is invalid. The argument might be valid even though you can’t figure out how to construct a proof for it. For this reason, proofs should not be used as a test of invalidity. To determine whether an argument is invalid, use a truth table or the truth assignment method instead.

To construct a formal proof, begin by making a numbered list of the premises, and write “premise” next to each of them. Then derive other propositions from the premises using inference rules and/or equivalence rules, and use those propositions as new premises to derive the final conclusion. This isn’t as easy as it sounds. There are infinitely many ways to apply the inference and equivalence rules to any given set of premises, and not all of these ways lead to the desired conclusion! For this reason, constructing proofs can be challenging, especially when dealing with highly complex arguments. There is no simple method that always yields a successful proof. However, some clever strategies can make the task a little bit easier.

Here is a strategy that often works well. First, check whether any two of the premises can be used in an inference rule:

If you can infer another proposition from any two of the premises, write the conclusion of that inference on a new numbered line, just below the premises, and justify it by citing the inference rule and the line numbers of the premises from which you derived it.
If you can’t derive any new propositions using the inference rules, then use the equivalence rules to transform one of the premises. (Plan ahead, if possible, and try to transform the premise into something that you’ll be able to use later—preferably something that will allow you to use an inference rule in the next step of the proof.) Write the equivalent proposition on the next numbered line, and justify it by citing the equivalence rule and the line number of the premise from which you derived it.

Now, treat the newly-added proposition as though it were another premise, and repeat the above procedure. For each new step of the proof, first check whether any two of the propositions can be used in an inference rule. If not, then use an equivalence rule instead.

In other words, a good strategy is to use the inference rules whenever possible, and use the equivalence rules only when necessary (that is, when you can’t derive any new propositions from the inference rules). Below are a couple of examples to illustrate this strategy.

Let’s construct a proof for the following valid argument:

(P ∨ (Q ∨ R))

(R ⊃ S)

∴ (P ∨ Q)

We begin by numbering and labeling the premises, like this:

1.	(P ∨ (Q ∨ R))	Premise
2.	(R ⊃ S)	Premise
3.	~S	Premise

Next, we check whether it’s possible to derive any new propositions using the inference rules. We can’t make any inferences from premises 1 and 2, nor from premises 1 and 3. If we use premises 2 and 3, however, we can infer ~R by modus tollens:

1.	(P ∨ (Q ∨ R))	Premise
2.	(R ⊃ S)	Premise
3.	~S	Premise
4.	~R	MT 2,3

We can’t make any further inferences from those four propositions, so we must now turn to the equivalence rules. If we use the association equivalence rule to rearrange the parentheses in premise 1, we’ll be able to use disjunctive syllogism to infer the conclusion we want:

1.	(P ∨ (Q ∨ R))	Premise
2.	(R ⊃ S)	Premise
3.	~S	Premise
4.	~R	MT 2,3
5.	((P ∨ Q) ∨ R)	Assoc 1
6.	(P ∨ Q)	DS 4,5

Let’s try another example. Can we construct a proof for the following valid argument?

~(A • B)

(~B ⊃ C)

∴ (A ⊃ C)

Again, we begin by numbering and labeling the premises:

1.	~(A • B)	Premise
2.	(~B ⊃ C)	Premise

Next, we check whether any inference rules can be applied to those two premises. Unfortunately, in this case, we can’t use any inference rules yet, so we’ll have to try an equivalence rule instead. Which premise should we transform, and which equivalence rule should we use to transform it? As mentioned above, a good strategy is to plan ahead and transform a premise into something that we can use later—preferably something we can use in an inference rule. Notice that premise 2 is a conditional, and the argument’s conclusion is also a conditional. If we transform premise 1 into a conditional as well, then we’ll be able to use hypothetical syllogism to infer the conclusion.

No equivalence rule allows us to transform premise 1 into a conditional directly, but we can transform it to (~A ∨ ~B) by DeMorgan’s law, and then we can transform that into a conditional by implication:

1.	~(A • B)	Premise
2.	(~B ⊃ C)	Premise
3.	(~A ∨ ~B)	DM 1
4.	(A ⊃ ~B)	Imp 3

Now we can use an inference rule, finally! Lines 2 and 4 will serve as premises in a hypothetical syllogism, to derive the conclusion we wanted:

1.	~(A • B)	Premise
2.	(~B ⊃ C)	Premise
3.	(~A ∨ ~B)	DM 1
4.	(A ⊃ ~B)	Imp 3
5.	(A ⊃ C)	HS 2,4

The strategy illustrated above is usually effective, but it doesn’t generate proofs automatically. It takes practice and ingenuity to master the skill of constructing proofs. Here are two additional tips:

To keep the argument’s final conclusion in view while constructing a proof, you may find it helpful to write the conclusion below the premises. Leave plenty of space to write other steps between the premises and the (final) conclusion. Don’t number the conclusion yet, because you don’t know how many lines you’ll need for the proof.
If all else fails, as a last resort, try working backwards: transform the conclusion using one of the equivalence rules and write that equivalent proposition just above the conclusion. (Don’t number these last two lines of the proof yet, since you don’t know how many lines the proof will have.) Then try to derive the equivalent proposition, instead of trying to derive the conclusion directly.