CS202: Discrete Structures

Symbol

Description

x ∈ A

x is an element of A

x ∉ A

x is not an element of A

|A|

The number of elements in a finite set A

A ⊆ B

A is a subset of B

∅

The empty set

A ∩ B

The intersection of A and B

A ∪ B

The union of A and B

B − A

The complement of A relative to B

A^c

The complement of A relative to the universe

A ⊕ B

The symmetric difference of A and B

A × B

The cartesian product of A with B

$\wp (A)$

The power set of A, the set of all subsets of A

n!

n factorial, the product of the first n positive integers

$\binom{n}{k}$

n choose k, the number of k element subsets of a n set

p ∧ q

The conjunction, p and q

p ∨ q

The disjunction, p or q

¬p

The negation of p, “not p"

p → q

The conditional proposition If p then q

p ↔ q

The biconditional proposition p if and only if q

1

The symbol for a tautology

0

The symbol for a contradiction

r ⇐⇒ s

r is logically equivalent to s

r ⇒ s

r implies s

p | q

The Sheffer Stroke of p and q

T_p

The truth set of p

$(\exists n)\cup (p(n))$

The statement that p(n) is true for at least one value of n

$(\forall n)\cup (p(n))$

The statement that p(n) is always true

0_m × n

The m by n zero matrix

I_n

The n × n identity matrix

A⁻¹

A inverse, the multiplicative inverse of A

det A or |A|

The determinant of A, 2 by 2 case

a | b

a divides b, or a divides evenly into b

xsy

x is related to y through the relation s

rs

The composition of relation r with relation s

a ≡_n b

a is congruent to b modulo n

a ≡ b (mod n)

a is congruent to b modulo n

c(a)

the equivalence class of a under r

r+

The transitive closure of r

f : A → B

A function, f, from A into B

B^A

The set of all functions from A into B

f(a)

The image of a under f

f(X)

Range of function f : X → Y

|A| = n

A has cardinality n

(g ◦ f)(x) = g(f (x))

The composition of g with f

f ◦ f = f²

The "square" of a function

i or i_A

The identity function (on a set A)

f⁻¹

The inverse of function f, read "f inverse"

log_ba

Logarithm, base b of a

S ↑

S pop

S ↓

S push

S ∗ T

Convolution of sequences S and T

S ↑ p

Multiple pop operation on S

S ↓ p

Multiple push operation on S

K_n

A complete undirected graph with n vertices

deg(v), indeg(v), outdeg(v)

degree, indegree, and outdegree of vertex v

e(v)

The eccentricity of a vertex

d(G)

The diameter of graph G

r(G)

The radius of graph G

C (G)

The center of graph G

Q_n

The n-cube

V (f)

The value of flow f

P_n

A path graph of length n

$\chi (G)$

The chromatic number of G

C_n

A cycle with n edges

∗

The generic symbol for a binary operation

string1 + string2

The concatenation of string1 and string2

[G; ∗]

A group with elements G and binary operation

gcd(a, b)

The greatest common divisor of a and b

a +_n b

The mod n sum of a and b

a ×_n b

The mod n product of a and b

$\mathbb{Z}_n$

The Additive Group of Integer Modulo n

$\mathbb{U}_n$

The Multiplicative Group of Integer Modulo n

W ≤ V

W is a subsystem of V

⟨a⟩

The cyclic subgroup generated by a

ord(a)

Order of a

V₁ × V₂ × · · · × V_n

The direct product of algebraic structures V₁, V₂, ..., V_n

G₁ ≅ G₂

G₁ is isomorphic to G₂

dim(V)

The dimension of vector space V

0

The least element in a poset

1

The greatest element in a poset

D_n

The set of divisors of integer n

a ∨ b

The join, or least upper bound of a and b

a ∧ b

The meet, or greatest lower bound of a and b

[L; ∨, ∧]

A lattice with domain having meet and join operations

$\bar{a}$

The complement of lattice element a

[B; ∨, ∧, ¯ ]

A boolean algebra with operations join, meet, and complementation

$M_{\delta_1\delta_2...\delta_k}$

The minterm generated by $x_1,x_2,...,x_k$ where $y_i=x_i$ if $\delta_i=1$ and $y_i=\bar{x}_i$ if $\delta_i=0$

A^∗

The set of all strings over an alphabet A

A_n

The set of all strings of length n over an alphabet A

$\lambda$

The empty string

s₁ + s₂

The concatenation of strings s₁ and s₂

L(G)

Language created by phrase structure grammar

(S, X, Z, w, t)

A finite-state machine with states S, input alphabet X, output alphabet Z, output function w, and next-state function t

m(M)

The machine of monoid M

a ∗ H, H ∗ a

The left and right cosets generated by a

G/H

The factor group G mod H

S_A

The group of permutations of the set A

S_n

The group of permutations on a set with n elements

A_n

The Alternating Group

D_n

The nth dihedral group

H ◁ G

H is a normal subgroup of G

kerθ

The kernel of homomorphism θ

[R; +, ·]

A ring with domain R and operations + and ·

U (R)

The set of units of a ring R

D

A generic integral domain

deg f(x)

The degree of polynomial f(x)

R[x]

The set of all polynomials in x over R

R[[x]]

The set of all powers series in R

$\grave{x}, \acute{x}$

Pre and post values of a variable x

M(A)_i,j

The i, j minor of A

C(A)_i,j

The i, j cofactor of A

det(A) or |A|

The determinant of A