論理推論: 帰還法と数学的帰納法 - 証明の2つの強力な武器

ある命題を証明するのが難しい場合、時には反対の方向からアプローチする方がはるかに効果的です。帰謬法（きびゅうほう）は「これが偽だと仮定すると矛盾が生じる、したがって真である」という論理的逆転であり、数学的帰納法は無限の場合を有限のステップで証明するエレガントな方法です。どちらの手法も直接証明が難しい状況で真価を発揮します。

帰謬法 (Proof by Contradiction)

原理

帰謬法の構造はシンプルです：

目標: Pを証明せよ

¬Pを仮定する (Pが偽であると仮定)
¬Pを出発点として論理的推論を進める
矛盾(Contradiction)に到達する — すなわち、Qであり同時に¬Qである状況
結論: ¬Pが偽であるため、Pは真である

数式記号で：

(¬P → ⊥) → P

ここで⊥は矛盾(False)を意味します。

他的な例題：√2は無理数である

定理：√2は無理数である（分数で表現できない）

帰謬法の証明：

① √2が有理数であると仮定する。すなわち、互いに素な整数a, bに対して：

\sqrt{2} = \frac{a}{b} \quad (a, b \text{は互いに素}, b \neq 0)

② 両辺を２乗すると：

2 = \frac{a^2}{b^2} \implies a^2 = 2b^2

③ a²が偶数ならばaも偶数である（奇数の２乗は奇数であるため）。

a = 2kとおくと：

(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2

④ b²が偶数ならばbも偶数である。

⑤ 矛盾：aも偶数、bも偶数 → ２数が公約数2を持つ。ところが、a, bは互いに素であると仮定した。矛盾！

⑥ 結論：仮定（√2が有理数）が偽。したがって√2は無理数である。■

例題2：素数は無限に存在する (ユークリッド)

帰謬法：

① 素数が有限であると仮定：p₁, p₂, …, pₙがすべての素数である

② N = (p₁ × p₂ × … × pₙ) + 1を構成する

③ Nをp₁, p₂, …, pₙのいずれで割っても余りが1 → どの素数でも割り切れない

④ すべての自然数 > 1は素数または素数の積であるが、Nは既存の素数リストのどの素数でも割り切れない → N自体が新しい素数であるか、新しい素数の因数を含む

⑤ 矛盾：p₁, …, pₙがすべての素数であるという仮定に反する

⑥ 結論：素数は無限に存在する。■

論理推論における帰謬法

試験では数学よりも論理パズルの形で頻出します：

例：「Aが犯人でないならば、BとCの双方がアリバイを持っていなければならない。しかし、Bにはアリバイがない。したがって、Aが犯人である。」

構造： ¬A → (B ∧ C)
¬B (Bのアリバイなし)
∴ A (対偶: ¬B → A)

これも帰謬法の応用 — 「Aではない」と仮定するとBとC双方がアリバイを持っていなければならないが、Bがいないため矛盾。したがってAが犯人。

数学的方法 (Mathematical Induction)

原理

数学的帰納法は自然数に関する命題を無限に証明する方法です。

目標: すべての自然数nについてP(n)が成り立つことを証明

[ステップ 1 — 基礎 (Base Case)]: P(1)が成り立つことを示す
[ステップ 2 — 帰納 (Inductive Step)]: P(k)が成り立つと仮定するとき、
P(k+1)も成り立つことを示す
結論: すべての自然数nについてP(n)が成り立つ

比喩：ドミノ

基礎：最初のドミノが倒れる
帰納：k番目のドミノが倒れれば、(k+1)番目も倒れる
結論：すべてのドミノが倒れる

例題：1 + 2 + 3 + … + n = n(n+1)/2

定理：すべての自然数nについて $\sum_{i=1}^(n) i = \frac{n(n+1)}{2}$

証明：

[基礎ステップ] n = 1：

左辺：1
右辺：1×2/2 = 1 ✓

[帰納ステップ] P(k)： $1 + 2 + ... + k = \frac{k(k+1)}{2}$ が成り立つと仮定する。

P(k+1)を示さなければならない： $1 + 2 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$

左辺 = $\frac{k(k+1)}{2} + (k+1)$ [帰納の仮定を使用]

$= (k+1)\left(\frac{k}{2} + 1\right)$

$= (k+1) \cdot \frac{k+2}{2}$

$= \frac{(k+1)(k+2)}{2}$ = 右辺 ✓

結論：数学的帰納法により、すべての自然数nについて成り立つ。■

例題2：2ⁿ > n (n ≥ 1)

[基礎] n = 1：2¹ = 2 > 1 ✓

[帰納] 2ᵏ > kが成り立つと仮定する。

2^(k+1) = 2 \cdot 2^k > 2k = k + k \geq k + 1 \quad (k \geq 1\text{であるため}k \geq 1)

したがって $2^(k+1) > k+1$ ✓

結論：すべてのn ≥ 1で成り立つ。■

帰謬法 vs 数学的帰納法 vs 直接証明

手法	いつ使用するか	構造
直接証明	Pが真であることを順方向で示せる時	P → Qを直接導出
帰謬法	「Pが偽」と仮定すると矛盾が容易に見える時	¬P → ⊥
対偶証明	対偶(¬Q → ¬P)が直接証明よりも簡単な時	¬Q → ¬P
数学的帰納法	自然数nに関する無限の場合を証明する時	P(1) + P(k)→P(k+1)

帰謬法 vs 対偶証明：

対偶：「QでなければPではない」を直接証明 — 順方向
帰謬法：「PかつQではない」と仮定 → 矛盾 → PならばQである — 間接的

用途は似ていますが構造が異なります。試験で2つの手法を混同しないようにしてください。

実戦問題

問題 1 (帰謬法)

次を帰謬法で証明せよ。「n²が偶数ならばnも偶数である。」

証明：

n²が偶数であるが、nは奇数であると仮定する。

nが奇数ならば n = 2m+1 と書ける。

n² = (2m+1)² = 4m² + 4m + 1 = 2(2m² + 2m) + 1 → 奇数

しかし、n²が偶数であると仮定した。矛盾。

したがって、nも偶数である。■

問題 2 (数学的帰納法)

次を数学的帰納法で証明せよ。すべての自然数nについて $1 + 3 + 5 + ... + (2n-1) = n^2$

[基礎] n = 1：左辺 = 1、右辺 = 1² = 1 ✓

[帰納] $1 + 3 + ... + (2k-1) = k^2$ であると仮定する。

左辺(k+1項まで) = $k^2 + (2(k+1)-1) = k^2 + 2k + 1 = (k+1)^2$ = 右辺 ✓

結論：すべてのnで成り立つ。■

問題 3 (論理クイズにおける帰謬法)

A, B, Cの3人のうち1人が嘘つきである。 A：「私は正直者だ」 B：「Aは嘘つきだ」 C：「Bは嘘つきだ」

嘘つきは誰か？

帰謬法の適用：

場合 1：Aが嘘つきであると仮定

Aは嘘 → Aの言葉「私は正直者だ」は嘘 → 合致（一貫性OK）
Bの言葉「Aは嘘つきだ」は真 → Bは正直者（一貫性OK）
Cの言葉「Bは嘘つきだ」は嘘 → Cは嘘つき

矛盾：嘘つきがAとCの2人になる → 仮定を棄却

場合 2：Bが嘘つきであると仮定

Bの言葉「Aは嘘つきだ」は嘘 → Aは正直者
Aの言葉「私は正直者だ」は真 → Aは正直者（一貫性OK）
Cの言葉「Bは嘘つきだ」は真 → Cは正直者（一貫性OK）

矛盾なし → Bが嘘つき

正解：B

よくある間違い

帰謬法において

間違い：仮定と結論を混同する — 「¬Pを仮定」したのに証明の途中でPを使用する循環エラー

正しいチェック：仮定(¬P)を出発点として矛盾に至る論理の流れが途切れていないか確認する

数学的帰納法において

間違い：帰納ステップでP(k+1)を直接証明しようとする — P(k)を必ず使用しなければ帰納の意味がない

間違い 2：基礎ステップの省略 — n=1だけでなく、時にはn=0やn=2から始まる場合があるため問題で確認する

コアまとめ

帰謬法: ¬P → ⊥ → P “反対を仮定すると矛盾 → もとの命題は真”

数学的帰納法

基礎: P(1)が成り立つことを確認
帰納: P(k) → P(k+1)を証明
結論: すべての自然数nについてP(n)が成り立つ

両者の違い

帰謬法 = 間接証明 (矛盾の誘導)
帰納法 = ドミノ証明 (無限の拡張)

数学的帰納法はドミノのように考えれば決して難しくありません。最初のピースが倒れ（基礎）、1つ倒れれば次も倒れる（帰納）という2つの点さえ示せば — 無限に多い場合をわずか2ステップで証明したことになります。帰謬法は直接進むのが難しい道を迂回する知恵です。逆に行けば行き詰まることを示すことで、もとの道が正しいことを証明します。次の章(Ch8)では実戦論理問題の戦略 — 帰謬・前件確定・連鎖推論の統合適用を扱います。