BCS1130-2 Logic and Proofs

Quantifiers

Lecture slides

Lecture notes

Introduction to quantifiers

• Universal quantifier
• Existential quantifier
• $\forall$ has the same logical meaning as $\to$
  • For each student at DACS, the student is smart
  • If a student is a DACS student, the student is smart

Proof techniques

• Direct proof
• Counterexample
• Contrapositive
• Contradiction
• Induction

Direct proof

• Move forward in logical steps from the assumptions to the conclusion
• To prove that a statement is false, you prove that the negation is true
• To prove a “for all” statement, you prove the statement for an arbitrary element
• To prove a “there exists” statement, you only need to give an example

Example

$\forall n\in N:n^2\ge n$

• Let $n\in N$
  • $⟹n\ge 1$
  • $⟹n\cdot n\ge n\cdot 1$ (since n > 0)
  • $⟹n^2\ge n$

Counterexample

• To disprove a “for all” statement