対偶と背理法について 問題のどこをみて、対偶を使うか、背理法を使うか判断しますか？
ベストアンサー
対偶について
Point 複雑な事象→簡単な事象を示すときに有効。
例 2^n -1が素数ならばnが素数であることを示せ。(京都府立医科大)
2^n -1を因数分解しても指数部分が素数であることはどう考えても難しいので、簡単な事象に変えてあげます。
対偶をとってnが合成数ならば2^n -1が合成数を証明すれば良いわけです。これならばn＝PQ(PQはそれぞれ自然数)として代入すれば良いわけです。(有名問題なので完全数と調べれば証明は出てきます。)
背理法について
Point 存在しないことを証明するときに有効。
例 nと2n＋1が互いに素であることを示せ。(一橋大)
これはつまり「nと2n＋1には2以上の公約数dが存在しない」ことを示せば良いわけです。
ここでそのようなdが存在すると仮定します。
自然数M,Lを用いて
n＝Md 2n＋1＝Ldと置いて代入すると
2(Md)＋1＝Ld
1＝(L−2M)d
dは２以上の自然数であり、L−2Mは自然数なのでこの等式は絶対に満たされません。1は2以上の自然数ではないのに
1＝(二以上の自然数)×(自然数)で表されてしまうからです。こんなことは絶対にないですよね。なのでこのようなdは存在せず矛盾なんです。よってd＝1に限るため、公約数は1であって互いに素だと証明できるわけです。
理解できたでしょうか。難しくてもノートにこの証明を実際に手を動かして書いてみると対偶と背理法の真髄が理解できるでしょう。
シェアしよう！
そのほかの回答（2件）
私の経験上、背理法は使えないけど対偶を考えれば解けるというケースに出会ったことがありません。
なので基本的に背理法を用いるようにすれば良いと思います。
また、背理法の方が用いることのできる条件が一つ多くなるので、解き易いことが多いです。A⇨Bという命題を示したいとします。対偶を考えるときは「Bでない」という条件から「Aでない」を示すことになります。使える条件は1つです。一方で、背理法では、「Aである」という条件と「Bでない」という2つの条件から矛盾を導くことになります。後者の方が用いることのできる条件が多くて考えやすいことが多いです。
質問者からのお礼コメント
理解しました！ありがとうございます！