Formal Proof Examples

Mathematical Logic · Axiom Academy

Master proof techniques through complete worked examples in propositional logic We'll walk through four fundamental proof techniques step-by-step: Example 1: Direct proof using axioms and inference rules Example 2: Proof by contradiction (reductio ad absurdum) Example 3: Proof by cases with disjunction elimination Example 4: Natural deduction with nested subproofs Example 2: Proof by Contradiction Example 4: Natural Deduction with Subproofs Excellent work! You've mastered four fundamental proof techniques in mathematical logic: Direct Proof (Example 1): Build up the conclusion from assumptions using inference rules. The proof of p → (q → p) shows how nested implications work through sequential discharge of assumptions. Proof by Contradiction (Example 2): Assume the negation of what you want to prove and derive a contradiction. We proved ¬(p ∧ ¬p) by showing that assuming its negation leads to both p and ¬p being true simultaneously. Proof by Cases (Example 3): When you have a disjunction A ∨ B, prove your goal from each disjunct separately. If the goal follows from both A and B, it follows from A ∨ B. Natural Deduction (Example 4): Chain together inference rules systematically. We used two applications of Modus Ponens to prove r from p → q, q → r, and p. Inference Rules: Key rules include Modus Ponens (→E), Implication Introduction (→I), Conjunction Introduction (∧I), Disjunction Elimination (∨E), and Negation Introduction (¬I).

This is the written version of the interactive lesson above. See the full Mathematical Logic course.