Proof via the Contrapositive

Return to List of Lectures

Previous Lecture

• Questions?
• Proof Via the Contrapositive
  • Section 3.2 through “Other Logical Equivalencies”
  • Examples / Problems
    • What is the contrapositive?
      • For P → Q, contrapositive is ¬Q → ¬P
      • P → Q ≡ ¬Q → ¬P
    • Contrapositive of…
      • “If 1+1 = 2 then 1+1+1 = 3”
        • If 1 + 1+1 ≠ 3 then 1+1 ≠ 2
      • “If n⁴ = 1 and n is a real number, then n = -1 or n = 1”
        • If n ≠ -1 and n ≠ 1 then n⁴ ≠ 1 or n is not real
    • Proofs
      • How does this help proofs?
        • Since P → Q ≡ ¬Q → ¬P, prove P → Q by proving ¬Q → ¬P
        • Say you’re doing it
      • For all integers a and b, if ab is even but a is odd, then b is even
        • Contrapositive: for all integers a and b, if b is odd, then ab is odd or a is even
        • X → Y ∨ Z ≡ X ∧ ¬Y → Z
        • So, for all integers a and b, if b is odd and a is odd, then ab is odd
        • True by Sundstrom Theorem 1.8
      • For all predicates P(x) and sets A, if P(x) is true for all members of A and P(x) is false for all members of A, then A is empty
        • Contrapositive: for all predicates P(x) and sets A, if A is not empty then P(x) is false for some member of A or P(x) is true for some member of A
        • True because A has at least one member, and P(x) must be either true or false for that member
  • Problem set
• Next
  • Proving biconditionals
  • Read rest of section 3.2
    • “Proofs of Biconditional Statements,” bottom half of page 107
    • Through bottom of page 111

Next Lecture