文庫版Ⅰの118pから120p ブール代数の
公準と定理の証明
定義と公準∵(開く)
0) 類、等号 $=$ 及び不等号 $\neq$ 。 ∵(開く)
類あるいは集合
我々は類を定義せず、とにかくある類(これを $C$ とおく)とあるもの( $i$ とおく)が与えられたとき、
$i$ が $C$ の構成要素であるか否かを直感的に認識できると仮定する。
もし $i$ が $C$ の構成要素ならば、$i$ は $C$ に属するという。
等号 $=$ 及び不等号 $\neq$
(より一般的には、等号は「
同値関係」が成立することを示し、不等号は成立しないことを示す。)
・ $a=b$ か、その否定 $a\neq b$ かのどちらか一方だけが成り立つ。
・ $a=a$ である。(反射率)
・ $a=b$ ならば $b=a$ である。(対称率)
・ $a, b, c$ が類 $K$ に属し $a=b$ かつ $b=c$ ならば $a=c$ である。(推移率)
・ もし $a, b, c ...$ が 類 $K$ の部分集合ならば、 $a=b$ とは
”$a$ に属する要素は全て $b$ に属し、 $b$ に属する要素は全て $a$ に属する”ことである。
このことを” $a$ は $b$ を含み、かつ $b$ は $a$ を含むともいう。
1-1) $a, b$ が類に属するならば $a\oplus b$ はこの類に属する。( $\oplus$ に関して閉じている。)
1-2) $a, b$ が類に属するならば $a\otimes b$ はこの類に属する。( $\otimes$ に関して閉じている。)
2-1) 類に属する任意の $a$ に対し $a\oplus 0=a$ となる要素 $0$ が存在する。( $\oplus$ に関し恒等元をもつ。)
2-2) 類に属する任意の $a$ に対し $a\otimes 1=a$ となる要素 $1$ が存在する。( $\otimes$ に関し恒等元をもつ。)
3-1) $a, b$ が類に属するならば $a\oplus b=b\oplus a$。( $\oplus$ は可換である。)
3-2) $a, b$ が類に属するならば $a\otimes b=b\otimes a$。( $\otimes$ は可換である。)
4-1) $a, b, c$ が類に属するならば $a\oplus(b\otimes c)=(a\oplus b)\otimes(a\oplus c)$。( $\oplus$ は交換法則を満たす。)
4-2) $a, b, c$ が類に属するならば $a\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c)$。 ( $\otimes$ は交換法則を満たす。)
5) 類に属する任意の $a$ に対し $a\oplus\overline{a}=1$ 、$a\otimes\overline{a}=0$ を満たす要素 $\overline{a}$ が存在する。
$\overline{a}$ を $a$ の補元という。
6) 類には少なくとも二つの要素が存在して、それを $x, y$ とすれば $x\neq y$ となる。
定理とその証明
公準系は 1) と 2) が対になっている(双対性)ので、演算子の変換により一方から他方が導ける。対になっている定理は 1) のみ証明する。
7-1) 公準 2-1)の要素 $0$ は唯一つしかない。∵(開く)
二つあるとして、それを $0$ と $z$ とすると、任意の $a, b$ に対し
$a\oplus 0=a, b\oplus z=b$
$a$ を $z$ とおくと$z\oplus 0=z$
$b$ を $0$ とおくと$0\oplus z=0$
公準 3-1)により $z\oplus 0=0$
よって
推移率により $z=0$。
7-2)
公準 2-2)の要素 $1$ は唯一つしかない。
8-1) $a\oplus a=a$ (巾等あるいは冪等)∵(開く)
公準 4-1)の $b$ を $a$ 、 $c$ を $\overline{a}$ とおくと
$a\oplus(a\otimes\overline{a})=(a\oplus a)\otimes(a\oplus\overline{a})$
この式は
公準 5)より $a\oplus 0=(a\oplus a)\otimes 1$
公準 2-1)、
公準 2-2) により $a=a\oplus a$ 。
8-2) $a\otimes a=a$
9-1) $a\oplus 1=1$∵(開く)
公準 4-1)の $b$ を $\overline{a}$ 、$c$ を $1$ とおくと $a\oplus(\overline{a}\otimes 1)=(a\oplus\overline{a})\otimes(a\oplus 1)$
この式は
公準 2-2)より $a\oplus\overline{a}=(a\oplus\overline{a})\otimes(a\oplus 1)$
従って、
公準5) より $1=a\oplus 1$。
9-2) $a\otimes 0=0$
10-1) $a\oplus(a\otimes b)=a$ (吸収法則)∵(開く)
公準 2-2)により、左辺 $a\oplus(a\otimes b)=(a\otimes 1)\oplus(a\otimes b)$
公準 4-2) の $b$ を $1$、 $c$ を $b$ とおいて$(a\otimes 1)\oplus(a\otimes b)=a\otimes(1\oplus b)$
定理 9-1) により $a$。
10-2) $a\otimes(a\oplus b)=a$
11) 公準 5)の要素 $\overline{a}$ は $a$ によってただ一つに定まる。
∵(開く)
二つあるとして、それを $\overline{a}$ と $\hat{a}$ とすると
$a\oplus\overline{a}=1$ ....①
$a\otimes\overline{a}=0$ ....②
$a\oplus\hat{a}=1$ ....③
$a\otimes\hat{a}=0$ ....④
①より $\hat{a}=(a\oplus\overline{a})\otimes\hat{a}$
公準 4-2) により
$=a\otimes\hat{a}\oplus\overline{a}\otimes\hat{a}$ ④から
$=\overline{a}\otimes\hat{a}$。
同様に、③より$\overline{a}=\hat{a}\otimes\overline{a}$ を得る。
従って $\overline{a}=\hat{a}$
12-1) $a\oplus b=\overline{\overline{a}\otimes\overline{b}}$ (ド・モルガンの定理)∵(開く)
$a\oplus b$の補元が $\overline{a}\otimes\overline{b}$ であることを示せばよい。
そのためには $(a\oplus b)\oplus(\overline{a}\otimes\overline{b})=1$ かつ $(a\oplus b)\otimes(\overline{a}\otimes\overline{b})=0$ を示せばよい。
公準 4-1) により $(a\oplus b)\oplus(\overline{a}\otimes\overline{b})=((a\oplus b)\oplus\overline{a})\otimes((a\oplus b)\oplus\overline{b})$
定理 13-1)、
公準 5) により
$=(1\oplus b)\otimes(a\oplus 1)$ この式は
定理 9-1) により $1$。
(定理12 の証明に定理13を使用しているが、定理13の証明に定理12を使っていないので問題ない。
しかし、気持ち悪いので別証明∵(開く))
$(a\oplus b)\oplus\overline{a}=1$ を示せばよい。
$(a\oplus b)\oplus\overline{a}=(a\oplus\overline{a})((a\oplus b)\oplus\overline{a})$
$=(a\otimes((a\oplus b)\oplus\overline{a}))\oplus(\overline{a}\otimes((a\oplus b)\oplus\overline{a}))$
定理10-2)により
$=(a\otimes((a\oplus b)\oplus\overline{a}))\oplus\overline{a}$
$=(a\otimes(a\oplus b)\oplus a\otimes\overline{a})\oplus\overline{a}$
公準 5)により
$=a\otimes(a\oplus b)\oplus\overline{a}$
定理10-2)により
$=a\oplus\overline{a}=1$。
また、
公準 4-2) により
$(a\oplus b)\otimes(\overline{a}\otimes\overline{b})=((\overline{a}\otimes\overline{b})\otimes a)\oplus((\overline{a}\otimes\overline{b})\otimes b)$
定理 13-2)、
公準 5) により
$=(\overline{b}\otimes 0)\oplus(\overline{a}\otimes 0)$ この式は
定理 9-2) により $0$。
12-2) $a\otimes b=\overline{\overline{a}\oplus\overline{b}}$
13-1) $(a\oplus b)\oplus c=a\oplus(b\oplus c)$ (結合法則)∵(開く)
右辺 $a\oplus(b\oplus c)=1\otimes(a\oplus(b\oplus c))$
$=(a\oplus\overline{a})\otimes(a\oplus(b\oplus c))$
$=(a\otimes(a\oplus(b\oplus c))\oplus(\overline{a}\otimes(a\oplus(b\oplus c)))$
定理 10-2)から
$a\otimes(a\oplus(b\oplus c))=a$ なので
$=a\oplus(\overline{a}\otimes(a\oplus(b\oplus c))) $展開すると
$=a\oplus((\overline{a}\otimes a)\oplus(\overline{a}\otimes(b\oplus c)))$
$=a\oplus((\overline{a}\otimes a)\oplus((\overline{a}\otimes b)\oplus(\overline{a}\otimes c)))$
公準 5)から
$\overline{a}\otimes a=0$ だから
$=a\oplus((\overline{a}\otimes b)\oplus(\overline{a}\otimes c))$
$=a\oplus((0\oplus(\overline{a}\otimes b))\oplus(\overline{a}\otimes c))$
公準 5)から
$=a\oplus(((\overline{a}\otimes a)\oplus(\overline{a}\otimes b))\oplus(\overline{a}\otimes c))$
$=a\oplus((\overline{a}\otimes(a\oplus b))\oplus(\overline{a}\otimes c))$
$=a\oplus((\overline{a}\otimes((a\oplus b)\oplus c))$ ここで
$a=a\otimes((a\oplus b)\oplus c)$
∵(開く) なので
$a\otimes((a\oplus b)\oplus c)=a\otimes(a\oplus b)\oplus a\otimes c$
定理 10-2)により
$=a\oplus a\otimes c$
定理 10-1)により $=a$ 。
$=(a\otimes((a\oplus b)\oplus c))\oplus((\overline{a}\otimes((a\oplus b)\oplus c))$
$=(a\oplus\overline{a})\otimes((a\oplus b)\oplus c))=(a\oplus b)\oplus c$。
13-2) $(a\otimes b)\otimes c=a\otimes(b\otimes c)$