「もし、その答えが正しいとしたら……あれ、条件が合わない」。推理パズルでこんな経験はありませんか。
背理法は、示したい主張の否定を仮定し、その仮定から矛盾を導く証明方法です。遠回りに見えますが、正しい答えを直接探すより、「その答えでは成り立たない」と示す方が簡単なことがあります。
目次
背理法の基本は、仮定・矛盾・結論の3段階
- 示したい主張の否定を、いったん仮定する。
- その仮定と、すでに分かっている条件から考えを進める。
- 両立しない結果が出たら仮定を退け、元の主張が成り立つと結論する。
矛盾とは、たとえば「同じ数が偶数でも奇数でもある」「一人だけのはずなのに二人いる」といった、同時には成り立たない状態です。「何となく変だ」ではなく、どの条件とどの結果がぶつかったかを示すのがポイントです。証明方法の定義はMathWorldのProof by Contradictionにあります。
例題：カードを隠したのは誰？
A、B、Cのうち、一人だけがカードを隠しました。隠した人だけが嘘をつき、ほかの二人は本当のことを話しています。3人の発言は次の通りです。
- A：「Bが隠した」
- B：「Cが隠した」
- C：「僕は隠していない」
誰が隠したでしょう。条件を書き出して、候補を一人ずつ確かめてみてください。
解答を見る
答えはBです。まずAが隠したと仮定します。この場合Bは正直なので、Bの「Cが隠した」も本当になるはず。でも隠した人は一人だけ。AとCの二人になってしまい、矛盾します。
次にCが隠したと仮定します。Aは正直なので、「Bが隠した」は本当。するとBとCの二人になり、また矛盾します。
Bが隠した場合は、Aの発言が本当、Bの発言が嘘、Cの発言が本当となり、すべての条件に合います。
この例では、限られた候補を仮定して矛盾を調べ、残った候補を確認しました。候補がA、B、Cで尽くされているから、この調べ方で答えを決められます。現実の推理で候補を見落としている場合には、同じ結論には進めません。
数学の例：√2が分数で表せないことを証明する
√2は、二乗すると2になる正の数です。これが整数同士の比、つまり分数では表せないことを背理法で示します。
1．分数で表せると仮定する
√2 = p/qと書けると仮定します。pとqは正の整数で、分数は約分しきってあるものとします。つまりpとqに、1以外の共通の約数はありません。
2．pもqも偶数になる
両辺を二乗して整理すると、p² = 2q²。したがってp²は偶数です。奇数を二乗すると奇数になるので、pは偶数でなければなりません。
p = 2kと書いて代入すると、4k² = 2q²。両辺を2で割ればq² = 2k²となり、今度はqも偶数だと分かります。
3．最初の仮定とぶつかる
pもqも偶数なら、分子と分母を2で約分できてしまいます。これは「約分しきってある」という条件に矛盾します。
よって「√2を分数で表せる」という仮定が間違い。√2は分数で表せない、無理数だと結論できます。
この証明の気持ちよさは、どれほど巨大な分子と分母を考えても逃げられないことです。「約分しきった分数を用意したはずなのに、必ず約分できる」という一点で、すべての候補がまとめて退けられます。
偶数か奇数かに注目して、不可能な場合を見つける練習には、偶奇性（パリティ）の移動パズルも使えます。盤面を二色に分けると、経路を一つずつ試さずに、到着できない手数を見分けられます。
背理法と対偶の違い
「PならばQ」を示すとき、二つの方法は次のように考えます。
| 方法 | 出発点 | 目指すもの |
|---|---|---|
| 背理法 | PなのにQではない、と仮定する | その仮定から矛盾を導く |
| 対偶による証明 | Qではないと仮定する | Pではないことを示す |
対偶は「P → Q」と「Qでない → Pでない」が同じ真偽になることを使います。どちらも否定を使いますが、証明で追いかけるものが違います。
背理法を使いやすくするコツ
- 否定を正しく書く。「すべて」の否定は「一つもない」ではなく、「少なくとも一つ例外がある」です。
- 仮定と確定事項を分ける。試しに置いた条件に印を付けると、どれを退けたのかが明確になります。
- 矛盾した場所を言葉にする。「二人になったので、一人という条件に反する」と一文で説明します。
条件から一手ずつ考えるなら、必要条件・十分条件も役に立ちます。ゲームで推理を楽しみたい方は、猫を眠らせる順番パズルもどうぞ。
同じ整数の命題を、三つの方法で比べる
| 方法 | 「n²が偶数ならnは偶数」への進み方 |
|---|---|
| 直接の証明 | nを2で割った余りを調べ、奇数の可能性を除く |
| 対偶による証明 | nが奇数ならn=2k+1。二乗は4k²+4k+1で奇数 |
| 背理法 | n²は偶数なのにnは奇数と仮定。同じ計算でn²が奇数になり矛盾 |
ここでnとkは整数です。同じ計算が登場しても、何を仮定して何を結論したかが違います。「対偶」と「背理法」を完全に無関係な技法として暗記するより、証明の出発点に印を付けると使い分けやすくなります。
一つの反例で足りる主張、足りない主張
「すべての整数は偶数だ」は3という一例で否定できます。一方、「偶数が存在する」を否定するには、奇数を一つ見つけるだけでは足りません。背理法に入る前に、「すべて」「存在する」のどちらを否定したのかを言葉にすると、誤った矛盾を作らずに済みます。