Introduction to Proofs

A proof is a finite series of  formulas, beginning with the premises of an argument and ending with its conclusion, in which each line is either a premise or derived from the premises according to established rules of inference and equivalence.  Constructing a proof for an argument definitively establishes that the argument is valid.  Failure to construct a proof, however, establishes nothing.  One's inability to construct a proof may be caused by the non-validity of the argument in question, but it may be caused by a lack of skill and insight.

Proofs can establish but not test validity, and they do that only if you (the logician) are clever enough. Unlike truth tables, proofs are not decision procedures (dumb, mechanical and infallible); on the contrary, they require ingenuity and insight. This has the disadvantage that we must now be smart, not just patient and legible, in order to succeed. For all these reasons, they are inferior to truth tables.

But proofs are superior to truth tables on several other fronts. Because they require ingenuity and insight, they are more like chess than tic-tac-toe; they are much less boring than truth-tables. What is more, they can generate valid conclusions from a given set of premises, to see where they lead, or to "unfold" them. Hence they can model exploratory reasoning. Moreover, they can handle any number of propositional variables without clumsiness, unlike truth tables (remember, 8 sentential variables creates a 256 row truth table). Finally, they are adequate for predicate logic (our next unit) with only a few additions, while truth tables are useless in predicate logic.

In proofs we use two kinds of rule: rules of inference and rules of equivalence (replacement).  The former apply only to entire lines of proof, or whole propositions, while the latter apply to components within compounds as well as to the whole compounds themselves.  

Rules of inference generate a new line whose truth value follows from, but is not identical to, the truth of the source lines.  Rules of inference can be applied ONLY to whole lines that are substitution instances of the argument form of the rule.

Rules of equivalence, on the other hand, generate a new line whose truth value is identical to that of the source line.  A rule of equivalence can be applied either to an entire line or to a part of a line, so long as that part is a substitution instance of the statement form on one side of rule.

Our system uses only the following 19 rules plus 2 additional techniques that will be intorduced later.

Rules of Inference and Equivalence

Rules of Inference

Modus Ponens (MP)

p q

p

Therefore: q

Modus Tollens (MT)

p q

~ q

Therefore: ~p

Hypothetical Syllogism (HS)

p q

q r

Therefore: p r

Simplification (SIMP)

p q

Therefore: p

Addition (ADD)

p

Therefore: p q

Conjunction (CONJ)

p

q

Therefore: p q

Constructive Dilemma (CD)

(p q)

 (r s)

(p r)

Therefore: (q s)

Disjunctive Syllogism (DS)

p q

~ p

Therefore: q

Rules of Equivalence

Absorption (ABS)

p q

Therefore: p (p q)

DeMorgan (DEM)

~ ( p q) = (~p ~q)

~ (p q) = (~p ~q)

Commutation (COM)

(p q) :: (q p)

(p q) :: (q p)

Association (ASSN)

[p (q r)] :: [(p q) r]

[p (q r)] :: [(p q) r]

Distribution (Dist)

[p (q r)] :: [(p q) (p r)]

[p (q r)] :: [(p q) (p r)]

Double Negation (DN)

p :: ~ ~p

Contraposition (Cont)

(p q) :: (~ q ~p)

Material Implication (MI)

(p q) :: (~ p q)

Exportation (EX)

[(p q) r] :: [p (q r)]

Material Equivalence (ME)

(p q) :: [(p q) (q p)]

(p q) :: [(p q) ( ~ p ~ q)]

Redundancy (Re)

p :: (p p)

p :: (p p)

Note that there are no inference rules for dealing with biconditionals.  What this means is that you must use the equivalence rules to either introduce or eliminate biconditionals as needed.

We could, if we wished, introduce more rules.  In fact, we could introduce a special rule for every valid argument, but such a system would be nearly impossible to use.  Instead, we use only 19 rules, with two additional techniques, that are sufficient to prove every valid argument valid. And we can call each by name.   Our  19 rules of inference and equivalence are like the multiplication table. If you memorize a few basic multiplications, then you can use them as tools to compute any complex multiplication. However, if you were superhuman, you could memorize every one of the infinity of correct multiplications so that you would never have to compute any. Similarly, by using a finite set of rules of inference, you prove every complex argument to be valid. However, if you were superhuman, you could memorize every one of the infinity of tautologous conditionals and biconditionals and never have to perform any proofs (of more than one step).

A proof is successful if each step is justified by one of our rules of inference, and the last step is the proposition to be proven. Everything else (except spelling and neatness) is irrelevant, including the length and niftiness of the proof, and repeated or unnecessary steps. Elegance is desirable, but only validity is essential.

Return to Tutorials Index     Go on to Justifying Steps in a Proof