Symbolic Logic

Here are some important things to keep in mind when doing proofs. These observations are all based on unproductive things I've noticed people have a tendency to do (and useful things they have a tendency not to do).

**Conditional Introduction**

If you need to prove a conditional, identify the antecedent and consequent of
the conditional that you want to prove. Set up a subproof with the antecedent as its assumption, and
the consequent as its last line. Then get the conditional as the first step
after the subproof, by Conditional Introduction. **Make sure **the assumption
of the subproof is the antecedent **of the conditional you are trying to prove**,
**not** the antecedent of some conditional you have as a premise or an
earlier line!

**Disjunction Elimination**

On the other hand, if you are using disjunction elimination, you need to look at
a disjunction that you already have as a premise or an earlier line of the proof. Set
up a subproof for each disjunct of the disjunction. The last line of every one
of the subproofs should be the conclusion you are trying to reach. Then the
first line after the subproofs will be the conclusion you reached as the last
line of each subproof, by Disjunction Elimination.

**Negation Introduction**

Assume the opposite of what you want to prove. Derive a contradiction as the
last line of the subproof. Get what you want by Negation Introduction as the
first line after the subproof.

**Proving a Contradiction (normally in a Negation Introduction subproof)
**Find a negation that you already have (if possible, somewhere other than the
first line of the subproof you are currently in). Then try to prove the exact
opposite. (That is, if you already have a negation ~P, then try to prove P. Once
you've proved P, use the two lines P and ~P as the support steps for
Contradiction Introduction.)

**Subproofs in General**

Never start a subproof unless you know what rule you are using it for, what the
assumption should be, what the last line of the subproof should be, and what the
first line after the subproof will be.

**Quantifier Proofs**

As a general rule of thumb, if you have a proof in which all the premises are
quantifier sentences (universals or existentials), and the conclusion is also a
quantifier sentence, you will want to apply the various sorts of rules in
the following order. (The general idea is (a) to do quantifier eliminations to
get propositional formulas, then use the propositional rules, then use
quantifier introduction rules to get back to quantifier statements, but this is
complicated by (b) the need to use the rules that have more restrictions earlier
than rules that have fewer restrictions so that you can use the same constants
as often as possible.)

- Set up ∀Intro and ∃Elim subproofs (if needed). (Notice that to determine whether you need a ∀Intro subproof you need to think backward from the conclusion.)
- Do ∀Elim.
- Use propositional rules as needed.
- Do ∃Intro if needed.
- Finish off the ∀Intro and ∃Elim subproofs.

**General Advice on Proofs**

- Don't try to prove things you've already got! (So, for instance, don't assume the antecedent of a conditional you already have for conditional introduction; don't assume the opposite of something you already have for negation introduction.)
- Think both about what you can get from the premises, and what intermediate steps might allow you to reach the conclusion. (That is, think forward from the premises and backward from the conclusion, and try to get the two chains of thought to meet in the middle!)
- When you can't think of anything else to do, try negation introduction! But remember how to use it, as described above.

**General Strategy for Constructing a Proof**

1 - look at the premises and see whether any elimination rules apply (i.e. if you have a conjunction, you'll probably want to use conjunction Elim; if you have a disjunction, you'll probably want to use disjunction Elim; etc. One exception is that negation Elim is not useful on garden-variety negations, but only on double negations).

2 - look at your current goal and see whether any intro rules would get you
there (if the goal is a conjunction, it's usually easiest to derive the
conjuncts separately and then use conjunction Intro to get the final conclusion;
if the conclusion is a negation, it may be a good idea to try to get it by
negation Intro. One exception: disjunction Intro is usually **not** the best
way to derive a disjunction, because usually you won't be able to prove either
of the disjuncts separately.)

3 - if it looks like nothing else will work, try negation intro.

If you've derived a new line, or you've made an assumption to get a subproof going, repeat #1 for that line.

If you see a good way to get the conclusion if you could get an intermediate step, repeat #2 for the intermediate step.

Keep on going until, working forward from the premises and backward from the conclusion, the two chains of reasoning meet in the middle (hopefully!).

Curtis Brown | Symbolic Logic | Philosophy Department | Trinity University

cbrown@trinity.edu