- 締切済み
対偶による証明法と背理法による証明について
数学Iの内容なのですが自分の使っている参考書に 対偶による証明法も一種の背理法と考えることが出来る。 命題p⇒qが真であることをいうために¬qと仮定して¬pが導かれたとする。 pではないからこれは矛盾で背理法が成立したことになる。 でも¬q⇒¬pとは文字通りこれは対偶のことで、これが真と言えたから 自動的に元の命題が真といってもいい と書いてあるのですが、色々な所で質問してみたのですが どうしてもあまり理解ができません。 (1)命題p⇒qが真であることをいうために¬qと仮定して¬pが導かれたとする 導かれた形は¬q⇒¬p 背理法の仮定の形では¬q⇒p (2)pではないからこれは矛盾で背理法が成立したことになる この導かれた形が¬q⇒¬pで命題の対偶の形をしていて それによっても命題が真であることが示されているから 対偶による証明法も一種の背理法と考えることが出来る、と書かれているのでしょうか?
- kuramochiwagon
- お礼率0% (0/40)
- 数学・算数
- 回答数9
- ありがとう数0
- みんなの回答 (9)
- 専門家の回答
みんなの回答
- Caper
- ベストアンサー率33% (81/242)
ごめんなさい。回答: No. 8 の訂正です。下から 2 番目 の ● 項目 においてです。 [ 誤 ] q = ( β = 2 α + 1 ) [ 正 ] q = ( β = 2 α + 1 は無理数である )
- Caper
- ベストアンサー率33% (81/242)
● 私は機転がきかなかったかもしれません。 ● 背理法の証明のしかたは、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 の両方がいずれも真であるという結果が得られる。矛盾。
- Caper
- ベストアンサー率33% (81/242)
ごめんなさい。回答: No. 6 に脱落がありました。回答: No. 6 上から 3 番目 の ● 項目においてです。以下の記述をつけたしてください。 「 ¬q が真であると仮定する 」という操作は、命題 (¬q ⇒ ¬p) が真であることを証明する際に必要となります。このように私は記述しました。加えて、この操作は後半において矛盾を発生させる際においても必要となります。 また、上記の説明では、"意識的に" 「 ¬q が真であると仮定する 」という記述を避けました。理由は、わかりやすさを追い求めたためです。上記の説明を正しいものとするためには、「 ¬q が真であると仮定する 」という記述を 2 か所 において補う必要があると、私は思います。 それから、小さな訂正を 1 つ。 回答: No. 6 上から 2 番目 の ● 項目におけるいちばん最後です。 [正] …、上記の『 』内の記述にあたるのではないかと、私は考えます。
- Caper
- ベストアンサー率33% (81/242)
● 私は 回答: 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 については「 仮定 」ではなく、「 前提 」という用語を用いるべきかもしれません。くわしくは、専門書でご確認ください。
- jmh
- ベストアンサー率23% (71/304)
参考書が証明したいのは、命題p⇒qです。 > 一種の背理法と考える… > まず「命題p⇒qの否定」を仮定する(←省略されています)。 > …¬qと仮定して¬pが導かれたとする。 > そうして、「¬q⇒¬p」が証明できたとします。これと、背理法の仮定「pなのにqでない」の後半から、「¬p」と言えます。 > pではないからこれは矛盾 > しかし、前半は「p」なのですから、これが矛盾です。 > 自動的に元の命題が真といってもいい > 対偶が証明できたときは、元の命題が証明できたことになる。 こんな感じじゃないかしら。
- Caper
- ベストアンサー率33% (81/242)
● 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 です。 ● まちがっていましたら、ごめんなさい。
- Rice-Etude
- ベストアンサー率46% (122/261)
ここで書かれているものは、情報セキュリティにおける暗号や電子署名の安全性の証明に使われるやり方です。なので、これでうまく説明できるかわかりませんが、概略的に書いてみます。 A:ある難しい(多項式時間で解けない)と思われている問題(例:離散対数問題や素因数分解問題など) B:あるセキュリティアルゴリズム(例:暗号方式や電子署名方式など) 証明したいこと: Aが多項式時間で解けないなら、Bも多項式時間で解読できない、すなわちBのアルゴリズムは計算量的に安全である。 証明方法: まず、Bのアルゴリズムが多項式時間で解読できると仮定した時に、Aが多項式時間で解くことができることを証明する(¬q⇒¬pを証明)。 この流れ全体(¬q⇒¬p)は真であるが、実際のAについては多項式時間では解けないと思われている(すなわち(おそらく)¬pは偽で、pが真)。 したがって流れ全体の真性を崩すことなく、かつ「Aは多項式時間で解けない」という事実を満たすには「Aが多項式時間で解けないなら、Bも多項式時間で解けない」(すなわちp⇒q)が正しい。 つまり、流れ全体の真性と、個々の命題の真性を照らし合わせて、どの表現が事実になるかを求めることが実際の証明になります。 #蛇足ですが、「思われている」とか「(おそらく)」と書いているのは、実際にはAが本当に多項式時間で解けるかどうか(P=NP問題)が証明されていないからです。なので、本当なら上で書いた証明はまだ不完全で、実際に使われている暗号アルゴリズムは(あくまで理論上ですが)100%安全性が保証されているわけではありません。
- alice_44
- ベストアンサー率44% (2109/4759)
対偶法と背理法の、それぞれの「結論」を確認しよう。 質問文の対偶法では「p⇒q」を、背理法では「p」を 証明する話をしており、「p」や「⇒」の役割が異なる。 証明する対象の命題に含まれる「⇒」と、証明内で 何かから何かが「導かれた」ことを、区別すべし。
- Tacosan
- ベストアンサー率23% (3656/15482)
「背理法の仮定の形では¬q⇒p」って, どういう意味なんでしょうか?
関連するQ&A
- 背理法による証明と対偶による証明法について
自分の使っている参考書に 「対偶による証明法も一種の背理法と考えることができる。 命題p→qが真であることをいうために ̄q(qでない)と仮定して ̄pが導かれたとする。 pではないからこれは矛盾で背理法が成立したことになる。 でも ̄qならば ̄pとは文字通り、これは対偶のことでこの対偶が真といえたから自動的に命題が真といってもいい」 と書かれているのですがいまいち意味がわかりません。 どういうことなのでしょうか? 数1の内容なのですがあまり数学が得意ではないので簡単に教えていただけると助かります よろしくお願いします。
- 締切済み
- 数学・算数
- 背理法と対偶法について
少し長くなるのですがお願いします。 私の使用している参考書に 「対偶による証明法も一種の背理法と考えることができる。 命題p→qが真であることをいうために¬q(qでない)と仮定して¬pが導かれたとする。 pではないからこれは矛盾で背理法が成立したことになる。 でも¬qならば¬pとは文字通り、これは対偶のことでこの対偶が真といえたから自動的に命題が真といってもいい」 と書かれていて この部分の意味がわからなかったので出版社に問い合わせました。 すると、このような回答を頂きました。 -------------------------------------------------------------------- 背理法は、 「pという前提条件下で、結論のqを否定して、¬qと仮定すると、矛盾が生じる。よって、p⇒q」とする論法ですね。対偶法において、この矛盾に相当するものが、 「¬pかつp」という矛盾です。なぜなら、¬q⇒¬pを示すのが対偶法だからです。 つまり、対偶:¬q⇒¬pが示されれば、この時点で「¬pかつp」という矛盾が生まれ、背理法が成立したことになります。 -------------------------------------------------------------------- 私は以前、この事に関する質問をここでして回答をいただいたのですが その時に頂いた回答をもとに考えたのがこの考え方です。 ---------------------------------------------------------------------- 「pならばq」を証明しようとしていて 「pならばq」に背理法を使って「pであって¬q」と仮定する。 その過程で「対偶 ¬qならば¬p」が証明できたとする。 「pであって¬q」と仮定しているのに対偶 ¬qならば¬p なので pではないため矛盾する。 よって「pならばq」は真である。 命題の対偶が証明された場合、普通は自動的に命題が真であると考えますが この説明文では 「命題の対偶が証明されたあと、背理法を使って命題が真であることを証明することになるので 対偶による証明法も一種の背理法と考えることが出来る」 ということが書かれている。 -------------------------------------------------------------------------- 出版社から頂いた回答と、この自分の考えが 合っているのか自信がもてません。 出版社にはこの事以外にも色々質問していて、何度もメールしづらいのでここで質問させてもらいました。 よろしくお願いします。
- 締切済み
- 数学・算数
- 対偶法も背理法の一種という考え方について
あるテキストの「対偶法も背理法の一種として考えることが出来る」ということについての説明で 命題「pならばq」を証明する過程で、「¬qならば¬p」が証明できたとする。 「pならばq」を背理法で証明するために「pならば q」を否定して「pかつ¬q」。 証明されている「¬qならば¬p」はpではないので 「pかつ¬p」となり矛盾。 背理法が成立して「pならばq」は真。 対偶法なら 「命題「pならばq」を証明する過程で、「¬qならば¬p」が証明できたとする。」の段階で自動的に命題が真といっていい。 という説明があるのですが なぜこれが「対偶法も背理法の一種として考えることが出来る」ということになるのか理解できず 出版社に問い合わせたところ 「対偶が成り立つので、矛盾が生じ、背理法が成立する。 よって、元の命題が成立する」 ということのようなのですがいまいち理解が出来ません。 私の考えでは、 対偶法による証明法の場合、対偶が証明された時点で自動的に命題は真である、と考えますが 対偶をつかって背理法によって命題が真であることを証明できるので 対偶が証明されたあと、自動的に命題が真であるということではなく 背理法によって命題が真であると言っているということが出来るので 対偶による証明法も一種の背理法と考えることができる ということだと思ったのですが、出版社の説明と私の考えはどのあたりが違うのでしょうか? 私はあまり数学が得意ではなく、これも数Iのレベルのものなので そんな私でも理解できるように説明していただけると助かります。 よろしくお願いします。 この質問とは違うのですが、これら関する質問を以前ここでさせてもらい、参考にさせてもらいました。 その時回答をしてくださった方ありがとうございました。
- ベストアンサー
- 数学・算数
- 対偶を示して証明する背理法について
対偶証明法も背理法の一種と考えることが出来る。 という考え方があるのですが それで、その理由について 「命題「pならばq」を証明する過程で、「¬qならば¬p」が証明できたとする。 命題を背理法で証明するために「pならばq」を否定して「pかつ¬q」。 証明されている「¬qならば¬p」はpではないので 「pかつ¬p」となり矛盾。 背理法が成立して「pならばq」は真となる。 対偶法なら 「命題「pならばq」を証明する過程で、「¬qならば¬p」が証明できたとする。」の段階で自動的に命題が真といっていい。」 という説明があるのですが 自分は 対偶証明法は 対偶を示して証明する形式の背理法と 「対偶を示して証明する」という流れが同じなので 対偶証明法も 見方によって 「対偶を示して証明する形式の背理法」と考える事が出来るので そういう意味で 「対偶証明法も背理法の一種と考えることが出来る」 ということになる、と 理解したのですが この考え方は間違っているのでしょうか?
- ベストアンサー
- 数学・算数
- 背理法と対偶法の関係について
自分の使っているテキストに 対偶法も一種の背理法と考えることが出来る。 命題「pならばq」を証明する過程で、「¬qならば¬p」が証明できたとする。 命題を背理法で証明するために「pならばq」を否定して「pかつ¬q」。 証明されている「¬qならば¬p」はpではないので 「pかつ¬p」となり矛盾。 背理法が成立して「pならばq」は真となる。 対偶法なら 「命題「pならばq」を証明する過程で、「¬qならば¬p」が証明できたとする。」の段階で自動的に命題が真といっていい。 という事が書かれており これは 「対偶法の考え方でみると「対偶が真」と証明された時点で、自動的に命題が真であると考えますが 対偶法の「対偶が証明されると、元の命題が真になる」 という流れが自動的にではなく背理法によって証明されている、と考えることが出来るので 対偶法は背理法であると考えることが出来て 「対偶法は一種の背理法と考えることが出来る」ということになる」 ということが書いてあるということで理解できました。 しかし、なぜ「一種の」と書かれているのか気になっています。 そこはあまり深く考えなくてもいいと別の場では言われたのですが、ここがわからないと理解できた気がせず、どうしても気になってしまい悩んでいます。 自分が考えているのは 対偶法を背理法として考えた場合、 それは「 背理法の中の対偶を示して証明する形式のもの」 を表している。 しかし背理法は対偶以外を示して証明することも出来るので 「背理法の何個かある証明の形式のうちの一つと同じと考えることが出来る」という意味で 「一種の背理法」という表現がされている ということかと考えています。 この考え方で間違っていることはあるでしょうか? どうかよろしくお願いします。
- ベストアンサー
- 数学・算数
- 対偶法による無理数の証明について教えて下さい。
√2が無理数ならば√2+1は無理数であることを証明せよ。 を背理法ではなく、対偶法で以下のように考えました。 √2+1=P(有理数)とすると√2=P-1(有理数)となり√2が有理数であること が証明された。 よって対偶法が真なので元の命題も真である。 これでも問題ないですか?
- ベストアンサー
- 数学・算数
- 対偶と背理法
こんにちは。 実数xが無理数であるとき,2xは無理数であることを証明せよ。 対偶は 2xが有理数ならばxは有理数である。 2xが有理数なので、2x=p/q (pとqは互いに素)とおける。 両辺2で割って、x=p/2q である。ここで、右辺のp/2qは有理数 であるから、左辺xも有理数。 対偶が真なので元の命題も真である。 これを背理法で解くとき, 2xを有理数とすると,2x=r (rは有理数)とおくと,x=r/2 rは有理数なので,r/2も有理数である。このことはxが無理数で あることと矛盾する。 したがって,2xは無理数である。 何がどう違うのでしょうか。
- 締切済み
- 数学・算数
- 数学A 対偶と背理法
命題が真であることを証明するのに、どういう場合に対偶を用いて証明し、どういう場合に背理法を用いて証明すればいいのか分かりません。 どなたか、教えてください。
- 締切済み
- 数学・算数
- 対偶法から背理法を導けるという事について
数日前に「対偶法は背理法の1つとして考えることが出来る」 ということについて、質問させてもらいました。 http://okwave.jp/qa/q8360646.html その事は解決したのですが、 回答の中で書かれていた 「対偶法が先にあれば、背理法を導くことが出来る」 というところが気になっています。 これがどういうことなのかよく理解が出来ません。 「背理法が先にあれば、対偶法が成立をすることを背理法によって導くことが出来る」 というのは私が上の質問で書いてあることだと思います。 これは対偶法を使って背理法が正しいことを導くということなのでしょうか? もしそうであれば、どのような流れになるのでしょうか? あまり考える必要がない部分かもしれませんが、どういうことか気になるのでよろしくお願いします。
- 締切済み
- 数学・算数
補足
命題p⇒qが真であることをいうために¬qと仮定して¬pが導かれたとする と書かれているので 背理法は結論を否定するやり方なので 結論qがqでないならば、pである という意味です