Mathematics for Computer Science (Translation) - inzkyk.xyz

Source: https://inzkyk.xyz/mcs/

Mathematics for Computer Science

About This Book (https://inzkyk.xyz/mcs/#%e6%9c%ac%e6%9b%b8%e3%81%ab%e3%81%a4%e3%81%84%e3%81%a6)

This book, Mathematics for Computer Science, is a translation of Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer (https://courses.csail.mit.edu/6.042/spring18/index.shtml). The original is published under the Creative Commons Attribution-ShareAlike 3.0 license (https://creativecommons.org/licenses/by-sa/3.0/).

This translation is published under the Creative Commons Attribution-ShareAlike 3.0 license.

This translation is published under the Creative Commons Attribution-ShareAlike 3.0 license.

If you redistribute or reuse this translation, please include a link to https://inzkyk.xyz/mcs/ as attribution in your description, etc.

Acknowledgments (https://inzkyk.xyz/mcs/#%e8%ac%9d%e8%be%9e)

We thank the authors of the original Mathematics for Computer Science: Eric Lehman, F. Thomson Leighton, and Albert R. Meyer.

Symbol Table (https://inzkyk.xyz/mcs/#%e8%a8%98%e5%8f%b7%e9%9b%86)

\[\def\arraystretch{1.35}\begin{array}{ll} \hspace{25pt} Symbol & \hspace{120pt} Meaning \\ \hline ::= & \text{ Defined as \(\cdots\)}, Equal by definition to \(\cdots\) \\ \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{ Defined to be equivalent to \(\cdots\)}, Equivalent by definition to \(\cdots\) \\ \neq & \text{ Not equal (negation of equality)} \\ ■ & \text{[\href{/mcs/proofs/what_is_a_proof/proving_an_implication/#subsection-1-5-1}{\text{Section 1.5.1}}] \{\small Q.E.D.\} (end of proof)} \\ \wedge & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{Section 3.1}}] {\footnotesize AND}, and} \\ \vee & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{Section 3.1}}] {\footnotesize OR}, or} \\ \longrightarrow & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{Section 3.1}}] {\footnotesize IMPLIES}, implies} \\ p \longrightarrow q & \text{[\href{/mcs/proofs/state_machines/states_and_transitions/#}{\text{Section 6.1}}] transition from state \(p\) to state \(q\)} \\ \lnot P, \overline{\mathstrut P} & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{Section 3.1}}] {\footnotesize NOT} \hspace{-4pt} (P), not \(P\)} \\ \longleftrightarrow & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{Section 3.1}}] {\footnotesize IFF}, if and only if, equivalent} \\ \otimes & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{Section 3.1}}] {\footnotesize XOR}}, exclusive or} \\ \exists & \text{[\href{/mcs/proofs/logical_formulas/predicate_formulas/#}{\text{Section 3.6}}] there exists \(\cdots\) satisfying the condition} \\ \forall & \text{[\href{/mcs/proofs/logical_formulas/predicate_formulas/#}{\text{Section 3.6}}] for all \(\cdots\), the condition holds} \\ \in & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{Section 4.1}}] is an element of, belongs to} \\ \subseteq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{Section 4.1}}] is a subset (including equality)} \\ \not \subseteq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{Section 4.1}}] is not a subset (negation of \(\subseteq\))} \\ \subsetneq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{Section 4.1}}] is a proper subset (subset and not equal)} \\ \not \subsetneq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{Section 4.1}}] is not a proper subset (negation of \(\subsetneq\))} \\ \cup & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/sets/#def-4-1-1}{4.1.1}] union} \\ \bigcup_{i \in I} S_{i} & \text{union of the family of sets \(S_{i}\) where the index \(i\) ranges over \(I\)} \\ \cap & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/sets/#def-4-1-1}{4.1.1}] intersection} \\ \bigcap_{i \in I} S_{i} & \text{intersection of the family of sets \(S_{i}\) where the index \(i\) ranges over \(I\)} \\ \varnothing & \text{empty set \(\left\{ \, \right\}\)} \\ \overline{\mathstrut A} & \text{complement of set \(A\)} \\ A - B & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/sets/#def-4-1-1}{4.1.1}] set difference: the set \(A\) with elements of \(B\) removed} \\ \operatorname{pow} (A) & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#subsection-4-1-3}{\text{Section 4.1.3}}] power set of \(A\)} \\ A \times B & \text{[\href{/mcs/proofs/mathematical_data_types/sequences/#}{\text{Section 4.2}}] Cartesian product of sets \(A\) and \(B\)} \\ S^{n} & \text{Cartesian product of \(n\) copies of set \(S\): \(S \times S \times \cdots \times S\)} \\ \mathbb{Z} & \text{set of all integers} \\ \mathbb{N}, \mathbb{Z}^{\geq 0} & \text{set of nonnegative integers} \\ \mathbb{Z}^{+}, \mathbb{N}^{+} & \text{set of positive integers} \\ \mathbb{Z}^{-} & \text{set of negative integers} \\ \mathbb{Q} & \text{set of rational numbers} \\ \mathbb{R} & \text{set of real numbers} \\ \mathbb{C} & \text{set of complex numbers} \\ \left\lfloor r \right\rfloor & \text{floor function value for real \(r\): the greatest integer less than or equal to \(r\)} \\ \left\lceil r \right\rceil & \text{ceiling function value for real \(r\): the smallest integer greater than or equal to \(r\)} \\ \left| r \right| & \text{absolute value of real \(r\)} \\ R(X) & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-4}{4.4.4}] image of set \(X\) under binary relation \(R\)} \\ R^{-1} & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-5}{4.4.5}] inverse of binary relation \(R\)} \\ R^{-1}(X) & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-6}{4.4.6}] inverse image of set \(X\) under binary relation \(R\)} \\ A \mathrel{\text{\small surj}} B & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/finite_cardinality/#def-4-5-2}{4.5.2}] \(\ \overset{\text{def}}{\longleftrightarrow}\) there exists a surjective function \(f \colon A \to B\)} \\ A \mathrel{\text{\small inj}} B & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/finite_cardinality/#def-4-5-2}{4.5.2}] \(\ \overset{\text{def}}{\longleftrightarrow}\) there exists a total injective function \(f \colon A \to B\)} \\ A \mathrel{\text{\small bij}} B & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/finite_cardinality/#def-4-5-2}{4.5.2}] \(\ \overset{\text{def}}{\longleftrightarrow}\) there exists a bijection \(f \colon A \to B\)} \\ [\text{内} \leq 1] & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] injective condition of a binary relation} \\ [\text{内} \geq 1] & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] surjective condition of a binary relation} \\ [\text{外} \leq 1] & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] function condition of a binary relation} \\ [\text{外} \geq 1] & \text{[\text{Definition }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] bijective condition of a binary relation} \\ R \circ S & \text{[\href{/mcs/proofs/mathematical_data_types/exercise/#problem-4-29}{Problem 4.29}, \text{Definition }\href{/mcs/structures/directed_graphs_and_partial_orders/walk_relations/#def-10-4-2}{10.4.2}] composition of binary relations \(R\) and \(S\)} \\ \lambda & \text{empty string or list of length \(0\)} \\ A^{\ast} & [\text{Definition }\href{/mcs/proofs/recursive_data_types/recursive_definitions_and_structural_induction/#def-7-1-1}{7.1.1}] \text{set of all finite-length strings over alphabet \(A\)} \\ A^{\omega} & \text{set of all infinite-length strings over alphabet \(A\)} \\ \operatorname{rev}(s) & \text{[\href{/mcs/proofs/recursive_data_types/exercise/#problem-7-3}{Problem 7.3}] reversal of string \(s\)} \\ s \cdot t & \text{[\text{Definition }\href{/mcs/proofs/recursive_data_types/recursive_definitions_and_structural_induction/#def-7-1-3}{7.1.3}] concatenation of strings \(s\) and \(t\), \(\operatorname{append}(s,t)\)} \\ \#_{c}(s) & \text{[\text{Definition }\href{/mcs/proofs/recursive_data_types/strings_of_matched_brackets/#def-7-2-2}{7.2.2}] number of occurrences of character \(c\) in string \(s\)} \\ m \; | \; n & \text{[\text{Definition }\href{/mcs/structures/number_theory/divisibility/#def-9-1-1}{9.1.1}] \(m\) divides \(n\), \(\, \overset{\text{def}}{\longleftrightarrow}\ \exists k \in \mathbb{Z}.\, km = n\)} \\ \operatorname{gcd}(a, b) & \text{[\href{/mcs/structures/number_theory/greatest_common_divisor/#}{\text{Section 9.2}}] greatest common divisor of integers \(a\) and \(b\)} \\ \operatorname{lcm}(a, b) & \text{least common multiple of integers \(a\) and \(b\)} \\ \log x & \text{base-2 logarithm of \(x\), \(\log_{2} x\)} \\ \ln x & \text{natural logarithm of \(x\), \(\log_{e} x\)} \\ [k..n] & \text{\(\left\{ i \; | \; k \leq i \leq n \right\}\)} \\ (k..n] & \text{\([k..n] - \left\{ k \right\}\)} \\ [k..n) & \text{\([k..n] - \left\{ n \right\}\)} \\ (k..n) & \text{\([k..n] - \left\{ k, n \right\}\)} \\ \sum_{i \in I} r_{i} & \text{sum of the values represented by \(r_{i}\) where index \(i\) ranges over \(I\)} \\ \prod_{i \in I} r_{i} & \text{product of the values represented by \(r_{i}\) where index \(i\) ranges over \(I\)} \\ \operatorname{qcnt}(n,d) & \text{[\href{/mcs/structures/number_theory/divisibility/#}{\text{Section 9.1}}] quotient when dividing \(n\) by \(d\)} \\ \operatorname{rem}(n,d) & \text{[\href{/mcs/structures/number_theory/divisibility/#}{\text{Section 9.1}}] remainder when dividing \(n\) by \(d\)} \\ a \equiv b \ \ (\text{mod } n) & \text{[\href{/mcs/structures/number_theory/modular_arithmetic/#}{\text{Section 9.6}}] \(a\) is congruent to \(b\) modulo \(n\)} \\ a \not \equiv b \ \ (\text{mod } n) & \text{[\href{/mcs/structures/number_theory/modular_arithmetic/#}{\text{Section 9.6}}] \(a\) is not congruent to \(b\) modulo \(n\) (negation of \(\equiv\))} \\ \mathbb{Z}_{n} & \text{[\href{/mcs/structures/number_theory/remainder_arithmetic/#subsection-9-7-1}{\text{Section 9.7.1}}] ring of integers modulo \(n\)} \\ a +_{n} b & \text{[\href{/mcs/structures/number_theory/remainder_arithmetic/#subsection-9-7-1}{\text{Section 9.7.1}}] addition in \(\mathbb{Z}_{n}\)} \\ a \cdot_{n} b & \text{[\href{/mcs/structures/number_theory/remainder_arithmetic/#subsection-9-7-1}{\text{Section 9.7.1}}] multiplication in \(\mathbb{Z}_{n}\)} \\ \mathbb{Z}^{\ast}_{n} & \text{[\text{Definition }\href{/mcs/structures/number_theory/eulers_theorem/#def-9-10-2}{9.10.2}] elements of \([0..n)\) that are relatively prime to \(n\)} \\ \phi (n) & \text{[\text{Definition }\href{/mcs/structures/number_theory/eulers_theorem/#def-9-10-1}{9.10.1}] Euler’s totient function, equal to \(\|\mathbb{Z}^{\ast}_{n}|\)} \\ \langle u \to v \rangle & \text{directed edge from source \(u\) to target \(v\)} \\ \text{Id}_{A} & \text{identity relation on set \(A\), \(\ a \mathrel{\text{Id}_{A}} a^{\prime}\ \overset{\text{def}}{\longleftrightarrow}\ a = a^{\prime}\)} \\ R^{\ast} & \text{[\href{/mcs/structures/directed_graphs_and_partial_orders/walk_relations/#}{\text{Section 10.4}}] walk relation of binary relation \(R\) (reflexive transitive closure of \(R\))} \\ R^{+} & \text{[\href{/mcs/structures/directed_graphs_and_partial_orders/walk_relations/#}{\text{Section 10.4}}] transitive closure of binary relation \(R\) (irreflexive transitive closure)} \\ \textbf{f} \;\widehat{\,\phantom{\text{\small l}}\,}\, \textbf{g} & \text{[\href{/mcs/structures/directed_graphs_and_partial_orders/walks_and_paths/#}{\text{Section 10.2}}] concatenation of walks \(\textbf{f}\) and \(\textbf{g}\)} \\ \textbf{f} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,x\,}\ \textbf{g} & \text{[\href{/mcs/structures/directed_graphs_and_partial_orders/walks_and_paths/#}{\text{Section 10.2}}] concatenation of walk \(\textbf{f}\) ending at vertex \(x\) and walk \(\textbf{g}\) starting at vertex \(x\)} \\ \langle u\>\text{---}\>v \rangle & \text{[\href{/mcs/structures/simple_graphs/vertex_adjacency_and_degrees/#}{\text{Section 12.1}}] undirected edge with endpoints at distinct vertices \(u\) and \(v\)} \\ E(G) & \text{edge set of graph \(G\)} \\ V(G) & \text{vertex set of graph \(G\)} \\ C_{n} & \text{[\href{/mcs/structures/simple_graphs/some_common_graphs/#}{\text{Section 12.3}}] cycle graph on \(n\) vertices} \\ L_{n} & \text{[\href{/mcs/structures/simple_graphs/some_common_graphs/#}{\text{Section 12.3}}] line graph on \(n\) vertices} \\ K_{n} & \text{[\href{/mcs/structures/simple_graphs/some_common_graphs/#}{\text{Section 12.3}}] complete graph on \(n\) vertices} \\ H_{n} & \text{[\href{/mcs/structures/simple_graphs/exercise/#problem-12-38}{Problem 12.38}] \(n\)-dimensional hypercube} \\ L(G) & \text{[\text{Definition }\href{/mcs/structures/simple_graphs/bipartite_graphs_and_matchings/#def-12-5-1}{12.5.1}] set of left vertices of bipartite graph \(G\)} \\ R(G) & \text{[\text{Definition }\href{/mcs/structures/simple_graphs/bipartite_graphs_and_matchings/#def-12-5-1}{12.5.1}] set of right vertices of bipartite graph \(G\)} \\ K_{n,m} & \text{[\href{/mcs/structures/planar_graphs/drawing_graphs_in_plane/#}{\text{Section 13.1}}] complete bipartite graph with \(n\) left vertices and \(m\) right vertices} \\ \chi(G) & \text{[\text{Definition }\href{/mcs/structures/simple_graphs/coloring/#def-12-6-1}{12.6.1}] chromatic number of simple graph \(G\)} \\ H_{n} & \text{[\text{Definition }\href{/mcs/structures/simple_graphs/bipartite_graphs_and_matchings/#def-12-5-1}{12.5.1}] \(n\)th harmonic number, \(\, ::= \sum_{i=1}^{n} 1/i\)} \\ n! & \text{[\href{/mcs/counting/sums_and_asymptotics/products/#}{\text{Section 14.5}}] factorial of \(n\), \(\, ::= n \cdot (n-1) \cdots 2 \cdot 1\)} \\ \binom{n}{m} & \text{binomial coefficient, \(\, \binom{n}{m} = n!/m!\,(n-m)!\)} \\ f \sim g & \text{[\text{Definition }\href{/mcs/counting/sums_and_asymptotics/hanging_out_over_edge/#def-14-4-2}{14.4.2}] \(f\) and \(g\) are asymptotically equal, \(\lim f / g = 1\)} \\ f = o(g) & \text{[\text{Definition }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-1}{14.7.1}] asymptotic notation: little-o} \\ f = O(g) & \text{[\text{Definition }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-5}{14.7.5}] asymptotic notation: big-O} \\ f = \Theta(g) & \text{[\text{Definition }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-13}{14.7.13}] asymptotic notation: Theta} \\ f = \Omega(g) & \text{[\text{Definition }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-15}{14.7.15}] asymptotic notation: big-Omega} \\ f = \omega(g) & \text{[\text{Definition }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-16}{14.7.16}] asymptotic notation: little-omega} \\ \operatorname{Pr}[A] & \text{[\text{Definition }\href{/mcs/probability/events_and_probability_spaces/set_theory_and_probability/#def-17-5-2}{17.5.2}] probability of event \(A\)} \\ \operatorname{Pr}[A \, | \, B] & \text{[\text{Definition }\href{/mcs/probability/conditional_probability/definition_and_notation/#def-18-2-1}{18.2.1}] probability of event \(A\) given event \(B\) occurs} \\ \mathcal{S}