Logic and Algorithms - Symbol Definitions

∧

AND (conjunction) — P ∧ Q is true only when both P and Q are true

∨

OR (disjunction) — P ∨ Q is true when at least one of P or Q is true

¬

NOT (negation) — flips the truth value of P; also written ~P

→

Implies (conditional) — "if P then Q"; false only when P is true and Q is false

↔

If and only if (biconditional) — true when P and Q have the same truth value

⊕

XOR (exclusive or) — true when exactly one of P, Q is true, not both

∀

For all (universal quantifier) — ∀x P(x) means P(x) holds for every x in the domain

∃

There exists (existential quantifier) — ∃x P(x) means at least one x makes P(x) true

∃!

There exists exactly one — exactly one x satisfies P(x)

⊨

Models / satisfies — A ⊨ P means A makes P true (semantic entailment)

⊢

Proves (syntactic turnstile) — A ⊢ P means P is derivable from A using proof rules

≡

Logical equivalence — P and Q have the same truth table; interchangeable in any formula

⊤

Tautology — always true regardless of variable assignments

⊥

Contradiction — always false regardless of variable assignments

∈

Element of — x ∈ S means x is a member of set S; ∉ means not a member

⊆

Subset of — every element of A is also in B; ⊂ means proper subset (A ≠ B)

∪

Union — all elements in A, in B, or in both

∩

Intersection — only elements that appear in both A and B

Set difference — A \ B is elements in A that are not in B; also written A − B

Aᶜ

Complement — all elements in the universal set U that are not in A; also written Ā

∅

Empty set — the set with no elements; note {∅} is not empty

𝒫(S)

Power set — set of all subsets of S; if |S| = n then |𝒫(S)| = 2ⁿ

|S|

Cardinality — number of elements in S; for infinite sets, compared via bijections

A × B

Cartesian product — set of all ordered pairs (a, b) where a ∈ A, b ∈ B

ℤ

Integers — {…, −2, −1, 0, 1, 2, …}; ℤ⁺ = positive integers only

ℕ

Natural numbers — {0, 1, 2, …} or {1, 2, 3, …} depending on convention

ℚ

Rational numbers — all numbers expressible as p/q where p, q ∈ ℤ and q ≠ 0

ℝ

Real numbers — all points on the number line; uncountably infinite

f: A→B

Function notation — f maps every element of domain A to exactly one element of codomain B

O(·)

Big-O (upper bound) — f grows no faster than g in the worst case; e.g. O(n log n)

Ω(·)

Big-Omega (lower bound) — f grows at least as fast as g; describes a complexity floor

Θ(·)

Big-Theta (tight bound) — f grows exactly like g; both O(g) and Ω(g)

o(·)

Little-o (strict upper bound) — f grows strictly slower than g; f/g → 0

log n

Logarithm — in algorithms, base 2 (lg) by default; appears in divide-and-conquer runtimes

⌊x⌋

Floor — rounds x down to the nearest integer; ⌊3.9⌋ = 3

⌈x⌉

Ceiling — rounds x up to the nearest integer; ⌈3.1⌉ = 4

T(n)

Runtime / recurrence — running time on input size n; e.g. T(n) = 2T(n/2) + n

Σ

Sigma (summation) — Σᵢ₌₁ⁿ f(i) adds f(i) for every i from 1 to n

Π

Pi (product) — Πᵢ₌₁ⁿ f(i) multiplies f(i) for every i from 1 to n

n!

Factorial — n × (n−1) × … × 1; counts arrangements; 0! = 1 by definition

P(n,r)

r-permutation — n!/(n−r)!; ordered selections of r items from n; order matters

C(n,r)

r-combination ("n choose r") — n!/(r!(n−r)!); unordered selections of r from n

(n r)

Binomial coefficient — same as C(n,r); appears in Pascal's triangle and the binomial theorem

2ⁿ

Subsets of an n-element set — also the number of n-bit strings

∴

Therefore — marks the conclusion of a logical argument

∵

Because — marks the justification or reason for a step

□ / QED

End of proof — signals the proof is complete; also written ■ or ∎

a | b

Divides — a divides b evenly; ∃k ∈ ℤ such that b = a·k; not a fraction

a ∤ b

Does not divide — no integer k satisfies b = a·k

a ≡ b (mod m)

Congruence mod m — a and b have the same remainder when divided by m

gcd(a,b)

Greatest common divisor — largest integer dividing both a and b; gcd(12,8) = 4

lcm(a,b)

Least common multiple — smallest positive integer divisible by both a and b; lcm(4,6) = 12

⟹

Implies (proof writing) — one statement directly follows from another in an active deduction step

WLOG

Without loss of generality — one case covers all symmetric cases by symmetry

IH

Inductive hypothesis — the assumption made in an induction proof (P(k) or all P(i) for base ≤ i ≤ k)