双対原理

前節では,定義3で,ブール代数($BA$ と略) ${\cal A}=<A,+, \cdot ,-,0,1>$ を定義しました.ブール代数を定義する仕方には,定義3以外の方法もあります。
代表的なものとして束論とのからみで定義することができます。
(演習4)で $BA$ についての若干の命題を証明していただきました.第節回でブール代数の異なる定義を示す前に, その準備もかねて少し演習の続きを行いましょう.その前に少し双対の原理を復習しましょう.

前節でも書きましたが,命題5から,双対の原理(duality principle)が成立します。
つまり, ${\cal A}=<A,+, \cdot ,-,0,1>$ について $BA$ で成立する文(式)は,そこに現れる全ての $+, \cdot ,0,1$ をそれぞれ, $\cdot,+,1,0$ で置き換えて作った文(式)もまたその $BA$ で成立します。
従って,その文(式)は,もとの $<A,+, \cdot ,-,0,1>$ で成立します。
この双対の原理をどんどん使ってみてください.いや使うべきです。
すばらしい原理なのですから.演習のときにも自由に使ってください. 双対の原理は,単に式だけでなく,当然その証明(文)にも当てはまります。
例えば, $x+x=x$ が証明できたとしましょう.すると,それから双対の原理を用いてすぐに $x \cdot x=x$ がいえます。
ですが,それのみならず, $x+x=x$ の証明が,

$$\begin{eqnarray*} x &=& x \cdot x+x \\ &=& x+x \cdot x \\ &=& (x+x) \cdot (x+x... ... \cdot (x+x) \\ &=& (x+x) \cdot x+(x+x) \cdot x \\ &=& x+x \\ \end{eqnarray*}$$

であったとすると, $x \cdot x=x$ の証明として,上の証明から双対の原理を用いてすぐに,

$$\begin{eqnarray*} x &=& x+x \cdot x \\ &=& x \cdot x+x \\ &=& (x \cdot x)+(x \... ...x \bigr) \cdot \bigl( (x \cdot x)+x \bigr) \\ &=& x \cdot x \\ \end{eqnarray*}$$

が得られます(括弧は少し補充しました).

ですから,お互いに双対の関係になっている式(文)は,片方の式(文)が証明できれば,双対の原理により,もう片方は自動的に成立します。

(演習5)

(注:下の $(1) \sim (4)$ で,演習4の結果は使ってよいことにします。
使わなくてもいいですが. もちろん,全てブール代数の公理を用いて証明します。 )

1. $BA$ で,$--x=x \quad$ (二重否定の法則);
   $-(x+y)=-x \cdot -y \quad$ (ド・モルガンの法則);
   $-(x \cdot y)=-x+-y \quad$ (ド・モルガンの法則)
   が成立することを,証明しなさい.
   

2. $BA$ で,次が成り立つことを証明しなさい.
   1. $x \leq x \quad$ (反射律);
   2. $(x \leq y ~and~ y \leq x) \Rightarrow x=y \quad$ (反対称律);
   3. $(x \leq y ~and~ y \leq z) \Rightarrow x \leq z \quad$ (推移律);
      

3. $BA$ で,次が成り立つことを証明しなさい.
   1. $x=-y \Leftrightarrow x+y=1 ~and~ x \cdot y=0;$
   2. $0 \leq x \leq 1;$
   3. $(x \leq z ~and~ y \leq z ) \Rightarrow x+y \leq z;$
   4. $(x \leq z ~and~ y \leq z) \Rightarrow x \cdot y \leq z;$
      $(x \leq y ~and~ x \leq z) \Rightarrow x \leq y \cdot z$
   5. $a \cdot x \leq y \Leftrightarrow x \leq -a+y.$ (結合の強さは, $-, \cdot ,+$ の順！)
      

4. $BA$ で, $-(-x+-y+z)+-(-x+y)+-x+z=1$
   が成り立つことを証明しなさい.
   

5. ${\bf N}$ を自然数全体の集合とします. $N$ を $0$ でない自然数とし,どんな素数 $P$ についても,$N$ は $P$ の2乗で割り切れないものとします(ここでは, 0は自然数の 内に含めるものとします). このとき, $An= \{ x \in {\bf N}:1 \leq x \leq N,x$ は $N$ を割り切る(つまり, $N$ は $x$ の倍数) $\}$ とおきます。
   任意の $x,y \in An$ について, $x+y$ を $x$ と $y$ の最小公倍数と定義し, $x \cdot y$ を $x$ と $y$ の最大公約数と定義します。
   また,任意の $x \in An$ について, $-x$ を$N/x$ ($N$ を $x$ で割った商)と定義します。
   このとき, 次の問いに答えなさい.
   1. 任意の $x,y \in An$ について, $x+y=y \Leftrightarrow$ ($y$ は $x$ の倍数)を証明しなさい.
   2. $1,N \in An$ であることを確認しなさい.
   3. $x+y=y$ を, $x \leq y$ と書くことにする. 任意の $x,y,z \in An$ について,
      1. $x \leq x \quad$ (反射律);
      2. $(x \leq y ~and~ y \leq x) \Rightarrow x=y \quad$ (反対称律);
      3. $(x \leq y ~and~ y \leq z) \Rightarrow x \leq z \quad$ (推移律)
      がいえることを証明しなさい.

   4. 任意の $x,y,z \in An$ について,
      $x \cdot (y+z)=x \cdot y+x \cdot z$
      $x+y \cdot z=(x+y) \cdot (x+z) \quad$ (分配律,分配法則)
      が成り立つことを証明しなさい.
   5. ${\cal A}N =(An,+, \cdot ,-,1,N )$はブール代数であることを証明しなさい. 　　
   (演習５の終わり)

さて,これ以後しばらく,ブール代数に関するいくつかの代数的概念を導入し,調べて行きましょう.

[定義7] ${\cal A}=<A,+, \cdot ,-,0,1>$ と ${\cal B} =<B,+', \cdot',-',0',1'>$ を2つのブール代数とする.${\cal A}$ と${\cal B}$ が次の条件(1),(2)を満足するとき, ${\cal A}$ は ${\cal B}$ の部分代数(subalgebra)であるという：

1. $A \subseteq B,0=0',1=1';$
2. 任意の $x,y \in A$ について, $x+y=x+'y,x \cdot y=x \cdot'y,-x=-'x.$ また,任意の $X \subseteq B$ について, $0',1' \in X$ であって, $X$ が $+', \cdot', -'$ について閉じているならば,$X$ は ${\cal B}$ の 部分宇宙(subuniverse)という.
   (定義7の終わり)

従って,もし ${\cal A}$ が ${\cal B}$ の部分代数ならば, $A$ は ${\cal B}$ の部分宇宙です。
${\cal B}$ の全ての部分宇宙は,${\cal B}$ のある部分代数の基礎集合(台集合)です。
ですから部分宇宙は, 単に部分代数からその基礎集合以外を無視したものと 考えられます。
いうまでもないことですが, $B$ は ${\cal B}$ の部分宇宙です。
次の命題は 部分宇宙に関する同値な定義を与えます。

[命題8] ${\cal A}=<A,+, \cdot ,-,0,1>$ をブール代数とし, $X \subseteq A$ とする. そのとき,次の $(1) \sim (3)$ は同値となる：

1. $X$ は ${\cal A}$ の部分宇宙である;
2. $X \ne 0$ であって, $X$ は $+,-$ について閉じている;
3. $X \ne 0$ であって,$X$ は $\cdot ,-$ について閉じている.
   (命題8の終わり)

[証明] (演習6)     [証明終わり]

次はほとんど明らかです。

[命題9] ${\cal A}=<A,+, \cdot ,-,0,1>$ をブール代数とする. $A_s$ を ${\cal A}$ の部分宇宙を 要素とする空でない集合とすると,$\cap A_s$ は, ${\cal A}$ の部分宇宙である.
(命題9の終わり)

[証明] (演習8)     [証明終わり]

ここで,命題9に出てきた集合論の記号 $\cap$ を説明します。
$\cap$は,集合 $X \ne 0$ について, $\cap X= \{ Z:$ 任意の $Y \in X$ について, $Z \in Y \}$ と定義される集合で, $X$ の積(積集合)といいます。
それでは演習で締めくくりましょう. この節は演習が多いですが ,じっくりと考えてみてください.

(演習6) 命題8を証明しなさい.(演習6の終わり)

(演習7) $\cap \{ X \}, \cap \{ X,Y \}$ はそれぞれ,今までの集合論の記号法では何になるでしょうか. もし,全体集合を $V$ として,そのなかで $X$ を考えているものとします。
このとき.$X=0$ として, 無理やり上の $\cap$ についての定義を適用すると, $\cap X$ は何になるでしょうか.(演習7の終わり)

(演習8) 命題9を証明しなさい.(演習8の終わり)

(演習9) $A$ の空でない部分集合 $X$ で, $0,1 \in X$ であり, +, $\cdot$ について閉じているが, $X$ は $A$ の部分宇宙でないというブール代数 ${\cal A}$ が存在することを証明しなさい.(演習9の終わり)