対偶命題 背理法 違い

質問

背理法を使って証明するときと対偶命題を使って証明するときとの違いはなんですか?

回答No.9

Caper

● まず、1つ の例題によって、そのちがいを私は示してみました。ごらんください。

　 例題
　「 x^2 が奇数であるならば、x は奇数である 」という命題が真であることを証明せよ。( ただし、x の変域は、自然数全体の集合であるとする )

　《 x^2 が奇数であって、》x が偶数であると "仮定する" ならば、x = 2m を満たす 自然数m が存在します。このとき、次の等式が満たされます。
　 x^2 = (2m)^2 = 4m^2 = 2(2m^2).
　 この等式が満たされることによって、x^2 が偶数であることが示されます。★《 これは、x^2 が奇数であるともしている "仮定" に反します。》
　 ( 証明終わり )

　 上記の証明の最初と最後に、《 》でくくった記述があります。これらの 2つ の記述を証明に盛りこめば、背理法による証明になると、私は思います。《 》でくくった 2つ の記述を省けば、「 証明しようとする命題の対偶 」の証明ということになると、私は思います。

● 記号を用いて、補足の説明をさせてください。

　 アルファベットの大文字は、それぞれ命題を表わすものとします。→ という記号は「 ならば 」を意味するものとします。￢ という記号は「 否定 」を意味するものとします。∧ という記号は「 かつ 」を意味する記号とします。

　 2つ の 命題 A, B を 次のとおりに置くことにします。

　 A = ( x^2 は奇数である )
　 B = ( x は奇数である )

　 前述の例題は、A → B を証明せよというものでした。《 》無し の証明は、￢B → ￢A という命題が真であることを示したものです。

　《 》付き の証明では、★ 印 より前において、(A ∧ ￢B) → ￢A という命題が真であることを示しています。そして、★ 印 より後ろにおいて、背理法による証明が行なわれたことを強調する「 補足の記述 」がなされています。

● 背理法についてだけ、さらなる補足の説明をさせてください。

　 背理法は「『 真であることを証明しようとする命題 』の否定から矛盾を導く 」という証明手段です。もっとくだいて説明すれば、「 真であることを証明しようとする命題が P であるとき、￢P → ( 矛盾 ) が真であることを示す 」という証明手段です。なお、矛盾とは、「 つねに偽である命題 」のことです。

　 前述の例題において、証明しようとした命題は A → B でした。これの否定、すなわち ￢(A → B) は、A ∧ ￢B と同値です。前述の証明では、★ 印 より前において、(A ∧ ￢B) → ￢A が真であることを示したわけです。
　 ところが、￢A が「 つねに偽である命題 」という扱いを受けるのかと言うと、そうではありません。この場合、「 つねに偽である命題 」という扱いを受けるのは、￢A ∧ A ということになるのです。

　 話を少し脱線させます。
　 P, Q がいずれも命題であるとき、次の 1) という命題は、P, Q がどんな内容であっても、真になります。このように「 つねに真である命題 」のことを、トートロジーと呼びます。

1) (P ∧ ￢Q) → P という命題は、

　 また、P, Q, R がいずれも命題であるとき、次の 2) という命題と、3) という命題とは、P, Q, R がどんな内容であっても、同値になります。

2) (P → Q)∧(P → R)
3) P → (Q ∧ R)

　 話をもとに戻します。
　 前述の証明では、★ 印 より前において、(A ∧ ￢B) → ￢A が真であることを示しました。一方、(A ∧ ￢B) → A はトートロジーです ( 前述の 1) 参照 )。すなわち、(A ∧ ￢B) → A も真であるわけです。
　 これにより、次の 4) が真になるのは、おわかりですよね。

4) ((A ∧ ￢B) → ￢A)∧((A ∧ ￢B) → A)

　 この 4) が真であれば、次の 5) も真になります ( 前述の 2) 3) 参照 )。

5) (A ∧ ￢B) → (￢A ∧ A)

　 ￢A ∧ A は矛盾です。前述の証明における、★ 印 より後ろには、このような意味が隠されているのであると、私は思います。

● 背理法による証明として、よく話題に上るのが、√2 が無理数であることの証明です。

　 2つ の 命題 A, B を次のとおりに置くことにします。

　 A = ( √2 は無理数である )
　 B = ( √2 = m/n であって、なおかつ m/n は既約分数である 整数 m と 自然数 n が存在する )

　 √2 が無理数であることの証明は、申し上げるまでもなく、A が真であることを示せばよいわけです。

　 証明の手順は、次の 1> - 4> であると、私は思います。通常、3> 4> については、明記されないでしょう。また、2> から 3> にかけては、理解しづらいかもしれません。命題 P が真であれば、どんな 命題 Q を持ってきても、すなわち、命題 Q が真であれ偽であれ、Q → P は真であるということを利用しています。

1> 有理数についての定義などにより、￢A → B が真であるということを示す。
2> ￢B = ( どの 整数 m をとっても、どの 自然数 n をとっても、√2 = m/n であるならば、m/n は既約分数ではない ) が真であることを示す。
3> 自動的に、￢A → ￢B が真であることが示される。
4> 自動的に、￢A → (B ∧ ￢B) が真であることが示される。

　 上記の 4> における B ∧ ￢B が矛盾です。

● 私はそこつ者です。以上の記述の中にあやまりが含まれている可能性は高いです。まちがっていましたら、ひらにごめんなさい。
　 また、理解しづらい個所がございましたら、[ 補足 ]欄 を利用するなどして、遠慮なくお知らせください。