対偶命題 背理法 違い

背理法を使って証明するときと対偶命題を使って証明するときとの違いはなんですか?

No.8 ベストアンサー 回答者： tknakamuri 回答日時： 2012/02/26 10:56

難しくなってきましたね。

時間がなくて、あまり専門書をあたってないのですが、
とりあえず、今感じている疑問を述べておきます。

まず、素数の定義の話ですが、ユークリッドの証明では
素数は別の複数個の素数の積にならない(合成数ではない)
ということみたいです。

もうひとつは、恒偽命題について。

素数の背理法による証明では、Q, ￢Q は前提条件 ￢P
が成り立たない範囲では未定義の命題を使っています(定義域が狭い？)。
そこから恒偽命題を導けるのでしょうか？

また、それを認めるにしても、それをPを証明する
対偶証明に使うのは変ではないでしょうか？

No.10 回答者： Caper 回答日時： 2012/03/07 15:20

　ごめんなさい。

私は ANo.9 を投稿した者です。

　ANo.9 において、よけいな記述がまぎれこんでいました。削除してください。1) 式 においてです。

　( 誤 )
　1) (P ∧ ￢Q) → P という命題は、

　( 正 )
　1) (P ∧ ￢Q) → P

No.9 回答者： Caper 回答日時： 2012/03/07 14:59

● まず、1つ の例題によって、そのちがいを私は示してみました。

ごらんください。

　 例題
　「 x^2 が奇数であるならば、x は奇数である 」という命題が真であることを証明せよ。( ただし、x の変域は、自然数全体の集合であるとする )

　《 x^2 が奇数であって、》x が偶数であると "仮定する" ならば、x = 2m を満たす 自然数m が存在します。このとき、次の等式が満たされます。
　 x^2 = (2m)^2 = 4m^2 = 2(2m^2).
　 この等式が満たされることによって、x^2 が偶数であることが示されます。★《 これは、x^2 が奇数であるともしている "仮定" に反します。》
　 ( 証明終わり )

　 上記の証明の最初と最後に、《 》でくくった記述があります。これらの 2つ の記述を証明に盛りこめば、背理法による証明になると、私は思います。《 》でくくった 2つ の記述を省けば、「 証明しようとする命題の対偶 」の証明ということになると、私は思います。

● 記号を用いて、補足の説明をさせてください。

　 アルファベットの大文字は、それぞれ命題を表わすものとします。→ という記号は「 ならば 」を意味するものとします。￢ という記号は「 否定 」を意味するものとします。∧ という記号は「 かつ 」を意味する記号とします。

　 2つ の 命題 A, B を 次のとおりに置くことにします。

　 A = ( x^2 は奇数である )
　 B = ( x は奇数である )

　 前述の例題は、A → B を証明せよというものでした。《 》無し の証明は、￢B → ￢A という命題が真であることを示したものです。

　《 》付き の証明では、★ 印 より前において、(A ∧ ￢B) → ￢A という命題が真であることを示しています。そして、★ 印 より後ろにおいて、背理法による証明が行なわれたことを強調する「 補足の記述 」がなされています。

● 背理法についてだけ、さらなる補足の説明をさせてください。

　 背理法は「『 真であることを証明しようとする命題 』の否定から矛盾を導く 」という証明手段です。もっとくだいて説明すれば、「 真であることを証明しようとする命題が P であるとき、￢P → ( 矛盾 ) が真であることを示す 」という証明手段です。なお、矛盾とは、「 つねに偽である命題 」のことです。

　 前述の例題において、証明しようとした命題は A → B でした。これの否定、すなわち ￢(A → B) は、A ∧ ￢B と同値です。前述の証明では、★ 印 より前において、(A ∧ ￢B) → ￢A が真であることを示したわけです。
　 ところが、￢A が「 つねに偽である命題 」という扱いを受けるのかと言うと、そうではありません。この場合、「 つねに偽である命題 」という扱いを受けるのは、￢A ∧ A ということになるのです。

　 話を少し脱線させます。
　 P, Q がいずれも命題であるとき、次の 1) という命題は、P, Q がどんな内容であっても、真になります。このように「 つねに真である命題 」のことを、トートロジーと呼びます。

1) (P ∧ ￢Q) → P という命題は、

　 また、P, Q, R がいずれも命題であるとき、次の 2) という命題と、3) という命題とは、P, Q, R がどんな内容であっても、同値になります。

2) (P → Q)∧(P → R)
3) P → (Q ∧ R)

　 話をもとに戻します。
　 前述の証明では、★ 印 より前において、(A ∧ ￢B) → ￢A が真であることを示しました。一方、(A ∧ ￢B) → A はトートロジーです ( 前述の 1) 参照 )。すなわち、(A ∧ ￢B) → A も真であるわけです。
　 これにより、次の 4) が真になるのは、おわかりですよね。

4) ((A ∧ ￢B) → ￢A)∧((A ∧ ￢B) → A)

　 この 4) が真であれば、次の 5) も真になります ( 前述の 2) 3) 参照 )。

5) (A ∧ ￢B) → (￢A ∧ A)

　 ￢A ∧ A は矛盾です。前述の証明における、★ 印 より後ろには、このような意味が隠されているのであると、私は思います。

● 背理法による証明として、よく話題に上るのが、√2 が無理数であることの証明です。

　 2つ の 命題 A, B を次のとおりに置くことにします。

　 A = ( √2 は無理数である )
　 B = ( √2 = m/n であって、なおかつ m/n は既約分数である 整数 m と 自然数 n が存在する )

　 √2 が無理数であることの証明は、申し上げるまでもなく、A が真であることを示せばよいわけです。

　 証明の手順は、次の 1> - 4> であると、私は思います。通常、3> 4> については、明記されないでしょう。また、2> から 3> にかけては、理解しづらいかもしれません。命題 P が真であれば、どんな 命題 Q を持ってきても、すなわち、命題 Q が真であれ偽であれ、Q → P は真であるということを利用しています。

1> 有理数についての定義などにより、￢A → B が真であるということを示す。
2> ￢B = ( どの 整数 m をとっても、どの 自然数 n をとっても、√2 = m/n であるならば、m/n は既約分数ではない ) が真であることを示す。
3> 自動的に、￢A → ￢B が真であることが示される。
4> 自動的に、￢A → (B ∧ ￢B) が真であることが示される。

　 上記の 4> における B ∧ ￢B が矛盾です。

● 私はそこつ者です。以上の記述の中にあやまりが含まれている可能性は高いです。まちがっていましたら、ひらにごめんなさい。
　 また、理解しづらい個所がございましたら、[ 補足 ]欄 を利用するなどして、遠慮なくお知らせください。

No.7 回答者： Tacosan 回答日時： 2012/02/23 02:23

#5 でも書いたんだけど, ぎりぎりいうためには設定をきっちり詰めておく必要があります.

というのも, いくつかの道具立てをすると #6 の「背理法」は「『対偶証明』の最後を省略したもの」と解釈できてしまいます. つまり, #6 では ￢P→Q と ￢P→￢Q からいきなり P を導いていますが, ここは
[(P→Q)∧(P→R)]→[P→(Q∧R)],
(Q∧￢Q)→f
(f は恒偽命題)
を認めれば
[(￢P→Q)∧(￢P→￢Q)]→[￢P→(Q∧￢Q)]
(Q∧￢Q)→f
から
[(￢P→Q)∧(￢P→￢Q)]→(￢P→f),
従って「￢P から『￢P を前提としない恒偽命題』を導いた」とみなせます.

逆に, 「対偶証明」も
t→(P→t)
(t は恒真命題) を認めれば
￢P→t
￢P→f
という「前提が等しく結論が矛盾した 2つの命題」から「背理法」で P を証明できる, といえます.

#6 の例をそのまま借りれば
[対偶証明→背理法]
√(2)が有理数 ⇒互いに素な偶数が存在する
√(2)が有理数 ⇒互いに素な偶数は存在しない
よって背理法より √2 は有理数ではない

[背理法→対偶証明]
素数は有限個である⇒全素数の積+1は合成数(￢Pから)
素数は有限個である⇒全素数の積+1は素数(素数の定義から)
よって「素数は有限個である」という仮定から「『合成数でありかつ素数である』ような整数が存在する」という結論が得られ, これはもちろん前提 (「素数が有限個」) によらず恒偽だから対偶証明により「素数は有限個ある」の否定が正しい... あれ? なんかおかしい. 「素数の定義」から, なんで「全素数の積+1は素数」といえるんだろう....

まあいいや. いずれにしても
いくつかの道具を認めれば『背理法』と『対偶証明』は本質的に同じ
(ただし対偶証明にしようとするともっと長くなる)
ということで.

No.6 回答者： tknakamuri 回答日時： 2012/02/22 21:56

No. 4 です。

ちょっと復習してみます。
さっき本から導き直したのですが
専門家ではないので、間違っているかもしれません。
誤っていればご指摘ください。
＃できれば具体例をあげておねがいします。

対偶証明とは何か。

1) 証明したい命題を P とします。
2) ￢P⇒￢Q という命題を探し出します。
この時 ￢Q が「￢Pを前提とせずに」恒偽命題なら
Q⇒P より P も恒真命題になります。

例 P: √(2)は無理数である。
　 ￢P⇒￢Q : √(2)が有理数 ⇒互いに素な偶数が存在する(恒偽命題)

背理法とは？

1) 証明したい命題を P とします。
2) ￢P⇒￢Q と ￢P⇒Q という命題を探し出します。
￢Q と Q は ￢P を前提にしてかまいません。
このような命題が存在した場合 P と推論します。

例 P: 素数は無限個である。
　 ￢P⇒Q 　:　素数は有限個である⇒全素数の積+1は合成数(￢Pから)
　 ￢P⇒￢Q :　素数は有限個である⇒全素数の積+1は素数(素数の定義から)

No.5 回答者： Tacosan 回答日時： 2012/02/22 13:25

難しい話だねぇ....

そもそも「正しい証明」かどうかを判定するためにはベースとなる論理体系や基礎的な知識としての公理, あるいは正しい道筋としての推論規則などを決めてやる必要があります. そして, これらの決め方によって「背理法による証明と対偶証明が同じかどうか」も決まります. つまり, ある設定においては「背理法で証明できる定理と対偶を使って証明できる定理とは全く同じ」となりえますし, 設定を変えるとそうでなくなってしまうこともあります.

で, #4 の「素数が無限個存在する」ことの証明も, 見ようによっては対偶証明といえなくもないです. 証明をたどると明らかですが, 実は「明言されていない仮定」がいくつかあります. つまり, この証明は
「いくつかの『明言されていない仮定』が成り立つ」ならば素数が無限個存在する
ことの証明です. これの対偶は
素数が有限個であれば「『明言されていない仮定』がすべては成り立たない」
で, #4 の証明はまさにこれを示しているともいえます.

勢いで「すべての証明は背理法」といってもいいのかもしれんけど, これは (ある面正しいとはいえ) 言いすぎだよなぁ....

No.4 回答者： tknakamuri 回答日時： 2012/02/22 09:06

背理法の証明のほとんどは対偶証明に置き換えられます。

但し、置き換えられないものもあるので同じものでは
ありません。

有名な、「素数は無限個ある」の背理法による証明は

P=素数は無限個ある
￢P=素数は有限個である

￢P→全ての素数の積 + 1 は仮定から合成数である。
￢P→全ての素数の積 + 1 は素数の定義から素数である。

つまり Q=全ての素数の積 + 1 は合成数 とすると
￢Q ∧ Q が真で矛盾

つまり ￢P から ￢Q ∧ Q が直接導かれていますが　

これはどうひねっても対偶証明に変換できなかったと
記憶してます。

No.3 回答者： boiseweb 回答日時： 2012/02/19 23:09

http://okwave.jp/qa/q6051628.html
↑の#1が，たぶん，そのままこの質問への回答になると思います．

No.2 回答者： han-ten 回答日時： 2012/02/19 22:43

背理法：

証明したい事象Aと、それとは別の事象Bがあり、Aの否定がB、Bの否定がAであるとき、「Bを突き詰めると矛盾が発生する」ことを証明することによって、Aが正しい事を結果的に導き出す方法
例）あるAが無理数だということの証明。Aが有理数であると仮定する（=B）と、矛盾が発生してしまう。故にAは無理数。

対偶命題を用いる方法：
元の命題＝対偶命題だから、対偶命題が真であると証明できれば、元の命題も真であると証明できることを利用する方法
例）x≦0またはy≦0のとき、xy≦0であることを証明せよ。対偶命題は「x>0かつy>0のとき、xy>0」。これは真であるから元の命題も真。



といった感じだと思います。
間違ってたらすみません。

No.1 回答者： hugen 回答日時： 2012/02/19 22:36

例えば、「　√2 = 無理数　」　の証明 .