付録A: 数学記法ガイド
本書で使用する数学記法の統一ガイドです。理論計算機科学で一般的に使用される記法に準拠しています。
この付録の使い方
- 向いている読者: 本文や練習問題で記号の意味・書き方・Markdown 上の注意を引き直したい読者
- 使うタイミング: 定義や証明を読んでいて、記号の意味や表記ルールに迷ったとき
- 読み方: まず
クイックナビ から該当分野へ移動し、必要なら 表記規約 と 使用上の注意 で Markdown / 数式の書き分けを確認してください。
クイックナビ
表記規約（Notation）
本書では、Markdown の解釈（| や *）による記号の欠落・意味変化を避けるため、数式・集合表記を次の規約で統一します。
- 濃度（集合の要素数）：
\\(\lvert A\rvert\\)（|A| の直書きはしない）
- 文字列長：
\\(\lvert w\rvert\\)（|w| の直書きはしない）
- 内包表記（集合の条件）：
\\(\\{x \mid P(x)\\}\\)（{x | ...} の直書きはしない）
- 条件（「…という条件の下で」）：
\mid（例：\\(\Pr[X=x \mid Y=y]\\)、\\(\mathrm{H}(Y \mid X)\\)）
- 割り切り（divisibility）：
\mid（例：\\(\,q \mid (p-1)\,\\)。q | (p-1) の直書きはしない）
- 連結（concatenation）：
\parallel（例：\\(\,r \parallel m\,\\)。|| の直書きはしない）
- KL の二重バー（Kullback–Leibler）：
\Vert（例：\\(\mathrm{D}(P \,\Vert\, Q)\\)。|| の直書きはしない）
- 補集合：
\\(\overline{L}\\)（L̄ 等の合成文字の直書きは避ける）
- Kleene 星：
\\(\Sigma^{\ast}\\)、\\(\\{0,1\\}^{\ast}\\) のように数式中で表記する
- 文字列への拡張も
^{\ast} を用いる（例：\\(C^{\ast}: X^{\ast} \\to D^{\ast}\\)。C*/X*/D* の直書きはしない）
- 正規表現：本文中は原則インラインコードで表記する（例：
`^[0-9]+$`）
集合論記号
基本記号
| 記号 |
読み |
意味 |
例 |
| ∈ |
〜に属する |
要素の所属関係 |
x ∈ A (xはAの要素) |
| ∉ |
〜に属さない |
要素の非所属関係 |
x ∉ A (xはAの要素でない) |
| ⊆ |
部分集合 |
集合の包含関係 |
A ⊆ B (AはBの部分集合) |
| ⊂ |
真部分集合 |
真の包含関係 |
A ⊂ B (AはBの真部分集合) |
| ∪ |
和集合 |
集合の合併 |
A ∪ B |
| ∩ |
共通部分（intersection） |
集合の共通部分 |
A ∩ B |
| ∅ |
空集合 |
要素を持たない集合 |
A ∩ B = ∅ |
| \ |
差集合 |
集合の差 |
A \ B |
| × |
直積 |
デカルト積 |
A × B |
| \(\mathcal{P}(A)\) |
冪集合 |
Aのすべての部分集合 |
\(\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\) |
集合の記法
外延的記法: {a, b, c, …}
例: \(A = \{1, 2, 3, 4, 5\}\)
内包的記法: \(\{x \mid P(x)\}\)
例: \(A = \{x \in \mathbb{N} \mid x \le 5\} = \{1, 2, 3, 4, 5\}\)
Markdown上の注意（縦棒・Kleene星・減算記号）
- Markdownの表では
| が区切り文字になるため、集合の濃度・長さ・内包表記の区切りは |...| や {x | ...} を直書きせず、\\(\lvert\cdot\rvert\\) と \mid を用いて数式として記述します。
- Kleene 星（
*）は Markdown の強調と衝突しうるため、\(\Sigma^{\ast}\) のように数式中で表記し、正規表現はインラインコードに統一します。
- 本文（数式でない部分）の減算は原則として
−（U+2212）を用い、両側に半角スペースを入れます（例: n − 1）。コードや疑似コード内では - を用います。
論理記号
命題論理
| 記号 |
読み |
意味 |
例 |
| ∧ |
かつ |
論理積（AND） |
\(P \land Q\) |
| ∨ |
または |
論理和（OR） |
\(P \lor Q\) |
| ¬ |
でない |
否定（NOT） |
\(\neg P\) |
| → |
ならば |
含意 |
\(P \to Q\) |
| ↔ |
と同値 |
同値 |
\(P \leftrightarrow Q\) |
| ⊤ |
真 |
恒真 |
\(P \lor \neg P \equiv \top\) |
| ⊥ |
偽 |
恒偽 |
\(P \land \neg P \equiv \bot\) |
述語論理
| 記号 |
読み |
意味 |
例 |
| ∀ |
すべての |
全称量詞 |
\(\forall x \in A,\ P(x)\) |
| ∃ |
存在する |
存在量詞 |
\(\exists x \in A,\ P(x)\) |
| ∃! |
唯一存在する |
一意存在量詞 |
\(\exists! x \in A,\ P(x)\) |
関数記法
基本記法
| 記号 |
意味 |
例 |
| \(f: A \to B\) |
AからBへの関数 |
\(f: \mathbb{N} \to \mathbb{N}\) |
| f(x) |
xのfによる像 |
f(3) = 9 |
| dom(f) |
fの定義域 |
dom(f) = A |
| ran(f) |
fの値域 |
ran(f) ⊆ B |
| \(f^{-1}\) |
fの逆関数 |
\(f^{-1}: B \to A\) |
| g ∘ f |
合成関数 |
(g ∘ f)(x) = g(f(x)) |
関数の性質
| 用語 |
記号 |
意味 |
| 単射（injection） |
∀x,y ∈ A, f(x) = f(y) → x = y |
異なる入力は異なる出力 |
| 全射（surjection） |
∀b ∈ B, ∃a ∈ A, f(a) = b |
すべての出力が使われる |
| 全単射（bijection） |
単射かつ全射 |
一対一対応 |
数と数列
数集合
| 記号 |
意味 |
例 |
| ℕ |
自然数（本書では1から） |
{1, 2, 3, …} |
| \(\mathbb{N}_0\) |
自然数（0を含む） |
{0, 1, 2, 3, …} |
| \(\mathbb{N}_{>0}\) |
正の自然数（0を除く） |
\(\{n \in \mathbb{N} \mid n > 0\}\) |
| ℤ |
整数 |
{…, -2, -1, 0, 1, 2, …} |
| ℚ |
有理数 |
\(\{p/q \mid p,q \in \mathbb{Z}, q \ne 0\}\) |
| ℝ |
実数 |
実数全体 |
| ℂ |
複素数 |
\(\{a + bi \mid a,b \in \mathbb{R}\}\) |
数列とその他
| 記号 |
意味 |
例 |
| ⌊x⌋ |
xの床関数 |
⌊3.7⌋ = 3 |
| ⌈x⌉ |
xの天井関数 |
⌈3.2⌉ = 4 |
| \(\log_2 n\) |
底2の対数 |
\(\log_2 8 = 3\) |
| ln n |
自然対数 |
ln e = 1 |
| n! |
nの階乗 |
5! = 120 |
| \(\binom{n}{k}\) |
二項係数 |
\(\binom{5}{2} = 10\) |
漸近記法（Big-O記法）
基本記法
| 記号 |
読み |
意味 |
| O(g(n)) |
ビッグオー |
上界（最悪の場合） |
| Ω(g(n)) |
ビッグオメガ |
下界（最良の場合） |
| Θ(g(n)) |
ビッグシータ |
上界と下界（平均的な場合） |
| o(g(n)) |
リトルオー |
真の上界 |
| ω(g(n)) |
リトルオメガ |
真の下界 |
定義
O(g(n)): \(\exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \ge n_0, f(n) \le c \cdot g(n)\)
Ω(g(n)): \(\exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \ge n_0, f(n) \ge c \cdot g(n)\)
Θ(g(n)): f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n))
グラフ理論記法
基本記法
| 記号 |
意味 |
例 |
| G = (V, E) |
グラフ |
V: 頂点集合, E: 辺集合 |
| \(\lvert V\rvert\) |
頂点数 |
\(n = \lvert V\rvert\) |
| \(\lvert E\rvert\) |
辺数 |
\(m = \lvert E\rvert\) |
| (u, v) |
辺 |
頂点uとvを結ぶ辺 |
| deg(v) |
次数 |
頂点vの次数 |
| δ(G) |
最小次数 |
\(\min\{\deg(v) \mid v \in V\}\) |
| Δ(G) |
最大次数 |
\(\max\{\deg(v) \mid v \in V\}\) |
パス・サイクル
| 記号 |
意味 |
| \(P_n\) |
n頂点のパス |
| \(C_n\) |
n頂点のサイクル |
| d(u, v) |
頂点u, v間の距離 |
基本記法
| 記号 |
意味 |
例 |
| Σ |
アルファベット |
Σ = {a, b} |
| \(\Sigma^{\ast}\) |
Σ上の文字列全体 |
\(\{\epsilon, a, b, aa, ab, ba, bb, \ldots\}\) |
| \(\Sigma^+\) |
Σ上の空でない文字列 |
\(\Sigma^{\ast} \setminus \{\epsilon\}\) |
| ε |
空文字列 |
長さ0の文字列 |
| \(\lvert w\rvert\) |
文字列wの長さ |
\(\lvert abc\rvert = 3\) |
| \(\mathcal{P}(Q)\) |
集合Qの冪集合 |
\(\delta: Q \times \Sigma \to \mathcal{P}(Q)\) |
| \(w^R\) |
文字列wの逆順 |
\((abc)^R = cba\) |
| \(L_1 \cup L_2\) |
言語の和集合 |
|
| \(L_1L_2\) |
言語の連結 |
|
| \(L^{\ast}\) |
言語のKleene閉包 |
|
オートマトン記法
| 記号 |
意味 |
| \(M = (Q, \Sigma, \delta, q_0, F)\) |
有限オートマトン |
| Q |
状態集合 |
| δ |
遷移関数 |
| \(q_0\) |
初期状態 |
| F |
受理状態集合 |
複雑性理論記法
複雑性クラス
| 記号 |
意味 |
| P |
多項式時間で解ける問題のクラス |
| NP |
非決定多項式時間で解ける問題のクラス |
| PSPACE |
多項式空間で解ける問題のクラス |
| EXPTIME |
指数時間で解ける問題のクラス |
還元記法
| 記号 |
意味 |
| \(A \le_p B\) |
AからBへの多項式時間還元 |
| \(A \le_m B\) |
AからBへのmany-one還元 |
証明記法
証明の構造
| 記号・用語 |
意味 |
| 証明 |
定理の正当性を示す論理的議論 |
| □ / ∎ |
証明終了記号 |
| 補題 |
定理の証明で使う補助的命題 |
| 系 |
定理から直接導かれる結果 |
証明技法
| 技法 |
構造 |
| 直接証明 |
P → Q を P を仮定して Q を導く |
| 対偶証明 |
P → Q を ¬Q → ¬P で証明 |
| 背理法 |
P を ¬P を仮定して矛盾を導く |
| 数学的帰納法 |
P(1) ∧ ∀k(P(k) → P(k+1)) → ∀n P(n) |
特殊記号
等価・関係
| 記号 |
意味 |
例 |
| ≡ |
定義による等価 |
\(f(n) \equiv n^2 + 1\) |
| ≈ |
近似 |
π ≈ 3.14 |
| ∼ |
漸近的等価 |
f(n) ∼ g(n) |
| ∝ |
比例 |
f(n) ∝ g(n) |
その他
| 記号 |
意味 |
例 |
| ⊕ |
排他的論理和 |
a ⊕ b |
| ≪ |
much less than |
\(n \ll 2^n\) |
| ≫ |
much greater than |
\(2^n \gg n\) |
| ∞ |
無限大 |
\(\lim_{n\to\infty}\) |
使用上の注意
- 一貫性: 同一文書内では記法を統一する
- 明確性: 初出時は意味を明示する
- 標準性: 広く受け入れられた記法を使用する
- 読みやすさ: 複雑な式は適切に改行・インデントする
このガイドを参考に、理論計算機科学の厳密で美しい数学的記述を習得してください。