Rozwój komputerów i techniki cyfrowej nie byłby możliwy bez podstawowego wynalazku, którym niewątpliwie jest algebra Boole'a. Jest to zbiór reguł wykonywania operacji na wartościach logicznych, czyli takich które mogą przyjmować wartość prawdy (true) lub fałszu (false). Algebrę tę po raz pierwszy opisał i usystematyzował matematyk angielski George Boole.

W algebrze Boole'a (podobnie jak w zwykłej algebrze) istnieją operacje elementarne które można wykonywać nad wartościami logicznymi. Są to:

• negacja (zaprzeczenie logiczne - NOT)
• alternatywa (suma logiczna - OR)
• koniunkcja (iloczyn logiczny - AND)

Bity są idealne do reprezentowania wartości logicznych. Umówmy się, iż wartość logiczną fałszu będziemy reprezentować stanem bitu 0, a wartość prawdy stanem 1.

Negacja - zaprzeczenie logiczne

Jest to operacja jednoargumentowa, tzn. rezultat zależy tylko od jednego argumentu. Wynikiem jest wartość logiczna przeciwna do tej, którą ma argument negacji.

Jeśli operację negacji wykonamy nad słowem binarnym, to w wyniku otrzymamy słowo, w którym wszystkie bity mają wartości przeciwne do słowa wyjściowego.

Przykład:

NOT	1110111100100011001001001001010100100111
	0001000011011100110110110110101011011000

Alternatywa - suma logiczna

 

Jeśli porównasz tabelkę alternatywy z tabliczką dodawania w systemie binarnym, to na pewno zauważysz duże podobieństwo. Różnica jest w ostatnim wierszu - dla obu argumentów równych 1 alternatywa daje 1, a suma binarna 10. Oczywiście jest to spowodowane faktem, iż operatory logiczne dają w wyniku zawsze wartości logiczne, czyli 0 lub 1. Mnemotechnicznie zapamiętajmy, iż alternatywa daje tylko wtedy 0, gdy wszystkie argumenty mają wartość 0 i 1 w przypadku przeciwnym.

Jeśli wykonamy operację alternatywy nad dwoma słowami binarnymi, to w wyniku otrzymamy słowo binarne, którego bity są wynikami operacji alternatywy nad odpowiadającymi im bitami argumentów.

Przykład:

	11000101001011
OR	10101011011000
	11101111011011

Koniunkcja - iloczyn logiczny

Porównaj tabelkę koniunkcji z tabliczką mnożenia w systemie dwójkowym. Mnemotechnicznie zapamiętajmy, iż koniunkcja przyjmuje wartość 1, gdy wszystkie jej argumenty mają wartość 1 i 0 w przeciwnym wypadku.

Jeśli wykonamy operację koniunkcji nad dwoma słowami binarnymi, to w wyniku otrzymamy słowo binarne, którego bity są wynikami operacji koniunkcji nad odpowiadającymi im bitami argumentów.

Przykład:

	11000101001011
AND	10101011011000
	10000001001000

Różnica symetryczna - suma modulo dwa

Operacja różnicy symetrycznej nie jest operacją elementarną, jednakże często przydaje się przy wielu okazjach. Jest to operacja dwuargumentowa.

Mnemotechnicznie zapamiętajmy, iż wynikiem różnicy symetrycznej jest 1 tylko wtedy, gdy dokładnie jeden z argumentów ma wartość 1 i 0 w przeciwnym przypadku.

Jeśli wykonamy operację różnicy symetrycznej nad dwoma słowami binarnymi, to w wyniku otrzymamy słowo binarne, którego bity są wynikami tej operacji nad odpowiadającymi im bitami argumentów.

Przykład:

	11000101001011
XOR	10101011011000
	01101110010011

Ustawianie wybranego bitu

W słowie binarnym chcemy ustawić n-ty bit na 1. W tym celu przygotowujemy maskę o długości słowa binarnego, w której wszystkie bity są wyzerowane z wyjątkiem bitu n-tego. Następnie wykonujemy operację alternatywy nad słowem binarnym i maską. W wyniku n-ty bit słowa zostanie ustawiony na 1.

Przykład:

Ustawiamy trzeci (uwaga - bity numerujemy od 0!) bit w słowie binarnym 110001010011.

	110001010011	zmieniane słowo
OR	000000001000	maska bitowa
	110001011011	wynik operacji

Zerowanie wybranego bitu

Operacją odwrotną do ustawiania bitu jest oczywiście jego zerowanie. W tym celu tworzymy maskę, w której wszystkie bity są ustawione na 1 z wyjątkiem bitu na pozycji do wyzerowania. Następnie wykonujemy operację koniunkcji nad słowem zawierającym bit oraz maską. W wyniku otrzymujemy słowo z wyzerowanym bitem na zadanej pozycji.

Przykład:

Zerujemy trzeci (uwaga - bity numerujemy od 0!) bit w słowie binarnym 110001011111.

	110001011111	zmieniane słowo
AND	111111110111	maska bitowa
	110001010111	wynik operacji

Negacja zadanego bitu

Operacja ta polega na zmianie stanu wybranego bitu na przeciwny. W tym celu przygotowujemy maskę z wyzerowanymi bitami za wyjątkiem pozycji do zamiany stanu. Nad słowem i maską wykonujemy operację różnicy symetrycznej.

Przykład:

Zmieniamy stan trzeciego (uwaga - bity numerujemy od 0!) bitu w słowie binarnym 110001010111.

	110001010111	zmieniane słowo
XOR	000000001000	maska bitowa
	110001011111	wynik operacji

Zastępowanie bitu/bitów

W tym przypadku mamy dwa słowa binarne. W drugim słowie chcemy zastąpić wybrany bit bitem ze słowa pierwszego. Operacja ta jest złożona i wymaga ciągu działań logicznych. Najpierw przygotowujemy maskę z ustawionym bitem na pozycji wymiany bitów. Nad pierwszym słowem i maską wykonujemy operację koniunkcji. W wyniku otrzymujemy nową maskę, w której bity niezmienione mają wartość 0, a bit na pozycji wymiany ma wartość taką jak w słowie pierwszym. Pierwszą maskę negujemy. W efekcie bity na pozycjach niezmienionych otrzymają wartość 1, a na pozycji wymiany bit będzie miał wartość 0. Maskę tę wykorzystujemy do wyzerowania bitu w drugim słowie operacją koniunkcji. Teraz łączymy za pomocą alternatywy maskę otrzymaną po pierwszej operacji z drugim słowem. W efekcie w drugim słowie na pozycji wymiany otrzymamy bit ze słowa pierwszego.

Przykład:

Mamy dane dwa 8-bitowe słowa binarne: 10110111 i 11101101. W drugim słowie chcemy zastąpić cztery najmłodsze bity odpowiadającymi im bitami ze słowa pierwszego. Najpierw wycinamy bity z pierwszego słowa:

	10110111	pierwsze słowo
AND	00001111	maska
	00000111	maska z wyciętymi bitami

Teraz w drugim słowie zerujemy bity, które mają być zastąpione:

	11101101	drugie słowo
AND	11110000	maska
	11100000	drugie słowo z wyzerowanymi bitami

Łączymy maskę z wyciętymi bitami z drugim słowem z wyzerowanymi bitami:

	11100000	drugie słowo z wyzerowanymi bitami
OR	00000111	maska z wyciętymi bitami
	11100111	wynik operacji

W efekcie w drugim słowie cztery najmłodsze bity pochodzą ze słowa pierwszego:

10110111 – pierwsze słowo 11101101 – drugie słowo 11100111 – wynik

Przy przekształcaniu wyrażeń logicznych korzysta się często z dwóch prostych praw zwanych prawami DeMorgana. Ich zapis słowny brzmi następująco:

1. Negacja alternatywy jest równa koniunkcji negacji:
   NOT(a OR b) = (NOT a) AND (NOT b).
2. Negacja koniunkcji jest równa alternatywie negacji
   NOT(a AND b) = (NOT a) OR (NOT b).

Prawa De Morgana udowadniamy za pomocą tabelek, w których konstruujemy wyniki wyrażenia po lewej i po prawej stronie równości i sprawdzamy, czy otrzymaliśmy to samo. Jeśli tak, to prawo zostaje udowodnione:

Prawa De Morgana pokazują nam, iż tak naprawdę potrzebne są tylko dwie operacje pierwotne (negacja i koniunkcja) lub (negacja i alternatywa). Drugą operację zawsze możemy wyprowadzić z pierwszej za pomocą odpowiednich przekształceń logicznych:

Przykład:

Koniunkcja:	a AND b =	NOT(NOT(a AND b)) =	NOT(NOT(a) OR NOT(b))
Alternatywa:	a OR b =	NOT(NOT(a OR b)) =	NOT(NOT(a) AND NOT(b))

Więcej na ten temat znajdziesz w artykule "Zastosowania bitów w praktyce".

Zadanie 1 (łatwe)

Wykonaj podane niżej operacje logiczne:

1001 OR 0101  =		.
1110 AND 0101 =		.
NOT 10111010 =		.
11011001 XOR 11111111  =		.
1101 AND 0111 XOR 1111 =		.

Zadanie 2 (średnie)

Wyprowadź wzór na operację XOR wykorzystując tylko operację NOT oraz AND.

Zadanie 3 (średnie)

Jak sprawdzisz, czy n-ty bit danego słowa binarnego jest ustawiony na 1 lub na 0? Podaj odpowiedni przykład.

Zadanie 4 (średnie)

Jak sprawdzić za pomocą operacji logicznych, czy dana liczba binarna jest nieparzysta?