A proof is a finite series of formulas, beginning with the premises of an argument and ending with the conclusion, in which each line following the premises is justified according to accepted rules of inference and equivalence.  A proof is a formal demonstration that the conclusion of the argument follows from the premises.  Any argument for which a proof can be constructed is valid, and for any valid argument a proof can be constructed.

Each line in a proof must be justified in some way, that is, some reason must be given for believing it to be true.  Remember, validity preserves truth.  Each line in an argument is either a premise or a derived line.  Premises justify themselves--they are assumed to be true.  A derived line can be justified by showing that it follows either from the premises in accordance with established rules of inference or equivalence, or that it follows from some combination of premises and other previously derived lines according to the rules.  Justifying a derived line amounts to little more than showing that the derived line is a substitution instance of the conclusion of an argument form (or an instance of one side of an equivalence rule) and that the line(s) from which the new line is derived are substitution instances of the premises in the argument form (or an instance the other side of the equivalence rule).

Let's see how this works.  Consider the argument:

[~(P Q) (~R  ~S)],   ~(P Q)           (~R  ~S)

First we need to set forth our premises, numbering each line so that we can easily refer back to it, and then justifying the premises by identifying them as premises.

Line # Argument (instance) Argument Form Justification
1 [~(P Q) (~R  ~S)]   premise
2 ~(P Q)   premise

Now, Identify an argument form or inference rule that maps onto your premises. In an actual proof we don' have a column for the argument form, but I have included it here to help you see just what is going on in the justification.

Line # Argument (instance) Argument Form Justification
1 [~(P Q) (~R  ~S)] (p q) premise
2 ~(P Q) p premise

Finally, create a new line, a substitution instance of the conclusion of the argument form using the proper WFF's to replace the sentential variables in the form.

Line # Argument (instance) Argument Form Justification
1 [~(P Q) (~R  ~S)] (p q) premise
2 ~(P Q) p premise
3 (~R  ~S) q 1,2 Modus Ponens

And that's all there is to it.

Here is a slightly more complicated example, in which I leave out the argument forms:

A, B, (A B) C    C

1 A   premise
2 B   premise
3 (A B) C   premise
4 (A B)   1,2 conjunction
5 C   3,4 modus ponens

Finally, a more complicated example, consider the argument:

(A▼B)C          AC

 Line Inf/Equiv Rule applied Justification
1 (AB)C  premise
2 ~(AB)C (p q) :: (~p ▼q)1, implication
3 (~A ~B)C ~(p q) ::  (~p ▼ ~q) 2, DeMorgan
4 C(~A ~B) (p ▼ q) :: (q ▼ p) 3, commutation
5 (C~A) (C~B) p▼(q  ● r) :: (p ▼q) ● (p▼ r) 4, distribution
6 C~A (p q)   p 5, simplification
7 ~AC (p ▼ q) :: (q ▼ p) 6, commutation
8 AC (p q) :: (~p ▼q)7, implication

Note that this rather complicated argument uses only 1 inference rule, and that a very simple one (simplification).  All of the heavy lifting in this argument is done by the equivalence rules.

Return to Tutorials Index                Go on to Constructing Proofs