対偶を利用する証明の応用

方針

解答

⓪ 発想 — どう考え始めるか。 「または」を含む結論は、そのままでは直接示しにくい。

ところが否定すると「または」は「かつ」に変わる。$x>1$ または $y>1$ の否定は、$x\le 1$ かつ $y\le 1$。$2$ つの条件が同時に成り立つ形になり、ぐっと扱いやすくなる。

このド・モルガンの感覚が、対偶に乗り換える動機だ。否定した仮定のほうが計算の回る形になっていないか、を判断の目安にする。

どちらも対偶を証明する。

(1) もとの命題『$x+y>2$ ならば $x>1$ または $y>1$』の対偶は、結論『$x>1$ または $y>1$』を否定して

『$x\le 1$ かつ $y\le 1$ ならば $x+y\le 2$』

(『または』の否定は『かつ』。)$x\le 1$、$y\le 1$ なら、足して

$$x+y\leqq 1+1=2$$

となり $x+y\le 2$。対偶が示せたので、もとの命題も真。(証明終わり)

(2) もとの命題『$m^2+n^2$ が奇数ならば $mn$ は偶数』の対偶は

『$mn$ が奇数ならば $m^2+n^2$ は偶数』

$mn$ が奇数になるのは、$m,n$ がともに奇数のとき。$m=2j+1$、$n=2k+1$($j,k$ は整数)とおくと

$$\begin{array}{rl}{m}^2+n^2& =(2j+1{)}^2+(2k+1{)}^2\\ & =4j^2+4j+1+4k^2+4k+1\\ & =2(2j^2+2j+2k^2+2k+1)\end{array}$$

$2\times (\text{整数})$ の形なので偶数。対偶が示せたので、もとの命題も真。(証明終わり)

まとめ:どちらも『結論を否定した対偶のほうが、具体的に計算できる』のがポイント。特に『または』の否定が『かつ』になることに注意しよう。

発展 — 一歩先へ。 (1)は「$2$ 数の和が $2$ を超えるなら、少なくとも一方は $1$ を超える」と読める。これは平均の考え方の一例だ。

一般に、$n$ 個の数 $x_1,\dots ,x_n$ の和が $nc$ を超えるなら、少なくとも $1$ つは $c$ を超える。もし全部が $c$ 以下なら、和は $nc$ 以下にしかならないからだ(対偶)。

「全部が平均以下なら、和は平均かける個数以下」という当たり前の事実が、こういう存在の主張を生む。個数と合計から「飛び抜けた $1$ つ」の存在を導くこの論法は、鳩の巣原理とも通じる強力な道具になる。

別解

別解 — 対偶を経由せず直接示す(別の証明の型)。 対偶をとらなくても、仮定から結論をまっすぐ導ける。

(1) $x+y>2$ を仮定する。もし $x>1$ ならそれで結論は成り立つ。そうでない場合、すなわち $x\le 1$ のときを考える。このとき

$$y=(x+y)-x>2-1=1$$

となり $y>1$。だからどちらの場合も「$x>1$ または $y>1$」が言える。

(2) $m^2+n^2$ が奇数と仮定する。和が奇数になるのは、$m^2$ と $n^2$ の一方が奇数・他方が偶数のときだけだ(偶数どうし・奇数どうしの和は偶数)。平方の偶奇はもとの数の偶奇と同じ。だから $m,n$ の一方が奇数・他方が偶数。すると積 $mn$ は偶数を因数に含み、偶数になる。

対偶で結論を裏返す本解に対し、こちらは仮定を場合分けして結論へ直進する。同じことが示せる。