Chapter 1 — Formula Sheet

Conditional formsConverse: q→p | Contrapositive: ¬q→¬p (always ≡ p→q) | Inverse: ¬p→¬q

Key Logical Equivalences (all 10 laws)Identity: p∧T≡p, p∨F≡p | Domination: p∨T≡T, p∧F≡F | Idempotent: p∨p≡p, p∧p≡p
Double negation: ¬¬p≡p | Commutative: p∨q≡q∨p, p∧q≡q∧p | Associative: (p∨q)∨r≡p∨(q∨r)
Distributive: p∨(q∧r)≡(p∨q)∧(p∨r) | De Morgan's: ¬(p∧q)≡¬p∨¬q, ¬(p∨q)≡¬p∧¬q
Absorption: p∨(p∧q)≡p | Negation: p∨¬p≡T, p∧¬p≡F

De Morgan's Laws for Quantifiers¬∀xP(x)≡∃x¬P(x) ¬∃xP(x)≡∀x¬P(x)

Rules of Inference for Quantified StatementsUniversal Instantiation (UI): ∀xP(x)∴P(c) | Universal Generalization (UG): P(c) for arbitrary c∴∀xP(x)
Existential Instantiation (EI): ∃xP(x)∴P(c) for some c | Existential Generalization (EG): P(c)∴∃xP(x)

Proof Methods (quick reference)Direct: assume p, derive q | Contraposition: assume ¬q, derive ¬p | Contradiction: assume ¬p, derive a contradiction
Trivial: q already true | Vacuous: p already false | Cases: prove (p₁→q)∧⋯∧(pₙ→q) | Biconditional: prove p→q AND q→p

Number of rows in a truth table2ⁿ (n = number of propositional variables)

Chapter 2 — Formula Sheet

Boolean operationsSum: 1+1=1, 1+0=1, 0+0=0 | Product: 1·1=1, else 0 | Complement: 0̄=1, 1̄=0

Number of Boolean functions of degree n2^2ⁿ

Boolean Algebra Identities (all laws)Identity: x∨0=x, x∧1=x | Complement: x∨x̄=1, x∧x̄=0
Associative: (x∨y)∨z=x∨(y∨z), (x∧y)∧z=x∧(y∧z) | Commutative: x∨y=y∨x, x∧y=y∧x
Distributive: x∨(y∧z)=(x∨y)∧(x∨z), x∧(y∨z)=(x∧y)∨(x∧z)

Minterm / Sum-of-Products (Disjunctive Normal Form)A minterm is a product y₁y₂⋯yₙ (yᵢ=xᵢ or x̄ᵢ); the function = sum of the minterms for which it equals 1

Functionally complete sets{·, +, ‾}, {·, ‾}, {+, ‾}, {NAND} alone, {NOR} alone

Chapter 3 — Formula Sheet

Set operationsA∪B={x|x∈A∨x∈B} | A∩B={x|x∈A∧x∈B} | Ā={x∈U|x∉A} | A−B=A∩B̄

Cardinality of union (inclusion–exclusion)|A∪B| = |A| + |B| − |A∩B|

Power set size|P(A)| = 2^|A|

Function typesInjective: f(a)=f(b)→a=b | Surjective: ∀b∈B ∃a∈A, f(a)=b | Bijective: both (only bijections invert)

Composition(f∘g)(x) = f(g(x))

Geometric / Arithmetic progressionsGeometric: aₙ = arⁿ | Arithmetic: aₙ = a+dn

Summation formulasΣk = n(n+1)/2 | Σk² = n(n+1)(2n+1)/6 | Σk³ = n²(n+1)²/4
Σar^k = (arⁿ⁺¹−a)/(r−1) | Σ(k=0 to ∞)x^k = 1/(1−x), |x|<1 | Σ(k=1 to ∞)kx^k−1 = 1/(1−x)², |x|<1

Chapter 4 — Formula Sheet

Algorithm properties (checklist)Input · Output · Correctness · Finiteness · Effectiveness · Generality

Big-O|f(x)| ≤ C|g(x)| for all x > k

Big-Omega|f(x)| ≥ C|g(x)| for all x > k

Big-ThetaC₁|g(x)| ≤ |f(x)| ≤ C₂|g(x)| for all x > k (f is O(g) AND Ω(g))

Polynomial big-Oaₙxⁿ+⋯+a₀ is O(xⁿ) (leading term dominates)

Standard growth results1+2+⋯+n is O(n²) | n! is O(nⁿ) | log(n!) is O(n log n)

Combining functionsf₁ O(g₁), f₂ O(g₂) ⟹ (f₁+f₂) is O(max(|g₁|,|g₂|)) and (f₁f₂) is O(g₁g₂)

Chapter 5 — Formula Sheet

Mathematical Induction[P(1) ∧ ∀k(P(k)→P(k+1))] → ∀n P(n)Basis Step: show P(1). Inductive Step: assume P(k), show P(k+1).

Strong Induction[P(1)∧P(2)∧⋯∧P(k)] → P(k+1), for all kUse when P(k+1) may depend on more than just P(k).

Well-Ordering PropertyEvery nonempty set of nonnegative integers has a least elementEquivalent to both forms of induction above.

Recursive definition (general structure)Basis Step: define f(0) | Recursive Step: define f(n+1) in terms of f(0),...,f(n)

Sum of first n positive integers (proved by induction)1+2+⋯+n = n(n+1)/2

Fibonacci recurrencef₀=0, f₁=1, fₙ=fₙ₋₁+fₙ₋₂

Chapter 6 — Formula Sheet

Product / Sum / Subtraction / Division RulesProduct: n₁·n₂ (AND) | Sum: n₁+n₂ (OR, disjoint) | Subtraction: n₁+n₂−(common to both) | Division: n/d

Pigeonhole / Generalized Pigeonholek+1 objects, k boxes ⟹ some box has ≥2 | N objects, k boxes ⟹ some box has ≥⌈N/k⌉

Permutations (no repetition)P(n,r) = n!/(n−r)!

Combinations (no repetition)C(n,r) = n!/[r!(n−r)!] (Corollary: C(n,r)=C(n,n−r))

Permutations with repetitionnʳ

Combinations with repetitionC(n+r−1,r) = (n+r−1)!/[r!(n−1)!]

Binomial Theorem(x+y)ⁿ = Σⱼ C(n,j) xⁿ⁻ʲyʲ (Corollary: Σⱼ C(n,j) = 2ⁿ)

Pascal's IdentityC(n+1,k) = C(n,k−1) + C(n,k)

Chapter 7 — Formula Sheet

Recurrence relation (general form)aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ⋯ + cₖaₙ₋ₖ (+ F(n) if nonhomogeneous)

Characteristic equation (degree k)rᵏ − c₁rᵏ⁻¹ − c₂rᵏ⁻² − ⋯ − cₖ = 0

Degree-2, distinct rootsaₙ = α₁r₁ⁿ + α₂r₂ⁿ

Degree-2, repeated root r₀aₙ = α₁r₀ⁿ + α₂nr₀ⁿ

Arbitrary degree k, distinct rootsaₙ = α₁r₁ⁿ + α₂r₂ⁿ + ⋯ + αₖrₖⁿ

Arbitrary degree, repeated roots allowedEach root rᵢ (multiplicity mᵢ) contributes terms αᵢ,ⱼnʲrᵢⁿ for j=0,...,mᵢ−1

Nonhomogeneous general solutionaₙ = aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾ (particular + associated homogeneous solution)

Divide-and-conquer recurrencef(n) = a·f(n/b) + g(n)

Tower of Hanoi closed formHₙ = 2ⁿ − 1

Chapter 8 — Formula Sheet

Reflexive∀x[x∈A → (x,x)∈R]

Symmetric∀x∀y[(x,y)∈R → (y,x)∈R]

Antisymmetric∀x∀y[(x,y)∈R ∧ (y,x)∈R → x=y]

Transitive∀x∀y∀z[(x,y)∈R ∧ (y,z)∈R → (x,z)∈R]

Matrix M_R conditionsReflexive: diagonal all 1s | Symmetric: mᵢⱼ=mⱼᵢ | Antisymmetric: mᵢⱼ=0 or mⱼᵢ=0 (i≠j)

Composition & powers(x,z)∈S∘R if (x,y)∈R,(y,z)∈S for some y | R¹=R, Rⁿ⁺¹=Rⁿ∘R | R transitive ⟺ Rⁿ⊆R for all n

Equivalence relationReflexive + Symmetric + Transitive

Equivalence classesaRb ⟺ [a]=[b] ⟺ [a]∩[b]≠∅ (equivalence classes always partition the set)

Partial orderingReflexive + Antisymmetric + Transitive

Number of relations on an n-element set2^n²

Chapter 9 — Formula Sheet

Handshaking Theorem2m = Σ deg(v)Corollary: every undirected graph has an even number of odd-degree vertices.

Directed graph degree sumΣ deg⁻(v) = Σ deg⁺(v) = |E|

Special graphsKₙ: complete graph (n vertices, all pairs connected) | Cₙ: cycle | Wₙ: wheel | Qₙ: n-cube (2ⁿ vertices) | K_m,n: complete bipartite

Graph isomorphism invariantsSame # vertices, same # edges, same degree sequence (necessary but not sufficient for isomorphism)

ConnectivityConnected: path between every pair | Strongly connected (directed): path a→b AND b→a for every pair

Paths of length r via adjacency matrix(i,j) entry of Aʳ = number of paths of length r from vᵢ to vⱼ

Euler circuit conditionConnected AND every vertex has even degree

Euler path (non-circuit) conditionConnected AND exactly two vertices of odd degree

Hamilton path/circuitSimple path/circuit passing through every VERTEX exactly once (no simple universal test — see Dirac/Ore below)

Dirac's Theoremn≥3, deg(v)≥n/2 for all v ⟹ Hamilton circuit exists

Ore's Theoremn≥3, deg(u)+deg(v)≥n for nonadjacent u,v ⟹ Hamilton circuit exists

Chapter 10 — Formula Sheet

Tree definition & unique path propertyTree = connected + no simple circuits ⟺ unique simple path between every pair of vertices

Edges in a treeedges = n − 1 (n = number of vertices)

Vertices in a full m-ary tree (from internal vertices i)n = mi + 1

Full m-ary tree relationships (Theorem 4)From n vertices: i=(n−1)/m, l=[(m−1)n+1]/m | From i internal vertices: n=mi+1, l=(m−1)i+1
From l leaves: n=(ml−1)/(m−1), i=(l−1)/(m−1)

Level & heightLevel(v) = length of path from root to v (root = level 0) | Height = max level in the tree

Balanced tree conditionAll leaves at level h or h−1 (h = tree height)