Podręcznik

2. Układy kombinacyjne

2.5. Zadawanie funkcji boolowskiej

Tabelka prawdy. Najprostszym pojęciowo opisem funkcji boolowskiej jest tabelka prawdy czyli bezpośrednie podanie wartości funkcji dla wszystkich możliwych układów argumentów. Dla większej liczby argumentów jest to jednak metoda kłopotliwa. Wyobraźmy sobie bowiem tabelkę dla funkcji boolowskiej 16 czy 32 argumentowej.

Rozważmy funkcję boolowską $f:\{0,1\}^3\rightarrow\{0,1\}$ zadaną wyrażeniem boolowskim

$f(x_1,x_2,x_3)=\overline{x_1}\cdot\overline{x_2}\cdot\overline{x_3}+\overline{x_1}\cdot x_2\cdot\overline{x_3}+x_1\cdot\overline{x_2}\cdot\overline{x_3}+x_1\cdot \overline{x_2}\cdot x_3+x_1\cdot x_2\cdot x_3$

Tabelka prawdy jest dla tej funkcji następująca

$x_1$	$x_2$	$x_3$	$f(x_1,x_2,x_3)$
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Rys. 5. Tabelka prawdy opisująca pewną funkcję boolowską

Wyrażenie boolowskie. Wygodnie jest funkcję boolowską zadawać wyrażeniem boolowskim czyli forma boolowską.

Tablica Karnaugha. Kolejną stosowaną w praktyce metodą jest tablica Karnaugh. Jest to w gruncie rzeczy odmiana tabelki prawdy.

Tablica Karnaugha to często stosowany sposób opisu, zadawania funkcji boolowskiej z reguły niewielkiej liczby zmiennych 2,3,4,5. Tablice Karnaugh można również wykorzystywać do minimalizacji funkcji boolowskich (niewielkiej liczby zmiennych). Na przykład dla funkcji boolowskiej 4 zmiennych $f(x_1,x_2,x_3,x_4)=\overline{x_1}\cdot x_2 \cdot x_3 \cdot x_4$ konstruujemy tablicę Karnaugh następująco:

Wypisujemy wartości argumentów $x_1,x_2$ w pierwszej kolumnie, tak by stanowiły 2 bitowy kod Gray’a. Podobnie wypisujemy wartości argumentów $x_3,x_4$ w pierwszym wierszu, tak by stanowiły 2 bitowy kod Gray’a

Rys. 6. Tablica Karnaugh dla funkcji $f(x_1,x_2,x_3,x_4)=\overline{x_1}\cdot x_2 \cdot x_3 \cdot x_4$