Discrete mathematics
Logic, sets, relations, induction, combinatorics and modular arithmetic with concrete examples.
Check digits: Luhn, ISBN and IBAN explained with remainders
How check digits work for payment cards, ISBNs and IBANs: the Luhn algorithm, weights modulo 10 and 11, the modulo 97 check, and which errors they catch.
CNF and DNF normal forms: what they are and how to get them
Conjunctive and disjunctive normal form explained with examples: literals, clauses, deriving them from a truth table, and why SAT solvers rely on them.
Combinations with repetition: the stars and bars method
Counting choices with repeated elements: the stars and bars method, integer solutions of an equation, minimum and maximum constraints, anagrams.
Counting principles: the sum rule and the product rule
The basic rules of combinatorics: sum, product, complement and division, applied to passwords, PINs, identifier codes and circular arrangements.
De Morgan's laws and logical equivalences for simplifying
The fundamental logical equivalences, De Morgan's laws and how to use them to simplify conditions in code and queries without changing their meaning.
Equivalence relations, classes and partitions of a set
Equivalence relations, equivalence classes and partitions: how the three ideas connect, concrete examples, and the union-find structure for computing them.
Extended Euclidean algorithm and modular inverse, step by step
GCD with Euclid's algorithm, Bézout's identity, the extended algorithm for modular inverses and the Chinese remainder theorem, with worked examples.
Implication, converse and contrapositive: never mix them up
The difference between implication, converse, inverse and contrapositive, necessary and sufficient conditions, with examples from code and real life.
The inclusion-exclusion principle: counting without duplicates
How to count the union of overlapping sets: inclusion-exclusion with two, three and n sets, divisibility, derangements and Euler's totient function.
Infinities of different sizes: countability and Cantor's diagonal
Why the evens are «as many as» the naturals, why the rationals are countable and the reals are not: bijections and Cantor's diagonal argument.
Injective, surjective and bijective functions with examples
Domain, codomain and image; when a function is injective, surjective or bijective, how to invert it, and why it matters for hashes, keys and encodings.
The principle of mathematical induction with worked examples
How a proof by induction works: base case, inductive hypothesis and step, with worked examples on sums, inequalities and divisibility, common mistakes.
Modular arithmetic and congruences: clock arithmetic
Congruences modulo n, operations on remainders, negative remainders in programming languages, modular powers and Fermat's little theorem, with examples.
Partial orders and Hasse diagrams: a practical guide
What a partial order is, how to draw a Hasse diagram, the difference between maximal and maximum, total orders, lattices and examples from computing.
Permutations, arrangements and combinations: which to use
When order matters and when it doesn't: permutations, k-permutations and combinations, the binomial coefficient, Pascal's triangle and practical examples.
The pigeonhole principle: a simple, surprising idea
The pigeonhole principle in its simple and generalised forms, with surprising proofs and real applications to compression, hash functions and checksums.
Power set and Cartesian product, clearly explained
What the power set and Cartesian product are, why they have 2^n and n·m elements, and how they apply to permissions, configurations and testing.
Proof techniques: direct, by contradiction and by cases
The main proof techniques in discrete mathematics with complete examples: direct proof, contradiction, proof by cases, constructive proof, counterexamples.
Binary relations: reflexive, symmetric and transitive
What a binary relation is and how to recognise reflexive, symmetric, antisymmetric and transitive properties using matrices, graphs and concrete examples.
Propositional logic: connectives and truth tables explained
What a proposition is, how negation, conjunction, disjunction and implication work, and how to build a truth table without mistakes, step by step.
Predicate logic: quantifiers, negation and their order
Predicates, domains, universal and existential quantifiers: how to negate them correctly and why the order of quantifiers changes what a statement means.
Recurrence relations: from definition to closed form
What recurrence relations are and how to solve them: iterated substitution, the characteristic equation, Tower of Hanoi, Fibonacci and divide and conquer.
Rules of inference: modus ponens, modus tollens, resolution
The rules of inference in logic: modus ponens, modus tollens, syllogisms and resolution, with an example of a formal deduction built up step by step.
Set operations: union, intersection and difference
Sets, membership and inclusion, union, intersection, difference and complement explained with practical examples, Venn diagrams and Python code.
Strong induction and loop invariants: proving code correct
Strong induction, structural induction and loop invariants: how to use them to prove theorems and the correctness of iterative algorithms, with examples.