next up previous
Next: $B$3$NJ8=q$K$D$$$F(B... (PDF ե: bool.pdf)

$BJ?@.(B 13 $BG/(B 5 $B7n(B 24 $BF|(B
$B652J=q(B $BDjM}(B 2.6 $B$N>ZL@(B
$B?73c9)2JBg3X(B $B>pJsEE;R9)3X2J(B $BC]LnLP<#(B

$B652J=q(B p.62 $B$NDjM}(B 2.6 $B$N>ZL@$O$d$dIT?F@Z$G!">JN,$5$l$F$$$k$b$N$b$"$k$N$G(B $B$3$3$G$=$l$r>ZL@$7$?$b$N$r>R2p$7$F$*$/!#(B


$B8xM}(B 1 ($B%V!<%kBe?t$N8xM}(B)

$\oplus$, $\ast$ $B$H$$$&(B 2 $B9`1i;;$H(B $'$ $B$H$$$&C19`1i;;$,Dj5A$5$l$F$$$F!"(B 0,1 $B$H$$$&L>A0$N85$r4^$`=89g(B $B$ $B$,$B%V!<%kBe?t(B $B$G$"$k$H$$$&!#(B

  1. $a\oplus b=b\oplus a$, $a\ast b=b\ast a$ ($B8r49B'(B)
  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)$ ($BJ,G[B'(B)
  3. $a\oplus 0=a$, $a\ast 1=a$ ($BC10L85(B)
  4. $a\oplus a'=1$, $a\ast a'=0$


$BNc$($P!"=89g1i;;$O(B $\oplus = \cup$, $\ast = \cap$, $A'=\bar{A}$, $0=\empty$, $1=U$ $B$K4X$7$F%V!<%kBe?t$H$J$k!#(B

$BG$0U$N%V!<%kBe?t$KBP$7$F
$BDjM}(B 2 ($B652J=q(B $BDjM}(B 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$ ($B5[<}B'(B)
  4. $(a\oplus b)\oplus c=a\oplus (b\oplus c)$, $(a\ast b)\ast c=a\ast (b\ast c)$ ($B7k9gB'(B)
  5. $0'=1$, $1'=0$
  6. $(a\oplus b)'=a'\ast b'$, $(a\ast b)' = a'\oplus b'$ ($B%I(B$\cdot$$B%b%k%,%s$NK!B'(B)


$B>ZL@(B

($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$ $B$NJ}$OAPBP!"$D$^$j(B $\oplus$ $B$H(B $\ast$, 0 $B$H(B 1 $B$rF~$l49$($F(B $B>e$HF1MM$K9T$($P$h$$!#0J2<$NL?Bj$K$D$$$F$bF1MM!#(B

($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$) $B:8JU(B = $L$ $B$H$9$k!#(B

\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}

$B$3$3$G!"(B

\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*}



$B$h$j!"(B

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

$B$f$($K(B

\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$) $B$G(B $a=0$ $B$H$9$k$H(B $0\oplus 0'=1$ $B$G!"(B($B_3$) $B$h$j(B $0\oplus 0'=0'$

($T_6$) $B$3$l$r<($9A0$K!"$^$: ($T_7$) $x\oplus a=1$ $B$+$D(B $x\ast a = 0$ $B$J$i$P(B $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*}



$B$3$l$rMQ$$$k$H!"(B$R=a'\ast b'$ $B$KBP$7$F(B
$R\oplus(a\oplus b)=1$ $B$+$D(B $R\ast (a\oplus b)=0$
$B$r<($;$P$h$$$3$H$K$J$k!#(B

\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*}




$B$3$N>ZL@Cf$G$b;H$C$?$b$N$b4^$`$,!"
$BDjM}(B 3

  1. $x\oplus a=1$ $B$+$D(B $x\ast a = 0$ $B$J$i$P(B $x=a'$
  2. $a\oplus b = 0$ $B$J$i$P(B $a=b=0$, $a\ast b = 1$ $B$J$i$P(B $a=b=1$


$B>ZL@(B

($T_7$) $B$OA0>ZL@Cf$K<($7$?$N$G!"(B($T_8$) $B$NA0H>$N$_<($9(B ($B8eH>$OAPBP(B)$B!#(B

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

$b$ $B$bF1MM!#(B





next up previous
Next: $B$3$NJ8=q$K$D$$$F(B...
Shigeharu TAKENO
2001$BG/(B 8$B7n(B 9$BF|(B