046 047

46

Nie należy także wykonywać wszystkich możliwych sklejeń, tzn. w "tym przypadku składników 2 1 5, 3 1 7, ł i 5 oraz 5 17, bo otrzymamy

y —    + ^x2^x3 ⁺ X1^Z2 ^ *<|*3

Należy skleić składniki 2 i 3, 4 i 5 oraz 517 otrzymując

y = x_/)x₂ + x₁x₂ + x₁Xj

co jest postacią minimalną.    '    #

Obecnie spróbujemy spojrzeć bardziej ogólnie na proces minimalizacji i podamy metody postępowania pozwalające automatycznie znaleźć postać minimalną funkcji. W tym celu wprowadzimy dwa następujące określenia.

Implikant funkcji f to taka funkcja g, że jeżeli g = 1, to f = 1. Mówi się, te amplikant pokrywa (część lub wszystkie) jedynki funkcji f.

Implikant prosty to iloczyn zmiennych, który jest implikantem 1 który zmniejszony o dowolną zmienną przestaje być implikantem.

Przykład 2>3

Zbadać czy funkcja *2*3 3^est implikantem prostym funkcji

12

f =

Przedstawimy w tabeli podane funkcje oraz funkcje x₂ i Xj wynikające z

*1 *t*J	*1 V*I^XZ	XjXj	^xi	^x5
1 1 1	1	•	t	1
1 1 1	1	1	1	1
0 1 t	1	t	t	1
1 t 1	1	1	1	I
f 1 1	1	1	1	1
t 1 1	t	1	1	1
1 1 1 t 1 1	1 1	1 t	1 1	1 1

pomniejszenia o jedną zmienną iloczynu jycj (patrz rys. 2.2).

Z tabeli widać, że gdy funkcja x₂x^ przyjmuje wartość 1, to funkcja f też przyjmuje wartość 1, z czego wynika, że ^X2^X3 jest implikantem tej funkcji. Ponadto, ponieważ *2*3 dest iloczynem oraz funkcja x₂ i funkcja x^ nie są implikantami funkcji f, więc x₂Xj Jest implikantem prostym funk-

Rys. 2.2. Tabela do przykła- cji f.    tt

Jest oczywiste, że każda funkcja może być przedstawiona v: postaci sumy wszystkich prostych implikantów (postać NPS) pokrywających wszystkie jedynki funkcji, co można zapisać

^f*2>i

i * i

gdzie: g - implikant prosty.

Postać (2.3) nazywana jest postacią skróconą funkcji logicznej. Znalezienie postaci skróconej jest Istotnym etapem minimalizacji, ponieważ otrzymany zapis funkcji składa się z sumy iloczynów, z których żaden nie daT się już uprościć przez eliminację którejś ze zmiennych. Nie jest to jednak jeszcze postać minimalna, bowiem niektóre z implikantów prostych mogą być zbędne, gdyż pozostałe pokrywają wszystkie jedynki funkcji. Dlatego też drugim etapem procesu minimalizacji jest usuwanie zbędnych implikantów. Po tym etapie otrzymujemy funkcję w minimalnej NPS.

Poniżej omówimy analogiczny proces prowadzący do minimalnej NPI. W tym celu wprowadzimy dwa określenia.

Impllcent funkcji f to taka funkcja h, że Jeżeli h = 0, to f = 0.

Impllcent prosty to suma zmiennych, która jest implicentem i która zmniejszona o dowolną zmienną przestaje byó implicentem.

Jest oczywiste, że każda funkcja może byó przedstawiona w postaci iloczynu wszystkich prostych implicentów (postać NPI) pokrywających wszystkie zera funkcji, co można zapisaó

f = 11 h.    (2.4)

i-i ¹

gdzie h - impllcent prosty.

Postać (2.4) zwana Jest też postacią skróconą funkcji logicznej.ponieważ otrzymany zapis składa się z iloczynu sum, z których żadna nie da się Już uprościć przez eliminacje którejś -ze zmiennych. Nie Jest to jednak jeszcze postać minimalna, bowiem niektóre z implicentów prostych mogą być zbędne, gdyż pozostałe pokrywają wszystkie zera funkcji. Dlatego też końcowym etapem tej wersji procesu minimalizacji jest usuwanie zbędnych implicentów.

Poniżej przedstawiamy dwie metody minimalizacji realizujące oba omówione etapy, zarówno gdy postacią końcową funkcji jest NPS, Jak i NPI.

2.1.1. Metoda Qulne'a-Mc Cluskey'a

W metodzie tej do wyjściowej postaci funkcji (ZNPS lub ZNPI) stosujemy wielokrotnie regułę sklejania (2.1 lub 2.2) dokonując wszystkich możliwych sklejeń. Otrzymujemy w ten sposób postać skróconą, ponieważ otrzymane iloczyny (sumy)^ są Już nieskracalne (gdyby się dały jeszcze skrócić, to byśmy Je skrócili stosując ponownie regułę sklejania).

Poszukiwanie minimalnego zbioru implikantów (implicentów) prostych, czyli minimalnej postaci funkcji, dokonuje się w tzw. tablicy implikantów (implicentów). Pokazuje ona pokrycie jedynek (zer) funkcji przez poszczególne implikanty (Implicenty) i w związku z tym wskazuje, które z implikantów (implicentów) są zbędne.

Przykład 2,2 (c.d.)

Dokonując wszystkich możliwych sklejeń w wyrażeniu

y =    + ^x-j^x2^xj

otrzymaliśmy

y = ^x.j^x2 ^{+ X}2^X3 ^{+ x}1^x2 ^{+ X}1^X3

Eliminację zbędnych implikantów przeprowadza się w tablicy, której kolumny opisuje się składnikami ZNPS, a wiersze otrzymanymi impllkantamt

Ponieważ metody prowadzące do minimalnych postaci NPS i NPI są analogiczne, oma-wiaoy ja jednocześnie podając w nawiasach terminologię występującą przy przekształ-^Cflniu ZNPI w minimalną NPI.