Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek
|
![]() |
George Boole |
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:
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.
Jest to operacja jednoargumentowa, 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.
Przykład:
NOT | 1110111100100011001001001001010100100111 |
0001000011011100110110110110101011011000 |
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.
Przykład:
11000101001011 |
|
OR | 10101011011000 |
11101111011011 |
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.
Przykład:
11000101001011 |
|
AND | 10101011011000 |
10000001001000 |
Operacja różnicy symetrycznej nie jest operacją elementarną, jednakże często przydaje się przy wielu okazjach. Jest to operacja dwuargumentowa.
Różnica symetryczna | ||
---|---|---|
a | b | a XOR b |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
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 |
W słowie binarnym chcemy ustawić
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 |
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 |
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 |
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łowo11101101 – drugie słowo11100111
– 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:
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:
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".
Wyprowadź wzór na operację XOR wykorzystując tylko operację NOT oraz AND.
Jak sprawdzisz, czy
Jak sprawdzić za pomocą operacji logicznych, czy dana liczba binarna jest nieparzysta?
Zobacz dalej...
Kody binarne | Naturalny system dwójkowy | Dwójkowy system stałoprzecinkowy | Operacje arytmetyczne w systemie dwójkowym | Konwersje dwójkowo ósemkowe i szesnastkowe
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.