Logic and Proofs Reference

Discrete Math · Axiom Academy

FORMULA SHEET Logic and Proofs Reference Complete reference for propositional logic, inference rules, and proof techniques TRUTH TABLES FOR LOGICAL CONNECTIVES FUNDAMENTAL LOGICAL EQUIVALENCES Use definitions, axioms, and previously proven theorems Apply logical steps to reach q Example: Prove that if n is even, then n² is even. Prove the equivalent statement Apply logical steps to reach ¬p Conclude original implication is true Example: Prove that if n² is odd, then n is odd. Goal: Prove statement p is true Example: Prove √2 is irrational. Goal: Prove where cases cover all possibilities Example: Prove n² + n is even for all integers n. Base Case: Prove P(n₀) is true (typically n₀ = 0 or n₀ = 1) Inductive Hypothesis: Assume P(k) is true for arbitrary k ≥ n₀ Inductive Step: Prove P(k+1) is true using the assumption that P(k) is true Conclusion: By mathematical induction, P(n) is true for all n ≥ n₀ Goal: Prove P(n) for all n ≥ n₀ Base Case(s): Prove P(n₀), P(n₀+1), ... as needed Inductive Hypothesis: Assume P(i) is true for all i where n₀ ≤ i ≤ k Inductive Step: Prove P(k+1) is true using any or all of P(n₀), P(n₀+1), ..., P(k) Conclusion: By strong induction, P(n) is true for all n ≥ n₀ Use when: P(k+1) depends on multiple previous cases, not just P(k) PROOF STRATEGY SELECTION GUIDE Definition: means for some integer k Strategy: Express a as a multiple of b using algebraic manipulation Useful facts: even ± even = even, odd ± odd = even, even × any = even

This is the written version of the interactive lesson above. See the full Discrete Math course.