問題12 (~p→(q∧~p))∧(~q→(p∧~q))≡p∨q →から∨への変換の補題、 ~X→Y≡X∨Y …① と、補完因子除去の補題、 X∨(Y∧~X)≡X∨Y …② が成り立ちます。 →から∨への変換の補題、 ~X→Y≡X∨Y …① は、A→Bの解釈「A→Bが真となるとき、そしてそのときに限り、Aが偽またはBが真」からの定義式、A→B≡~A∨Bの、Aに~Xを代入したものです。 補完因子除去の補題、 X∨(Y∧~X)≡X∨Y …② は、 ╅⃝∨┾⃝≡╅⃝∨╆⃝で両辺ともに╈⃝で同値です。 ベン図を暗示する記号で、X≡╅⃝、Y≡╆⃝とすると、~X≡╄⃝、Y∧~X≡╆⃝∧╄⃝≡┾⃝なので、X∨(Y∧~X)≡ ╅⃝∨┾⃝ ≡ ╈⃝ ≡ ╅⃝∨╆⃝ ≡ X∨Yとなることから、成立することが直感的に分かります。あたりまえなので、これを証明するのは面倒臭いです。 では補題①,②から証明していきましょう。 【→から∨への変換の補題】 ~X→Y≡X∨Y …① (証明) 左辺≡ ~X→Y ≡~(~X)∨Y (∵→の定義式A→B≡~A∨B) ≡X∨Y (∵二重否定則) (証明終わり) 【補完因子除去の補題】 X∨(Y∧~X)≡X∨Y …② (証明) 左辺≡ X∨(Y∧~X) ≡ (X∨Y)∧(X∨~X) (∵分配則) ≡ (X∨Y)∧T(∵相補則X∨~X≡T(x+x'=1)) ≡ (X∨Y) (∵Tの規則X∧T≡X(x•1=x)) ≡ 右辺 (証明終わり) ①,②が証明されたのでこれらを使って、 (~p→(q∧~p))∧(~q→(p∧~q))≡p∨q 証明します。 (証明) 左辺≡ (~p→(q∧~p))∧(~q→(p∧~q)) ≡ (p∨(q∧~p))∧(q∨(p∧~q)) (∵①) ≡ (p∨q)∧(q∨p) (∵②) ≡ (p∨q)∧(p∨q) (∵交換則Y∨X≡X∨Y) ≡ (p∨q) (∵冪等則X∧X≡X) (証明終わり) ①,②を用いたのでスッキリと証明できました。もちろん一括証明もできますが面倒臭いので書きません。練習になるからやって見てください。