今回は、命題論理でよく使われるもう一つの性質である、「ド・モルガンの法則」および「論理積と論理和の分配法則」の証明を確認します。これらの法則は集合論で頻繁に登場し、その応用範囲は数学全般に及びます。確率論や位相空間論はもちろん、電子工学やプログラミングの分野でも重要な役割を果たします。これまで学んできた推論技法を基に、これらの法則の証明を丁寧に解き明かしていきましょう。

ド・モルガンの法則

ド・モルガンの法則は、否定と論理積および論理和の分配を形式化する一連の同値関係です。形式的には次の同値式で表されます：

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

これらの同値関係は、これまで行ってきたような証明を用いずとも、論理積と論理和の関係に関する定義と、二重否定の同値性、そしていくつかの置換を用いることで導出できます。論理積の定義から次の式が得られます：

(A \wedge B):= \neg(\neg A \vee \neg B)

この式の両辺に否定を加えることで、次のようになります：

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

そして、二重否定の同値性によって、

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

最後に、A=\alpha および B=\beta を代入することで、ド・モルガンの第1の同値式が得られます：

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

第2の同値式を得るには、先ほどの式に再び両辺へ否定を加えます。すると次のようになります：

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

そして再度、二重否定により次の式を得ます：

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

この式に対して、A=\neg\alpha および B=\neg\beta を代入すると、

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

ここから二重否定を適用すれば、ド・モルガンの第2の同値式が導かれます：

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

さらに、完全に同様の手順で、以下のような追加の変形形も得られます。これらは先ほどの法則の単なる変形版です：

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \dashv \vdash (\neg\alpha \wedge \beta)

論理積と論理和における分配法則

その名の通り、これらの規則は、式の中で論理積や論理和を分配することを可能にします。これらの法則は次の2つの同値関係にまとめられます：

これまでに見てきたように、これらは既知の結果ではあるものの、その証明は決して自明ではありません。完全な証明には両方向の推論が必要ですが、今回は一方向のみの証明を示し、逆方向の証明は読者への課題とします。

∧ – 分配法則

次を証明するために \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)) 以下の推論が得られます。

これにより、\{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)) が証明されました。次はあなたの番です。学んだことを活用して、\{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)) を自分で証明してみましょう。

∨ – 分配法則

次の証明 \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) は、以下の推論によって得られます：

これで証明の半分が完了しました。あとは逆方向の証明が残っていますが、それは読者への課題とします :3

最終的な考察

ここまで、論理積および論理和の分配に関するド・モルガンの法則の証明を振り返ってきました。これにより、命題論理の推論技法に関する学習と、それらがいかにして古典論理の主要な法則の証明へと収束していくかという点についての考察を終えることができます。

これらの技法に関する理解を深めるためには、提案されたすべての証明を自力で完成させることが重要です。証明を完成させる際には、証明同士を比較して類似点を探すと良いでしょう。ある証明で機能した戦略が、少し手を加えることで別の証明にも適用できる場合があるからです。

最後に注目すべき点として、これらの証明を展開する際に私が選んだ順序があります。よく見ると、各証明はそれ以前の証明の結果を活用していることがわかります。私はこの順番の方が個人的にわかりやすいと感じたため、この構成を選びました。こうした能力を高めるための良い練習として、「同じ手法を用いて、異なる順序でこれらの証明を構築できるだろうか？」という問いを自分に投げかけてみてください。ぜひ挑戦してみてください。たとえうまくいかなくても、その試み自体が論理における証明や技法に対する理解を確実に深めてくれるはずです。