Formula sheet

Every formula from every topic. Type to filter.

🧠 Propositional & First-Order Logic

Rows in a truth table
2ⁿ for n variables
Boolean functions of n variables
2^(2ⁿ): 4 for n=1, 16 for n=2, 256 for n=3
Implication
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
Negating quantifiers
¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x)
Quantifier directions
∃y∀x P ⇒ ∀x∃y P (not conversely); ∀x(P∧Q) ≡ ∀xP ∧ ∀xQ; ∃x(P∨Q) ≡ ∃xP ∨ ∃xQ
Number of minterms of a formula
count of true rows; CNF has one clause per false row
Functionally complete sets
{¬,∧}, {¬,∨}, {¬,→}, {NAND}, {NOR}

🔗 Sets, Relations & Functions

Inclusion–exclusion
|A∪B∪C| = Σ|A| − Σ|A∩B| + |A∩B∩C|
Power set / product
|P(A)| = 2^|A|; |A × B| = |A|·|B|
Relations on an n-set
all 2^(n²), reflexive 2^(n²−n), symmetric 2^(n(n+1)/2)
Antisymmetric / asymmetric
2ⁿ·3^(n(n−1)/2) / 3^(n(n−1)/2)
Equivalence relations
Bell(n): 1, 2, 5, 15, 52, 203, …
Functions m → n
all nᵐ; injective n!/(n−m)!; onto n!·S(m,n)
Transitive closure
R⁺ = R ∪ R² ∪ … ∪ Rⁿ
Divisor lattice
D_n is Boolean iff n is squarefree; |D_n| = Π(eᵢ + 1)

🎲 Combinatorics & Recurrences

Permutations / combinations
P(n,r) = n!/(n−r)!; C(n,r) = n!/(r!(n−r)!)
Stars and bars
x₁+…+x_k = n, xᵢ ≥ 0: C(n+k−1, k−1); xᵢ ≥ 1: C(n−1, k−1)
Pigeonhole
⌈n/k⌉ in some box; k(m−1)+1 force m in one box
Derangements
Dₙ = n!(1 − 1/1! + 1/2! − …) = (n−1)(Dₙ₋₁ + Dₙ₋₂)
Euler totient
φ(n) = n Π (1 − 1/p) over primes p | n
Linear recurrence
r² = c₁r + c₂ ⇒ aₙ = A r₁ⁿ + B r₂ⁿ or (A + Bn) rⁿ
Catalan
Cₙ = C(2n,n)/(n+1) = Σ CᵢCₙ₋₁₋ᵢ
Bell / Stirling
Bₙ = Σ S(n,k); S(n,k) = k S(n−1,k) + S(n−1,k−1)

🕸️ Graph Theory

Handshake
Σ deg(v) = 2e; odd-degree vertices come in pairs
Edges
K_n: n(n−1)/2; K_{m,n}: mn; tree: n−1; r-regular: nr/2
Components
c ≥ n − e; forest: e = n − c; connected if e > C(n−1, 2)
Euler
circuit: all degrees even and connected; path: 0 or 2 odd vertices
Planar graph
v − e + f = 2; e ≤ 3v − 6; triangle-free e ≤ 2v − 4
Cayley
labelled trees on n vertices: n^(n−2)
Colouring
ω ≤ χ ≤ Δ + 1; bipartite ⇔ no odd cycle ⇔ χ ≤ 2
König / Gallai
bipartite: ν = τ; always α + τ = n

⭕ Groups & Algebraic Structures

Lagrange
|H| divides |G|; order of an element divides |G|
Cyclic group of order n
φ(n) generators; one subgroup per divisor of n
Order of aᵏ
n / gcd(n, k) in a cyclic group of order n
Units of ℤₙ
|ℤₙ*| = φ(n) = n Π(1 − 1/p)
Field test
ℤₙ is a field ⇔ n is prime
Group of prime order
cyclic, abelian, only trivial subgroups
Inverse of a product
(ab)⁻¹ = b⁻¹a⁻¹
Groups of small order
order 4: ℤ₄ or Klein; order 6: ℤ₆ or S₃