Skip to content
Tutorials Center
My learning

Topics

Discrete Mathematics Tutorial

Learn Discrete Mathematics step by step: 68 lessons in 12 chapters with examples, quizzes, diagrams and projects.

Start learning →

of lessons completed

Getting Started

  1. 1 What Is Discrete Mathematics? Discover what discrete mathematics is, how it differs from calculus, where it powers software, and how to explore proofs and notation by running Python.
  2. 2 Mathematical Notation and Python Translate mathematical symbols into Python: sigma and pi as sums and products, quantifiers as all() and any(), set-builder notation, floor, ceiling and divmod.

Logic

  1. 3 Propositional Logic Learn propositions, truth values, the connectives AND, OR and NOT, how to build compound statements, operator precedence and how to evaluate them in Python.
  2. 4 Implication and Biconditional Understand if-then statements, why a false hypothesis makes them vacuously true, and how converse, inverse, contrapositive and iff relate, with Python checks.
  3. 5 Truth Tables Build truth tables by hand and with itertools.product, classify formulas as tautologies, contradictions or contingencies, and test equivalence by brute force.
  4. 6 Logical Equivalences and Laws Learn the laws of propositional logic, including De Morgan, distributive and absorption, use them to simplify expressions, and verify each law in Python.
  5. 7 Normal Forms and SAT Convert logical formulas to CNF and DNF, understand the SAT problem, write a brute-force solver and learn how DPLL with unit propagation searches smarter.
  6. 8 Predicates and Quantifiers Learn predicate logic: predicates, universal and existential quantifiers, nested quantifiers and negation rules, tested on finite domains with all() and any().
  7. 9 Rules of Inference and Formal Arguments Learn valid arguments and the standard rules of inference: modus ponens, modus tollens, syllogism, resolution and common fallacies, checked in Python.

Sets, Relations and Functions

  1. 10 Sets and Set Operations Learn sets: membership, subsets, union, intersection, difference, complement, Venn reasoning and set identities, all tested with Python's set type.
  2. 11 Fuzzy Sets and Multisets Go beyond ordinary sets: multisets that count repeats and fuzzy sets with degrees of membership, with union, intersection and complement in Python.
  3. 12 Power Sets and Cartesian Products Generate power sets and understand 2^n growth, build ordered pairs and Cartesian products with itertools, and enumerate the partitions of a set in Python.
  4. 13 Relations Learn binary relations as sets of pairs, the properties reflexive, symmetric, antisymmetric and transitive, Python checkers and relation matrices.
  5. 14 Closures of Relations and Warshall's Algorithm Build the reflexive, symmetric and transitive closure of a relation, understand reachability and compute transitive closure with Warshall's algorithm in Python.
  6. 15 Equivalence Relations and Partial Orders Equivalence classes and partitions, partial and total orders, Hasse diagrams drawn with matplotlib, lattices and topological sorting, all in Python.
  7. 16 Partial Orders, Hasse Diagrams and Lattices Go deeper into partially ordered sets: upper and lower bounds, least upper bound and greatest lower bound, lattice tests, distributive and Boolean lattices.
  8. 17 Functions and Cardinality Learn injective, surjective and bijective functions, composition, inverses, counting functions, and why some infinite sets are bigger than others.

Proof Techniques

  1. 18 How Proofs Work Learn what a proof is, how definitions and theorems fit together, and how to write direct proofs, find counterexamples and split into cases.
  2. 19 Contradiction and Contrapositive Learn proof by contrapositive and proof by contradiction with classic examples: the irrationality of the square root of 2 and infinitely many primes.
  3. 20 Mathematical Induction Learn mathematical induction with base case and inductive step, proofs of sum formulas, divisibility and inequalities, and the mistakes to avoid.
  4. 21 Strong Induction and Well-Ordering Learn strong induction, the well-ordering principle and structural induction on lists and trees, with prime factorization and stamp examples in Python.

Number Theory

  1. 22 Divisibility and Primes Learn divisibility, the division algorithm, primes, the Fundamental Theorem of Arithmetic, prime factorization, the sieve of Eratosthenes and primality tests.
  2. 23 GCD, LCM and the Euclidean Algorithm Compute the greatest common divisor and least common multiple, trace Euclid's algorithm, use the extended version for Bezout coefficients, and see why it is fast.
  3. 24 Modular Arithmetic Learn congruences and residues, do clock arithmetic, use Python's pow(a, b, m) for fast powers, compute modular inverses and solve linear congruences.
  4. 25 Number Bases and Representations Convert between decimal, binary, octal and hex with division and place values, learn two's complement for negative numbers and see why 0.1 + 0.2 is not 0.3.
  5. 26 Number Theory in Cryptography See Fermat's little theorem, the Chinese remainder theorem, toy RSA, a Diffie-Hellman exchange and the Luhn and ISBN checksums, all with tiny numbers in Python.

Sequences, Sums and Recurrences

  1. 27 Sequences and Summations Work with arithmetic and geometric sequences, sigma notation, closed-form sums and telescoping series, then compute and plot partial sums in Python.
  2. 28 Recurrence Relations Define sequences recursively, model problems with recurrences, study Fibonacci and the Tower of Hanoi, and compute terms with recursion, memoization and loops.
  3. 29 Solving Recurrences Turn a recurrence into a closed form by unrolling, characteristic equations and the Master theorem, and check every answer numerically in Python.
  4. 30 Generating Functions Use ordinary generating functions to count selections, dice sums and partitions, and to solve linear recurrences like Fibonacci, with Python series code.

Counting

  1. 31 Counting Principles Learn the sum rule, product rule, inclusion-exclusion and the pigeonhole principle, and verify each counting argument by brute force in Python.
  2. 32 Permutations and Combinations Count arrangements and selections with factorials, nPr and nCr, with and without repetition, and use math.perm, math.comb and itertools to verify.
  3. 33 Binomial Theorem and Pascal's Triangle Expand (x + y)^n with binomial coefficients, build Pascal's triangle, prove identities by counting, and use stars and bars and multinomial coefficients.
  4. 34 Balls into Boxes: The Twelvefold Way Count the ways to place n balls into k boxes in all twelve cases (distinguishable or not, any, injective or surjective) using powers, binomials, Stirling and partition numbers.
  5. 35 Advanced Counting Count derangements, Catalan numbers, Stirling numbers and integer partitions, and meet generating functions, with each result computed and checked in Python.
  6. 36 Counting with Symmetry: Burnside's Lemma Count objects up to symmetry with Burnside's lemma: orbits, fixed points, necklaces and colored cubes, all verified against brute force in Python.
  7. 37 Discrete Probability Learn sample spaces, events, conditional probability, independence, Bayes' theorem and expected value, with exact fractions and seeded Monte Carlo in Python.
  8. 38 Discrete Distributions: Uniform, Binomial, Poisson, Geometric, Hypergeometric Learn random variables, the PMF, mean and variance, then the uniform, binomial, geometric, Poisson and hypergeometric distributions, checked by simulation.
  9. 39 Ramsey Theory and Pigeonhole Extensions Learn Ramsey theory: why any group of six contains three mutual friends or strangers, how R(3,3) = 6 is proved, and verify it by brute force in Python.

Graph Theory

  1. 40 Graphs: Terms and Representations Learn graph vocabulary, degree, the handshake lemma and special graphs, then store graphs as adjacency lists and matrices in plain Python.
  2. 41 Paths, Cycles and Connectivity Learn walks, paths, cycles, connected components and cut vertices, and compute each one in Python with BFS, DFS and matrix powers.
  3. 42 Trails, Circuits and Graph Connectivity: kappa, lambda and Menger Classify walks, trails, paths, circuits and cycles, then measure how well connected a graph is with vertex connectivity, edge connectivity, Whitney's inequality and Menger's theorem.
  4. 43 Euler and Hamilton Paths Learn when a graph has an Euler circuit or a Hamilton cycle, from the Konigsberg bridges to Hierholzer's algorithm and brute-force search.
  5. 44 Independent Sets, Vertex Covers, Edge Covers and Matchings Learn independent sets, vertex covers, edge covers and matchings, the identities that link them, and how maximal differs from maximum, with Python.
  6. 45 Matching Algorithms: Augmenting Paths, Hopcroft-Karp and the Hungarian Method Find maximum matchings with augmenting paths (Kuhn's algorithm), speed them up with Hopcroft-Karp, solve cheapest assignments with the Hungarian method, and meet the blossom algorithm.
  7. 46 Trees and Spanning Trees Learn tree properties, Cayley's formula and spanning trees, then build minimum spanning trees with Kruskal and Prim and encode trees as Prufer codes.
  8. 47 Binary Tree Traversals and Huffman Coding Visit binary trees in preorder, inorder, postorder and level order, evaluate expression trees, and build prefix codes with Huffman's algorithm in Python.
  9. 48 Graph Coloring and Planarity Learn chromatic numbers, greedy and exact coloring, bipartite tests, scheduling as coloring, Euler's formula and planar graphs, with Python code.
  10. 49 Shortest Paths, Matching and Flows Learn weighted shortest paths with Dijkstra, bipartite matching with Hall's theorem, and max-flow min-cut with Edmonds-Karp, all in short Python code.
  11. 50 Graph Isomorphism and Drawing Graphs Decide when two graphs are the same, use invariants to tell them apart, and draw graphs with a hand-written spring layout in matplotlib.

Algebraic Structures and Boolean Algebra

  1. 51 Boolean Algebra and Logic Circuits Learn Boolean algebra, logic gates, Karnaugh maps, half and full adders, and build a small ALU from gates in Python, with live examples.
  2. 52 Groups, Rings and Fields (Gentle Intro) Meet groups, rings and fields through modular arithmetic and the symmetries of a square, and check the axioms by brute force in Python.
  3. 53 Permutation Groups: Cycles, Transpositions, Parity and Conjugation Work with permutations in cycle notation, factor them into transpositions, decide even or odd, find orders, use conjugation and inner automorphisms, and apply parity to sliding puzzles.
  4. 54 Homomorphisms, Isomorphisms and Automorphisms Learn structure-preserving maps between groups: homomorphisms, kernels, isomorphisms, automorphisms, plus semigroups and monoids, all checked by Python.

Computation and Languages

  1. 55 Finite Automata and Regular Languages Learn DFAs, NFAs and regular languages, simulate state machines in Python, convert NFAs to DFAs, and see how regular expressions connect.
  2. 56 Context-Free Grammars, Pushdown Automata and Turing Machines Climb the Chomsky hierarchy: write context-free grammars, simulate pushdown automata with a stack, and run a Turing machine, with Python simulators.
  3. 57 Algorithms, Recursion and Growth Prove algorithms correct with loop invariants and induction, count operations, and compare growth rates from log n to 2^n with runnable Python.

Projects

  1. 58 Project: A Tiny SAT Solver Build a SAT solver from scratch: parse formulas, convert to CNF, run DPLL with unit propagation, then solve a Sudoku and an exam schedule.
  2. 59 Project: A Combinatorics Toolkit Build a small counting library from scratch, check every formula against brute-force enumeration, simulate the birthday paradox and print a tidy report.
  3. 60 Project: Social Network Analyzer Model a small social network as a graph and compute degrees, components, shortest paths and centrality by hand, then draw the result with matplotlib.
  4. 61 Project: Modular Arithmetic and Toy RSA Build a modular arithmetic library with extended gcd, inverses and the Chinese remainder theorem, test it, then use it to run a toy RSA demonstration.
  5. 62 Project: Exam Scheduler with Graph Coloring Turn exam conflicts into a graph, color it with greedy and backtracking algorithms to find the fewest time slots, and print a clean timetable.

Practice and Review

  1. 63 Common Mistakes and Pitfalls Learn the classic errors in counting, implication, double counting, floating point and induction, and use short Python experiments to catch each one.
  2. 64 Exercises: Logic, Sets and Proofs Sixteen graded exercises on logic, quantifiers, sets, relations, functions and proofs, each with a runnable Python solution that checks the answer.
  3. 65 Exercises: Counting and Number Theory Seventeen graded exercises on counting, probability, divisibility, modular arithmetic, number bases and toy RSA, each with a runnable Python solution.
  4. 66 Exercises: Graphs and Recurrences Seventeen graded exercises on graphs, trees, coloring, shortest paths, matching and recurrence relations, each with a runnable Python solution.
  5. 67 Discrete Math Interview Questions Typical interview questions on logic puzzles, counting, probability, graphs and modular arithmetic, with short answers and runnable checks in Python.
  6. 68 Discrete Mathematics Cheat Sheet A one-page discrete mathematics cheat sheet: formulas for logic, sets, counting, probability, number theory, graphs and recurrences, with Python one-liners.