next up previous
Következő: Logikai függvények realizálása áramkörökkel | Tartalomjegyzék | Előző: Kétváltozós Boole függvények

Boole függvények minimalizálása

Az előzőekben már láttunk példát arra, hogy a Boole algebra szabályainak alkalmazásával az eredeti függvény egyszerűbb alakra hozható. Az "egyszerűbb" itt azt jelenti, hogy a függvényt kevesebb írásmunkával állíthatjuk elő, ami nyilván azt is jelenti, hogy kevesebb logikai áramkörből kell építkeznünk. Az egyszerűsítés általában gazdasági és megbízhatósági előnyökkel jár együtt. Az algebrai szabályok közvetlen ("hasra ütéses", heurisztikus) alkalmazása azonban csak kevés (2-3-4) változós függvények esetén használható: ha a bemenetek száma növekszik, a függvény áttekinthetetlenné válik, a műveletek közben elkövetett hiba valószínűsége növekszik. Ezért különböző szemléletes, és könnyen mechanizálható eljárásokat dolgoztak ki az egyszerűsítések megkönnyítésére. E módszerek egyike az ún. Veitch-Karnaugh módszer. Lényege egy diagram, melybe az igazságtáblázat közvetlenül berajzolható, mert a diagramot alkotó négyzetek egy-egy kanonikus tényezőnek felelnek meg.


6.4.1. ábra


A 6.4.1. ábra az n = 3,4,5 változóra felrajzolható diagramokat mutatja. A 6.4.2. ábrán feltüntettünk néhány elemi tényezőnek (változók szorzata, de nem feltétlenül szerepel benne az összes változó) a Veitch diagramon történő elhelyezését. Az ábrák vizsgálatából kiderül, hogy a kanonikus tényezőknek egyetlen kis négyzet felel meg, az elemi tényezőknek pedig 2,4,8 vagyis annál több, minél kevesebb változó szerepel benne. Észre kell vennünk azt is, hogy ilyenkor az 1-et tartalmazó négyzetek mindig egymás mellett helyezkednek el, természetesen csak akkor, ha a diagramot függőleges és vízszintes határoló vonalai mellett "összeragasztva" képzeljük el. (A diagram tehát egy tóruszon helyezkedik el.)


6.4.2. ábra

A kanonikus alakban megadott Boole függvények minimalizálása a fentiek alapján tehát azt jelenti, hogy a diagramon feltüntetjük a lehetséges elemi tényezőket úgy, hogy minél több 1-et lehessen egymás mellett levőnek tekinteni. Ez ugyanis az elemi tényezőket realizáló logikai áramkörök bemeneteinek számát (ÉS, VAGY áramkörnél a diódák számát) csökkenti. Példaképpen a 6.4.3. ábrára utalva minimalizáljuk az

f =P3+P7+P8+P9+P12+P13+P15

függvényt.


6.4.3. ábra


A megoldás láthatóan nem egyértelmű: függ attól, hogy melyik 1-eket tekintjük összetartozóknak:

\begin{displaymath}f_1=A\cdot \bar{C}+\bar{A}\cdot C\cdot D+B\cdot C\cdot D\quad,\end{displaymath}


\begin{displaymath}f_2=A\cdot \bar{C}+\bar{A}\cdot C\cdot D+A\cdot B\cdot D\quad.\end{displaymath}

A két függvény realizáláshoz szükséges bemenetek száma azonban azonos. A Veitch-Karnaugh diagram használata tehát igen egyszerű, és eredményül elemi tényezők összegeként kapjuk a végeredményt. Természetesen az S tényezőkre teljesen szimmetrikusan hasonló egyszerűsítési szabályok vezethetők le. A Veitch diagram módszernek igen szemléletes voltából még egy további előny fakad. Ennél az eljárásnál ugyanis az ún. "közömbös" tényezők figyelembevétele nagyon könnyű. Közömbös tényezőnek tekintünk olyan bemeneti változó kombinációt (P tagot), amely a működés során nem jöhet létre, vagy a létrejöttekor kialakuló kimeneti függvény értéket nem használjuk. Közömbös tényező pl. a 4 bistabilból felépített BCD számlálóban (Binary Coded Decimal - binárisan kódolt decimális - vagyis csak a 0 - 9 számok fordulnak elő, az ennél nagyobbak nem) az 1010, 1011... kombináció. Ha az előző példánkban az ABCD kombináció nem jöhet létre, az eredeti függvény sokkal radikálisabban egyszerűsíthető:

\begin{displaymath}f_3=A\cdot \bar{C}+C\cdot D\quad .\end{displaymath}

A Boole függvények egyszerűsítésének tehát vannak nagyon szemléletes és gyorsan eredményre vezető módszerei. Az "egyszerű" alakra való törekvés azonban nem egyértelmű. Számos függvény ugyanis egyszerűbb alakra hozható, ha nem elemi tényezők összegeként, vagy szorzataként írjuk fel őket. Ez persze azzal jár, hogy az ún. kétfokozatú logika helyett több fokozatút használunk, vagyis a bemenőjel a kimenetig nem csak két kapurendszeren (egy ÉS és egy VAGY) jut a kimenetre, hanem több fokozaton keresztül. A fokozatok számának növekedése pedig a bemenőjel és a kimenőjel közötti - esetleg tetemes - időkésést eredményez, ami a logikai kimenet időlegesen helytelen értékében is megnyilvánulhat. Gondot okozhat az is, hogy az egyszerűsítési eljárás ÉS, VAGY áramkörökre ugyan minimalizálja a bemenet számát, de ha rendelkezésünkre $\overline{\rm\acute{E}S}$ illetve $\overline{\rm VAGY}$ áramkörök állnak, már némileg eltérő módon kell az áramkört realizálni. Nem szabad elfeledkezni arról sem, hogy a ténylegesen kivitelezett logikai áramkörök kimenetei nem terhelhetők korlátlanul. Logikailag helyes összefüggést éppen ezért nem biztos, hogy a rendelkezésre álló rendszerekkel közvetlenül meg lehet valósítani. Inverterek, emitterkövetők, teljesítményerősítők elhelyezését pedig az egyszerűsítő eljárások nem adják meg. Lehetséges az is, hogy a bemenő változók egy adott csoportjához több kimenő függvény is tartozik. A több kimenetű függvények egyszerűsítése pedig - a közös részek keresése - az ismertetett módszertől eltérő eljárást igényel. Logikai függvények "kézi" egyszerűsítéséhez csak a legegyszerűbb esetekben folyamodjunk. Összetettebb problémák megoldásához használjunk számítógépet: nagyszámú, igen hatékony program létezik, amelyek gyorsan és fáradság mentesen szolgáltatnak eredményt.
next up previous
Következő: Logikai függvények realizálása áramkörökkel | Tartalomjegyzék | Előző: Kétváltozós Boole függvények

1999-09-23