Discrete Math

The language of proof, counting without listing, number theory classics, and the vocabulary of graphs.

Sets & Relations

Set Operations — Union, intersection, complement — and the Venn-diagram picture.
Power Sets & Partitions — All 2^n subsets, and splitting a set into disjoint blocks.
Relations — Reflexive, symmetric, transitive — and the transitive closure.
Equivalence Relations — Reflexive + symmetric + transitive: classes that partition a set.
Partial Orders — Reflexive, antisymmetric, transitive — comparability and Hasse diagrams.

Logical Connectives — Negation, and, or, if-then, and if-and-only-if — the truth-table machinery behind every proof, plus the contrapositive and De Morgan's laws.
Quantifiers — For all versus there exists: read the quantifiers, negate them by flipping each one, and remember that the order they appear in changes the claim.
Truth Tables — Evaluate compound propositions; spot tautologies and contradictions.
Logical Equivalence — De Morgan, the conditional rewrite, and the contrapositive.
Valid Arguments — Modus ponens, modus tollens, and the fallacies that mimic them.

Injective & Surjective Functions — One-to-one, onto, bijective — and counting injections.
Cardinality — Same size = a bijection; countable vs uncountable infinity.
Big-O Notation — Bounding growth up to constants; polynomials vs exponentials.

Direct Proof — Start from the hypothesis, unfold the definitions, and push the algebra until the conclusion has nowhere left to hide.
Proof by Contrapositive — When the forward implication feels sticky, turn it around: prove that failing the conclusion would have forced the hypothesis to fail too.
Proof by Contradiction — Assume the opposite, derive absurdity, conclude the original — the technique of √2, primes, and Gödel.
Induction — Base case + inductive step — knock over a chain of dominoes.
Pigeonhole Principle — n items in k boxes: some box has ≥ n/k items.
Permutations & Combinations — Count selections with C(n, k) and arrangements with P(n, k) — cancel the big factorial.
Inclusion–Exclusion — |A ∪ B| = |A| + |B| - |A ∩ B| — alternate signs by intersection size.
Stars and Bars — n items into k bins with nonnegative counts gives n + k - 1k - 1.
Binomial Coefficients — nk counts k-subsets — symmetry, Pascal's recursion, row sums = 2^n.
Constructing Bijections — Prove two sets are equinumerous with an explicit pairing.

Counting Principles — Rule of product (and) and rule of sum (or).
Factorials — n! — the number of ways to line n things up.
Recurrence Relations — Characteristic equation, roots, and the closed-form solution.
Integer Partitions — Counting p(n), and Euler's distinct-parts = odd-parts identity.

Lattices — Meet and join (gcd and lcm); bounded and distributive lattices.
Boolean Algebra — Simplify with complement, absorption, idempotence, and De Morgan.
Karnaugh Maps — Group adjacent 1s to minimize a Boolean function.
Logic Gates & Circuits — AND/OR/NOT/NAND, circuit evaluation, and NAND universality.

Graph Terminology & Representations — Vertices, edges, degree, the handshaking theorem, and adjacency matrices.
Trees — n−1 edges, unique paths, spanning trees, and the MST.
Graph Coloring & Chromatic Number — Proper colorings, the chromatic number, and the Four Color Theorem.
Finite-State Machines & Regular Expressions — DFAs, the languages they recognize, and regular expressions.