背理法とは対偶がその原理だと私は思っています。つまり対偶と背理法は基

　背理法とは対偶がその原理だと私は思っています。つまり対偶と背理法は基本的に同一と言う説です。

　ところが違うと言う方が多いようで、その原理式は((A⇒￢B)∧(A⇒B))⇒￢Aだというのです。
その意味がわかる方は詳しく説明してください。私はこの式は間違いと思います。

No.10 回答者： naenaea 回答日時： 2013/04/06 19:13

誤解してたら悪いんだけど、証明したい式がp⇒qの場合、

恒真式((A⇒￢B)∧(A⇒B))⇒￢AのAに￢(p⇒q)を代入すれば終わりじゃないのですか？
そういう意味とは違う？

No.9 回答者： MagicianKuma 回答日時： 2012/03/10 15:17

証明したい命題を　Ａとします。

多くの場合、ＡはＰ⇒Ｑの形をしています。

１．対偶を用いた証明
　　Ｐ⇒Ｑ　を証明するのにその対偶　￢Ｑ⇒￢Ｐ　を証明すればＰ⇒Ｑを証明したことになる。
　　その根拠となるのが　Ｐ⇒Ｑ　⇔　￢Ｑ⇒￢Ｐ　という恒真命題です。 (1)

２．背理法
　　Ａを証明するのにその否定￢Ａを仮定（真とすると）矛盾が発生すること示し、￢Ａが偽、つまりＡは真を導く方法です。
　　では、矛盾とはなにかというと、隠れていた公理や定義や証明済みの定理について、その否定が導かれたということです。
　　上記矛盾以外に、ＡがＰ⇒Ｑの形の場合は、Ｐは仮定として真とおきますから、証明の過程でＰの否定が導かれたということです。
　　たいていの背理法では、矛盾として上記が全てです。なので、公理等をＳ1,Ｓ2,Ｓ3,・・・Ｓnとおけば、
　　Ｐ⇒Ｑの￢(Ｐ⇒Ｑ) ⇒ Ｐ∧￢Ｑ　ですから￢Ｑから推論して、￢Ｐ∨￢Ｓ1∨￢Ｓ2∨￢・・・∨Ｓnが導かれれば、対偶をとって
　　Ｐ∧Ｓ1∧Ｓ2∧・・・∧Ｓn ⇒ Ｂ で対偶による証明と同じです。
　　ですが、背理法では、上記以外の矛盾として、その他の任意の命題（真偽はわかっていない）Ｘを持ってきて、証明の過程でＸと￢Ｘの両方が
　　導かれれば(排中律に反するので）最初に仮定した￢Ａが偽　すなわちＡは真　と導けかれるという考え方です。
　　その根拠となるのが　((￢Ａ⇒Ｘ)∧(￢Ａ⇒￢Ｘ)) ⇒ Ａ　という恒真命題です。 (2)

　　背理法では、￢Ａを真と仮定して推論してますから、上記のＸが真とわかっている命題であれば、（２）の左辺の∧の１項目の(￢Ａ⇒Ｘ)は真です。
　　なので、２項目 ￢Ａ⇒￢Ｘ が導かれればＡが導かれたことになります。　￢Ａは　Ｐ∧￢Ｑにほかなりませんから、￢Ｑから出発する対偶による証明です。


結論をまとめると
　　対偶を用いた証明とは、恒真命題(2)でＸを真の命題として、左辺２項目だけを使い (￢Ａ⇒￢Ｘ) ⇒ Ａ　を導く方法。
　　背理法とは、(2)の１項目と２項目が同時に成り立てば、Ａがなりたつを導く方法。

No.8 回答者： kabaokaba 回答日時： 2010/02/16 22:31

http://oshiete1.goo.ne.jp/qa5663283.html
↑
とりあえず，こういう問題で，前の議論を公にしないのは
きわめてアンフェアだと思うので，リンクはっときますね．
リンク先をみると質問者の考えがわかります．

＃なんで放置したまま同じ質問するのかあ。。。
＃締めきれば，あちこちに分散しないですむのに．

この回答へのお礼

このサイトは前に質問したサイトと同じではないでしょう??

前のサイトでは低レベルの回答者ばかりで、なんらの解決もしないし、しかも逃げ出したのは貴方ではなかったですか。それでも私にクレームつける資格があるのですか。

　逃げずに自説を詳しく説明すればいいのですよ。

お礼日時：2010/02/17 17:56

No.7 回答者： alice_44 回答日時： 2010/02/16 22:01

貴方の言う「基本的に同一」というのが、

公理として同値だという意味であれば、
普通の論理系では、その通りです。
ただし、二つの公理が同値か否かは、
それ以外の公理の下で決まることです。

ヒルベルトによる命題論理の公理系では、
対偶論法の公理を背理法に置き換えてもよいし、
ゲンツェンの自然演繹でも、
背理法の推論規則を対偶論法に置き換える
ことができます。

しかし、確か、ブラウアーの直観主義論理では、
背理法の公理を対偶論法に置き換えることは
できなかったんじゃないかな。(ヤマカン)
背理法から対偶論法を示すには、
二重否定の除去が必要だったはずだから。

No.6 回答者： koko_u_u 回答日時： 2010/02/16 20:11

>つまり対偶と背理法は基本的に同一と言う説です。

その説を詳しく説明して補足にどうぞ。


>私はこの式は間違いと思います。

ついでに間違いと考える根拠も補足に。

No.5 回答者： serpentboa 回答日時： 2010/02/16 19:35

最初の回答は論理表を使うものでしたが、

P⇒Q = ￢P∨Q ................. (1)
(P∨Q)∧(P∨R) = P∨(Q∧R) .... (2)
￢P∧P = F .................... (3)
P∨F = P ...................... (4)
￢(￢P) = P ................... (5)
P∨￢P = T .................... (6)

を認めれば、以下のようにブール計算によっても求める
ことができます。こっちのほうがわかりやすいかも知れないので
別解ということで、もうひとつアップしてみました:

((A⇒￢B)∧(A⇒B))⇒￢A
￢((A⇒￢B)∧(A⇒B))∨￢A ....... ∵(1)を使って変形しました
￢((￢A∨￢B)∧(￢A∨B))∨￢A ... ∵(1)を使ってさらに変形しました
￢(￢A∨(￢B∧B))∨￢A .......... ∵(2)で、Pを￢A、Qを￢B、RをBに見立てて変形しました。
￢(￢A∨F)∨￢A ................. ∵(￢B∧B)は(3)により常にF(偽)なので変形しました。
￢(￢A)∨￢A .................... ∵(4)を使って変形しました。
A∨￢A .......................... ∵(5)を使って、二重否定を取り除きました。
T ............................... ∵(6)により、この式は常にT(真)になります。めでたし、めでたし。

等幅フォントが使えないようで、がんばっては見ましたが、ちょっと見にくくなってしまいました。テキストファイルが添付できそうなら、同一内容を添付しておきます。

No.4 回答者： 33550336 回答日時： 2010/02/16 18:30

まず、貴方の使っている、

「基本的に同一」
という言葉が数学的に定義されたものではないので、当然数学的な解答は出てこない、ということを先に断っておきます。
このことから、この問題は各々の主観による問題になるのですが、私は背理法と対偶法は同じものだと思っています。以下でそう思っている「こころ」を説明します。
まずＡ、Ｂを命題とし、ＡならばＢを示したいとします。
もし対偶法を使うとするならば「￢Ｂならば￢Ａを示す」ということになりますが、これは「Ａかつ￢Ｂを仮定して矛盾（Ａかつ￢Ａ）を示す」ことと捉えることができます。
逆にＡを背理法で示したいとき、「￢Ａを仮定して矛盾を導く」という方法をとりますが、これはＣを恒真命題（要するに常に正しい命題）とすると、「￢Ａから￢Ｃ（つまり矛盾）を導き、対偶をとればＣ（つまり何も仮定されていない状態）からＡが示される」と、対偶を使っていると無理矢理捉えることもできます。
このように背理法と対偶法はその人のものの見方の違いだけであって、大差はない、というのが私の意見です。

最初にも述べましたが数学的にどちらか（背理法と対偶が「同じ」かどうか）を決定できる問題ではないので、貴方が納得する方で思っておけばいいと思います。その上で私の意見が参考になれば幸いです。

あと、原理式として書いてある式は正しいです。
その式は常に成立します。

No.3 回答者： imasokari 回答日時： 2010/02/16 17:56

こんばんは。

「ＡならばＢである」

に対して、

「ＡでないならばＢでない」は【否定】
「ＢならばＡである」は【逆】
「ＢでないならばＡでない」は【対偶】

です。#2さんのご回答の中に些細な誤りがありましたので、訂正させていただきました。

No.2 回答者： chie65535 回答日時： 2010/02/16 17:46

●背理法とは

命題Ｐを証明するとき、仮に「￢Ｐは真」と仮定し、それにより矛盾が発生する事を示し「￢Ｐは偽、つまり、命題Ｐは真」を導く事を言います。

ここで言う矛盾とは「ある命題とその否定が同時に証明されること。つまり(Ａ∧￢Ａ)が成り立つ状態」を言います。(Ａ∧￢Ａ)は((Ａ⇒Ｂ)∧(Ａ⇒￢Ｂ))としても構いません。

キモは「矛盾が起きる」と言う部分で「対偶」は一切関係ありません。

●対偶とは

命題「ＡならばＢである」のとき、命題「ＡでないならＢでない」を「対偶」と言います。

もちろん、２つの事象Ａ、Ｂは
・命題「ＡならばＢである」のとき、命題「ＡでないならＢでない」が成り立つとき
と
・命題「ＡならばＢである」のとき、命題「ＡでないならＢでない」が成り立たないとき
の２種類が起こりえます。

命題「日本人ならば人間である」のとき、命題「日本人でないなら人間でない」は成り立ちません。

命題「心臓が動いているなら生きている」のとき、命題「心臓が動いてないなら生きてない」は成り立ちます。

ここでは「矛盾」は無関係です。

単に「ある命題が与えられた時、待遇命題は、真になったり偽になったりする」と言う事実があるだけです。

対偶のみを用いて、何かの命題を証明する事は出来ません。

No.1 回答者： serpentboa 回答日時： 2010/02/16 17:31

「背理法とは対偶がその原理か」というところは、うまく答える力がありませんが、

P: ((A⇒￢B)∧(A⇒B))⇒￢A

は、正しいです。理由は以下です(簡単のため、真をT,偽をF と書きます):

A, B, 共にTのとき:

A⇒￢B は、F です。
A⇒B は、T です。
だから、
(A⇒￢B)∧(A⇒B) は、F です。
だから、
((A⇒￢B)∧(A⇒B))⇒￢A は、T です。

同じようにして、
AがT,BがF:
AがF,BがT:
A, B, 共にF:

の場合を計算してみれば、すべての場合で問題の論理式が T になることが
わかります。(論理表を見ながら手を動かしてみると良い訓練になると思います)。

ついでですが、C を任意の論理式として、

((A⇒￢B)∧(A⇒B))⇒C は、T です。

日本語に翻訳すると、「前提が矛盾していれば、どんな論理式も真になりますよ」
ということですね。そして問題提起された論理式 P は、C を ￢A とした場合の
特殊ケースになっているというわけです。