Podręcznik: Postacie kanoniczne funkcji boolowskiej n-zmiennych

2. Układy kombinacyjne

2.3. Postacie kanoniczne funkcji boolowskiej n-zmiennych

Wyrażenie boolowskie (lub forma boolowska) to formalnie poprawnie zbudowany opis funkcji boolowskiej f zawierający wprowadzone w algebrze Boole’a działania i nawiasy opisujące kolejność wykonywanych działań na wprowadzonych zmiennych (argumentach funkcji $f$ ). Najczęściej w tworzonych zapisach bierzemy dodatkowo pod uwagę następujący priorytet wykonywanych działań: negacja ma największy priorytet, potem mnożenie a potem dodawanie.

Iloczyn pełny $n$ zmiennych (inaczej minterm) to iloczyn zawierający $n$ różnych zmiennych zanegowanych lub nie. Minterm dla $n$ zmiennych (lub dla $n$ argumentów) jest funkcją przyjmująca wartość 1 tylko dla jednego układu argumentów $x_1,x_2,...,x_n$ .

Iloczyn niepełny $n$ zmiennych to iloczyn zawierający $m$ różnych zmiennych zanegowanych lub nie.

$f(x_1,x_2,x_3)=\overline{x_1} \cdot x_2 \cdot x_3$ jest iloczynem pełnym 3 zmiennych

Suma pełna $n$ zmiennych (inaczej maksterm) to suma zawierająca $n$ różnych zmiennych zanegowanych lub nie. Maksterm dla $n$ zmiennych (lub dla $n$ argumentów) jest funkcją przyjmującą wartość 0 tylko dla jednego układu argumentów $x_1,x_2,...,x_n$ .

Suma niepełna $n$ zmiennych to iloczyn zawierający $m$ różnych zmiennych zanegowanych lub nie.

$f(x_1,x_2,x_3)=\overline{x_1}+x_2+x_3$ jest sumą pełną 3 zmiennych

Postać normalna sumacyjna (inaczej postać normalna dysjunkcyjna) funkcji boolowskiej $n$ zmiennych $f$ to opis funkcji w postaci sumy iloczynów pełnych lub niepełnych.

Postać normalna iloczynowa (inaczej postać normalna koniunkcyjna) funkcji boolowskiej $n$ zmiennych $f$ to opis funkcji w postaci iloczynu sum pełnych lub niepełnych.

Implikant. Funkcja boolowska $g:\{0,1\}^n \rightarrow \{0,1\}$ implikuje inną funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}$ jeśli dla każdego układu $x=(x_1,x_2,...,x_n) \in \{0,1\}^n$ takiego, że $g(x)=1$ mamy $f(x)=1$ . Funkcję $g$ nazywamy implikantem funkcji $f$ .

Niech

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

$g(x_1,x_2)=\overline{x_1}$ jest implikantem funkcji

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

Jeśli funkcja boolowska

$f$ przedstawiona jest w postaci normalnej sumacyjnej, to każdy iloczyn lub suma iloczynów występujących w tym przedstawieniu jest implikantem tej funkcji.

Implikant prosty funkcji boolowskiej $n$ zmiennych zapisanej w postaci normalnej sumacyjnej to iloczyn $m$ różnych zmiennych (ewentualnie zanegowanych), $m \leq n$ będący implikantem funkcji $f$ posiadający tę własność, że po usunięciu jakiejkolwiek zmiennej z tego iloczynu, tak powstała funkcja przestaje być implikantem funkcji $f$ .

Dla każdej funkcji boolowskiej spełniona jest oczywista (proste sprawdzenie) ale pożyteczna równość:

$f(x_1,x_2,...,x_n)=\overline{x_1}f(0,x_2,...,x_n)+x_1f(1,x_2,...,x_n)$

Jest to tzw. wzór na rozłożenie sumacyjne funkcji boolowskiej.

Podobnie uzyskujemy wzór

$f(x_1,x_2,...,x_n)=(\overline{x_1}+f(1,x_2,...,x_n))(x_1+f(0,x_2,...,x_n)$

Jest to tzw. wzór na rozłożenie iloczynowe funkcji boolowskiej.

Stosując wielokrotnie ( $n$ krotnie) wzór na rozłożenie sumacyjne funkcji boolowskiej otrzymujemy następujące twierdzenie o postaci kanonicznej sumacyjnej (lub dysjunkcyjnej).

Twierdzenie (o postaci kanonicznej sumacyjnej):

Każdą funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}$ można przedstawić jednoznacznie w postaci sumy implikantów prostych

$f(x_1,x_2,...,x_n)=\sum\limits ^{2^{n} -1}_{k=0} \alpha _{k} \cdot I_k(x_1,x_2,...,x_n)$

(*)

gdzie $\alpha_k=f(k_{n-1},k_{n-2},...,k_0)$ a $k_{n-1}k_{n-2}...k_0$ jest $n$ bitowym zapisem NKB liczby $k\in$ . $I_k(x_1,x_2,...,x_n)$ jest ( $n$ -argumentowym) mintermem o numerze $k$ , tzn. funkcją postaci $I_k(x_1,x_2,...,x_n)=\overline{x_1}\cdot x_2 \cdot...\cdot x_n$ , gdzie negacje lub ich brak odpowiada liczbie $k$ w taki sposób: umieszczamy ciąg bitów $k_{n-1}k_{n-2}...k_0$ nad zmiennymi $x_1,x_2,...,x_n$ i tam gdzie nad zmienną stoi 0, wpisujemy negację, a tam gdzie stoi 1, nie wpisujemy negacji.

Równość (*) to tzw. kanoniczna postać sumacyjna (dysjunkcyjna) funkcji boolowskiej $f(x_1,x_2,...,x_n)$ .

Podobnie jak wprowadzamy kanoniczną postać sumacyjną można wprowadzić kanoniczną postać iloczynowi (koniunkcyjną) i wykazać twierdzenie o postaci kanonicznej iloczynowej.