PC用は別頁

== 対偶証明法と背理法 ==

《解説》
**** 1 対偶証明法 ****
○ p,q あるいは p(x),q(x)が条件であるとき,この条件が成り立つかどうかはxの値しだいです.
【例】
 条件x>1をp(x)で表わすとき,x=2ならばp(x)は真ですが,x=0ならばp(x)は偽です.
○ このように,条件については(どんなxについても成り立つ[あるいは成り立たない]ような特別なものを除いて),それ自体の真偽を問うことはまれです−−条件は命題と異なり,真偽が定まるとは限りません.条件を満たすものの集合を考えるだけです.
【ここまでの要約】
 通常,x>1のような文字を含む条件に対しては,それ自体の真偽を問うことはまれで,その条件を満たすものの集合を考えます.
 すなわち,条件には集合を対応させます.
○ これに対して,「すべてのxにたいして,p(x)が成り立つ」「あるxについて,p(x)が成り立つ」という主張・判断は,正しいか間違っているかが定まる命題となります.一般に,条件p(x)に対して,「すべてのxについて」あるいは「あるxについて」という述語を付けたものは命題になります.
【例】
 すべてのxについて,x>1 はx=0,−1などで成立しないので偽の命題です.

【例】
 (文字を実数の範囲で考えるものとするとき)

 すべてのxについて,x+1>0 は真の命題です.(どんな実数xについても成立するからです.)
 あるxについて,x+2x+2<0 は偽の命題です.(この不等式には解がないからです.)
【ここまでの要約】
 通常,x>1のような文字を含む条件に対しては,それ自体の真偽を問うことはまれですが,
「すべてのxについてx2+1>0が成り立つ」
「あるxについてx2+2x+2<0が成り立つ」
などのように,条件に「すべての」「ある」を付けた主張は真偽の定まる命題になります.
○ ところで,一般に「p(x)→q(x)」は「すべてのxについて,p(x)→q(x)」が省略されたものと決められています.
 そこで,p(x)→q(x)は命題です.
【ここまでの要約】
「すべてのxについて,p(x)ならばq(x)
記号で書けば
「すべてのxについて,p(x)→q(x)
は,単に
p(x)→q(x)
と省略的に書かれますので,これは真偽の定まる命題になります.すなわち「p(x)→q(x)」は「すべてのxについて,p(x)→q(x)」が省略されたものとなっているので命題です.
本当に,p(x)を満たすxがすべてq(x)を満たすのならばこの命題は真です.しかし,p(x)を満たすxの中に1つでもq(x)を満たさないものがあれば,この命題は偽になります.
【例】
x>1→x>0」は真の命題です.
【例】
x>0→x>1」は偽の命題です.(x=0.5のとき,x>0が成り立つのにx>1が成り立たないからです)
○ 条件p(x)を満たすものの全体を集合Pで,条件q(x)を満たすもの全体を集合Qで表わすとき,命題「p(x)→q(x)は,P⊂Qに対応します.
【ここまでの要約】
p(x)→q(x)」を集合で考えると「P⊂Q」に対応する
すなわち
P⊂Qのときは「p(x)→q(x)」は真
P⊂Qでないときは「p(x)→q(x)」は偽
【例】
P={ x | x>1 }, Q= { x | x>0 }とするとき,
P⊂Qだから「x>1→x>0」は真
Q⊂Pでないから「x>0→x>1」は偽

■ 対偶証明法
 p→qが成り立つとき,すなわちP⊂Qのとき, です.


 逆に,が成り立つとき,すなわち  のとき,P⊂Q だから p→q です.
  一般に,p→q と の真偽は一致します.
そこで,p→qを証明したいときに,直接示すのが困難な場合,を示せばよいことになります.
<対偶証明法>
 を証明することにより,p→qを間接的に証明する方法
■ 対偶証明法の例
例1
 x+y+z≧0のとき,x.y,zの少なくとも1つは0以上であることを証明しなさい.
(答案)
[考え方のポイント]
「少なくとも1つは0以上」の否定は,「全部0より小さい」
x,y,z<0 ならば x+y+z<0 が成り立つ.
対偶が真であるから,もとの命題も真である.
例2
 nが自然数を表わすとき,nが奇数ならば,nは奇数であることを証明しなさい.
(答案)
n=2k(偶数)と仮定すると,n=4k=2(2k)は偶数になる.
よって対偶により示された.
例3
 既約分数の分母・分子のどちらかは奇数であることを示しなさい。
(答案)
[考え方のポイント]
「少なくとも一方が奇数である」の否定=「両方とも偶数である」
既約分数において,m,nともに偶数と仮定すると,分母・分子は2で約分できることになり,既約分数でなくなる。
よって,対偶により示された。 
例4
 m,nを自然数とするとき,が既約分数であるならば,も既約分数であることを証明しなさい.
(答案)
m,nが互いに素でないと仮定すると,m=km’,n=kn’(kは2以上の整数)とおける.
このとき, はkで約分できる.
よって対偶により示された.
 我々の思考は,「個々の要素についての条件」から,「複合的な条件」の成否を判断する方が自然なので,
「複合的な条件」から「個々の要素についての条件」
を証明するような問題は,矢印を付け変えて(=対偶で考えて)
「個々の要素についての条件」の否定→「複合的な条件」の否定
を証明すると分かりやすくなります.

《問題》

 x+y≧2ならばx,yのうち少なくとも1つは1以上であることを証明しなさい.
(ア,イに入る語句を下の欄から選びなさい.)
(答案)
x,yの[ ア ]ならば[ イ ]となる.
よって対偶により示された.
[ ア ]
両方とも1以下

両方とも1より小さい

少なくとも1つは1以下

少なくとも1つは1より小さい
[ イ ]
x+y≧2

x+y>2

x+y≦2

x+y<2

 整数m,nについて,mnが奇数ならば,m,nはともに奇数であることを証明しなさい.
(ア,イに入る語句を右欄から選びなさい.)
(答案)
m,nの[ ア ]ならば[ イ ]となる.
よって対偶により示された.
[ ア ]
両方とも奇数

両方とも偶数

少なくとも一方が奇数

少なくとも一方が偶数
[ イ ]
mnは奇数

mnは偶数

 x+y≦1ならばx≦1であることを証明しなさい.
 (ア,イに入る語句を右欄から選びなさい.)
(答案)
≧0だから
[ ア ]ならば[ イ ]となる.
よって対偶により示された.
[ ア ]
x>1

x<1

x≧1

x≦1
[ イ ]
+y>1

+y<1

+y≧1

+y≦1

**** 2 背理法 ****
■ 背理法と対偶証明法は別のものです.背理法の一部に対偶証明法を用いることもありますが,そのような場合だけではありません.

■イラストによる背理法の説明(1)

qとで世界の全部です. これ以外にはありません
Q∪=U(全体集合)


p→qを証明したいが,qに行くのが困難なとき,
行きたくない方の道に進んでみて,そちらに進めば世界が破滅してしまう(矛盾がある)ことを言う

(おとぎばなしによる解説)
地獄に行って,地獄を壊してしまうと天国だけが残ります・・・地獄に行かないと天国には行けません.
#〜地獄を見たものにしか,天国なんて分かるはずはないのだ,クソ−負けてたまるか〜#
と自分に言い聞かせると覚えやすい

pとを仮定して矛盾を示す.
(pも仮定します.)


という形でpとが矛盾という構造でもよい.(一部に対偶証明法を用いる)
p 
→(数学的常識に反すること:1+1=1など)

という構造でもよい.
■イラストによる背理法の説明(2)
とは
P:卵の黄身が
Q:卵の白身の
中にあることだと思えばよい
 論理的な関係pならばq)は,集合ではに対応します.
 言い換えれば,集合の関係としてとなっていることを示せば,の証明になります.
 この証明は,集合P, Qの関係が一般のゆるい関係,すなわちP独自の部分,Q独自の部分,P, Qの共通部分から成り立っているのではなく,
が空集合になることを言えばよい.(右図の×印の部分が空集合になることを言う).
 そうすると「P:卵の黄身」は「Q:卵の白身」の中にある部分だけから成り立っていることになり,が言える.
 が空集合になること(右図の×の部分には何もないこと)を示すには,「Pであって」かつ「である」ものが存在すると仮定すると,矛盾を生じることを示せばよい.
 何かある要素xが,かつを満たすとすると具合の悪いことが起こることを示せばよい.
<背理法>
pとを仮定して矛盾を示す方法
※pを仮定することが重要.この点が対偶証明法と異なり,結論としてが導ける場合に限られず,他の内容でも数学的に矛盾することが示せたら何でもよいので,自由度が大きい.

■ 背理法の例
例1
 自然数a,b,cについて,a+b=cが成り立つとき,a,b,cのうち少なくとも1つは偶数であることを証明しなさい.
(答案)
+b=c・・・(1)
a,b,cは奇数・・・(2) と仮定する.
(2)よりa+bは奇数+奇数で偶数となり,cは奇数・・・(3)
(3)は(1)と矛盾する.
ゆえに,a,b,cのうち少なくとも1つは偶数である.
例2
 が無理数であることを用いて,が無理数であることを証明しなさい.
(答案)
(m,nは整数)と仮定する.
両辺を2乗すると2+3+2=(
となるが,左辺は無理数,右辺は有理数なので矛盾.
ゆえに,は無理数
例3
 △ABCにおいて,
a<bならば∠A<∠B・・・(1)
a=bならば∠A=∠B・・・(2)
a>bならば∠A>∠B・・・(3)
が成り立つ.これらを用いて,(1)(2)(3)の逆が成り立つことを証明しなさい.
(答案)
∠A<∠Bのとき,
a=bと仮定すると(2)により∠A=∠B これは∠A<∠Bと矛盾する.
a>bと仮定すると(3)により∠A>∠B これは∠A<∠Bと矛盾する.
以上により,∠A<∠Bならばa<b

(2)(3)の逆も同様にして示される. 背理法の一種の「転換法」と呼ばれる方法です.転換法は(1)(2)・・・の仮定側がすべての場合を尽くしていて,(1)(2)・・・の結論側に共通部分がなければいつでも使えます.

例4
 素数は無限個あることを証明しなさい.
(答案)
素数は有限個だけあると仮定し,これらをp1,p2,p3,p4,...,pとおく
p1・p2・p3・p4・・・p+1はp1,p2,p3,p4,...,pのいずれでも割り切れない(1余る)から素数である.
これは矛盾であるから,素数は無限個ある.(ユークリッドの証明)
例5
 は無理数であることを証明しなさい.
(答案)
 が有理数であると仮定し,これをとおく. (ここに,m,nは整数で互いに素)

(*)のようなことが起こるのは,nが2の倍数でmも2の倍数の場合に限るということが示される.

とすれば,約分できるはずになる.結局,そんな既約分数は存在しえないことになる.
両辺を2乗すると…(*)
2m=n
よって,nは2の倍数・・・(1)

n=2kとおく
2m=4k
=2k
よって,mは2の倍数・・・(2)

(1)(2)はm,nが互いに素という仮定に反し,矛盾.
ゆえに,は無理数

 ※この証明を見て,「m,nは整数で互いに素」などという根本的には重要でなさそうな仮定と矛盾するということによって証明を行っていることについて,普通の感覚の高校生なら,なんとなく割り切れない印象を持つかもしれない.
 しかし,この証明は昔から有名な証明で,高校生としては,まず「そんな形の矛盾でもよいのか〜♪」と感心して,次に「これに味をしめて」「機会があったら真似しよう」と考えるとよい
⇒ころんでもタダでは起きないしたたかさが重要

《問題》


 21人を4組に分けたとき,どの組かは必ず6人以上になることを証明しなさい.
(ア,イ,ウに入る語句を下欄から選びなさい.)
(答案)
21人を4組に分けたとする・・・(1)
どの組も[ ア ]以下で4組あると仮定する・・・(2)
(2)より合計[ イ ]以下となる.・・・(3)
(3)は(1)と矛盾するから,[ ウ ]
[ ア ]
4人 5人 6人
[ イ ]
20人 21人

24人 25人

[ ウ ]
全部で3組以下

全部で5組以上

どこかの組は5人以上

すべての組は5人以上

どこかの組は6人以上

すべての組は6人以上


 自然数a,b,cについて,a+b=cが成り立つとき,a,b,cのうち少なくとも1つは3の倍数であることを証明しなさい.
(ア,イ,ウに入る語句を下欄から選びなさい.)
(答案)
a,b,cのいずれも[ ア ]と仮定する.・・・(1)
ところで
 (3k)=3(3k
 (3k+1)=3(3k+2k)+1
 (3k+2)=3(3k+4k+1)+1
だから,(1)のとき
  c[ イ ]
  a+b[ ウ ]
これらが等しいことは矛盾であるから,
a,b,cのうち少なくとも1つは3の倍数である.
[ ア ]
3の倍数である

3の倍数でない
[ イ ]
3で割ると1余る

3で割ると2余る
[ ウ ]
3の倍数である

3で割ると1余る

3で割ると2余る

 √3が無理数であることを用いて,2+√3が無理数であることを証明しなさい.
(ア,イ,ウに入る語句を下欄から選びなさい.)
(答案)
2+√3が[ ア ]であると仮定する.・・・(1)

2+√3=r (rは[ ア ])とおくと
√3=r−2となる.・・・(2)

(2)の左辺は[ イ ],右辺は[ ウ ]
これは矛盾であるから,2+√3は無理数である.

[ ア ]
有理数

無理数
[ イ ]
有理数

無理数
[ ウ ]
有理数

無理数

 点Cを中心とする半径Rの円と直線Lがあって,点CからLにひいた垂線の長さをdとするとき,
d<RならばLは円と2点で交わる・・・(1)
d=RならばLは円と1点で接する・・・(2)
d>RならばLは円と共有点を持たない・・・(3)
 これらを用いて,(1)(2)(3)の逆をそれぞれ証明しなさい. (ア,イ,ウに入る語句を下欄から選びなさい.)
(答案)
Lは円と2点で交わるとき,・・・(*)
  • d=RならばLは円と[ ア ].これは(*)と矛盾する.
  • d>RならばLは円と[ イ ].これは(*)と矛盾する.
ゆえに,Lが円と2点で交わるとき,[ ウ ]

(2)(3)の逆も同様にして示される.

[ ア ]
2点で交わる

1点で接する

共有点を持たない
[ イ ]
2点で交わる

1点で接する

共有点を持たない
[ ウ ]
d<R

d=R

d>R

 nが2以上の整数であるとき,は無理数となることを証明しなさい. (ア,イ,ウに入る語句を下欄から選びなさい.)
(答案)
 n<<n+1だから,[ ア ]ではない.・・・(1)
 [ イ ]であると仮定すると,・・・(2)
(1)(2)より とおくと (p,qは正の整数で互いに素,p≠1)・・・(3)

左辺は[ ウ ]で,右辺は(3)により[ ウ ]でない.
これは矛盾であるから,は無理数
[ ア ]
整数

有理数

無理数
[ イ ]
整数

有理数

無理数
[ ウ ]
整数

有理数

無理数

(携帯版)...メニューに戻る

...(PC版)メニューに戻る

■[個別の頁からの質問に対する回答][対偶証明法と背理法について/18.6.25]
お世話になります。背理法を使って数について考えていますが、行き詰まってしまいました。知恵をお借りできませんでしょうか? 任意の有理数をY、任意の無理数をMとする。Y÷Mが有理数なのか無理数なのか、両方ありえるのか考える。 Y÷M=Y/Mであり、これが有理数だと仮定すると、互いに素な自然数a.bを用いてa/bと表せるので、 (Y/M)=(a/b) 両辺にMaをかけると、Yb=Maとなり、左辺は有理数、右辺は無理数なので矛盾する。したがって、Y÷M=有理数という仮定は誤りで、Y÷M=無理数となる。 ところで、Y=0のとき、Y÷M=0となり、有理数となってしまう。 と、こんな具合に無理数なのか、有理数なのかわかりません。 私の解き方、どこがおかしいのかわかりませんか? よろしくお願いいたします。
=>[作者]:連絡ありがとう.
「両辺にMaをかけると、Yb=Maとなり」の部分はおかしいですが,ほぼ合っています.ただし,主張の内容をはっきりしなければなりません.
ア) のとき

の両辺にを掛けると

左辺は有理数で右辺は無理数だから矛盾.よって元の式は無理数.
イ) のとき

は有理数.
したがって,有理数になる場合と無理数になる場合がある.
問題が,「任意の有理数をY、任意の無理数をMとするとき,Y÷Mは無理数になる」という命題ならば,イ)が反例となって偽
問題が,「任意の有理数をY、任意の無理数をMとするとき,Y÷Mは有理数になる」という命題ならば,ア)により偽
■[個別の頁からの質問に対する回答][対偶証明法と背理法について/18.6.23]
証明問題では、背理法とか対偶法といった証明のテクニックだけでは点がとれません。例えば無理数は整数/整数で表せないとか、無理数÷有理数は無理数みたいな、予備知識が必要です。そこで、大学入試の証明問題に必要でよく問われる予備知識をまとめたノートを作り始めたのですが、なかなか必要な予備知識をまとめたサイトが見当たりません。ゲイシャ様のページでそれら予備知識をまとめたページがあるとうれしいです。
=>[作者]:連絡ありがとう.「幾つか」は可能ですが「全部」は無理でしょう.
■[個別の頁からの質問に対する回答][対偶証明法と背理法について/16.11.26]
1対偶証明法の問題1で[ア]の選択肢 両方とも1より小さい、 少なくとも1つは1以下、 少なくとも1つは1より小さいの3つを選んでもエラーになり、404:File Not Found となって結果が表示されません。ゲイシャさんの管理者に問い合わせるようにとのことでしたので、ここに書かせていただきました。僕はiPadでSafariを使ってこのページを開いています。(使っている検索エンジンはGoogleです。)肝心な正解の選択肢でさえ開けませんので(とはいえとても難しい問題というわけではありませんが、、、)どうかご点検をお願いいたします。 補足:なぜか唯一 両方とも1以下 の選択肢だけは反応してバツになります。[イ]の方は問題ありませんでした。
=>[作者]:連絡ありがとう.「あ」ビックリ仰天のプログラムミスでしたので,訂正しました.
■[個別の頁からの質問に対する回答][対偶証明法と背理法について/16.8.23]
背理法例5について。 なぜ、n/mが互いに素という仮定をつけていいのかがよく分からないのですが、例えば入試にこれが出てきて問題を解こうとするとき、解答者がn/mに互いに素という条件をつける意図は何なのでしょうか?
=>[作者]:連絡ありがとう.整数の比で表された分数は,もし約分できるものなら約分した形で考えることができます.これが「互いに素」という仮定の意味です(約分しない形のまま扱っていたら分母と分子が確定しません.)
たとえば,のまま使うととすることになりますが,こんなことが許されるならもすべてできることなり,n,mが定まりません.この分数ではとしてn,mを確定する必要があります.
本音を言えば,高校生なら誰でも知っているように,が有限個の桁で等しくなるとしたら,その約分した結果のn/mについて両辺を2乗したら「分母も分子も2の倍数でなければならないことになるのは矛盾である」という理屈です.
そこで質問を振り返ってみると,n/mが互いに素という仮定を付けないと(既約分数でないものでもそのまま使っているとすると)n,mが定まらないことになります.