情報科学のための数学

\[\def\arraystretch{1.35}\begin{array}{ll} \hspace{25pt}記号 & \hspace{120pt}意味 \\ \hline ::= & \text{ \(\cdots\) と定義される}, \text{定義より \(\cdots\) に等しい} \\ \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{ \(\cdots\) と同値だと定義される}, \text{定義より \(\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}] 文字列 \(s\) に文字 \(c\) が現れる回数} \\ 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\) の最大公約数} \\ \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..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\) は \(n\) を法として \(b\) と合同} \\ a \not \equiv b \ \ (\text{mod } n) & \text{[\href{/mcs/structures/number_theory/modular_arithmetic/#}{\text{第 9.6 節}}] \(a\) は \(n\) を法として \(b\) と合同でない (\(\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}] Euler のトーシェント関数, \(|\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\) の反射推移閉包)} \\ \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\)} \\ 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\) の確率} \\ \mathcal{S} & \text{[\href{/mcs/probability/events_and_probability_spaces/four_step_method/#subsection-17-2-1}{\text{第 17.2.1 項}}, \text{定義 }\href{/mcs/probability/events_and_probability_spaces/set_theory_and_probability/#def-17-5-1}{17.5.1}] 標本空間} \\ I_{A} & \text{[\href{/mcs/probability/random_variables/random_variable_examples/#subsection-19-1-1}{\text{第 19.1.1 項}}] 事象 \(A\) に対応する指示確率変数 (Bernoulli 変数)} \\ \text{PDF} & \text{[\text{定義 }\href{/mcs/probability/random_variables/distribution_functions/#def-19-3-1}{19.3.1}] 確率密度関数} \\ \text{CDF} & \text{[\text{定義 }\href{/mcs/probability/random_variables/distribution_functions/#def-19-3-1}{19.3.1}] 累積分布関数} \\ \operatorname{Ex}[R] & \text{[\text{定義 }\href{/mcs/probability/random_variables/great_expectations/#def-19-4-1}{19.4.1}] 確率変数 \(R\) の期待値} \\ \operatorname{Ex}[R \, | \, A] & \hspace{-5pt} \begin{array}{l} \text{[\text{定義 }\href{/mcs/probability/random_variables/great_expectations/#def-19-4-5}{19.4.5}] 事象 \(A\) が起こるという条件の下での確率変数 \(R\) の} \\ \text{条件付き期待値} \end{array} \\ \operatorname{Ex}^{2}[R] & \text{\((\operatorname{Ex}[R])^{2}\) の略記} \\ \operatorname{Var}[R] & \text{[\text{定義 }\href{/mcs/probability/deviation_from_mean/chebyshevs_theorem/#def-20-2-2}{20.2.2}] 確率変数 \(R\) の分散} \\ \operatorname{Var}^{2}[R] & \text{\((\operatorname{Var}[R])^{2}\) の略記} \\ \sigma_{R} & \text{[\text{定義 }\href{/mcs/probability/deviation_from_mean/chebyshevs_theorem/#def-20-2-4}{20.2.4}] 確率変数 \(R\) の標準偏差} \end{array}\]