Summary
Proving implications
- direct proof using modus ponens
- proof by contradiction, very little information
- proof by contrapositive using modus tollens
Counter-example (disprove)
Proving biconditonals
- prove the implication in both directions
- proving logical equivalences
Proof by cases
Concept
Builds upon the rules of inference
Universal instantiation
- if true for all, then true for one instance
Existential generalization
- if true for one, then there exists one or more
Quantified statements in conditional form
Application
Pigeonhole principle
- if there are more cards then boxes, then there is a(at least one) box with more than one card
- general
- no ordering