Układy logiczne

Funkcję boolowską nazywamy również funkcją logiczną lub funkcją przełączającą. Funkcja boolowska jest też definiowana nieco ogólniej jako funkcja postaci $f:D \rightarrow \{0,1\}^m$, gdzie $D \subset \{0,1\}^n$ jest niepustym podzbiorem zbioru wszystkich słów binarnych binarnych długości $n$.

Jeśli mówimy „funkcja boolowska $n$ argumentowa” nie precyzując $D$ to przyjmujemy, że $D=\{0,1\}^n$. Jeśli $D=\{0,1\}^n$ to funkcję boolowską nazywamy zupełną. Jeśli $D$ jest właściwym podzbiorem zbioru $\{0,1\}^n$, to funkcję boolowską nazywamy niezupełną. Jeśli $m>1$, to funkcję boolowską nazywamy wektorową.

Na ogół mówiąc funkcja boolowska będziemy mieć na myśli funkcję $f:\{0,1\}^n \rightarrow \{0,1\}$.

Zauważmy, że nawet dla małych $n$ liczba wszystkich funkcji boolowskich jest duża. Jest to bowiem liczba wariancji z powtórzeniami zbioru $2^n$ elementowego ze zbioru 2-elementowego, czyli $2^{2^n}$. Dla $n=2$ mamy 16 funkcji ale dla $n=5$ już $2^{32}$ (to więcej niż 100 milionów).

Rys.1. Układ kombinacyjny o $n$ wejściach i jednym wyjściu (układ jednowyjściowy) realizujący funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}$

Rys. 2. Układ kombinacyjny o $n$ wejściach i $m$ wyjściach (układ wielowyjściowy) realizujący funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}^m$