●練習問題3.103(5)について：もとの問題は\(\varphi,\psi\)を用いていますが、説明の都合で命題記号\(P,Q\)に置き換えます。\(P,Q,\rightarrow\)のみから構成されるいかなる論理式\(\chi\)も\(P\wedge Q\)と同値にならない、つまり\(\chi\)と\(P\wedge Q\)の真偽が食い違うような解釈が必ず存在することを示したいわけですが、実際には\(\chi\)を真にし\(P\wedge Q\)を偽にする解釈が必ず存在するので、このことを示せば十分です。以下、論理式\(\chi\)についての条件\(C(\chi)\)を、
・\(\chi\)を真にし、同時に\(P\wedge Q\)を偽にする解釈が存在する。
と定義しておきます。構造帰納法による証明のアウトラインは、
(1)\(C(P)\)および\(C(Q)\)が成り立つこと。
(2)\(C(\alpha)\)および\(C(\beta)\)を仮定し、\(C(\alpha\rightarrow\beta)\)を導く。
というものになります。
