Discrete Mathematics Tutorial: Learn Math from Scratch (2026)
Discrete mathematics is the mathematical language of computer science. Unlike calculus (which deals with continuous quantities), discrete math studies countable, distinct structures — integers, graphs, logical statements, and finite sets. My experience teaching and applying discrete math in algorithm design, cryptography, and formal verification has shown me that its concepts reappear across every CS subfield. This tutorial covers logic, set theory, combinatorics, graph theory, recurrence relations, and algebraic structures.
We emphasize both theoretical foundations and computational applications: how propositional logic drives digital circuits, combinatorics quantifies algorithm complexity, graph theory models networks, and recurrence relations analyze recursive algorithms.
Propositional and Predicate Logic
Propositional logic deals with statements that are true or false, connected by logical operators: not, and, or, implies, and equivalence. Truth tables define the semantics of each operator. A tautology is always true, a contradiction always false. Predicate logic extends propositions with quantifiers: universal (for all) and existential (there exists), and predicates over variables. Logical equivalence and implication are used in program verification — Hoare logic uses preconditions and postconditions to reason about program correctness.
from itertools import product
def truth_table(variables, expr):
print(" ".join(variables) + " | Result")
print("-" * 15)
for vals in product([True, False], repeat=len(variables)):
env = dict(zip(variables, vals))
result = eval(expr, {"__builtins__": {}}, env)
row = " ".join(str(int(env[v])) for v in variables)
print(f"{row} | {int(result)}")
# De Morgan: not (P and Q) == (not P) or (not Q)
truth_table(['P', 'Q'], "not (P and Q) == (not P) or (not Q)")Set Theory and Functions
A set is a well-defined collection of distinct objects. Operations include union, intersection, difference, complement, and Cartesian product. The power set is the set of all subsets. Functions map elements from a domain to a codomain, classified as injective (one-to-one), surjective (onto), or bijective (both). Cardinality compares set sizes — Cantor's diagonal argument proves that real numbers are uncountably infinite. In computer science, sets model database relations, access control lists, and type systems.
def set_operations(A, B):
return {
"union": A | B,
"intersection": A & B,
"diff A-B": A - B,
"sym_diff": A ^ B,
"A_subset_B": A.issubset(B),
"A_superset_B": A.issuperset(B)
}
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
# Result: union={1,2,3,4,5,6}, intersection={3,4}
from itertools import chain, combinations
def powerset(s):
return list(chain.from_iterable(
combinations(s, r) for r in range(len(s)+1)))
# powerset({1,2}) -> [(), (1,), (2,), (1,2)]Combinatorics: Permutations and Combinations
Combinatorics counts arrangements and selections of objects. Permutations count ordered arrangements: P(n,k) = n! / (n-k)!. Combinations count unordered selections: C(n,k) = n! / (k!(n-k)!) also written as the binomial coefficient. The pigeonhole principle states that if n items are placed into m containers and n > m, at least one container holds more than one item. The inclusion-exclusion principle computes the size of unions of overlapping sets. These tools are essential for probability calculations and analyzing algorithm worst-case bounds.
import math
def permutations(n, k):
return math.factorial(n) // math.factorial(n - k)
def combinations(n, k):
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
def binomial_coefficient(n, k):
# Pascal's triangle recurrence: C(n,k) = C(n-1,k-1) + C(n-1,k)
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)
# C(5,2) = 10, P(5,2) = 20Graph Theory Fundamentals
A graph G = (V,E) consists of vertices and edges. Graphs can be directed or undirected, weighted or unweighted. Key properties include degree (number of incident edges), paths, cycles, connectivity, and planarity. Eulerian paths traverse every edge exactly once; Hamiltonian paths visit every vertex exactly once. A tree is a connected acyclic graph with |V|-1 edges. Bipartite graphs partition vertices into two sets with edges only crossing between sets. Graph coloring assigns colors to vertices such that adjacent vertices have different colors — the four color theorem states that any planar graph is 4-colorable.
from collections import defaultdict
class Graph:
def __init__(self):
self.adj = defaultdict(list)
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
def is_bipartite(self):
color = {}
for start in self.adj:
if start not in color:
queue = [start]
color[start] = 0
while queue:
v = queue.pop(0)
for nb in self.adj[v]:
if nb not in color:
color[nb] = 1 - color[v]
queue.append(nb)
elif color[nb] == color[v]:
return False
return True
# Complete bipartite graph K_{2,3} has chromatic number 2Recurrence Relations
Recurrence relations define sequences where each term depends on previous terms. The Fibonacci sequence F(n) = F(n-1) + F(n-2) with F(0)=0, F(1)=1 is the classic example. Solving recurrences determines closed-form complexity — the Master Theorem provides solutions for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n). Linear recurrences with constant coefficients can be solved by finding characteristic equation roots. Recurrences appear throughout algorithm analysis: binary search T(n) = T(n/2) + O(1) = O(log n), merge sort T(n) = 2T(n/2) + O(n) = O(n log n).
# Master Theorem solver
def master_theorem(a, b, f_n_power):
import math
log_b_a = math.log(a, b)
if f_n_power < log_b_a:
return f"Theta(n^{log_b_a:.2f})"
elif f_n_power == log_b_a:
return f"Theta(n^{log_b_a:.2f} * log n)"
else:
return f"Theta(n^{f_n_power:.2f})"
# Merge sort: a=2, b=2, f(n)=n -> log_2(2)=1, f(n) power=1 -> equal
print(master_theorem(2, 2, 1)) # Theta(n log n)
# Binary search: a=1, b=2, f(n)=1 -> log_2(1)=0, f(n) power=0 -> equal
print(master_theorem(1, 2, 0)) # Theta(log n)Algebraic Structures: Groups, Rings, Fields
Algebraic structures define sets with operations satisfying specific axioms. A group (G, *) has closure, associativity, identity, and inverses. An abelian group also has commutativity. A ring adds a second operation (addition and multiplication) with distributivity. A field is a ring where every non-zero element has a multiplicative inverse — the real numbers and integers modulo a prime are fields. Finite fields (Galois fields) are fundamental to cryptography (AES uses GF(2^8)), error-correcting codes, and checksum algorithms like CRC.
# Modular arithmetic and finite field GF(p)
class GaloisField:
def __init__(self, p):
self.p = p # must be prime
def add(self, a, b):
return (a + b) % self.p
def mul(self, a, b):
return (a * b) % self.p
def inv(self, a):
# Extended Euclidean algorithm for modular inverse
if a == 0:
raise ZeroDivisionError
t, new_t = 0, 1
r, new_r = self.p, a
while new_r != 0:
quotient = r // new_r
t, new_t = new_t, t - quotient * new_t
r, new_r = new_r, r - quotient * new_r
return t % self.p
GF_23 = GaloisField(23)
print(GF_23.inv(3)) # 3 * 8 = 24 ≡ 1 mod 23, so inverse is 8Frequently Asked Questions
Why is discrete mathematics important for computer science?
Computers store discrete values (bits), not continuous quantities. Discrete math provides the theoretical foundation for algorithms, data structures, cryptography, network analysis, formal verification, and type theory.
What is the difference between permutations and combinations?
Permutations consider order (arrangements of items in sequence). Combinations ignore order (selections of subsets). For example, choosing 3 people from 5: 10 combinations (C(5,3)), but 60 permutations (P(5,3)) if order matters.
How does graph theory apply to real-world problems?
Graph theory models social networks (Facebook friend graphs), navigation (shortest path in road networks), dependency resolution (package managers), circuit design, scheduling (graph coloring for register allocation), and network flow (max flow = min cut).
What is the practical use of the Master Theorem?
The Master Theorem solves divide-and-conquer recurrences T(n) = aT(n/b) + f(n) without expanding the recurrence. It immediately classifies complexity as one of three cases based on comparing f(n) with n^{log_b(a)}.
Originally published on Ayodhyyya. Last updated June 1, 2026.