Proof by Cases

Return to List of Lectures

Previous Lecture

• Questions?
  • Problem set 6 question 2 (6|n iff 3|n and 2|n)
    • For 3|n and 2|n implies 6|n direction
      • Contrapositive? i.e., 6 does not divide n implies 3 does not divide n or 2 does not divide n
        • Not sure how much this would really help
      • Hint: proved in class that if xy is even and x is odd then y is even
    • Other direction: factor 6 as 3 × 2
• Proof by Cases
  • Section 3.4
  • Warm-Up: show that ( P ∨ Q ) → R ≡ ( P → R ) ∧ ( Q → R )
    • ( P ∨ Q ) → R ≡ ¬( P ∨ Q ) ∨ R
    • ≡ (¬P ∧ ¬Q ) ∨ R
    • ≡ (¬P ∨ R) ∧ (¬Q ∨ R)
    • ≡ (P → R) ∧ (Q → R)
    • Laws used
      • (A ∧ B) ∨ C ≡ (A ∨ C) ∧ (B ∨ C)
      • A → B ≡ ¬A ∨ B
      • (A ∨ B) ∧ C ≡ (A ∧ C) ∨ (B ∧ C)
    • P and Q are cases!
  • Define ⌊x⌋ (the floor of x) to be the greatest integer less than or equal to x
    • e.g., ⌊3.14⌋ = 3, ⌊7⌋ = 7, ⌊-3.14⌋ = -4
    • Prove that for all real x ⌊x⌋ ≤ x < ⌊x⌋ + 1
      • Case 1: x is an integer
        • ⌊x⌋ = x ≤ x
        • ⌊x⌋ + 1 = x + 1 > x
      • Case 2: x is not an integer
        • x = n + f where n is integer and 0 < f < 1
        • ⌊x⌋ = n
        • ⌊x⌋ + 1 = n + 1 > n + f = x
    • Could also do from definition
  • Problem set
• Next
  • The division algorithm
  • Section 3.5

Next Lecture