ListofSymbols.md

List of Symbols (Discrete Mathematics)

CS-113 Discrete Structures

Logic

• p ∨ q: p or q
• p ∧ q: p and q
• ¬ p, − p, p bar: not p
• p → q: if p, then q
• p ↔ q: p if and only if q
• P ≡ Q: P and Q are logically equivalent
• ∀: for all
• ∃: there exists
• ∴: therefore

Set Notation

• {x₁, ... , x_n}: set consisting of the elements x₁, ... , x_n
• {x | p(x)}: set consisting of those elements x satisfying property p(x)
• x ∈ X: x is an element of X
• x ∉ X: x is not an element of X
• X = Y: set equality (X and Y have the same elements)
• |X|: number of elements in X
• ∅: empty set
• X ⊆ Y: X is a subset of Y
• P(X): power set of X (all subsets of X)
• X ⋃ Y: X union Y (all elements in X or Y)
• i = 1 ⋃ n X_i: union of X₁, ... , X_n (All elements that belong to at least one of X₁, X₂, ... , X_n)
• i = ∞ ⋃ n X_i: union of X₁, X₂, ... , (All elements that belong to at least one of X₁, X₂, ...)
• ⋃ S: union of S (all elements that belong to at least one set in S)
• X ∩ Y: X intersect Y (all elements in X and Y)
• i = 1 ∩ n X_i: intersection of X₁, ... , X_n (All elements that belong to every one of X₁, X₂, ... , X_n)
• i = ∞ ∩ n X_i: intersection of X₁, X₂, ... , (All elements that belong to every one of X₁, X₂, ...)
• ∩ S: intersection of S (all elements that belong to at every set in S)
• X − Y: set difference (all elements in X but not in Y)
• X̄: complement of X (all elements not in X)
• (x, y): ordered pair
• (x₁, ... , x_n): n-tuple
• X × Y: Cartesian product of X and Y [pairs (x, y) with x in X and y in Y]

Relations

• xRy: (x, y) is in R (x is related to y by the relation R)
• [x]: equivalence class containing x
• R⁻¹: inverse relation (all (y, x) with (x, y) in R)
• R₂ ∘ R₁: composition of relations
• x ≼ y: xRy

Functions

• f(x): value assigned to x
• f: X → Y: function from X to Y
• f ∘ g: composition of f and g
• f⁻¹: inverse function (all (y, x) with (x, y) in f)
• f(n) = Ο(g(n)): |f(n)| ≤ C|g(n)| for n sufficiently large
• f(n) = Ω(g(n)): c|g(n)| ≤ |f(n)| for n sufficiently large
• f(n) = Θ(g(n)): c|g(n)| ≤ |f(n)| ≤ C|g(n)| for n sufficiently large

Counting

• C(n, r): number of r-combinations of an n-element set (n!/[(n − r)!r!])
• P(n, r): number of r-permutations of an n-element set (n(n − 1) ... (n − r + 1))

Graphs

• G = (V, E): graph G with vertex set V and edge set E
• (v, w): edge
• δ(v): degree of vertex v
• (v₁, ... , v_n): path from v₁ to v_n
• (v₁, ... , v_n): v₁ = v_n: cycle
• K_n: complete graph on n vertices
• K_{m, n}: complete bipartite graph on m and n vertices
• w(i, j): weight of edge (i, j)
• F_ij: flow in edge (i, j)
• C_ij: capacity of edge (i, j)
• (P, P̄): cut in a network

Probability

• P(x): probability of outcome x
• P(E): probability of event E
• P(E|F): conditional probability of E given F[P(E ∩ F)/P(F)]

Boolean Algebras and Circuits

• x ∨ y: x or y (1 if x or y is 1, 0 otherwise)
• x ∧ y: x and y (1 if x and y are 1, 0 otherwise)
• x ⊕ y: exclusive-OR of x and y (0 if x = y, 1 otherwise)
• x̄: not x (0 if x is 1, 1 if x is 0)
• x ↓ y: x NOR y (0 if x or y are 1, 1 otherwise)
• x ↑ y: x NAND y (0 if x and y are 1, 1 otherwise)
• Circuits:
  
  • More Information: ExtendedCircuits.png, Circuits.md, Circuit Symbols from Electronics Club

Strings, Grammars, and Languages

• λ: null string
• |s|: length of the string s
• st: concatenation of strings s and t (s followed by t)
• aⁿ: aa ... a (n a's)
• X^*: set of all strings over X
• X⁺: set of all nonnul strings over X
• α → β: production in a grammar
• α ⇒ β: β is derivable from α
• α₁ ⇒ α₂ ⇒ ... ⇒ α_n: derivation of α_n from α₁
• L(G): language generated by the grammar G
• S ::= T: Backus normal form (BNF)
• S ::= T₁ | T₂: S ::= T₁, S ::= T₂
• Ac(A): set off strings accepted by A

Matrices

• (a_ij): matrix with entries a_ij
• A = B: matrices A and B are equal (A and B are the same size and their corresponding entries are equal)
• A + B: matrix sum
• cA: scalar product
• − A: (−1)A
• A − B: A + (− B)
• AB: matrix product
• Aⁿ: matrix product AA ... A (n A's)

Miscellaneous

• lg x: logarithm to the base 2 of x
• ln x: natural logarithm of x (logarithm to the base e of x)
• m mod n: remainder when m is divided by n
• ⌊x⌋: floor of x (greatest integer less than or equal to x)
• ⌈x⌉: ceiling of x (smallest integer greater than or equal to x)
• b | a: b divides a
• b ∤ a: b does not divide a
• gcd(a, b): greatest common divisor of a and b
• n!: n factorial (n(n − 1) ... 2 ⋅ 1)
• f_n: n th Fibonacci number
• C_n: n th Catalan number
• i = m Σ n a_i: a_m + a_m+1 + ... + a_n
• i ∈ X Σ a_i: the sum of the elements in the set {a_i | i ∈ X}
• i = m ∏ n a_i: a_m ⋅ a_m+1 ⋅ ... ⋅ a_n
• i ∈ X ∏ a_i: the product of the elements in the set {a_i | i ∈ X}

Algorithm Notation

• x := y
  • assign the value y to x
• begin end
  • mark the beginning and end of a block of statements

• if p then
    action
  

  • if p is true, execute action

• if p then  
    action 1  
  else  
    action 2  
  

  • if p is true, execute action1; if p is false, execute action2
• //
  • a comment starts with // and continues to the end of the line
• return
  • suspend execution and return to invoker
• return(x)
  • suspend execution and return the value x to invoker

• while p do
    action
  

  • if p is true, execute action and repeat this process

• for var := init to limit do
    action
  

  • execute action for values of var from init to limit
• call proc(p1, ... , pk)
  • invoke procedure proc with arguments p1, ... , pk