論理式は真理表を使わないと証明できないでしょうか？（「P→『Q∨R』」⇔「『P∧￢Q』→R」）

質問

お世話になります。よろしくお願いします。

今まで私は
論理式といえば
(1)「P→Q」⇔「￢Q→￢P」（対偶）
(2)「P→Q」⇔「￢P∨Q」
の2つしか知りませんでした。

そして最近数学の証明問題で大変便利な
(3)「P→『Q∨R』」⇔「『P∧￢Q』→R」
というものを知りました。

確か先の(1)、(2)は真理表を使って証明した記憶があるのですが、
(3)は文字が３つなので、真理表での証明はとても大変だと思います。
(3)は結構当たり前の事実のような気がするのですが、もっと簡単に証明する方法はないでしょうか？
よろしくお願いします。

また(1)、(2)、(3)以外に数学を証明するのに役に立つ論理式をご存知でしたら是非教えてください。
こちらも合わせてよろしくお願いします。

回答No.1

Tacosan · ベストアンサー

・真理表で証明する: 所詮 8通り×いくつか, だからこのくらいなら力技でもいける.
・式の変形だけで示す: 「ドモルガンの法則」が必要.
・推論規則を使う: たぶんこれが本筋. きれいに示そうとすると先を読む必要があって面倒だけど.
いずれにしても「ドモルガンの法則」は「論理をかじった人なら知っていないと恥ずかしい」レベルだと思ってください.

お礼

ご回答どうもありがとうございます。

そうですね、ド・モルガンの法則がありました。
大事なのを忘れておりました。ありがとうございます。

>推論規則を使う: たぶんこれが本筋. きれいに示そうとすると先を読む必要があって面倒だけど
いろいろ調べてみたのですけど、これがちょっと分からないです・・・。

「P→『Q∨R』」⇔「￢P∨（Q∨R）」⇔「（￢P∨Q）∨R」
⇔「￢（￢P∨Q）→R」⇔「『P∧￢Q』→R」
というのは多分２番目に呈示されている「・式の変形だけで示す」
方法だと思うのですが。確かに直観的とは言いづらい気がします。
「・推論規則を使う」が本筋と言われて気になっています（笑）
この方法を勉強したいのですが、ヒントだけでもいいので何か教えていただけないでしょうか？
よろしくお願いします。

回答No.2

uyama33

P→『Q∨R』 が成立するとき,
(P∧￢Q) → ((Q∨R)∧￢Q)　→　(Q∧￢Q)∨(R∧￢Q) → (R∧￢Q) → R

『P∧￢Q』→R が成立するとき、
P　→　P∧(Q∨￢Q) → (P∧Q)∨(P∧￢Q) → (P∧Q)∨R → Q∨R

お礼

別解どうもありがとうございます。
とても勉強になります。
何となく集合で似たような証明をしたような気がします。
「P→『Q∨R』」⇔「『P∧￢Q』→R」において
Pと「P∧￢Q」をどのように結びつけるかがどうしても分からなかったのですが、「∧(Q∨￢Q)」を付け加えてしまう方法がありました・・・。
ご回答の２式をまとめると

「P→(Q∨R)」⇔「『(P∧Q）∨（P∧￢Q）』→(Q∨R)」
⇔「(P∧￢Q)→（Q∨R）」⇔「（P∧￢Q）→R」

みたいな感じでしょうか。
どうもありがとうございました。