演習５

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

[証明]

はの補元だから定義により

$\begin{eqnarray*} && x \cdot -x=0 \\ && x+-x=1 \quad *1 \\ \end{eqnarray*}$

はの補元だから定義により

$\begin{displaymath}-x \cdot --x=0 \end{displaymath}$

$\begin{displaymath}-x+--x=1 \end{displaymath}$

交換律により

$\begin{displaymath}--x \cdot -x=0 \end{displaymath}$

$\begin{displaymath}--x+-x=1 \quad *2 \end{displaymath}$

2組の式*1,*2により補元の一意性から

$\begin{eqnarray*} (x+y)+(-x \cdot -y) &=& (x+y+-x) \cdot (x+y+-y) \quad 分配.. ...交換律,補元律 \\ &=& 1 \cdot 1 \quad 演習4問題(3) \\ &=& 1 \end{eqnarray*}$

$\begin{eqnarray*} \lefteqn{(x+y) \cdot (-x \cdot -y)} \\ &=& x \cdot (-x \cdo... ..., \\ &=& 0+0 \quad 演習4問題(3) \\ &=& 0 \quad 演習4問題(3) \end{eqnarray*}$

よって,既に証明した補元の一意性から

$\begin{displaymath}-(x+y) = -x \cdot -y \end{displaymath}$

以後,公理,演習4の結果,は断り無く使います.双対の原理によれば

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

$\begin{eqnarray*} (x \cdot y)+(-x+-y) &=& (x+(-x+-y)) \cdot (y+(-x+-y)) \\ &=& 1+-y+-x+1 \\ &=& 1+1 \\ &=& 1 \end{eqnarray*}$

よって,補元の一意性から

$\begin{displaymath}-(x \cdot y)=-x+-y \end{displaymath}$

[証明終]
で,次が成り立つことを証明しなさい.
1. $x \le x \quad$ (反射律);
2. $(x \le y ~and~ y \le x) \Rightarrow x=y \quad$ (反対称律);
3. $(x \le y ~and~ y \le z) \Rightarrow x \le z \quad$ (推移律);
[証明]
1. から定義により $x \le x$
2. $(x \le y ~and~ y \le x)$
  
  $\begin{eqnarray*} & \Rightarrow & (x+y=y ~and~ y+x=x) \quad 定義 \\ & \Rightarrow & x=y+x=x+y=y \\ & \Rightarrow & x \le x \quad 定義 \end{eqnarray*}$
3. $(x \le y ~and~ y \le z)$
  
  $\begin{eqnarray*} & \Rightarrow & (x+y=y ~and~ y+z=z) \quad 定義 \\ & \Righta... ...=x+(y+z)=(x+y)+z=y+z=z \\ & \Rightarrow & x \le z \quad 定義 \end{eqnarray*}$
[証明終]
で,次が成り立つことを証明しなさい.
1. $x=-y \Leftrightarrow x+y=1 ~and~ x \cdot y=0;$
2. $0 \le x \le 1;$
3. $(x \le z ~and~ y \le z) \Rightarrow x+y \le z;$
4. $(x \le z ~and~ y \le z) \Rightarrow x \cdot y \le z;$
5. $a \cdot x \le y \Leftrightarrow x \le -a+y. (結合の強さは, -,\cdot,+ の順！)$
[証明]
1. $x=-y \Leftrightarrow x+y=1 ~and~ x \cdot y=0$ ならば,補元の一意存在のことですから
  
  $\begin{displaymath}x=-y \Rightarrow x+y=-y+y=1 ~and~ x \cdot y=-y \cdot y=0 \end{displaymath}$
  
  逆に $x+y=1 ~and~ x \cdot y=0$ は以下のように演習3で証明済みです.
  例えば
  
  $\begin{eqnarray*} -x &=& -x \cdot 1 \\ &=& -x \cdot (x+y) \\ &=& -x \cdot x+-x \cdot y \\ &=& x \cdot -x+y \cdot -x \\ &=& 0+y \cdot -x \end{eqnarray*}$
  
  $\begin{eqnarray*} y &=& y \cdot 1 \\ &=& y \cdot (x+-x) \\ &=& y \cdot x+y \cdot -x \\ &=& x \cdot y+y \cdot -x \\ &=& 0+y \cdot -x \end{eqnarray*}$
  
  よって
  
  $\begin{displaymath}y=-x \end{displaymath}$
  
  　　
2. から定義により $0 \le x$
  から定義により $x \le 1$
3. $(x \le z ~and~ y \le z)$
  
  $\begin{eqnarray*} & \Rightarrow & x+z=z ~and~ y+z=z \quad 定義 \\ & \Rightarr... ...+z=(x+z)+y=z+y=y+z=z \\ & \Rightarrow & x+y \le z \quad 定義 \end{eqnarray*}$
4. (d-1)
  
  $(x \le z ~and~ y \le z) \Rightarrow x \cdot y \le z$
  
  $\begin{eqnarray*} (x \le z ~and~ y \le z) & \Rightarrow & x \cdot z=x ~and~ y ... ... z) \cdot y=x \cdot y \\ & \Rightarrow & x \cdot y \le z 定義 \end{eqnarray*}$
  
  (d-2)
  
  $(x \le y ~and~ x \le z) \Rightarrow x \le y \cdot z;$
  
  $\begin{displaymath}x \le y ~and~ x \le z \Leftrightarrow x \cdot y=x ~and~ x \cdot z=x :演習4(6) \end{displaymath}$
  
  であることから,
  
  $\begin{eqnarray*} x \cdot (y \cdot z) &=& (x \cdot y) \cdot z :結合律 \\ &=& x \cdot z \\ &=& x \end{eqnarray*}$
  
  $x \cdot (y \cdot z)=x \Leftrightarrow x \le y \cdot z :演習4(6)$
  
  [証明終わり]
5. $a \cdot x \le y \Leftrightarrow x \le -a+y$
  [証明]
  $a \cdot x \le y$ なら定義により $a \cdot x+y=y$ で
  
  $\begin{eqnarray*} x+-a+y &=& x \cdot (-a+a)+-a+y \\ &=& x \cdot -a+x \cdot a+-a+y \\ &=& (x \cdot -a+-a)+(x \cdot a+y) \\ &=& -a+y \end{eqnarray*}$
  
  よって
  
  $\begin{displaymath}x \le -a+y \end{displaymath}$
  
  逆に $x \le -a+y$ なら定義により $x \cdot (-a+y)=x$ で
  
  $\begin{eqnarray*} a \cdot x+y &=& a \cdot x \cdot (-a+y)+y \\ &=& a \cdot x \... ...a+a \cdot x \cdot y+y \\ &=& 0+a \cdot x \cdot y+y \\ &=& y \end{eqnarray*}$
  
  よって
  
  $\begin{displaymath}a \cdot x \le y \end{displaymath}$
［証明終］
$\begin{eqnarray*} \lefteqn{-(-x+-y+z)+-(-x+y)+-x+z} \\ &=& x \cdot y \cdot -z... ...cdot (y+-y)+-x+z 分配則 \\ &=& x+-x+z \\ &=& 1+z \\ &=& 1 \end{eqnarray*}$

上で用いたド・モルガン則の一般化

$\begin{displaymath}-(x_1+x_2+ \cdots +x_n)=-x_1 \cdot -x_2 \cdot \: \cdots \: \cdot -x_n \end{displaymath}$

$\begin{displaymath}-(x_1 \cdot x_2 \cdot \: \cdots \: \cdot x_n)=-x_1+-x_2+ \cdots +-x_n \end{displaymath}$

につては

[証明]

数学的帰納法を使うとについては成立.(既に証明済み)
$n \le k$ について成立つと仮定して

$\begin{eqnarray*} \lefteqn{(x_1+x_2+ \cdots +xk+x_{k+1})} \\ &=& -((x_1+x_2+ ... ...x_1 \cdot -x_2 \cdot \: \cdots \: \cdot -x_k \cdot -x_{k+1} \\ \end{eqnarray*}$

よっての場合も成立.
また双対原理により

$\begin{displaymath}-(x_1 \cdot x_2 \cdot \: \cdots \: \cdot x_n)=-x_1+-x_2+ \cdots +-x_n \end{displaymath}$

[証明終]
${\bf N}$ を自然数全体の集合とします. をでない自然数とし, どんな素数についても, はの2乗で割り切れないものとします (ここでは, は自然数の内に含めるものとします). このとき,

$\begin{displaymath} A_n = \{ x \in {\bf N}:1 \le x \le N ,x は N を割り切る \mbox{ } (つまり，N は x の倍数) \} \end{displaymath}$

とおきます. 任意の $x,y \in A_n$ について, をとの最小公倍数と定義し, $x \cdot y$ をとの最大公約数と定義します.また,任意の $x \in A_n$ について, ををで割った商)と定義します. このとき,次の問いに答えなさい.
1. 任意の $x,y \in A_n$ について, $x+y=y \Leftrightarrow (yはxの倍数)$ を証明しなさい.
  
  [証明]
  
  の最小公倍数をで表すことにすると
  
  $\begin{eqnarray*} x+y=y & \Leftrightarrow & L(x,y)=y 定義から \\ & \Leftright... ...sts k \in {\bf N})(kx=y) \\ & \Leftrightarrow & (yはxの倍数) \end{eqnarray*}$
  
  [証明終]
2. $1,N \in A_n$ であることを確認しなさい.
  
  [証明]
  
  $1/1=1,1 \le 1 \le N$ ゆえ $1 \in A_n$
  $N/N=1,1 \le N \le N$ ゆえ $N \in A_n$
  [証明終]
3. を, $x \le y$ と書くことにする. 任意の $x,y,z \in A_n$ について
  1. $x \le x$ (反射律);
  2. $(x \le y ~and~ y \le x) \Rightarrow x=y$ (反対称律);
  3. $(x \le y ~and~ y \le z) \Rightarrow x \le z$ (推移律)
  [証明]
  の最小公倍数をで表すことにすると
  1. ゆえ
    
    $\begin{displaymath}x+x=x \end{displaymath}$
    
    よって
    
    $\begin{displaymath}x \le x \end{displaymath}$
  2. $(x \le y ~and~ y \le x)$ とすると
    
    $\begin{displaymath}L(x,y)=y ~and~ L(y,x)=x \end{displaymath}$
    
    $\begin{displaymath}(\exists k \in {\bf N})(kx=y) ~and~ (\exists l \in {\bf N})(ly=x) \end{displaymath}$
    
    ここで
    
    $\begin{displaymath}(\exists k \in {\bf N})(kx=y) となる k \end{displaymath}$
    
    $\begin{displaymath}(\exists l \in {\bf N})(ly=x) となる l \end{displaymath}$
    
    を選ぶと, からよって
    
    $\begin{displaymath}l=k=1 \end{displaymath}$
    
    　　　よって
    
    $\begin{displaymath}y=x \end{displaymath}$
  3. $(x \le y ~and~ y \le z)$ とすると
    
    $\begin{displaymath}L(x,y)=y ~and~ L(y,z)=z \end{displaymath}$
    
    $\begin{displaymath}(\exists k \in {\bf N})(kx=y) ~and~ (\exists l \in {\bf N})(ly=z) \end{displaymath}$
    
    　　　ここで
    
    $\begin{displaymath}(\exists k \in {\bf N})(kx=y) となる k \end{displaymath}$
    
    $\begin{displaymath}(\exists l \in {\bf N})(ly=z) となる l \end{displaymath}$
    
    を選ぶとよって
    
    $\begin{displaymath}L(x,z)=z \end{displaymath}$
    
    ゆえに
    
    $\begin{displaymath}x \le z \end{displaymath}$
  [証明終]
4. 任意の $x,y,z \in A_n$ について,
  
  $\begin{eqnarray*} && x \cdot (y+z)=x \cdot y+x \cdot z \\ && x+y \cdot z=(x+y) \cdot (x+z) (分配律,分配法則) \end{eqnarray*}$
  
  [証明]
  
  の最小公倍数をで,最大公約数とで表すことにすると
  
  $\begin{eqnarray*} x \cdot (y+z) &=& G(x,L(y,z)) 定義 \\ &=& L(G(x,y),G(x,z)) 自然数の性質 \\ &=& x \cdot y+x \cdot z 定義 \end{eqnarray*}$
  
  $\begin{eqnarray*} x+y \cdot z &=& L(x,G(y,z)) 定義 \\ &=& G(L(x,y),L(x \cdot z)) 自然数の性質 \\ &=& (x+y) \cdot (x+z) 定義 \end{eqnarray*}$
  
  [証明終]
5. $A_gN =(A_n,+, \cdot,-,1,N)$ はブール代数であることを証明しなさい.
  
  [証明]
  
  $A_n= \{ x \in {\bf N}:1 \le x \le N,x$ はを割り切る (つまり, はの倍数) $\}$
  の最小公倍数をで,最大公約数とで表すことにする.
  
  (1)
  
  (b)から $1,N \in A_n$ では空でない集合である. $x,y \in A_n$ について $x+y=L(x,y),x \cdot y=G(x,y)$ とすると
  $x,y \in A_n$ から
  
  $\begin{displaymath}x,y\geq 1, (\exists k \in {\bf N})(N=kx),(\exists l \in {\bf N})(N=ly) \end{displaymath}$
  
  このようなを選べばすなわち, はの公倍数. よって最小公倍数はを割り切る.
  また $x,y \geq 1$ から
  
  $\begin{displaymath}L(x,y) \geq 1 \end{displaymath}$
  
  よって
  
  $\begin{displaymath}x+y=L(x,y) \in A_n \end{displaymath}$
  
  はを割り切り, はを割り切るからは従ってを割り切る. また $x,y \geq 1$ から $G(x,y) \geq 1$ よって
  
  $\begin{displaymath}x \cdot y \in A_n \end{displaymath}$
  
  $x \in A_n$ なら $x \geq 1,(\exists k \in {\bf N})(N=kx)$ でそのようなをとれば $-x = k \geq 1$ で,
  
  $\begin{displaymath}-x=k \in {\bf N} \end{displaymath}$
  
  よっては $+,\cdot,-$ について閉じている;
  
  (2)
  
  任意の $x,y,z \in A$ について：
  
  (暙)
  
  $\begin{displaymath}x+y=L(x,y)=L(y,x)=y+x \end{displaymath}$
  
  $\begin{displaymath}x \cdot y=G(x,y)=G(y,x)=y \cdot x \end{displaymath}$
  
  (暠)
  
  $\begin{displaymath}x+(y+z)=L(x,L(y,z))=L(L(x,y),z)=(x+y)+z \end{displaymath}$
  
  $\begin{displaymath}x \cdot (y \cdot z)=G(x,G(y,z)) =G(G(x,y),z)=(x \cdot y) \cdot z \end{displaymath}$
  
  (暲)
  
  $\begin{displaymath}x \cdot y+y=L(G(x,y),y)=y \end{displaymath}$
  
  $\begin{displaymath}(x+y) \cdot y=G(L(x,y),y)=y \end{displaymath}$
  
  (暿)
  
  (d)より
  
  $\begin{displaymath}x \cdot (y+z)=x \cdot y+x \cdot z, \end{displaymath}$
  
  $\begin{displaymath}x+y \cdot z=(x+y) \cdot (x+z) \end{displaymath}$
  
  (曺)
  
  どんな素数についても, はの2乗で割り切れないから
  
  $\begin{displaymath}x \cdot -x=G(x,N/x)=1 自然数の性質 \end{displaymath}$
  
  また,
  
  $\begin{displaymath}L(x,N/x)=N \end{displaymath}$
  
  [証明終]

[LCM,GCMについての補足]

の最大公約数,最小公倍数をで表します.

しかし,きりが無いので「素因数分解の一意性」は使うことにします.
で素数全体の集合を表すとします.
写像 $\tau : x \in {\bf N}- \{ 0 \} \rightarrow \tau (x) \in P ((P_m \cup \{ 1 \} ) \times {\bf N})$ を次のように定義します.
$x \in {\bf N}, \ne 0,1$ とするとき「素因数分解の一意性」から

$\begin{displaymath}(\exists ! n \in {\bf N})( \exists !(p_1,p_2, \cdots ,p_n) \in {P_m}^n )\end{displaymath}$

$\begin{displaymath}(\exists ! (l_1,l_2, \cdots ,l_n) \in {N_b}^n) \end{displaymath}$

$\begin{displaymath}(x={p_1}^{l_1} \cdot {p_2}^{l_2} \cdot \: \cdots \: \cdot {p_n}^{l_n}) \end{displaymath}$

のときは

として

$\begin{displaymath}\tau(x)= \{ (1,1) \} \cup (\cup \{ \{ \{ (p_k,i) \} \vert i=1, \cdots ,l_k \} \vert k=1, \cdots ,n \} \end{displaymath}$

例: なら $x=1^1 \cdot 2^3 \cdot 3$ で

$\begin{displaymath}\tau(x)= \{ (1,1),(2,1),(2,2),(2,3),(3,1) \} \end{displaymath}$

このとき $\tau$ の作り方から $\tau(x)= \tau(y)$ なら (すなわち単射)
また,

$\begin{displaymath}\tau (G(x,y))= \tau(x) \cap \tau(y) \end{displaymath}$

$\begin{displaymath}\tau (L(x,y))= \tau(x) \cup \tau(y) \end{displaymath}$

です.

以下, $x,y,z \ne 0$ とします.

$\begin{eqnarray*} \tau (G(x,y)) &=& \tau (x) \cap \tau (y) \\ &=& \tau (y) \cap \tau (x) \\ &=& \tau (G(y,x)) \end{eqnarray*}$

$\tau$ は単射だから

$<交換則:x \cdot x=y \cdot x>$

$\begin{eqnarray*} \tau(L(x,y)) &=& \tau(x) \cup \tau(y) \\ &=& \tau(y) \cup \tau(x) \\ &=& \tau (L(y,x)) \end{eqnarray*}$

$\tau$ は単射だから

$\begin{eqnarray*} \tau(G(G(x,y),z)) &=& \tau(G(x,y)) \cap \tau(z) \\ &=& (\ta... ... \\ &=& \tau(x) \cap \tau(G(y,z)) \\ &=& \tau (G(x,G(y,z))) \end{eqnarray*}$

$\tau$ は単射だから

全く同様に

$<結合則:(x \cdot y) \cdot z=x \cdot (y \cdot z)>$

$\begin{eqnarray*} \tau(L(L(x,y),z)) &=& \tau(L(x,y)) \cup \tau(z) \\ &=& (\ta... ...) \\ &=& \tau(x) \cup \tau(L(y,z)) \\ &=& \tau(L(x,L(y,z))) \end{eqnarray*}$

$\tau$ は単射だから

$<吸収律:x \cdot y+y=y >$

$\begin{eqnarray*} \tau(G(L(x,y),y)) &=& \tau(L(x,y)) \cup \tau(y) \\ &=& (\tau(x) \cap \tau(y)) \cup \tau(y) \\ &=& \tau(y) \end{eqnarray*}$

$\tau$ は単射だから

$<吸収律:(x+y) \cdot y=y >$

$\begin{eqnarray*} \tau(L(G(x,y),y)) &=& \tau(G(x,y)) \cap \tau(y) \\ &=& (\tau(x) \cup(y)) \cap \tau(y) \\ &=& \tau(y) \end{eqnarray*}$

$\tau$ は単射だから

$<分配律:(x \cdot y)+z=(x+z) \cdot (y+z)>$

$\begin{eqnarray*} \tau(G(L(x,y),z)) &=& \tau(L(x,y)) \cap \tau(z) \\ &=& (\ta... ... \tau(G(x,z)) \cup \tau(G(y,z)) \\ &=& \tau(L(G(x,z),G(y,z))) \end{eqnarray*}$

$\tau$ は単射だから

$<分配律:(x+y) \cdot z=(x \cdot z)+(y \cdot z)>$

$\begin{eqnarray*} \tau(L(G(x,y),z)) &=& \tau(G(x,y)) \cup \tau(z) \\ &=& (\ta... ... \tau(L(x,z)) \cap \tau(L(y,z)) \\ &=& \tau(G(L(x,z),L(y,z))) \end{eqnarray*}$

$\tau$ は単射だから

をどんな素数についても, の2乗で割り切れない数とすると $N=1 \cdot p_1 \cdot \: \cdots \: \cdot p_n$ の形をしているので, がを割りきるとするとは1と, $p_1, \cdots ,p_n$ から幾つか選ばれた素数の積では1とに使われた $p_1, \cdots ,p_n$ の残りの素数の積で

$\begin{displaymath}\tau(G(x,N/x)) = \{ (1,1) \}= \tau(1) \end{displaymath}$

$\tau$ は単射だから

また

$\begin{displaymath}\tau(L(x,N/x))= \tau(N) \end{displaymath}$

$\tau$ は単射だから

: 演習の解答 : ブール代数の基礎 : 演習４

Yasunari SHIDAMA