โ Discrete Mathematics learning pathDiscrete Mathematics ยท Module 2 of 10
Predicates and proofs
Quantifiers and proof methods.
๐ Key ideas
- A predicate P(x) becomes a proposition when x is given a value.
- Universal quantifier: for all x; existential quantifier: there exists x.
- Negation swaps them: NOT (for all x, P(x)) = there exists x with NOT P(x).
- Proof methods: direct proof, contrapositive, contradiction and counterexample.
- Mathematical induction proves statements for all natural numbers: base case and inductive step.
๐ก Real-life example: Induction is like dominoes: if the first falls, and each one knocks over the next, then all of them fall.
PredicateStatement with variables
Universal quantifierFor all
Existential quantifierThere exists
Mathematical inductionProof by base case and inductive step