Discrete mathematics is the mathematics of countable things: integers, sets, logical statements, graphs and finite structures. Computers work on exactly these, so it is the working language of algorithms, cryptography, databases and proofs. It also teaches the habit of stating a claim precisely and proving it.
Key concepts
- Logic and proof: implications, quantifiers, direct proof, contradiction and induction.
- Sets, relations and functions: the vocabulary for describing any structure, including equivalence relations and orderings.
- Number theory: divisibility, primes, gcd and modular arithmetic, the base of hashing and cryptography.
- Counting and recurrences: how many objects there are, and how a sequence defines itself.
- Graphs and trees: the basic model of connected things.
Vocabulary
- Induction: prove a base case and that each case implies the next, to cover all natural numbers.
- Congruence: two integers are congruent modulo n when n divides their difference.
- Bijection: a one-to-one matching between two sets, used to compare sizes.
- Partial order: a relation that is reflexive, antisymmetric and transitive, as in "divides".
What to study, in order
- Propositional logic and truth tables; then write proofs by contradiction and by induction.
- Sets, functions and relations, and test equivalence relations in code.
- Modular arithmetic: implement Euclid's algorithm and modular exponentiation.
- Counting: permutations, combinations, the pigeonhole principle, and recurrences solved by hand.
- Graph basics, then a small project that uses several of these together, such as a toy RSA.
Related tags
#combinatorics #graph-theory #logic #cryptography #algorithms