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\) 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.10 |
| \(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 \uparrow q\) | NAND 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 |
| \(\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 |
| \(log_b a\) | Logarithm, base \(b\) of \(a\) | Definition 13.2.4 |
| \(S\uparrow\) | \(S\) pop | Definition 13.3.3 |
| \(S\downarrow\) | \(S\) push | Definition 13.3.3 |
| \(S*T\) | Convolution of sequences \(S\) and \(T\) | Definition 13.3.3 |
| \(S\uparrow p\) | Multiple pop operation on \(S\) | Definition 13.3.6 |
| \(S\downarrow p\) | Multiple push operation on \(S\) | Definition 13.3.6 |
| \(\grave x, \acute x\) | pre and post values of a variable \(x\) | Definition 14.2.1 |
| \(K_n\) | A complete undirected graph with \(n\) vertices | Definition 15.1.12 |
| \(deg(v), indeg(v), outdeg(v)\) | degree, indegree and outdegree of vertex \(v\) | Definition 15.1.29 |
| \(Q_n\) | the \(n\)-cube | Definition 15.4.17 |
| \(V(f)\) | The value of flow \(f\) | Definition 15.5.21 |
| \(P_n\) | Definition 15.6.4 | |
| \(\chi(G)\) | the chromatic number of \(G\) | Definition 15.6.14 |
| \(C_n\) | A cycle with \(n\) edges. | Definition 16.1.1 |
| \(\Sigma = \{0,1}\) | An alphabet with two elements, 0 and 1. | Definition 17.1.1 |
| \(a_1 a_2 \ldots a_n\) | A string with \(n\) symbols | Definition 17.1.3 |
| \(|x|\) | The length of string \(x\) | Definition 17.1.5 |
| \(xy\) | The concatenation of string \(x\) and string \(y\text{.}\) | Definition 17.1.6 |
| \(x^R\) | The reverse of string \(x\text{.}\) | Definition 17.1.7 |
| \(\Phi\) | A regular expression. | Definition 17.2.1 |
| \(L(r)\) | A language generated by regular expression \(r\text{.}\) | Definition 17.2.2 |
| \(\PRODUCES\) | Produces, as in \(A\PRODUCES ab\) | Paragraph |
| \(\YIELDS\) | Yields, as in \(x\YIELDS_G y.\)String \(y\) can be obtained from a string \(x\) by applying one production rule in \(G\) | Paragraph |
| \(\YIELDS_G^*\) | Yields in zero or more steps. | Paragraph |
