命題論理の完全性の証明？：トートロジーのからくり

これまでの内容については、
電流が流れるか流れないか学（電流学）｜カピ哲！｜note
をご覧ください。

　前記事の応用である。

(Ａ∧Ｂ∧Ｃ)→Ｄ

がトートロジーであるとする。

(Ａ∧Ｂ∧Ｃ)→Ｄ は、
(Ａ∧Ｂ)→(Ｃ→Ｄ)
Ａ→(Ｂ→(Ｃ→Ｄ))　というふうに（同値のまま）変形できるが、一方で、

(Ａ∧Ｂ∧Ｃ)→Ｄ
(Ａ∧Ｂ∧Ｃ)→(￢￢Ｄ∨⋏)
(Ａ∧Ｂ∧Ｃ)→(￢Ｄ→⋏)
(Ａ∧Ｂ∧Ｃ∧￢Ｄ)→⋏

・・・というふうに（→の左側、左辺・前件を）矛盾回路へ導くこともできるのである（もちろん論理式全体としてはトートロジーが維持されている）。
　このように、おそらくすべてのトートロジーは

矛盾回路→⋏

という形式に変形することができるのではなかろうか。というか、むしろトートロジーであるからこそ(矛盾回路→⋏)という形へ導くことができると言える。
　Ａ、Ｂ、Ｃ、￢Ｄを前提とし、そこから矛盾を導くことができる。そしてそこからEx falso quodibetあるいは背理法？により(Ａ∧Ｂ∧Ｃ)→Ｄというトートロジーを証明することができるのである。

　まずは一つ事例を示してみたい。前原『記号論理入門』42ページの例２である。

(Ａ→(Ｂ→Ｃ))→((Ａ∧Ｂ)→Ｃ)

矛盾回路→⋏の形へ変形してみる。
((Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ))→Ｃ
((Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ))→(￢￢Ｃ∨⋏)
((Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ))→(￢Ｃ→⋏)
((Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ)∧￢Ｃ)→⋏

(Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ)∧￢Ｃを変形すると
(￢Ａ∨(￢Ｂ∨Ｃ))∧(Ａ∧Ｂ)∧￢Ｃ

回路図にすると、図46のようになり、明らかな矛盾回路であることが分かる。

図46 (￢Ａ∨(￢Ｂ∨Ｃ))∧(Ａ∧Ｂ)∧￢Ｃの回路図

前原は、(Ａ→(Ｂ→Ｃ))→((Ａ∧Ｂ)→Ｃ)を以下のように証明している。

（前原昭二『記号論理入門』日本評論社、42ページ）

　一方、((Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ)∧￢Ｃ)→⋏の証明プロセスは以下のようなものとなる。

これを回路図で説明してみよう。

図47 ((Ａ→(Ｂ→Ｃ))∧(Ａ∧Ｂ)∧￢Ｃ)→⋏の回路図による証明