Funkcja boolowska

Funkcja boolowska, znana również jako funkcja logiczna, jest odwzorowaniem $f\colon X \to Y$ , gdzie $B = \{0,1\}$ , $X$ jest podzbiorem $B^n$ , a $Y$ jest podzbiorem $B^m$ . Funkcje boolowskie mogą być pełne, gdy $X = B^n$ , lub niezupełne, gdy $X$ jest właściwym podzbiorem $B^n$ . Liczba wszystkich n-argumentowych funkcji zupełnych wynosi $2^{2^n}$ .

Zapis funkcji boolowskiej

W zapisie funkcji boolowskich używane są literały oraz wartości z zbioru $\{0,1,-\}$ , gdzie 0 i 1 są umownymi oznaczeniami, a kreska oznacza, że funkcja nie jest określona dla danego wektora.

Literały

Literał definiuje się jako:

$x^e = \left\{\begin{matrix} x & \text{dla} & e=1 \\ \overline{x} & \text{dla} & e=0 \\ 1 & \text{dla} & e=- \end{matrix}\right.$

Przykłady literałów z wieloma zmiennymi to:

$x_1^{e_1} x_2^{e_2} \ldots x_n^{e_n} \to e_1 e_2 \dots e_n.$

Termy

Termy iloczynowe (np. $ab\overline{z}$ ) lub sumowe (np. $\overline{d}+\overline{e}+z+y$ ) nie powinny zawierać powtarzających się zmiennych. Miniterm to iloczyn pełny, a maxterm to suma pełna. Indeksy minitermów i maxtermów mogą być przedstawione w postaci wektora wskaźników literałów.

Formy zapisu funkcji

Opis słowny

Używany w przypadku prostych funkcji, np. „funkcja ma wartość jeden, gdy a jest różne od b lub c jest równe b”.

Tablica prawdy

Przechowuje wszystkie kombinacje zmiennych wejściowych i odpowiadające im wartości funkcji.

Mapa Karnaugha

Prostokątna tablica przedstawiająca przekształconą tablicę prawdy, gdzie grupowane są indeksy dwójkowe.

Kanoniczna postać sumy

Funkcję boolowską można rozłożyć na sumę iloczynów minitermów. Można pominąć iloczyny, w których funkcja ma wartość zero.

Kanoniczna postać iloczynu

Podobnie jak suma, można przedstawić funkcję w postaci iloczynu maxtermów, które odpowiadają wartościom zero.

Funkcja boolowska samodwoista

Funkcja jest samodwoista, jeśli $f(x_0, x_1, …, x_n) = \neg{f(\bar{x_0}, \bar{x_1}, …, \bar{x_n})}$ , co przypomina funkcje nieparzyste.

Podsumowanie

Minimalizacja funkcji boolowskiej i inne techniki, takie jak redukcja argumentów i dekompozycja, pozwalają na tworzenie bardziej efektywnych układów cyfrowych. Najczęściej używane funkcje boolowskie to: