対偶証明法と背理法
《解説》
**** 1 対偶証明法 ****
■ 条件pを満たすものの全体を集合Pで,条件qを満たすもの全体を集合Qで表わすとき,命題「p→q」は,P⊂Qに対応します.
 p,q あるいは p(x),q(x)が条件であるとき,この条件が成り立つかどうかはxの値しだいです.
例 条件x>1をp(x)で表わすとき,x=2ならばp(x)は真ですが,x=0ならばp(x)は偽です.
 このように,条件については(どんなxについても成り立つ[あるいは成り立たない]ような特別なものを除いて),それ自体の真偽を問うことはまれです−−条件は命題と異なり,真偽が定まるとは限りません.条件を満たすものの集合を考えるだけです.

 これに対して,「すべての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 は偽の命題です.(この不等式には解がないからです.)
 ところで,一般に「p(x)→q(x)」は「すべてのxについて,p(x)→q(x)」が省略されたものと決められています.
 そこで,p(x)→q(x)は命題です.
■ 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で約分できることになり,既約分数でなくなる。
よって,対偶により示された。 (※Not「少なくとも一方が奇数である」=「両方とも偶数である」)
例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 背理法 ****
■ 背理法と対偶証明法は別のものです.背理法の一部に対偶証明法を用いることもありますが,そのような場合だけではありません.
■ イラストによる背理法の説明
■ qとで世界の全部です.
これ以外にはありません:Q∪=U(全体集合)
■ p→qを証明したいが,qに行くのが困難なとき,
行きたくない方の道に進んでみて,そちらに進めば世界が破滅してしまう(矛盾がある)ことを言う

(おとぎばなしによる解説)
地獄に行って,地獄を壊してしまうと天国だけが残ります・・・地獄に行かないと天国には行けません.)
pとを仮定して矛盾を示す.
(pも仮定します.)


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

という構造でもよい.
<背理法>
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は整数で互いに素)
 ※この証明を見て,「m,nは整数で互いに素」などという根本的には重要でなさそうな仮定と矛盾するということによって証明を行っていることについて,普通の感覚の高校生なら,なんとなく割り切れない印象を持つかもしれない.
 しかし,この証明は昔から有名な証明で,高校生としては,まず「そんな形の矛盾でもよいのか〜♪」と感心して,次に「これに味をしめて」「機会があったら真似しよう」と考えるとよい
⇒ころんでもタダでは起きないしたたかさが重要
両辺を2乗すると2=(
2m=n
よって,nは2の倍数・・・(1)

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

(1)(2)は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)により[ ウ ]でない.
これは矛盾であるから,は無理数
[ ア ]
整数
有理数
無理数

[ イ ]

整数
有理数
無理数
[ ウ ]
整数
有理数
無理数



.