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

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

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は整数で互いに素)

(*)のようなことが起こるのは,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版)メニューに戻る


■[個別の頁からの質問に対する回答][対偶証明法と背理法について/16.11.26]
1対偶証明法の問題1で[ア]の選択肢 両方とも1より小さい、 少なくとも1つは1以下、 少なくとも1つは1より小さいの3つを選んでもエラーになり、404:File Not Found となって結果が表示されません。ゲイシャさんの管理者に問い合わせるようにとのことでしたので、ここに書かせていただきました。僕はiPadでSafariを使ってこのページを開いています。(使っている検索エンジンはGoogleです。)肝心な正解の選択肢でさえ開けませんので(とはいえとても難しい問題というわけではありませんが、、、)どうかご点検をお願いいたします。 補足:なぜか唯一 両方とも1以下 の選択肢だけは反応してバツになります。[イ]の方は問題ありませんでした。
=>[作者]:連絡ありがとう.「あ」ビックリ仰天のプログラムミスでしたので,訂正しました.