Skip to main content

Appendix C 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
\(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 difference of set \(B\) and set \(A\) or the complement of \(A\) relative to \(B\text{.}\) Definition 1.2.10
\(\overline{A}\) The complement of \(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 4.1.3
\( p \lor q\) the disjunction, \(p \textrm{ or } q\) Definition 4.1.4
\(\neg p\) the negation of \(p\text{,}\) “not \(p\)” Definition 4.1.5
\(p \to q\) The conditional proposition If \(p\) then \(q\text{.}\) Definition 4.1.6
\( p \leftrightarrow q\) The biconditional proposition \(p\) if and only if \(q\) Definition 4.1.11
\(1\) symbol for a tautology Definition 4.3.2
\(0\) symbol for a contradiction Definition 4.3.4
\( r \iff s\) \(r\) is logically equivalent to \(s\) Definition 4.3.6
\(r \Rightarrow s\) \(r\) implies \(s\) Definition 4.3.11
\(p \mid q\) the Sheffer Stroke of \(p\) and \(q\) Definition 4.3.14
\(T_p\) the truth set of \(p\) Definition 4.5.3
\((\exists n)_U(p(n))\) The statement that \(p(n)\) is true for at least one value of \(n\) Definition 4.6.1
\((\forall n)_U(p(n))\) The statement that \(p(n)\) is always true. Definition 4.6.3
\(\pmb{0}_{m\times n}\) the \(m\) by \(n\) zero matrix Item
\( I_{n}\) The \(n \times n\) identity matrix Definition 7.2.4
\(A^{-1}\) \(A\) inverse, the multiplicative inverse of \(A\) Definition 7.2.5
\(\det A\textrm{ or }\lvert A \rvert\) The determinant of \(A\) Definition 7.2.7
\(f:A \rightarrow B\) A function, \(f\text{,}\) from \(A\) into \(B\) Definition 8.1.1
\(B^A\) The set of all functions from \(A\) into \(B\) Definition 8.1.4
\(f(a)\) The image of \(a\) under \(f\) Definition 8.1.6
\(f(X)\) Range of function \(f:X \rightarrow Y\) Definition 8.1.7
\(\lvert A \rvert = n\) \(A\) has cardinality \(n\) Definition 8.2.7
\((g \circ f)(x) = g(f(x))\) The composition of \(g\) with \(f\) Definition 8.3.2
\(f \circ f = f^2\) the “square” of a function. Definition 8.3.5
\(i \textrm{ or } i_A\) The identitiy function (on a set \(A\)) Definition 8.3.8
\(f^{-1}\) The inverse of function \(f\) read “\(f\) inverse” Definition 8.3.11
\(a \mid b\) \(a\) divides \(b\text{,}\) or \(a\) divides evenly into \(b\) Definition 10.1.5
\(x R y\) \(x\) is related to \(y\) through the relation \(R\) Paragraph
\(r s\) the composition of relation \(R\) with relation \(S\) Definition 10.1.9
\(a \equiv_m b\) \(a\) is congruent to \(b\) modulo \(m\) Definition 10.3.13
\(a \equiv b (\textrm{mod } m)\) \(a\) is congruent to \(b\) modulo \(m\) Definition 10.3.13
\(c(a)\) the equivalence class of \(a\) under \(R\) Item 10.3.4.7.b
\(r^+\) The transitive closure of \(R\) Definition 10.5.1
\(\bullet \) generic symbol for a binary operation Definition 11.1.1
\(string1 + string2\) The concatenation of \(string1\) and \(string2\) Item a
\([G;\bullet ]\) a group with elements \(G\) and binary operation \(\bullet \) Definition 11.2.4
\(\gcd(a,b)\) the greatest common divisor of \(m\) and \(n\) Definition 11.4.4
\(a +_n b\) the mod \(n\) sum of \(m\) and \(n\) Definition 11.4.12
\(a \times_n b\) the mod \(n\) product of \(m\) and \(n\) Definition 11.4.13
\(\mathbb{Z}_n\) The Additive Group of Integer Modulo \(n\) Definition 11.4.16
\(\mathbb{U}_n\) The Multiplicative Group of Integer Modulo \(n\) Definition 11.4.17
\(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 \cong G_2\) \(G_1\) is isomorphic to \(G_2\) Definition 11.7.9
\(\pmb{0}\) least element in a poset Definition 12.1.7
\(\pmb{1}\) greatest element in a poset Definition 12.1.7
\(D_n\) the set of divisors of integer \(n\) Definition 12.1.9
\(a \lor b\) the join, or least upper bound of \(a\) and \(b\) Definition 12.2.1
\(a \land b\) the meet, or greatest lower bound of \(a\) and \(b\) Definition 12.2.1
\([L;\lor,\land]\) A lattice with domain having meet and join operations Definition 12.2.2
\(\bar{a}\) The complement of lattice element \(a\) Definition 12.3.6
\([B; \lor , \land, \bar{\hspace{5 mm}}]\) a Boolean algebra with operations disjunction, conjunction and complementation Definition 12.3.8
\(\) Definition 12.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 12.6.3
\(K_n\) A complete undirected graph with \(n\) vertices Definition 13.1.12
\(deg(v), indeg(v), outdeg(v)\) degree, indegree and outdegree of vertex \(v\) Definition 13.1.29
\(Q_n\) the \(n\)-cube Definition 13.4.17
\(V(f)\) The value of flow \(f\) Definition 13.5.21
\(\) Definition 13.6.1
\(P_n\) a path graph of length \(n\) Definition 13.6.4
\(\chi(G)\) the chromatic number of \(G\) Definition 13.6.14
\(C_n\) A cycle with \(n\) edges. Definition 14.1.1
\(A^*\) The set of all strings over an alphabet \(A\) Definition 15.2.1
\(A^n\) The set of all strings of length \(n\) over an alphabet \(A\) Definition 15.2.1
\(\lambda\) The empty string Definition 15.2.1
\(s_1+s_2\) The concatenation of strings \(s_1\) and \(s_2\) Definition 15.2.4
\(L(G)\) Language created by phrase structure grammar \(G\) Definition 15.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 15.3.1
\(m(M)\) The machine of monoid \(M\) Definition 15.4.5
\(log_b a\) Logarithm, base \(b\) of \(a\) Definition 16.2.4
\(\) Definition 16.3.1
\(S\uparrow\) \(S\) pop Definition 16.3.3
\(S\downarrow\) \(S\) push Definition 16.3.3
\(S*T\) Convolution of sequences \(S\) and \(T\) Definition 16.3.3
\(S\uparrow p\) Multiple pop operation on \(S\) Definition 16.3.6
\(S\downarrow p\) Multiple push operation on \(S\) Definition 16.3.6
\(\grave x, \acute x\) pre and post values of a variable \(x\) Definition 17.2.1