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:
- List the premises, numbering each line.
- Draw a line and write the conclusion, prefixed with "/ ∴".
- Create new lines, each one justified by citing a previous line(s) and the abbreviation for the rule used.
- 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:
- We start with the three premises.
- 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.
- 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).
- 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.
- Since C was our conclusion, the proof is complete.