Układy logiczne

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