2. Układy kombinacyjne

2.1. Funkcje boolowskie

Funkcja boolowska (n-zmiennych) (ang. Boolean function) to każda funkcja postaci \(f:\{0,1\}^n \rightarrow \{0,1\}\), a układ (na ogół układ elektroniczny) realizujący funkcję boolowską nazywamy układem kombinacyjnym.

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\)

 

Funkcje boolowskie i ogólniej nieco układy logiczne można realizować (czyli konstruować) w różny sposób. Najczęściej (w praktyce prawie wyłącznie) układy logiczne realizowane są jako układy elektroniczne ale znane i stosowane są również realizacje mechaniczne, elektromechaniczne i pneumatyczne. Na przykład w układach automatyki przeznaczonych do pracy atmosferach wybuchowych stosuje się pneumatyczne układy logiczne.