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 systematyzował 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 operacją jednoargumentową, tzn. rezultat zależy tylko od jednego argumentu. Wynikiem jest wartość logiczna przeciwna do tej, którą ma argument negacji.
Negacja a NOT a 0 1 1 0 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.
NOT 1110111100100011001001001001010100100111 0001000011011100110110110110101011011000
Operacja alternatywy (sumy logicznej) jest operacją dwuargumentową, tzn. rezultat zależy od obu argumentów.
| Alternatywa | ||
|---|---|---|
| a | b | a OR b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
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.
11000101001011 OR 10101011011000 11101111011011
Operacja koniunkcji (iloczynu logicznego) jest również dwuargumentowa.
Koniunkcja a b a AND b 0 0 0 0 1 0 1 0 0 1 1 1 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.
11000101001011 AND 10101011011000 10000001001000
Operacja sumy symetrycznej nie jest operacją elementarną, jednakże często przydaje się przy różnych okazjach. Jest to operacja dwuargumentowa.
Suma symetryczna a b a XOR b 0 0 0 0 1 1 1 0 1 1 1 0 Mnemotechnicznie zapamiętajmy, iż wynikiem sumy symetrycznej jest 1 tylko wtedy, gdy dokładnie jeden z argumentów ma wartość 1 i 0 w przeciwnym przypadku.
Jeśli wykonamy operację sumy 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.
11000101001011 XOR 10101011011000 01101110010011
| |
Ustawianie zadanego 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.
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 zadanego 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.
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ę sumy symetrycznej.
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.
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
Prawa DeMorgana
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:
- Negacja alternatywy jest równa koniunkcji negacji: NOT(a OR b) = (NOT a) AND (NOT b).
- 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:
NOT(a OR b) = (NOT a) AND (NOT b) a b a OR b NOT(a OR b) NOT a NOT b NOT(a) AND NOT(b) 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0
NOT(a AND b) = (NOT a) OR (NOT b) a b a AND b NOT(a AND b) NOT a NOT b NOT(a) OR NOT(b) 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 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:
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 instrukcji do Przykładowej Maszyny Cyfrowej.
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.
Źródło: mgr Jerzy Wałaszek