Podręcznik: Formy kanoniczne funkcji boolowskich

2. Formy kanoniczne funkcji boolowskich

Niech wektorowi w = (x₁, …, x_j, …, x_n) odpowiada następujące wyrażenie zapisane w formie iloczynu zmiennych prostych i zanegowanych:

$x_1^{e_1}\ldots\ x_j^{e_j}\ldots\ x_n^{e_n},$

gdzie $x_j^{e_j}=\left\{\begin{matrix}{\bar{x}}_j\ \ \ dla\ e_j=0\\x_{j\ \ \ \ }dla\ e_j=1\\\end{matrix}\right.$

Oznacza to, że składowej 0 wektora odpowiada w iloczynie zmienna zanegowana, a składowej 1 – zmienna prosta. Iloczyn taki nazywamy iloczynem pełnym, gdyż zawiera on wszystkie zmienne. Iloczyn pełny przyjmuje wartość 1 tylko dla tych wektorów w tablicy prawdy funkcji, dla których wartość funkcji jest 1; dla innych wektorów wartość jego wynosi 0. Iloczyn pełny będziemy także oznaczać P_i.

Zbiorowi wektorów {w1, …, wi, …, wr} Í {0,1}ⁿ, gdzie dla każdego i, f(w_i)=1, odpowiada wyrażenie:

$F( x_{1} ,\dotsc ,x_{n}) =\sum\limits ^{2^{n} -1}_{i=0} P_{i} f( i)$

Jest to tzw. kanoniczna postać sumy. Stanowi ona sumę wszystkich iloczynów pełnych mnożonych przez wartość funkcji dla kombinacji i. W wyrażeniu tym pozostają w efekcie te iloczyny (tzw. mintermy), którym odpowiada wartość funkcji 1; iloczyny, którym odpowiada wartość funkcji 0, znikają. Kanoniczną postać sumy można utworzyć bezpośrednio z tablicy prawdy przez wybranie wierszy, dla których wartość funkcji wynosi 1, utworzenie dla każdego takiego wiersza iloczynu pełnego, oraz utworzenie sumy iloczynów pełnych.

Kanoniczna postać sumy funkcji z tabl. 2.1a jest zatem następująca:

$f={\bar{x}}_1{\bar{x}}_2x_3+{\bar{x}}_1x_2x_3+x_1{\bar{x}}_2x_3+x_1x_2{\bar{x}}_3+x_1x_2x_3$

Postępowanie dualne prowadzi do tzw. kanonicznej postaci iloczynu. Wektorowi w_i = (x₁, …, x_j, …, x_n), gdzie f(w_i) = 0, odpowiada następujące suma logiczna:

$x_1^{e_1}+\ldots+x_j^{e_j}+\ldots{+x}_n^{e_n},$

gdzie $x_j^{e_j}=\left\{\begin{matrix}x_{j\ \ \ \ }\ dla\ e_j=0\\{\bar{x}}_j\ \ dla\ e_j=1\\\end{matrix}\right.$

Oznacza to, że składowej 0 wektora odpowiada w sumie zmienna prosta, a składowej 1 – zmienna zanegowana. Suma taka nazywa się sumą pełną, gdyż zawiera ona wszystkie zmienne w postaci prostej lub zanegowanej. Suma pełna przyjmuje wartość 0 dla wektora x_i; dla innych wektorów wartość jej wynosi 1. Sumę pełną będziemy także oznaczać S_i.

Zbiorowi wektorów {x1, …, xi, …, xr} Í {0,1}ⁿ, gdzie dla każdego i, f(x_i) = 0, odpowiada iloczyn:

$F( x_{1} ,\dotsc ,x_{n}) =\prod\limits ^{2^{n} -1}_{i=0}( S_{i} +f( i))$

Wyrażenie to stanowi iloczyn zawierający wszystkie sumy pełne z dodanymi wartościami funkcji dla kombinacji i. Te sumy S_i, dla których f(i) = 1, znikają; zostają sumy (tzw. maxtermy) z f(i) = 0.

Jest to tzw. kanoniczna postać iloczynu, której interpretacja za pomocą funkcji z tabl. 2.1a jest następująca:

$f=\left(x_1+x_2+x_3\right)\left(x_1+{\bar{x}}_2+x_3\right)\left({\bar{x}}_1+x_2+x_3\right)$

W tym przypadku synteza funkcji sprowadza się do wybrania wierszy, dla których wartość funkcji wynosi 0, utworzenia dla każdego takiego wiersza sumy pełnej oraz utworzenia iloczynu sum pełnych.

Należy mieć świadomość, że kanoniczna postać iloczynu może być uproszczona w analogiczny sposób jaki stosowaliśmy przy uproszczeniu kanonicznej postaci sumy tej funkcji. Stosując zasady algebry Boole’a łatwo sprawdzić, że funkcję tę, zapisaną w postaci iloczynu sum reprezentuje następujące wyrażenie:

$f=\left(x_1+x_3\right)\left(x_2+x_3\right)$

Tablica 2.4

W tablicy 2.4 zestawiono dla przykładu wszystkie iloczyny pełne i sumy pełne dla trzech zmiennych x₁, x₂, x₃.

Dla funkcji f₁ = S[0, 1, 2, 5, 8, 9, 10, (4, 12, 13)] podanej w tablicy 2.5 odpowiednie wyrażenie boolowskie wg kanonicznej postaci sumy jest:

Tablica 2.5

i	x₁	x₂	x₃	x₄	f₁	f₂
0	0	0	0	0	1	1
1	0	0	0	1	1	–
2	0	0	1	0	1	1
3	0	0	1	1	0	–
5	0	1	0	1	1	1
6	0	1	1	0	0	0
7	0	1	1	1	0	1
8	1	0	0	0	1	0
9	1	0	0	1	1	–
10	1	0	1	0	1	0
11	1	0	1	1	0	–
13	1	1	0	1	–	1
14	1	1	1	0	0	0
15	1	1	1	1	0	1

$\begin{array}{{>{\displaystyle}l}} f_{1} =\overline{x}_{1}\overline{x}_{2}\overline{x}_{3}\overline{x}_{4} +\overline{x}_{1}\overline{x}_{2}\overline{x}_{3} x_{4} +\overline{x}_{1}\overline{x}_{2} x_{3}\overline{x}_{4} +\overline{x}_{1} x_{2}\overline{x}_{3} x_{4} +x_{1}\overline{x}_{2}\overline{x}_{3}\overline{x}_{4} \ +\\ +x_{1}\overline{x}_{2}\overline{x}_{3} x_{4} +x_{1}\overline{x}_{2} x_{3}\overline{x}_{4} \end{array}$

Kolejne iloczyny odpowiadają i = 0, 1, 2, 5, 8, 9, 10.

Natomiast dla funkcji f₂ = Õ[6, 8, 10, 14, (1, 3, 4, 9, 11, 12)] kanoniczna postać iloczynu jest następująca:

$f_2=\left(x_1+{\bar{x}}_2{+\bar{x}}_3+x_4\right)\left({\bar{x}}_1+x_2{+x}_3+x_4\right)\left({\bar{x}}_1{+x}_2+{\bar{x}}_3+x_4\right)\left({\bar{x}}_1{+\bar{x}}_2{+\bar{x}}_3+x_4\right)$

Kolejne sumy odpowiadają i = 6, 8, 10, 14.