Podręcznik

W 2 elementowej algebrze Boole’a definiujemy kilka dodatkowych użytecznych w praktyce działań. Zaczniemy od sumy modulo 2 (suma modulo 2 jest szczególnym przypadkiem sumy modulo $m$ wprowadzanej w zbiorze $Z_m=\{0,1,...,m-1\}$). Sumę modulo 2 oznaczamy symbolem $\oplus$ i definiujemy za pomocą tabelki.

Rys. 3. Tabelka definiująca sumę modulo 2

Podstawowe własności sumy modulo 2 są następujące

$0 \oplus0=0, \qquad 1 \oplus 1=0, \qquad 1 \oplus 0=1, \qquad 0 \oplus 1=1, \qquad x \oplus x=0$

$x \oplus 1 = \overline{x}, \qquad x \oplus 0=x, \qquad x_1 \oplus x_2= \overline{x_1} \oplus \overline{x_2}, \qquad x_1 \oplus x_2=x_1 \overline{x_2}+\overline{x_1}x_2$

$(x_1 \oplus x_2) \oplus x_3=x_1 \oplus (x_2 \oplus x_3)$ (łączność sumy modulo 2)

$x_1 \oplus x_2=x_2 \oplus x_1$ (przemienność sumy modulo 2)

$x_1\oplus x_2 \oplus x_2=x_1$

Przypomnijmy (por. rozdz.1), że zbiór $Z_m=\{0,1,2,...,m-1\}$ wraz z działaniami dodawania modulo $m$ i mnożenia modulo $m$ jest pierścieniem przemiennym z jednością a jeśli $m=p$, (gdzie p$p$jest liczbą pierwszą) to $Z_p$ jest ciałem. Zatem w szczególności $Z_2=\{0,1\}$ z dodawania działaniami modulo 2 i mnożenia modulo 2 jest ciałem.

Łatwo sprawdzić, że 2 argumentowa suma modulo 2 zdefiniowana tabelką z Rys. 2.3 i suma modulo 2 zdefiniowana jako szczególny przypadek sumy modulo $m$ (dla $m=2$) to to samo działanie. Z kolei iloczyn modulo 2 zdefiniowany jako szczególny przypadek sumy modulo $m$ (dla $m=2$) to mnożenie logiczne. Zatem trójka uporządkowana $(Z_2,\oplus,\cdot)$ jest ciałem. Zatem wprowadzenie w algebrze Boole’a sumy modulo 2 jako działania 2 argumentowego pozwala spojrzeć na zbiór $\{0,1\}$ jak na ciało.

Z algebry liniowej wiadomo (jest to prosty do sprawdzenia fakt), że jeśli $K$ jest ciałem, to iloczyn kartezjański $\underbrace{K \times K \times ... \times K}_{n}=K^n$ jest przestrzenią liniową nad ciałem $K$ . Zatem również $\underbrace{Z_2 \times Z_2 \times ... \times Z_2}_{n}=Z_2^n$ jest przestrzenią liniową nad $Z_2=\{0,1\}$. Można więc słowa binarne o długości $n$ (czyli elementy przestrzeni $Z_2^n$) nazywać wektorami.

Podobnie jeśli mamy ustalone dowolne ciało $K$ to można rozważać pierścień wielomianów $K[x]$ nad ciałem $K$. Tak też można zrobić w przypadku $Z_2$ wprowadzając wielomiany nad ciałem $Z_2=\{0,1\}$.

a)

Bramka NOT realizuje funkcję $y=\overline{x}$

b)

Bramka AND czyli bramka iloczynu (dwuwejściowego) realizuje funkcję $y=x_1x_1$. Stosowane są również bramki wielowejściowe.

c)

Dwuwejściowa bramka OR czyli bramka sumy (dwuwejściowej) realizuje funkcję $y=x_1+x_1$. Stosowane są również bramki wielowejściowe.

d)

Dwuwejściowa bramka EXOR czyli bramka sumy modulo dwa (dwuwejściowa) realizuje funkcję $y=x_1 \oplus x_1$. Stosowane są również bramki wielowejściowe EXOR. Bardzo pożyteczna jest w praktyce tożsamość $x_1 \oplus x_2=x_1\overline{x_2}+\overline{x_1}x_2$

Rys. 4. Symbole typowych bramek a) bramka NOT, b) bramka AND, c) bramka OR d) bramka EXOR