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.

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 jest operacją dwuargumentową. Wynikiem jest \(1\)  (\(\text{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 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{-}\text{tej}}\), to wykonujemy operację koniunkcji z maską, której wszystkie bity są ustawione na \(1\) za wyjątkiem bitu na pozycji \({i{-}\text{tej}}\).

Ustawianie bitu

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

Negacja bitu

Jeśli chcemy zmienić stan \({i{-}\text{tego}}\) bitu na przeciwny, wykonujemy operację sumy symetryczne z maską, której wszystkie bity są wyzerowane za wyjątkiem bitu na pozycji \({i{-}\text{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)2026 J.W.

#include <iostream>
// Lokalizacja
#include <clocale>
// Wymagane dla funkcji _getch()
#include <conio.h>

using namespace std;

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

  // Ustawiamy lokalizację na
  // domyślną dla systemu
  // użytkownika
  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 = 0x8000000000000000ull;
      m;
      m >>= 1)
    cout << ((n & m) ? "1" : "0");

  cout << "\n\nNaciśnij Enter...";
  _getch();
  cout << endl;
  return 0;
}

Uwaga: W języku Python liczby całkowite nie mają ograniczenia zakresu i mogą przyjmować dowolną wielkość (standardowo do 4300 cyfr – jako zabezpieczenie przed atakami hackerskimi, ale limit ten możesz łatwo zmienić poleceniem sys.set_int_max_str_digits(nowy_limit), poszukaj informacji w Google.). Tutaj liczbę sztucznie ograniczamy do 64 bitów. Dlatego nie wprowadzaj wartości wykraczających poza \({2^{64}-1}\), czyli od \(0\) do \({18{'}446{'}744{'}073{'}709{'}551{'}615}\).

# Liczba binarna
# (C)2026 J.W.

# Program główny

print("Przeliczanie liczby "
      "dziesiętnej na binarną\n"
      "--------------------"
      "----------------------\n")

# Odczytujemy liczbę
# do konwersji
n = int(input("liczba = "))

print()

# ograniczamy liczbę
#do 64 bitów
n &= 0xFFFFFFFFFFFFFFFF

# W pętli przeglądamy kolejne
# bity liczby od najstarszego
# do najmłodszego i wypisujemy
# ich stan w terminalu
m = 0x8000000000000000

while m:
    if n & m:
        print(1,end="")
    else:
        print(0,end="")
    m >>= 1

print()
print()

input("Naciśnij Enter...")

Przeliczanie liczby dziesiętnej na binarną
------------------------------------------

liczba = 1234567890123456789

0001000100100010000100001111010001111101111010011000000100010101

Naciśnij Enter...