How to Construct Proofs, Part 1: Working Backward

1. See a Proof Being Constructed

before you start

As we begin to construct proofs, you must have a good understanding of what proofs are and how they work, as well as the rules of inference we will use to construct our proofs and the shorthand for referring to them.

To recap, a proof shows step-by-step why a conclusion follows from a set of premises. Each step after the premises applies a rule of inference, noting which rule is applied and to which previous sentence(s) in the proof.

Rule	Notation	Definition	General Form	Example
Conditional Elimination	→E	If we know a conditional and its antecedent are true, we can conclude that the consequent is also true.	p → q p ∴q	If it rains, the ground is wet. It rained, so the ground must be wet.
Modus Tollens	MT	If we know a conditional and the negation of its consequent are true, we can conclude the negation of the antecedent.	p → q ¬q ∴¬p	If it’s raining, the ground is wet. The ground is not wet, so it must not have rained.
Conditional Introduction	→I	If we know two conditionals are true, and the consequent of one is the antecedent of the other, we can conclude that a novel conditional is true, with the antecedent of the first and the consequent of the second.	p → q q → r ∴p → r	If it rains, the ground is wet, and if the ground is wet, I don’t have to water the lawn. So, if it rains, I don’t have to water the lawn.
Conjunction Elimination	^E	If we know a conjunction is true, we can conclude that either conjunct is true.	p ∧ q ∴p	I have a refrigerator and a freezer. Therefore, I have a freezer.
Conjunction Introduction	^I	If we have two sentences that are true, we can conclude that their conjunction is also true.	p q ∴p ∧ q	I have a son. I have a daughter. Therefore, I have a son and daughter.
Disjunctive Syllogism	DS	If we know a disjunction and the negation of one disjunct are true, we can conclude that the other disjunct is true.	p ∨ q ¬p ∴q	Diner: I’ll have either the roast beef or the shrimp. Server: We’re all out of shrimp. Diner: Then I’ll have the roast beef!
Disjunction Introduction	∨I	If we know that one sentence is true, we can conclude the truth of a novel disjunction with the first sentence as one disjunct, and any other sentence as the second.	p ∴p ∨ q	I have a cat, so yes, I have a cat or a dog.
DeMorgan’s Laws	DeM	We can rewrite certain sentences with conjuncts and negations or disjuncts and negations by “pushing the negation,” and “flipping the sign.”	¬(p ∨ q) ↔ ¬p ∧ ¬q ¬(p ∧ q) ↔ ¬p ∨ ¬q	Carla won’t have cake or ice cream. Therefore, Carla won’t have cake and won’t have ice cream.

There are two ways to approach a proof. The first is working backward, where we start with the conclusion and see how to derive it, by gradually filling in intermediate steps until we reach the premises. If we know our conclusion, this is often the best way to go. Here is an example:

1. R ∧ S
2. T
3. ∴ (T ∨ L) ∧ (R ∧ S)

1. R ∧ S
2. T
   .
   .
   .
   (T ∨ L) ∧ (R ∧ S)

The conclusion here, (T ∨ L) ∧ (R ∧ S), has ∧, conjunction, as the main operator. What rule can derive this conjunction? There is only one—Conjunction Introduction, which introduces a conjunction when we have already established that both conjuncts are true. We note to the right of the conclusion, “∧I” for Conjunction Introduction.

1. R ∧ S
2. T
   .
   .
   .
   (T ∨ L) ∧ (R ∧ S)       ∧I

think about it

What two sentences will be referenced in the conjunction rule? Look at the table above if you need to.

We need two lines establishing that the sentences we are conjoining are true.

So, what are the conjuncts we need to establish as true in order to derive the conjunction/conclusion? We need both T ∨ L on one line and R ∧ S on another. Now look at premise 1—there we are already assuming that R ∧ S is true! We add that to the note, leaving a space for the other line.

1. R ∧ S
2. T
   .
   .
   .
   (T ∨ L) ∧ (R ∧ S)       ∧I 1,

We need to derive the sentence T ∨ L. Once that’s on a separate line, we can use the conjunction rule to conjoin those two sentences to derive the conclusion. We add this line to the proof, but need to indicate that it is not yet proven; we will use italics to do that. We will also refrain from numbering it yet, since we will require more steps of reasoning to get there.

1. R ∧ S
2. T
   .
   .
   .
   T ∨ L
   (T ∨ L) ∧ (R ∧ S)       ∧I 1,

So, how can we derive the sentence T ∨ L? What rule allows us to derive a disjunction? There are two: Disjunction Introduction and DeMorgan’s Laws. However, we can rule out DeMorgan’s Laws because none of our sentences are negated, and those laws revolve around negation. That leaves Disjunction Introduction.

think about it

In the previous paragraph, we reasoned about which rule to apply by actually using one of our rules of inference.

Can you see which one it is?

We have a disjunction in the sentence, so we can use Disjunction Introduction or DeMorgan’s Laws. However, since we don’t have negation in the sentence, we cannot use DeMorgan’s Laws; therefore, we must use Disjunction Introduction. This is an example of Disjunctive Syllogism and shows how these rules of inference tend to lie beneath many decisions.

Recall that the rule of Disjunction Introduction allows us to infer a sentence with a disjunction when one disjunct is already established to be true, and we can introduce any other sentence as the second disjunct. We can thus derive T ∨ L, if either T or L is previously established in our proof. Look at the premises again: we already have T, so we have all we need to derive T ∨ L. Since we already have the line penciled in, we can now solidify it with a number and a notation. The notation will be ∨I, for Disjunction Introduction. We need only refer to one previous sentence, line 2 from the premises. We don’t need support for the other disjunct, L, because only one part of the disjunct need be true for the disjunction to be true. So now our proof is almost complete.

1. R ∧ S
2. T
3. T ∨ L                       ∨I 2
   .
   .
   .
   (T ∨ L) ∧ (R ∧ S)     ∧I 1,

1. R ∧ S
2. T
3. T ∨ L                           ∨I 2
4. (T ∨ L) ∧ (R ∧ S)         ∧I 1,3

That’s it. That is all there is to constructing a proof. Let’s check our work. 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. We do not need a truth table or to generate counterexamples to test the validity; the proof establishes the validity of the argument.

watch

View a demonstration of this example.

term to know

Working Backward

A method for drafting a proof where we start with the conclusion of the argument and see how it can be derived, then see how we can derive any intermediate steps until we have no gaps between the premises and the conclusion.

2. Construct a Proof Yourself

Now that you have seen a proof constructed, you should be ready to try it yourself. In the exercise below, you will follow along with the steps, completing each step before you check your work.

hint

While these symbols are part of the expanded character set on all computers, in a pinch, you may also use workarounds: lowercase v for a disjunction, carat (^, shift 6) for a conjunct, a dash and bracket (->) for a conjunction, and a tilde (~) for a negation. However, the standard set of symbols is strongly preferred. You can copy/paste the proper set of symbols from the website proofs.openlogicproject.org/.

step by step

Work backwards from the conclusion to construct a proof.

1. A ∧ B
2. (A ∨ C) → D
3. ∴ A ∧ D

First, what rule do we need to derive the conclusion?

Check Your Answer

The conclusion is a conjunction, so we will need to use Conjunction Introduction, which allows us to infer one.

1. A ∧ B
2. (A ∨ C) → D
   .
   .
   .
   A ∧ D                  ∧I

Next, what sentences do we need to derive the conclusion?

Check Your Answer

Since we are using Conjunction Introduction to derive the conclusion, we need to first establish both conjuncts A and D on separate lines to employ this rule.

1. A ∧ B
2. (A ∨ C) → D
   .
   .
   .
   A
   D
   A ∧ D                   ∧I

Here we use italics to show that A and D are speculative at this point; we know we need them for our conclusion, but have not yet established that they are true.

Next, how can we derive first A from the premises? There are four rules of inference that can give us a single proposition: Conditional Elimination, Modus Tollens, Conjunction Elimination, and Disjunctive Syllogism. Which of these can be applied in this situation?

Check Your Answer

The first premise is a conjunction with A, so we can apply Conjunction Elimination to derive A. Since we have it penciled in, we need only give it a number and note the rule we applied and the previous sentence we applied it to. We can also add the first number to our final notation.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   .
   .
   .
   D
   A ∧ D                  ∧I 3,

Now we need to establish that D is true. Looking at previous sentences with D, we see it only as the consequent of the conditional in line 2. This tells us two things. First, what rule must we use to derive D?

Check Your Answer

We must use Conditional Elimination to derive D, since the only sentence we have using D is a conditional with D as the consequent. We can thus add this incomplete note to the draft proof to remind us what our next step is. We also know the first sentence the rule will be applied to is line 2, so we can add that to the note.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   .
   .
   .
   D                         →E 2,
   A ∧ D                  ∧I 3,

Next, what sentence must we add to derive D using the rule we just identified?

Check Your Answer

Since we are using Conditional Elimination to derive D from the conditional in line 2, we must have a line deriving A ∨ C.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   .
   .
   .
   A v C
   D                         →E 2,
   A ∧ D                  ∧I 3,

Uh oh, this proof is turning out to be a bit more work than the other one. We now have another sentence we need to derive. Do you see any way to derive A ∨ C, the antecedent of the conditional sentence in line 2?

Check Your Answer

A ∨ C is a disjunction, so we can use Disjunction Introduction to derive it.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   .
   .
   .

A v C                  ∨I
D                         →E 2,
A ∧ D                  ∧I 3,

To complete the note and make the sentence official, we only need one of the disjuncts to be true. Do we have either A or C as a standalone sentence in the proof? We do! We derived it earlier in line 3. We can thus also give this line a number, 4, making it official, and complete the note by indicating the rule of Disjunction Introduction was applied to line 3.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   
4. A v C                  ∨I3
   .
   .
   .
   D                         →E 2,
   A ∧ D                  ∧I 3,

What next? If you aren’t sure what we need to derive next, it is because there is nothing left to derive. We only have to finish and formalize our work. This is where you might see which lines are still italicized, lack numbers, or have incomplete notes (or whatever personal techniques you come up with to complete proofs in draft form). We see that the line establishing D is all three: unnumbered, in italics, and has an incomplete note. What do we need to do?

Check Your Answer

We see from our note that we were deriving D from the conditional on line 2 and only needed the antecedent, which we derived in the previous step on line 4. So, we can finalize that note by adding “4”, then give the line a number and make it official by removing the italics.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   
4. A v C                  ∨I 3
   
5. D                         →E 2, 4
   
6. A ∧ D                  ∧I 3,

Now we only need to finish up with the conclusion. How can we do that?

Check Your Answer

We need to complete the note for conjunction. We have applied the rule to sentence 3 (A), which is already shown, and can now add 5 for the sentence we just derived (D). Since the conclusion is now complete, we can also give it a number.

1. A ∧ B
2. (A ∨ C) → D
3. A                         ∧E 1
   
4. A v C                  ∨I 3
   
5. D                         →E 2, 4
   
6. A ∧ D                  ∧I 3, 5

If you were able to follow along and complete the proof, you are well on your way to being a logician (and thus a good critical thinker!). See the formalized proof below.

See the Completed Proof

watch

View a demonstration of this example.

SOURCE: THIS TUTORIAL HAS BEEN ADAPTED FROM 1)“INTRODUCTION TO LOGIC AND CRITICAL THINKING” BY MATTHEW J. VAN CLEAVE. ACCESS FOR FREE AT OPEN.UMN.EDU/OPENTEXTBOOKS/TEXTBOOKS/457 2) “FORALL X: CALGARY” BY TIM BUTTON. ACCESS FOR FREE AT FORALLX.OPENLOGICPROJECT.ORG. LICENSE: CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL.