理論計算機科学教科書

第1章 数学的基礎

章プロフィール

集合論、論理学、証明技法

読了目安 3〜4週間
難易度 ★★☆☆
章構成 5節

主要トピック

  • 集合論
  • 論理学
  • 証明技法
  • 関係と関数
  • グラフ理論の基礎

戻り先

付録A: 記法 付録C: 解答 付録D: 用語 付録F: 進捗

理論計算機科学の全体像

本書で学ぶ理論計算機科学の全体像を以下の図に示します。各章がどのように関連し、理論がどのように発展していくかを把握してから学習を始めることで、より深い理解が得られるでしょう。

理論計算機科学の体系と相互関連

この図では、第1章〜第3章で扱う数学的基礎が土台となり、その上に計算可能性・計算複雑性・形式言語といった理論が積み上がり、さらに情報理論・暗号理論・並行計算などの応用的なトピックへと展開していく流れを表しています。
実線の矢印は「この分野の理解には矢印の元の分野の知識が直接必要である」という前提関係を、二重線の矢印は特に強い理論的発展の関係を示しています。点線の矢印は補助的な関連や応用の関係を表しており、後の章を読む際に「どの基礎に戻ればよいか」を確認する手掛かりになります。

凡例

  • 実線の矢印 (→): 直接的な前提知識の関係
  • 二重線の矢印 (⇒): 強い理論的発展の関係
  • 点線の矢印 (⋯>): 補助的な関連・応用

はじめに

コンピュータサイエンスの理論を学ぶ上で、数学は欠かせない基盤となります。アルゴリズムの正確性を証明し、計算の複雑さを解析し、形式的な仕様を記述するには、数学的な言語と思考法が必要不可欠です。

本章では、後の章で必要となる数学的概念と証明技法を体系的に学びます。具体的には、集合論、論理学、証明技法、関係と関数、そしてグラフ理論の基礎に焦点を当てます。これらの知識は、計算理論、アルゴリズム解析、形式的手法において中核的な役割を果たします。

学習目標

  • 集合の基本演算（和・共通部分・差・補）と冪集合を説明できる
  • 命題論理・述語論理の基礎と代表的な推論規則を用いて証明できる
  • 証明技法（直接法・背理法・数学的帰納法・構造帰納法）を使い分けられる
  • 関係と関数（単射・全射・全単射、合成、逆関数）の性質を述べられる
  • グラフの基本概念（次数、連結、木、二部グラフ）を説明できる

1.1 集合論

集合論は、現代数学の基礎となる言語です。

1.1.1 集合の基本概念

集合（set）とは、明確に区別できる「もの」の集まりです。集合に含まれる個々の「もの」を要素（element）または元（げん）と呼びます。 要素 a が集合 A に属することを a ∈ A と表記し、属さないことを a ∉ A と表記します。

集合を表す主な方法は2つあります。

  1. 外延的記法（列挙）: A = {1, 2, 3, 4, 5}
    • 要素をコンマで区切り、中括弧 {} で囲みます。
    • 要素の順序は問いません ({1, 2, 3} と {3, 1, 2} は同じ集合です)。
    • 要素の重複は許されません ({1, 2, 2, 3} は {1, 2, 3} と同じ集合です)。
  2. 内包的記法（条件指定）: \(A = \{x \in \mathbb{Z} \mid 1 \le x \le 5\}\)
    • \(\{x \mid P(x)\}\) の形で、条件 P(x) を満たす要素 x 全体の集合を表します。

いくつかの重要な集合は次のとおりです。

  • 空集合（empty set）: 要素を一つも含まない集合。∅ または {} で表記します。
  • 自然数の集合: ℕ = {1, 2, 3, …} （本書では1から始めます）
  • 非負整数の集合: \(\mathbb{N}_0 = \{0, 1, 2, 3, \ldots\}\)（0 を含めたい場合は必ず \(\mathbb{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}, i^2 = -1\}\)
  • 全体集合（universal set）: 考察の対象となるすべての要素を含む集合。通常 U で表記します。

部分集合と相等: 集合 A のすべての要素が集合 B にも含まれるとき、A は B の部分集合（subset）であるといい、A ⊆ B と表記します。

  • 真部分集合（proper subset）: A ⊆ B かつ A ≠ B のとき、A ⊂ B と表記します。
  • 相等（equality）: A = B ⟺ A ⊆ B かつ B ⊆ A

集合 A の冪集合（power set）\(\mathcal{P}(A)\) または \(2^A\) は、A のすべての部分集合からなる集合です。 例: A = {a, b} のとき、\(\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}\)

定理 1.1 有限集合 A に対して、\(\lvert \mathcal{P}(A)\rvert = 2^{\lvert A\rvert}\)

証明：A の各要素について、それを部分集合に含めるか含めないかの2通りの選択があります。A の要素数を n とすると、独立な選択が n 回あるので、部分集合の総数は 2^n となります。□

1.1.2 集合演算

基本的な集合演算は次のとおりです。

  1. 和集合（union）: \(A \cup B = \{x \mid x \in A \lor x \in B\}\)
  2. 共通部分（intersection）: \(A \cap B = \{x \mid x \in A \land x \in B\}\)
  3. 差集合（difference）: \(A \setminus B = \{x \mid x \in A \land x \notin B\}\)（\(A - B\) とも書きます）
  4. 対称差（symmetric difference）: \(A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)\)
  5. 補集合（complement）: \(A^c = U \setminus A\)（\(U\) は全体集合）

計算機科学における具体例

  • プログラミング言語：A = {Java, Python, C++}, B = {Python, JavaScript, Go}
    • A ∪ B = {Java, Python, C++, JavaScript, Go}（すべての言語）
    • A ∩ B = {Python}（両方のセットに共通する言語）
    • A \ B = {Java, C++}（Aにはあるが、Bにはない言語）
    • A Δ B = {Java, C++, JavaScript, Go}（どちらか一方にのみ存在する言語）
  • データ型：整数型変数の集合Iと浮動小数点型変数の集合Fの関係
    • I ∩ F = ∅（異なるデータ型は同一の変数になれない）
    • I ∪ F ⊆ 数値型変数の集合

集合演算の視覚化

定理 1.2 任意の集合 A, B, C に対して、以下が成り立ちます。

  • 交換法則: A ∪ B = B ∪ A, A ∩ B = B ∩ A
  • 結合法則: (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C)
  • 分配法則: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
  • 吸収法則: A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A
  • 冪等法則: A ∪ A = A, A ∩ A = A
  • ド・モルガンの法則: (A ∪ B)^c = A^c ∩ B^c, (A ∩ B)^c = A^c ∪ B^c
  • その他: A ∪ ∅ = A, A ∩ U = A, A ∩ ∅ = ∅, A ∪ U = U, (A^c)^c = A

証明（ド・モルガンの法則 (A ∪ B)^c = A^c ∩ B^c のみ示します） \(x ∈ (A ∪ B)^c\) \(⟺ x ∉ (A ∪ B)\) \(⟺ ¬(x ∈ A ∨ x ∈ B)\) \(⟺ (x ∉ A) ∧ (x ∉ B)\) \(⟺ (x ∈ A^c) ∧ (x ∈ B^c)\) \(⟺ x ∈ (A^c ∩ B^c)\) よって、(A ∪ B)^c = A^c ∩ B^c が成り立ちます。□

(注意: 他の法則の証明は省略し、演習問題とします。)

直積: 集合 A と B の直積（Cartesian product）は、順序対の集合として定義されます。 \(A \times B = \{(a, b) \mid a \in A, b \in B\}\)
例: \(\{1, 2\} \times \{a, b\} = \{(1, a), (1, b), (2, a), (2, b)\}\)

n 個の集合の直積は次のとおりです。 \(A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_i \in A_i\ (i = 1, \ldots, n)\}\) とくに A × A × … × A (n 回) を \(A^n\) と書きます。

1.1.3 集合の濃度 (可算と非可算)

集合の濃度（cardinality）または基数は、集合の「大きさ」や「要素数」を表す概念です。

  • 有限集合：要素数が自然数で表される集合。\(\lvert A\rvert = n\) と表記します。
  • 無限集合：有限でない集合。

定義 1.1 集合 A が可算（countable）であるとは、A の要素の個数が有限であるか、または A の要素全体を自然数 1, 2, 3, … と順番に番号付けできる（つまり自然数の集合 ℕ と一対一対応がつく）場合をいいます。有限集合はすべて可算です。無限集合のうち可算であるものを可算無限集合（countably infinite set）と呼びます。

可算集合の例は次のとおりです。

  • すべての有限集合
  • 自然数の集合 ℕ
  • 整数の集合 ℤ (0, 1, -1, 2, -2, … のように番号付け可能)

定理 1.3 有理数の集合 ℚ は可算です。

証明の概略：正の有理数を p/q (p, q は互いに素な自然数) としたとき、p+q の値が小さい順に、p+q の値が同じものについては p の値が小さい順に並べることで、すべての正の有理数を列挙できます。 以下にその列挙の様子を図示します。矢印の順にたどることで、すべての正の有理数を網羅的に数え上げることができます。

有理数の可算性の証明

この図では、(k) は k 番目に数えられる有理数を示します。分母と分子の和 (p+q) が小さいものから順に、和が同じ場合は分子 p が小さいものから順に並べています。既約でない分数 (例: 2/2) はスキップします。 この列挙により、正の有理数全体に番号を振ることができます。負の有理数と0を含めても、同様の手法（たとえば、0, 正の有理数1, 負の有理数1, 正の有理数2, … のように交互に並べる）で列挙可能であり、全体の可算性が保たれます。□

非可算集合（uncountable set）は、可算でない無限集合です。

定理 1.4（Cantor）実数の集合 ℝ は非可算です。

直感的理解 この証明は「対角化論法」と呼ばれ、「すべての実数を数え上げることは不可能」であることを示します。想像してみてください：もし実数がすべて番号付けできるなら、それらを表に並べることができるはずです。しかし、この表から「表に載っていない実数」を必ず作ることができるのです。

証明の戦略

  1. 仮定：実数は可算だと仮定（背理法）
  2. 構成：仮定に基づいて実数の一覧表を作成
  3. 対角化：この表から「表に載っていない実数」を構成
  4. 矛盾：仮定に矛盾するため、実数は非可算

証明：背理法によります。ℝ が可算であると仮定し、実数を \(r_1, r_2, r_3, \ldots\) と列挙できるとします。 区間 [0, 1] の実数の小数展開を考えます。

r1 = 0.d11d12d13d14d15...
r2 = 0.d21d22d23d24d25...
r3 = 0.d31d32d33d34d35...
r4 = 0.d41d42d43d44d45...
r5 = 0.d51d52d53d54d55...
...

対角化の技法：表の対角線上の数字（\(d_{11}, d_{22}, d_{33}, \ldots\)）を変更して、新しい実数を作ります。

ここで、新しい実数 \(r = 0.e_1e_2e_3\ldots\) を以下のように構成します。 各 \(i\) について、\(e_i \ne d_{ii}\) となるように選びます（例：\(d_{ii} = 5\) なら \(e_i = 6\)、\(d_{ii} \ne 5\) なら \(e_i = 5\)）。

なぜこれが矛盾を生むか

  • この r は [0, 1] の実数です
  • しかし、すべての \(i\) に対して \(r\) は \(r_i\) と異なります（第 \(i\) 桁が異なります）
  • これは、ℝ のすべての実数が列挙されたという仮定に矛盾します

したがって、ℝ は非可算です。□

この証明の意義 この対角化論法は、計算機科学の多くの重要な不可能性証明（停止問題や、ある種の問題がアルゴリズムでは解けないことを示す証明など）の基礎となっています。「すべてを数え上げることはできない」という基本的な限界を示すだけでなく、第2章以降で学ぶ計算理論の諸結果にも繰り返し現れる重要なアイデアです。

1.2 論理学

論理学は、正しい推論の形式を研究する分野です。

1.2.1 命題論理

命題（proposition）とは、真 (true, T, 1) または偽 (false, F, 0) のいずれかの値をとる文です。 例：「地球は丸い」（真）、「1 + 1 = 3」（偽）

命題を変数 p, q, r, … で表し、論理演算子を用いて複合命題を作ります。 主な論理演算子は次のとおりです。

  1. 否定（negation）: ¬p（「p でない」）
  2. 論理積（conjunction）: p ∧ q（「p かつ q」）
  3. 論理和（disjunction）: p ∨ q（「p または q」）
  4. 含意（implication）: p → q（「p ならば q」）。p が偽であれば q の真偽に関わらず真です。
  5. 同値（equivalence）: p ↔ q（「p と q は同値」）。(p → q) ∧ (q → p) と同じです。

真理値表（truth table）は、命題の真理値を体系的に示す表です。

p q ¬p p ∧ q p ∨ q p → q p ↔ q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T

論理的同値: 二つの論理式 φ と ψ が論理的に同値（logically equivalent）であるとは、いかなる真理値割当に対しても同じ真理値をとることであり、φ ≡ ψ と書きます。 重要な論理的同値関係は次のとおりです。

  1. 二重否定: ¬¬p ≡ p
  2. 交換法則: p ∧ q ≡ q ∧ p, p ∨ q ≡ q ∨ p
  3. 結合法則: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r), (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
  4. 分配法則: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
  5. 吸収法則: p ∧ (p ∨ q) ≡ p, p ∨ (p ∧ q) ≡ p
  6. 冪等法則: p ∧ p ≡ p, p ∨ p ≡ p
  7. ド・モルガンの法則: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
  8. 含意の書き換え: p → q ≡ ¬p ∨ q
  9. 対偶: p → q ≡ ¬q → ¬p

例：論理式 (p → q) ∧ p ∧ ¬q が矛盾式であることを示す。

p → q ≡ ¬p ∨ q を用いると、 \[ (p \to q) \land p \land \lnot q \equiv (\lnot p \lor q) \land p \land \lnot q \] である。分配法則を用いて \[ (¬p ∨ q) ∧ p ≡ (¬p ∧ p) ∨ (q ∧ p) ≡ ⊥ ∨ (p ∧ q) ≡ p ∧ q \] を得る。したがって \[ (p \to q) \land p \land \lnot q \equiv (p \land q) \land \lnot q \equiv p \land (q \land \lnot q) \equiv p \land \bot \equiv \bot \] となるため、この論理式はどの真理値割り当てでも偽となる、すなわち矛盾式である。このように、論理的同値の一覧は実際の論理式変形や証明において有用な道具として機能する。

定義 1.3

  • 恒真式（tautology）：すべての真理値割当で真となる論理式。例: p ∨ ¬p
  • 矛盾式（contradiction）：すべての真理値割当で偽となる論理式。例: p ∧ ¬p
  • 充足可能式（satisfiable formula）：真となるような真理値割当が少なくとも一つ存在する論理式。

定理 1.5 論理式 \(\varphi\) が恒真式である \(\Leftrightarrow\) \(\lnot\varphi\) が矛盾式である。

証明：φ が恒真式であれば、すべての真理値割当でφが真となる。したがって、すべての真理値割当で¬φが偽となるため、¬φは矛盾式である。逆向きも同様に証明できる。□

1.2.2 述語論理

命題論理では扱えない「すべての x について…」「ある x が存在して…」といった表現を扱うための論理です。 述語（predicate）P(x) は、変数 x に特定の値を代入すると命題となるものです。 例: P(x) = 「x は偶数である」

量化子（quantifier）

  • ∀（全称量化子）：「すべての x について」
  • ∃（存在量化子）：「ある x が存在して」

例:

  • ∀x ∈ ℕ, P(x) : 「すべての自然数 x について P(x) が成り立つ」
  • \(\exists x \in \mathbb{R},\ x^2 = 2\) : 「\(x^2 = 2\) となる実数 \(x\) が存在する」

述語論理の構文:

  • 項（term）：個体変数、個体定数、または関数記号と項から構成されます。
    • 個体変数は項です。
    • 個体定数は項です。
    • \(t_1, \ldots, t_n\) が項で \(f\) が \(n\) 項関数記号なら、\(f(t_1, \ldots, t_n)\) は項です。
  • 原子論理式（atomic formula）：述語記号と項から構成されます。
    • \(t_1, \ldots, t_n\) が項で \(P\) が \(n\) 項述語記号なら、\(P(t_1, \ldots, t_n)\) は原子論理式です。
  • 論理式（formula）：原子論理式や論理結合子、量化子を用いて帰納的に定義されます。
    • 原子論理式は論理式です。
    • φ, ψ が論理式なら、¬φ, φ ∧ ψ, φ ∨ ψ, φ → ψ, φ ↔ ψ は論理式です。
    • φ が論理式で x が変数なら、∀x φ, ∃x φ は論理式です。

定義 1.4

  • 束縛変数（bound variable）：量化子の作用域内にある変数です。
  • 自由変数（free variable）：束縛されていない変数です。 例：∀x (P(x) → Q(x, y)) において、x は束縛変数、y は自由変数です。

解釈（interpretation）I は以下から構成されます。

  • 空でない集合 D（議論領域）
  • 各定数記号 c に対する D の要素 I(c)
  • 各 n 項関数記号 f に対する関数 \(I(f): D^n \to D\)
  • 各 n 項述語記号 P に対する関係 \(I(P) \subseteq D^n\)

ある解釈 I のもとで論理式 φ が真であるとき、I ⊨ φ と書きます。

  • 妥当式（valid formula）：すべての解釈で真となる論理式。
  • 充足可能式（satisfiable formula）：真となる解釈が少なくとも一つ存在する論理式。

1.3 証明技法

数学的証明は、前提から結論を論理的に導出する厳密な議論です。コンピュータサイエンスでは、アルゴリズムの正当性、計算複雑性の解析、システムの性質の検証など、さまざまな場面で証明が必要となります。

1.3.1 直接証明

直接証明（direct proof）は、前提から出発し、論理的推論の連鎖により結論を導くもっとも基本的な証明方法です。 命題「P ならば Q」（P → Q）の直接証明は次のとおりです。

  1. P を仮定します。
  2. 定義、公理、既知の定理などを用いて論理的ステップを積み重ねます。
  3. 最終的に Q を導出します。

例 1.1 「n が偶数ならば \(n^2\) も偶数である」を証明せよ。

証明：n を偶数とします。偶数の定義より、ある整数 k が存在して \(n = 2k\) と表せます。 このとき、\(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\) となります。 \(2k^2\) は整数なので、\(n^2\) は 2 の倍数、すなわち偶数です。□

1.3.2 対偶による証明

命題 P → Q を証明する代わりに、その対偶（contrapositive）¬Q → ¬P を証明する方法です。 定理 1.6 \(P \to Q\) と \(\lnot Q \to \lnot P\) は論理的に同値である。

証明：真理値表により確認できる。また、P → Q ≡ ¬P ∨ Q および ¬Q → ¬P ≡ ¬(¬Q) ∨ ¬P ≡ Q ∨ ¬P ≡ ¬P ∨ Q より明らか。□

例 1.2 「\(n^2\) が偶数ならば n も偶数である」を証明せよ。

なぜ対偶を使うのか？ 元の命題を直接証明しようとすると「\(n^2\) が偶数」という仮定から「n が偶数」を導くのは困難です。しかし対偶「n が奇数ならば \(n^2\) も奇数」は奇数の定義を使って直接的に示すことができます。

証明（対偶による）：対偶「n が奇数ならば \(n^2\) も奇数である」を証明します。 n を奇数とすると、奇数の定義により、ある整数 k が存在して n = 2k + 1 と表せます。 このとき、 \[ \begin{aligned} n^2 &= (2k + 1)^2 \
&= (2k)^2 + 2(2k)(1) + 1^2 \quad (\text{二項定理}) \
&= 4k^2 + 4k + 1 \
&= 2(2k^2 + 2k) + 1 \end{aligned} \]

\(2k^2 + 2k\) は整数なので、\(n^2\) は「2×(整数) + 1」の形、すなわち奇数です。

対偶が成立したので、元の命題も成立します。□

対偶による証明が有効な場面

  • 元の命題の否定が扱いやすい場合
  • 無限性や存在性に関する命題
  • 「～でない」ことを直接示すのが困難な場合

1.3.3 背理法

命題 P を証明するために、¬P を仮定し、そこから矛盾を導く方法です。 論理的根拠：¬P → ⊥（矛盾）が真であれば、¬P は偽でなければならず、したがって P は真となります。

なぜ背理法が有効なのか？ 背理法は「論理的完全性」に基づいています。論理では、命題は真か偽のどちらかでなければなりません（排中律）。もし命題の否定を仮定して矛盾が導かれるなら、その否定は偽であり、したがって元の命題は真でなければなりません。この手法は、直接証明が困難な存在性や無限性に関する命題で特に力を発揮します。

具体例1：√2 は無理数であることを証明せよ。

証明（背理法） √2 が有理数であると仮定します。このとき、互いに素な正整数 p, q が存在して √2 = p/q と表せます。

Step 1: 両辺を2乗すると、次の式が得られます。 \(2 = p^2/q^2\) したがって、\(2q^2 = p^2\) が成り立ちます。

Step 2: \(p^2\) の性質を調べます。 \(2q^2 = p^2\) より、\(p^2\) は偶数です。 ところで、「\(n^2\) が偶数ならば n も偶数」（例1.2で証明済み）なので、p は偶数です。

Step 3: pが偶数であることを利用します。 p が偶数なので、ある整数 k が存在して p = 2k と表せます。 これを \(2q^2 = p^2\) に代入すると、次の式が得られます。 \(2q^2 = (2k)^2 = 4k^2\) したがって、\(q^2 = 2k^2\) が成り立ちます。

Step 4: \(q^2\) の性質を調べます。 \(q^2 = 2k^2\) より、\(q^2\) は偶数です。 再び「\(n^2\) が偶数ならば n も偶数」を用いると、q は偶数です。

Step 5: 矛盾を導きます。 p と q が共に偶数であることは、「p と q が互いに素」という仮定に矛盾します。

結論: 仮定が誤りなので、√2 は無理数です。□

具体例2（計算機科学での応用）：停止問題の判定不可能性（簡略版）

命題：「任意のプログラムについて、そのプログラムが停止するかどうかを判定するアルゴリズムは存在しない」

証明の概略（背理法） そのような万能判定アルゴリズム HALT(P, I) が存在すると仮定します。

  • P: プログラムのコード
  • I: 入力データ
  • 戻り値: プログラムPが入力Iで停止するなら TRUE、無限ループなら FALSE

この HALT を使って、次のような「自己言及的」プログラム PARADOX を考えます。

PARADOX(P):
  if HALT(P, P) == TRUE:
    infinite_loop()  // 無限ループに入る
  else:
    return "finished"  // 正常終了

ここで、PARADOX(PARADOX) を実行するとどうなるでしょうか？

  • HALT(PARADOX, PARADOX) が TRUE を返す場合 PARADOX は無限ループに入る → しかし HALT は「停止する」と判定した（矛盾）

  • HALT(PARADOX, PARADOX) が FALSE を返す場合
    PARADOX は正常終了する → しかし HALT は「停止しない」と判定した（矛盾）

どちらの場合も矛盾が生じるため、そのような万能判定アルゴリズムは存在できません。□

背理法が特に有効な場面

  • 無限性や存在性に関する命題（無理数の証明など）
  • 一意性の証明（「～は高々1個しか存在しない」）
  • 不可能性の証明（停止問題、4色定理の反例が存在しないことなど）
  • 最小性・最大性の証明（「これより小さい/大きいものは存在しない」）

1.3.4 数学的帰納法

自然数 \(n\) に関する命題 \(P(n)\) がすべての \(n \ge n_0\) で成り立つことを証明する強力な手法です。

なぜ数学的帰納法が成り立つのか？ 数学的帰納法は、自然数の性質に基づいています。自然数は1から始まり、次々と後続者（+1）を取ることで構成されます。基底段階で最初の場合が成り立ち、帰納段階で「一つが成り立てば次も成り立つ」ことを示せば、ドミノ倒しのように無限に続くすべてのケースで命題が成立することが保証されます。この2つのステップで無限のケースを証明できるのが数学的帰納法の驚くべき力です。

手順

  1. 基底段階（base case）：\(P(n_0)\) が真であることを示します。
  2. 帰納段階（inductive step）：任意の \(k \ge n_0\) に対して、\(P(k) \to P(k+1)\) を示します（\(P(k)\) を帰納法の仮定といいます）。

例 1.4 すべての n ≥ 1 に対して、1 + 2 + … + n = n(n+1)/2 が成り立つことを証明せよ。

計算機科学での応用：この公式は、二重ループのアルゴリズムの計算量解析やデータ構造の解析で頻繁に使用されます。

なぜこの公式が重要か？ この公式は、アルゴリズムの計算量解析で頻繁に現れます。例えば、n個の要素について「すべてのペア」を調べるアルゴリズム（例：選択ソート、単純な重複検出）では、1回目にn-1回、2回目にn-2回、…、最後に1回の比較を行います。これは正に 1 + 2 + … + (n-1) = (n-1)n/2 \(\approx n^2/2\) の計算量になります。

証明：P(n) を「1 + 2 + … + n = n(n+1)/2」とします。

基底段階：n = 1 のとき

  • 左辺 = 1
  • 右辺 = 1(1+1)/2 = 1×2/2 = 1
  • よって P(1) は成立します。

帰納段階：k ≥ 1 に対して P(k) が成り立つと仮定します。すなわち、次のとおりです。 1 + 2 + … + k = k(k+1)/2 （帰納法の仮定）

この仮定のもとで、P(k+1) が成り立つことを示します。つまり、次のとおりです。 \(1 + 2 + … + k + (k+1) = (k+1)((k+1)+1)/2 = (k+1)(k+2)/2\)

計算 1 + 2 + … + k + (k+1) \(= (1 + 2 + … + k) + (k+1)\) = k(k+1)/2 + (k+1) （帰納法の仮定を使用） = (k+1)[k/2 + 1] （(k+1) を因数に出す） \(= (k+1)[(k + 2)/2] （k/2 + 1 = (k + 2)/2）\) = (k+1)(k+2)/2 （整理）

これは P(k+1) の形そのものです。

結論：数学的帰納法により、すべての n ≥ 1 で命題が成立します。□

証明の本質

  • 基底段階：「最初のドミノ（n=1）は倒れる」
  • 帰納段階：「k番目のドミノが倒れれば、(k+1)番目も倒れる」
  • 結論：「すべてのドミノが倒れる」

アルゴリズムでの応用例

# 選択ソートの比較回数の解析
def selection_sort(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n):
        for j in range(i+1, n):
            comparisons += 1
            if arr[j] < arr[i]:
                arr[i], arr[j] = arr[j], arr[i]
    return comparisons

# 比較回数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2

強い帰納法（strong induction）では、帰納段階で \(P(n_0), P(n_0+1), \ldots, P(k)\) すべてを仮定して \(P(k+1)\) を示します。

例 1.5 すべての n ≥ 2 は素数の積として表せることを証明せよ。

証明（強い帰納法）：P(n) を「n は素数の積として表せる」とします。 基底：n = 2 のとき、2 自身が素数なので成立します。 帰納段階：2 ≤ m ≤ k なるすべての m が素数の積として表せると仮定します。 k+1 について考えます。

  • k+1 が素数なら、それ自身が素数の積表示です。
  • k+1 が合成数なら、k+1 = ab (1 < a, b < k+1) と表せます。 仮定より 2 ≤ a ≤ k かつ 2 ≤ b ≤ k なので、a と b は帰納法の仮定を満たします。 よって、a と b は素数の積として表せるので、k+1 も素数の積として表せます。 したがって、すべての n ≥ 2 は素数の積として表せます。□

1.4 関係と関数

1.4.1 関係

定義 1.5 集合 A から集合 B への二項関係（binary relation）\(R\) は、直積 \(A \times B\) の部分集合です。

(a, b) ∈ R のとき、aRb と表記します。 とくに、A = B のとき、R を A 上の関係といいます。

例

  • 整数の集合 ℤ 上の「より小さい」関係：\(< = \{(a, b) \mid a, b \in \mathbb{Z}, a < b\}\)
  • 集合 A の冪集合 \(\mathcal{P}(A)\) 上の「部分集合」関係：\(\subseteq = \{(X, Y) \mid X, Y \in \mathcal{P}(A), X \subseteq Y\}\)

集合 A 上の関係 R について、以下の性質を考えます。

  • 反射的（reflexive）: ∀a ∈ A, aRa
  • 対称的（symmetric）: ∀a, b ∈ A, aRb → bRa
  • 反対称的（antisymmetric）: ∀a, b ∈ A, (aRb ∧ bRa) → a = b
  • 推移的（transitive）: ∀a, b, c ∈ A, (aRb ∧ bRc) → aRc

定義 1.6

  • 同値関係（equivalence relation）: 反射的、対称的、かつ推移的な関係です。
  • 半順序関係（partial order relation）: 反射的、反対称的、かつ推移的な関係です。

例

  • 整数の集合 ℤ 上の合同関係 (a ≡ b (mod m)) は同値関係です。
  • 冪集合 \(\mathcal{P}(A)\) 上の ⊆ は半順序関係です。
  • ≤ は反射的、反対称的、推移的（全順序）です。

計算機科学における具体例

同値関係の例

  • プログラムの意味的同値性：同じ入力に対して同じ出力を生成するプログラムの関係
  • データ型の互換性：同じデータ型を持つ変数の関係
  • 状態の同値性：プログラムの実行状態において、同じ変数値を持つ状態の関係

半順序関係の例

  • プログラムの依存関係：プログラムAの実行前にプログラムBが実行される必要がある関係
    • 反射的：プログラムは自分自身に依存する（自明な依存）
    • 反対称的：A→B かつ B→A なら A=B（循環依存は同一プログラム）
    • 推移的：A→B かつ B→C なら A→C（間接的依存）
  • コンパイル順序：ソースファイルの依存関係とコンパイル順序
  • バージョン管理：ソフトウェアバージョンの「より新しい」関係

集合 A 上の同値関係 R に対して、要素 a の同値類（equivalence class）を次のように定義します。
\([a] = \{b \in A \mid aRb\}\)

定理 1.7 集合 A 上の同値関係 R に対して、以下が成り立ちます。

  1. ∀a ∈ A, a ∈ [a]（同値類は空でない）
  2. \(aRb ⟺ [a] = [b]\)
  3. [a] ∩ [b] ≠ ∅ → [a] = [b]（同値類は互いに素か、または等しい）
  4. A は同値類の直和として表せる（A の分割を与える）

証明：(1) 反射性より a ∈ [a]。(2) (⇒) aRb なら [a] = [b] を示す。c ∈ [a] とすると aRc。推移性と対称性より bRc、すなわち c ∈ [b]。よって [a] ⊆ [b]。同様に [b] ⊆ [a]。(⇐) [a] = [b] かつ a ∈ [a] = [b] より aRb。(3) と (4) は (2) から従う。□

1.4.2 関数

定義 1.7 集合 A から集合 B への関数（function）f は、以下を満たす関係です。

  • \(\forall a \in A,\ \exists b \in B,\ (a, b) \in f\)（全域性）
  • \(\forall a \in A,\ \forall b_1, b_2 \in B,\ ((a, b_1) \in f \land (a, b_2) \in f) \to b_1 = b_2\)（一意性）

通常、\((a, b) \in f\) を \(f(a) = b\) と書きます。\(f: A \to B\) と表記します。

  • A を f の定義域（domain）といいます。
  • B を f の終域（codomain）といいます。
  • \(\{f(a) \mid a \in A\}\) を f の値域（range）といいます。

定義 1.8 関数 \(f: A \to B\) について

  • 単射（injection, one-to-one）: \(\forall a_1, a_2 \in A,\ f(a_1) = f(a_2) \to a_1 = a_2\) （異なる要素は異なる要素に写る）
  • 全射（surjection, onto）: \(\forall b \in B,\ \exists a \in A,\ f(a) = b\) （終域のすべての要素が写される）
  • 全単射（bijection, one-to-one correspondence）: f が単射かつ全射であることです。

例 1.7

  • f: ℤ → ℤ, f(x) = 2x は単射ですが全射ではありません（奇数が写されません）。
  • f: ℝ → ℝ, \(f(x) = x^3\) は全単射です。
  • f: ℝ → ℝ, \(f(x) = x^2\) は単射ではありません (例: f(2)=f(-2)=4)。また、終域を ℝ とすると全射でもありません (負の値を取りません)。

定義 1.9 関数 \(f: A \to B\) と \(g: B \to C\) の合成（composition）\(g \circ f: A \to C\) を次のように定義します。

任意の \(a \in A\) に対して \((g \circ f)(a) = g(f(a))\) と定義します。

定理 1.8

  1. 結合法則：(h ∘ g) ∘ f = h ∘ (g ∘ f)
  2. f, g が単射なら g ∘ f も単射です。
  3. f, g が全射なら g ∘ f も全射です。
  4. f, g が全単射なら g ∘ f も全単射です。

定義 1.10 関数 \(f: A \to B\) が全単射のとき、逆関数（inverse function）\(f^{-1}: B \to A\) が存在し、次の関係が成り立ちます。

\(f^{-1}(b) = a \iff f(a) = b\) このとき、以下が成り立ちます。

  • \(f^{-1} \circ f = \mathrm{id}_A\)（A 上の恒等関数）
  • \(f \circ f^{-1} = \mathrm{id}_B\)（B 上の恒等関数）

1.5 グラフ理論の基礎

グラフ理論は、点（頂点）とそれらを結ぶ線（辺）からなる構造を扱う分野です。

1.5.1 グラフの定義

定義 1.11 グラフ（graph）\(G\) は、頂点集合 \(V(G)\) と辺集合 \(E(G)\) の組 \(G = (V, E)\) です。

  • 無向グラフ（undirected graph）: E は V の要素の非順序対の集合（または2要素部分集合）。

  • 有向グラフ（directed graph, digraph）: E は V の要素の順序対の集合。

  • 無向グラフでは辺を {u, v} または単に uv と表記します。

  • 有向グラフでは辺を (u, v) または u → v と表記します（u から v への辺）。

  • ループ（loop）: (v, v) の形の辺。
  • 多重辺（multiple edges）: 同じ頂点対を結ぶ複数の辺。
  • 単純グラフ（simple graph）: ループも多重辺も持たないグラフ。とくに断りがなければ単純グラフを考えます。

グラフ理論の基本例

定義 1.12 無向グラフ G において、頂点 v の次数（degree）\(\deg(v)\) は、v に接続する辺の数です。

有向グラフ G において、頂点 v の次数は次のとおりです。

  • 入次数（in-degree）：\(\deg^{-}(v) = \lvert \{u \in V \mid (u, v) \in E\}\rvert\)
  • 出次数（out-degree）：\(\deg^{+}(v) = \lvert \{u \in V \mid (v, u) \in E\}\rvert\)

定理 1.9（握手補題）無向グラフ \(G = (V, E)\) において、次が成り立ちます。

\(\sum_{v \in V} \deg(v) = 2\lvert E\rvert\) （すべての頂点の次数の和は、辺の数の2倍に等しい） 系：次数が奇数である頂点の数は偶数個です。

1.5.2 道と閉路

定義 1.13 グラフ \(G\) における頂点の列 \(v_0, v_1, \ldots, v_k\) について

  1. 歩道（walk）：各 \(i\) で \(v_i v_{i+1} \in E\)（有向グラフの場合は \((v_i, v_{i+1}) \in E\)）
    • 歩道の長さは辺の数 k です。
  2. 道（path）：すべての頂点が異なる歩道です。
  3. 閉路（cycle, circuit）：\(v_0 = v_k\) であり、\(v_0, \ldots, v_{k-1}\) が道である長さ \(k \ge 1\) の歩道です（単純グラフでは \(k \ge 3\)）。

定義 1.14

  • 無向グラフ G が連結（connected）：任意の2頂点間に道が存在します。
  • 有向グラフ G が強連結（strongly connected）：任意の2頂点間に有向道が存在します。
  • 有向グラフ G が弱連結（weakly connected）：基礎となる無向グラフ（辺の向きを無視したグラフ）が連結です。

1.5.3 木

定義 1.15 木（tree）は、連結で閉路を持たない無向グラフです。

森（forest）は、閉路を持たない無向グラフ（木の集まり）です。

定理 1.10 n 頂点のグラフ G について、以下は同値です。

  1. G は木です。
  2. G は連結で、辺数は n-1 です。
  3. G は閉路を持たず、辺数は n-1 です。
  4. G の任意の2頂点間に道がちょうど1つ存在します。
  5. G は閉路を持たないが、任意の辺を加えると閉路が1つできる最小のグラフです。
  6. G は連結だが、任意の辺を除去すると非連結になる最大のグラフです。

証明の概略 （1→2）木は連結である。辺数については頂点数に関する帰納法で示せる。n=1 では自明。n≥2 で成立すると仮定し、n+1 頂点の木 T を考える。葉（次数1の頂点）vを除去すると、n 頂点の木 \(T^{\prime}\) ができ、帰納法の仮定により \(\lvert E(T^{\prime})\rvert = n-1\)。よって \(\lvert E(T)\rvert = \lvert E(T^{\prime})\rvert + 1 = n\)。 （2→3）連結で n-1 本の辺を持つグラフに閉路があるとすると、閉路上の1辺を除去しても連結性が保たれ、n-2 本の辺で連結グラフとなる。しかし n≥2 のとき、n 頂点の連結グラフには最低 n-1 本の辺が必要なので矛盾。 （3→4）と他の同値性も同様に証明できる。□

1.5.4 その他のグラフの概念

定義 1.16 グラフ G が二部グラフ（bipartite graph）であるとは、

頂点集合 V を \(V_1\) と \(V_2\) の2つの互いに素な部分集合に分割でき（\(V = V_1 \cup V_2\) かつ \(V_1 \cap V_2 = \emptyset\)）、 すべての辺が \(V_1\) と \(V_2\) の間を結ぶことです。 \((V_1, V_2)\) を二部グラフの部集合（partite sets）といいます。

定理 1.11 グラフ \(G\) が二部グラフ \(\Leftrightarrow\) \(G\) は奇数長の閉路を持ちません。

定義 1.17 n 頂点の完全グラフ（complete graph）\(K_n\) は、

任意の2頂点間に辺が存在する単純グラフです。

  • 辺数：\(\lvert E(K_n)\rvert = n(n-1)/2\)

定義 1.18 m 頂点と n 頂点の部集合を持つ完全二部グラフ（complete bipartite graph）\(K_{m,n}\) は、

部集合 \(V_1\)（\(\lvert V_1\rvert = m\)）と \(V_2\)（\(\lvert V_2\rvert = n\)）を持ち、\(V_1\) の各頂点と \(V_2\) の各頂点の間に辺が存在する二部グラフです。

  • 辺数：\(\lvert E(K_{m,n})\rvert = mn\)

まとめ

  • 集合・論理・証明は理論計算機科学の基盤であり、後続章の定義・定理の理解に必須
  • 関数と関係は計算や写像の形式化に不可欠で、後のオートマトンや複雑性の議論で頻出
  • グラフの基礎はアルゴリズム設計・解析（章8以降）で直接利用される

次章への橋渡し

ここでそろえた集合・論理・証明の言葉は、第2章で「計算」を機械として定義するための前提になります。次章ではこの土台の上でチューリング機械を導入し、アルゴリズム一般をどこまで厳密に扱えるかを見ます。

補助資料を併用するなら、手を動かす確認は 付録B の第1章節、実世界との接続は 付録E の第1章節、理解確認は 付録F の第1章節を参照してください。

参考文献と次の一歩

  • 図版の再参照: 本章の図をまとめて見返したいときは 付録H: 図版ガイドと図一覧 を参照してください。
  • 入門: Kenneth H. Rosen, 『Discrete Mathematics and Its Applications』. 集合・論理・関係・グラフを広く復習したいときの標準的な入口です。
  • 証明技法: Daniel J. Velleman, 『How to Prove It: A Structured Approach』. 直接証明・対偶・背理法・帰納法の読み書きを集中的に補いたい読者に向いています。
  • 出典メモ: 本章の記法と証明技法は、離散数学と初等数理論理の標準的な導入に依拠しています。記号で迷ったときは 付録A を辞書として併用してください。
  • 次の一歩: 第2章へ進む前に証明の読み方に不安があれば、付録C（第1章） を使って基本問題を回収してください。グラフの話題を先に深めたい場合は第8章を拾い読みしても構いません。

    章末問題

  • 代表演習と詳細解答は 付録C（第1章） を参照。

取り組み方ガイド

迷ったら次の表の順で進め、詰まったら「主に戻る節」にある定義・例題・注意点を先に見直してください。

区分 推奨順 主に戻る節 使い方
基礎問題 1番目 1.1〜1.5 定義・記法・証明の基本確認に使う
計算機科学応用問題 2番目 1.1, 1.3, 1.5 数学的基礎を計算機科学の文脈へ接続する
発展問題 3番目 1.1〜1.5 証明を自力で再構成する
探究課題 4番目 1.1〜1.5 比較軸を決めて論点を整理する
実装課題 5番目 1.1, 1.4, 1.5 仕様を先に書いてから実装する

基礎問題

  1. 集合 A = {1, 2, 3, 4} に対して、以下を求めよ。 (a) \(\mathcal{P}(A)\) の要素数 (b) A × A の要素数 (c) A 上の反射的関係の個数

  2. ド・モルガンの法則 (A ∩ B)^c = A^c ∪ B^c を証明せよ。

  3. 関数 f: ℝ → ℝ, f(x) = 2x + 1 について、次に答えよ。 (a) f は単射であることを示せ (b) f は全射であることを示せ (c) f の逆関数を求めよ

  4. グラフ \(K_4\) について、次に答えよ。 (a) 頂点数と辺数を求めよ (b) 各頂点の次数を求めよ (c) 握手補題が成り立つことを確認せよ

  5. 数学的帰納法を用いて、すべての \(n \ge 1\) に対して \(1^2 + 2^2 + \cdots + n^2 = n(n+1)(2n+1)/6\) が成り立つことを証明せよ。

計算機科学応用問題

  1. アルゴリズム解析：バブルソートの比較回数について (a) 最悪の場合の比較回数を数学的帰納法で求めよ (b) 平均的な場合の比較回数を推定せよ

  2. データ構造：n要素のハッシュテーブルについて (a) 完全ハッシュ関数の個数を集合論的に表現せよ (b) 衝突が発生する確率を計算せよ

  3. 再帰アルゴリズム：フィボナッチ数列 F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1 について (a) \(F(n) \ge \varphi^{n-2}\)（\(n \ge 2\), \(\varphi = (1+\sqrt{5})/2\)）を数学的帰納法で証明せよ (b) 単純再帰実装の時間計算量を論理的に推論せよ

  4. グラフ理論：n 個のプロセスからなる分散システムについて (a) 各プロセス間の通信を辺で表現したグラフを考える。全てのプロセスが直接通信可能な場合のグラフ構造を述べよ (b) 最小の通信回数でブロードキャストを実現するグラフ構造を求めよ

発展問題

  1. \(n^3 - n\) は常に6の倍数であることを数学的帰納法で証明せよ。

  2. 関数 f: ℝ → ℝ, \(f(x) = x^3 - x\) について、次に答えよ。 (a) f は単射か？ (b) f は全射か？ (c) f の値域を求めよ

  3. 可算無限個の可算集合の和集合は可算であることを証明せよ。

  4. 集合 A 上の関係 R が推移的であることと、R ∘ R ⊆ R が成り立つことが同値であることを示せ。

  5. n 頂点の木において、次数が k の頂点が \(n_k\) 個あるとき、\(n_1 = 2 + \sum_{k \ge 3}(k-2)n_k\) が成り立つことを証明せよ。（\(n_1\) は葉の数）

探究課題

  1. グラフの彩色問題について調査し、4色定理の歴史とコンピューターによる証明の意義について論ぜよ。

  2. Cantor の対角線論法を用いて、区間 (0,1) の実数の集合が非可算であることを証明せよ。さらに、この手法が集合論においてどのような意義を持つかを調べよ。

  3. 同値関係と分割の関係について詳しく調べ、商集合の概念とその応用例を調査せよ。

実装課題

1. 集合演算を実装せよ

以下の機能を含むこと。

  • 和集合、共通部分、差集合
  • 冪集合の生成
  • 直積の計算
class SetOperations:
    def __init__(self, elements):
        self.elements = set(elements)

    def union(self, other_set):
        # 和集合を実装
        pass

    def intersection(self, other_set):
        # 共通部分を実装
        pass

    def difference(self, other_set):
        # 差集合を実装
        pass

    def power_set(self):
        # 冪集合を実装
        pass

    def cartesian_product(self, other_set):
        # 直積を実装
        pass

2. グラフの基本アルゴリズムを実装せよ

  • 隣接リストまたは隣接行列によるグラフ表現
  • 幅優先探索 (BFS)
  • 深さ優先探索 (DFS)
  • 連結成分の検出
  • 二部グラフの判定

3. 関係の性質を判定するプログラムを作成せよ

与えられた関係が反射的、対称的、推移的かどうかを判定し、同値関係や半順序関係かを判断する機能を実装せよ。

Edit this page on GitHub