Skip to main content
Logo image

Applied Discrete Structures

Appendix E Notation

The following table defines the notation used in this book. Page numbers or references refer to the first appearance of each symbol.
Symbol Description Location
\(x \in A\) \(x\) is an element of \(A\) Paragraph
\(x \notin A\) \(x\) is not an element of \(A\) Paragraph
\(\lvert A \rvert \) The number of elements in a finite set \(A\text{.}\) Definition 1.1.2
\(A \subseteq B\) \(A\) is a subset of \(B\text{.}\) Definition 1.1.3
\(\emptyset\) the empty set Paragraph
\(\{\:\}\) the empty set Paragraph
\(A \cap B\) The intersection of \(A\) and \(B\text{.}\) Definition 1.2.1
\(A \cup B\) The union of \(A\) and \(B\text{.}\) Definition 1.2.4
\(B - A\) The complement of \(A\) relative to \(B\) Definition 1.2.10
\(A^c\) The complement of set \(A\) relative to the universe. Definition 1.2.10
\(A\oplus B\) The symmetric difference of \(A\) and \(B\text{.}\) Definition 1.2.15
\(A \times B\) The cartesian product of \(A\) with \(B\text{.}\) Definition 1.3.1
\(\mathcal{P}(A)\) The power set of \(A\text{,}\) the set of all subsets of \(A\text{.}\) Definition 1.3.3
\(n!\) \(n\) factorial, the product of the first \(n\) positive integers Definition 2.2.5
\(\binom{n}{k}\) \(n\) choose \(k\text{,}\) the number of \(k\) element subsets of an \(n\) element set. Definition 2.4.3
\(p \land q\) the conjunction, \(p \textrm{ and } q\) Definition 3.1.3
\(p \lor q\) the disjunction, \(p \textrm{ or } q\) Definition 3.1.4
\(\neg p\) the negation of \(p\text{,}\) “not \(p\) Definition 3.1.5
\(p \to q\) The conditional proposition If \(p\) then \(q\text{.}\) Definition 3.1.6
\(p \leftrightarrow q\) The biconditional proposition \(p\) if and only if \(q\) Definition 3.1.12
\(1\) symbol for a tautology Definition 3.3.2
\(0\) symbol for a contradiction Definition 3.3.4
\(r \iff s\) \(r\) is logically equivalent to \(s\) Definition 3.3.6
\(r \Rightarrow s\) \(r\) implies \(s\) Definition 3.3.11
\(p \mid q\) the Sheffer Stroke of \(p\) and \(q\) Definition 3.3.14
\(\blacksquare\) Symbol that denotes the end of a proof. Can be replaced with QED Paragraph
\(T_p\) the truth set of \(p\) Definition 3.6.3
\((\exists n)_U(p(n))\) The statement that \(p(n)\) is true for at least one value of \(n\) Definition 3.8.1
\((\forall n)_U(p(n))\) The statement that \(p(n)\) is always true. Definition 3.8.3
\(\pmb{0}_{m\times n}\) the \(m\) by \(n\) zero matrix Item
\(I_{n}\) The \(n \times n\) identity matrix Definition 5.2.4
\(A^{-1}\) \(A\) inverse, the multiplicative inverse of \(A\) Definition 5.2.5
\(\det A\textrm{ or }\lvert A \rvert\) The determinant of \(A\text{,}\) 2 by 2 case Definition 5.2.7
\(a \mid b\) \(a\) divides \(b\text{,}\) or \(a\) divides evenly into \(b\) Definition 6.1.5
\(x s y\) \(x\) is related to \(y\) through the relation \(s\) Paragraph
\(r s\) the composition of relation \(r\) with relation \(s\) Definition 6.1.9
\([a]\) The equivalence class of a Definition 6.3.13
\(A/r\) Partition of \(A\) with respect to an equivalence relation \(r\) Definition 6.3.13
\(a \equiv_n b\) \(a\) is congruent to \(b\) modulo \(n\) Definition 6.3.15
\(a \equiv b (\textrm{mod } n)\) \(a\) is congruent to \(b\) modulo \(n\) Definition 6.3.15
\(r^+\) The transitive closure of \(r\) Definition 6.5.1
\(f:A \rightarrow B\) A function, \(f\text{,}\) from \(A\) into \(B\) Definition 7.1.1
\(B^A\) The set of all functions from \(A\) into \(B\) Definition 7.1.4
\(f(a)\) The image of \(a\) under \(f\) Definition 7.1.6
\(f(X)\) Range of function \(f:X \rightarrow Y\) Definition 7.1.7
\(\chi_S\) Characteristic function of the set \(S\) Exercise 7.1.5.4
\(\lvert A \rvert = n\) \(A\) has cardinality \(n\) Definition 7.2.7
\((g \circ f)(x) = g(f(x))\) The composition of \(g\) with \(f\) Definition 7.3.2
\(f \circ f = f^2\) the “square” of a function. Definition 7.3.5
\(i \textrm{ or } i_A\) The identity function (on a set \(A\)) Definition 7.3.8
\(f^{-1}\) The inverse of function \(f\) read “\(f\) inverse” Definition 7.3.11
\(log_b a\) Logarithm, base \(b\) of \(a\) Definition 8.4.4
\(\) Definition 8.5.1
\(S\uparrow\) \(S\) pop Definition 8.5.3
\(S\downarrow\) \(S\) push Definition 8.5.3
\(S*T\) Convolution of sequences \(S\) and \(T\) Definition 8.5.3
\(S\uparrow p\) Multiple pop operation on \(S\) Definition 8.5.6
\(S\downarrow p\) Multiple push operation on \(S\) Definition 8.5.6
\(K_n\) A complete undirected graph with \(n\) vertices Definition 9.1.10
\(deg(v), indeg(v), outdeg(v)\) degree, indegree and outdegree of vertex \(v\) Definition 9.1.30
\(e(v)\) The eccentricity of a vertex Paragraph
\(d(G)\) The diameter of graph \(G\) Paragraph
\(r(G)\) The radius of graph \(G\) Paragraph
\(C(G)\) The center of graph \(G\) Paragraph
\(Q_n\) the \(n\)-cube Definition 9.4.17
\(V(f)\) The value of flow \(f\) Definition 9.5.21
\(P_n\) a path graph of length \(n\) Definition 9.6.4
\(\chi(G)\) the chromatic number of \(G\) Definition 9.6.15
\(C_n\) A cycle with \(n\) edges. Definition 10.1.1
\(*\) generic symbol for a binary operation Definition 11.1.1
\(string1 + string2\) The concatenation of \(string1\) and \(string2\) Item a
\([G;*]\) a group with elements \(G\) and binary operation \(*\) Definition 11.2.3
\(\gcd(a,b)\) the greatest common divisor of \(a\) and \(b\) Definition 11.4.4
\(a +_n b\) the mod \(n\) sum of \(a\) and \(b\) Definition 11.4.12
\(a \times_n b\) the mod \(n\) product of \(a\) and \(b\) Definition 11.4.13
\(\mathbb{Z}_n\) The Additive Group of Integer Modulo \(n\) Definition 11.4.17
\(\mathbb{U}_n\) The Multiplicative Group of Integer Modulo \(n\) Definition 11.4.18
\(W \leq V\) \(W\) is a subsystem of \(V\) Definition 11.5.1
\(\langle a \rangle\) the cyclic subgroup generated by \(a\) Definition 11.5.6
\(ord(a)\) Order of a Definition 11.5.9
\(V_1\times V_2 \times \cdots \times V_n\) The direct product of algebraic structures \(V_1, V_2, \dots , V_n \) Definition 11.6.1
\(G_1 \times G_2\) The direct product of groups \(G_1\) and \(G_2\) Definition 11.6.3
\(G_1 \cong G_2\) \(G_1\) is isomorphic to \(G_2\) Definition 11.7.9
\(\) Definition 12.3.6
\(dim(V)\) The dimension of vector space \(V\) Definition 12.3.18
\(\pmb{0}\) least element in a poset Definition 13.1.7
\(\pmb{1}\) greatest element in a poset Definition 13.1.7
\(D_n\) the set of divisors of integer \(n\) Definition 13.1.9
\(a \lor b\) the join, or least upper bound of \(a\) and \(b\) Definition 13.2.1
\(a \land b\) the meet, or greatest lower bound of \(a\) and \(b\) Definition 13.2.1
\([L;\lor,\land]\) A lattice with domain having meet and join operations Definition 13.2.2
\(\bar{a}\) The complement of lattice element \(a\) Definition 13.3.6
\([B; \lor , \land, \bar{\hspace{5 mm}}]\) a boolean algebra with operations join, meet and complementation Definition 13.3.8
\(\) Definition 13.3.12
\(M_{\delta_1 \delta_2 \cdots \delta_k}\) the minterm generated by \(x_1, x_2, \ldots , x_k\text{,}\) where \(y_i=x_i\) if \(\delta_i = 1\) and \(y_i=\bar{x_i}\) if \(\delta_i = 0\) Definition 13.6.3
\(A^*\) The set of all strings over an alphabet \(A\) Definition 14.2.1
\(A^n\) The set of all strings of length \(n\) over an alphabet \(A\) Definition 14.2.1
\(\lambda\) The empty string Definition 14.2.1
\(s_1+s_2\) The concatenation of strings \(s_1\) and \(s_2\) Definition 14.2.4
\(L(G)\) Language created by phrase structure grammar \(G\) Definition 14.2.15
\((S, X, Z, w, t)\) A finite-state machine with states \(S\text{,}\) input alphabet \(X\text{,}\) output alphabet \(X\text{,}\) and output function \(w\) and next-state function \(t\) Definition 14.3.1
\(m(M)\) The machine of monoid \(M\) Definition 14.5.1
\(\) Definition 15.1.1
\(a*H, H*a\) the left and right cosets generated by \(a\) Definition 15.2.2
\(G/H\) The factor group G mod H. Definition 15.2.20
\(S_A\) The group of permutations of the set \(A\) Definition 15.3.5
\(S_n\) The group of permutations on a set with \(n\) elements Definition 15.3.5
\(A_n\) The Alternating Group Definition 15.3.18
\(\mathcal{D}_n\) The \(n\)th dihedral group Definition 15.3.26
\(H \triangleleft G\) \(H\) is a normal subgroup of \(G\) Definition 15.4.5
\(ker \theta\) the kernel of homomorphism \(\theta\) Definition 15.4.19
\(d_H(a,b)\) Hamming distance between \(a\) and \(b\) Definition 15.5.3
\([R; +, \cdot]\) a ring with domain \(R\) and operations \(+\) and \(\cdot\) Definition 16.1.1
\(U(R)\) the set of units of a ring \(R\) Definition 16.1.10
\(\) Definition 16.1.13
\(\) Definition 16.1.20
\(D\) a generic integral domain Definition 16.1.23
\(\textrm{deg }f(x)\) the degree of polynomial \(f(x)\) Definition 16.3.1
\(R[x]\) the set of all polynomials in \(x\) over \(R\) Definition 16.3.1
\(R[[x]]\) the set of all powers series in \(R\) Definition 16.5.1
\(\grave x, \acute x\) pre and post values of a variable \(x\) Definition A.2.1
\(M(A)_{i,j}\) The \(i, j\) minor of \(A\) Definition C.1.2
\(C(A)_{i,j}\) The \(i, j\) cofactor of \(A\) Definition C.1.4
\(\det(A) or \lvert A \rvert\) The determinant of \(A\) Definition C.1.6