Algebra Boole'a

Wstęp

George Boole

Ogólnie algebrą nazwiemy zbiór określonych elementów (np. liczb) oraz działań, które można na nich wykonywać. Przykładowo, każdy z nas posługuje się algebrą liczb rzeczywistych. Zawiera ona nieskończenie wiele liczb. Można na nich wykonywać operacje takie jak np. dodawanie, odejmowanie, mnożenie, czy dzielenie.

Komputery i inne urządzenia cyfrowe wykorzystują tylko dwie wartości. W logice formalnej jest to prawda lub fałsz, a w systemach cyfrowych 0 (logiczne zero - wyłączony) i 1 (logiczna jedynka - włączony). Te cyfry również można dodawać, odejmować, mnożyć, czy dzielić, jednak tutaj wyniki mogą być inne. Zestaw tych wartości i operacji nazywamy właśnie tytułową algebrą Boole'a. Jej nazwa pochodzi od nazwiska matematyka, filozofa i logika George’a Boole’a, który opracował jej zasady już w XIX wieku. Znalazła ona swoje zastosowanie w matematyce, informatyce teoretycznej oraz elektronice cyfrowej

Taka uproszczona algebra może przydać się na przykład do opisania:

  • stanu przycisku, np. wciśnięty, wysoki (1) lub puszczony, niski (0),
  • stanu wyjścia układu - jest napięcie (1) lub nie ma napięcia (0).

Oznaczenia

Istnieją co najmniej trzy różne, szeroko rozpowszechnione tradycje oznaczeń w teorii algebr Boole’a. W definicji sformułowanej na Wikipedii użyto symboli ∪, ∩, ~, ale w częstym użyciu są również +, ·, ā oraz ∨, ∧, ¬. Symbole oznaczające operacje dwuczłonowe algebry Boole’a są prawie zawsze wprowadzane przez wybór jednej z par (+, ·), (∨, ∧) albo (∪, ∩) W oznaczeniach operacji jednoargumentowej algebry istnieje mniejsza konsekwencja i można się spotkać zarówno z symbolami +, ·, ~, jak i ∨, ∧, ’.

Suma Iloczyn Negacja
∪ ∩ ~
+ · a
∨ ∧ ¬
| & !
OR AND NOT

Podstawowe operacje

Alternatywa / suma logiczna / LUB / OR

Suma logiczna (inaczej alternatywa) wymaga dwóch argumentów. Gdy przynajmniej jeden z nich ma wartość 1, to wtedy wynik całej funkcji ma wartość 1. W przeciwnym razie, wynik jest zerowy.

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

Koniunkcja / iloczyn logiczny / I / AND

Iloczyn logiczny (nazywany również koniunkcją) działa podobnie do znanego nam mnożenia: jeżeli wśród argumentów znajdzie się chociaż jedno 0, to wtedy cały wynik będzie zerowy.

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

Negacja / zaprzeczenie / NIE / NOT

Negacja to jednoargumentowe działanie, które każdemu zdaniu a przyporządkowuje zdanie a (nie a). W algebrze Boole'a jest operacją, która przyjmuje tylko jeden argument. W wyniku jej działania otrzymujemy wartość przeciwną. Wynikiem zaprzeczenia "prawdy" będzie "fałsz" i odwrotnie, negacją "fałszu" będzie "prawda".

0 = nie 0 = 1
1 = nie 1 = 0

a a
0 1
1 0

Prawa i twierdzenia (aksjomaty)

Jak w każdej algebrze, i w tej określono pewne zasady. Są nimi łączność, rozdzielność, przemienność oraz prawa De Morgana. Pierwsze trzy dotyczą wyłącznie operatorów AND i OR. Podobnie, jak zero determinuje wynik mnożenia, tak w algebrze Boole'a jedynka przesądza o wyniku sumowania. Dodanie 1 do jakiejkolwiek liczby zawsze da w efekcie 1. To jest nowość, która dla wielu wydaje się być nieintuicyjna. Podstawowe prawa algebry Boole’a:

a = dowolna wartość (0 lub 1)

Prawa przemienności

a ∨ b = b ∨ a
a ∧ b = b ∧ a

zmiana kolejności czynników nie zmienia wyniku

Prawa identyczności (tożsamości)

a ∨ 0 = a
a ∧ 1 = a

zero (0) nie wpływa na wynik dodawania
jeden (1) nie wpływa na wynik mnożenia

a ∨ 1 = 1
a ∧ 0 = 0

dodanie jedynki (1) zawsze da jeden (1)
mnożenie przed zero (0) zawsze da zero (0)

Prawa idempotentności (operacji między równymi zmiennymi)

a ∨ a = a
a ∧ a = a

0 + 0 = 0 oraz 1 + 1 = 1
0 · 0 = 0 oraz 1 · 1 = 1

Prawa dopełnienia (uzupełnienia)

a ∨ a = 1
a ∧ a = 0

0 + 1 = 1 oraz 1 + 0 = 1
0 · 1 = 0 oraz 1 · 0 = 0

Prawo inwolucji (podwójnej negacji)

a = a

a = 0 lub 1
a = 1 lub 0
a = 0 lub 1 = a

Prawa łączności

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

kolejność wykonywania działań przy takim samym operatorze nie ma znaczenia

Prawa rozdzielności

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

rozdzielność mnożenia względem dodawania (powiązanie z wyłączaniem wspólnego czynnika przed nawias)
rozdzielność dodawania względem mnożenia (taka reguła nie obowiązuje w zwykłej algebrze)

Prawa pochłaniania (absorpcji)

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

Prawa De Morgana

Dziewiętnastowieczny matematyk, Augustus De Morgan, zaproponował używane do dziś następujące prawa definiujące koniunkcję i alternatywę. Okazuje się, że podstawowymi operacjami w logice są tylko dwie funkcje: negacja + alternatywa lub negacja + koniunkcja. Za pomocą tych dwóch funkcji można utworzyć wszystkie pozostałe.

a ∧ b = a V b
a V b = a ∧ b

negacja koniunkcji (mnożenia) jest alternatywą (dodawaniem) negacji
negacja alternatywy (dodawania) jest koniunkcją (mnożeniem) negacji

Przykłady zastosowania praw De Morgana

c ∧ d = c ∧ d = c V d

podwójnie negujemy wyrażenie, stosujemy prawo De Morgana

p ∧ q = p ∧ q = p V q = p V q

podwójnie negujemy wyrażenie, stosujemy prawo De Morgana, usuwamy podwójną negację p

Funkcje logiczne (boolowskie)

Definicja

Funkcje logiczne definiują zależność sygnału wyjściowego od wartości zmiennych. Każda funkcja jest matematycznym modelem układu kombinacyjnego. Układy tego typu są używane do budowy między innymi multiplekserów, mikroprocesorów, do sterowania na przykład wyświetlaczami LED i w wielu innych urządzeniach elektronicznych.

Funkcja boolowska to dowolne odwzorowanie f: X → Y, gdzie B = {0,1}, X jest podzbiorem Bn, a Y jest podzbiorem Bm.

Jeżeli funkcja jest określona dla całego zbioru Bn nazywamy ją funkcją zupełną. W przeciwnym wypadku jest to funkcja niezupełna, nie w pełni określona.

Liczba wszystkich n-argumentowych funkcji boolowskich zupełnych jest równa 22n

W przykładach zakładamy, że funkcja f ma trzy argumenty: a, b i c.

Sposoby opisu

Opis słowny

Ten sposób stosowany jest w przypadku prostych funkcji, lub gdy charakteryzowane są pewne specyficzne własności funkcji. Spotyka się go w zasadzie wyłącznie we wstępnej fazie projektowania układu. Do dalszej analizy tworzy się na podstawie opisu słownego tabelę lub/oraz postacie kanoniczne.

„funkcja ma wartość jeden, gdy a jest różne od b, lub c jest równe b”
„dla indeksów nieparzystych funkcja jest równa zero”

Tablica prawdy

Postać najczęściej spotykana, zwłaszcza dla funkcji niewielu zmiennych. W tablicy wypisuje się wszystkie kombinacje zmiennych wejściowych oraz odpowiadające im wartości funkcji. Oprócz stanów 0 i 1 można uwzględnić również stany nieokreślone, oznaczane zwykle - (minus) lub x.

# a b c f
0 0 0 0 1
1 0 0 1 1
2 0 1 0 1
3 0 1 1 –
4 1 0 0 1
5 1 0 1 0
6 1 1 0 1
7 1 1 1 0

Kanoniczna postać sumy (sumacyjna)

W polskiej literaturze kanoniczna postać sumy oznaczana jest skrótem KPS, a w angielskiej SOP.

W KPS funkcja stanowi sumę iloczynów (implikantów) pomnożonych przez wartości funkcji.

a b f(a, b)
0 0 0
0 1 0
1 0 0
1 1 1

f = ...(... ∧ ... ∧ ...) ∨ (... ∧ ... ∧ ...) ∨ (... ∧ ... ∧ ...)...

Wyrażenie w nawiasie (iloczyn) odpowiada jednej jedynce. W tym konkretnym przypadku:
f = (a ∧ b)

Zapis skrócony dziesiętny:
f(a, b) = Σ(3)

Kanoniczna postać iloczynu (iloczynowa)

W polskiej literaturze kanoniczna postać iloczynu oznaczana jest skrótem KPI, a w angielskiej POS.

W KPI funkcja stanowi iloczyn sum (implicentów) z dodanymi wartościami funkcji.

a b f(a, b)
0 0 0
0 1 0
1 0 0
1 1 1

f = ...(... ∨ ... ∨ ...) ∧ (... ∨ ... ∨ ...) ∧ (... ∨ ... ∨ ...)...

Wyrażenie w nawiasie (suma) odpowiada jednemu zeru. W tym konkretnym przypadku:
f = (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b).

Zapis skrócony dziesiętny:
f(a, b) = Π(0, 1, 2)

Minimalizacja funkcji logicznych

Aby zaprojektować układ kombinacyjny pierwsze trzeba uprościć funkcje opisującą jego działanie. Stosuje się wówczas metody minimalizacji funkcji logicznych. Polegają one na upraszczaniu wyrażeń logicznych, tak aby zawierały jak najmniejszą liczbę tylko niezbędnych argumentów oraz operacji logicznych. Zadanie to ma podstawowe znaczenie dla techniki cyfrowej, gdzie funkcje urządzenia realizowane są za pomocą tzw. bramek logicznych (układów wykonujących podstawowe operacje logiczne). Jest chyba jasne, iż prostsze wyrażenie oznacza mniejszą złożoność układu elektronicznego, a co za tym idzie mniejszy koszt wykonania, większą niezawodność (mniej elementów, które mogą przestać działać) oraz zwykle szybsze działanie (mniej uzależnień powoduje szybszą stabilizację sieci logicznej).

Sposoby minimalizacji:

  • stosowanie praw algebry Boole’a (jest to jednak sposób bardzo pracochłonny i mało efektywny),
  • metoda graficzna – tablic Karnaugha (stosuje się ją do minimalizacji funkcji maksymalnie 6 zmiennych).

Źródła