Graphs, Number Theory & Algebra
Discrete Mathematics Formula Sheet
Every rule, law and formula from Discrete Mathematics on one page — logic, proofs, sets, relations, functions, counting, recurrences, graphs, trees, number theory and Boolean algebra.
Logic
| Concept | Formula |
|---|---|
| Implication | p → q ≡ ¬p ∨ q ≡ ¬q → ¬p |
| Negated implication | ¬(p → q) ≡ p ∧ ¬q |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Quantifier negation | ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x) |
| Modus ponens / tollens | p, p → q ⊢ q; ¬q, p → q ⊢ ¬p |
Proof methods
Direct · contrapositive · contradiction · cases · counterexample · induction (base + step) · strong induction.
Sets and functions
| Concept | Formula |
|---|---|
| Power set | |P(A)| = 2ⁿ |
| Cartesian product | |A × B| = |A|·|B| |
| Inclusion–exclusion (2 sets) | |A ∪ B| = |A| + |B| − |A ∩ B| |
| Inclusion–exclusion (3 sets) | Σ|A| − Σ|A ∩ B| + |A ∩ B ∩ C| |
| Functions A → B | nᵐ (m = |A|, n = |B|) |
| Injections (m ≤ n) | n!/(n − m)! |
| Bijections | n! |
Relations
| Type | Properties |
|---|---|
| Equivalence relation | reflexive, symmetric, transitive → partitions into classes |
| Partial order | reflexive, antisymmetric, transitive → Hasse diagram |
| Lattice | every pair has a lub (join) and glb (meet) |
Counting
| Situation | Count |
|---|---|
| Ordered, no repetition | P(n, r) = n!/(n − r)! |
| Ordered, with repetition | nʳ |
| Unordered, no repetition | C(n, r) = n!/(r!(n − r)!) |
| Unordered, with repetition | C(n + r − 1, r) |
| Arrangements with identical items | n!/(n₁! n₂! … nₖ!) |
| Circular arrangements | (n − 1)! |
| Derangements | Dₙ = n! Σ (−1)ᵏ/k! ≈ n!/e |
| Pigeonhole | N objects, k boxes → some box has ≥ ⌈N/k⌉ |
| Binomial theorem | (x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ |
| Pascal's rule | C(n, r) = C(n − 1, r − 1) + C(n − 1, r) |
Recurrences
| Characteristic roots | Solution of aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ |
|---|---|
| distinct r₁, r₂ | aₙ = αr₁ⁿ + βr₂ⁿ |
| repeated r | aₙ = (α + βn)rⁿ |
| Fibonacci | Fₙ = (φⁿ − ψⁿ)/√5 |
Graphs and trees
| Fact | Formula |
|---|---|
| Handshake lemma | Σ deg(v) = 2|E| |
| Edges of Kₙ | n(n − 1)/2 |
| Euler circuit | connected, all degrees even |
| Euler path | connected, exactly two odd vertices |
| Euler's formula (planar) | V − E + F = 2; E ≤ 3V − 6 |
| Tree | n vertices, n − 1 edges, unique paths |
| Full m-ary tree | n = mi + 1, l = (m − 1)i + 1 |
| Cayley | nⁿ⁻² labelled trees |
| Four colour theorem | planar graphs: χ ≤ 4 |
Number theory
| Fact | Formula |
|---|---|
| Division algorithm | a = dq + r, 0 ≤ r < d |
| Euclid | gcd(a, b) = gcd(b, a mod b) |
| GCD–LCM | gcd(a, b)·lcm(a, b) = ab |
| Bézout | gcd(a, b) = sa + tb |
| Inverse exists | a⁻¹ mod m ⇔ gcd(a, m) = 1 |
| Fermat | aᵖ⁻¹ ≡ 1 (mod p), p prime, p ∤ a |
Boolean algebra
| Law | Identity |
|---|---|
| Absorption | x + xy = x; x(x + y) = x |
| De Morgan | (x + y)′ = x′y′; (xy)′ = x′ + y′ |
| Consensus | xy + x′z + yz = xy + x′z |
| Functionally complete | {NAND} or {NOR} alone |
Final check: mixed revision
4 questions · pick an answer to check it instantly
- 1
Which is logically equivalent to ¬(p → q)?
An implication is false exactly when p is true and q is false. - 2
How many ways can 4 people be seated at a round table?
(n − 1)! = 3! = 6. - 3
Solve aₙ = 4aₙ₋₂ with a₀ = 0, a₁ = 4.
Roots ±2: α + β = 0 and 2α − 2β = 4 give α = 1, β = −1. - 4
A connected planar graph has 6 vertices and 9 edges. How many faces?
6 − 9 + F = 2 → F = 5.