Unit 4: Formal Proof of Validity

Table of Contents

What is a Formal Proof (Natural Deduction)?

For complex arguments (with 4+ variables), truth tables become too large (16+ rows). A Formal Proof is a step-by-step method of deducing a conclusion from a set of premises using a small set of "Elementary Rules of Inference."

This method is called Natural Deduction because it mimics the way we naturally reason.

Structure of a Proof:

  1. List the premises, numbering each line.
  2. Draw a line and write the conclusion, prefixed with "/ ∴".
  3. Create new lines, each one justified by citing a previous line(s) and the abbreviation for the rule used.
  4. The proof is complete when you have derived the conclusion.

The Elementary Rules of Inference

These are 9 basic, valid argument forms that we accept as given. They are the tools we use to build our proofs.

Rule Name Abbreviation Argument Form
Modus Ponens M.P. p ⊃ q
p
/ ∴ q
Modus Tollens M.T. p ⊃ q
~q
/ ∴ ~p
Hypothetical Syllogism H.S. p ⊃ q
q ⊃ r
/ ∴ p ⊃ r
Disjunctive Syllogism D.S. p v q
~p
/ ∴ q
Constructive Dilemma C.D. (p ⊃ q) • (r ⊃ s)
p v r
/ ∴ q v s
Destructive Dilemma D.D. (p ⊃ q) • (r ⊃ s)
~q v ~s
/ ∴ ~p v ~r
Simplification Simp. p • q
/ ∴ p
Conjunction Conj. p
q
/ ∴ p • q
Addition Add. p
/ ∴ p v q
Crucial Rules for Exams:
  • M.P. (Modus Ponens): The "workhorse" of proofs. If you have "If P then Q" and you have "P", you can write "Q".
  • M.T. (Modus Tollens): If you have "If P then Q" and you have "Not Q", you can write "Not P".
  • H.S. (Hypothetical Syllogism): Lets you chain implications together.
  • D.S. (Disjunctive Syllogism): If you have "P or Q" and you know "Not P", you must have "Q".

Example of a Formal Proof

Let's construct a formal proof for the following valid argument:

1. A ⊃ B
2. A v (C • D)
3. ~B
/ ∴ C

Proof:

4. ~A                              (from 1, 3, M.T.)
5. C • D                        (from 2, 4, D.S.)
6. C                               (from 5, Simp.)

Explanation:

  1. We start with the three premises.
  2. Line 4: We look at lines 1 (A ⊃ B) and 3 (~B). This perfectly matches the form for Modus Tollens (M.T.). So, we can deduce ~A.
  3. Line 5: We look at lines 2 (A v (C • D)) and 4 (~A). This matches the form for Disjunctive Syllogism (D.S.). We have "P or Q" and we have "Not P", so we can deduce "Q", which in this case is (C • D).
  4. Line 6: We look at line 5 (C • D). The rule of Simplification (Simp.) says if we have "P and Q", we can deduce "P". So, we deduce C.
  5. Since C was our conclusion, the proof is complete.