Skip to the content ForoHackers
Log inJoin

Discrete mathematics: start here

Discrete mathematics
#629 · Ophuscado · · Report

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

  1. Propositional logic and truth tables; then write proofs by contradiction and by induction.
  2. Sets, functions and relations, and test equivalence relations in code.
  3. Modular arithmetic: implement Euclid's algorithm and modular exponentiation.
  4. Counting: permutations, combinations, the pigeonhole principle, and recurrences solved by hand.
  5. 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

Log in or join to reply.