In a proof, the wff we're proving is the last line of the derivation. The premises are the wffs we are proving the last line from.  So this is a proof of (~A v E) from {(~A v B), (B ⊃ (C & D)), ~(C & D)}.

Many of the skills you've developed in logic so far are skills in which you've implemented mechanical processes. Constructing truth-tables, for example, is a purely step-by-step, mechanical process. If you follow the rules of truth and complete the truth table, you are guaranteed to achieve a result in a finite amount of time. That's comforting, but it's not as much fun as achieving a result which requires something more than the finite application of the rules.  That extra something is a strategy. In attempting to prove a wff from a set of propositions,  you will need to think about what rules of inferences might lead to the desired conclusion. 

The best way to learn to do proofs is to do them. We'll walk through a few proofs here, and more as we introduce additional rules and strategies.  You're strongly urged to do all the exercises.  The more practice you have with proofs, the easier they will be to do.

We'll construct a proof of the following:

First we list the premises to start the derivation:

The conclusion we're trying to reach is (L v ~M).  A critical question to ask at the beginning of the proof is this: What is the form of the conclusion, and what rules might be applied to reach that conclusion?  In this proof, our conclusion is a disjunction.  We can obtain a disjunction by using our disjoining rule.  To apply that rule, we'll need one of the disjuncts.  The next question to ask is where we might find one of the disjuncts in the premises.  A quick survey reveals that L is in premise 2 and ~M isn't in any premise. So we'll investigate L further.  Notice that the strategy we're using is thinking backwards. We' re beginning with the conclusion and asking how we can get to that conclusion. 

L occurs in the second premise, as the consequent of the conditional (R ⊃ L), which is itself the right conjunct of the conjunction (~~C & (R ⊃ L)).  We can get (R ⊃ L) from line 2 by simplification, and then if we can get R by itself, we can infer L by modus ponens. So how do we get R?  Take a look:

Now we can complete the proof, using the backwards-reasoning we employed above:

This is our proof, because it ends with the conclusion we wanted, and used only the premises we were given and the rules of inference. Each line is either a premise or the application of a rule of inference.

All proofs proceed in this fashion.  It is strongly urged that before you begin to apply rules of inference, you attempt to formulate a strategy for constructing the proof.  Ask the following questions:

1. What is the form of the conclusion, and what rules can be used to infer a wff which has that form?

2. Where can components of the conclusion be found in the premises?

As you work backward, you will find that proof strategies often can be broken up into subtasks. For example, we knew we needed to get R, and that getting R would help us get L. So the proof through line 6 is a subtask of the proof, and another are the lines 6 through 9.  As you tackle longer and more complicated proofs, breaking the proof up into subtasks will help enormously.

So far we've just one proof. The next section provides several examples and works through proof strategy.