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
- 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.
- 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
- 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.
- 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.
- Truth Tables Build truth tables by hand and with itertools.product, classify formulas as tautologies, contradictions or contingencies, and test equivalence by brute force.
- 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.
- 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.
- Predicates and Quantifiers Learn predicate logic: predicates, universal and existential quantifiers, nested quantifiers and negation rules, tested on finite domains with all() and any().
- 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
- Sets and Set Operations Learn sets: membership, subsets, union, intersection, difference, complement, Venn reasoning and set identities, all tested with Python's set type.
- 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.
- 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.
- Relations Learn binary relations as sets of pairs, the properties reflexive, symmetric, antisymmetric and transitive, Python checkers and relation matrices.
- 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.
- 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.
- 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.
- Functions and Cardinality Learn injective, surjective and bijective functions, composition, inverses, counting functions, and why some infinite sets are bigger than others.
Proof Techniques
- 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.
- 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.
- Mathematical Induction Learn mathematical induction with base case and inductive step, proofs of sum formulas, divisibility and inequalities, and the mistakes to avoid.
- 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
- Divisibility and Primes Learn divisibility, the division algorithm, primes, the Fundamental Theorem of Arithmetic, prime factorization, the sieve of Eratosthenes and primality tests.
- 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.
- 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.
- 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.
- 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
- 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.
- Recurrence Relations Define sequences recursively, model problems with recurrences, study Fibonacci and the Tower of Hanoi, and compute terms with recursion, memoization and loops.
- Solving Recurrences Turn a recurrence into a closed form by unrolling, characteristic equations and the Master theorem, and check every answer numerically in Python.
- 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
- Counting Principles Learn the sum rule, product rule, inclusion-exclusion and the pigeonhole principle, and verify each counting argument by brute force in Python.
- 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.
- 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.
- 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.
- Advanced Counting Count derangements, Catalan numbers, Stirling numbers and integer partitions, and meet generating functions, with each result computed and checked in Python.
- 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.
- Discrete Probability Learn sample spaces, events, conditional probability, independence, Bayes' theorem and expected value, with exact fractions and seeded Monte Carlo in Python.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- Exercises: Graphs and Recurrences Seventeen graded exercises on graphs, trees, coloring, shortest paths, matching and recurrence relations, each with a runnable Python solution.
- Discrete Math Interview Questions Typical interview questions on logic puzzles, counting, probability, graphs and modular arithmetic, with short answers and runnable checks in Python.
- 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.