‹ All tracks

Discrete Mathematics

Logic and proofs, induction, sets, functions and relations, counting, recurrences, number theory, RSA and graphs, every idea checked with Python.

• Online Python compiler
• Python code visualizer
• Discrete Math exercises with solutions

1. 1

   Propositions and truth tables

   Statements that are true or false, the connectives not, and, or, xor, implies and if-and-only-if, and truth tables that list every case.

2. 2

   Logical equivalence

   Tautologies and contradictions, when two formulas mean the same, the laws of logic (De Morgan's and more), and the contrapositive, converse and inverse.

3. 3

   Predicates and quantifiers

   Statements with variables, 'for all' and 'there exists', Python's all() and any(), negating a quantifier, and why the order of nested quantifiers matters.

4. 4

   Proofs and counterexamples

   Why checking examples is not a proof, and four ways to prove things: directly, by the contrapositive, by contradiction, and disproving with a counterexample.

5. 5

   Mathematical induction

   Prove a statement for every whole number with a base case and an inductive step, see strong induction, and connect induction to recursion.

6. 6

   Sets

   Writing sets, subsets, union, intersection, difference and complement, Venn diagrams, power sets, Cartesian products and counting with inclusion-exclusion.

7. 7

   Functions

   Domain, codomain and range; one-to-one, onto and bijective functions, checked in Python; composition, inverses, floor and ceiling, and counting functions.

8. 8

   Relations

   Relations as sets of pairs; reflexive, symmetric, antisymmetric and transitive relations; equivalence relations and their classes; and partial orders.

9. 9

   Counting: permutations and combinations

   The sum and product rules, permutations and combinations with and without repetition, Pascal's triangle and the binomial theorem.

10. 10

    The pigeonhole principle and inclusion-exclusion

    If there are more items than boxes, some box holds two; the generalized form; the birthday problem; and counting a union of three sets.

11. 11

    Recurrence relations

    Sequences defined by earlier terms: the Tower of Hanoi and Fibonacci, solving by unrolling, the characteristic equation, and divide-and-conquer recurrences.

12. 12

    Divisibility, primes and the gcd

    Division with remainder, primes and the sieve of Eratosthenes, unique factorization, the greatest common divisor by Euclid's algorithm, and the lcm.

13. 13

    Modular arithmetic and RSA

    Congruences and clock arithmetic, modular inverses with the extended Euclidean algorithm, fast modular powers, Fermat's little theorem, and how RSA encryption works.

14. 14

    Graphs

    Vertices and edges, degrees and the handshake lemma, special graphs, trees, Euler paths and circuits (the bridges of Königsberg), Hamilton cycles, colouring and planar graphs.