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<n\) 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<n\) 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<0,2^n-1>\). \(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.