人気ブログランキング | 話題のタグを見る

ド・モルガンの法則

ウカシェビッチの公理系を再掲する。

P1. A -> (B -> A) ..... 含意の公理
P2. (A -> (B -> C)) -> ((A -> B) -> (A -> C)) ..... 推移律の公理
P3. (¬B -> ¬A) -> (A -> B) ..... 否定演算(対偶)の公理

また、論理式への代入をするため次の公理を追加する。

P4. ((A -> B) -> (B -> A)) -> ((A -> C) -> (B -> C)) ..... 代入の公理

この条件で論理計算の法則を定理として演繹してみる。今回は、次のド・モルガンの法則を証明する。

¬(A ∧ B) -> (¬A ∨ ¬B)

証明は次のようになる。

A0 = ¬¬A -> A ..... 定理
A1 = ¬¬(A -> ¬B) -> (A -> ¬B) .... A を A -> ¬B で置き換える
A2 = A -> ¬¬A .... 定理
A3 = (A -> ¬B) -> (¬¬A -> ¬B) ..... 代入の公理
A4 = ¬(¬(A -> ¬B)) -> (¬¬A -> ¬B) ..... P2(推移律)
A5 = ¬(A ∧ B) -> (¬A ∨ ¬B)

逆の (¬A ∨ ¬B) -> ¬(A ∧ B) も証明できる。

A0 = A -> ¬¬A ..... 定理
A1 = (A -> ¬B) -> ¬¬(A -> ¬B) ..... A を A -> ¬B に置き換え
A2 = A -> ¬¬A ..... 定理
A3 = (A -> ¬B) -> (¬¬A -> ¬B) ..... 代入の公理
A4 = ¬¬A -> A ..... 定理
A4 = (¬¬A -> ¬B) -> (A -> ¬B) ..... 代入の公理
A5 = (¬¬A -> ¬B) -> ¬¬(A -> ¬B) ..... A1 に代入の公理を適用して前件を ¬¬A -> ¬B に置き換える
A6 = (¬(¬A) -> (¬B)) -> ¬(¬(A -> ¬B))
A7 = (¬A ∨ ¬B) -> ¬(A ∧ B)

一方、

¬(A ∨ B) -> ¬A ∧ ¬B

の証明は非常に簡単だ。証明は次のようになる。

A0 = A -> A ..... 定理
A1 = ¬(¬A -> B) -> ¬(¬A -> B) ..... 置き換え
A2 = ¬(¬A -> B) -> ¬((¬A) -> ¬(¬B))
A3 = ¬(A ∨ B) -> (¬A ∧ ¬B)

A1 の前件と後件の解釈を反対にすれば、逆の証明も同じようにできる。

A4 = ¬((¬A) -> ¬(¬B)) -> ¬(¬A -> B)
A5 = (¬A ∧ ¬B) -> ¬(A ∨ B)

論理計算の法則を定理として証明するのは大変だが、一旦証明してしまうと、その法則を使って行った論理計算は全て公理系で証明可能であるということができる。

命題論理の完全性定理の印象としては、まず公理系があって、それとトートロジーとの関連を探るということを考える。しかし、論理計算の体系が最初にあって、その論理計算を演繹できるような最小限の公理を選択するという逆の方向への発想もできる。この方向からのアプローチであれば、すべてのトートロジーを演繹できる公理を選ぶのだから、トートロジーは全て公理から演繹できるということは至極当たり前のことになる。

論理計算の場合は、トートロジーの計算は機械的にできる。公理系では定理を元に証明を機械的に発見するのは難しい。だから、論理計算の体系が先にあって、それを元に公理を選び出すというのが自然な流れだ。しかし、公理系を構築することによって、論理結合子の意味を取り去って論理体系を単なる記号の配列の操作にすることができる。公理系と論理計算が別々にあってたまたま同値関係にあったと考えるよりは、論理計算の体系が先にあって、その抽象化を行ったのが公理系だと考える方がわかりやすいのではないだろうか。

by tnomura9 | 2016-09-11 22:15 | 考えるということ | Comments(0)
<< 命題論理と結合律 公理系と論理計算の法則 >>