next up previous
Next: この文書について... (PDF ��������: bool.pdf)

平成 13 年 5 月 24 日
教科書 定理 2.6 の証明
新潟工科大学 情報電子工学科 竹野茂治

教科書 p.62 の定理 2.6 の証明はやや不親切で、省略されているものもあるので ここでそれを証明したものを紹介しておく。


公理 1 (ブール代数の公理)

$\oplus$, $\ast$ という 2 項演算と $'$ という単項演算が定義されていて、 0,1 という名前の元を含む集合 $B$ が次を満たすとき、 それを ブール代数 であるという。

  1. $a\oplus b=b\oplus a$, $a\ast b=b\ast a$ (交換則)
  2. $a\oplus (b\ast c)=(a\oplus b)\ast (a\oplus c)$, $a\ast (b\oplus c)=(a\ast b)\oplus (a\ast c)$ (分配則)
  3. $a\oplus 0=a$, $a\ast 1=a$ (単位元)
  4. $a\oplus a'=1$, $a\ast a'=0$


例えば、集合演算は $\oplus = \cup$, $\ast = \cap$, $A'=\bar{A}$, $0=\empty$, $1=U$ に関してブール代数となる。

任意のブール代数に対して次が成り立つ。


定理 2 (教科書 定理 2.6)

  1. $a\oplus a=a$, $a\ast a=a$
  2. $a\oplus 1 = 1$, $a\ast 0=0$
  3. $a\oplus (a\ast b)=a$, $a\ast (a\oplus b)=a$ (吸収則)
  4. $(a\oplus b)\oplus c=a\oplus (b\oplus c)$, $(a\ast b)\ast c=a\ast (b\ast c)$ (結合則)
  5. $0'=1$, $1'=0$
  6. $(a\oplus b)'=a'\ast b'$, $(a\ast b)' = a'\oplus b'$ (ド$\cdot$モルガンの法則)


証明

($T_1$) $a$ $\stackrel{(B_3)}{\ \ =\ \ }a\oplus 0$ $\stackrel{(B_4)}{\ \ =\ \ }a\oplus (a\ast a')$ $\stackrel{(B_2)}{\ \ =\ \ }(a\oplus a)\ast(a\oplus a')$ $\stackrel{(B_4)}{\ \ =\ \ }(a\oplus a)\ast 1$ $\stackrel{(B_3)}{\ \ =\ \ }a\oplus a$

$\ast$ の方は双対、つまり $\oplus$ と $\ast$, 0 と 1 を入れ換えて 上と同様に行えばよい。以下の命題についても同様。

($T_2$) 1 $\stackrel{(B_4)}{\ \ =\ \ }a\oplus a'$ $\stackrel{(B_3)}{\ \ =\ \ }a\oplus(a'\ast 1)$ $\stackrel{(B_2)}{\ \ =\ \ }(a\oplus a')\ast(a\oplus 1)$ $\stackrel{(B_4)}{\ \ =\ \ }1\ast(a\oplus 1)$ $\stackrel{(B_3)}{\ \ =\ \ }a\oplus 1$

($T_3$) $a\oplus(a\ast b)$ $\stackrel{(B_3)}{\ \ =\ \ }(a\ast 1)\oplus(a\ast b)$ $\stackrel{(B_2)}{\ \ =\ \ }a\ast(1\oplus b)$ $\stackrel{(T_2)}{\ \ =\ \ }a\ast 1$ $\stackrel{(B_3)}{\ \ =\ \ }a$

($T_4$) 左辺 = $L$ とする。

\begin{displaymath} L \mbox{$\stackrel{(B_3)}{\ \ =\ \ }L\ast 1$} \mbox{$\sta... ...\mbox{$\stackrel{(B_2)}{\ \ =\ \ }(L\ast a)\oplus(L\ast a')$} \end{displaymath}

ここで、

\begin{eqnarray*}&& L\ast a \mbox{$\stackrel{}{\ \ =\ \ }\{(a\oplus b)\oplus c... ...us(b\ast a')$} \mbox{$\stackrel{(B_3)}{\ \ =\ \ }b\ast a'$}\\ \end{eqnarray*}



より、

\begin{displaymath} L\ast a' =(b\ast a')\oplus (c\ast a') = (b\oplus c)\ast a' \end{displaymath}

ゆえに

\begin{eqnarray*} L & = & (L\ast a)\oplus (L\ast a') \\ & = & a\oplus\{(b\opl... ...us c)\}\ast 1$} \\ & \stackrel{(B_3)}{=} & a\oplus(b\oplus c) \end{eqnarray*}



($T_5$) ($B_4$) で $a=0$ とすると $0\oplus 0'=1$ で、($B_3$) より $0\oplus 0'=0'$

($T_6$) これを示す前に、まず次を示す。

($T_7$) $x\oplus a=1$ かつ $x\ast a = 0$ ならば $x=a'$

\begin{eqnarray*}x & \stackrel{(B_3)}{=} & 1\ast x \mbox{$\stackrel{(B_4)}{\... ...}{\ \ =\ \ }a'\ast(a'\oplus x)$}\\ & \stackrel{(T_3)}{=} & a' \end{eqnarray*}



これを用いると、$R=a'\ast b'$ に対して
$R\oplus(a\oplus b)=1$ かつ $R\ast (a\oplus b)=0$
を示せばよいことになる。

\begin{eqnarray*}R\oplus(a\oplus b) & = & (a'\ast b')\oplus(a\oplus b) \mbox... ..._4)}{\ \ =\ \ }a\ast 0$} \mbox{$\stackrel{(T_2)}{\ \ =\ \ }0$} \end{eqnarray*}




この証明中でも使ったものも含むが、次が成り立つこともいえる。


定理 3

  1. $x\oplus a=1$ かつ $x\ast a = 0$ ならば $x=a'$
  2. $a\oplus b = 0$ ならば $a=b=0$, $a\ast b = 1$ ならば $a=b=1$


証明

($T_7$) は前証明中に示したので、($T_8$) の前半のみ示す (後半は双対)。

\begin{displaymath} a\mbox{$\stackrel{(T_3)}{\ \ =\ \ }a\ast(a\oplus b)$} = a\ast 0 \mbox{$\stackrel{(T_2)}{\ \ =\ \ }0$} \end{displaymath}

$b$ も同様。



next up previous
Next: この文書について...
Shigeharu TAKENO
2001年 8月 9日