Podręcznik

Układ kombinacyjny jest podstawowym układem logicznym umożliwiającym realizację funkcji boolowskich. Układ kombinacyjny konstruujemy z elementów logicznych po to, aby realizować funkcje lub ich zespoły opisujące bardziej skomplikowane układy cyfrowe. Dlatego rozważania o układach kombinacyjnych rozpoczynamy od pojęcia funkcji boolowskiej.

Pojęcie funkcji boolowskiej jest pojęciem podstawowym umożliwiającym modelowanie zjawisk fizycznych reprezentowanych jako odwzorowanie ciągów (wektorów) binarnych należących do zbioru X w ciągi binarne (wektory) ze zbioru Y, gdzie zbiory X, (Y) są podzbiorami n-krotnego, (m-krotnego) iloczynu kartezjańskiego zbioru B = {0, 1}.

Formalnie funkcją boolowską zmiennych binarnych x₁, …, x_n nazywamy odwzo­rowanie:

f: X ® Y, gdzie X Í Bⁿ, Y Í B^m.

Jeżeli X = Bⁿ, to funkcję taką nazywamy zupełną; w przeciwnym przypadku jest to funkcja niezupełna, zwana również funkcją nie w pełni określoną.

Najczęściej stosowane reprezentacje funkcji boolowskich to tablica prawdy oraz formuła (wyrażenie) boolowskie.

Funkcja f może być przedstawiona w postaci tablicy prawdy. Jest to tablica o n+1 kolumnach i 2ⁿ wier­szach. W kolejnych wierszach są zapisywane wszystkie wartości ciągu x₁, …, x_n, czyli wszystkie wektory x. W ostatniej kolumnie podana jest wartość y przyporządkowywana danemu wektorowi lub „–”, jeżeli funkcja dla tego wektora nie jest określona. Kolejne wektory są numerowane, przy czym wartość i podana z lewej strony w dodatkowej kolumnie jest dziesiętnym odpowiednikiem wektora x traktowanego jako liczba w zapisie dwójkowym:

$A_{D} =L( A_{NKB}) =\sum\limits ^{n-1}_{j=0} a_{j} \cdot 2^{j} =a_{n-1} \cdot2^{n-1} +\cdots +a_{2} \cdot2^{2} +a_{1} \cdot2^{1} +a_{0} \cdot2^{0}$

Na przykład przeliczenia liczb binarnych (0101)_B oraz (1010)_B (podanych w NKB – naturalnym kodzie binarnym) na liczby dziesiętne 5_D i 10_D dokonujemy następująco:

(0101)_B = 0 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = 5_D

(1010)_B = 1 × 2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰ = 10_D

Przykłady tablicowej reprezentacji funkcji boolowskiej podane są w tabl. 2.1a (funkcja zupełna) i tabl. 2.1b – funkcja niezupełna.

Tablica 2.1

Tablice te specyfikują funkcje boolowskie, których wektory wejściowe są dodatkowo określone liczbami dziesiętnymi. Stąd pomysł, aby specyfikacje funkcji boolowskich podawać w uproszczonej formie. Dla funkcji z tabl. 2.1a odpowiedni zapis powinien być:

f = S(1, 3, 5, 6, 7)

Natomiast funkcję z tabl. 2.1b zapisać należy z dodatkowym specyfikowaniem wektorów nieokreślonych:

f = S[1, 3, 5, 7, (2, 6)].

Rys. 2.1. Dekoder (a) wskaźnika siedmiosegmentowego (b)

Typowym zastosowaniem tablic prawdy do specyfikacji funkcji boolowskich może być opis deko­de­ra wskaźnika siedmiosegmen­towego pow­szechnie stosowanego do wyświetlania cyfr w urządzeniach pomiarowych i monitoru­jących. Deko­der taki to układ kombina­cyjny o wejściach x₃, x₂, x₁, x₀ oraz wyjściach a, b, c, ..., g (rys. 2.1a), odpowiadających segmentom wskaź­nika (rys. 2.1b). Na wejścia x podawane są liczby binarne 0000, 0001,...,1000,1001 (dziesiętnie: 0,1,...,8,9). Wyjścia a, b, c, ..., g sterują diodami świecącymi. Dioda zostaje podświetlona, gdy odpo­wiednie wyjście jest w stanie 1. W rezultacie działanie dekodera jest opisane tablicą prawdy, podaną w tablicy 2.2. W tym przypadku mamy do czynienia z funkcjami niezupełnymi. Jak się później przekonamy, omówiony dekoder nie nastręcza żadnych trudności w syntezie odpowiadającego im układu kombinacyjnego.

Tablica 2.2

Można jednak podać zastosowania bardziej skomplikowane. Na przykład układ kryptograficzny realizujący tzw. algorytm DES (Data Encryption Standard), jest wyposażony w klucze S, których działanie specyfikuje się funkcjami boolowskimi o 6 wejściach i 4 wyjściach. Przykładowa specyfikacja dla klucza S₁ jest podana w tablicy 2.3.

Tablica 2.3

Jeśli wejścia klucza S₁ oznaczymy x₁,...,x₆, a wyjścia y_1, y_2, y_3, y_4, to zapis w tablicy 2.3 rozumiemy następująco: dla wektora x = (000000) wyjścia y są liczbą binarną, której zapis dziesiętny jest L = 14 (czyli 1110), dla x = (000001), L = 4, wreszcie dla x = (111111), L = 13.

Funkcje boolowskie reprezentowane odwzorowaniem f, jakkolwiek możliwe do bezpośredniej realizacji technicznej, nie są najlepszą formą do zastosowań w strukturach bramkowych. Znacznie wygodniejsze w tym przypadku są reprezentacje funkcji w postaci wyrażeń boolowskich (formuł boolowskich). Ich zaleta wynika przede wszystkim z łatwej realizacji elementów logicznych zwanych bramkami logicznymi, które to elementy stanowią naturalną realizację wyrażeń boolowskich, gdzie występują w postaci operatorów.

Dla funkcji opisanej tablicą prawdy podaną w tabl. 2.1a odpowiednia formuła boolowska jest 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$

a jej realizacja na bramkach AND, OR, NOT pokazana jest na rys. 2.2.

W układzie kombinacyjnym z rys. 2.2 funkcja f, realizowana na jego wyjściu f, reprezentuje odwzorowanie z tabelki prawdy, co łatwo sprawdzić wprowadzając na wejścia układu odpowiednie wektory binarne i obliczając wartość uzyskaną na wyjściu y. Na przykład dla x₁ = x₂ = 0, x₃ = 1 na wyjściu bramki AND1 pojawi się sygnał o wartości 1, i w rezultacie wyjście y przyjmie wartość 1.

Natomiast dla x₁ = x₂ = x₃ = 0 na wyjściach wszystkich bramek AND będzie 0, a więc jednocześnie y przyjmie wartość 0, co jest zgodne z tablicą prawdy.

Rys. 2.2. Realizacja funkcji f: a) bezpośrednio, b) po uproszczeniu wg zasad algebry Boole’a

Niekwestionowaną zaletą formuł boolowskich jest możliwość ich upraszczania, a co zatem idzie możliwość uzyskiwania realizacji oszczędniejszych z punktu widzenia liczby bramek. Zasady formalne upraszczania formuł boolowskich związane są z prawami i własnościami algebry Boole’a. Stosując prawa algebry Boole’a, poprzednio podane wyrażenie na f można uprościć w sposób podany w następującym przykładzie.

Ostatecznie wyrażenie to można zrealizować w układzie kombinacyjnym, którego struktura – znacznie prostsza od poprzedniej realizacji – jest pokazana na rys. 2.2b.

Sens fizyczny minimalizacji i jej ogromne znaczenie praktyczne wynika z faktu, że oba układy: pierwotny i zminimalizowany działają identycznie. Zatem upraszczając wyrażenia boolowskie będziemy mogli jednocześnie uprościć ich realizację, np. zmniejszyć liczbę zastosowanych bramek co decyduje o kosztach realizacji i tym samym jest głównym czynnikiem zwiększającym konkurencyjność naszego produktu na rynku.

Zasygnalizowany tu proces upraszczania wyrażeń boolowskich ma ogromne znaczenie praktyczne i opracowano  dla jego potrzeb wiele zaawan­sowanych metod syntezy, które z technicznego punktu widzenia nazywa się metodami minimalizacji funkcji boolowskich. Wiele z nich doczekało się realizacji w postaci zaawansowanych narzędzi komputerowych i stanowi podstawę nowoczesnej syntezy logicznej.

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 {<b><i>w</i></b>₁, …, </span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black"><b><i>w</i></b><i>_i</i></span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">, …, <b><i>w</i></b><i>_r</i>} Í {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 {<b><i>x</i></b>₁, …, <b><i>x</i></b><i>_i</i>, …, <b><i>x</i></b><i>_r</i>} Í {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₃.

Omówione w poprzednich podrozdziałach zasady reprezentacji funkcji boolowskich są w praktyce projektowania układów cyfrowych bardziej sformalizowane. Stosowanie formalnych zasad specyfikacji funkcji boolowskich jest ważne ze względu na coraz powszechniejsze stosowanie komputerowych systemów projektowania. Zasady te – w przypadku języków opisu sprzętu – są mocno rozbudowane i przy założonej tematyce tego podręcznika mało istotne dla omawiania zaawansowanych algorytmów syntezy logicznej.

Z tych powodów ograniczymy się do tzw. standardu berkeley’owskiego stosowanego w komputerowym systemie Espresso [2.1].

Tablica 2.6

W tablicy 2.6 jest podana tablica prawdy funkcji boolowskiej reprezentującej działanie dekodera wskaźnika siedmiosegmentowego (por. tabl. 2.2). Istotą takiej reprezentacji (plik typu pla) jest specyficzny zapis nagłówka określającego:

.type fr – typ danych

.i  4 – liczba wejść

.o 7 – liczba wyjść

.p 10 – liczba wektorów (kostek)

Realizacje funkcji boolowskich

Dysponując różnymi bramkami logicznymi możemy realizować funkcje boolowskie w różnych strukturach. Do najbardziej typowych i najczęściej stosowanych należą:

realizacja AND-OR,

realizacja OR-AND.

Na rys. 2.3a pokazano realizację AND-OR funkcji opisanej wyrażeniem:

$y=x_1x_2+x_1{\bar{x}}_3+x_2{\bar{x}}_3$

Rys. 2.3. Realizacja AND-OR (a) i OR-AND (b)

Realizacja AND-OR jest bezpośrednim odwzorowaniem wyrażenia boolowskiego typu SOP (Sum of Product). Z kolei realizację OR-AND uzyskujemy z wyrażenia typu iloczyn sum. Na rys 2.3b pokazano realizację OR-AND funkcji opisanej wyrażeniem $y=\left(x_1+x_2\right)(\ x_1+{\bar{x}}_3)\left(x_2+{\bar{x}}_3\right)$

W dwuelementowej algebrze Boole'a wprowadza się też inne działania (operatory). Do najważniejszych z nich należą: zanegowana suma (NOR), zanegowany iloczyn (NAND), oraz suma wyłączająca (tzw. suma modulo 2 lub różnica symetryczna, oznaczana EXOR).

Określenia tych działań podano w tablicy 2.7, a odpowiednie symbole bramek na rys. 2.4.

Rys. 2.4. Symbole bramek NAND, NOR i EXOR

Tablica 2.7

Dysponując bramkami logicznymi NAND, NOR możemy realizować funkcje boolowskie w innych strukturach. Do najbardziej typowych i najczęściej stosowanych należą:

realizacja NAND,

realizacja NOR.

Realizację NAND uzyskujemy z wyrażenia typu suma iloczynów, które przekształcamy zgodnie z prawem De Morgana do postaci:

$y=\overline{\overline{x_1x_2}\cdot\overline{x_1{\bar{x}}_3}\cdot\overline{x_2{\bar{x}}_3}}$

Rys. 2.5. Realizacja NAND (a) i NOR (b)

Realizację NAND podano na rys. 2.5a.

Z kolei przekształcenie wyrażenia typu iloczyn sum wg prawa De Morgana:

$y=\overline{\overline{x_1{+x}_2}+\overline{x_1+{\bar{x}}_3}+\overline{x_2{+\bar{x}}_3}}$

bezpośrednio prowadzi do realizacji NOR, którą podano na rys. 2.5b.

Realizacje takie polegają na konfigurowaniu (programowaniu) matrycy AND-OR, która jest podstawowym elementem konstrukcyjnym układów PLD. Matryca AND-OR może być matrycą typu PAL (Programmable Array Logic), której cechą charakterystyczną jest programowalna matryca AND i stała matryca OR lub typu PLA (Programmable Logic Array), gdzie obie matryce, AND i OR są programowalne. Znaczy to, że PAL jest zespołem bramek iloczynowych dołączonych do oddzielnych bramek OR (rys. 2.6a), a w PLA każda bramka AND może być dołączona do dowolnej bramki OR (rys. 2.6b). Programowanie polega na realizacji połączeń w punktach styku linii poziomych i pionowych.

Całkowicie odmienne możliwości realizacji funkcji boolowskich powstały wraz z wprowadzeniem struktur programowalnych typu FPGA (Field Programmable Gate Array). Wynika to z faktu, że w układach FPGA typową strukturą jest prostokątna macierz elementów logicznych zwanych komórkami, rozmieszczonych w środowisku komutacyjnym kanałów połączeniowych.

Rys.  2.6. Matryca typu PAL (a) i typu PLA (b)

Komórka struktur FPGA jest zbudowana z uniwersalnego układu kombinacyjnego, umożliwiającego realizację dowolnej funkcji logicznej (zadanej tablicą prawdy) o kilku wejściach i jednym lub dwóch wyjściach. Z tych powodów taką komórkę nazywa się komórką typu  LUT (Look Up Table), a jednocześnie klasę układów zbudowanych z takich komórek nazywa się układami FPGA typu LUT. Dlatego realizacje w strukturach FPGA mają całkiem odmienne wymagania na struktury układów logicznych. Bezpośrednie odwzorowanie struktur bramkowych na komórki logiczne układów FPGA jest sprzeczne z naturą komórki o tyle, że z punktu widzenia syntezy jest ona przystoso­wana do realizacji dowolnej funkcji logicznej o argumentach wprowadzo­nych na jej wejścia. Z tych powodów dla struktur FPGA znacznie skuteczniejszą metodą syntezy okazuje się dekompozycja funkcji boolowskich, której istotą jest synteza funkcji boolowskich w strukturach wielopoziomowych złożonych z kompo­nentów w postaci bloków logicznych typu LUT specyfikowanych pierwot­nymi tablicami prawdy.

Tablica 2.8

Rys. 2.7. Realizacja funkcji f z tab. 2.8

Na przykład funkcję podaną w tablicy 2.8 można zrealizować w strukturze FPGA, jeśli tylko bloki g i h realizują odwzorowania podane w tablicach 2.9a i 2.9b, co pokazano na rys. 2.7. Można sprawdzić, że dla każdego wektora złożenie funkcji g oraz h wytwarza na wyjściu h = f  tę samą wartość.

Tablica 2.9

Mimo swoich niedoskonałości metoda Karnaugha jest najczęściej wykładaną metoda minimalizacji funkcji boolowskich. Paradoksalnie to co jest jej wadą – prostota – jest jednocześnie jej zaletą, gdyż można szybko ją „opanować” i stosować w obliczeniach ręcznych. Należy jednak pamiętać, że w praktyce projektowania inżynierskiego metoda tablic Karnaugha jest absolutnie nieprzydatna, gdyż zakres jej zastosowań kończy się na funkcjach 6 – 7 argumentów, a typowe zadania praktyczne operują funkcjami o kilkudziesięciu argumentach.

Rys. 2.8. Zasada sklejania

W metodzie Karnaugha każda kratka odpowiedniej tablicy (zwanej tablicą Karnaugha) odpowiada wektorowi zmiennych binarnych. Można więc powiedzieć, że ciąg wartości tych zmiennych tworzy adres kratki. Kratki są ponumerowane w taki sposób, że numer i jest liczbą dziesiętną odpowiadającą kombinacji zmiennych (wektorowi zero-jedynkowemu) traktowanej jako liczba dwójkowa. W poszczególnych kratkach wpisane są wartości funkcji, tj. 0 lub 1 przyjmowanej przez funkcję dla tej kombinacji lub symbol „–”, jeżeli funkcja nie jest określona (rys. 2.8). W tablicy Karnaugha różniącym się tylko o negację pełnym iloczynom przyporządkowane są leżące obok siebie pola tablicy (sąsiednie kratki), które się łączy (skleja) odpowiednią pętelką. Korzysta się z faktu, że dla dowolnego $A,A\bar{x}+Ax=A$.

Dla uzyskania efektu sąsiedztwa współrzędne pól opisuje się tzw. kodem Gray’a. Kod Gray’a jest takim ciągiem wektorów binarnych, w którym każde dwa sąsiednie wektory różnią się wyłącznie na jednej pozycji. Przykłady kodu Gray’a dla dwóch i trzech zmiennych podane są w tabl. 2.10.

Tablica 2.10

Minimalizacja metodą Karnaugha polega na wykonaniu dwóch czynności:

1. wpisanie funkcji do tablicy,
2. zakreślanie pętelek i kojarzenie z nimi iloczy­nów zmiennych prostych i zanegowanych.

Wpisywanie funkcji do tablicy Kar­naugha ułatwia numeracja kratek. Na rys. 2.9 podajemy przykłady tablic Karnaugha z ponu­merowanymi kratkami według naturalnego kodu binarnego (NKB), odpowiednikami. Wzorce tych tablic ułatwiają znajdowanie kratek odpowiadających wektorom w tablicy prawdy.

Rys.  2.9. Przykłady tablic z ponumerowanymi kratkami

Niestety zakreślanie pętelek i kojarzenie z nimi odpowiednich iloczynów jest trudniejsze. Omawiamy ten proces na bardziej skomplikowanym przykładzie (rys. 2.10), w którym dla poszczególnych kopii tablicy Karnaugha trzech zmiennych zaznaczamy pola odpowiadające pojedynczym zmiennym (prostym i zanegowanym). Pokrywanie się tych pól określa odpowiedni iloczyn zmiennych prostych

Rys. 2.10. Ilustracja minimalizacji funkcji boolowskiej

Minimalizacja funkcji za pomocą tablic Karnaugha sprowadza się do wykonania czynności opisanych w następującym algorytmie.

Algorytm 2.1

1) Wpisujemy funkcję do tablicy Karnaugha.

2) Zakreślamy pętelki.

a) Pętelki zakreślamy wokół grup sąsiadujących kratek zawierających „1” albo „1” i „–” (kreski).

b) Liczba kratek objętych pętelka musi wynosić: 1, 2, 4, …,2^k.

c) Staramy się objąć pętelką jak największą liczbę kratek.

3) Pętelki zakreślamy tak długo, aż każda „1” będzie objęta co najmniej jedną pętelką, pamiętając o tym aby pokryć wszystkie „1” możliwie minimalną liczbą pętelek.

4) Z każdą pętelką kojarzymy iloczyn zmiennych prostych lub zanegowanych. Suma tych iloczynów, to minimalne wyrażenie boolowskie danej funkcji.

Przykład 2.4 posłuży teraz do wprowadzenia jednego z najważniejszych pojęć minimalizacji jakim jest implikant.

Na przykład ${\bar{x}}_1x_3x_4$ jest implikantem funkcji f, bo zbiór wektorów reprezentowanych przez ten implikant: 0111 oraz 0011 nie zawiera żadnego wektora (mintermu), dla którego wartość funkcji jest 0. Są to bowiem mintermy, które w naturalnym kodzie binarnym odpowiadają liczbom 7 i 12, i jak widać z zapisu funkcji  f = S[0, 5, 6, 7, 10, (2, 3, 11, 12)], nie należną one do zbioru wektorów „zerowych” tej funkcji.

Pojęcie implikantu można zinterpretować na tablicy Karnaugha. W tablicy 2.16 zakreślono dwie pętelki. Mniejsza odpowiada implikantowi ${\bar{x}}_1x_3x_4$. Nie może to być implikant prosty, gdyż pętelkę tę można powiększyć. Większej pętelce odpowiada implikant prosty ${\bar{x}}_1x_3$, w którym nie można już usunąć żadnego literału.

Tablica 2.16

W dotychczasowych przykładach minimalizowane były pojedyncze funkcje boolowskie, dla których – w celu uzyskania rozwiązania z minimalnym kosztem – two­rzo­ne były wyłącznie implikanty proste. W ogól­nym przypadku minimalizacji zespołów funkcji boolowskich tworzenie minimalnego rozwiązania wyłącznie na podstawie impli­kantów prostych nie zawsze prowadzi do najlepszego rezultatu końcowego. Problem sygnalizuje przykład 2.8.

Przykład sugeruje, że w realizacji zespołu funkcji stosowanie minimalnej sumy implikantów prostych nie zawsze prowadzi do rozwiązania z minimalnym kosztem. Kolejny przykład ilustruje w jaki sposób należy dobierać implikanty zespołu funkcji, aby uzyskać rozwiązanie z minimalnym kosztem.

W metodzie systematycznej zbiór wektorów (w ogólności kostek), dla których funkcja f = 1 oznacza się F. Natomiast zbiór tych wektorów (kostek), dla których funkcja f = 0 oznacza się R.

W tabl. 2.21 przedstawiono tablicę prawdy funkcji boolowskiej 7-argumentowej. Funkcję tę w dalszej części wykładu oznaczać będziemy EXTL. Wektory zbioru F oznaczono symbolami k₁, …, k₅.

Tablica 2.21

Metoda systematyczna jest procesem działającym na kostkach zbiorów F i R, a jej celem jest uzyskanie dla danej k Î F kostki k' tak dużej, jak to tylko możliwe (tzn. z możliwie dużą liczbą pozycji o wartości *) i nie pokrywającej żadnego wektora zbioru R. W swoich obliczeniach metoda ta wykorzystuje tzw. macierz blokującą B.

Macierzą blokującą (kostkę k) nazywać będziemy macierz:

B(k,R) = [b_ij],              1 £ i £ ÷R÷,                  1 £ j £ n,

w której każdy element b_ij Î {0,1} jest definiowany następująco:

b_ij = 1, jeśli k_j = 1 oraz r_ij = 0 lub k_j = 0 oraz r_ij = 1;

b_ij = 0, w pozostałych przypadkach.

W przypadku funkcji opisanej wektorami binarnymi macierz blokująca dla danej kostki k Î F powstaje z macierzy R przez zanegowanie tych kolumn R, których pozycje są wyznaczone przez pozycje jedynek w kostce k Î F.

Macierz blokująca B(k, R) pozwala wyznaczyć uogólnioną kostkę k oznaczaną k⁺(L, k) w sposób następujący:

$k^{+}( L,k) =\begin{cases} k_{j}\text{, gdy} \ j\in L\\ *\text{, w pozostałych przypadkach} \end{cases}$

Uogólnioną kostkę k⁺(L, k) nazywa się również ekspansją kostki k, co oznacza, że wszystkie składowe kostki k należące do L nie ulegają zmianie, natomiast składowe nie należące do L przyjmują wartość *.

Można wykazać, że k⁺(L, k) jest implikantem funkcji f = (F, R). W szczególności k⁺(L, k) jest implikantem prostym, gdy L jest minimalnym pokryciem kolumnowym macierzy B(k, R). Wykorzystując pojęcie macierzy blokującej można obliczyć implikanty proste dla poszczególnych kostek zbioru F.

Każdy z obliczonych w ten sposób implikantów może zastąpić (często mówimy pokrywa) wiele innych kostek pierwotnych funkcji f, gdzie relację pokrycia definiujemy następująco:

K Í K’  (K’  pokrywa K)  wtedy i tylko wtedy, gdy $k_i=k_i^\prime\ lub\ k_i=\ast\ $ dla każdego i, 1 £ i £ n,

gdzie: K = (k₁, …, k_n) i $K^\prime=\left(k_1^\prime,\ldots,k_n^\prime\right),$

Na przykład obliczony wyżej implikant  pokrywa kostki k₂, k₃, k_4, co zapisujemy formalnie:

$\ {\bar{x}}_4{\bar{x}}_7$Ê k₂, k₃, k₄.

Relacja pokrycia dla kostek i sposób postępowania omówiony w przykładzie 2.12 nasuwa pomysł  systematycznej metody obliczania minimalnych realizacji funkcji boolowskich.

Kolejne etapy takiej metody są następujące.

1. Dla każdej k_i  należącej do zbioru  F  obliczyć macierz blokującą.
2. Wyznaczyć wszystkie minimalne pokrycia kolumnowe tej macierzy.
3. Wyznaczyć wszystkie implikanty proste.
4. Obliczyć sumę zbiorów implikantów prostych generowanych przez poszczególne kostki.
5. Z tak utworzonego zbioru wszystkich implikantów prostych usunąć implikanty powtarzające się.
6. Spośród obliczonych implikantów prostych wyselekcjonować minimalny podzbiór implikantów pokrywający wszystkie kostki zbioru  F.

Niezależnie jednak od metody ograniczania liczności zbioru implikantów prostych proces ich selekcji wykonuje się za pośrednictwem tzw. tablicy implikantów prostych.

Tablica implikantów prostych jest to tablica elementów binarnych 0 lub 1, o liczbie wierszy równej liczbie kostek zbioru F oraz liczbie kolumn równej liczbie wyznaczonych implikantów prostych funkcji f.

Tablicę implikantów prostych konstruujemy w następujący sposób. Jeśli implikant I_j pokrywa kostkę k_i, to na przecięciu wiersza k_i z kolumną I_j piszemy 1, w przeciwnym przypadku piszemy 0.

Tablica implikantów prostych umożliwia wybór (selekcję) takiego minimalnego zbioru implikantów, który pokrywa wszystkie kostki funkcji pierwotnej.

Minimalny zbiór implikantów prostych reprezentujących funkcję f można wyznaczyć obliczając minimalne pokrycie kolumnowe tablicy implikantów prostych. W tym celu tworzymy wyrażenie CNF,

I₂ (I₁ + I₄) (I₂ + I₃ + I₅) (I₄ + I₅), które po oczywistych uproszczeniach zamieniamy na DNF: I₂I₄ + I₁I₂I₅

Zatem minimalne pokrycie tworzą implikanty I₂, I₄. Czyli,

$f={\bar{x}}_4{\bar{x}}_7+x_2{\bar{x}}_6$

Obliczeniem decydującym o eksplozji kombinatorycznej zadania minimalizacji funkcji boolowskiej jest obliczenie wszystkich pokryć kolumnowych tablicy implikantów prostych. O złożoności tego problemu decyduje szybko rosnąca (ze wzrostem liczby argumentów) liczność rodziny tych implikantów.

Otóż w przypadku funkcji z tablicy 2.21 liczba wszystkich implikantów jest 5:  tym samym odpowiednia tablica implikantów (tabl. 2.22) ma 5 kolumn. W rezultacie obliczenie minimalnych pokryć kolumnowych tej tablicy można wykonać „ręcznie” – jest widoczne „gołym okiem”. Ale nie zawsze tak musi być. Zjawisko występującej w tym problemie złożoności obliczeniowej lepiej wyjaśni następny przykład, którego wyniki obliczono programem InstantRS.