背理法の定理を排中律から証明できません。

質問

よろしくお願い致します。

先ず、
Pを命題とし、「→」は含意を表す。
Pが真→￢Pは偽
Pが偽→￢Pは真
Pが否定の否定が真ならばPは真
Pが否定の否定が偽ならばPは偽
Ｐが真であるか，またはＰの否定が真であるかのいずれかである．

が成立しているとします。

これらから背理法が正しい事を証明したくと思ってます。

先ず、「矛盾」の定義はP∧￢Pが真となる事です。
ですから
P→Qが
と
(P→￢Q)∧￢(P→￢Q)
の真偽が等しくならなければ背理法が正しい証明法とはいえません。
つまり、
P→Qを示したい((P→Q)=true)時、代わりに
((P→￢Q)∧￢(P→￢Q))=true
を示す事である。
しかし、
((P→￢Q)∧￢(P→￢Q))は
(￢P)∨(￢Q)∧￢(￢P∨￢Q)と書け、更に
￢(P∧Q)∧(P∧Q)
でこれは自動的に恒偽命題となってしまい、
P→Qと真偽が一致しません。
とい事はP→Qを示すのに背理法
((P→￢Q)∧￢(P→￢Q))=trueが使えなくなってしまいます。

一体、何処を勘違いしていますでしょうか?

回答No.2

Tacosan · ベストアンサー

あ～, P→Q を背理法で証明するってことね.
これをどう証明するかというと
「P ∧ ￢Q を仮定すると矛盾が生じるので P→Q」のはずなので, これを式に書くと
((P∧￢Q)→(R∧￢R))→(P→Q)
か?
例えば, 「√2 が有理数でない」ことを背理法で証明する (中学校レベルの) 方法だと,
「x^2 = 2 ならば x は有理数でない」なので, P = 「x^2 = 2」, Q = 「x は有理数でない」とおけます.
で, x = m/n (m, n は整数で互いに素) とおくときの「互いに素」が R となって, これらを使うと
((P∧￢Q∧R)→￢R)→(P→Q)
あれ? 上と式が違う (苦笑). 証明中では (P∧￢Q∧R)→R を使う (最後に「互いに素と仮定したのに」といっているので) ので,
((P∧￢Q∧R)→(R∧￢R))→(P→Q)
なのかなぁ? もしくは (「互いに素」までを含めて有理数とすれば)
((P∧￢Q)→Q)→(P→Q) あるいは ((P∧￢Q)→(Q∧￢Q))→(P→Q)
という論理で証明しているみたいです. うお, 以外と複雑.

お礼

有難うございます。
大変参考になっております。

￢P⇒(P∧￢P) = ￢(￢P)∨(P∧￢P)
= P∨(P∧￢P)
　　　　　　　=(P∨P)∧(P∨￢P)
=P∧(P∨￢P)
=P∧(true)
=P
∴ 真理関数Pにおいて、P と ￢P⇒(P∧￢P) の真偽は一致する
したがって、
Pが真であることを示すためには￢P⇒(P∧￢P)が真である事を言えばいいのですね。

回答No.1

Tacosan

なんか, 示したいものが違うような気がします.
(P→(Q∧￢Q))→￢P
くらいかなぁ? ちなみにこれは恒真ですが... 証明できるかなぁ?

お礼

ご回答有難うございます。

> なんか, 示したいものが違うような気がします.
> (P→(Q∧￢Q))→￢P
> くらいかなぁ? ちなみにこれは恒真ですが... 証明できるかなぁ?

つまり、(P→(Q∧￢Q))→￢Pが背理法であり、
P→Q
と
(P→(Q∧￢Q))→￢P
の真偽が一致するというわけですね。

(P→(Q∧￢Q))→￢Pは
[￢((￢P)∨(Q∧￢Q))]∨(￢P)
と書け、
[(P∧￢(Q∧￢Q))]∨(￢P)
は
[(P∧(￢Q∨Q))]∨(￢P)
は
[(P∧(真))]∨(￢P)
となるので
P　Q　P→Q　[(P∧(真))]∨(￢P)
T　T　　T　　　　　　　T
T　F F　　　　　　　T
F T　　T　　　　　　　T
F F T T

となり真偽が一致しません。
何か勘違いしてますでしょうか?