付録A: 数学記法ガイド
本書で使用する数学記法の統一ガイドです。理論計算機科学で一般的に使用される記法に準拠しています。
集合論記号
基本記号
| 記号 |
読み |
意味 |
例 |
| ∈ |
〜に属する |
要素の所属関係 |
x ∈ A (xはAの要素) |
| ∉ |
〜に属さない |
要素の非所属関係 |
x ∉ A (xはAの要素でない) |
| ⊆ |
部分集合 |
集合の包含関係 |
A ⊆ B (AはBの部分集合) |
| ⊊ |
真部分集合 |
真の包含関係 |
A ⊊ B (AはBの真部分集合) |
| ∪ |
和集合 |
集合の合併 |
A ∪ B |
| ∩ |
積集合 |
集合の共通部分 |
A ∩ B |
| ∅ |
空集合 |
要素を持たない集合 |
A ∩ B = ∅ |
| \ |
差集合 |
集合の差 |
A \ B |
| × |
直積 |
デカルト積 |
A × B |
| 𝒫(A) |
べき集合 |
Aのすべての部分集合 |
𝒫({1,2}) = {∅,{1},{2},{1,2}} |
集合の記法
外延的記法: {a, b, c, …}
内包的記法: {x | P(x)}
例: A = {x ∈ ℕ | x ≤ 5} = {1, 2, 3, 4, 5}
論理記号
命題論理
| 記号 |
読み |
意味 |
例 |
| ∧ |
かつ |
論理積（AND） |
P ∧ Q |
| ∨ |
または |
論理和（OR） |
P ∨ Q |
| ¬ |
でない |
否定（NOT） |
¬P |
| → |
ならば |
含意 |
P → Q |
| ↔ |
と同値 |
同値 |
P ↔ Q |
| ⊤ |
真 |
恒真 |
P ∨ ¬P ≡ ⊤ |
| ⊥ |
偽 |
恒偽 |
P ∧ ¬P ≡ ⊥ |
述語論理
| 記号 |
読み |
意味 |
例 |
| ∀ |
すべての |
全称量詞 |
∀x ∈ A, P(x) |
| ∃ |
存在する |
存在量詞 |
∃x ∈ A, P(x) |
| ∃! |
唯一存在する |
一意存在量詞 |
∃!x ∈ A, P(x) |
関数記法
基本記法
| 記号 |
意味 |
例 |
| f: A → B |
AからBへの関数 |
f: ℕ → ℕ |
| f(x) |
xのfによる像 |
f(3) = 9 |
| dom(f) |
fの定義域 |
dom(f) = A |
| ran(f) |
fの値域 |
ran(f) ⊆ B |
| f⁻¹ |
fの逆関数 |
f⁻¹: B → 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, 2, 3, …} |
|
| ℕ₀ |
自然数（0を含む） |
{0, 1, 2, 3, …} |
|
| ℤ |
整数 |
{…, -2, -1, 0, 1, 2, …} |
|
| ℚ |
有理数 |
{p/q |
p,q ∈ ℤ, q ≠ 0} |
| ℝ |
実数 |
実数全体 |
|
| ℂ |
複素数 |
{a + bi |
a,b ∈ ℝ} |
数列とその他
| 記号 |
意味 |
例 |
| ⌊x⌋ |
xの床関数 |
⌊3.7⌋ = 3 |
| ⌈x⌉ |
xの天井関数 |
⌈3.2⌉ = 4 |
| log n |
底2の対数 |
log 8 = 3 |
| ln n |
自然対数 |
ln e = 1 |
| n! |
nの階乗 |
5! = 120 |
| (ⁿₖ) |
二項係数 |
(⁵₂) = 10 |
漸近記法（Big-O記法）
基本記法
| 記号 |
読み |
意味 |
| O(g(n)) |
ビッグオー |
上界（最悪の場合） |
| Ω(g(n)) |
ビッグオメガ |
下界（最良の場合） |
| Θ(g(n)) |
ビッグシータ |
上界と下界（平均的な場合） |
| o(g(n)) |
リトルオー |
真の上界 |
| ω(g(n)) |
リトルオメガ |
真の下界 |
定義
O(g(n)): ∃c > 0, ∃n₀ ∈ ℕ, ∀n ≥ n₀, f(n) ≤ c·g(n)
Ω(g(n)): ∃c > 0, ∃n₀ ∈ ℕ, ∀n ≥ n₀, f(n) ≥ c·g(n)
Θ(g(n)): f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n))
グラフ理論記法
基本記法
| 記号 |
意味 |
例 |
|
| G = (V, E) |
グラフ |
V: 頂点集合, E: 辺集合 |
|
| |V| |
頂点数 |
n = |V| |
|
| |E| |
辺数 |
m = |E| |
|
| (u, v) |
辺 |
頂点uとvを結ぶ辺 |
|
| deg(v) |
次数 |
頂点vの次数 |
|
| δ(G) |
最小次数 |
min{deg(v) |
v ∈ V} |
| Δ(G) |
最大次数 |
max{deg(v) |
v ∈ V} |
パス・サイクル
| 記号 |
意味 |
| Pₙ |
n頂点のパス |
| Cₙ |
n頂点のサイクル |
| d(u, v) |
頂点u, v間の距離 |
形式言語記法
基本記法
| 記号 |
意味 |
例 |
| Σ |
アルファベット |
Σ = {a, b} |
| Σ* |
Σ上の文字列全体 |
{ε, a, b, aa, ab, ba, bb, …} |
| Σ⁺ |
Σ上の空でない文字列 |
Σ* \ {ε} |
| ε |
空文字列 |
長さ0の文字列 |
| |w| |
文字列wの長さ |
|abc| = 3 |
| wᴿ |
文字列wの逆順 |
(abc)ᴿ = cba |
| L₁ ∪ L₂ |
言語の和集合 |
|
| L₁ ∘ L₂ |
言語の連結 |
|
| L* |
言語のKleene閉包 |
|
オートマトン記法
| 記号 |
意味 |
| M = (Q, Σ, δ, q₀, F) |
有限オートマトン |
| Q |
状態集合 |
| δ |
遷移関数 |
| q₀ |
初期状態 |
| F |
受理状態集合 |
複雑性理論記法
複雑性クラス
| 記号 |
意味 |
| P |
多項式時間で解ける問題のクラス |
| NP |
非決定多項式時間で解ける問題のクラス |
| PSPACE |
多項式空間で解ける問題のクラス |
| EXPTIME |
指数時間で解ける問題のクラス |
還元記法
| 記号 |
意味 |
| A ≤ₚ B |
AからBへの多項式時間還元 |
| A ≤ₘ 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) ≡ n² + 1 |
| ≈ |
近似 |
π ≈ 3.14 |
| ∼ |
漸近的等価 |
f(n) ∼ g(n) |
| ∝ |
比例 |
f(n) ∝ g(n) |
その他
| 記号 |
意味 |
例 |
| ⊕ |
排他的論理和 |
a ⊕ b |
| ≪ |
much less than |
n ≪ 2ⁿ |
| ≫ |
much greater than |
2ⁿ ≫ n |
| ∞ |
無限大 |
lim_{n→∞} |
使用上の注意
- 一貫性: 同一文書内では記法を統一する
- 明確性: 初出時は意味を明示する
- 標準性: 広く受け入れられた記法を使用する
- 読みやすさ: 複雑な式は適切に改行・インデントする
このガイドを参考に、理論計算機科学の厳密で美しい数学的記述を習得してください。