背理法と対偶法について

質問

少し長くなるのですがお願いします。

私の使用している参考書に

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

と書かれていて
この部分の意味がわからなかったので出版社に問い合わせました。
すると、このような回答を頂きました。

--------------------------------------------------------------------
背理法は、
「ｐという前提条件下で、結論のｑを否定して、￢ｑと仮定すると、矛盾が生じる。よって、ｐ⇒ｑ」とする論法ですね。対偶法において、この矛盾に相当するものが、
「￢ｐかつｐ」という矛盾です。なぜなら、￢ｑ⇒￢ｐを示すのが対偶法だからです。
つまり、対偶：￢ｑ⇒￢ｐが示されれば、この時点で「￢ｐかつｐ」という矛盾が生まれ、背理法が成立したことになります。

--------------------------------------------------------------------

私は以前、この事に関する質問をここでして回答をいただいたのですが
その時に頂いた回答をもとに考えたのがこの考え方です。

----------------------------------------------------------------------

「pならばq」を証明しようとしていて
「pならばq」に背理法を使って「pであって￢q」と仮定する。

その過程で「対偶　￢qならば￢p」が証明できたとする。

「pであって￢q」と仮定しているのに対偶　￢qならば￢p　なので　pではないため矛盾する。　

よって「pならばq」は真である。

命題の対偶が証明された場合、普通は自動的に命題が真であると考えますが
この説明文では
「命題の対偶が証明されたあと、背理法を使って命題が真であることを証明することになるので
対偶による証明法も一種の背理法と考えることが出来る」
ということが書かれている。

--------------------------------------------------------------------------

出版社から頂いた回答と、この自分の考えが　合っているのか自信がもてません。
出版社にはこの事以外にも色々質問していて、何度もメールしづらいのでここで質問させてもらいました。
よろしくお願いします。

回答No.10

Caper

● pseudonym2013 さん がお持ちの参考書より。

　 対偶による証明法も一種の背理法と考えることができる。
　 命題 p → q が真であることをいうために ￢q ( qでない ) と仮定して ￢p が導かれたとする。★ p ではないからこれは矛盾で背理法が成立したことになる。

● この文章が伝えようとする内容を具体的に理解しないと、pseudonym2013 さん が抱える悩みは解消されないかもしれません。
　 ★ 印 の後ろに位置する一文が理解しづらいはずです。「 ★ 印 の後ろに位置する 命題 p はいったいどこからわいてきたのか 」という問いかけに答えを見いだすことができれば、悩みの解消につながるかもしれません。

● その 命題 p の出どころについて

　 ★ 印 の直前において、対偶が真であることが証明済みとなりました。すなわち、★ 印 の直前において、次の 命題 1) が真であることが証明済みとなりました。

1) ￢q → ￢p
　 ￢q ならば ￢p

　 この 命題 1) が真であることが証明されると、次の 命題 2) が自動的に真となります。

2) p → (￢q → ￢p)
　 p ならば「 ￢q ならば ￢p 」

　 また、次の 命題 3) は、命題 p の真偽に関係なく、真となります。

3) p → p
　 p ならば p

　 ですから、命題 1) が真であれば、次の 命題 4) は自動的に真になります。

4) p → ((￢q → ￢p) ∧ p)
　 p ならば「『 ￢q ならば ￢p 』であって p 」

● 命題 1) が 真であれば 命題 4) が自動的に真となることを踏まえて、回答 No. 3 "出版社の説明" および 回答 No. 6, 7, 8 をお読みください。
　 理解しづらい個所がございましたら、補足機能を利用するなどして、遠慮なくご指摘ください。

回答No.9

Caper

● とり急ぎ、ご連絡まで。

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

　 記事の後半に 2 つ の例が。2 例目 が対偶が真であるという結果を用いた背理法。
　 1 例目 は MagicianKuma さん 回答 No. 4 の最後の記述。

回答No.8

Caper

● ごめんなさい。さらに訂正です。回答 No. 3 < * 1 > の訂正に伴い、回答 No. 3 "出版社の説明" に訂正個所が発生しました。

● [ 誤 ]
　 そこで、p ならば q という命題が真であることの証明を通常どおり行なう途中で "背理法を用いる"。まず、命題 p が真であるとする。

● [ 正 ]
　 そこで、p ならば q という命題が真であることの証明を通常どおり行なう途中で "矛盾を導く"。まず、命題 p が真であるとする。

回答No.7

Caper

● ごめんなさい。回答 No. 3 < * 1 > の訂正です。
　 回答 No. 3 < * 1 > については、回答 No. 4 における MagicianKuma さん のご指摘どおりであると、私は考えます。MagicianKuma さん、pseudonym2013 さん、閲覧者のみなさん、たいへん失礼いたしました。

● [ 誤 ]
< * 1 >
　 pseudonym2013 さん の考えかたでは、"背理法による証明の対象" が p ならば q という命題全体であったのに対し、出版社の説明では、その対象が 命題 q のみ。

● [ 正 ]
< * 1 >
　 pseudonym2013 さん の考えかたでは、"矛盾が導かれたことによって影響を受ける対象" が p ならば q という命題全体であったのに対し、出版社の説明では、その対象が 命題 q のみ。

回答No.6

Caper

● 私の 回答 No. 3 における "出版社の説明" の解釈はまちがっているというご指摘を、回答 No. 4 において、MagicianKuma さん からいただいたようです。

　 現時点において、その解釈はまちがっていないと、私は思っています。

● ∧ は「 であって 」「 かつ 」を表わし、
　 ￢ は「 否定 」を表わし、
　 → は「 ならば 」を表わし、
　 ≡ は「 同値 」を表わす記号であるとします。

　 ( 左辺の命題 ) ≡ ( 右辺の命題 ) とは、
　 すなわち「( 左辺の命題 ) と ( 右辺の命題 ) が同値である 」とは、
　 (( 左辺の命題 ) → ( 右辺の命題 )) ∧ (( 右辺の命題 ) → ( 左辺の命題 )) という命題が
　 トートロジー (= 恒真命題 ) であることを表わすものとします。

　 a, b, c, p, q は任意の命題を表わす記号であるとします。

● まず、次の 1) が正しいことを確認します。

1) (a ∧ b) → c ≡ a → (b → c)

　 p → q という命題が真であることを証明するために、次の 2) という命題が真であることを証明します。( ここでの矛盾とは、p ∧ ￢p という命題のことです )

2) (p ∧ ￢q) → ( 矛盾 )

　 ここまでは、問題がないと思われます。
　 そこで 上記の 1) を利用します。この 命題 2) は次の 命題 3) と同値になります。

3) p → (￢q → ( 矛盾 ))

　 すなわち、命題 2) 3) はいずれも p → q という命題と同値になるわけです。
　 ですから、この 命題 3) に沿った証明も有効であろうと、私は考えます。

　 回答 No. 3 における "pseudonym2013 さん の考えかた" は、命題 2) に沿った証明であり、回答 No. 3 における "出版社の説明" は、命題 3) に沿った証明です。

● 出版社からの回答の冒頭から。

　 背理法は、「 p という "前提" 条件下で、結論の q を否定して、￢q と "仮定" すると、矛盾が生じる。…

　 "前提" と "仮定" が使い分けられています。この使い分けは、「 命題論理の自然演繹体系 」で行なわれているようです。出版社からの回答はこの「 … 体系 」に従ったものではないかと、私は推測しました。この「 … 体系 」なるものを、私はほとんど理解していません。
　 この「 … 体系 」によれば、"仮定" は "前提" の一種であるらしいです。そして、"仮定" はのちに消えるらしいです。

　 回答 No. 3 における "出版社の説明" では、もちろん、"前提" が p で、"仮定" が ￢q です。矛盾が導かれた時点で、"仮定" の ￢q は消えています。
　 回答 No. 3 における "pseudonym2013 さん の考えかた" では、"前提" は最初から存在しません。"仮定" は p ∧ ￢q です。矛盾が導かれた時点で、"仮定" の p ∧ ￢q は消えています。

● 以上の私の回答もまちがっていました場合は、ひらにひらにごめんなさい。

回答No.5

中村 拓男（@tknakamuri）

私の理解はこうです。

証明したい命題を p とすると

背理法 p = false から q = true と q = false を導く
待遇証明 p = false から から恒偽命題を導く

回答No.4

MagicianKuma

まず背理法を整理してみましょう。

目的：ある命題Ｘが真であることを証明したい。
背理法：Ｘが偽と仮定してみる。すると、矛盾が生じる。なのでＸは真。
矛盾というのは、ある命題Ｙと￢Ｙの両方が成り立つことです。ここでＹは証明済みの命題でもよいし、証明されてない命題でもよい。
（矛盾というのはある命題が偽のことではありません。ある命題が真であることと、偽であることが両方とも導き出されることです。）

では、ｐ⇒ｑを証明したいとする。重要な点は、ｐを証明したいわけでもなく、ｑを証明したいわけでもなく。ｐ⇒ｑを証明したいわけです。
背理法に従って、ｐ⇒ｑが偽と仮定します。すなわち、￢(ｐ⇒ｑ)が真と仮定します。￢(ｐ⇒ｑ)＝￢(￢ｐ∨ｑ)＝ｐ∧￢ｑ　ですから、
ｐかつ￢ｑが成り立つと仮定するわけですね。これから矛盾が導き出せれば仮定が間違いで、証明できたということになります。

ところで、￢ｑが真として、￢ｐが導き出されたとすると、まさしく、上記ｐ∧￢ｐの仮定と矛盾するわけです。この意味で背理法になっています。
上記の流れは、￢ｑ⇒￢ｐを導いたわけですから、この形はｐ⇒ｑの対偶を証明したという形になっているということです。

ですから、出版社の表現はわかりにくいです。
「命題ｐ⇒ｑが真であることをいうために￢ｑと仮定して￢ｐが導かれたとする。ｐではないからこれは矛盾で背理法が成立したことになる。」
背理法で仮定すべきは、￢ｑではなく、あくまでｐ⇒ｑの否定を仮定します。これがｐ∧￢ｑとなります。

まとめると、
対偶法：対偶の真理表は元命題と一致することがわかっているから、ｐ⇒ｑの対偶をとって、￢ｑ⇒￢ｐを導けばよい。という考え方。
背理法：ｐ⇒ｑの否定（すなわちｐ∧￢ｑ）を仮定して￢ｐが導き出された。よって矛盾。仮定が間違い。という考え方。
　　　　上記背理法では、￢ｐではなく、全然別のＹと￢Ｙが導き出されてもよいところが対偶法との違い。
　　　　たとえば、ｐからＹが￢ｑから￢Ｙが導き出されても矛盾。

回答No.3

Caper

● ごめんなさい。回答 No.2 における 7) 8) は混乱を招く無駄な遠回りだったようです。どうかお許しください。回答を以下のとおり記述しなおしてみました。

● pseudonym2013 さん の考えかた

1)　￢q ならば ￢p

　 上記の 命題 1) が真であるという結果をすでに得ている。

　 そこで、p ならば q という命題が真であることを証明するために、その 否定命題 ￢(p ならば q) が真であるとして矛盾を導く < * 1 > 。すなわち、p であって ￢q という命題が真であるとして矛盾を導く。

2) (p であって ￢q) ならば ￢q

　 上記の 命題 2) は トートロジー (= 恒真命題 ) である。よって、命題 2) は真である。
　 命題 1) 2) が真であることから、三段論法 < * 2 > により、次の 命題 3) が真となる。

3) (p であって ￢q) ならば ￢p

　 一方、次の 命題 4) はトートロジーである。よって 命題 4) は真である。

4) (p であって ￢q) ならば p

　 上記の 命題 3) 4) が真であることから、p であって ￢q という命題が真であれば、矛盾が導かれる ( この場合の矛盾とは、p であって ￢p という命題 < * 3 > )。
　 以上の結果から、p ならば q という命題が真であることが証明された。

● 出版社の説明

1)　￢q ならば ￢p

　 上記の 命題 1) が真であるという結果をすでに得ている。

　 そこで、p ならば q という命題が真であることの証明を通常どおり行なう途中で背理法を用いる。まず、命題 p が真であるとする。

　 このとき、命題 q が真であることを証明するために、その 否定命題 ￢q が真であるとして矛盾を導く < * 1 > 。

　 命題 p が真であるから、次の 命題 5) は必ず真となる < * 4 > 。

5) ￢q ならば p

　 上記の 命題 1) 5) が真であることから、命題 ￢q が真であれば、矛盾が導かれる ( この場合の矛盾とは、p であって ￢ p という命題 < * 3 > )。
　 以上の結果から、命題 p が真であるとき、命題 q が真であることが証明された。すなわち、p ならば q という命題が真であることが証明された。

●

< * 1 >
　 pseudonym2013 さん の考えかたでは、背理法による証明の対象が p ならば q という命題全体であったのに対し、出版社の説明では、その対象が 命題 q のみ。

< * 2 >
　 a, b, c は任意の命題を表わす記号であるとする。
　 ((a ならば b) であって (b ならば c)) ならば (a ならば c) という命題はトートロジー。よって、((a ならば b) であって (b ならば c)) ならば (a ならば c) という命題は真。

< * 3 >
　 a, b, c は任意の命題を表わす記号であるとする。
　 (a ならば b) であって (a ならば c) という命題は、
　 a ならば (b であって c) という命題と同値。
　 c を ￢b と置き換えて、3) 4) という命題の組と見比べる。同様に、1) 5) という命題の組と見比べる。

< * 4 >
　 a, b は任意の命題を表わす記号であるとする。
　 a ならば (b ならば a) という命題はトートロジー。よって、a ならば (b ならば a) という命題は真。

● 以上の回答にも落ち度がある場合は、ひらにごめんなさい。

回答No.2

Caper

● pseudonym2013 さん の考えかたと、出版社の説明との間には、少しだけ差異があると、私は考えます。

　 着目すべきは、出版社の説明に見られる用語の使い分けです。「 前提 」「 仮定 」
　 これらの用語の説明は、省略します。それを正確に行なう自信が私にはありません。

● pseudonym2013 さん の考えかたは、次の 1) であると、推測します。

1) (p であって ￢q) ならば 矛盾

　 出版社の説明は、次の 2) であると、私は推測します。

2) p ならば (￢q ならば 矛盾)

● 要点は次のとおりではないでしょうか。

3) 矛盾とは、平たく言えば、偽 である命題のこと。

4) a であって ￢a は矛盾であること。

5) (a であって b) ならば c という命題と
　 a ならば (b ならば c) という命題は同値であること。

6) a ならば 矛盾、すなわち a ならば 偽 という命題と
　 ￢a という命題は同値であること。

7) b ならば c という命題が真であると証明されれば、a の真偽を問わず、
　 a ならば (b ならば c) という命題が真であると必ず証明される。

8) a ならば (b ならば c) という命題と
　 a ならば (b ならば (a であって c)) という命題は同値であること。

9) 上記の 命題 1) が真であると証明された場合、
　 上記の 6) より ( a = p であって ￢q と置く )、
　 ￢(p であって ￢q) という命題が真であると証明される。
　 すなわち、p ならば q という命題が真であると証明される。

　 上記の 命題 2) が真であると証明された場合
　 上記の 6) より (a = ￢q と置く )、
　 p ならば q という命題が真であると証明される。

● 以上の回答がまちがっていました場合は、ひらにごめんなさい。

回答No.1

noname#221368

そうですね。

＞「pならばq」を証明しようとしていて
＞「pならばq」に背理法を使って「pであって￢q」と仮定する。

そして￢pという結論を出す。ところが「pであって￢q」だからpも成り立つ。従って矛盾。故にp⇒q。

　・・・という「記述の仕方」は、少し古臭いかも知れないですね。命題理論において、

　　(p⇒q)　⇔　(￢q⇒￢p)　　　(1)

は保証されているので、自分は、背理法と対偶は同じと考えて問題ないと思っています。

　ただ命題理論を地道にたどると、対偶の前に「証明の方法」として背理法が先に出てきて、対偶はその系（結果）となっているのが普通です。そこでの背理法とは、

　　(Ｐかつ￢Ｐ)　⇒　Ｑ　　　(2)

となります。ここでＱは任意の命題です。つまり矛盾した前提からは、何でも結論できるという、考えようによっては当たり前の結論です。この事を根拠にして(1)が導かれますが、その手順は、まさに背理法の古臭い「記述の仕方」そのものです。

　数学はけっこう律儀なところもありますから、今回は原典の古臭い「記述の仕方」が偶然に残っていただけだ、と考えてかまわない気がします。

　ちなみに(2)の対偶をとってみますか(^^)。

　　￢Ｑ　⇒　(Ｐまたは￢Ｐ)　　　(3)

ですが、(3)でＰも任意の命題にとれます。またＱも任意の命題だったので(3)は、

　　Ｑ　⇒　(Ｐまたは￢Ｐ)　　　　(4)

と書いても意味は同じです。そして普通、「Ｐまたは￢Ｐ」は絶対に真です。(4)の意味は、真な命題の真偽性は、前提に影響されないと読めます。これもまた、ある意味当然の結論です。

　このような観点から命題理論を見直すと、なぜ論理が有効に働くかを、感覚的に把握できるようになると思います。で、その見直しは、けっこう面白いですよ(^^)。