• ベストアンサー
※ ChatGPTを利用し、要約された質問です(原文:背理法の定理を排中律から証明できません。)

背理法の定理を排中律から証明できない理由とは?

このQ&Aのポイント
  • 背理法の定理を排中律から証明することはできません。背理法の証明法では、矛盾が必要ですが、排中律では矛盾が生じないためです。
  • 背理法の正しさを証明するためには、P→Qを示す際に((P→¬Q)∧¬(P→¬Q))=trueを示す必要がありますが、これは恒偽命題であるため、P→Qと一致しません。
  • 背理法を使用する際には別の証明法を用いる必要があります。背理法は矛盾が必要なため、排中律では使用できません。

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

あ~, 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) という論理で証明しているみたいです. うお, 以外と複雑.

Arice123
質問者

お礼

有難うございます。 大変参考になっております。 ¬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)が真である事を言えばいいのですね。

その他の回答 (1)

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

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

Arice123
質問者

お礼

ご回答有難うございます。 > なんか, 示したいものが違うような気がします. > (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 となり真偽が一致しません。 何か勘違いしてますでしょうか?   

関連するQ&A