George Boole

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

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:

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:

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.

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.

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

Łączność (ang. associativity)

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.

Przemienność (ang. commutativity)

Rozdzielność (ang. distributivity)

Odwrotność (ang. complement)

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:

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

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:

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.

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.

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

Alternatywa

Koniunkcja

Różnica symetryczna / Suma modulo 2

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.

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.

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.

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.

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