046 047

tym

Nie należy także wykonywać wszystkich możliwych sklejeń, 'tzn. w przypadku składników 21 3, 317, 415 ora* 5 1 7, bo otrzymamy

y —    ^ ^X2^X3 * ^X1^X2 ^xi^x3

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

y = x₁x₂ + x₁x₂ + x₁x_J

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ę, że amplikant pokrywa (część lub wszystkie) jedynki funkcji f.

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

Przykład 2.3

Zbadać czy funkcja XgXj jest Impllkantem prostym funkcji

1*3 + ^X1^X2

f = x„

Przedstawimy w tabeli podane funkcje oraz funkcje x₂ i

Xj wynikające z

^X1 ^xl^xJ	*1V*I ^XI	^xl^x3	^xl	^xł
1 1 1	1	•	t	1
1 1 1	1	1	1	1
0 1 i	1	t	t	1
1 1 1		1	1	1
t 1 1	1	1	1	1
t 1 1 t 1 1	1 1	1 !	1 1	1 1

pomniejszenia o jedną zmienną Iloczynu (patrz rys. 2.2).

Z tabeli widać, że gdy funkcja *₂^X3 przyjmuje wartość 1, to funkcja f też przyjmuje wartość 1, z czego wynika, że ^X2^X3 jest Impllkantem tej funkcji. Ponadto, po-

jest iloczynem oraz funkcja x₅

nieważ

i funkcja Xj nie są implikantaml funkcji f, więc x₂Xj jest impllkantem prostym funkcji 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ć

Rys.

2.2. Tabela do przykładu 2.3

^X2^X3

n

(2.3)

2>i

gdzie: g - implikant prosty.

Postać (2.3) nazywana jest postacią skróconą funkcji logicznej. Znale- ■ zienie postaci skróconej jest istotnym etapem minimalizacji, ponieważ otny-many 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 jed-jj nak jeszcze postać minimalna, bowiem niektóre z implikantów prostych mogą być zbędne, gdyż pozostałe pokrywają wszystkie jedynki funkcji. Dlategot 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 KPI. 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 impllcentem 1 która zmniejszona o dowolną zmienną przestaje być lmpllcentem.

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

f = n    (2.4)

i-i ¹

gdzie h - Impllcent prosty.

Postać (2.4) zwana jest też postacią skróconą funkcji logiczneJponieważ otrzymamy 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 lmplicentó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 im-plicentów.

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

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 (lmplicentów) prostych, czyli minimalnej postaci funkcji, dokonuje się w tzw. tablicy implikantów (impllcentów). Pokazuje ona pokrycie Jedynek (zer) funkcji przez poszczególne implikanty (impllcenty) i w związku z tym wskazuje, które z impli-kantów (impllcentów) są zbędne.

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

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

y = ^    ⁺ ^-i^x2^x3 ^{+ x}-]^x2^x3 ^{+ x}i ^x2^x3 ^{+ X}1^X2^X3

otrzymaliśmy

y = x₁x₂ + x₂Xj + x₁x₂ + x₁ij

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

1

Ponieważ metody prowadzące do minimalnych postaci NPS i NPI są analogiczne, omawiamy je jednocześnie podając w nawiasach terminologię występującą przy przekształcaniu ZNPI w minimalną NPI.