演習４

1. 系4を証明しなさい.

   『系4 もし, $A_s$ が集合の体ならば, $(A_s,\cup ,\cap ,\sim,0,\cup A_s)$ は $BA$ 』

   [証明]

   集合の体の定義と集合演算の規則によります。集合演算の規則は前節の演習でやったので全て既知とします.

   1. $A_s \ne 0. \cup A_s \in A.$ また, $X, Y \in A$ なら
      
      $$X \cup Y \in A,X \cap Y \in A,\cup A_s \sim X \in A$$
      
      
      すなわち $\cup , \cap , \sim$ について閉じている.

   2. $X,Y,Z \in A$ を任意にとると,
      1. $X \cup Y =Y \cup X,X \cap Y=Y \cap X$ (交換律,交換法則)
      2. $X \cup (Y \cup Z)=(X \cup Y) \cup Z,$
         $X \cap (Y \cap Z)=(X \cap Y) \cap Z$ (結合律,結合法則)
      3. $X \cap Y \cup Y=Y,(X \cup Y) \cap Y=Y$ (吸収律,吸収法則)
      4. $X \cap (Y \cup Z)=(X \cap Y) \cup (X \cap Z)$
         $X \cup (Y \cap Z) =(X \cup Y) \cap (X \cup Z)$ (分配律,分配法則)
      5. $X \cap (UA \sim X)=0,$
         $X \cup (UA \sim X)=UA$ (補元律,補元法則,相補法則)

   [証明終]

2. 命題5を証明しなさい.
   もし, ${\cal A}=<A,+, \cdot ,-,0,1>$ が $BA$ ならば, $<A, \cdot ,+,-,1,0>$ もそうである.

   [証明]

   $BA$ の定義から自明. ただし、(2)(i) $\sim$ (v)の各式については,第1式と第2式の順序を逆にする.
   

   [証明終]

3. $BA$ で, $x+x=x,x \cdot x=x$ (べき等律),
   $x \cdot 0=0,x \cdot 1=x,$
   $x+0=x,x+1=1$

   [証明]

   $$\begin{eqnarray*} x+x &=& x+x \cdot (x+y) \quad 吸収律第2式 \\ &=& x \quad 吸収律第1式 \end{eqnarray*}$$

   
   

   
   

   
   

   $$\begin{eqnarray*} x \cdot x &=& x \cdot (x+x \cdot (x \cdot y)) \quad 吸収律第1式 \\ &=& x \quad 吸収律第2式 \end{eqnarray*}$$

   
   

   
   

   
   

   $$\begin{eqnarray*} x \cdot 0 &=& x \cdot (x \cdot -x) \quad 補元律第1式 \\ &=&... ...\qquad べき等律 \quad x \cdot x=x \\ &=& 0 \quad 補元律第1式 \end{eqnarray*}$$

   
   

   
   

   
   

   $$\begin{eqnarray*} x \cdot 1 &=& x \cdot (x+-x) \quad 補元律第2式 \\ &=& x \cd... ... \qquad べき等律 \quad x \cdot x=x \\ &=& x \quad 吸収律第2式 \end{eqnarray*}$$

   
   

   
   

   
   

   $$\begin{eqnarray*} x+0 &=& x+x \cdot -x \quad 補元律第1式 \\ &=& x \quad 吸収律第2式 \end{eqnarray*}$$

   
   

   
   

   
   

   $$\begin{eqnarray*} x+1 &=& x+(x+-x) \quad 補元律第1式 \\ &=& (x+x)+-x \quad 結... ...-x \qquad べき等律 \quad x+x=x \\ &=& 1 \quad 補元律第1式 \\ \end{eqnarray*}$$

   
   

   
   

   
   

   [証明終]
4. ブール代数において,補元が一意的であることを証明しなさい.
   
   $$(x \cdot y=0 ~and~ x+y=1) \Rightarrow y=-x$$
   
   

   [証明]

   $x \cdot y=0 ~and~ x+y=1$ を仮定すると

   $$\begin{eqnarray*} -x &=& -x \cdot 1 \qquad 問題(3) \\ &=& -x \cdot (x+y) \qqu... ...-x+y \cdot -x \qquad 交換律 \\ &=& 0+y \cdot -x \qquad 補元律 \end{eqnarray*}$$

   
   

   
   

   
   

   $$\begin{eqnarray*} y &=& y \cdot 1 \qquad 問題(3) \\ &=& y \cdot (x+-x) \qquad... ...+y \cdot -x \qquad 交換律 \\ &=& 0+y \cdot -x \qquad 仮定から \end{eqnarray*}$$

   
   

   
   

   
   

   よって $y=-x$
   (証明終)
   

5. ブール代数において, 0と1の働きをする要素はそれぞれ1つしかないことを証 明しなさい.

   [証明]

   まず. $A$ は空でないので $x \in A$ が少なくとも一つ存在する. ここで0と1の働きをする要素0'と1'が在ったとしても 補元律より
   

   $$0'=x \cdot -x=0$$

   
   

   
   

   $$1'=x+-x=1$$

   
   

   [証明終]
   

6. $BA$ で,次が成り立つことを証明しなさい.
   1. $x \le y \Leftrightarrow x \cdot y=x;$
   2. $x \le y \Leftrightarrow x \cdot -y=0.$

      [証明]

      1. $x \le y$ のとき $x+y=y$ で,
         $$\begin{eqnarray*} x \cdot y &=& x \cdot (x+y) \\ &=& x \cdot x+x \cdot y \qqu... ...\\ &=& x+x \cdot y \qquad 冪等律 \\ &=& x \qquad 吸収律 \\ \end{eqnarray*}$$
         
         
         
         
         
         
         逆に、 $x \cdot y=x$ のとき
         $$\begin{eqnarray*} x+y &=& x \cdot y+y \qquad 仮定 \\ &=& y \qquad 吸収律 \end{eqnarray*}$$
         
         
         
         
         
         
         よって定義から
         
         $$x \le y$$
         
         
         
         

      2. $x \le y$ のとき $x+y=y$ で,　
         $$\begin{eqnarray*} x \cdot -y &=& x \cdot -(x+y) \\ &=& x \cdot (-x \cdot -y) ... ... 0 \cdot -y \qquad 結合律、補元律 \\ &=& 0 \qquad 問題(3) \\ \end{eqnarray*}$$
         
         
         
         
         
         
         逆に, $x \cdot -y=0$ のとき,ドモルガン則と $-0=1$ から
         $$\begin{eqnarray*} -x+y &=& 1 \\ x+y &=& x \cdot 1+y \qquad 問題(3) \\ &=& x... ...律 \\ &=& x \cdot y+y \qquad 問題(3) \\ &=& y \qquad 吸収律 \end{eqnarray*}$$
         
         
         
         
         
         
         よって定義から $x \le y$

      [証明終]

      *(6)で使ったドモルガン則
      

      $$-(x+y) = -x \cdot -y$$
      
      
      
      
      $$-(x \cdot y)=-x+-y$$
      
      
      の証明は
      $$\begin{eqnarray*} (x+y)+(-x \cdot -y) &=& (x+y+-x)\cdot(x+y+-y) \qquad 分配律... ...砧\\ &=& 1 \cdot 1 \qquad 問題(3) \\ &=& 1 \qquad 問題(3) \end{eqnarray*}$$
      
      
      
      
      
      
      $$\begin{eqnarray*} (x+y) \cdot (-x \cdot -y) &=& x \cdot (-x \cdot -y)+y \cdot... ...∧筝砧А\\ &=& 0+0 \qquad 問題(3) \\ &=& 0 \qquad 問題(3) \end{eqnarray*}$$
      
      
      
      
      
      

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

      $$-(x+y) = -x \cdot -y$$
      
      
      第2式も同様にできる.

      [証明終]
      

      * -0=1については

      $$\begin{eqnarray*} && 0+1=1 \\ && 0 \cdot 1=0 \\ \end{eqnarray*}$$
      
      
      
      
      
      
      と補元の一意性による.
      全く同様に $\quad$ -1=0