2015/06/19

対偶を用いた証明のいろいろな具体例

分野: 集合,命題,論証  レベル: 基本公式

「 $P$ ならば $Q$ 」という命題とその対偶「 $Q$ でないならば $P$ でない」という命題の真偽は一致する。

対偶の真偽は一致する

  • 「 $P$ ならば $Q$ 」という命題について,両方否定してひっくり返したもの「 $Q$ でないならば $P$ でない」を対偶と言います。
  • 対偶という概念は数学の世界の外(日常会話とか)でも使います。例えば「数学は面白い」の対偶は「面白くないなら数学でない」です。
  • もとの命題と対偶の真偽は必ず一致します。上の例だと,数学が面白い人に取ってはどちらも真ですし,数学が面白くない人にとってはどちらも偽です。
  • 対偶

    対偶の真偽が一致することは,ベン図で理解することもできます。
    「 $P$ ならば $Q$ 」が真
    $\iff$ $P$ が $Q$ に含まれている
    $\iff$ $Q$ の外側が $P$ の外側に含まれている
    $\iff$ 「 $Q$ でないならば $P$ でない」が真

    上側のベン図は,$P$ ならば $Q$ およびその対偶が真である状況。下側のベン図はいずれも偽である状況を表しています。

対偶法

対偶はもとの命題と真偽が一致しているので,もとの命題の証明をしたいときに代わりに対偶を証明してもOKというわけです。対偶を取ると証明しやすくなることもけっこうあります!

例題1

整数 $n$ に対して $n^3+n^2+n$ が奇数ならば $n$ も奇数であることを証明せよ。

解答

対偶を取る。「 $n$ が偶数なら $n^3+n^2+n$ が偶数」を証明すればよい。 $n$ が偶数のとき $n^3+n^2+n$ は偶数3つの和なので偶数となりOK。

注:命題の仮定部分が複雑だと証明しにくいことが多いです。「 $n^3+n^2+n$ が奇数」というやや複雑な仮定から逃げるために対偶を取って「 $n$ が偶数」という仮定にします。

いろいろな例題

例題2

$a,b$ を整数とする。不定方程式 $ax+by=1$ が整数解を持つとき $a$ と $b$ が互いに素であることを証明せよ。

解答

対偶を取る。 $a$ と $b$ が互いに素でないとき,不定方程式 $ax+by=1$ が整数解を持たないことを証明すればよい。
実際,$a$ と $b$ がいずれも $d\:(\geq 2)$ の倍数なら $ax+by$ も $d$ の倍数となり,$ax+by=1$ は整数解を持たない。

注:重要な定理の片側です。→一次不定方程式ax+by=cの整数解


最後はややマニアックです。興味のある人だけどうぞ!

例題3

$a^n\not\equiv a\:\mathrm{mod}\:n$ なる自然数 $a$ が存在するとき,$n$ が合成数であることを証明せよ。

解答

対偶を取る。 $n$ が素数のとき,全ての自然数 $a$ に対して $a^n\equiv a\:\mathrm{mod}\:n$ を証明すればよい。これはフェルマーの小定理と呼ばれる有名な定理である!

注:例題3は $n$ が合成数であるための十分条件を与えてくれています。これを用いると与えられた整数が素数かどうか高確率で判定できます(フェルマーテスト)。

整数問題ばっかりになってしまいました。対偶を使った素晴らしい例題(分野不問)をご存知の方はご一報下さい!

Tag: 数学1の教科書に載っている公式の解説一覧

分野: 集合,命題,論証  レベル: 基本公式