Logic and Proofs Summary

Discrete Math · Axiom Academy

Let's review how propositional logic and proof techniques form the foundation for precise mathematical reasoning. Proposition: A declarative statement that is either true or false, but not both. Examples: "2 + 2 = 4" (true), "All birds can fly" (false) Logical Connectives: Operators that combine propositions: ¬ (NOT), ∧ (AND), ∨ (OR), → (IMPLIES), ↔ (IFF) Truth Tables: Systematic method to evaluate compound propositions by listing all possible truth value combinations Logical Equivalence: Two propositions are equivalent ( ≡ ) if they have identical truth tables under all conditions De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q Implication: p → q ≡ ¬p ∨ q . An implication is only false when the hypothesis is true and conclusion is false Contrapositive: p → q ≡ ¬q → ¬p . Always logically equivalent to the original implication Converse: q → p is NOT equivalent to p → q . Common source of logical errors Modus Ponens: From p → q and p , conclude q . The most fundamental inference rule Modus Tollens: From p → q and ¬q , conclude ¬p . Reasoning by contrapositive Hypothetical Syllogism: From p → q and q → r , conclude p → r . Chaining implications Disjunctive Syllogism: From p ∨ q and ¬p , conclude q . Elimination by cases Direct Proof: Assume premises are true, apply definitions and previously proven results, derive the conclusion step-by-step Proof by Contrapositive: To prove p → q , instead prove ¬q → ¬p . Often simpler than direct proof

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