I will walk you through the three general proof strategies - the only strategies you'll need in this class - using proofs as examples.
Proof Strategies
There are three strategies you'll need in this class for proofs: Direct, Conditional, Indirect.
Direct Proof: In many cases to prove something you need only apply one or more rules without making any assumptions. For example, I might want to prove "P v Q" follows from "P". That's simple:
P
P v Q vI, 1
We just introduce a disjunct and we're done. The absence of the need to make additional assumptions is a hallmark of Direct Proof.
Of course, were that the only sort of proof strategy, we'd not be able to prove much. Fortunately, we have others.
Conditional Proof: Sometimes you're asked to prove something of the form: "P -> Q", i.e. something that has "->" as the main connective. This might be simple, as is the example I just gave, or it could be complex, like: "(P /\ R) -> ~(S v T). In either case, if the main connective is a conditional then you will be using the Conditional Proof Strategy. You have a basic rule that reflects this already, namely, "->I". But let's make sure you know when to use it.
Pro-Tip - This is a common stumbling point for students, so pay attention to what I say here even if you feel confident about using "->I". Students often feel confident about logical steps when they see them, but then have trouble proving things on their own. That's likely because every step we make in this class should seem obviously true on reflection. You make inferences like this in your daily life all the time. Of course you can follow a proof; we're not trying to teach you that skill. Rather, we're teaching you how to prove things on your own, intentionally.
Anytime you need to prove a statement that has a conditional as its main connective, you will always assume the antecedent. This is important to keep in mind for at least one good reason. In our logic, you can assume anything you want. Literally, anything, e.g. "P /\ ~P". That's fine, you won't break the logic. That might seem overwhelming. You might feel you have too much freedom to assume things, and so you might find it difficult to know where to start making assumptions. That's a reasonable thing to worry about given the freedom we have in this logic. But note when employing Conditional Proof, you only ever assume the antecedent. That sharply narrows down the scope of things you might assume. Moreover, assuming the antecedent is - we logicians have learned over time - one of the most efficient ways to prove conditional statements. Put another way, you can strictly speaking assume anything you want, but not everything will be useful to you when you're trying to prove something. If you're proving a conditional, just restrict your attention to the assuming the antecedent.
Get into that habit. Whenever you're asked to prove an expression with a conditional as the main connective, assume the antecedent. This should be the first thing that comes to mind.
After you've assumed, then you'll prove the consequent follows. You may need to use Direct Proof steps to get you there. For example (recall, I include "SHOW" lines to remind you - in the proof - of your goal; you can remove them if you prefer):
1. SHOW P -> (Q -> P)
Here I've to prove a conditional expression. There are two connectives. Both are conditionals. The first is the main connective. So I employ the Conditional Proof Strategy (recall, I include "SUPPOSE" in proofs instead of drawing vertical bars, to illustrate sub-proofs):
2. SUPPOSE P
3. SHOW (Q -> P)
Now, we've broken our proof down to the consequent, which we must prove. We can apply the same reasoning as above, and note the main connective here is also a conditional. That means we should apply the Conditional Proof Strategy again:
4. SUPPOSE Q
5. SHOW P
At this point, we've only to show P follows from lines 2 and 4 to finish. This is perhaps a good point to observe that when you assume something you get to use it as a premise in your argument. Put another way: assuming something gets you more to work with.
It's at this point we apply the Direct Proof Strategy. This one is rather simple. We use the "R" - Repetition - derived rule to bring "P" down under the scope of our assumed "Q".
6. P
From here we can discharge our assumption of Q with "->I", resulting in:
7. Q -> P ->I, 4-6
Which was what we were trying to prove on the assumption that "P", so we can discharge with "->I" again, resulting in:
8. P -> (Q -> P) ->I, 2-7
And that's the end of the proof. We used Conditional Proof twice, and Direct Proof once. It should be clear then how these proof strategies play together.
That said, sometimes you must prove something you can't prove directly and which is not in the form of a conditional. For that, we use the last proof strategy:
Indirect Proof: Anything that can be proven in our logic can be proven using Indirect Proof. You can always convert a proof using the Direct Proof or Conditional Proof Strategy into one using the Indirect Proof Strategy. The respective converses are not true. Some expressions can only be proved with the Indirect Strategy.
This strategy is codified in our rule "-I". Namely, if you assume something and get a contradiction on that assumption, then you take that assumption back. Since every sentence in our language is either true or false, and no sentence is both, you know, say, if you get a contradiction from assuming "A", then it has to be the case that "~A".
Pro-Tip - If you can't figure out how to apply a rule to prove something without making an assumption and you aren't being asked to prove something with a conditional as its main connective, then use the Indirect Proof Strategy. Put another way, if the other two strategies aren't obviously helpful, then just assume the opposite of what you need to prove. In fact, I wouldn't spend much time trying to figure out if one of the other proof strategies will be helpful. If it's not obvious, just assume the opposite of your goal and try to derive a contradiction.
Note again, we can assume anything we want in our logic. But, it will be most efficient to simply assume the opposite of what you want to prove. This sharply constrains what you might practically want to assume. Coupled with the Conditional Proof Strategy, and noting that these are the only three strategies you will be using in this course, it should be clear that though you can assume whatever you like in a proof, you should only be assuming things that take one of two forms: (i) The antecedent of a conditional; (ii) The negation of what you want to prove.
I said some things can only be proven with Indirect Proof. I'll give you an example:
1. SHOW (P v ~P)
Observe: this is not in the form of a conditional proof, and it's not obvious how to apply rules without making an assumption to prove it (of course, you can derive rules, e.g. De Morgan's, to help, but you often use Indirect Proof to establish those derived rules are true, so…). With that in mind, we'll apply the Indirect Proof Strategy:
2. SUPPOSE ~(P v ~P)
Here, we still don't have an obvious way to use Direct Proof or Conditional Proof. We'll have to be creative. Observe, we have proven the following in previous lectures:
De Morgan's: ~(P v Q) -> (~P /\ ~Q)
Let's rehearse:
1. SHOW ~(P v Q) -> (~P /\ ~Q)
2. SUPPOSE ~(P v Q)
3. SHOW (~P /\ ~Q)
We pause here to note we are again at a loss for how to apply Direct or Conditional Proof to show line 3. So, we go Indirect:
4. SUPPOSE P
5. P v Q vI, 4
6. ! Contradiction, 2, 5
7. ~P
Note, we have to prove a conjunction, so we need to show each side independently. We continue:
8. SUPPOSE Q
9. P v Q vI, 8
10. ! Contradiction, 2, 9
11. ~Q
12. ~P /\ ~Q /\I, 7, 11
Okay, back to the other proof, we had:
1. SHOW (P v ~P)
2. SUPPOSE ~(P v ~P)
3. ~P /\ ~~P De Morgan's, 2
4. ~P /\E, 3
5. ~~P /\E, 3
6. ! Contradiction, 4, 5
7. (P v ~P)
And that's it. We have proven this, note, from no premises. That means it's a logical truth, i.e. it's always true in our logic. In many cases, proving logical truths that don't have conditional main connectives requires Indirect Proof.
To sum up:
(1) There are only three proof strategies you need to remember: Direct, Conditional, Indirect
(2) Direct Proofs do not need you to provide assumptions
(3) Conditional Proofs are used when you need to prove an expression where the main connective is a conditional; you always assume the antecedent, then derive the consequent
(4) Everything else is Indirect Proof, where you assume the negation of what you want to prove
(5) There is no need to assume anything other than what I've noted in (3) and (4), and anything you can prove in this logic you can prove using (2)-(4)