Article: Constructing proofs (Dr. Van Cleave)

By Matthew Van Cleave

You can think of constructing proofs as a game.  The goal of the game is to derive the conclusion from the given premises using only the 8 valid rules of inference that we have introduced. Not every proof requires you to use every rule, of course.  But you may use any of the rules—as long as your use of the rule is correct.  Like most games, people can be better or worse at the “game” of constructing proofs.  Better players will be able to a) make fewer mistakes, b) construct the proofs more quickly, and c) construct the proofs more efficiently.  In order to construct proofs, it is imperative that you internalize the 8 valid forms of inference introduced in the previous section.  You will be citing these forms of inference as rules that will justify each new line of your proof that you add.  By “internalize” I mean that you have memorized them so well that you can see those forms manifest in various sentences almost without even thinking about it.  If you internalize the rules in this way, constructing proofs will be a pleasant diversion, rather than a frustrating activity.  In addition to internalizing the 8 valid forms of inference, there are a couple of different strategies that can help when you’re stuck and can’t figure out what to do next.  The first is the strategy of working backwards.  When we work backwards in a proof, we ask ourselves what rule we can use to derive the sentence(s) we need to derive.  Here is an example:

The conclusion, which is to the right of the second premise and follows the “/∴” symbol, is a conjunction (since the dot is the main operator).  If we are trying to “work backwards,” the relevant question to ask is: What rule can we use to derive a conjunction?  If you know the rules, you should know the answer to that question.  There is only one rule that allows us to derive (infer) a sentence that is a conjunction.  That rule is called “conjunction.”  The form of the rule conjunction says that in order to derive a conjunction, we need to have each conjunct on a separate line.  So, what are the two conjuncts that we would need in order to derive the conjunction that is the conclusion (i.e., “(T v L) ⋅ (R ⋅ S)”).  We would need both “T v L” on a line and “R ⋅ S” on a separate line.  But look at premise 1—we already have “R ⋅ S” on its own line!  So the only other thing we need to derive is the sentence “T v L”.  Once we have that on a separate line, then we can use the rule conjunction to conjoin those two sentences to get the conclusion!  So the next question we have to ask is: How can I derive the sentence “T v L”?  Again, if we are working backwards, the relevant question to ask here is: What rule allows me to derive a disjunction?  There are only two: constructive dilemma and addition.  However, we know that we won’t be using constructive dilemma since none of the premises are conditional statements, and constructive dilemma requires conditional statements as premises.  That leaves addition.  Addition allows us to disjoin any statement we like to an existing statement.  Since we have “T” as the second premise, the rule addition allows us to disjoin “L” to that statement.  The first new line of the proof should thus look like this:

What I have done is number a new line of the proof (continuing the numbering from the premises) and then have written the rule that justifies that new line as well as the line(s) from which that line was derived via that rule.  In this case, since addition is a rule that allows you to derive a sentence directly from just one line, I have cited only one line.  The next step of the proof should be clear since we have already talked through it above.  All we have to do now is go directly to the conclusion, since the conclusion is a conjunction and we now have (on separate lines of the proof) each conjunct.  Thus, the final line of this (quite simple) proof should look like this:

Again, all I’ve done is the write the new line of the proof (continuing the numbering from the previous line) and then have written the rule that justifies that new line as well as the line(s) from which that line was derived via that rule.  In this case, the rule conjunction requires that we cite two lines (i.e., each conjunct that we are conjoining).  So, I have to find the lines that contained “T v L” and “R ⋅ S” and cite those lines.  It does not matter the order in which you cite the lines as along as you have cited the correct lines (e.g., I could have equally well have written, “Conjunction 3, 1” as the justification).  Thus the complete proof should look like this:

That’s it.  That is all there is to constructing a proof.  The last line of the proof is the conclusion to be derived: check.  Each line of the proof follows by the rule and the line(s) cited: check.  Since both of those requirements check out, our proof is complete and correct.

I have just walked you through a simple proof using the strategy of working backwards.  This strategy works well as long as the conclusion we are trying to derive is complex—that is, if it contains truth functional connectives.  However, sometimes our conclusion will simply be an atomic statement.  In that case, we will not as easily be able to utilize the strategy of working backwards.  But there is another strategy that we can utilize: the strategy of working forward.  To utilize the strategy of working forward, we simply ask ourselves what rules we can apply to the existing premises to derive something, even if it isn’t the conclusion we are ultimately trying to derive.  As a part of this strategy, we should typically break apart a conjunction whenever we have one as a premise of our argument.  Doing this can help to see where to go next.  (If you’ve ever played Scrabble, then you can think of this as rearranging your Scrabble tiles in order to see what words you can build.)  Here is an example of a proof where we should utilize the strategy of working forward:

Notice that since the conclusion is atomic, we cannot utilize the strategy of working backwards.  Instead, we should try working forward.  As part of this strategy, we should break apart conjunctions by using the rule “simplification.”  That will be the first step of our proof:

The first two lines of the proof is just breaking down the conjunction in line 1, where line 3 is just the left conjunct and line 4 is just the right conjunct.  Both lines 3 and 4 follow by the same rule and the same line, in this case.  The next question we ask when utilizing the strategy of working forward is: what lines of the proof we can apply some rule to in order to derive something or other?  Look at the conditional on line 2.  We haven’t used that yet.  So what rule can we apply to that line?  You should be thinking of the rules that utilize conditional statements (modus ponens, modus tollens, and hypothetical syllogism).  We can rule out hypothetical syllogism since here we have only one conditional and the rule hypothetical syllogism requires that we have two.  If you look at line 4 (that we have just derived) you should see that it is the antecedent of the conditional statement on line 2.  And you should know that that means we can apply the rule, modus ponens.  So our next step is to do that:

But now also notice that the line that we have just derived is in fact the conclusion of the argument.  So our proof is finished.

Before the close of this section, let’s work through a bit longer proof.  Remember: any proof, long or short, is the same process and utilizes the same strategy.  It is just a matter a keeping track of where you are in the proof and what you’re ultimately trying to derive.  So here is a bit more complex proof:

The conclusion is a conjunction of “L v G” and “~R” so we know that if we can get each of those sentences on a separate line, then we can use the rule conjunction to derive the conclusion.  That will be our long range goal here (and this is utilizing the strategy of working backwards).  However, we cannot see how to directly get there from here at this point, so we will begin utilizing the strategy of working forward.  The first thing we’ll do is simplify the conjunction on line 5:

Look at lines 2 and 6: they are both negated atomic propositions.  Another part of the strategy of working forward is to utilize either atomic or negated atomic sentences.  We should look for how we can utilize modus tollens or disjunctive syllogism by plugging these negated atomic sentences into other lines of the proof.  Look at lines 2 and 3.  You should see a modus tollens there.  That will be our next step:

The next step of this proof can be a bit tricky.  There are a couple different ways we could go.  One would be to utilize the rule “addition.”  Can you see how we might helpfully utilize this rule using either line 6 or 8?  If not, I’ll give you a hint: what if we were to use addition on line 8 to derive “~A v B”?  Can you see how we could then plug that into line 1?  In fact, “~A v B” is the antecedent of the conditional in line 1, so we could then use modus ponens to derive the consequent.  Thus, let’s try starting with the addition on line 8:

Next, we’ll utilize line 9 and line 1 with modus ponens to derive the next line:

Notice at this point that what we have derived on line 10 is “L” and what we earlier said we needed as one of the conjuncts was “L v G”.  You should recognize that we have a rule that will allow us to infer directly from “L” to “L v G”.  That rule is addition (again).  That will be the next line of the proof:

At this point, our strategy should be to try to derive the other conjunct, “~R”.  Notice that “~R” is contained within the sentence on line 4, but it is embedded.  How can we “get it free”?  Start by noticing that the ~R is a part of a disjunction, which is itself a consequent of a conditional statement.  Also notice that we have already derived the antecedent of that conditional statement, which means that we can use modus ponens to derive the consequent:

The penultimate step is to use a disjunctive syllogism to derive “~R”. 

The final step is simply to conjoin lines 11 and 13 to get the conclusion:

Thus, here is the completed proof:

Constructing proofs is a skill that takes practice. Quiz 11 involves 20 proofs. All 20 items are available below. Make sure you work through these proofs before starting the online quiz.

Quiz 11 Questions

You have two hours for this quiz. There are 20 questions, each worth a point. The entire quiz is worth 20 points.

Construct proofs for the following valid arguments. The first fifteen proofs can be done in only a few additional lines. The last five proofs will be a bit longer. Often there is more than one way to construct a proof. Work through these 20 arguments and create proofs for each one on paper. After you've done your best on all twenty, do the online quiz. It covers these same 20 arguments.

Proofs for #1 and #2 are provided here as examples.

#1

1.     A ⋅ B

2.     (A v C) ⊃ D      /∴ A ⋅ D

#2

1.     A

2.     B          /∴ (A v C) ⋅ B

#3

1.     D ⊃ E

2.     D ⋅ F               /∴ E

 

#4

1.     J ⊃ K

2.     J          /∴ K v L

 

#5

1.     A v B

2.     ~A ⋅ ~C          /∴ B

 

#6

1.     A ⊃ B

2.     ~B ⋅ ~C          /∴ ~A

 

#7

1.     D ⊃ E

2.     (E ⊃ F) ⋅ (F⊃  D)  /∴D ⊃ F

 

#8

1.     (T ⊃ U) ⋅ (T ⊃ V)

2.     T                      /∴ U v V

 

#9

1.     (E ⋅ F) v (G ⊃ H)

2.     I ⊃ G

3.     ~(E ⋅ F)           /∴ I ⊃ H

 

 

#10

1.     M ⊃ N

2.     O ⊃ P

3.     N ⊃ P

4.     (N ⊃ P) ⊃ (M v O)  /∴N v P

 

#11

1.     A v (B ⊃ A)

2.     ~A ⋅ C            /∴ ~B

 

#12

1.     (D v E) ⊃ (F ⋅ G)

2.     D                     /∴ F

 

#13

1.     T ⊃ U

2.     V v ~U

3.     ~V ⋅ ~W         /∴ ~T

 

#14

1.     (A v B) ⊃ ~C

2.     C v D

3.     A                     /∴ D

 

#15

1.     L v (M ⊃ N)

2.     ~L ⊃ (N ⊃ O)

3.     ~L                    /∴ M ⊃ O

 

#16

1.     A ⊃ B

2.     A v (C ⋅ D)

3.     ~B ⋅ ~E          /∴ C

 

#17

1.     (F ⊃ G) ⋅ (H ⊃ I)

2.     J ⊃ K

3.     (F v J) ⋅ (H v L)   /∴ G v K

 

#18

1.     (E v F) ⊃ (G ⋅ H)

2.     (G v H) ⊃ I

3.     E                      /∴ I

 

#19

1.     (N v O) ⊃ P

2.     (P v Q) ⊃ R

3.     Q v N

4.     ~Q      /∴ R

 

#20

1.     J ⊃ K

2.     K v L

3.     (L ⋅ ~J) ⊃ (M ⋅ ~J)

4.     ~K                   /∴ M