index.md (3888B)
1 +++ 2 template = 'page-math.html' 3 title = 'Propositional logic' 4 +++ 5 # Propositional logic 6 ## Notation review 7 * `A, B, C` -- propositions 8 * `A ∧ B` -- conjunction ("and") 9 * `A ∨ B` -- disjunction ("or") 10 * `A → B` -- implication ("if A then B") 11 * `A ↔ B` -- bi-implication ("A iff B") 12 * `¬ A` -- negation ("not A") 13 * `⊥` -- false, falsum, nonsense, bullshit, the middle finger 14 15 ## Rules of inference 16 "C is a logical consequence of A and B": 17 18  19 20 21 <table> 22 <tr><th>Implication</th><th>Conjunction</th><th>Negation</th><th>Disjunction</th><th>Bi-implication ("if and only if")</th></tr> 23 <tr><td><img alt="Hypothesis" src="hypothesis.png"></td><td><img alt="Conjunction introduction" src="conjunction-introduction.png"></td> <td><img alt="Negation hypothetical reasoning" src="negation-hypothetical-reasoning.png"></td><td><img alt="Disjunction introduction" src="disjunction-introduction.png"></td><td><img alt="Bi-implication introduction" src="bi-implication-introduction.png"></td></tr> 24 <tr><td><img alt="Implication elimination" src="implication-elimination.png"></td><td><img alt="And elimination" src="and-elimination.png"></td><td><img alt="Negation elimination" src="negation-elimination.png"></td><td><img alt="Disjunction elimination" src="disjunction-elimination.png"></td><td><img alt="Bi-implication elimination" src="bi-implication-elimination.png"></td></tr> 25 </table> 26 27 Truth and falsity: from false, you can conclude anything, and from nothing, you can conclude true. 28 29 ,  30 31 You can also derive this conjunction rule: 32 33  34 35 ## Forward and backward reasoning 36 Backward reasoning: looking at the goal and seeing what rules need to be applied ("bottom-up") 37 38 Forward reasoning: starting at some hypotheses/assumptions 39 40 The general heuristic is to always work backwards, as much as possible. Only once you get stuck should you work from your assumptions or hypotheses. 41 42 If all else fails, try proof by contradiction. 43 44 ## Proof by contradiction 45 Suppose a negation of a formula is true, prove that it's impossible, thereby proving the original formula. 46 47  48 49 RAA stands for _"reductio ad absurdum"_ 50 51 ## Vocab definitions 52 * derivable: a formula φ is "derivable" if we can prove φ with no global hypotheses (bottom line is φ, everything is closed). Then we write ⊢ φ. 53 * φ is derivable from hypotheses ψ₁..ψn if we can compute φ assuming ψ₁..ψn 54 * formulas φ and ψ are logically equivalent if ⊢ φ ↔ ψ 55 56 ## Classical reasoning 57 Principles: 58 * Proof by contradiction: assume the contradiction, and show false, thereby proving the original. 59 * Double negation elimination: ¬ ¬ A ↔ A. 60 * Contrapositive: if A → B, then ¬ B → ¬ A 61 62 A general heuristic: 63 1. Work backward from the conclusion, using introduction rules. 64 2. When you run out of stuff to do, work forward with elimination rules. 65 3. If you get stuck, 66 67  68 69 (meme credit goes to Geo) 70 71 ## Syntax vs Semantics 72 Syntax: 73 - derivation, proofs 74 - Γ ⊢ A ("A is derivable from hypotheses in Γ") 75 76 Semantics: 77 - truth and falsity 78 - truth assignment says which propositional letters are true 79 - valuation says which formulas are true 80 81 ## Soundness and completeness 82 provable: if there is a formal proof of a formula (syntactic) 83 84 tautology/valid: if true under any truth assignment (semantic) 85 86 soundness: if a formula is provable, it is valid (if ⊢ A, then ⊨ A) 87 88 completeness: if a formula is valid, it is provable (if ⊨ A, then ⊢ A) 89 90 Proving soundness is easier than proving completeness. 91 92 A is a logical consequence of Γ if, given any truth assignment that makes every formula in Γ true, A is true. 93