Discrete Math for CS [2026]: The Math That Powers Computing

Discrete Math Is the Foundation of Every Algorithm You Use

Continuous math (calculus, differential equations) deals with smooth, uninterrupted quantities. Discrete math deals with distinct, countable structures — integers, graphs, sets, logic. Computers work with discrete structures: bits are 0 or 1, arrays have integer indices, algorithms process finite inputs. Discrete math is the native language of computing.

You use discrete math every day in code, whether you know it or not. Boolean logic in every if statement. Graph algorithms in routing and dependency trees. Set operations in SQL. Combinatorics when you analyze algorithm complexity. Understanding the math makes these things click at a deeper level.

Logic and Boolean Algebra

Propositional logic studies how propositions (statements that are true or false) combine using logical connectives. The connectives map directly to code:

De Morgan's Laws are especially useful in code:

• ¬(P ∧ Q) = ¬P ∨ ¬Q — NOT(A AND B) equals NOT-A OR NOT-B
• ¬(P ∨ Q) = ¬P ∧ ¬Q — NOT(A OR B) equals NOT-A AND NOT-B

// De Morgan in practice: simplify NOT(isAdmin && isLoggedIn)
// Equivalent to: !isAdmin || !isLoggedIn
if (!isAdmin || !isLoggedIn) return "Access denied";

Sets and Functions

A set is an unordered collection of distinct elements. Set theory is the foundation of SQL, type systems, and functional programming.

Key set operations:

• Union A ∪ B — All elements in A or B (SQL: UNION)
• Intersection A ∩ B — Elements in both A and B (SQL: INNER JOIN on same data)
• Difference A \ B — Elements in A but not B (SQL: LEFT JOIN WHERE B IS NULL)
• Subset A ⊆ B — Every element of A is in B
• Power set P(A) — All possible subsets of A. If |A|=n, then |P(A)|=2ⁿ

A function f: A → B maps each element of A (domain) to exactly one element of B (codomain). Types that matter in CS:

• Injective (one-to-one) — Different inputs always produce different outputs. No collisions. Good cryptographic hash functions aim for this.
• Surjective (onto) — Every element of B is mapped to by some element of A.
• Bijective — Both injective and surjective. One-to-one correspondence between domain and codomain. Encryption functions are bijections (decryptable).

Graph Theory: The Most Practically Useful Topic

A graph G = (V, E) consists of vertices (nodes) V and edges (connections) E. Graphs model virtually every relationship-based system.

Graph types:

• Undirected — Edges have no direction (friends on Facebook)
• Directed (digraph) — Edges have direction (Twitter follows, web links)
• Weighted — Edges have numeric weights (road distances, latency)
• DAG (Directed Acyclic Graph) — Directed, no cycles. Task scheduling, dependency graphs, Git history.
• Tree — Connected undirected graph with no cycles. N nodes, N-1 edges.

Graph algorithms every developer should know:

Combinatorics: Counting and Complexity

Combinatorics is the study of counting and arrangements. It's directly connected to algorithm analysis.

Fundamental counting principle: If task A can be done in m ways and task B in n ways independently, there are m × n ways to do both.

Permutations (ordered arrangements): P(n, k) = n!/(n-k)! — ways to choose k items from n in order. A 4-character PIN from 10 digits (no repeats): P(10,4) = 5040.

Combinations (unordered): C(n, k) = n! / (k!(n-k)!) — ways to choose k items from n, order doesn't matter. Choosing 3 features from 10 for a sprint: C(10,3) = 120.

How this connects to Big O:

• O(log n) — Binary search: each step halves the problem. Number of halvings = log₂(n).
• O(n log n) — Merge sort: log n levels of recursion × n work per level
• O(2ⁿ) — Checking all subsets (power set): exponential growth. Infeasible for large n.
• O(n!) — Checking all permutations: factorial growth. The traveling salesman brute force.

Proof Techniques Every CS Person Should Know

Direct proof — Show P implies Q by a chain of valid logical steps. Used in algorithm correctness proofs.

Proof by contradiction — Assume the opposite is true, derive a contradiction. Classic example: proving √2 is irrational.

Proof by induction — Most important for CS. Prove a statement P(n) holds for all n:

1. Base case — Prove P(1) (or P(0)) is true
2. Inductive step — Assume P(k) is true; prove P(k+1) is true

This is the mathematical basis for recursion. When you write a recursive function, you're implicitly constructing an inductive proof that it works.

Number Theory: The Math Behind Cryptography

Number theory studies integers and their properties. Two concepts matter most for CS:

Modular arithmetic — "Clock arithmetic." a mod n is the remainder when a is divided by n. 17 mod 5 = 2. In code: a % n. Used in:

• Hash tables: bucket = hash(key) % table_size
• Cryptography: RSA, Diffie-Hellman key exchange, AES all operate in modular arithmetic
• Checksums and error detection

Greatest Common Divisor (GCD) — Euclid's algorithm (one of the oldest algorithms in existence) finds GCD in O(log n) time. Used in fraction simplification, cryptographic key generation, and RSA.

Frequently Asked Questions