 # Applied Discrete Structures

## AppendixENotation

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
$$\mathbb{P}$$ the positive integers Item
$$\mathbb{N}$$ the natural numbers Item
$$\mathbb{Z}$$ the integers Item
$$\mathbb{Q}$$ the rational numbers Item
$$\mathbb{R}$$ the real numbers Item
$$\mathbb{C}$$ the complex numbers Item
$$\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 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
$$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
 Definition 9.6.1
$$P_n$$ a path graph of length $$n$$ Definition 9.6.4
$$\chi(G)$$ the chromatic number of $$G$$ Definition 9.6.14
$$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