next up previous
: 双対原理についての補足 : ブール代数の基礎 : 補足:命題論理・ブール代数・集合論の対応について

双対原理

前節では,定義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 ) $はブール代数であることを証明しなさい.   
    (演習5の終わり)

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

[定義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の終わり)


next up previous
: 双対原理についての補足 : ブール代数の基礎 : 補足:命題論理・ブール代数・集合論の対応について
Yasunari SHIDAMA