論理積と論理和の結合法則

結合法則の演繹

命題論理の結合法則を自然演繹の推論規則から導いてみます。
結合法則は加法なら

(A+B)+C=A+(B+C)

と同値変形できる法則のことです。

論理積の結合法則の証明

1.A∧(B∧C)(前提)
2.A,B∧C(除去)
3.A,B,C(除去)
4.A∧B,C(導入)
5.(A∧B)∧C(導入)

自然演繹の推論規則に従い結合法則が成立することを演繹できました。

A∧(B∧C)⇔(A∧B)∧C

論理和の結合法則

1.[C](仮定)
2.B∨C(∨導入)
3.A∨(B∨C)(∨導入)
4.C→A∨(B∨C)(→導入)
5.[A]
6..A∨(B∨C)(∨導入)
7.A→A∨(B∨C)(→導入)
8.[B]
9.B∨C(∨導入)
10.A∨(B∨C)(∨導入)
11.B→A∨(B∨C)(→導入)
12.[A∨B](仮定)
13.A∨(B∨C)(∨除去)
14.A∨B→A∨(B∨C)(→導入)
15.[(A∨B)∨C](仮定)
16.A∨(B∨C)(∨除去)
17.(A∨B)∨C→A∨(B∨C)

(A∨B)∨CがA∨(B∨C)となること、つまりA,B,C各命題変数がA∨(B∨C)に変形できることを示し、その後に∨除去により一つの結論に統一します。

ABCの全てを同じ場所に着地させられることを証明することで必然的に∨が外れてしまいます。