集合の包含関係に関する推移律の証明について

質問

3つの集合を
　　A = { x|P(x) },　 B = { x|Q(x) },　　C = { x|R(x) }
とします。直感的には明らかな、集合の包含関係に関する推移律

　　(A⊆B)∧(B⊆C) ⇒ A⊆C …… (#1)

を論理記号を使って、機械的に導くことができるのでしょうか？
　(#1) は

　　(x∈A ⇒ x∈B)∧(x∈B ⇒ x∈C) ⇒ (x∈A ⇒ x∈C)

と同じことなので、任意の a について

　　(　P(a)⇒Q(a)∧Q(a)⇒R(a)　)⇒( P(a)⇒R(a) ).

　したがって

　　(P⇒Q∧Q⇒R) ⇒ (P⇒R)
　⇔￢{ (P⇒Q∧Q⇒R) }∨(￢P∨R)
　⇔￢{ (￢P∨Q)∧(￢Q∨R) }∨(￢P∨R)
　⇔ {￢(￢P∨Q)∨￢(￢Q∨R) }∨(￢P∨R)
　⇔ { (P∧￢Q)∨(Q∧￢R) }∨(￢P∨R)

が真であることを証明すればよさそうです。で、分配律を使って変形しているのですが、分配変形すればするほどゴチャゴチャして（笑）うまくいきません。
　ここから先、どうしたらいいのでしょうか。

回答No.1

f272 · ベストアンサー

(P⇒Q∧Q⇒R) ⇒ (P⇒R)
を証明したいのなら真偽表を作って8通りの場合のどれでも真になることをいうのが速いと思うが...

　⇔ { (P∧￢Q)∨(Q∧￢R) }∨(￢P∨R)
　⇔ (P∧￢Q) ∨ (Q∧￢R) ∨ (￢P) ∨ (R) 4つの論理和と見る
　⇔ (P∧￢Q) ∨ (￢P) ∨ (Q∧￢R) ∨ (R) 順番を入れ替えてもよい
　⇔ ((P∨￢P)∧(￢Q∨￢P)) ∨ ((Q∨R)∧(￢R∨R)) 中に入れてみた
　⇔ (￢Q∨￢P) ∨ (Q∨R) 恒真は省略可能
　⇔ ￢Q ∨ ￢P ∨ Q ∨ R 4つの論理和と見ると￢QとQがあるので明らかに恒真

お礼

丁寧な回答、まことにありがとうございます。

> 真偽表を作って8通りの場合のどれでも真になることをいうのが速いと思うが...
　作って確認しました。確かに手っ取り早いですね。

　論理計算に不慣れなので、丁寧な解説がとてもよくわかりました。本当にありがとうございました。