背理法と対偶証明の違いについて

質問

背理法と対偶による証明は同じと私は考えています。しかし、インターネットを含み、世間では違うというのが定説かのようです。

　従って、違うとお考えの方に、その理屈と根拠を教えて頂きたいのです。

回答No.11

B-juggler

Ｃａｐｅｒさま　ありがとうございます。

Ｂ－ｊｕｇｇｌｅｒです。私もまだまだですね＾＾；

餅は餅屋と言いますが、なるほど。助かります。

そうか、Ａ→Ｂ　これを否定しないと背理法にはならないですよね。
　＃含意と加法の真理値で、A→B ≡ ￢A∨B　出てこないと嘘ですね

何で気が付かないかなぁ～。
　＃情けなくて、笑うしかないっていう（＾＾；）

((ψ→￢φ)∧(ψ→φ))→￢ψ
うんなるほどそうですね、分かりました。ありがとうございます。
いい勉強になります。根拠と言うよりそのものと言ってもいいのかも。

数学って面白いですね！　同じ世界なのにこうも分からないことがたくさんある　ヾ（＠⌒ー⌒＠）ノ

ありがとうございました。スッキリしました。

お礼

そんなに簡単に、この珍説に納得・同意していいのですか!!?

回答No.10

Caper

● 以下の文章は、skoyan さん にあてたものでは決してありません。
　 B-juggler さん にあてたものです。

● この質問の回答としては、kabaokaba さん が提示なさいました ANo.1 と ANo.2 が概ね適していると、私は思います。

　 背理法については、下記の Web ページ に説明があります。長岡技術科学大学の先生による説明のようです。

　『 集合と論理 』 ( p.3-4 )
　 http://pelab.nagaokaut.ac.jp/kondolab/convenience/pdffiles/syugou-ronri-main.pdf

● B-juggler さん による説明には、「 命題 A→B について証明する。
背理法ですから A→￢B を考える 」とあります。
　 残念ですが、これはまちがいで、命題 A→B を背理法で証明する場合には、A∧￢B を考えるものであると、私は思います。

　 A→B は ￢A∨B と同値です。記号を用いて示せば、次のようになります。
　 A→B ≡ ￢A∨B

　 ですから、A→B の否定 ￢(￢A∨B) は、A∧￢B となります。記号を用いて示せば次のようになります。途中で ド・モルガン の法則を用いています。
　 ￢(A→B) ≡ ￢(￢A∨B) ≡ A∧￢B

　 この ￢(A→B) ≡ A∧￢B から、矛盾を導いて A→B を示すというのが背理法であると、私は思います。

● いまここで、問題となっている 恒真命題 (= トートロジー) はこれですよね。
1) ((ψ→￢φ)∧(ψ→φ))→￢ψ
　 この恒真命題と背理法による証明がどう結びついているかということを、私は考察してみました。その考察は以下のとおりです。

　 1) は恒真命題ですから、1) は証明いらずの常に真である合成命題です。また、(ψ→￢φ)∧(ψ→φ) が真であれば、必ず ￢ψ も真になるという合成命題です。

　 ところで、背理法によって、仮に、
2) (A∧￢B)→￢A
が証明されたとします。つまり、「 A が真であって、B の否定が真であるときに必ず A の否定が真となる 」ことが証明されたとします。
　 2) という合成命題は恒真命題ではありません。ですから、いまここで、2) という命題が常に真であることを証明したとします。

　 そこで、次の合成命題を考えます。
3) ((A∧￢B)→￢A)∧(恒真命題)
　 この 3) は 2) と同値になります。さらに、次の命題を考えます。
4) (A∧￢B)→A
　 この 4) は恒真命題です。さらに、次の命題を考えます。
5) ((A∧￢B)→￢A)∧((A∧￢B)→A)
　 この 5) は 2) と同値になります。同値となる根拠は 3) と 4) です。

　 ですから、2) が証明されれば、自動的に 5) も証明されることになるのだと、私は思います。

　 1) の前提 ((ψ→￢φ)∧(ψ→φ)) と 5) を見比べれば、もうおわかりのとおりです。
　 2) が証明されれば、自動的に 5) も証明され、そして、1) という更新命題によって、￢(A∧￢B) すなわち A→B が証明されるという運びになるのではないかと、私は思います。

● 以上の考察では、K1, K2, … , Kn を登場させませんでした。説明が複雑になるからです。ご容赦ください。

● B-juggler さん に申し上げます。skoyan さん の挑発に乗ってはいけません。時間を無駄にするだけです。

お礼

● 以下の文章は、skoyan さん にあてたものでは決してありません。
　 B-juggler さん にあてたものです。

＊＊　と言う事で私が答えるのは悪いような気がしますが、とんでもない　　事を書いているので割り込みます。

● B-juggler さん による説明には、「 命題 A→B について証明する。
背理法ですから A→￢B を考える 」とあります。
　 残念ですが、これはまちがいで、命題 A→B を背理法で証明する場合には、A∧￢B を考えるものであると、私は思います。

　 A→B は ￢A∨B と同値です。記号を用いて示せば、次のようになります。
　 A→B ≡ ￢A∨B

　 ですから、A→B の否定 ￢(￢A∨B) は、A∧￢B となります。記号を用いて示せば次のようになります。途中で ド・モルガン の法則を用いています。
　 ￢(A→B) ≡ ￢(￢A∨B) ≡ A∧￢B

　 この ￢(A→B) ≡ A∧￢B から、矛盾を導いて A→B を示すというのが背理法であると、私は思います。

**　ここまでは正解です。

省略

●・・・ ところで、背理法によって、仮に、
2) (A∧￢B)→￢A
が証明されたとします。つまり、「 A が真であって、B の否定が真であるときに必ず A の否定が真となる 」ことが証明されたとします。
　 2) という合成命題は恒真命題ではありません。ですから、いまここで、2) という命題が常に真であることを証明したとします。

＊＊　「B の否定が真であるときに必ず A の否定が真となる」とは式で書　　　くとどうなりますか。￢B⇒￢Aですよ!!
証明したい元々の式はA⇒Bですね。これは≡￢B⇒￢Aてす。
　　　　A⇒Bの証明に￢B⇒￢Aを仮定して意味がありますか。
　　　以下には複雑に推論していますが、仮定が誤りでは無意味です。

● B-juggler さん に申し上げます。skoyan さん の挑発に乗ってはいけません。時間を無駄にするだけです。

＊＊　こんな珍説で他人を迷酔わすのはやめて下さい。
　　このようなスレッドは、もっと優れた方が多いのかと思っていたので　　落胆しています。

回答No.9

B-juggler

おそらくプロさんだと思うのですが、私では無理です。
先に宣言してしまいましょう。

＞((ψ → ￢φ)∧(ψ → φ))→￢ψ
これが「背理法の根拠」とされているのが分かりません。

私にとってはこれが全てです。
これが違うでしょ？と思うのです。
十分条件だけ否定しても、そこにある意味がつかめないでいます。
　＃私も数学屋ですから（代数系ですが）
　＃「思う」は意思表示だとして、受け取ってください。
　＃プロ同士で私不利な土俵ですし・・。
　＃ケンカするわけじゃないですから

引用はむやみにするものではないですね。。
手書きしてみたんです。　そしたら違いました。

～～～～
数学の証明などで、背理法で証明で・・・というときには、ほとんどが
A⇒Bの命題では￢B、つまりBの否定を仮定して演繹し何らかの矛盾を導き、結果的に￢B⇒￢A[≡￢(A∧K1∧K2∧・・・∧Kn)]≡[￢A∨￢K1∨￢K2∨・・・∨￢Kn]に達し、この対偶としてA≡(A∧K1∧K2∧・・・∧Kn)⇒Bを証明します。
　この導かれた矛盾が、直接的に￢Aの場合が￢B⇒￢Aと通常対偶と呼ばれている形です。しかしこれは潜在的には、Kiのすべてで前提されています。
～～～
重複していますが、すいません、これは対偶証明ですね、気が付くのが遅い！！
　＃再三申し上げている通り、順番は違いますが・・・。

もし背理法なら、こうなりませんか？
命題Ａ⇒Ｂについて演繹的に得られる解をKiとしましょう。

命題Ａ⇒Ｂについて証明する。
背理法ですから、Ａ⇒￢Ｂ　を考える。
ここから得られる解が、￢Ki　つまり
（Ａ⇒￢Ｂ）∧￢K1∧￢K2∧・・・・∧￢Ki∧・・・・∧￢Kn
≡[(￢（Ａ⇒Ｂ）∨￢Ki)]≡[（Ａ⇒Ｂ）∧Ki]・・・(1)
　＃順番がちょっと違いますが、Kiの取り方を変えただけです。

(1)式は∧か∨　か迷うところで　本職に聞かないと自信がありません。ただ、ここは対偶ではないですよね。ド・モルガンなだけでしょう？

これによって、Ａ⇒￢Ｂのとき背理的に　Ａ⇒Ｂ　が得られる。
こういう証明にならないでしょうか。

Ａ⇒Ｂ　の証明をするときに、十分条件のほうだけ否定した答えになるのかなぁ？　と思いまして。
　＃手書きと違うのを気が付かないのも馬鹿な話なんですが＾＾；

プロさんだと、お見受けしています。
なので、ここが分からないと言っていきます。
宣言してますが、論理式は専門外です。
ここが私の限界です。

どっちにしろ本職に一回頼んでみます。
　＃こういう書き込みするのを嫌がる奴なので、あまり期待はしないで下さい。。

申し訳ないですが、質問させてください。
証明をしている、プロセスが違うが論理式に直すと同じものになる。
この場合は、論理形式上は「同じ証明」になるんでしょうか。
　＃それこそ本職に聞けば分かるのですが。。
　＃多分、違う式になるはず、と答えが返ってくると思うのですが。

議論（使われていますので私も使いますね）が平行線をたどるのは、
お互いに違うよ！と思い込んでいるからなのかなぁとも、感じます。

私の証明があっているとして、(1)式から同値を得るときに、対偶を取っていそうな気はします。何かが引っかかります。
同じなのかな？　プロセスが違うと思うけど。

こうなのかな？「背理法の証明では対偶の概念を使う」、でも対偶から演繹的に証明を図るときには、背理法は使わないでしょうし・・。
う～ん。

お礼

残念ながら、私はプロでもなんでもありません。
---------------------------------------------------
＞＞((ψ → ￢φ)∧(ψ → φ))→￢ψ
これが「背理法の根拠」とされているのが分かりません。
----------------------------------------------------
　この説を遠方にいる友人が主張して、頑として譲らず、そのくせ詳しい説明もなく、相手が逃げたままになってるので、謙虚に?自分に誤りがあるのかと色々読んだり考えたりしているだけです。

＞私にとってはこれ・・・・・・。

　＃私も数学屋ですから（代数系ですが）
　・・・・・・

　貴方のほうが自称数学屋というのですから、私よりはプロでしょう。
省略

＞命題Ａ⇒Ｂについて証明する。
背理法ですから、Ａ⇒￢Ｂ　を考える。
ここから得られる解が、￢Ki　つまり
（Ａ⇒￢Ｂ）∧￢K1∧￢K2∧・・・・∧￢Ki∧・・・・∧￢Kn
≡[(￢（Ａ⇒Ｂ）∨￢Ki)]≡[（Ａ⇒Ｂ）∧Ki]・・・(1)
　＃順番がちょっと違いますが、Kiの取り方を変えただけです。

・・・・ド・モルガンなだけでしょう？
・・・・・

　ここでの式が私の式の引用とすれば、引用の間違いです。またド・モルガンの定理と式自体の中には二重の間違いがあります。
　ド・モルガンの定理とは￢(A∨B)≡(￢A∧￢B)、￢(A∧B)≡(￢A∨￢B)のことです。
　従って(1)式の≡は二つとも成り立ちません。また￢(A⇒￢B)≡(A⇒B)と思っているような節がありますが、これも違いますよ。
省略

＞申し訳ないですが、質問させてください。
・・・・・
　具体性が無いのでよくわかりません。

＞議論（使われていますので私も使いますね）が平行線をたどるのは、
お互いに違うよ！と思い込んでいるからなのかなぁとも、感じます。

＞私の証明があっているとして、(1)式、・・・

　貴殿の説は間違いだらけです。
　A⇒Bを証明するというのは、既に証明済みの定理や公理や定義が前提になりA∧K1∧K2∧・・・∧Ki(≡ψ)⇒Bをψ⇒Bと証明するのであり、従って背理法で命題ないし結論を否定して矛盾に至るというのは、￢B⇒￢ψ(￢A∨￢Ki)になることで、その対偶からψ⇒Bが証明されるというのが私見であります。

　もっとお勉強されてから、議論に参加されることを望みます。

回答No.8

B-juggler

早速ありがとうございます。
論理のプロではないので、その辺はご容赦願いたく・・。

出来るだけ分かりやすい例を出して、他のアイディアが出てくれば・・・、論理記号だけだと入りにくいでしょうし、と考えてのことです。何せ自身が無いですから、論理記号で出来る気がしないんです。

ただ「違う根拠」は思い当たるんです。
言葉でもいいから伝わらないかなと。

＞((ψ → ￢φ)∧(ψ → φ))→￢ψ
これが「背理法の根拠」とされているのが分かりません。

全く違う見地なのか、おっしゃる通り無知でしかないのか。
　＃含意の真理値が「背理法の根拠」ではいけないですか。

プロセスの問題ではないか、と下に書かせていただきました。
引用ばかりさせてもらうのもどうかと、差し控えましたが
～～～～
数学の証明などで、背理法で証明で・・・というときには、ほとんどが
A⇒Bの命題では￢B、つまりBの否定を仮定して演繹し何らかの矛盾を導き、結果的に￢B⇒￢A[≡￢(A∧K1∧K2∧・・・∧Kn)]≡[￢A∨￢K1∨￢K2∨・・・∨￢Kn]に達し、この対偶としてA≡(A∧K1∧K2∧・・・∧Kn)⇒Bを証明します。
　この導かれた矛盾が、直接的に￢Aの場合が￢B⇒￢Aと通常対偶と呼ばれている形です。しかしこれは潜在的には、Kiのすべで前提されています。
～～～
ＮＯ．４の回答です。ここなんです。
卵なのか鶏なのか、になりそうですが。
この方法は背理法だと考えます。
　＃￢Ａが一つでも得られた時点で、背理法は終わりますね、実際は。

そこで、Ａ→Ｂ　に対し　￢Ｂ→￢Ａ　を先に出して、
　＃同値の論理式を作る作業が先に来る
ここから、演繹的に上記の方法で証明して「真」を得れば、
と言うのが、対偶証明になるのではないかなと。

くしくも書かれていますが、「結果的に」同じになっている。
ところが、プロセスが異なりますよね。
　＃順序は関係ない！論理的に同じならば、と言うことでしたら同じなんでしょう。
　＃実際の証明では、やることが変わってきますから、違うとしているだけかもしれませんね。

私の持っている理屈や根拠は、含意の真理値、後先の問題、後やはり条件だと。写像の証明とかやると、条件絡むんですよね。。

その道のプロに頼んでみます。出て来てくれるかどうかは分かりませんが。
ありがとうございました。

お礼

このような議論は文学的な議論と違います。論理学は知らないとか、記号がどうとかいうのは論議のらちがいですよ。特殊な記号などでは、解説すればいいだけですし、相手の議論のレベルと同等には論じるべきです。

　引用されている私の説は、背理法と言うのはすべて対偶の中に含まれているという論旨ですし。それに対して異議を唱えているのは・・・

((ψ → ￢φ)∧(ψ → φ))→￢ψが「背理法の根拠」・・・というものです。この式から(ψ → φ)が証明されるというのは、全くの間違いと言っています。

　この式から目的の(ψ → φ)は証明できるならしてください。できないはずです。というようなことは、言葉だけの議論ではできないはずです。

回答No.7

B-juggler

ちょっと気になってきました。ＮＯ．６です

えっと、論理式には強くないのですが
＞((ψ → ￢φ)∧(ψ → φ))→￢ψ
何でこれが背理法なんだろう？？？？

命題ψ → φを正しいと証明したいのに、ψだけ否定してどうするんだろう？
これなんか違う気がします。

１＋１→２　だとして、　
（１＋１が２ではない）∧（１＋１は２）　ならば　（１＋１）ではない？？
これは何がしたいんだろう？？

＞(￢ψ → ￢φ)→(φ → ψ)は(￢ψ → ￢φ)←(φ → ψ)
これは対偶そのものだし、同値なのは分かります。

変な話ですが、記号論理はおいてみましょう？

私は
「背理法は逆か裏（どっちでもいいんだと思うけど）をとって、矛盾すれば、命題は真」
「対偶法は、対偶をとって、出来た命題を証明することで同値なので証明とする」
と、考えています。
条件とかいろいろと絡んでくるのでしょうが、「反証」なのか「同値のもので別のアプローチをして正しいと導き出す」か。
この違いなのかなぁと思えてきました。

この考え方はどうでしょう？　お考えと違いますか？

これを論理式化する事はやったこと無いから、ちょっと考えて見ます。

私も勉強になりますから、ぜひお話させてください。

お礼

折角の御返信ですが、kabaokabaさんとのやり取りをご覧になりましたか。

「私も勉強になりますから、ぜひお話させてください。」と言うのは大変結構ですが、私が求めているのは、「対偶の証明と背理法は違う」という見解の方の理論です。

　その理屈では((ψ → ￢φ)∧(ψ → φ))→￢ψが、背理法の原理を示すというのですが、kabaokabaさんもかつて論争していた方も、其の解説ができな
いのに、それを妄信しているだけでした。従ってその理屈を聞きたいのです。

　どうやらこの私が誤りと思う理屈の根拠は、高校生向けの教科書か参考書にミスがあって、世間に広く流布されているようです。
　石谷茂氏の【∀と∃に泣く】現代数学社でも、そのようなミスの参考書が数冊見つかったと書いてあります。従って本になっているモノも、先生にもミスはあります。

　貴方はまだ対偶の意味も背理法の意味も、全く理解されてないようです。
書かれている例題も不適切です。初等幾何学の証明例題などで、まず適切な例を見つけるべきです。
　上記の参考書でも入手されて、少し理解を進めてからまた対話しましょう。
背理法と対偶が同一と思う私の見解は、kabaokabaさんへの返信をご覧ください。詳細に書いてあります。

　また念のまために、このようなお話では「そのように思う」とか「らしい」と言うのは使うへき言葉ではありません。

回答No.6

B-juggler

一応代数系だけど、論理数学にはそれほど強くないので先に申し上げておきますね。

背理法の証明と、対偶を使った証明が同じことではない、というのを説明させてもらえればいいわけですよね。

論理式は使いませんよ（もちろん強くないですし、細かな矢印の方向だけで論争になってしまう恐れもありますから）。

単純に行きましょう。
背理法の証明は、ある命題について（Ａ→Ｂ　これはこうしておきましょう）、ＡならばＢでないと仮定して、違うことを示すわけですよね。
Ａ→￢Ｂ　ですかね。

これだけしか証明してないんですよね。
もしものはなしですが、ＡならばＢではない。と証明できたとして、ゆえにＡならばＢと言える状態なら、使えるものだと私は解釈しています。
極端にこういう例で。
１＋１　ならば　２　である。　と言う命題に対して、
背理法では、１＋１　ならば　２ではない　とやってみるわけですよね。
通常の考え方（自然数の和）と考えれば、１＋１＝２なので、
１＋１　ならば　２　ではない　と言う仮定が間違っている。
ので、　１＋１　ならば　２　で大丈夫ですが・・・。

これは２進数ならダメですよね・・・。
２→１０（２進数）では　ですから

背理法は他の道が無いときにしか使えないと解釈しています。

対偶の証明は、他の道があっても大丈夫なんですよね。
（言い方を変えると、他の道には行かないんだと思うんですね）

同じように行きますね。Ａ→Ｂ　対偶で　￢Ｂ　→　￢Ａ　ですね。
１＋１ならば２　これの対偶、２でなければ　１＋１ではない。
　＃あってますよね。
仮に２進数の状況下においても、この証明は通用しますよね。

１０（２進数）でなければ１＋１　ではない　これはあっていますから
１＋１　ならば　１０（２進数）　２（１０進数）でも構いませんね。
これは否定のしようが無いですよね。

まとめます、ものすごく極端ですが。
「背理法」は他に逃げ道が無い状況でしか使えない、
　条件が結構厳しい。
「対偶証明」はどんな場合でも対外大丈夫。

私はこんな風に考えています。

論理学的にどうこうと言うよりも、「背理法の怖さ」とか「落とし穴」
のようなのがあると思っています。
　＃文献でもと思ったのですが、すいません何も見つかりませんでした

回答No.5

kabaokaba

なんか疲れてきたからそろそろ逃げます（苦笑）
んーー。。。宗教論争になってきそう．
たぶん，お互いの根本的な立脚点が違うんだと思うので
逃げるよ．私ディジタル回路には興味ないし．

＞この式(￢ψ → ￢φ)→(φ → ψ)は(￢ψ → ￢φ)←(φ → ψ)と同値なので、
いや，だからなんでなんですか？
一般にA->BとB->Aは同値じゃないでしょう．
今「同値」だというなら，この式では同値であるという
「証明」が必要ですよ．
＃実際は「二重否定の除去」ですけど

＞この前半の式(ψ → ￢φ)∧(ψ → φ)は何ですか。
＞(ψ → φ)の証明に使うためですね。
ちがうよ．
そもそも証明したい命題は「￢ψ」でしょう．
これを証明するために
ψを仮定すると，
φと￢φがでてきた．
そしたら，トートロジー
((ψ → ￢φ)∧(ψ → φ)) → ￢ψ
を使って、めでたく「￢ψ」でしょう．

＞((ψ → ￢φ)∧(ψ → φ))は展開すると￢ψです。従って￢ψ⇒￢ψを示すだけなので当然トートロジーです。ご存知でしたか

そうそう．トートロジー．
よかったよかった・・これを計算で示すのは
タイプするのが面倒かなと思ってた．
あなたがいう「展開」ってのが「命題論理での証明」ですよね．
この展開の途中で「対偶」使いますよね．
つまり，「対偶」を使って証明したわけですよ．
定理ですよ，万歳！
このトートロジーを「背理法」というわけです．

命題論理の公理系から，延々と展開して
でてくる命題論理の定理は「トートロジー」でしかないのです．
けどそれが大事で，したがって，命題を構成するパーツの命題の
真偽に関係なく，推論として成り立つ「正しい推論」ですね．

((ψ → ￢φ)∧(ψ → φ)) → ￢ψ

っていう式が
トートロジー（ψとφの真偽にかかわらず常に真）
なんだから
ψ → ￢φ
と
ψ → φ
が示されたならば
(ψ → ￢φ)∧(ψ → φ)
がでてきて，
＃ここは，A, BからA∧Bを導出できるってあれ
めでたく合意が得られた「トートロジー」によって
￢ψ
がでてくる
＃これはAとA→BからBが導出できるってあれ
これってまさに背理法．

でわ

補足

御気の毒ですが、貴方は全く論理学の知識がありませんね!!
「一般にA->BとB->Aは同値じゃないでしょう」とは頭大丈夫ですか。そんなの書いていませんよ。

　立脚点が違うのではなく、知識レベルが違い過ぎるようです。

　他人におこがましくも教えようというからには、いい加減な理屈だけ並べて逃げてはだめです。この辺も論争の相手だった方によく似ています。

知りもしない数学の項目だけ羅列して、・・・他の問題に転嫁しよと・・・これも良く似ているのが不思議です。
　同一人物でしょうか。KSさんですか。

　ご参考に下記式のトートロジー性の証明を書いてあげます。対偶の式くらいはご自分でどうぞ。

　 (A⇒￢B)∧(A⇒B)⇒￢A≡T
≡(￢A∨￢B)∧(￢A∨B) ≡(￢A∨￢B)∧(￢A) ∨(￢A∨￢B)∧(B)
≡￢A￢A∨￢A￢B∨￢A B∨￢BB≡￢A∨￢A￢B∨￢A B∨0
≡￢A∨￢A(￢B∨ B) ≡￢A∨￢A・1≡￢A
∴ (A⇒￢B)∧(A⇒B)⇒￢A≡(￢A⇒￢A)≡T
　こんなの簡単でしう。

回答No.4

kabaokaba

んーーー・・・・論理の公理系とか分かってるのかな・・・

私は別にあなたの主張を全否定してるわけじゃない．
・「背理法」と「対偶の証明」が論理的には同値
というのは同意してるんだ．
ただ，「論理式」としては形が違うし
実際に使うときも使い方が違うことが多いから
違うってみなすことの方が自然じゃないのかといってるんだ．

あなたはたぶん「背理法の論理式」と「対偶の論理式」は
完全に同一の式だと主張してるんじゃないのかな．
これに対しては「違う」と私は主張してる．

>1)(￢ψ → ￢φ)→(φ → ψ)は(￢ψ → ￢φ)←(φ → ψ)でもあり

ちがーう．なんで勝手に矢印の方向変えるの？
そんなこと，安易にやっちゃだめ！
どこにそんなことしていいって根拠があるの？
いや，この場合は根拠あるんだけども，
その根拠わかってやってます？
＃こういう微妙なことを話してるときに
＃安易に→の向きを変えるってのは・・・分かってるのか
＃不安になってしまう・・・・

＞その矛盾とはどの事なのかが分かりません。
よくみてよ
((ψ → ￢φ)∧(ψ → φ))→￢ψ
ψを仮定して，φと￢φがでてきてて，
それが「かつ（∧）」でつながってるでしょう．
だから「矛盾」．

これの導出って・・・
真理値表かいてみればいいんじゃない？．
(ψ → ￢φ)∧(ψ → φ)と￢ψの真偽は完全に一致する．

書籍としては命題論理の本をいろいろみてみれば
でてるんじゃないのかな．

お礼

＞んーーー・・・・論理の公理系とか分かってるのかな・・・

　この辺は論理式で話をするからには良く知っております。

＞私は別にあなたの主張を全否定してるわけじゃない．
・「背理法」と「対偶の証明」が論理的には同値
というのは同意してるんだ．
ただ，「論理式」としては形が違うし
実際に使うときも使い方が違うことが多いから
違うってみなすことの方が自然じゃないのかといってるんだ．

＞あなたはたぶん「背理法の論理式」と「対偶の論理式」は
完全に同一の式だと主張してるんじゃないのかな．
これに対しては「違う」と私は主張してる．

　数学の証明などで、背理法で証明で・・・というときには、ほとんどが
A⇒Bの命題では￢B、つまりBの否定を仮定して演繹し何らかの矛盾を導き、結果的に
￢B⇒￢A[≡￢(A∧K1∧K2∧・・・∧Kn)]≡[￢A∨￢K1∨￢K2∨・・・∨￢Kn]
に達し、この対偶としてA≡(A∧K1∧K2∧・・・∧Kn)⇒Bを証明します。
　この導かれた矛盾が、直接的に￢Aの場合が￢B⇒￢Aと通常対偶と呼ばれている形です。しかしこれは潜在的には、Kiのすべで前提されています。

　なんだか質問者の方が教えているようで、申しわけありませんが・・・。

　続く・・・・

補足

つつき・・・

もともとこの件は、憲法の論議で論争になり、背理法とは?とまで遡ってしまい、相手は貴方と同じ下記の式を背理法の根拠と主張して、物別れになっていたので、このスレッドに質問しました。従って当初の質問で『背理法が対偶と違う』という方の論拠を聞いています。そして同様の主張に会いました。

＞＞1)(￢ψ → ￢φ)→(φ → ψ)は(￢ψ → ￢φ)←(φ → ψ)でもあり

＞ちがーう．なんで勝手に矢印の方向変えるの？
そんなこと，安易にやっちゃだめ！
どこにそんなことしていいって根拠があるの？
いや，この場合は根拠あるんだけども，
その根拠わかってやってます？
＃こういう微妙なことを話してるときに
＃安易に→の向きを変えるってのは・・・分かってるのか
＃不安になってしまう・・・・

この式(￢ψ → ￢φ)→(φ → ψ)は(￢ψ → ￢φ)←(φ → ψ)と同値なので、勝手に変えたのではなくて、事実としてトートロジーで、従って両方向が成立するので、(￢ψ → ￢φ)≡(φ → ψ)同値なのです。

＞＞その矛盾とはどの事なのかが分かりません。
＞よくみてよ
((ψ → ￢φ)∧(ψ → φ))→￢ψ
ψを仮定して，φと￢φがでてきてて，
それが「かつ（∧）」でつながってるでしょう．
だから「矛盾」．

＞これの導出って・・・
真理値表かいてみればいいんじゃない？．
(ψ → ￢φ)∧(ψ → φ)と￢ψの真偽は完全に一致する．

　ここの理屈も全く論争相手と同じです。しかもこれ以上の展開を示さなかったのも同じです。
この式((ψ → ￢φ)∧(ψ → φ))→￢ψもトートロシーです。
((ψ → ￢φ)∧(ψ → φ))は展開すると￢ψです。従って￢ψ⇒￢ψを示すだけなので当然トートロジーです。ご存知でしたか。

「ψを仮定して，φと￢φがでてきてて・・・だから「矛盾」」と言う理屈まで全く同一です。この前半の式(ψ → ￢φ)∧(ψ → φ)は何ですか。
(ψ → φ)の証明に使うためですね。∧の両辺は対称ですね。丁寧に説明すると(ψ → ￢φ)∧(ψ → φ)≡(ψ→ φ)∧(ψ → ￢φ)ですから、当初の→の左辺を証明するのが目的とすれば、≡の右の式からはψ → ￢φが証明されますよ。正確には￢φ＝δとでも変数変換して、結果を戻してみれば正確に出てきます。
　または(ψ → ￢φ)∧(ψ → φ)を仮定したという事に戻れば、すでに
(ψ → φ)を仮定しているので、ψ → φを証明するのは同語反復です。

＞書籍としては命題論理の本をいろいろみてみれば
でてるんじゃないのかな．

　この奇妙な理屈がこ広くまかり通っているのは、どこかに原因があるのだろうと思い文献の求めています。
　最近亡くなった論理学者の石谷茂氏が、複数の高校参考書の間違いを指摘していますが、どこかその辺りに間違いのもと資料があるのでしょうか。
　社会的には重大事です。誤りの伝染と言う意味ですが・・・。

　トートロジーは論理的には真理かどうかは、かなり重大な問題です。
　トートロジーをディジタル論理回路で表現すると面白い結果が出ますが、次回にします。

回答No.3

kabaokaba

>これは間違いと思います。
自分で主張してるんだから
先に間違いだというのを示すべきでは？
論拠もなにも，ある命題から，矛盾が示されたから
その命題の否定が示されるというだけの定式化でしょう．
あなたのいう「背理法」とは何でしょう？
まさか「対偶」と同じ論理式ではないしょう？

背理法の論理式の記述はどうなんかなあ
そこまで噛み付かれると不安になるなあ(^^;
もっときっちり書けるのかな
けどテクニカルな部分で違ってても
この場合影響ないと思う
要は，命題論理で
「「対偶証明」を示す論理式」
「「背理法」を示す論理式」
が存在し，それらのどちらを公理系にいれても
同じ体系ができるでしょうといってるわけだから．

なんか，根本的な立脚点というか考え方が違う気がしてきたなあ
私は
背理法と対偶は論理的には同じというか
どっちを命題論理の公理系に突っ込んでも
同じ体系ができるんじゃないのっていってます．

けど，数学の実運用として
使い方が違う（これを認めますか？
これを主張するためにあえて例として，有名な
選択公理とかFermatを出したんだけども，
あっさりスルーされたしぃ）ものだし，だから
普通は「違う」と捉えられるんじゃないの？
といってるんですよ．
それが「捉え方の違い」といったところ．

論理的に同値なものが，どんな文脈でも
「同じ」と捉えられるわけでは
ないと私は主張してるわけです．
「同じ」「違う」ということは結構文脈依存です．
そして，いわゆる「定説」もそういう立場じゃないのかと
いってるわけです．

お礼

>これは間違いと思います。
自分で主張してるんだから
先に間違いだというのを示すべきでは？
論拠もなにも，ある命題から，矛盾が示されたから
その命題の否定が示されるというだけの定式化でしょう．
あなたのいう「背理法」とは何でしょう？
まさか「対偶」と同じ論理式ではないしょう？

「間違いだというのを示すべきでは？」との事ですが、この式から目的の式のA⇒Bを証明する過程が理解できないので、間違い?　と言っているだけです。「ある命題から，矛盾が示されたから、その命題の否定が示されるというだけの定式化でしょう．」という意味や、その矛盾とはどの事なのかが分かりません。

　[背理法」の私の意味とは、前に詳細に書いたとおりの対偶式そのもので、これ以外の矛盾はあり得ないと考えています。

補足

どなたか、もっとレベルの高い方のご回答をお待ちします。

　特に(A⇒￢B)∧(A⇒B)⇒￢A式が、背理法の根拠式だという説の方の理論をお聞かせ下さい。

回答No.2

kabaokaba

んーー・・・そういう論理式できますかい
おもいっきりシンプルにしてみるとこんな感じかな

命題論理の公理系だったら，
ヒルベルト式でいけば
(￢ψ → ￢φ)→(φ → ψ)
が公理の一個で，これはまさに「対偶」ですな
このとき，背理法
((ψ → ￢φ)∧(ψ → φ))→￢ψ
は定理です．
逆に背理法の方を公理にすれば，対偶は定理でしょう．
けど背理法の方にはいきなり「縁もゆかりもないφ」がでてくる．
これはもう違うものと考えるものでは？

お互いに他方を証明できるという意味で
論理としては確かに同値なのかもしれません．
けど・・・それをいうと極端な話
「選択公理」と
「（無限次元を含めた）ベクトル空間の基底の存在」と
「Zornの補題」と・・・ほかにもいろいろある，は同じ．
いや，確かに「同じ」なんだけど，「違う」でしょう？

「同じ」「違う」ということの捉え方でしょうか．
これは「感覚的」には「違う」ものでしょうし
実際に運用する際でも「違う」形になるんじゃないですか？

語弊を招くかもしれないけど，たとえば
フェルマーの最終定理の証明は
「対偶」ではないと思うんだ．
あれは背理法でしょう．
「保型形式」とか「フライ曲線」なんて
「遠いもの」につなげるんだから．

お礼

これは私の返信の後のものでしょうか。

省略

>命題論理の公理系だったら，
ヒルベルト式でいけば
(￢ψ → ￢φ)→(φ → ψ)
が公理の一個で，これはまさに「対偶」ですな
このとき，背理法
((ψ → ￢φ)∧(ψ → φ))→￢ψ
は定理です．

　この式「(ψ → ￢φ)∧(ψ → φ))→￢ψ」が背理法の根拠だという説は前にも見たことがありますが、これは間違いと思います。念のために貴方の論拠を説明してください。

省略

お互いに他方を証明できるという意味で
論理としては確かに同値なのかもしれません．
けど・・・それをいうと極端な話

以下の話はこの狭い空間で論ずるのには不適当ですし、難解すぎるのでもっと簡単に考えましょう。
　従って省略します。

>「同じ」「違う」ということの捉え方でしょうか．
これは「感覚的」には「違う」ものでしょうし
実際に運用する際でも「違う」形になるんじゃないですか？

背理法の私見では、A⇒Bを証明する場合には、表面に出ていないKiを含んで、そのANDとして(A∧K1∧K2∧・・・∧Kn)⇒Bを証明することなので、命題の否定から生じる矛盾とは、Aだけでなく、Kiのいずれかに対するものも含んでいるので、￢B⇒(￢A∨￢K1∨￢K2∨・・・∨￢Kn)≡￢B⇒￢(A∧K1∧K2∧・・・∧Kn)と表現でき、これは対偶と同一形態だと言いたいのです。
　その中の￢B⇒￢Aの場合だけを取り出して、対偶と言うのは感覚的にも違うと言うのです。見えないものを見ていないだけです。

>語弊を招くかもしれないけど，たとえば
フェルマーの最終定理の証明は
「対偶」ではないと思うんだ．
あれは背理法でしょう．
「保型形式」とか「フライ曲線」なんて
「遠いもの」につなげるんだから．

これらは話題が拡散し過ぎるので、前記と同様に省略しましょう。
背理法の定理なるものについての説明をお願いましす。

　どうやらこれが違いの根底にありそうです。この説が記載されている著書がありましたら、ご紹介ください。私は残念ながら見たことがありません。

補足

>>命題論理の公理系だったら，
ヒルベルト式でいけば
(￢ψ → ￢φ)→(φ → ψ)
が公理の一個で，これはまさに「対偶」ですな
このとき，背理法
((ψ → ￢φ)∧(ψ → φ))→￢ψ
は定理です．

>・・・これは間違いだと思います。・・・

・・・と言う事に、何やら私が噛みついてるすように、受け取られているようですがそれは誤解です。
　フエルマーの定理とかその他の例は、この狭い中で論じるほど簡単でもないし、要約して論じるほどの知識もないしで、スルーさせていただきました。

(1)(￢ψ → ￢φ)→(φ → ψ)は(￢ψ → ￢φ)←(φ → ψ)でもあり従って
(￢ψ → ￢φ)≡(φ → ψ)は同値なので、≡の両辺は片方から他方が証明できます。

(2)(ψ → ￢φ)∧(ψ → φ)→￢ψの方は(ψ → φ)を証明する方法としての
背理法と言うのであれば、その理屈が理解できないので教えて頂きたいと、その根拠を示して下さいと書きました。

　前にもこの説の方に出会ったことがありますが、ついに理屈の説明をしてもらえず、その記載著書の紹介もなかったので、どこに詳細な説明があるのか分かりませんでした。是非その参考文献をご紹介ください。また貴殿がご理解されているのなら、それを教えて下さい。