有人正在为我翻译成日语。谢谢。https://inzkyk.xyz/mcs/

信息科学数学（翻译版） - inzkyk.xyz

来源：https://inzkyk.xyz/mcs/

信息科学数学

关于本书 (https://inzkyk.xyz/mcs/#%e6%9c%ac%e6%9b%b8%e3%81%ab%e3%81%a4%e3%81%84%e3%81%a6)

本书《信息科学数学》是 Eric Lehman、F. Thomson Leighton、Albert R. Meyer 所著 Mathematics for Computer Science (https://courses.csail.mit.edu/6.042/spring18/index.shtml) 的翻译版。原著根据 Creative Commons Attribution-ShareAlike 3.0 (https://creativecommons.org/licenses/by-sa/3.0/) 许可证发布。

本翻译版根据 Creative Commons Attribution-ShareAlike 3.0 许可证的授权发布。

本翻译版根据 Creative Commons Attribution-ShareAlike 3.0 许可证发布。

二次分发或二次使用本翻译版时，请务必在介绍文等处包含指向 https://inzkyk.xyz/mcs/ 的链接作为署名标识。

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

感谢原著 Mathematics for Computer Science 的作者 Eric Lehman 先生、F. Thomson Leighton 先生和 Albert R. Meyer 先生。

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

\[\def\arraystretch{1.35}\begin{array}{ll} \hspace{25pt}符号 & \hspace{120pt}含义 \\ \hline ::= & \text{ 被定义为 \(\cdots\)}, 根据定义等于 \(\cdots\) \\ \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{ 被定义为等价于 \(\cdots\)}, 根据定义与 \(\cdots\) 等价 \\ \neq & \text{不等于 (等号的否定)} \\ ■ & \text{[\href{/mcs/proofs/what_is_a_proof/proving_an_implication/#subsection-1-5-1}{\text{第 1.5.1 节}}] \text{\small Q.E.D.} (证明完毕)} \\ \wedge & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{第 3.1 节}}] {\footnotesize AND}, 且} \\ \vee & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{第 3.1 节}}] {\footnotesize OR}, 或} \\ \longrightarrow & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{第 3.1 节}}] {\footnotesize IMPLIES}, 则} \\ p \longrightarrow q & \text{[\href{/mcs/proofs/state_machines/states_and_transitions/#}{\text{第 6.1 节}}] 从状态 \(p\) 到状态 \(q\) 的转移} \\ \lnot P, \overline{\mathstrut P} & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{第 3.1 节}}] {\footnotesize NOT} \hspace{-4pt} \(P\), 非 \(P\)} \\ \longleftrightarrow & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{第 3.1 节}}] {\footnotesize IFF}, 当且仅当 \(\cdots\) 时, 等价} \\ \otimes & \text{[\href{/mcs/proofs/logical_formulas/propositions_from_propositions/#}{\text{第 3.1 节}}] {\footnotesize XOR}, 异或} \\ \exists & \text{[\href{/mcs/proofs/logical_formulas/predicate_formulas/#}{\text{第 3.6 节}}] 存在 \(\cdots\) 满足条件} \\ \forall & \text{[\href{/mcs/proofs/logical_formulas/predicate_formulas/#}{\text{第 3.6 节}}] 所有 \(\cdots\) 均满足条件} \\ \in & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{第 4.1 节}}] 是集合的元素, 属于} \\ \subseteq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{第 4.1 节}}] 是子集 (包括相等情况)} \\ \not \subseteq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{第 4.1 节}}] 不是子集 (\(\subseteq\) 的否定)} \\ \subsetneq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{第 4.1 节}}] 是真子集}\(是子集但不相等\) \\ \not \subsetneq & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#}{\text{第 4.1 节}}] 不是真子集 (\(\subsetneq\) 的否定)} \\ \cup & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/sets/#def-4-1-1}{4.1.1}] 并集} \\ \bigcup_{i \in I} S_{i} & \text{索引 \(i\) 取值范围为 \(I\) 的集合族 \(S_{i}\) 的并集} \\ \cap & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/sets/#def-4-1-1}{4.1.1}] 交集} \\ \bigcap_{i \in I} S_{i} & \text{索引 \(i\) 取值范围为 \(I\) 的集合族 \(S_{i}\) 的交集} \\ \varnothing & \text{空集 \(\left\{ \, \right\}\)} \\ \overline{\mathstrut A} & \text{集合 \(A\) 的补集} \\ A - B & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/sets/#def-4-1-1}{4.1.1}] 从集合 \(A\) 中去除集合 \(B\) 的元素后得到的差集} \\ \operatorname{pow} (A) & \text{[\href{/mcs/proofs/mathematical_data_types/sets/#subsection-4-1-3}{\text{第 4.1.3 节}}] 集合 \(A\) 的幂集} \\ A \times B & \text{[\href{/mcs/proofs/mathematical_data_types/sequences/#}{\text{第 4.2 节}}] 集合 \(A\), \(B\) 的笛卡尔积} \\ S^{n} & \text{\(n\) 个集合 \(S\) 的笛卡尔积 \(S \times S \times \cdots \times S\)} \\ \mathbb{Z} & \text{整数集} \\ \mathbb{N}, \mathbb{Z}^{\geq 0} & \text{非负整数集} \\ \mathbb{Z}^{+}, \mathbb{N}^{+} & \text{正整数集} \\ \mathbb{Z}^{-} & \text{负整数集} \\ \mathbb{Q} & \text{有理数集} \\ \mathbb{R} & \text{实数集} \\ \mathbb{C} & \text{复数集} \\ \left\lfloor r \right\rfloor & \text{实数 \(r\) 的向下取整函数值: 不大于 \(r\) 的最大整数} \\ \left\lceil r \right\rceil & \text{实数 \(r\) 的向上取整函数值: 不小于 \(r\) 的最小整数} \\ \left| r \right| & \text{实数 \(r\) 的绝对值} \\ R(X) & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-4}{4.4.4}] 二元关系 \(R\) 下集合 \(X\) 的像} \\ R^{-1} & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-5}{4.4.5}] 二元关系 \(R\) 的逆} \\ R^{-1}(X) & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-6}{4.4.6}] 二元关系 \(R\) 下集合 \(X\) 的逆像} \\ A \mathrel{\text{\small surj}} B & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/finite_cardinality/#def-4-5-2}{4.5.2}] \(\ \overset{\text{def}}{\longleftrightarrow}\) 存在满射函数 \(f \colon A \to B\)} \\ A \mathrel{\text{\small inj}} B & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/finite_cardinality/#def-4-5-2}{4.5.2}] \(\ \overset{\text{def}}{\longleftrightarrow}\) 存在全局单射函数 \(f \colon A \to B\)} \\ A \mathrel{\text{\small bij}} B & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/finite_cardinality/#def-4-5-2}{4.5.2}] \(\ \overset{\text{def}}{\longleftrightarrow}\) 存在双射 \(f \colon A \to B\)} \\ [\text{内} \leq 1] & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] 二元关系的单射条件} \\ [\text{内} \geq 1] & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] 二元关系的满射条件} \\ [\text{外} \leq 1] & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] 二元关系的函数条件} \\ [\text{外} \geq 1] & \text{[\text{定义 }\href{/mcs/proofs/mathematical_data_types/binary_relations/#def-4-4-2}{4.4.2}] 二元关系的双射条件} \\ R \circ S & \text{[\href{/mcs/proofs/mathematical_data_types/exercise/#problem-4-29}{问题 4.29}, \text{定义 }\href{/mcs/structures/directed_graphs_and_partial_orders/walk_relations/#def-10-4-2}{10.4.2}] 二元关系 \(R\), \(S\) 的复合} \\ \lambda & \text{空字符串或长度为 \(0\) 的列表} \\ A^{\ast} & [\text{定义 }\href{/mcs/proofs/recursive_data_types/recursive_definitions_and_structural_induction/#def-7-1-1}{7.1.1}] \text{字母表 \(A\) 上有限长字符串的集合} \\ A^{\omega} & \text{字母表 \(A\) 上无限长字符串的集合} \\ \operatorname{rev}(s) & \text{[\href{/mcs/proofs/recursive_data_types/exercise/#problem-7-3}{问题 7.3}] 字符串 \(s\) 的反转} \\ s \cdot t & \text{[\text{定义 }\href{/mcs/proofs/recursive_data_types/recursive_definitions_and_structural_induction/#def-7-1-3}{7.1.3}] 字符串 \(s\), \(t\) 的连接, \(\operatorname{append}(s,t)\)} \\ \#_{c}(s) & \text{[\text{定义 }\href{/mcs/proofs/recursive_data_types/strings_of_matched_brackets/#def-7-2-2}{7.2.2}] 字符 \(c\) 在字符串 \(s\) 中出现的次数} \\ m \; | \; n & \text{[\text{定义 }\href{/mcs/structures/number_theory/divisibility/#def-9-1-1}{9.1.1}] \(m\) 整除 \(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{第 9.2 节}}] 整数 \(a\), \(b\) 的最大公约数} \\ \operatorname{lcm}(a, b) & \text{整数 \(a\), \(b\) 的最大公约数注意: 日语原文此处疑似有误，应为“最小公倍数“，但鉴于翻译要求忠实原文，此处保留“最大公约数“，但需指出英文原词为 lcm (Least Common Multiple)，故更准确翻译应为“最小公倍数“。} \\ \log x & \text{以 \(2\) 为底 \(x\) 的对数, \(\log_{2} x\)} \\ \ln x & \text{\(x\) 的自然对数, \(\log_{e} x\)} \\ [k..n] & \text{\(\left\{ i \; | \; k \leq 1 \leq n \right\}\)注意: 原文条件为 k ≤ 1 ≤ n，疑为笔误，应理解为 k ≤ i ≤ n} \\ (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{索引 \(i\) 取值范围为 \(I\) 时 \(r_{i}\) 所表示的值的和} \\ \prod_{i \in I} r_{i} & \text{索引 \(i\) 取值范围为 \(I\) 时 \(r_{i}\) 所表示的值的积} \\ \operatorname{qcnt}(n,d) & \text{[\href{/mcs/structures/number_theory/divisibility/#}{\text{第 9.1 节}}] \(n\) 除以 \(d\) 的商} \\ \operatorname{rem}(n,d) & \text{[\href{/mcs/structures/number_theory/divisibility/#}{\text{第 9.1 节}}] \(n\) 除以 \(d\) 的余数} \\ a \equiv b \ \ (\text{mod } n) & \text{[\href{/mcs/structures/number_theory/modular_arithmetic/#}{\text{第 9.6 节}}] \(a\) 与 \(b\) 模 \(n\) 同余} \\ a \not \equiv b \ \ (\text{mod } n) & \text{[\href{/mcs/structures/number_theory/modular_arithmetic/#}{\text{第 9.6 节}}] \(a\) 与 \(b\) 模 \(n\) 不同余 (\(\equiv\) 的否定)} \\ \mathbb{Z}_{n} & \text{[\href{/mcs/structures/number_theory/remainder_arithmetic/#subsection-9-7-1}{\text{第 9.7.1 节}}] 模 \(n\) 的整数环} \\ a +_{n} b & \text{[\href{/mcs/structures/number_theory/remainder_arithmetic/#subsection-9-7-1}{\text{第 9.7.1 节}}] \(\mathbb{Z}_{n}\) 中的加法} \\ a \cdot_{n} b & \text{[\href{/mcs/structures/number_theory/remainder_arithmetic/#subsection-9-7-1}{\text{第 9.7.1 节}}] \(\mathbb{Z}_{n}\) 中的乘法} \\ \mathbb{Z}^{\ast}_{n} & \text{[\text{定义 }\href{/mcs/structures/number_theory/eulers_theorem/#def-9-10-2}{9.10.2}] 与 \(n\) 互质的 \([0..n)\) 中的元素} \\ \phi (n) & \text{[\text{定义 }\href{/mcs/structures/number_theory/eulers_theorem/#def-9-10-1}{9.10.1}] 欧拉函数, 等于 \(|\mathbb{Z}^{\ast}_{n}|\)} \\ \langle u \to v \rangle & \text{ 起点为 \(u\) 终点为 \(v\) 的有向边} \\ \text{Id}_{A} & \text{集合 \(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{第 10.4 节}}] 二元关系 \(R\) 的路径关系 (\(R\) 的自反传递闭包)} \\ R^{+} & \text{[\href{/mcs/structures/directed_graphs_and_partial_orders/walk_relations/#}{\text{第 10.4 节}}] 二元关系 \(R\) 的路径关系 (\(R\) 的自反传递闭包)注意原文对于 R* 和 R+ 的描述完全相同，但通常 R* 是自反传递闭包，R+ 是传递闭包（不自反）。} \\ \textbf{f} \;\widehat{\,\phantom{\text{\small l}}\,}\, \textbf{g} & \text{[\href{/mcs/structures/directed_graphs_and_partial_orders/walks_and_paths/#}{\text{第 10.2 节}}] 路径 \(\textbf{f}\), \(\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{第 10.2 节}}] 终点为顶点 \(x\) 的路径 \(\textbf{f}\) 与起点为顶点 \(x\) 的路径 \(\textbf{g}\) 的连接} \\ \langle u\>\text{---}\>v \rangle & \text{[\href{/mcs/structures/simple_graphs/vertex_adjacency_and_degrees/#}{\text{第 12.1 节}}] 以不同顶点 \(u\), \(v\) 为端点的无向边} \\ E(G) & \text{图 \(G\) 的边集} \\ V(G) & \text{图 \(G\) 的顶点集} \\ C_{n} & \text{[\href{/mcs/structures/simple_graphs/some_common_graphs/#}{\text{第 12.3 节}}] \(n\) 个顶点的圈图} \\ L_{n} & \text{[\href{/mcs/structures/simple_graphs/some_common_graphs/#}{\text{第 12.3 节}}] \(n\) 个顶点的线图} \\ K_{n} & \text{[\href{/mcs/structures/simple_graphs/some_common_graphs/#}{\text{第 12.3 节}}] \(n\) 个顶点的完全图} \\ H_{n} & \text{[\href{/mcs/structures/simple_graphs/exercise/#problem-12-38}{问题 12.38}] \(n\) 维超立方体} \\ L(G) & \text{[\text{定义 }\href{/mcs/structures/simple_graphs/bipartite_graphs_and_matchings/#def-12-5-1}{12.5.1}] 二部图 \(G\) 的左顶点集} \\ R(G) & \text{[\text{定义 }\href{/mcs/structures/simple_graphs/bipartite_graphs_and_matchings/#def-12-5-1}{12.5.1}] 二部图 \(G\) 的右顶点集} \\ K_{n,m} & \text{[\href{/mcs/structures/planar_graphs/drawing_graphs_in_plane/#}{\text{第 13.1 节}}] 具有 \(n\) 个左顶点和 \(m\) 个右顶点的完全二部图} \\ \chi(G) & \text{[\text{定义 }\href{/mcs/structures/simple_graphs/coloring/#def-12-6-1}{12.6.1}] 简单图 \(G\) 的色数} \\ H_{n} & \text{[\text{定义 }\href{/mcs/structures/simple_graphs/bipartite_graphs_and_matchings/#def-12-5-1}{12.5.1}] \(n\) 次调和数, \(\, ::= \sum_{i=1}^{n} 1/i\)注意: 原书此处 H_n 定义可能指调和数，但链接指向二部图定义，存疑} \\ n! & \text{[\href{/mcs/counting/sums_and_asymptotics/products/#}{\text{第 14.5 节}}] \(n\) 的阶乘, \(\, ::= n \cdot (n-1) \cdots 2 \cdot 1\)} \\ \binom{n}{m} & \text{二项式系数, \(\, \binom{n}{m} = n!/m!\,(n-m)!\)} \\ f \sim g & \text{[\text{定义 }\href{/mcs/counting/sums_and_asymptotics/hanging_out_over_edge/#def-14-4-2}{14.4.2}] \(f\) 与 \(g\) 渐近等价, \(\lim f / g = 1\)} \\ f = o(g) & \text{[\text{定义 }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-1}{14.7.1}] 渐近记号: 小欧} \\ f = O(g) & \text{[\text{定义 }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-5}{14.7.5}] 渐近记号: 大欧} \\ f = \Theta(g) & \text{[\text{定义 }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-13}{14.7.13}] 渐近记号: 西塔} \\ f = \Omega(g) & \text{[\text{定义 }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-15}{14.7.15}] 渐近记号: 大欧米茄} \\ f = \omega(g) & \text{[\text{定义 }\href{/mcs/counting/sums_and_asymptotics/asymptotic_notation/#def-14-7-16}{14.7.16}] 渐近记号: 小欧米茄} \\ \operatorname{Pr}[A] & \text{[\text{定义 }\href{/mcs/probability/events_and_probability_spaces/set_theory_and_probability/#def-17-5-2}{17.5.2}] 事件 \(A\) 的概率} \\ \operatorname{Pr}[A \, | \, B] & \text{[\text{定义 }\href{/mcs/probability/conditional_probability/definition_and_notation/#def-18-2-1}{18.2.1}] 在事件 \(B\) 发生的条件下事件 \(A\) 的概率}