S016 · Discrete Math — Sets, Logic, Combinatorics, Graphs
The vocabulary of computer science: sets, boolean logic, counting arguments, and graph theory — the four discrete-math tools you'll use in every subsequent session.
🎯 Fluently translate ‘programmer English’ into set / logic / graph notation, and back — enough to read a paper, a formal spec, or a database query plan without stalling.
Why this session exists
The interesting part of computer science lives in the discrete world: whole numbers, yes/no answers, choices, graphs, states. When you write WHERE a AND (b OR NOT c) you're doing propositional logic. When you index a dict you're using a partial function on a set. When you write a permission system you're doing set algebra. When you route packets you're walking a graph. Discrete math is the notation professionals use to think precisely about these things — and to write down algorithms in a way that other people (and mypy, and formal-verification tools) can actually verify.
- Read and write set-builder notation ({x ∈ S | P(x)}), and translate to Python comprehensions and SQL.
- Read a propositional-logic expression (¬, ∧, ∨, →, ⇔) fluently and simplify with De Morgan's laws.
- Count arrangements with permutation and combination formulas (nPr, nCr) — and know which one to use.
- Distinguish directed vs undirected, weighted vs unweighted graphs and pick the right representation.
- Recognise which of BFS, DFS, or topological sort applies to a given real-world problem.
Prerequisites
- S015 · Big-O — you'll count operations on sets and graphs.
- High-school algebra. That's it — no calculus.
(a) Intuition · 5 min
A city planner asks four completely different questions in a single meeting: "Which neighbourhoods have both schools and hospitals?" (sets) · "If we build a bridge, will the traffic-light logic still work?" (logic) · "How many bus routes are possible between five hubs?" (combinatorics) · "What's the shortest route from A to B?" (graphs). Same city, four vocabularies.
You'll do the same in code. A search filter is a set. An access-control rule is logic. A pagination-key generator is combinatorics. A dependency resolver is a graph. Different problems, one language once you learn each dialect.
The four sub-fields aren't optional — they're the alphabet of everything downstream. SQL is applied set theory. Type systems are applied propositional logic. Machine-learning cost of a feature explosion is combinatorics. Every dependency graph, permission graph, social graph, model graph is graph theory.
You don't need to become a mathematician. You need to be fluent enough to read when someone writes it down.
The four sub-fields, in one line each
- Sets — collections without order or duplicates. Union ∪, intersection ∩, difference ∖, subset ⊆.
- Logic — propositions and connectives. ¬ (not), ∧ (and), ∨ (or), → (implies), ⇔ (iff).
- Combinatorics — counting arrangements. Permutations P(n,r) = n!/(n-r)!, combinations C(n,r) = n!/(r!(n-r)!).
- Graphs — vertices connected by edges. Directed vs undirected, weighted vs unweighted, cyclic vs DAG.
A quick history
- 1874Cantor · set theoryGeorg Cantor invents set theory, discovers different sizes of infinity. Foundations shake for 50 years.
- 1854Boole · logic as algebraGeorge Boole writes The Laws of Thought — the algebra that becomes every digital circuit.
- 1736Euler · Seven Bridges of KönigsbergLeonhard Euler solves a Prussian-town puzzle and accidentally invents graph theory.
- 1936Turing · computable numbersAlan Turing formalises what an algorithm IS using an abstract machine — the seed of CS.
- 1959Dijkstra's shortest-path algorithmEdsger Dijkstra thinks it up in 20 minutes at a café. Every routing system today descends from it.
- 1970sCodd · relational algebra = set theory for DBsTed Codd shows a database is just sets of tuples with set-algebra operators. SQL is born.
(b) Visual walkthrough · 15 min
Sets: three operations, three Venn diagrams
Concrete: if A = {1,2,3} and B = {3,4,5} then
A ∪ B = {1,2,3,4,5}, A ∩ B = {3}, A ∖ B = {1,2}.
Python translation:
A, B = {1,2,3}, {3,4,5}
A | B # union
A & B # intersection
A - B # difference
A ^ B # symmetric difference {1,2,4,5}
A <= B # subset checkLogic: connectives and De Morgan's laws
Boolean connectives and their code equivalents
De Morgan's laws — the two identities that unblock 90% of boolean bugs:
¬(p ∧ q) ≡ ¬p ∨ ¬q (NOT of AND = OR of NOTs)
¬(p ∨ q) ≡ ¬p ∧ ¬q (NOT of OR = AND of NOTs)
Combinatorics decision tree
Picking → combination. Arranging → permutation.
Without = each item used at most once (the usual case). With = same item can appear multiple times.
‘Arrange all n people in a line’ is n!. ‘Arrange r of n people’ is P(n,r) = n!/(n-r)!.
If two items are identical, divide out the ways they could be permuted (multinomial coefficient).
Formulas cheat sheet:
Order matters
- Number of ways to arrange r of n distinct items
- P(n,r) = n! / (n-r)!
- P(5,3) = 60 — sprint-podium finishes for 5 runners
- Python: math.perm(5, 3)
Order doesn't matter
- Number of ways to CHOOSE r of n distinct items
- C(n,r) = n! / (r! (n-r)!) — the ‘binomial coefficient’
- C(52,5) = 2 598 960 — five-card poker hands
- Python: math.comb(52, 5)
Same item reusable
- Ordered w/ repl: n^r — 10⁴ = 10 000 four-digit PINs
- Unordered w/ repl: C(n+r-1, r) — stars-and-bars
- Passwords, hash outputs, IP subnets
Some items identical
- n! / (n₁! · n₂! · … · nk!)
- ‘MISSISSIPPI’ = 11! / (4!·4!·2!·1!) = 34 650 anagrams
- Rare in day-to-day code; useful in probability
Graph representations
Two ways to store the same graph:
# Adjacency list — O(V + E) space, best for sparse graphs
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D", "E"],
"D": ["E"],
"E": [],
}
# Adjacency matrix — O(V^2) space, best for dense graphs / fast edge lookup
V = ["A", "B", "C", "D", "E"]
M = [[0,1,1,0,0],
[0,0,0,1,0],
[0,0,0,1,1],
[0,0,0,0,1],
[0,0,0,0,0]]Choose the representation:
Sparse graphs, most real graphs
- O(V+E) memory
- O(degree) to enumerate neighbours
- O(V+E) full traversal
- Web graph, social graph, roads
Dense graphs, edge-lookup-heavy
- O(V²) memory
- O(1) ‘is A→B an edge?’
- O(V²) full traversal
- Small dense graphs, ML on graphs, image grids
"Discrete math is academic. Sets, logic, combinatorics, graphs — I use SQL and Python every day and never need any of it."
You use it constantly, unnamed. A SQL JOIN is a filtered Cartesian product, DISTINCT is set semantics, GROUP BY is a partition into equivalence classes, a DAG scheduler is graph theory, a hash partition is modular arithmetic, and every WHERE clause is propositional logic that the optimiser rewrites using De Morgan's laws. Not knowing the names is what makes the failures look mysterious.
Because the abstractions are genuinely good — they let you be productive without the theory, so the theory looks optional. It stops being optional at precisely the moments that cost the most. A NOT IN subquery that silently returns zero rows when the subquery contains one NULL is three-valued logic, and it is completely inexplicable under two-valued reasoning. A left join that produced more rows than the left table is a non-unique key breaking the function property you assumed. A pipeline that deadlocks is a cycle in a graph you believed was acyclic. Each of these looks like a database quirk and is in fact a theorem you didn't know you were relying on.
Three-valued logic, in the wild — this returns nothing, and nothing warns you:
-- ids = (1, 2, NULL)
SELECT * FROM t WHERE t.id NOT IN (1, 2, NULL); -- zero rows, always
-- because NOT IN expands to:
-- id <> 1 AND id <> 2 AND id <> NULL
-- and (anything <> NULL) is UNKNOWN, never TRUE
-- so the AND can never be TRUE. Use NOT EXISTS instead.Why does the pigeonhole principle guarantee that every hash function has collisions — and why does that force every hash table to carry a collision-handling mechanism it can never remove?
- 1A hash function maps an input domain (all possible keys) to a finite codomain (buckets, or fixed-width hash values).forced by · the output must fit in a fixed number of bits to be usable as an index or a stored digest
- 2The domain of possible keys is vastly larger than the codomain — unbounded, for strings — while the codomain has at most 2^k elements.forced by · keys are arbitrary-length data; hashes are fixed-length by construction
- 3By pigeonhole, mapping more items than containers forces at least two items into some container. With an infinite domain, every bucket has infinitely many keys mapping to it.forced by · you cannot injectively map a larger set into a smaller one — this is arithmetic, not a property of the function
- 4Therefore collisions are not a defect of a bad hash function; they are unavoidable for every hash function that will ever exist. A good hash only makes them uniformly distributed rather than rare.forced by · the counting argument is independent of how the function computes its output
- 5So a hash table must always include a resolution strategy — chaining or open addressing — and its O(1) guarantee is conditional on collisions staying rare, which requires both a good hash and a bounded load factor.forced by · with all n keys in one bucket, lookup degenerates to a linear scan
Therefore "O(1) average" for hash tables carries a hidden assumption about key distribution, and that assumption is attackable. This is exactly the basis of hash-flooding denial-of-service attacks, and why Python randomises string hashing per process by default (PYTHONHASHSEED).
And note what this predicts in data engineering: hash-partitioning a dataset on a skewed key cannot distribute it evenly, no matter how good the hash — if 40% of rows share one customer id, they share one hash and therefore one partition. That is a straight consequence of the same counting argument, and it is why the fix is salting the key rather than changing the hash function. It also predicts why birthday-bound reasoning matters for ID generation: collision probability rises with the square root of the space, not linearly.
Almost every data structure and query is one of three things. A set: unordered, no duplicates, membership is the only question. A relation: a set of tuples, i.e. a table, and every join, filter, and projection is an operation on relations. A graph: nodes and edges, which is what you have whenever things reference other things — dependencies, lineage, foreign keys, retries.
Naming which one you are holding tells you immediately which properties you get for free and which you must prove. Sets give you dedup and commutative union. Relations give you the whole algebra SQL implements. Graphs give you reachability and cycles — and the question "is this acyclic?" that scheduling depends on.
- A join is a Cartesian product with a filter. Row explosion is not a bug; it is the product doing exactly what it does when the join key isn't unique on the side you assumed.
- NULL is not a value, it's "unknown", so SQL logic is three-valued.
NULL = NULLis UNKNOWN, which is whyNOT INwith NULLs is empty and whyGROUP BYnonetheless groups NULLs together. - De Morgan's laws are how you rewrite a filter you can't reason about:
NOT (A AND B)≡(NOT A) OR (NOT B). Query planners do this constantly, and so should you when a predicate stops making sense. - Any dependency structure is a graph; if it must be executed, it must be acyclic. Topological sort is the only correct execution order, and "cannot topologically sort" is what a cycle error actually means.
Fire this model the moment you see: a join that multiplied your row count · NOT IN returning nothing · a COUNT(*) and COUNT(col) disagreeing · a scheduler reporting a circular dependency · one partition taking 10× longer than the rest · a dedup that didn't dedup because the key had NULLs.
You need to test membership of billions of keys — "have I seen this id before?" Exact set, sorted structure, or a probabilistic filter?
The question that decides it is not "how much memory do I have" but "what does a wrong answer cost?" If a false positive triggers a cheap verification step, the probabilistic structure wins massively on memory. If a false positive silently drops a record, no space saving justifies it.
The layered answer is the one production systems actually use: a Bloom filter in front of an exact store, so the filter absorbs the overwhelming majority of negative lookups for a few bits per key, and the exact structure resolves the small fraction that pass. Storage engines are built this way for precisely this reason.
(c) Hands-on · 25 min
You'll compute a small dependency graph, run BFS + DFS + topological sort on it, and turn boolean-condition simplification into a testable function. Save as discrete_demo.py.
Run it:
python discrete_demo.pyExpected output (BFS/DFS orders depend on insertion order):
What each block does
Anatomy of the demo
Match each real-world task to a discrete-math tool:
# 1. Users allowed if they're in group A OR group B, but NOT banned.
# 2. Total number of possible 8-character passwords using a-z A-Z 0-9.
# 3. Given a set of pages a user visited, find pages visited by both users A and B.
# 4. Order in which npm should install packages so no dep is installed after its dependent.
# 5. Find shortest path from London to Berlin on a road network.
# 6. Simplify: NOT (isAdmin AND (isBanned OR NOT hasPaid)).Answer key
- Set + Logic (set membership + boolean combo)
- Combinatorics (ordered with replacement: 62⁸ ≈ 218 trillion)
- Sets (intersection)
- Graph (topological sort on a DAG)
- Graph (BFS if unweighted, Dijkstra if weighted)
- Logic (De Morgan:
NOT isAdmin OR (NOT isBanned AND hasPaid))
(d) Production reality · 15 min
LinkedIn's "People You May Know" feature computed 2nd-degree connections by BFS. Naive implementation: for each user, expand to friends, then friends-of-friends, dedupe with a set. Simple enough — until n hit 500 million and a single query took 30 s of database round-trips.
The graph was there. The algorithm was correct. The representation was wrong for the scale.
A data engineer writes SELECT user_id FROM active EXCEPT SELECT user_id FROM banned to find non-banned users. Except banned has NULL user_ids for guests. EXCEPT's handling of NULL is subtle across engines — some treat NULLs as equal, some don't — and the query silently drops different rows on PostgreSQL vs Snowflake vs BigQuery.
WHERE user_id NOT IN (SELECT ... WHERE user_id IS NOT NULL) — spell out the NULL handling. Add a unit test that runs the query against a fixture including NULLs. Read the engine's docs on 3-valued logic (TRUE / FALSE / UNKNOWN) once and remember forever.Where this shows up in the rest of the plan
(e) Recall + stretch · 10 min
Explain-out-loud test
- What's the difference between a permutation and a combination? Give one real example of each.
- State one of De Morgan's laws in plain English.
- What is a DAG and name one everyday example.
What comes next
Hub: The 6-Month Learning Plan
Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.