数学的帰納法・背理法とは（全体像）
これらは、「ある主張が正しい」と論理的に示す（証明する）ための方法。プログラムが正しく動くこと（アルゴリズムの正当性）を示すときの土台になる。
代表的な3つを押さえる。
- 数学的帰納法 … すべての自然数（1, 2, 3, …）について成り立つことを、ドミノ倒しのように示す。
- 背理法 … 「成り立たない」と仮定して、おかしなこと（矛盾）が起きることを示し、もとの主張が正しいと結論づける。
- 対偶証明 … 「PならばQ」を、ひっくり返した「QでないならPでない」で示す。
詳しく：この2ステップと対偶だけ覚えれば戦える
ここが記事の心臓部。まずは数学的帰納法の2ステップ。
数学的帰納法の2ステップ
| ステップ | 内容 |
|---|---|
| ①基底ステップ | 最初の1つ（n＝1など）で成り立つことを示す |
| ②帰納ステップ | n＝kで成り立つと仮定し、n＝k＋1でも成り立つことを示す |
この2つがそろうと、「最初が成り立つ」＋「成り立てば次も成り立つ」から、ドミノ倒しのように全部に成り立つと言える。つまり、最初の1枚と「次に伝わる」の両方がそろって、初めて全部に成り立つ、というわけだ。どちらか片方だけでは証明にならない——ここが試験の狙い目だ。
次に、背理法と対偶証明。
背理法と対偶証明
| 手法 | やり方 |
|---|---|
| 背理法 | 主張の否定を仮定 → 矛盾を導く → もとの主張が正しい |
| 対偶証明 | 「PならばQ」の代わりに「QでないならPでない」を示す |
背理法の有名な例が「√2は割り切れない数（無理数）」の証明。「もし割り切れる（分数で書ける）なら…」と仮定して進めると矛盾が出るので、「割り切れない」が正しいと分かる。
対偶は、「PならばQ」と「QでないならPでない」が論理的に同じ意味（同値）であることを使う。直接示しにくいときに、ひっくり返したほうで示すと楽になる。なお、ただの「逆（QならばP）」は同値ではないので混同に注意だ。
わかりやすく言い換えると
要するに、帰納法は「ドミノ倒し」だ。
①基底ステップ … 最初の1枚を倒す（n＝1で成り立つ）
②帰納ステップ … 「k枚目が倒れればk＋1枚目も倒れる」を示す
この2つがそろえば、最初の1枚から順に全部倒れる＝すべてで成り立つ、というわけだ。最初を倒さなかったり、「次に伝わる」を示さなかったりすると、ドミノは途中で止まってしまう。
背理法は「わざと逆を言ってみて、おかしくなることを見せる」。対偶は「ならばを裏返しても同じ」というワザだ。
試験のツボ
🔴 一番出る：数学的帰納法の2ステップ
①基底ステップ＝最初の1つで成り立つ
②帰納ステップ＝kで成り立てばk＋1でも成り立つ
③この2つがそろって初めて証明が完成する
🔴 次に出る：背理法と対偶
①背理法＝否定を仮定して矛盾を導く
②対偶＝「PならばQ」と「QでないならPでない」は同値
🟡 押さえると安定：応用
①アルゴリズムの正当性証明
②ループ不変条件（ループ中つねに成り立つ性質）
よくある間違い
①「数学的帰納法は基底ステップだけで証明が完成する」→ ✗ 基底＋帰納の2ステップがそろって初めて完成する。
②「対偶（QでないならPでない）と逆（QならばP）は同じ意味だ」→ ✗ もとの命題と同値なのは対偶だけ。逆は同値ではない。
③「背理法は主張をそのまま仮定して進める証明だ」→ ✗ 背理法は主張の「否定」を仮定して矛盾を導く。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（帰納法の2ステップ）
数学的帰納法に関する次の記述のうち、正しいものはどれか。
- 基底ステップと帰納ステップの2つがそろって初めて証明が完成する手法だ
- 最初の1つ（基底ステップ）だけを示せば、すべての場合の証明が完成する
- n＝kで成り立つことだけを示せば、基底ステップは不要となる証明である
- 数学的帰納法は1つの例を示すだけでよく、すべてを確認する必要はない
解答は 1 だぜ。
数学的帰納法は基底ステップ（最初の1つ）と帰納ステップ（kならk＋1）の2つがそろって完成する。ドミノ倒しで、最初を倒し、次に伝わることを示す、という流れだな。
選択肢2は「基底だけ」、選択肢3は「帰納だけ・基底不要」、選択肢4は「1つの例だけ」で、どれも2ステップを欠いた誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 基底＋帰納の2つの手順で完成 |
| 2 | ✗ | 基底だけでは不十分 |
| 3 | ✗ | 基底ステップも必要 |
| 4 | ✗ | 1つの例では証明にならない |
オリジナル問題2（背理法）
背理法に関する次の記述のうち、正しいものはどれか。
- 背理法は示したい主張をそのまま仮定して、その正しさを確かめる証明である
- 背理法は1つの具体例を挙げるだけで、主張全体を証明できる手法である
- 背理法は主張の否定を仮定し、矛盾を導くことでもとの主張を正しいとする
- 背理法は基底と帰納の2つの手順で、すべての自然数について示す方法だ
解答は 3 だぜ。
背理法は主張の「否定」を仮定して、矛盾を導くことで、もとの主張が正しいと結論づける。√2が無理数の証明が有名な例だな。
選択肢1は「そのまま仮定」が誤り（否定を仮定する）。選択肢2は「具体例だけ」が誤り。選択肢4は数学的帰納法の説明だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 否定を仮定する |
| 2 | ✗ | 具体例だけでは証明にならない |
| 3 | ✓ | 否定を仮定して矛盾を導く |
| 4 | ✗ | それは数学的帰納法 |
オリジナル問題3（対偶）
命題「PならばQ」と論理的に同値なものとして、正しいものはどれか。
- 「QならばP」（逆）が、もとの命題とつねに同値になるとされている
- 「QでないならPでない」（対偶）が、もとの命題と論理的に同値である
- 「PでないならQでない」（裏）が、もとの命題とつねに同値になる
- 「PかつQ」が、もとの命題「PならばQ」と論理的に同値であるとされる
解答は 2 だぜ。
「PならばQ」と同値なのは対偶「QでないならPでない」だ。直接示しにくいときは、この対偶で示すと楽になることがあるんだ。
選択肢1の逆（QならばP）、選択肢3の裏（PでないならQでない）は、もとの命題と同値ではない。選択肢4の「PかつQ」も別物だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 逆は同値ではない |
| 2 | ✓ | 対偶はもとの命題と同値 |
| 3 | ✗ | 裏は同値ではない |
| 4 | ✗ | 「PかつQ」は別の意味 |
まとめ
押さえどころ
- 🔴 数学的帰納法 ＝ 基底ステップ＋帰納ステップの2つで完成（ドミノ倒し）。片方だけではダメ。
- 🔴 背理法と対偶 ＝ 背理法は否定を仮定して矛盾を導く。対偶「QでないならPでない」はもとの命題と同値。
- 🟡 応用 ＝ アルゴリズムの正当性証明・ループ不変条件。
次に学ぶ
- 集合・述語論理 ── 「ならば」「すべて」「ある」を扱う論理の土台。証明で使う論理記号の意味がはっきりする。
- アルゴリズムの正当性 ── 帰納法やループ不変条件は、プログラムが正しく動くことを示すのに使われる。理論が実務につながる。
執筆: SikakuQuest編集部