対偶による証明法と背理法による証明について

質問

数学Iの内容なのですが自分の使っている参考書に

対偶による証明法も一種の背理法と考えることが出来る。
命題p⇒qが真であることをいうために￢qと仮定して￢pが導かれたとする。
pではないからこれは矛盾で背理法が成立したことになる。
でも￢q⇒￢pとは文字通りこれは対偶のことで、これが真と言えたから
自動的に元の命題が真といってもいい

と書いてあるのですが、色々な所で質問してみたのですが
どうしてもあまり理解ができません。

(1)命題p⇒qが真であることをいうために￢qと仮定して￢pが導かれたとする

導かれた形は￢q⇒￢p
背理法の仮定の形では￢q⇒p

(2)pではないからこれは矛盾で背理法が成立したことになる

この導かれた形が￢q⇒￢pで命題の対偶の形をしていて
それによっても命題が真であることが示されているから
対偶による証明法も一種の背理法と考えることが出来る、と書かれているのでしょうか？

回答No.9

Caper

ごめんなさい。回答: No. 8 の訂正です。下から 2 番目 の ● 項目 においてです。

　[ 誤 ]
　q = ( β = 2 α + 1 )

　[ 正 ]
　q = ( β = 2 α + 1 は無理数である )

回答No.8

Caper

● 私は機転がきかなかったかもしれません。

● 背理法の証明のしかたは、2 種類 あります ( 前提を設けるか、設けないか の 2 種類 ではありません )。こちらの Web ページ をごらんください。

　 背理法 reductive absurdum
　 http://100.yahoo.co.jp/detail/%E8%83%8C%E7%90%86%E6%B3%95/

　 その Web ページ の中では、それら 2 種類 について、次のとおりに説明がなされています。

1) すでに真であるとわかっている事実や、2) 元の命題の仮設 …

　 kuramochiwagon さん が問題としている、背理法の証明のしかたは、2) に該当するものと思われます。仮設とは、(p ⇒ q) という命題における p のことです。

　 その Web ページ には、それぞれの例についての説明もなされています。1) の例 が「 凸多角形の内角のうち、鋭角であるものは 3 個 より多くない 」の証明です。2) の例が「 α を無理数とすると、β = 2α + 1 はまた無理数である 」の証明です。

● ところで、先日、私は次のとおりに記述いたしました。次の Web ページ の 回答: No. 11 においてです。

　 http://okwave.jp/qa/q7931613.html

　「 書物などで見受けられる背理法の説明の多くは、『 前提 』の存在が織りこみ済みになっているのではないかと、私は思います 」

　 この前提という用語を理解するのに、私はたいへん苦労いたしました。ですから、初歩の段階でこの用語に深入りすることを、私はおすすめいたしません。
　 (p ⇒ q) という命題を、背理法を用いて証明する際にまず行なう操作は、(p かつ ￢q) という命題を真とすることです。前提を設けても設けなくても、いちばん最初に行なう操作は、(p かつ ￢q) という命題を真とすることです。初歩の段階であれば、このような認識で問題ないはずです。

● 上記の 2)

　 p = ( α は無理数である )
　 q = ( β = 2 α + 1 )

　 (p ⇒ q) という命題が真であることを、これより証明する。

　 (p かつ ￢q) という命題が真であるとした場合、p と ￢p の両方がいずれも真であるという結果が得られる。矛盾。

● 上記の 1)

　 p = ( x は凸多角形の内角である )
　 q = ( x の内角のうち、鋭角であるもは 3 個 より少ない )
　 r = ( x の各頂点における外角の総和は 360 度 である )

　 (p ⇒ q) という命題が真であることを、これより証明する。

　 (p かつ ￢q) という命題が真であるとした場合、r と ￢r の両方がいずれも真であるという結果が得られる。矛盾。

回答No.7

Caper

ごめんなさい。回答: No. 6 に脱落がありました。回答: No. 6 上から 3 番目 の ● 項目においてです。以下の記述をつけたしてください。

「 ￢q が真であると仮定する 」という操作は、命題 (￢q ⇒ ￢p) が真であることを証明する際に必要となります。このように私は記述しました。加えて、この操作は後半において矛盾を発生させる際においても必要となります。
　また、上記の説明では、"意識的に" 「 ￢q が真であると仮定する 」という記述を避けました。理由は、わかりやすさを追い求めたためです。上記の説明を正しいものとするためには、「 ￢q が真であると仮定する 」という記述を 2 か所 において補う必要があると、私は思います。

　それから、小さな訂正を 1 つ。
　回答: No. 6 上から 2 番目 の ● 項目におけるいちばん最後です。

　[正]
　…、上記の『 』内の記述にあたるのではないかと、私は考えます。

回答No.6

Caper

● 私は 回答: No. 4 を投稿した者です。その回答が kuramochiwagon さん を混乱させてしまったかもしれません。ごめんなさい。

　 回答: No. 4 の記述はまちがいではないと、私は思っています。ですが、kuramochiwagon さん の目線に合わせた回答ではなかったようです。以下のとおりに改めさせてください。

● kuramochiwagon さん が問題としている文章の前半部分を、次のとおりに変更します。

　 命題 (p ⇒ q) が真であることをいうために、命題 (￢q ⇒ ￢p) が真であることが証明されたとする。

　 変更した上記の文章を足がかりにして、推論を始めます。

　『 p が真であると仮定します。p が真であれば、(￢q ⇒ p) は真になります ( この証明は不要です。必ず真になります )。
　 一方、(￢q ⇒ ￢p) が真であることはすでに証明済みです。
　 これらの結果より、￢q から、p と ￢p が導かれたことになります。すなわち、￢q から矛盾が導かれたことになります。よって、￢q は真ではありません。すなわち、q が真となります。
　 以上の記述から、p が真であると仮定したことによって、q が真であるという結果を得ました。すなわち、p ⇒ q が真であることが証明されたわけです 』

　 kuramochiwagon さん が問題としている文章の後半部分は、次のとおりでした。「 pではないからこれは矛盾で背理法が成立したことになる 」
　 この後半部分をかみくだいて説明したものが、上記の『 』内の記述にあたあるのではないかと、私は考えます。

● 上記において「 p が真であると仮定します 」という記述はあっても、「 ￢q が真であると仮定する 」という記述はありません。ですが、「 ￢q が真であると仮定する 」という操作は、命題 (￢q ⇒ ￢p) が真であることを証明する際に必要となります。
　 回答者のみなさんの中に、この場合の仮定は (p かつ ￢q) であると主張なさる方々がいらっしゃいました。私もそう主張した 1人 です。この主張はまちがいではないと、私は考えます。

● 最後に、「 仮定 」という用語についてです。p については「 仮定 」ではなく、「 前提 」という用語を用いるべきかもしれません。くわしくは、専門書でご確認ください。

回答No.5

jmh

参考書が証明したいのは、命題ｐ⇒ｑです。

> 一種の背理法と考える…
>
まず「命題ｐ⇒ｑの否定」を仮定する（←省略されています）。

> …￢ｑと仮定して￢ｐが導かれたとする。
>
そうして、「￢ｑ⇒￢ｐ」が証明できたとします。これと、背理法の仮定「ｐなのにｑでない」の後半から、「￢ｐ」と言えます。

> ｐではないからこれは矛盾
>
しかし、前半は「ｐ」なのですから、これが矛盾です。

> 自動的に元の命題が真といってもいい
>
対偶が証明できたときは、元の命題が証明できたことになる。

こんな感じじゃないかしら。

回答No.4

Caper

● kuramochiwagon さん が問題としている文章を、私は次のとおりに補ってみました。

　 命題 p ⇒ q が真であることを言うために、( まず p と仮定し、その上 ) ￢q と仮定して ￢p が導かれたとする。( 導かれた ￢p は ) p ではない ( ということである ) から、これは矛盾で背理法が成立したことになる。

● この文章に出てくる矛盾とは、p かつ ￢p という命題のことであると、私は思います。一般に、矛盾とは、真になり得ない命題のことであると、私は認識しています。p かつ ￢p は真になり得ません。
　 そして、この文章が指し示す仮定とは、p かつ ￢q という命題のことであると、私は思います。

● p かつ ￢q と仮定したとき、すなわち p が真であり、￢q が真であると仮定したとします。このとき、p ⇒ p は必ず真になります ( 証明は不要です ) 。加えて、￢q ⇒ ￢p がもし証明されれば、p かつ ￢q という仮定から p かつ ￢p という矛盾が導かれることになります。それにより、仮定である p かつ ￢q が真ではないという結果を得ます。

　 p かつ ￢q という命題が真ではないという結果を得た場合、p かつ ￢q の否定が自動的に真になります。p かつ ￢q の否定とは p ⇒ q です。

● まちがっていましたら、ごめんなさい。

回答No.3

Rice-Etude

ここで書かれているものは、情報セキュリティにおける暗号や電子署名の安全性の証明に使われるやり方です。なので、これでうまく説明できるかわかりませんが、概略的に書いてみます。

A：ある難しい（多項式時間で解けない）と思われている問題（例：離散対数問題や素因数分解問題など）
B：あるセキュリティアルゴリズム（例：暗号方式や電子署名方式など）

証明したいこと：
Aが多項式時間で解けないなら、Bも多項式時間で解読できない、すなわちBのアルゴリズムは計算量的に安全である。

証明方法：
まず、Bのアルゴリズムが多項式時間で解読できると仮定した時に、Aが多項式時間で解くことができることを証明する（￢q⇒￢pを証明）。
この流れ全体（￢q⇒￢p）は真であるが、実際のAについては多項式時間では解けないと思われている（すなわち（おそらく）￢pは偽で、pが真）。
したがって流れ全体の真性を崩すことなく、かつ「Aは多項式時間で解けない」という事実を満たすには「Aが多項式時間で解けないなら、Bも多項式時間で解けない」（すなわちp⇒q）が正しい。

つまり、流れ全体の真性と、個々の命題の真性を照らし合わせて、どの表現が事実になるかを求めることが実際の証明になります。

＃蛇足ですが、「思われている」とか「（おそらく）」と書いているのは、実際にはAが本当に多項式時間で解けるかどうか（P=NP問題）が証明されていないからです。なので、本当なら上で書いた証明はまだ不完全で、実際に使われている暗号アルゴリズムは（あくまで理論上ですが）100％安全性が保証されているわけではありません。

回答No.2

alice_44

対偶法と背理法の、それぞれの「結論」を確認しよう。
質問文の対偶法では「p⇒q」を、背理法では「p」を
証明する話をしており、「p」や「⇒」の役割が異なる。
証明する対象の命題に含まれる「⇒」と、証明内で
何かから何かが「導かれた」ことを、区別すべし。

回答No.1

Tacosan

「背理法の仮定の形では￢q⇒p」って, どういう意味なんでしょうか?

補足

命題p⇒qが真であることをいうために￢qと仮定して￢pが導かれたとする
と書かれているので

背理法は結論を否定するやり方なので
結論qがqでないならば、pである

という意味です