Discrete Mathematics

Units

1. 1

   Logic

   3 lessons

   1. Propositions and truth tablesCombine propositions with not, and, or, if-then and if-and-only-if, and build truth tables column by column, including the conditional's rows read as a promise kept or broken.
   2. Logical equivalenceDecide whether two compound propositions are equivalent by comparing truth tables, use De Morgan's laws to negate 'and' and 'or', and tell the contrapositive, which is equivalent to a conditional, from the converse and inverse, which are not.
   3. Predicates and quantifiersRead a predicate P(x) over a domain through its truth set, decide statements with ∀ and ∃, negate them by flipping the quantifier, and see why the order of nested quantifiers matters.
2. 2

   Methods of proof

   2 lessons

   1. Direct proofProve statements about even and odd integers and about divisibility straight from the definitions: take arbitrary objects satisfying the hypothesis, write the definitions as equations, compute, and match the definition of the conclusion, laid out as a chain of statements and reasons.
   2. Contrapositive and contradictionProve "if n² is even then n is even" by the contrapositive and "√2 is irrational" by contradiction, choosing the method by which side gives an equation to work with.
3. 3

   Induction and recursion

   3 lessons

   1. Mathematical inductionProve a statement P(n) for every integer n ≥ 1 by a base case and an inductive step that uses the inductive hypothesis, and write the proof in full sentences.
   2. Strong inductionProve P(n) by assuming P(j) for every case from the base up to k, not only for k itself, and choose the right number of base cases for the step.
   3. Recursive definitionsDefine a sequence, a set of strings and a family of trees recursively, compute with the definition, and prove a property of a recursively defined structure by structural induction.
4. 4

   Sets, functions and relations

   3 lessons

   1. Sets and set operationsDescribe sets in roster and set-builder notation, decide subset relations, compute unions, intersections, differences and complements on a Venn diagram, and count the power set and the Cartesian product.
   2. FunctionsRead a function as an arrow diagram from domain to codomain, decide whether it is one-to-one, onto or bijective, and compose functions and invert a bijection.
   3. RelationsRepresent a relation as a set of pairs and as a directed graph, test it for the reflexive, symmetric, antisymmetric and transitive properties, find the classes of an equivalence relation, and draw a partial order as a Hasse diagram.
5. 5

   Counting

   5 lessons

   1. The product and sum rulesCount outcomes with the product rule for choices made in a row, the sum rule for choices from separate cases, and the subtraction rule when two cases overlap, drawing a tree diagram to check each.
   2. Permutations and combinationsCount ordered selections with P(n, r) = n!/(n − r)! and unordered selections with C(n, r) = n!/(r!(n − r)!), deciding from the wording whether order matters, and apply both to committees, poker hands and bit strings.
   3. The binomial theorem and Pascal's triangleExpand (x + y)ⁿ with the binomial theorem by counting choices, build Pascal's triangle from C(n, k) = C(n − 1, k − 1) + C(n − 1, k), and prove identities by counting one set in two ways.
   4. The pigeonhole principleState and prove the pigeonhole principle and its generalized form ⌈N/k⌉, choose the pigeons and the boxes in a problem, and use it to prove that some outcome must occur.
   5. Inclusion and exclusionCount |A ∪ B ∪ C| by adding the singles, subtracting the pairs and adding the triple, explain why each region is counted once, and apply the principle to integers divisible by 2, 3 or 5 and to onto functions.
6. 6

   Number theory

   4 lessons

   1. Divisibility and primesDivide with remainder as a = qb + r, test divisibility by rule and by trial division up to √n, find primes with the sieve of Eratosthenes, and factor an integer into primes in exactly one way.
   2. The Euclidean algorithmCompute gcd(a, b) by repeated division, reverse the steps to write it as as + bt (Bézout's identity), and decide and solve linear Diophantine equations ax + by = c.
   3. Modular arithmeticWork with congruence mod n as clock arithmetic, add and multiply residues, find an inverse mod n when gcd(a, n) = 1, and solve linear congruences such as 3x ≡ 4 (mod 7).
   4. Public-key cryptographyCompute large powers mod n by repeated squaring, use Fermat's little theorem, and run RSA with small primes: choose n = pq, e and d, encrypt and decrypt a number, and say why decryption works.
7. 7

   Recurrence relations

   2 lessons

   1. Modelling with recurrencesSet up a recurrence with initial conditions from a counting or growth problem by splitting on the first or last move, then solve simple ones by iterating, guessing a closed form and proving it by induction.
   2. Solving linear recurrencesSolve linear homogeneous recurrences aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ with constant coefficients through the characteristic equation, for distinct and repeated roots, and derive Binet's formula for the Fibonacci numbers.
8. 8

   Graphs and trees

   4 lessons

   1. Graphs and degreesVertices, edges, degree, the handshake theorem (the degrees sum to twice the edges), simple graphs, complete and bipartite graphs, and adjacency matrices.
   2. Paths, Euler circuits and Hamilton cyclesConnectivity, the bridges of Königsberg and Euler's condition (every degree even), and Hamilton cycles, for which no such test is known.
   3. TreesA tree is connected with no cycles, so it has n − 1 edges; rooted trees, binary trees, and spanning trees found by search and by Kruskal's algorithm on a weighted graph.
   4. Planar graphs and colouringEuler's formula v − e + f = 2 for planar graphs, why K₅ and K₃,₃ are not planar, and vertex colouring with the chromatic number of a map.