$2^X$ 上のブール代数の構造

(0)

準備
$({0,1},+,\cdot,-,0,1)$ は演算の規則

$$1+1=1,1+0=1$$

$$0+1=1,0+0=0$$

$$1 \cdot 1=1,1 \cdot 0=0$$

$$0 \cdot 1=0,0 \cdot 0=0$$

$$-0=1,-1=0$$

のもとでブール代数になっています.[証明は根気良く公理をチェックするだけなので省略]

(1)

$2^X$ 上のブール代数の構造
0と1は

$$\begin{eqnarray*} 0: x \in X &\longmapsto& 0 \in \{ 0,1 \} \\ 1: x \in X &\longmapsto& 1 \in \{ 0,1 \} \\ \end{eqnarray*}$$

で定義し, $+,\cdot,-$ は $g,h \in 2^X$ について

$$\begin{eqnarray*} -g :x \in X &\longmapsto& -g(x) \in \{ 0,1 \} \\ g+h :x \in... ...cdot h :x \in X &\longmapsto& g(x) \cdot h(x) \in \{ 0,1 \} \\ \end{eqnarray*}$$

で定義すれば $(2^X,+,\cdot,-,0,1)$ はブール代数です.

ただし,上の定義式の右辺の $g(x),h(x) \in \{ 0,1 \}$ についての演算 $g(x)+h(x),g(x) \cdot h(x),-g(x)$ はブール代数 $({0,1},+,\cdot,-,0,1)$ の演算です.

[証明]

$X$ が空集合でなければ $2^X$ が空集合でないことは自明. $+,\cdot,-$ が $2^X$ 上の演算であることも自明なので省略. 以下 $g,h,k \in 2^X$ を任意 とり公理 (i) $\sim$ (v) が成立することを確認します.

これは $g,h,k$ が何れも $X$ 上で定義され,0か1の値しか取らない関数であるこ とと,(0)で述べたように $({0,1},+,\cdot,-,0,1)$ がブール代数である ことを用いて根気良くチェックすればできます.

以下,各 $x \in X$ に対する $g(x),h(x),k(x) \in \{ 0,1 \}$ についての演算 $(+,\cdot,-)$ は(0)のブール代数 $({0,1},+,\cdot,-,0,1)$ の演算で, 交換律,結合律,吸収律,補元律その他は断りなく使います.

1. 交換律
   $x \in X$ を任意とると
   $$\begin{eqnarray*} (g+h)(x) &=& g(x)+h(x) \\ &=& h(x)+g(x) \\ &=& (h+g)(x) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)((g+h)(x)=(h+g)(x))$$
   
   
   よって
   
   $$g+h=h+g$$
   
   
   全く同様にして ( $+$ を $\cdot$ に替えて)
   
   $$g \cdot h=h \cdot g$$
   
   
   
   

2. 結合律
   $x \in X$ を任意とると
   $$\begin{eqnarray*} ((g+h)+k)(x) &=& (g+h)(x)+k(x) \\ &=& (g(x)+h(x))+k(x) \\ &=& g(x)+(h(x)+k(x)) \\ &=& (g+(h+k))(x) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)(((g+h)+k)(x)=(g+(h+k))(x))$$
   
   
   よって
   
   $$(g+h)+k=g+(h+k)$$
   
   
   全く同様にして ( $+$ を $\cdot$ に替えて)
   
   $$(g \cdot h) \cdot k=g \cdot (h \cdot k)$$
   
   
   
   
3. 吸収律
   $x \in X$ を任意とると
   $$\begin{eqnarray*} ((g \cdot h)+h)(x) &=& (g \cdot h)(x)+h(x) \\ &=& (g(x) \cdot h(x))+h(x) \\ &=& h(x) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)(((g \cdot h)+h)(x)=h(x))$$
   
   
   よって
   
   $$(g \cdot h)+h=h$$
   
   
   全く同様にして $+$ を $\cdot$ に, $\cdot$ を $+$ に替えて $x \in X$ を任意とると
   $$\begin{eqnarray*} ((g+h) \cdot h)(x) &=& (g+h)(x) \cdot h(x) \\ &=& (g(x)+h(x)) \cdot h(x) \\ &=& h(x) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)((g+h) \cdot h)(x)=h(x))$$
   
   
   よって
   
   $$(g+h) \cdot h=h$$
   
   

4. 分配律
   $x \in X$ を任意とると
   $$\begin{eqnarray*} (g \cdot (h+k))(x) &=& g(x) \cdot (h+k)(x) \\ &=& g(x) \cdo... ...cdot h)(x)+(g \cdot k)(x) \\ &=& (g \cdot h+g \cdot k)(x) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)((g \cdot (h+k))(x)=(g \cdot h+g \cdot k)(x))$$
   
   
   よって
   
   $$g \cdot (h+k)=g \cdot h+g \cdot k$$
   
   

   $x \in X$ を任意とると

   $$\begin{eqnarray*} (g+(h \cdot k))(x) &=& g(x)+(h \cdot k)(x) \\ &=& g(x)+(h(x... ...&=& (g+h)(x) \cdot (g+k)(x) \\ &=& ((g+h) \cdot (g+k))(x) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)((g+(h \cdot k))(x)=((g+h) \cdot (g+k))(x))$$
   
   
   よって
   
   $$g+(h \cdot k)=(g+h) \cdot (g+k)$$
   
   

5. 補元律
   $x \in X$ を任意とると
   $$\begin{eqnarray*} ( g \cdot (-g))(x) &=& g(x) \cdot (-g(x)) \\ &=& 0 \end{eqnarray*}$$
   
   
   
   
   
   
   $$\begin{eqnarray*} (g+(-g))(x) &=& g(x)+(-g(x)) \\ &=& 1 \end{eqnarray*}$$
   
   
   
   
   
   
   $x$ は任意だったから
   
   $$(\forall x \in X)((g \cdot (-g))(x)=0(x))$$
   
   
   
   
   $$(\forall x \in X)((g+(-g))(x)=1(x))$$
   
   

   よって
   

   $$g \cdot (-g)=0,g+(-g)=1$$
   
   
   
   

(2)

双射 $f:P(X) \rightarrow 2^X$ の構成
これは

$$\begin{eqnarray*} f: Y \in P(X) \longmapsto f(Y) \in 2^X \\ f(Y): x \in X \longmapsto \chi_Y(x) \in \{ 0,1 \} \\ \end{eqnarray*}$$

で定義します. $\chi_Y$ は $X$ 上の $Y$ の特性関数で $x \in Y$ のとき $1、x \in X-Y$ のとき $0$ をとる関数です. これが双射であることは

1. $Y,Z \in P(X)$ を任意にとり $f(Y)=f(Z)$ とすると
   
   $$(\forall x \in X)(f(Y)(x)=f(Z)(x))$$
   
   
   で $x$ を任意にとると
   $$\begin{eqnarray*} x \in Y &\Leftrightarrow& f(Y)(x)=1 \\ &\Leftrightarrow& f(Z)(x)=1 \\ &\Leftrightarrow& x \in Z \end{eqnarray*}$$
   
   
   
   
   
   
   で, $x$ は任意でしたから
   
   $$(\forall x)(x \in Y \Leftrightarrow x \in Z)$$
   
   
   よって
   
   $$Y=Z$$
   
   
   $Y,Z$ は任意でしたから
   
   $$(\forall Y \in P(X))(\forall Z \in P(X))(f(Y)=f(Z) \Rightarrow Y=Z)$$
   
   
   すなわち, $f$ は単射

2. $g \in 2^X$ を任意にとり, $Y \in P(X)$ を $Y= \{ x\vert x \in X ~and~ g(x)=1 \}$ とすれば： $x \in X$ を任意にとると, $x \in Y$ のとき $\chi_Y(x)=1=g(x)$ $x \in X-Y$ のとき $\chi_Y(x)=0=g(x)$ $x$ は任意にとったから
   
   $$(\forall x \in X)(\chi_Y(x)=g(x))$$
   
   
   すなわち,
   
   $$\chi_Y=g$$
   
   
   よって
   
   $$f(Y)=g$$
   
   
   $g \in 2^X$ は任意にとったので
   
   $$(\forall g \in 2^X)(\exists Y \in P(X))(f(Y)=g)$$
   
   
   　すなわち $f$ は全射

(3)

双射 $f:P(X) \rightarrow 2^X$ がブール代数の構造について 同型であること. これも,特性関数の性質から殆ど自明ですが, $(P(X),\cup,\cap,\sim,0,X)$ がブール代数であることは演習(3)で既に示されています. $(2^X,+,\cdot,-,0,1)$ もブール代数であることは(1)で示しました.

$Y,Z \in P(X)$ のとき $Y \cup Z,Y \cap Z,X-Y$ の特性関数については

1. $\chi_{Y \cup Z}= \chi_Y + \chi_Z$
2. $\chi_{Y \cap Z}= \chi_Y \cdot \chi_Z$
3. $\chi_{X -Y}=- \chi_Y$

が成立します. これと$f$ の定義から

$$f(Y \cup Z)= \chi_{Y \cup Z}= \chi_Y + \chi_Z =f(Y)+f(Z)$$

$$f(Y \cap Z)= \chi_{Y \cap Z}= \chi_Y \cdot \chi_Z =f(Y) \cdot f(Z)$$

$$f(X-Y)= \chi_{X -Y}=- \chi_Y =-f(Y)$$

(a) $\sim$ (b)の [証明]

$x \in X$ を任意にとると, $x \in Y \cup Z$ のとき

$$\chi_{Y \cup Z}(x)=1$$

また, $x \in Y ~or~ x \in Z$ から

$$\chi_Y (x)=1 ~or~ \chi_Z (x)=1$$

よって

$$\chi_Y (x)+ \chi_Z (x)=1$$

ゆえに

$$\chi_{Y \cup Z}(x)= \chi_Y (x)+ \chi_Z (x)$$

$x \in X-(Y \cup Z)$ のとき

$$\chi_{Y \cup Z}(x)=0$$

また, $X-(Y \cup Z)=(X-Y) \cap (X-Z)$ ゆえ $x \in (X-Y) ~and~ x \in (X-Z)$ から

$$\chi_Y (x)=0 ~and~ \chi_Z (x)=0$$

よって

$$\chi_Y (x)+ \chi_Z (x)=0$$

ゆえに

$$\chi_{Y \cup Z}(x)= \chi_Y (x)+ \chi_Z (x)$$

結局,どちらの場合でも

$$\chi_{Y \cup Z}(x)= \chi_Y (x)+ \chi_Z (x) =( \chi_Y + \chi_Z )(x)$$

$x \in X$ を任意にとったので

$$(\forall x \in X)( \chi_{Y \cup Z}(x)=( \chi_Y + \chi_Z )(x))$$

よって

$$\chi_{Y \cup Z}= \chi_Y + \chi_Z$$

$x \in X$ を任意にとると $x \in Y \cap Z$ のとき

$$\chi_{Y \cap Z}(x)=1$$

また, $x \in Y ~and~ x \in Z$ から

$$\chi_Y (x)=1 ~and~ \chi_Z (x)=1$$

よって

$$\chi_Y (x) \cdot \chi_Z (x)=1$$

ゆえに

$$\chi_{Y \cap Z}(x)= \chi_Y (x) \cdot \chi_Z (x)$$

$x \in X-(Y \cap Z)$ のとき

$$\chi_{Y \cap Z}(x)=0$$

また, $X-(Y \cap Z)=(X-Y) \cup (X-Z)$ ゆえ $x \in (X-Y) ~or~ x \in (X-Z)$ から

$$\chi_Y (x)=0 ~or~ \chi_Z (x)=0$$

よって

$$\chi_Y (x) \cdot \chi_Z (x)=0$$

ゆえに

$$\chi_{Y \cap Z}(x)= \chi_Y (x) \cdot \chi_Z (x)$$

結局、どちらの場合でも

$$\chi_{Y \cap Z}(x)= \chi_Y (x) \cdot \chi_Z (x) =( \chi_Y \cdot \chi_Z )(x)$$

$x \in X$ を任意にとったので

$$(\forall x \in X)( \chi_{Y \cap Z }(x)=( \chi_Y \cdot \chi_Z)(x))$$

よって

$$\chi_{Y \cap Z}= \chi_Y \cdot \chi_Z$$

$x \in X$ を任意にとると $x \in Y$ のとき

$$\chi_X -Y(x)=0$$

また $\chi_Y (x)=1$ ゆえ $- \chi_Y (x)=0$
よって

$$\chi_{X -Y}(x)=- \chi_Y (x)$$

$x \in X-Y$ のとき

$$\chi_{X -Y}(x)=1$$

また $\chi_Y (x)=0$ ゆえ $-\chi_Y (x)=1$
よって

$$\chi_{X -Y}(x)=- \chi_Y (x)$$

結局,どちらの場合でも

$$\chi_{X -Y}(x)= -\chi_Y (x)=( -\chi_Y )(x)$$

$x \in X$ を任意にとったので

$$(\forall x \in X)( \chi_{X -Y}(x)=( -\chi_Y )(x))$$

よって

$$\chi_X -Y= -\chi_Y$$

[証明終]

(命題) ブール代数の同型写像の逆写像は,またブール代数の同型写像である.
(命題終わり)

[証明]

$f:A \rightarrow B$ をブール代数の同型写像とします.
任意の $a, b \in A$ について,

$$f(a \cdot b)=f(a) \cdot f(b),f(-a)=-f(a)$$

がいえます.
$f^{(-1)} :B \rightarrow A$ を $f$ の逆写像とします.
$f$ が全単射であることから, $f^{(-1)}$ は全単射です.
任意の $x, y \in B$ について,

$$f^{(-1)}(x),f^{(-1)}(y) \in A$$

ですから, $f$ が準同型写像であることから,

$$f(f^{(-1)}(x) \cdot f^{(-1)}(y))=f(f^{(-1)}(x)) \cdot f(f^{(-1)}(y))$$

がいえます.
任意の $x \in B$ について, $f(f^{(-1)}(x))=x$ ですから,上の 式は

$$f(f^{(-1)} (x) \cdot f^{(-1)}(y) )= x \cdot y$$

となります. 従って,

$$f^{(-1)} (f(f^{(-1)}(x) \cdot f^{(-1)}(y))) = f^{(-1)}(x \cdot y).$$

任意の $a \in A$ について, $f^{(-1)}(f(a))=a$ がいえるから,上の式は

$$f^{(-1)}(x) \cdot f^{(-1)}(y) = f^{(-1)}(x \cdot y)$$

となり,

$$f^{(-1)}(x \cdot y) =f^{(-1)}(x) \cdot f^{(-1)}(y). \quad (*)$$

同様にして,任意の $x \in B$ について, $f^{(-1)}(x) \in A$ ですから, $f$ が 準同型写像であることから,

$$f(-f^{(-1)}(x)) = -f(f^{(-1)}(x)) = -x.$$

上と同様に考えて,

$$f^{(-1)} (f(-f^{(-1)} (x))) = f^{(-1)}(-x).$$

従って,

$$f^{(-1)} (-x) = -f^{(-1)}(x)) \quad (**)$$

がいえる. (*)と(**)から, $f^{(-1)}$ もまた,準同型写像であり,全単射である から,同型写像である.

[証明終わり]