Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Pojęcie bitu

Algebra Boole'a

SPIS TREŚCI
Podrozdziały

Podstawy algebry Boole'a

George Boole
George Boole (ur. 2 XI 1815 r., zm. 8 XII 1864 r.) był matematykiem angielskim, którego uważa się za jednego z twórców dzisiejszej technologii komputerowej. Najważniejszym wynalazkiem Boole'a było opracowanie zasad wykonywania operacji logicznych – w ten sposób powstała tzw. Algebra Boole'a. Przed Boole'm logika była dziedziną zagmatwaną i trudną w zastosowaniach. Po nim stała się łatwa i przejrzysta.

W Algebrze Boole'a mamy do czynienia z danymi binarnymi. Dana może przyjąć tylko jedną z dwóch możliwych wartości:

prawda  – true  – 1
fałsz  – false  – 0

Z tego powodu danymi mogą być bity. Nad danymi można wykonywać operacje logiczne (podobnie jak w zwykłej algebrze nad liczbami można wykonywać operacje arytmetyczne). Podstawowych operacji logicznych mamy dokładnie trzy:

Nazwa operacji logicznej Notacja
w
logice
w
C++
w technice
cyfrowej
Negacja / zaprzeczenie / NIE / NOT ¬ a !a a
Alternatywa / suma logiczna / LUB / OR a ∨ b a || b a + b
Koniunkcja / iloczyn logiczny / I / AND a ∧ b a && b a · b

W powyższej tabelce zebraliśmy również różne sposoby zapisu operacji logicznych. W tym rozdziale będziemy się posługiwali oznaczeniami stosowanymi w logice. Jednakże w dalszych rozdziałach wykorzystamy również notację dla języka C++ oraz notację dla techniki cyfrowej przy projektowaniu sieci logicznych.

Negacja zaprzeczenie NIE NOT

Jest to operacja jednoargumentowa. Wynikiem negacji jest wartość odwrotna, przeciwna do wartości argumentu. Zatem jeśli argument miał wartość 0, to negacja daje w wyniku 1 i na odwrót z 1 otrzymujemy 0. Wartości funkcji logicznych w zależności od ich argumentów podaje się zwykle w tabelkach. My też skorzystamy z tego prostego sposobu:

¬ a
0 1
1 0

Alternatywa suma logiczna LUB OR

Alternatywa jest operacją dwuargumentową. Wynikiem jest 1 ( true, prawda), jeśli chociaż jeden z argumentów ma wartość 1. Jeśli oba argumenty mają wartość 0, alternatywa też ma wartość 0.

a b a ∨ b
0 0 0
0 1 1
1 0 1
1 1 1

Operację tą często nazywa się sumą logiczną ze względu na jej podobieństwo do sumy arytmetycznej dla liczb naturalnych: suma dwóch liczb jest różna od zera, gdy chociaż jedna z tych liczb jest różna od zera, a równa zero, gdy obie liczby są równe zero.

Koniunkcja iloczyn logiczny I AND

Koniunkcja jest również operacją dwuargumentową. Wynikiem jest 1, jeśli oba argumenty są równe 1. W pozostałych przypadkach wynikiem jest 0.

a b a ∧ b
0 0 0
0 1 0
1 0 0
1 1 1

Ze względu na podobieństwo do operacji mnożenia arytmetycznego koniunkcję często nazywa się iloczynem logicznym.

Na początek:  podrozdziału   strony 

Prawa algebry Boole'a

Łączność (ang. associativity)

a ∨ ( b ∨ c) = ( a ∨ b ) ∨ c

oraz

a ∧ ( b ∧ c ) = ( a ∧ b ) ∧ c

W celu udowodnienia tej własności posłużymy się tabelką prawdy. W tabelce najpierw obliczamy wartość lewego wyrażenia, a następnie prawego. Jeśli kolumny wyniku dla lewego i prawego wyrażenia są identyczne, własność zostaje udowodniona.

a ∨ ( b ∨ c) = ( a ∨ b ) ∨ c
a b c b ∨ c a ∨ ( b ∨ c) a b c a ∨ b ( a ∨ b ) ∨ c
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 1 0 1
0 1 0 1 1 0 1 0 1 1
0 1 1 1 1 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 0 1 1 1 1 0 1 1 1
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
a ∧ ( b ∧ c ) = ( a ∧ b ) ∧ c
a b c b ∧ c a ∧ ( b ∧ c ) a b c a ∧ b ( a ∧ b ) ∧ c
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 1 0 0 0
0 1 1 1 0 0 1 1 0 0
1 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 1 0 0
1 1 0 0 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1

Przemienność (ang. commutativity)

a ∨ b = b ∨ a

oraz

a ∧ b = b ∧ a

Absorpcja (ang. absorption)

a ∨ ( a ∨ b ) = a

oraz

a ∧ ( a ∧ b ) = a

Rozdzielność (ang. distributivity)

a ∨ ( b ∧ c) = ( a ∨ b ) ∧ ( a ∨ c )

oraz

a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c )

Odwrotność (ang. complement)

a ∨ ¬ a = 1

oraz

a ∧ ¬ a = 0

Prawa pochodne

Z podanych powyżej praw podstawowych algebry Boole'a oraz własności operacji logicznych wynikają następujące prawa pochodne:

a ∨ a = a,  a ∧ a = a
a ∨ 0 = a,  a ∧ 1 = a
a ∨ 1 = 1,  a ∧ 0 = 0
¬ 0 = 1,  ¬ 1 = 0
¬ ( ¬ a ) = a

Różnica symetryczna, suma modulo dwa

W logice bardzo często wykorzystuje się złożoną operację logiczną o nazwie różnicy symetrycznej lub sumy modulo dwa ( ang. exclusive or). Wzór logiczny tej operacji jest następujący:

a ⊕ b = ( ¬ a ∧ b ) ∨ ( a ∧ ¬ b )

Chociaż nie jest on specjalnie oczywisty, to operacja różnicy symetrycznej ma bardzo prostą tabelkę stanów:

a b  a ⊕ b
0 0 0
0 1 1
1 0 1
1 1 0

Wynikiem jest 1, jeśli argumenty operacji się różnią od siebie, a 0, jeśli są takie same.

Na początek:  podrozdziału   strony 

Prawa De Morgana

August De Morgan

August De Morgan (ur. 27 VI 1806 r., zm. 18 III 1871 r.) był urodzonym w Indiach angielskim matematykiem i logikiem. Wkładem De Morgana do rozwoju matematyki i logiki są prawa odnoszące się do negacji koniunkcji i negacji alternatywy. Prawa te brzmią następująco:

¬ ( a ∨ b ) = ¬ a ∧ ¬ b
Negacja alternatywy jest równa koniunkcji negacji.
¬ ( a ∧ b ) = ¬ a ∨ ¬ b
Negacja koniunkcji jest równa alternatywie negacji.

Z praw De Morgana wynikają bardzo poważne konsekwencje dla logiki. Okazuje się bowiem, iż do wykonania dowolnej operacji logicznej wystarczy para ( negacja, koniunkcja) lub para ( negacja, alternatywa). Ma to olbrzymi wpływ na współczesną technikę cyfrową, o czym możesz się prosto przekonać czytając dalsze artykuły. Prawa De Morgana w prosty sposób udowadniamy przy pomocy tabelek prawdy.

¬ ( a ∨ b ) = ¬ a ∧ ¬ b
a b a ∨ b ¬ (a ∨ b) a b ¬ a ¬ b ¬ a ∧ ¬ b
0 0 0 1 0 0 1 1 1
0 1 1 0 0 1 1 0 0
1 0 1 0 1 0 0 1 0
1 1 1 0 1 1 0 0 0
¬ ( a ∧ b ) = ¬ a ∨ ¬ b
a b  a ∧ b ¬ ( a ∧ b ) a b ¬ a ¬ b ¬ a ∨ ¬ b
0 0 0 1 0 0 1 1 1
0 1 0 1 0 1 1 0 1
1 0 0 1 1 0 0 1 1
1 1 1 0 1 1 0 0 0

Teraz pokażemy, jak wykorzystując prawa De Morgana, można zastąpić koniunkcję alternatywą i alternatywę koniunkcją.

a ∧ b = ¬ ( ¬ ( a ∧ b )) = ¬ ( ¬ a ∨ ¬ b )
a ∨ b = ¬ ( ¬ ( a ∨ b )) = ¬ ( ¬a ∧ ¬ b )

W ramach ćwiczeń udowodnij tabelkami prawdy poprawność otrzymanych wyników.

Jeśli w dowolnym wyrażeniu logicznym zastąpimy wszystkie koniunkcje negacjami i alternatywą, to wyrażenie będzie zawierało tylko dwa działania logiczne alternatywę i negację. Wynika stąd, iż te dwa działania wystarczą do zapisania dowolnego wyrażenia logicznego. Zachodzi również sytuacja odwrotna. Zastąpienie alternatywy negacjami i koniunkcją ruguje alternatywy z wyrażenia. Zatem dowolne wyrażenie logiczne można zapisać tylko przy pomocy negacji i koniunkcji.

Na początek:  podrozdziału   strony 

Operacje bitowe

Wszystkie operacje logiczne mogą być wykonywane na słówkach bitowych. W takim przypadku w operacji uczestniczą poszczególne bity na odpowiadających sobie pozycjach w obu słowach. Oto odpowiednie przykłady:

Negacja

¬   1 1 0 0
    0 0 1 1
¬   0 1 0 1
    1 0 1 0

Alternatywa

    1 0 1 0
  1 1 0 0
    1 1 1 0
    0 0 1 1
  1 1 0 0
    1 1 1 1
    1 1 0 1
  1 0 1 1
    1 1 1 1

Koniunkcja

    1 0 1 0
  1 1 0 0
    1 0 0 0
    0 0 1 1
  1 1 0 0
    0 0 0 0
    1 1 0 1
  1 0 1 1
    1 0 0 1

Różnica symetryczna / Suma modulo 2

    1 0 1 0
  1 1 0 0
    0 1 1 0
    0 0 1 1
  1 1 0 0
    1 1 1 1
    1 1 0 1
  1 0 1 1
    0 1 1 0

Zerowanie bitu

Jeśli w słowie binarnym chcemy wyzerować bit (bity ) na pozycji i-tej, to wykonujemy operację koniunkcji z maską, której wszystkie bity są ustawione na 1 za wyjątkiem bitu na pozycji i-tej.

    1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0
  1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
    1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0

Ustawianie bitu

Jeśli w słowie binarnym chcemy ustawić i-ty bit na 1, to wykonujemy operację alternatywy z maską, której wszystkie bity są wyzerowane za wyjątkiem bitu na pozycji i-tej.

    1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0
  0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
    1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 0

Negacja bitu

Jeśli chcemy zmienić stan i-tego bitu na przeciwny, wykonujemy operację sumy symetryczne z maską, której wszystkie bity są wyzerowane za wyjątkiem bitu na pozycji i-tej.

    1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0
  0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
    1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 0
    1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0
  0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
    1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0

Sprawdzanie stanu bitu

Jeśli chcemy sprawdzić, jaki stan ma bit na pozycji i-tej, to wykonujemy operację koniunkcji z maską, której wszystkie bity są wyzerowane za wyjątkiem bitu na pozycji i-tej. Jeśli wynik jest różny od 0, to bit i-ty miał stan 1. W przeciwnym wypadku bit i-ty miał stan 0.

    1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0
  0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0
  0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

Poniższy program wykorzystuje sprawdzanie stanu bitu do szybkiej konwersji liczby dziesiętnej na binarną właściwie wykorzystuje on fakt, iż komputer wewnętrznie przechowuje liczby w postaci binarnej, zatem konwersja została już wykonana przy zapisie odczytanej wartości do pamięci.

C++
// Liczba binarna
//------------------------------------------
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

int main( ) 
{ 
    unsigned n; // Liczba do konwersji
    unsigned m; // Maska bitowa do testowania stanu bitów liczby n

    setlocale( LC_ALL,"" );

    cout << "Przeliczanie liczby dziesiętnej na binarną\n"
            "------------------------------------------\n\n"
            "liczba = ";

    // Odczytujemy liczbę do konwersji
    cin >> n;

    cout << endl;

    // W pętli przeglądamy kolejne bity liczby od najstarszego do najmłodszego
    // i wypisujemy ich stan w oknie konsoli
    for( m = 0x80000000L; m; m >>= 1 )
        cout << (( n & m ) ? "1" : "0" );
  
    cout << endl << endl;
  
    return 0;
}
Wynik:
Przeliczanie liczby dziesiętnej na binarną
------------------------------------------

liczba = 3854219376

11100101101110101011100001110000
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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.