Quantifiers, Part 2

Return to List of Lectures

Previous Lecture

• Misc
  • Exam 1 is next Friday (Sept. 30)
    • Material from beginning of semester through quantifiers (e.g., statements and non-statements, conditional and biconditional statements, propositional logic, quantifiers, etc.)
    • 3 - 5 short-answer questions, probably a longer question where I ask you to write a formal proof
    • Whole class period
    • Open book, notes, computer; closed person
  • Problem set 3 solution (with LaTeX) is online
  • PRISM LaTeX Workshop
    • Sept. 27 (tomorrow!)
    • 5:00 PM, Bailey 107 (or maybe 101)
    • Bring laptop
• Questions?
• Quantifiers
  • Which of the following are true?
    • If x is a pink dragon in this room, then x is dancing on the tables
      • True (hypothesis is false)
    • All the pink dragons in this room are dancing on the tables
      • True (vacuous truth—any statement about all elements of the empty set is true)
    • Some pink dragon in this room is dancing on the tables
      • False (there are no pink dragons in the room)
  • Airport logic (which is these can be true in logic as we know it)
    • “All gates are up stairway A; you can only get to gate 43 by going up stairway B”
      • Can’t be true
    • “All missing passengers are on the plane 20 minutes before departure”
      • Airlines want this to be (vacuously) true
  • Proving quantified statements
    • For every real number x, (x+1)² = x² + 2x + 1
      • To prove ( ∀ x ∈ U) …
      • Let x be any member of U, reason using only membership in U, not using things that aren’t true of every member
      • “for all x in U …” is closely related to “if x is in U, then….”
    • There is some natural number n such that n > 100
      • Show an example
      • Or more commonly how to calculate an example (constructive proofs)
      • But sometimes you find non-constructive proofs that show something must exist but not how to find it
• Next
  • Direct proofs
  • Read section 3.1

Next Lecture