Pojęcie bitu
Algebra 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
Alternatywa / suma logiczna / LUB / OR a || b a+b
Koniunkcja / iloczyn logiczny / I / AND a && b ab
  

 

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:

 

 
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.

 

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.

 

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.


Prawa Algebry Boole'a

Łączność (ang. associativity)

oraz

 

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.

 

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
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)

oraz

Absorpcja (ang. absorption)

oraz

Rozdzielność (ang. distributivity)

 oraz

Odwrotność (ang. complement)

oraz

Prawa pochodne

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

 

 

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:

 

 

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

 

 
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.


Prawa De Morgana

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:

 

Negacja alternatywy jest równa koniunkcji negacji.

 

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.

 

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
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ą.

 


 

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.


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.

 

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

#include <iostream>

using namespace std;

int main()
{
  unsigned n,m;

  cout << "Przeliczanie liczby dziesietnej na binarna\n"
          "------------------------------------------\n\n"
          "liczba = ";
  cin >> n;
  cout << endl;
  for(m = 0x80000000L; m; m >>= 1) cout << ((n & m) ? "1" : "0");
  cout << endl << endl;
  return 0;
}
Przeliczanie liczby dziesietnej na binarna
------------------------------------------

liczba = 3854219376

11100101101110101011100001110000

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.