証明と真理値表
ヴィトゲンシュタインの解説本を読んでいたら、真理値表って面白いなって思う場面があったのでメモ。
大学生のころ、命題の証明法として「証明木」をつかったものを教わった。 証明木を使った証明とは、いくつかのルール（論理記号の「導入ルール」「削除ルール」）に従って、与えられた命題が正しいことを形式的に示すものだ。
たとえば「(A ∧ B) ∨ (A ∧ C) ⇒ B ∨ C」*1を示すには、以下の3つのルールが必要になる。（X, Y, Zはそれぞれ真または偽の値をもつ変数。）
∧ の除去：X ∧ Y が真ならば、 Xは真である。 （例：あなたが男性でかつ東京都出身ならば、あなたは男性である。）
∨ の導入：X が真ならば、 X ∨ Yは真である。 （例：あなたが男性であるならば、「あなたは男性または東京都出身である」という命題は真である。）
∨ の除去： X ∨ Y が真であり、Xを仮定してZという結果が証明できたとする。また、Yを仮定してZという結果が証明できたとする。このとき、Zは真である。 （例：すべての人は必ず男か女のいずれかである。ある人が男ならば、その人はいつか死ぬ。ある人が女ならば、その人はいつか死ぬ。したがってすべての人はいつか死ぬ。）
この3つのルールを用いると、「(A ∧ B) ∨ (A ∧ C) ⇒ B ∨ C」は次のように証明できる。
A ∧ B を仮定した場合、Bは真である。（∧の除去ルール）・・・① ①より、A ∧ Bを仮定した場合、B ∨ Cが真になる。（∨の導入ルール）・・・② A ∧ C を仮定した場合、Cは真である。（∧の除去ルール）・・・③ ③より、A ∧ Cを仮定した場合、B ∨ Cが真になる。（∨の導入ルール）・・・④ もし (A ∧ B) ∨ (A ∧ C) が真ならば、 ②④より、B ∨ C が真になる。（∨の除去ルール）・・・⑤ ⑤は「(A ∧ B) ∨ (A ∧ C) ⇒ B ∨ C」と等しい。したがって与えられた命題が証明された。
こんな風に、あらかじめ決められたルールをカチカチ組み合わせて、求める形式までもっていくのが証明木を用いた証明である。
今回やったようにつらつら文章で書くととっつきづらいが、図示しながらやると全体の構造がとってもわかりやすいので、けっこうポピュラーな証明方法なのかなと思う。
＊＊＊
続いて真理値表を用いた証明方法について。
真理値表は、命題を構成する変数の真 or 偽の組み合わせと、その命題の真 or 偽の対応関係を表にしたものだ。
例えば「X ∧ Y」と「X ∨ Y」の真理値表は次のようになる。
この図をながめながら「(A ∧ B) ∨ (A ∧ C)」と「B ∨ C」の真理値表をそれぞれつくってみる。これらの真理値表を作成するには、ただたんにAとかBに「真」「偽」の値を代入して、X ∧ Y とかの真理値表と照らし合わせればよい。形式的にできる*2。
これらをながめていると、すでに (A ∧ B) ∨ (A ∧ C) ⇒ B ∨ C の証明が完了していることに気づく。 ⇒（ならば）は前提が真である場合に結論が真であるという推論規則である。したがって、 (A ∧ B) ∨ (A ∧ C)の真理値表の真になっている行が、B ∨ C の真理値表の真になっている行に包含されていればよい。真理値表を確認してみるとそのようになっている（表中の赤く色づけした行）ため、(A ∧ B) ∨ (A ∧ C) ⇒ B ∨ C が証明された。
ついでに、B ∨ C ⇒ (A ∧ B) ∨ (A ∧ C) が成立しないことも、真理値表を眺めているとわかる。（B ∨ Cの真理値表の真になっている行が、(A ∧ B) ∨ (A ∧ C) の真になっている行を真に包含しているため。）
＊＊＊
最後に所感。 真理値表を用いて命題論理の証明ができるということについて、面白いなと思ったことが2つある。
ひとつはシンプルに、こういう証明方法もあるんだな～ということである。正直、証明木をつかった証明も真理値表をつかった証明も、本質的にやっていることは変わらない気はする。（証明木における「導入ルール」「除去ルール」が、X ∧ Y や X ∨ Y の真理値表に相当するため。）が、実際に手を動かしてみて、証明をしたいだけなら真理値表を用いたほうが簡単に証明ができることがわかった。
もうひとつは、普段僕らが使っている論理命題（「(A ∧ B) ∨ (A ∧ C)」とか「B ∨ C」とか）って論理にとってそんなに本質的なものではなく、真理値表だけが本質的なのかなと思ったことだ。（本質的ってなんなん、という話はあると思うけど、、） ∧ とか ∨ とか ￢*3 とか ⇒ を使った命題の表現は人間にとってわかりやすい。が、真理値が同じ命題を何通りも生み出せる。例えば ￢ A ∧ ￢ B は ￢(A ∨ B) と同じだ（ド・モルガンの法則）。真理値が同じ命題を何通りも生み出せるということは共通した構造が背景にあるはずで、それをわかりやすく示しているのは真理値表なのだなと思った。
証明と真理値表についてのメモおわり。
