第3章 証明技法
章間ナビゲーション
この章で使う記号
| 記号 | 意味 |
|---|---|
P ⇒ Q |
P から Q が従う |
¬Q ⇒ ¬P |
対偶 |
∀n ∈ N |
自然数全体に対する主張 |
Base |
帰納法の基底部 |
Step |
帰納法の帰納ステップ |
I(k) |
ループ不変条件や帰納法の仮定を表す記号 |
⊥ |
矛盾を表すことがある記号 |
この章で解消する詰まりどころ
理論計算機科学の本文では、定義・補題・定理・証明が連続します。証明を読めない原因は、難しい式変形ではなく、証明の型を知らないことが多いです。
この章の目的は、次の状態を作ることです。
- 定義を展開して証明を開始できる。
- 直接証明、対偶証明、背理法を選べる。
- 反例で普遍命題を否定できる。
- 数学的帰納法と構造帰納法を使える。
- アルゴリズムの正しさをループ不変条件や帰納法で説明できる。
本体教科書のどこで使うか
- 第1章 数学的基礎
- 第3章 形式言語とオートマトン理論
- 第4章 計算可能性理論
- 第5章 計算複雑性理論
- 第6章 アルゴリズムの数学的解析
- 第7章 データ構造の理論
- 第12章 並行計算の理論
証明は全章で使います。特に、形式言語、計算可能性、複雑性、アルゴリズム解析では、証明の型を知らないと本文を追えません。
1. 証明とは何か
証明とは、仮定と定義から出発し、許された推論だけで結論に到達する説明です。
証明で重要なのは、次の3点です。
- 何を示すかを明確にする。
- どの定義を使うかを明確にする。
- どの証明の型を使うかを選ぶ。
例として、次の命題を考えます。
任意の整数 n について、n が偶数ならば n^2 は偶数である。
この命題は、論理式としては次です。
∀n∈Z, even(n) -> even(n^2)
証明では、まず n を任意に取ります。次に n が偶数であると仮定します。偶数の定義より、ある整数 k が存在して n = 2k と書けます。すると、
n^2 = (2k)^2 = 4k^2 = 2(2k^2)
です。2k^2 は整数なので、n^2 は偶数です。
ここで使ったのは次です。
- 偶数の定義
- 任意の整数に対する証明の始め方
- 含意
P -> Qの証明方法
2. 定義展開
理論計算機科学の証明は、多くの場合、定義を展開すれば進みます。
例:
A ⊆ B かつ B ⊆ C ならば A ⊆ C を証明せよ。
使う定義:
A ⊆ B とは、任意の x について x∈A ならば x∈B であること。
証明:
A ⊆ B かつ B ⊆ C と仮定する。
A ⊆ C を示すには、任意の x について x∈A ならば x∈C を示せばよい。
任意の x を取り、x∈A と仮定する。
A ⊆ B より x∈B である。
B ⊆ C より x∈C である。
したがって x∈A ならば x∈C である。
よって A ⊆ C である。
この証明には高度な発想はありません。定義を展開して、順番につなげています。
定義展開の手順
1. 示すべき結論の定義を展開する。
2. 仮定の定義を展開する。
3. 任意の要素、任意の入力、任意の状態を1つ取る。
4. 仮定から結論へ進む。
3. 直接証明
直接証明は、仮定から結論へまっすぐ進む証明です。
対象は主に次の形です。
P -> Q
証明テンプレート:
P を仮定する。
[定義を展開する]
[必要な計算または推論を行う]
したがって Q が成り立つ。
例：偶数同士の和
命題:
a と b が偶数ならば、a+b も偶数である。
証明:
a と b が偶数であると仮定する。
偶数の定義より、ある整数 m,n が存在して a=2m, b=2n と書ける。
このとき a+b = 2m+2n = 2(m+n) である。
m+n は整数なので、a+b は偶数である。
直接証明が向いている場合
- 結論が定義展開で自然に出る。
- 仮定から式変形できる。
- 「存在する」を示すために具体的な対象を構成できる。
4. 対偶証明
含意 P -> Q は、その対偶 ¬Q -> ¬P と同値です。
対偶証明のテンプレート:
対偶 ¬Q -> ¬P を示す。
¬Q を仮定する。
[定義を展開する]
[必要な推論を行う]
したがって ¬P が成り立つ。
よって元の命題 P -> Q も成り立つ。
例：平方が偶数なら元も偶数
命題:
n^2 が偶数ならば n は偶数である。
直接証明より対偶の方が簡単です。
対偶:
n が偶数でないならば、n^2 は偶数でない。
整数では「偶数でない」は「奇数」です。したがって、
n が奇数ならば n^2 は奇数である。
を示せばよいです。
証明:
n が奇数であると仮定する。
奇数の定義より、ある整数 k が存在して n=2k+1 と書ける。
このとき
n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1
である。
2k^2+2k は整数なので、n^2 は奇数である。
よって対偶が成り立つため、元の命題も成り立つ。
対偶証明が向いている場合
- 結論の否定から仮定の否定へ進みやすい。
- 「〜ならば〜でない」という主張が自然に出る。
- 偶奇、整除、包含関係などで有効。
5. 背理法
背理法は、示したい命題の否定を仮定し、矛盾を導く方法です。
テンプレート:
示したい命題が成り立たないと仮定する。
[推論する]
矛盾が生じる。
したがって、仮定が誤りであり、元の命題が成り立つ。
例：√2 は無理数
命題:
√2 は無理数である。
証明:
√2 が有理数であると仮定する。
すると、互いに素な整数 p,q が存在して √2 = p/q と書ける。ただし q≠0。
両辺を2乗すると 2 = p^2/q^2 なので、p^2 = 2q^2 である。
したがって p^2 は偶数であり、前節の結果より p は偶数である。
p=2r と書ける。
すると 4r^2 = 2q^2 なので、q^2 = 2r^2 であり、q^2 は偶数である。
同様に q も偶数である。
これは p と q が互いに素であることに矛盾する。
したがって √2 は無理数である。
背理法が向いている場合
- 「存在しない」を示したい。
- 否定を仮定すると条件が強くなり、扱いやすくなる。
- 不可能性証明、下界証明、計算不能性の直観に使う。
6. 場合分け
対象を有限個のケースに分け、それぞれで結論を示します。
テンプレート:
場合1: ...
[証明]
場合2: ...
[証明]
...
すべての場合で結論が成り立つので、命題は成り立つ。
例：整数 n について n(n+1) は偶数
任意の整数 n について、n は偶数か奇数です。
nが偶数なら、n(n+1)は偶数を因子に持つので偶数。nが奇数なら、n+1は偶数なので、n(n+1)は偶数。
したがって常に偶数です。
注意
場合分けでは、ケースが漏れていないことと、ケースが対象全体を覆っていることを明示します。
7. 反例
普遍命題 ∀x, P(x) を否定するには、P(x) が成り立たない具体例を1つ示せば十分です。
例:
すべての素数は奇数である。
これは偽です。反例は 2 です。2 は素数ですが、奇数ではありません。
反例で否定できる命題
すべての x について P(x)任意の入力でアルゴリズム A は正しい任意のグラフで性質 P が成り立つ
1つでも失敗例があれば、普遍命題は偽です。
反例で否定できないもの
存在命題 ∃x, P(x) を反例1つで否定することはできません。存在命題を否定するには、すべての候補で P(x) が成り立たないことを示す必要があります。
8. 数学的帰納法
数学的帰納法は、自然数 n に関する命題 P(n) を示す方法です。
テンプレート:
基底部: P(0) または P(1) を示す。
帰納ステップ: 任意の k について P(k) を仮定し、P(k+1) を示す。
したがって、すべての n について P(n) が成り立つ。
例：1+2+…+n
命題:
n ≥ 1 について、1+2+...+n = n(n+1)/2
基底部:
n=1 のとき、左辺は 1、右辺は 1(1+1)/2 = 1。
よって成り立つ。
帰納ステップ:
k ≥ 1 について 1+2+...+k = k(k+1)/2 が成り立つと仮定する。
このとき、
1+2+...+k+(k+1)
= k(k+1)/2 + (k+1)
= (k+1)(k/2 + 1)
= (k+1)(k+2)/2
である。
これは n=k+1 の場合の式である。
したがって P(k) -> P(k+1) が成り立つ。
結論:
数学的帰納法により、すべての n≥1 について成り立つ。
帰納法でよくある誤り
誤り1: 基底部を示さない。
誤り2: P(k) を仮定せずに P(k+1) を示そうとする。
誤り3: P(k) を示しただけで、P(k+1) を示していない。
誤り4: P(k) を使う場所がない。これは帰納法が不要か、証明が欠けている可能性があります。
9. 強い帰納法
強い帰納法では、P(k+1) を示すために P(0), P(1), ..., P(k) をすべて仮定できます。
テンプレート:
基底部を示す。
帰納ステップ:
P(0), P(1), ..., P(k) がすべて成り立つと仮定する。
その仮定から P(k+1) を示す。
例：2以上の整数は素数の積に分解できる
命題:
すべての整数 n≥2 は素数の積として表せる。
証明スケッチ:
n が素数なら、それ自身が素数の積である。
n が合成数なら、n=ab かつ 2≤a<n, 2≤b<n と書ける。
強い帰納法の仮定により、a と b は素数の積に分解できる。
したがって n=ab も素数の積に分解できる。
強い帰納法は、再帰的アルゴリズムや分割統治法の正しさでよく使います。
10. 構造帰納法
構造帰納法は、自然数ではなく、再帰的に定義された対象に対する帰納法です。
対象例:
- 文字列
- 木
- 数式
- 論理式
- プログラムの構文
文字列の例
アルファベット Σ 上の文字列を次のように定義します。
1. ε は文字列である。
2. w が文字列で a∈Σ ならば wa は文字列である。
3. 以上で作られるものだけが文字列である。
文字列の長さ |w| を次のように定義します。
|ε| = 0
|wa| = |w| + 1
示したい命題:
任意の文字列 u,v について |uv| = |u| + |v|
証明は v の構造に関する帰納法で行えます。
基底部:
v=ε のとき、uε = u なので |uε| = |u|。
また |u| + |ε| = |u| + 0 = |u|。
よって成り立つ。
帰納ステップ:
v=w a とする。ただし w は文字列、a∈Σ。
帰納法の仮定として |uw| = |u| + |w| を仮定する。
このとき、
|u(wa)| = |(uw)a| = |uw| + 1 = |u| + |w| + 1 = |u| + |wa|
である。
したがって、任意の v について命題が成り立ちます。
構造帰納法が本体で効く箇所
- 正規表現で定義される言語の性質
- 文法による導出
- 構文木
- 論理式の意味論
- 再帰的定義された計算過程
11. アルゴリズムの正しさとループ不変条件
アルゴリズムの正しさを示すときは、通常、次の2つを分けます。
- 停止すること。
- 停止したとき、正しい答えを返すこと。
ループを含むアルゴリズムでは、ループ不変条件を使います。
ループ不変条件とは、ループの各反復の開始時点で常に成り立つ性質です。
示すこと:
初期化: ループ開始前に不変条件が成り立つ。
保存: ある反復の開始時に不変条件が成り立つなら、次の反復の開始時にも成り立つ。
終了: ループ終了条件と不変条件から、求める正しさが従う。
例：線形探索
LinearSearch(A, x):
for i = 0 to len(A)-1:
if A[i] == x:
return i
return NOT_FOUND
不変条件:
各反復の開始時点で、A[0], ..., A[i-1] には x が存在しない。
初期化:
i=0 のとき、A[0], ..., A[-1] は空範囲なので、x が存在しないという主張は真である。
保存:
反復開始時に A[0], ..., A[i-1] に x が存在しないとする。
もし A[i] == x なら i を返して終了する。
そうでなければ A[i] != x なので、次の反復開始時には A[0], ..., A[i] に x が存在しない。
終了:
ループが最後まで終わった場合、不変条件より A 全体に x は存在しない。
したがって NOT_FOUND は正しい。
12. 証明を書くときのチェックリスト
証明を書いたら、次を確認します。
[ ] 示すべき命題を明記した。
[ ] 任意の対象を1つ取る箇所を書いた。
[ ] 仮定を書いた。
[ ] 使う定義を展開した。
[ ] 結論が何かを途中で見失っていない。
[ ] 存在命題では、具体的な対象または構成方法を示した。
[ ] 普遍命題では、任意性を確保した。
[ ] 帰納法では、基底部と帰納ステップがある。
[ ] アルゴリズムでは、正しさと停止性を分けた。
13. 練習問題
A⊆BかつC⊆DならばA∪C ⊆ B∪Dを証明せよ。aが奇数ならばa^2は奇数であることを証明せよ。abが奇数ならばaとbは奇数であることを対偶で証明せよ。- 任意の整数
nについてn^3-nは3で割り切れることを証明せよ。 2^n ≥ n+1を帰納法で証明せよ。- 文字列
wについて|w|=0ならばw=εを、文字列の定義に基づいて説明せよ。 - 線形探索のループ不変条件を書き、正しさを説明せよ。