質問＜１０７１＞２００３／１／１５
from=あめちゃん
「背理法について」

「pならばq」を背理法で証明するとき、問題集では
「pならば(qの否定)」が矛盾することを示す手順で
書いていますが、
「(pの否定)ならばq」が矛盾することを示しても
証明としてはOKですか。
それとも「pならばq」であるとき、必ずしも「qならばp」
とは言えないのと同じように、必ずしも証明したことには
ならないのでしょうか。

お便り２００３／１／２２
from=phaos

背理法は (「p ならば q」 を示したいときは)
「p と (q の否定) を同時に仮定すると矛盾する」
を示しているのであって
「p ならば (q の否定)」
を示してはいないはずです。
「(p の否定) と q を同時に仮定すると矛盾する」
事が示されたとすると, 証明できるのは
(1) q ならば p,
(2) (p の否定) ならば (q の否定)
です。

最初のことをもう一度詳しく言っておきましょう。
「p ならば q」 が直接法で示せないときに間接法の一つである背理法
を用いて示すときは

先ず q を否定して, 色々変形していって,
p と矛盾した結果を出します。

これは p と q の否定は同時には成り立たないことを示しているわけです。
だから 「p 且つ (q の否定)」 が矛盾するのであって,
「p ならば (q の否定)」 が矛盾しているのではないのです

(実際にはこちらも矛盾しているかもしれませんが)。

(因みに古典論理では 「p ならば (q の否定)」 と 「(p の否定) 又は
 (q の否定)」 が同値ですから,
これは 「p 且つ (q の否定)」 と同値ではありませんので, 多分矛盾
しないでしょう。)

論理学をちゃんと学びたいのなら
「記号論理学」 「数理論理学」
といった本を探して読んでみられることをお勧めします。