I.5. A LOGIKAI FÜGGVÉNYEK EGYSZERŰSÍTÉSE (MINIMALIZÁCIÓ) Nem mindegy, hogy a logikai függvényeket mennyi erőforrás felhasználásával valósítjuk meg. Előnyös, ha kevesebb logikai kaput alkalmazunk ugyanarra a feladatra, illetve, ha csökkenteni tudjuk az egyes részfüggvények bemeneti változóinak számát. 1
Elsőként az algebrai lehetőségeket tekintjük át, majd a Karnaugh féle grafikus egyszerűsítési módszerrel ismerkedünk meg. Ez utóbbinak ma szinte csak pedagógiai jelentősége van, mivel a kézi tervezések háttérbe szorultak. Harmadikként a Quine féle módszert tárgyaljuk, amely alkalmas szoftveres megvalósításra.
2
ALGEBRAI EGYSZERŰSÍTÉS Az algebrai egyszerűsítésnél a matema3kai logika törvényeit felhasználva egyszerűsítjük a A+ A =1 függvényt. Pl. Az egyenlőség felhasználásával az alábbi két logikai szorzat egyetlen szorzatra vezethető vissza, valamint a bemeneti változók számát is sikerült csökkenteni:
A ⋅ B ⋅ C + A ⋅ B ⋅ C = ( A + A) ⋅ B ⋅ C = B ⋅ C 3
Természetesen ez jelentős megtakarítást jelent a hardverben: két darab három bemenetű ÉS kapu és egy darab két bemenetű VAGY kapu helyett egyetlen két bemenetű ÉS kapuval megvalósítható a kifejezés. Az algebrai egyszerűsítéssel az a gond, hogy nem áttekinthető és nem gépiesíthető. Nehéz felfedni, hogy mely tagokat lehetne összevonni, mely törvények alkalmazásával. 4
A KARNAUGH FÉLE GRAFIKUS MÓDSZER A grafikus egyszerűsítésnél rendszerint a függvény igazságtáblázatából indulunk ki. Ha algebrai alak áll rendelkezésre, azt ki kell bővíteni a diszjunktív kanonikus alakra, amiből egyértelműen következik az igazságtáblázat. Az igazságtáblázatból nem egyszerű belátni, hogy mely mintermeket lehetne összevonni és ezzel egyszerűsíteni a függvényt. Az összevonással kapott tagokat prím implikánsoknak nevezzük. Esettől függően kettő, négy, nyolc, tizenhat... minterm vonható össze. 5
Úgy kell a mintermeket elrendezni (síkban vagy térben), hogy a szomszédosak (amelyek csak egyetlen változó ponált és negált alakja miatt különböznek) egymás mellé kerüljenek. Az összevonást lefedő tömbbel jelöljük. Az ilyen elrendezést Karnaugh táblának nevezzük. A tábla előnye, hogy jól beláthatók az egyszerűsítési lehetőségek. Egy változó esetére a Karnaugh tábla a következő:
A mi 0 A = m0 1
A = m1
A 0
m0
1
m1 6
Két változó esetére a Karnaugh tábla a következő:
A B mi 0 0 AB = m0 0 1 AB = m1 1 0 AB = m2 1 1 AB = m3
B A
B 0
1
0 m0 m1 A 1 m2 m3
Attól függően, hogy melyik mintermek szerepelnek a függvényben, összevonhatók pl. m0 és m1, m1 és m3, m0 és m2, m2 és m3. 7
Egyszerűsítsük az alábbi függvényt először algebrai úton.
f ( A, B ) = ∑ m(0,2,3) = A ⋅ B + A ⋅ B + A ⋅ B A következő két tételt használtuk fel a függvény egyszerűsítésére.
A + A = 1,
A+ A = A
f ( A, B ) = A ⋅ B + A ⋅ B + A ⋅ B = A ⋅ B + A ⋅ B + A ⋅ B + A ⋅ B = ( A + A) ⋅ B + A ⋅ ( B + B) = (1) ⋅ B + A ⋅ (1) = B + A 8
f ( A, B ) = ∑ m(0,2,3) = A ⋅ B + A ⋅ B + A ⋅ B
függvénynek megfelelő Karnaugh táblában három egyes van, mivel három minterm alkotja a függvényt. A lehetséges összevonásokat a következő ábra mutatja. A lefedő tömböket karikázással jelöltük, a tábla mellé írtuk a lefedő tömböknek megfelelő prím implikánsokat.
B A
B 0
1
0
1
0
A 1
1
1 9
Az egyszerűsített függvény a következő:
f ( A, B ) = B + A Az eredmény jelentős: a korábbi három két bemenetű ÉS kapu és egy darab három bemenetű VAGY kapu helyett a függvény megvalósítható egyetlen VAGY kapuval.
10
Három változó esetére a Karnaugh táblában a következő módon rendezzük el a mintermeket:
11
Tekintsük a következő két háromváltozós függvényt, amelyetket mind algebrai módszerrel, mind pedig a Karnaugh táblával egyszerűsítünk:
f1 ( X , Y , Z ) = ∑ m(1,3,5,7) = X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z f 2 ( X , Y , Z ) = ∑ m(1,2,3,6,7) = X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z 12
(
)
f1 ( X , Y , Z ) = X ⋅ Y + X ⋅ Y + X ⋅ Y + X ⋅ Y ⋅ Z
(
)
(
)
= X ⋅ (Y + Y ) + X ⋅ (Y + Y ) ⋅ Z = X ⋅1 + X ⋅1 ⋅ Z = Z YZ X 00 0 0
01 1
11 1
10 0
X 1
1
1
0
0
Y
Mindez együttesen Z
Z 13
f 2 (X , Y , Z ) = X ⋅ Y ⋅ Z + X ⋅ Y ⋅ Z + X ⋅ Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z
(
)
(
= X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + Z + X ⋅Y ⋅ Z + Z
(
)
)
= X ⋅Y ⋅ Z + X ⋅Y + X ⋅Y = X ⋅Y ⋅ Z + X + X ⋅Y
(
)
= X ⋅Y ⋅ Z + Y = X ⋅ Z ⋅Y + X ⋅ Z ⋅Y + Y
(
)
= X ⋅Z ⋅ Y +Y +Y = X ⋅Z +Y 14
A
Ennek eredménye
XY YZ X 00 0 0
01 1
11 1
10 1
X 1
0
1
1
0
Y
Ennek eredménye Y
Z 15
Négy változó esetére a Karnaugh táblában a következő módon rendezzük el a mintermeket:
16
QUINE FÉLE TÁBLÁZATOS MÓDSZER Ez az eljárás is a szomszédos mintermek összevonására épül. Megfelelő algoritmussal azokat a logikai szorzatokat keressük, amelyek kódjai csak egy értékben különböznek egymástól. Az algoritmus a következő lépésekből áll:
17
1. Csoportosítjuk a mintermeket a kódjukban szereplő egyesek száma szerint. 2. Felsorakoztatjuk a kapott csoportokat, kezdve azzal, amelyben a legkevesebb egyes van. 3. Az i-edik csoport minden elemét megpróbáljuk kombinálni az i+1-edik csoport minden elemével. Ha összevonási lehetőséget látunk, felírjuk az egyszerűsített szorzatot, a kiküszöbölt változót alsó vonallal jelöljük. 18
4. A 3. pontban leírt műveletet folytatjuk az egyszerűsített szorzatokon is, mindaddig, amíg összevonási lehetőség kínálkozik. Az utolsó menetben kapott egyszerűsített szorzatok a prím implikánsok. 5. Prím implikáns táblát szerkesztünk annyi oszloppal, ahány minterm van a függvényben és annyi sorral, amennyi a prím implikánsok száma. X-szel jelöljük azokat a sor és az oszlop metszéspontját, ha az adott prím implikáns fedi az illető mintermet. 19
6. Kiválasztjuk azokat a (lényeges) prím implikánsokat, amelyek szükségesek a mintermek lefedéséhez (nincsenek már fedve más prím implikánsokkal). 7. A maradék prím implikánsok közül kiválasztjuk azokat, amelyek minimálisan szükségesek a lényeges prím implikánsokkal még le nem fedett mintermek lefedéséhez. 8. Az így kapott prím implikánsok alkotják az egyszerűsített függvényt. 20
