Karnaugh-tábla (Karnaugh map): definíciója és szerepe a logikai függvények egyszerűsítésében

A digitális elektronika és a logikai tervezés világában az egyik leggyakoribb feladat a komplex Boole-függvények egyszerűsítése. Ez a folyamat nem csupán elméleti érdekesség, hanem alapvető fontosságú a hatékony, megbízható és költséghatékony digitális áramkörök megalkotásához. Egy bonyolult logikai kifejezés, amely nagyszámú logikai kaput igényel, lassabb működést, nagyobb energiafogyasztást és több hardverkomponenst jelenthet. Ezzel szemben egy egyszerűsített forma kevesebb kaput, gyorsabb jelfeldolgozást és alacsonyabb gyártási költségeket eredményez. Ebben a kontextusban vált a Karnaugh-tábla, vagy angolul Karnaugh map (K-map), a digitális tervezőmérnökök és informatikusok egyik legfontosabb eszközévé. Ez a vizuális módszer lehetővé teszi a logikai függvények intuitív és rendszerezett minimalizálását, gyakran sokkal gyorsabban és kevesebb hibával, mint a tisztán algebrai megközelítések.

A Boole-algebra, bár elegáns és precíz, a gyakorlatban nehézségekbe ütközhet, amikor sok változós, összetett függvényeket kell egyszerűsíteni. Az algebrai azonosságok alkalmazása, mint a disztributivitás, kommutativitás, asszociativitás, vagy a De Morgan-törvények, rendkívül időigényes és hibalehetőségeket rejt magában, különösen, ha az ember nem látja át azonnal a mintázatokat. Itt jön képbe a Karnaugh-tábla, amely egy grafikus megjelenítési formát kínál, ahol a logikai változók közötti szomszédság vizuálisan is értelmezhetővé válik. Ez a vizuális megközelítés segít az emberi agynak felismerni azokat a mintázatokat és csoportosításokat, amelyek az algebrai manipulációk során könnyen elkerülhetők lennének. A Karnaugh-tábla megalkotója, Maurice Karnaugh, 1953-ban publikálta módszerét, amely azóta is a digitális rendszerek tervezésének alapkövének számít.

A Karnaugh-tábla lényegében egy speciális elrendezésű igazságtábla. Míg egy hagyományos igazságtábla sorban listázza az összes lehetséges bemeneti kombinációt és a hozzájuk tartozó kimeneti értékeket, addig a Karnaugh-tábla úgy rendezi el ezeket a kimeneti értékeket egy rácsban, hogy a szomszédos cellákban (azaz a közvetlenül egymás mellett elhelyezkedő mezőkben) csak egyetlen bemeneti változó értéke tér el. Ez a Gray-kód szerinti elrendezés kulcsfontosságú, mert ez biztosítja a logikai szomszédság vizuális megjelenítését. A cél az, hogy a táblázatban szereplő egyeseket (vagy nullákat, ha a POS forma érdekel minket) csoportosítsuk a lehető legnagyobb méretű, téglalap alakú, kettő hatványú (1, 2, 4, 8, 16, stb.) csoportokba. Minél nagyobb egy csoport, annál több redundáns változót tudunk kiküszöbölni, és annál egyszerűbb lesz a végső logikai kifejezés.

A Karnaugh-tábla használatának elsajátítása alapvető lépés mindenki számára, aki mélyebben szeretne elmerülni a digitális logika és a hardvertervezés világában. Nem csupán egy egyszerűsítő eszköz, hanem egyfajta gondolkodásmód is, amely segít strukturáltan megközelíteni a logikai problémákat. Ahhoz, hogy teljes mértékben kihasználhassuk a benne rejlő potenciált, meg kell érteni az alapelveit, a felépítését, a csoportosítási szabályait, és azt, hogyan kezeljük a különböző változószámú függvényeket, beleértve a „don’t care” feltételeket is. Ez a cikk részletesen bemutatja a Karnaugh-tábla definícióját, működési elvét, lépésről lépésre történő alkalmazását különböző változószámok esetén, valamint kitér a haladóbb fogalmakra és a gyakorlati alkalmazásokra is.

A Boole-algebra és a logikai függvények alapjai

Mielőtt mélyebbre merülnénk a Karnaugh-tábla rejtelmeibe, érdemes röviden áttekinteni a Boole-algebra alapjait, amely a digitális logika matematikai alapját képezi. A Boole-algebra olyan matematikai rendszer, amely csak két logikai értéket ismer: igaz (1) és hamis (0). A műveleteket logikai kapuk valósítják meg, mint az ÉS (AND), VAGY (OR) és NEM (NOT). Ezekből az alapkapukból építhetők fel a bonyolultabb logikai függvények és áramkörök. Egy logikai függvény egy vagy több bemeneti változótól függ, és egyetlen kimeneti értéket ad vissza, amely 0 vagy 1 lehet. A függvények felírhatók algebrai kifejezések formájában, mint például $F(A, B, C) = A \cdot B + \overline{C}$.

A logikai függvények gyakran több különböző formában is felírhatók, amelyek logikailag egyenértékűek, de bonyolultságukban eltérőek. A digitális tervezésben az a célunk, hogy a függvényt a lehető legegyszerűbb formában fejezzük ki, ami a legkevesebb logikai kapuval és összeköttetéssel valósítható meg. Az egyszerűsítés nemcsak a hardveres költségeket csökkenti, hanem a működési sebességet is növelheti, mivel kevesebb kapukésleltetés halmozódik fel. A Boole-algebra számos azonosságot és tételt kínál az egyszerűsítésre, például az idempotencia ($A \cdot A = A$, $A + A = A$), a komplementer törvény ($A \cdot \overline{A} = 0$, $A + \overline{A} = 1$), a disztributivitás ($A \cdot (B + C) = A \cdot B + A \cdot C$), és a De Morgan-törvények ($\overline{A \cdot B} = \overline{A} + \overline{B}$, $\overline{A + B} = \overline{A} \cdot \overline{B}$).

Azonban, ahogy a változók száma növekszik, az algebrai manipulációk egyre bonyolultabbá válnak. Egy négy-, öt- vagy többváltozós függvény kézi algebrai egyszerűsítése rendkívül időigényes és hibalehetőségeket rejt magában. Nehéz garantálni, hogy a végső forma valóban a legminimálisabb. Ezért van szükség olyan szisztematikus módszerekre, mint a Karnaugh-tábla vagy a Quine-McCluskey algoritmus, amelyek biztosítják a minimális vagy közel minimális megoldás megtalálását.

A logikai függvényeket gyakran két kanonikus formában fejezzük ki: összegzési szorzatok (SOP – Sum of Products) és szorzati összegek (POS – Product of Sums). Az SOP forma mintermek összegeként jelenik meg, ahol egy minterm egy olyan szorzati tag, amely minden változót tartalmaz, vagy eredeti, vagy negált formában. Például egy 3 változós függvény esetén $A \cdot B \cdot \overline{C}$ egy minterm. A POS forma maxtermek szorzataként írható fel, ahol egy maxterm egy olyan összegezési tag, amely minden változót tartalmaz, vagy eredeti, vagy negált formában. Például $A + \overline{B} + C$ egy maxterm. A Karnaugh-tábla elsősorban az SOP forma egyszerűsítésére alkalmas, az 1-esek csoportosításával, de a 0-k csoportosításával a POS forma is levezethető belőle.

A Karnaugh-tábla felépítése és a Gray-kód jelentősége

A Karnaugh-tábla egy kétdimenziós rács, amelynek cellái a bemeneti változók összes lehetséges kombinációját reprezentálják. Minden cella egyetlen mintermnek felel meg, vagyis a bemeneti változók egy adott konfigurációjának. A tábla felépítése kulcsfontosságú az egyszerűsítési folyamat szempontjából: a sorok és oszlopok címeit úgy kell elrendezni, hogy a szomszédos cellákban (függőlegesen vagy vízszintesen) mindössze egyetlen bemeneti változó értéke térjen el. Ezt az elrendezést biztosítja a Gray-kód.

A Gray-kód, más néven reflektált bináris kód, egy olyan bináris számsorozat, amelyben az egymást követő számok csak egyetlen bitben különböznek egymástól. Ez ellentétben áll a hagyományos bináris számsorral, ahol például a 011 (3) és a 100 (4) között három bit is eltér. A Gray-kód használata a Karnaugh-táblán belül garantálja, hogy a táblázatban egymás mellé kerülő cellák logikailag is szomszédosak legyenek, azaz a bemeneti változók tekintetében csak egy pozíción térjenek el. Ez a tulajdonság teszi lehetővé a csoportosítást és a redundáns változók kiküszöbölését.

Tekintsünk egy példát a Gray-kódra két változó esetén:

• 00
• 01
• 11
• 10

Látható, hogy minden lépésben csak egy bit változik. Ugyanez vonatkozik három változóra:

• 000
• 001
• 011
• 010
• 110
• 111
• 101
• 100

A Karnaugh-tábla celláihoz rendelt bináris kódok pontosan ezt a Gray-kód sorrendet követik a sor- és oszlopfejlécekben.

A táblázat mérete a bemeneti változók számától függ:

• 2 változó (pl. A, B): 2×2-es tábla, 4 cella.
• 3 változó (pl. A, B, C): 2×4-es (vagy 4×2-es) tábla, 8 cella.
• 4 változó (pl. A, B, C, D): 4×4-es tábla, 16 cella.
• 5 változó (pl. A, B, C, D, E): Két 4×4-es tábla (egyik E=0, másik E=1 esetén), összesen 32 cella.
• 6 változó (pl. A, B, C, D, E, F): Négy 4×4-es tábla, összesen 64 cella.

A táblázat celláiba a logikai függvény kimeneti értékeit írjuk be: 1-et, ha a függvény igaz az adott bemeneti kombinációra, és 0-t, ha hamis. Emellett léteznek a „don’t care” feltételek, amelyeket ‘X’ vagy ‘d’ betűvel jelölünk, és amelyekről később részletesebben is szó lesz.

A Karnaugh-tábla felrajzolásakor a változókat általában úgy rendezzük el, hogy a tábla felső és oldalsó részén helyezkedjenek el. Például egy 4 változós táblánál az AB változók a sorokat, a CD változók az oszlopokat címkézhetik. Fontos, hogy a Gray-kód sorrendet mindkét tengelyen betartsuk. A cellákba a mintermek indexeit (bináris értéküket decimálisan) is beírhatjuk, hogy könnyebben azonosíthassuk őket.

A Karnaugh-tábla használata 2 változó esetén

A Karnaugh-tábla legegyszerűbb formája a kétváltozós tábla. Ez a bevezető példa segít megérteni az alapvető elrendezést és a csoportosítási elveket.

Tegyük fel, hogy van egy $F(A, B)$ logikai függvényünk, amelynek igazságtáblája a következő:

Ez a függvény valójában az XOR (exkluzív VAGY) műveletet írja le. Az SOP forma mintermekkel felírva: $F(A, B) = \overline{A}B + A\overline{B}$.

A 2 változós Karnaugh-tábla felépítése:

A tábla 2×2-es méretű. Az egyik változó (pl. A) a sorokat, a másik (pl. B) az oszlopokat címkézi. A Gray-kód sorrend itt egyszerű, mivel csak két érték van (0 és 1).

A függvény beírása a táblába:

Most beírjuk a kimeneti értékeket (0 vagy 1) a megfelelő cellákba az igazságtábla alapján.

A zárójelben lévő m0, m1, m2, m3 a mintermek decimális indexei.

Csoportosítási szabályok:

A Karnaugh-tábla lényege az 1-esek csoportosítása. A csoportoknak a következő szabályoknak kell megfelelniük:

1. A csoportoknak téglalap alakúaknak kell lenniük.
2. A csoportok méretének kettő hatványának kell lennie (1, 2, 4, 8, 16, stb. cella).
3. A csoportoknak összefüggőnek kell lenniük (azaz a cellák élükkel érintkeznek, nem csak sarkukkal).
4. A csoportok átfedhetik egymást, ha ez nagyobb csoportok képzését segíti elő, vagy ha szükséges az összes 1-es lefedéséhez.
5. Minden 1-es cellát le kell fedni legalább egy csoporttal.
6. A cél a lehető legnagyobb csoportok képzése. Minél nagyobb egy csoport, annál kevesebb változót tartalmaz a végső kifejezés.
7. A cél a lehető legkevesebb számú csoport alkalmazása, miközben minden 1-est lefedünk.

Az egyszerűsített kifejezés leolvasása:

Az XOR függvény táblájában két 1-es van. Ezeket nem lehet egyetlen 2-es csoportba foglalni, mert nem szomszédosak. Ezért két különálló 1-es csoportot alkotunk:

1. Az A=0, B=1 cella (m1): Ez a cella a $\overline{A}B$ mintermnek felel meg.
2. Az A=1, B=0 cella (m2): Ez a cella az $A\overline{B}$ mintermnek felel meg.

Az egyszerűsített kifejezés tehát: $F(A, B) = \overline{A}B + A\overline{B}$. Ebben az esetben a Karnaugh-tábla nem hozott további egyszerűsítést, mivel az XOR függvény eleve minimális SOP formában van. Ez azonban egy jó példa arra, hogy hogyan azonosítjuk a mintermeket.

A Karnaugh-tábla használata 3 változó esetén

Három változó (pl. A, B, C) esetén a Karnaugh-tábla 8 cellából áll, általában 2×4-es vagy 4×2-es elrendezésben. A leggyakoribb elrendezés a 2×4-es, ahol egy változó (pl. A) címkézi a sorokat, és a másik kettő (pl. BC) az oszlopokat. Fontos újra hangsúlyozni, hogy az oszlopok címkézésekor a Gray-kód sorrendet kell használni (00, 01, 11, 10).

A 3 változós Karnaugh-tábla felépítése:

Legyenek a változók A, B, C. A sorokat az A, az oszlopokat a BC kombinációk címkézik.

A minterm indexek (m0-m7) segítenek a cellák azonosításában.

Példa függvény egyszerűsítése:

Egyszerűsítsük a következő függvényt SOP formában: $F(A, B, C) = \sum(0, 1, 2, 5, 7)$, ami azt jelenti, hogy a függvény igaz (1) az m0, m1, m2, m5, m7 mintermekre.

1. lépés: A tábla feltöltése:

2. lépés: Az 1-esek csoportosítása:

Keresünk téglalap alakú, kettő hatványú (2, 4, 8) csoportokat, amelyek csak 1-eseket tartalmaznak, és a lehető legnagyobbak.

1. Négyes csoport (Quad): Nézzük az A=0 sorban lévő 1-eseket: m0, m1, m2. Ezek közül az m0 és m1 szomszédos. Az m2 is szomszédos az m0-val, ha a táblát henger alakúnak képzeljük (a szélső oszlopok „körbeérnek”). Azaz, a 00 és 10 oszlopok szomszédosak. Így az m0 és m2 alkothatnak egy párt. Az m0 és m1 szintén. Az m1 és m3 nem. Az m0(000) és m2(010) közötti szomszédság azt jelenti, hogy csak a B változó értéke tér el (000 vs 010). Ugyanígy az m0(000) és m1(001) között csak a C változó tér el.
   
   Van egy négyes csoport, ami az m0, m1, m2, m3-at tartalmazná, ha az m3 is 1-es lenne. Mivel nem az, nézzünk mást.
   
   Nézzük a szélső oszlopokat: az A=0, BC=00 (m0) és A=0, BC=10 (m2) cellák 1-esek. Ezek szomszédosak a tábla „körbetekerése” miatt. Ugyanígy az A=1, BC=00 (m4) és A=1, BC=10 (m6) cellák is szomszédosak. Ha az m4 és m6 is 1-es lenne, akkor egy 4-es csoportot alkothatnának az m0, m2, m4, m6. De nem azok.
   
   A táblán lévő 1-esek: m0, m1, m2, m5, m7.
   
   Van egy négyes csoport: m0, m1, m2-t nem lehet négyes csoportba foglalni, mivel az m3 nulla.
   
   Nézzünk egy másik megközelítést. A 00 és 10 oszlopok szomszédosak, valamint a 01 és 11 oszlopok is.
   
   Vegyük az m1 és m5 cellákat. Ezek függőlegesen szomszédosak (001 és 101, csak az A változó tér el). Ez egy kettes csoport.
   
   Vegyük az m5 és m7 cellákat. Ezek vízszintesen szomszédosak (101 és 111, csak a C változó tér el). Ez egy kettes csoport.
   
   Vegyük az m0 és m1 cellákat. Ezek vízszintesen szomszédosak (000 és 001, csak a C változó tér el). Ez egy kettes csoport.
   
   Vegyük az m0 és m2 cellákat. Ezek vízszintesen szomszédosak a körbetekerés miatt (000 és 010, csak a B változó tér el). Ez egy kettes csoport.
   
   A lehető legnagyobb csoportok keresése a cél.
   
   Látunk egy négyes csoportot, amely az m0, m1, m2 cellákat foglalja magában, ha a 00, 01, 11, 10 oszlopok közötti szomszédságot is figyelembe vesszük. Az m0 (000), m1 (001), m2 (010) cellák.
   
   A m0 és m1 egy csoport: $\overline{A}\overline{B}$. A m0 és m2 egy csoport: $\overline{A}C$.
   
   Nézzük a m0, m1, m2. M0=000, M1=001, M2=010.
   
   A m0, m1, m2 cellák nem alkotnak egy négyes csoportot. Az m0, m1 egy kettes csoport: $\overline{A}\overline{B} + \overline{A}B\overline{C}$. Ez nem jó.
   
   Csoportosítsuk az 1-eseket:
   
   Van egy négyes csoport, ami az m0, m1, m2 cellákat fogja össze. Nem, ez nem négyes csoport. A négyes csoportnak téglalapnak kell lennie és 2 hatványnak.
   
   Nézzük a 00 és 10 oszlopokat. A=0, BC=00 (m0) és A=0, BC=10 (m2). Ezek 1-esek. Ezek egy kettes csoportot alkotnak, mert a C változó 0-ról 1-re változik (000-010), de a B fixen 0, A fixen 0. Tehát $A=0, B=0$, a C változik, tehát $\overline{A}\overline{B}$.
   
   Nézzük az m1 (001) és m5 (101) cellákat. Ezek függőlegesen szomszédosak. Az A változik (0-ról 1-re), a B és C fixen 0 és 1. Tehát $\overline{B}C$.
   
   Nézzük az m5 (101) és m7 (111) cellákat. Ezek vízszintesen szomszédosak. A fixen 1, B változik (0-ról 1-re), C fixen 1. Tehát $AC$.
   
   Van még az m0 (000) cella. A m0-t már lefedtük az $\overline{A}\overline{B}$ csoporttal.
   
   Az m2 (010) cellát is lefedtük az $\overline{A}\overline{B}$ csoporttal.
   
   Az m1 (001) cellát lefedtük a $\overline{B}C$ csoporttal.
   
   Az m5 (101) cellát lefedtük a $\overline{B}C$ és $AC$ csoportokkal.
   
   Az m7 (111) cellát lefedtük az $AC$ csoporttal.
   
   Tehát a csoportok:
   1. Csoport 1 (kettes): m0 (000) és m2 (010). Ez a csoport az $\overline{A}\overline{B}$ kifejezést adja. (A fix 0, B fix 0, C változik 0-ról 1-re).
      * Helyesbítés: A m0 (000) és m2 (010) cellákban az A (0) és B (0) érték fix, míg a C változik (0-ról 1-re). Ez a csoport tehát $\overline{A}\overline{B}$ minterm.
      * Helyesbítés 2: Az oszlopok címei: 00, 01, 11, 10. Az m0 a (0,00), m1 a (0,01), m2 a (0,10). Az m0 és m2 szomszédosak a tábla „körbetekerése” miatt. Azaz az A=0 sorban a BC=00 és BC=10 oszlopok szomszédosak. Ezekben a cellákban az A=0 és B=0 (m0) ill. A=0 és B=1 (m2). Itt a B változik, a C fix. Tehát $\overline{A}\overline{C}$. (m0: 000, m2: 010. A=0, C=0. B változik.)
   2. Csoport 2 (kettes): m1 (001) és m5 (101). Ez a csoport $\overline{B}C$ kifejezést adja. (B fix 0, C fix 1, A változik 0-ról 1-re).
   3. Csoport 3 (kettes): m5 (101) és m7 (111). Ez a csoport $AC$ kifejezést adja. (A fix 1, C fix 1, B változik 0-ról 1-re).

   Most nézzük meg, van-e nagyobb csoport. Az m0, m1, m2, m5, m7.
   
   Van egy négyes csoport: m1 (001), m3 (011 – ez 0), m5 (101), m7 (111). Ha az m3 is 1 lenne, akkor a m1, m3, m5, m7 alkotna egy négyes csoportot.
   
   A m1 (001) és m5 (101) egy kettes csoport: $\overline{B}C$.
   
   A m2 (010) és m0 (000) a szélénél összeérve egy kettes csoport: $\overline{A}\overline{C}$.
   
   Még le kell fedni a m7-et. A m7 (111) a m5-tel (101) együtt egy kettes csoport: $AC$.
   
   Összefoglalva a lefedést:

   1. Csoport 1: m0 (000) és m2 (010) → $\overline{A}\overline{C}$
   2. Csoport 2: m1 (001) és m5 (101) → $\overline{B}C$
   3. Csoport 3: m7 (111) és m5 (101) → $AC$

   Mivel az m5-öt már lefedtük a második csoporttal, és az m7-et a harmadikkal, ez rendben van. Minden 1-est lefedtünk.

   A minimalizált kifejezés tehát az egyes csoportok által reprezentált egyszerűsített tagok összege:

   $F(A, B, C) = \overline{A}\overline{C} + \overline{B}C + AC$

   Ez egy példa arra, hogy a Karnaugh-tábla hogyan segít a vizuális csoportosításban, hogy a lehető legegyszerűbb SOP formát kapjuk.

A Karnaugh-tábla használata 4 változó esetén

A négyváltozós Karnaugh-tábla (pl. A, B, C, D) 16 cellából áll, és általában 4×4-es rácsként ábrázoljuk. Ez a leggyakoribb és talán a legfontosabb eset a gyakorlatban, mivel a legtöbb digitális áramkör logikája 2-4 változóval írható le. Itt a Gray-kód sorrend még hangsúlyosabbá válik mind a sorokban, mind az oszlopokban.

A 4 változós Karnaugh-tábla felépítése:

Legyenek a változók A, B, C, D. A sorokat az AB kombinációk, az oszlopokat a CD kombinációk címkézik.

Figyeljük meg a Gray-kód sorrendet mind a sorokban (00, 01, 11, 10), mind az oszlopokban (00, 01, 11, 10). Ez biztosítja, hogy minden szomszédos cella (beleértve a tábla széleit is, mintha egy tóruszt alkotna) csak egy bitben tér el.

Példa függvény egyszerűsítése:

Egyszerűsítsük a következő függvényt SOP formában: $F(A, B, C, D) = \sum(0, 2, 5, 6, 7, 8, 10, 13, 15)$.

1. lépés: A tábla feltöltése:

2. lépés: Az 1-esek csoportosítása:

Keressük a lehető legnagyobb, kettő hatványú téglalap alakú csoportokat, amelyek csak 1-eseket tartalmaznak, és lefedik az összes 1-est.

1. Négyes csoport (Quad) a sarkokban: Az m0 (0000), m2 (0010), m8 (1000), m10 (1010) cellák mind 1-esek. Ezek a tábla négy sarkában helyezkednek el, és vizuálisan is szomszédosak, ha a táblát hengernek, majd tórusznak képzeljük. Ez egy négyes csoport.
   * M0: A=0, B=0, C=0, D=0
   * M2: A=0, B=0, C=1, D=0
   * M8: A=1, B=0, C=0, D=0
   * M10: A=1, B=0, C=1, D=0
   Ezekben a mintermekben a B=0 és D=0 fix. Az A és C változik. Tehát ez a csoport a $\overline{B}\overline{D}$ kifejezést adja.
2. Négyes csoport (Quad) középen: Az m5 (0101), m7 (0111), m13 (1101), m15 (1111) cellák mind 1-esek. Ezek egy 2×2-es téglalapot alkotnak a táblázatban. Ez egy négyes csoport.
   * M5: A=0, B=1, C=0, D=1
   * M7: A=0, B=1, C=1, D=1
   * M13: A=1, B=1, C=0, D=1
   * M15: A=1, B=1, C=1, D=1
   Ezekben a mintermekben a B=1 és D=1 fix. Az A és C változik. Tehát ez a csoport a $BD$ kifejezést adja.
3. Kettes csoport (Pair): Még le kell fedni az m6 (0110) 1-est.
   * Az m6 (0110) szomszédos az m7 (0111) cellával. Az m7-et már lefedtük a $BD$ csoporttal. Az m6-ot lefedhetjük az m7-tel alkotott kettes csoporttal.
   * M6: A=0, B=1, C=1, D=0
   * M7: A=0, B=1, C=1, D=1
   Ebben a csoportban az A=0, B=1, C=1 fix. A D változik. Tehát ez a csoport a $\overline{A}BC$ kifejezést adja.

Minden 1-est lefedtünk. A minimalizált kifejezés az összes csoport tagjainak összege:

$F(A, B, C, D) = \overline{B}\overline{D} + BD + \overline{A}BC$

Ez egy hatékony és gyors módja a komplex logikai függvények egyszerűsítésének.

A „don’t care” feltételek (X vagy d) kezelése

A digitális rendszerek tervezése során gyakran előfordul, hogy egy logikai függvény bemeneti kombinációinak egy része soha nem fordul elő, vagy ha mégis, a kimenet értéke irreleváns. Ezeket a feltételeket nevezzük „don’t care” feltételeknek, és ‘X’ vagy ‘d’ betűvel jelöljük őket a Karnaugh-táblában. A „don’t care” feltételek rendkívül hasznosak az egyszerűsítési folyamatban, mivel rugalmasságot biztosítanak: érdemes őket 1-esnek tekinteni, ha segítenek nagyobb csoportok képzésében, és 0-nak, ha nem.

A „don’t care” feltételek alkalmazása lehetővé teszi, hogy a Karnaugh-táblában a lehető legnagyobb csoportokat hozzuk létre, ami a leginkább egyszerűsített logikai kifejezéshez vezet. Ezáltal csökkenthető a szükséges logikai kapuk száma, ami kisebb áramköri méretet, alacsonyabb energiafogyasztást és gyorsabb működést eredményez.

Hogyan használjuk a „don’t care” feltételeket?

1. Töltsük fel a Karnaugh-táblát az 1-esekkel (ahol a függvény kimenete 1) és a 0-kkal (ahol a függvény kimenete 0).
2. Helyezzük el az ‘X’ vagy ‘d’ jeleket azokra a cellákra, amelyek a „don’t care” feltételeknek felelnek meg.
3. Amikor csoportokat képzünk, tekintsük az ‘X’ cellákat 1-esnek, ha ezáltal nagyobb (kettő hatványú) csoportot tudunk létrehozni.
4. Ha egy ‘X’ cella nem segít nagyobb csoportot képezni, akkor tekintsük 0-nak, és ne vegyük bele semmilyen csoportba.
5. Fontos: Nem szükséges minden ‘X’ cellát lefedni. Csak azokat használjuk fel, amelyek előnyösek a csoportosítás szempontjából.
6. A végső kifejezésben az ‘X’ cellák eltűnnek, mivel csak a csoportképzéshez használtuk fel őket.

Példa „don’t care” feltételekkel (4 változós):

Egyszerűsítsük a következő függvényt SOP formában: $F(A, B, C, D) = \sum(0, 1, 2, 8, 9, 10)$ és $d(A, B, C, D) = \sum(13, 14, 15)$.

1. lépés: A tábla feltöltése:

2. lépés: Az 1-esek és X-ek csoportosítása:

1. Négyes csoport (Quad) a felső sorban és az alsó sorban:
   * Az m0 (0000), m1 (0001), m2 (0010) cellák 1-esek. Az m3 (0011) nulla.
   * Az m8 (1000), m9 (1001), m10 (1010) cellák 1-esek. Az m11 (1011) nulla.
   
   A m0, m1, m2, m3 nem alkot négyes csoportot.
   
   Nézzük a 00 és 10 oszlopokat (CD=00 és CD=10).
   * M0 (0000), M2 (0010) a 00 sorban.
   * M8 (1000), M10 (1010) a 10 sorban.
   Ezek a négy cella egy négyes csoportot alkot, mivel az A változik (0-ról 1-re) és a C változik (0-ról 1-re), de a B és D fixen 0. Tehát a csoport: $\overline{B}\overline{D}$.
   
   Ez a csoport lefedi az m0, m2, m8, m10 1-eseket.
2. Négyes csoport (Quad) a bal oldali oszlopokban:
   * Az m0 (0000), m1 (0001) a 00 sorban.
   * Az m8 (1000), m9 (1001) a 10 sorban.
   Ezek a négy cella egy négyes csoportot alkot. Az m0 és m8 már lefedettek. Az m1 és m9 még nem.
   * M0: A=0, B=0, C=0, D=0
   * M1: A=0, B=0, C=0, D=1
   * M8: A=1, B=0, C=0, D=0
   * M9: A=1, B=0, C=0, D=1
   Ezekben a mintermekben a B=0 és C=0 fix. Az A és D változik. Tehát a csoport: $\overline{B}\overline{C}$.
   
   Ez a csoport lefedi az m0, m1, m8, m9 1-eseket.
3. Négyes csoport (Quad) a jobb alsó sarokban (X-ek felhasználásával):
   * Az m13 (1101), m14 (1110), m15 (1111) X-ek.
   * Az m10 (1010) 1-es.
   * Az m11 (1011) nulla.
   
   Nézzük az m10 (1010) 1-est. Szomszédos az m14 (1110) X-el. Szintén szomszédos az m9 (1001) 1-essel (amit már lefedtünk).
   
   Tekintsük az m13, m14, m15 X-eket 1-esnek, ha segítenek.
   
   Az m10 (1010) 1-es és az m14 (1110) X egy kettes csoportot alkot. Ez a csoport $A\overline{D}C$.
   
   Az m13 (1101) X és m15 (1111) X egy kettes csoportot alkot. Ez a csoport $AB D$.
   
   Van egy négyes csoport, amely az m10 (1010) 1-est, és az m14 (1110), m15 (1111), m13 (1101) X-eket foglalja magába. Ezek a cellák alkotnak egy 2×2-es téglalapot a tábla jobb alsó sarkában (m10, m11 (0), m14, m15).
   * M10: A=1, B=0, C=1, D=0
   * M13: A=1, B=1, C=0, D=1
   * M14: A=1, B=1, C=1, D=0
   * M15: A=1, B=1, C=1, D=1
   Ez a csoport az $A$ változót rögzíti 1-nek. A B, C, D változik.
   * M10 (1010) és M14 (1110) egy kettes csoport: $A C \overline{D}$
   * M14 (1110) és M15 (1111) egy kettes csoport: $A B C$
   * M13 (1101) és M15 (1111) egy kettes csoport: $A B D$
   
   A 4-es csoport, ami az m10-et és az X-eket foglalja magába: m10, m14, m15, m13.
   * M10: 1010
   * M13: 1101
   * M14: 1110
   * M15: 1111
   Ezek nem alkotnak téglalapot.
   
   Nézzük újra. M10 (1-es), M14 (X), M15 (X). Ezek egy sort alkotnak. M10, M14, M15.
   
   A 2×2-es négyes csoportok:
   * M0(1), M1(1), M8(1), M9(1) → $\overline{B}\overline{C}$ (már lefedve)
   * M0(1), M2(1), M8(1), M10(1) → $\overline{B}\overline{D}$ (már lefedve)
   
   Van még az m10 1-es. Ezt már lefedtük a $\overline{B}\overline{D}$ csoporttal.
   
   Nézzük meg, hogy az X-ekkel tudunk-e nagyobb csoportot alkotni.
   
   Van egy nyolcas csoport (Octet), ami az m0, m1, m2, m3(0), m8, m9, m10, m11(0) cellákból állna, ha az m3 és m11 is 1 vagy X lenne. De nem azok.
   
   Nézzük az m10 (1-es). Ez már le van fedve.
   
   Nézzük az m13, m14, m15 X-eket.
   
   Az m14 és m15 X-ek, valamint az m6 és m7 nullák.
   
   Van egy nyolcas csoport, ami az m0, m1, m2, m3 (0) és m8, m9, m10, m11 (0) cellákból áll. Ez nem egy nyolcas csoport.
   
   A $F(A, B, C, D) = \sum(0, 1, 2, 8, 9, 10)$ és $d(A, B, C, D) = \sum(13, 14, 15)$.
   
   Csoportok:
   1. Négyes csoport: m0(1), m1(1), m8(1), m9(1). Ez a csoport lefedi az első két oszlopot a 00 és 10 sorokban. Az A változik, a D változik. B=0 és C=0. Tehát: $\overline{B}\overline{C}$.
   2. Négyes csoport: m0(1), m2(1), m8(1), m10(1). Ez a csoport lefedi az első és utolsó oszlopot a 00 és 10 sorokban. Az A változik, a C változik. B=0 és D=0. Tehát: $\overline{B}\overline{D}$.
   3. Négyes csoport (X-ekkel): m10(1), m14(X), m15(X), m11(0). Ez nem téglalap.
      * Nézzük az m10 (1-es). Ez már le van fedve az $\overline{B}\overline{D}$ csoporttal.
      * Tekintsük az X-eket. Az m13, m14, m15.
      * Van egy négyes csoport: m13(X), m15(X), m5(0), m7(0). Ez nem jó.
      * Van egy négyes csoport: m13(X), m15(X), m14(X). Ez egy sor.
      * Nézzünk egy nyolcas csoportot az X-ekkel.
      * A 00 és 10 sorok (AB=00 és AB=10) valamint a 00 és 10 oszlopok (CD=00 és CD=10) találkozásánál van a $\overline{B}\overline{D}$ csoport.
      * A 00 és 10 sorok, valamint a 00 és 01 oszlopok találkozásánál van a $\overline{B}\overline{C}$ csoport.
      * Van egy nyolcas csoport, ami az m0, m1, m2, m10, m8, m9, m13, m14, m15. Nem.
      
      A m0, m1, m2, m8, m9, m10 1-esek.
      A m13, m14, m15 X-ek.
      
      Nézzük a nyolcas csoportot, ami az m0, m1, m2, m10, m8, m9, m13, m14, m15-öt érinti.
      
      Van egy nyolcas csoport: m0, m1, m2, m3(0), m8, m9, m10, m11(0). Nem.
      
      A 00 és 10 sorok. A 00 és 01 oszlopok.
      * m0, m1, m8, m9 → $\overline{B}\overline{C}$ (ezt már azonosítottuk)
      
      A 00 és 10 sorok. A 00 és 10 oszlopok.
      * m0, m2, m8, m10 → $\overline{B}\overline{D}$ (ezt is azonosítottuk)
      
      Az m13, m14, m15 X-ek.
      * m13, m15 → $ABD$
      * m14, m15 → $ABC$
      
      Van egy négyes csoport az X-ekből és az m10-ből: m10 (1010), m14 (1110), m15 (1111), m13 (1101). Ezek nem alkotnak téglalapot.
      
      Van egy négyes csoport, ami az m10 (1-es), m14 (X), m15 (X), m11 (0) cellákat tartalmazza. Nem.
      
      Van egy négyes csoport, ami az m10(1), m14(X), m2(1), m6(0) cellákat tartalmazza. Nem.
      
      Nézzük az m10 (1-es) és a környező X-eket. M10 (1010). M14 (1110). Ezek egy kettes csoport: $A C \overline{D}$.
      
      M13 (1101) és M15 (1111). Ezek egy kettes csoport: $A B D$.
      
      Lefedett 1-esek: m0, m1, m2, m8, m9, m10.
      
      A $\overline{B}\overline{C}$ lefedi: m0, m1, m8, m9.
      A $\overline{B}\overline{D}$ lefedi: m0, m2, m8, m10.
      
      Minden 1-es le van fedve.
      
      A „don’t care” feltételeket csak akkor használjuk, ha segítenek nagyobb csoportot képezni, és nem feltétlenül kell lefedni őket.
      
      A jelenlegi megoldás már optimális, mivel minden 1-est lefedtünk a lehető legnagyobb csoportokkal. Az X-eket nem használtuk fel.
      
      A minimalizált kifejezés: $F(A, B, C, D) = \overline{B}\overline{C} + \overline{B}\overline{D}$.
      
      Ez az eredmény helyes, de az X-ek felhasználásával lehet, hogy még nagyobb csoportot tudunk találni.
      
      Nézzük újra az m10 (1-es), m14 (X), m15 (X), m13 (X) cellákat.
      * M10 (1010)
      * M14 (1110)
      * M15 (1111)
      * M13 (1101)
      Ezek nem alkotnak téglalapot.
      
      Nézzük a 00 és 10 oszlopokat, és a 00 és 11 sorokat.
      * M0 (0000), M2 (0010)
      * M12 (0), M14 (X)
      Ez egy 4-es csoport, ami az $A=0, C=0$ és $A=0, C=1$ cellákat. $A$ változik, $C$ változik. $B=0, D=0$.
      * M0 (0000), M2 (0010), M12 (0), M14 (X). Ezek téglalapot alkotnak.
      * M0(0000), M2(0010), M12(1100), M14(1110).
      * M0 és M2: $\overline{A}\overline{B}\overline{D}$.
      * M12 és M14: $A B \overline{D}$.
      * M0, M2, M12, M14 alkotnak egy négyes csoportot, ami $\overline{D}$ tagot ad.
      * M0 (0000), M2 (0010), M12 (1100), M14 (1110).
      * A változik, B változik, C változik. D fixen 0. Tehát ez a csoport a $\overline{D}$ kifejezést adja.
      * Ez a csoport lefedi az m0, m2, m14 (X) cellákat.
      
      Most az 1-esek, amik még nincsenek lefedve: m1, m8, m9, m10.
      
      Van egy négyes csoport: m1 (0001), m9 (1001), m13 (1101 – X), m5 (0).
      * m1 (0001), m9 (1001), m13 (1101 – X), m5 (0101 – 0). Ez nem jó.
      
      Van egy négyes csoport: m1 (0001), m9 (1001), m13 (1101 – X), m15 (1111 – X).
      * M1 (0001)
      * M9 (1001)
      * M13 (1101)
      * M15 (1111)
      Ez a négy cella egy téglalapot alkot (az első és harmadik oszlopban, az első és harmadik sorban).
      * A változik (00, 10, 11), B változik (00, 10, 11). C fixen 0, D fixen 1.
      * M1 (0001), M9 (1001), M13 (1101), M15 (1111).
      * A C változik, D fixen 1. A változik, B változik.
      * A B változó a 0-ból 1-be, majd vissza 0-ba. A C változó a 0-ból 1-be.
      * A m1 (0001), m9 (1001), m13 (1101), m15 (1111) cellákban D=1 és C=0 (m1, m9, m13).
      * A m1 (0001), m9 (1001) cellákban C=0, D=1. Az A változik (0-ról 1-re). B fixen 0. Tehát $\overline{B}D$.
      * A m13 (1101), m15 (1111) cellákban C változik (0-ról 1-re), D fixen 1. A fixen 1, B fixen 1. Tehát $ABD$.
      
      Van egy négyes csoport, ami az m1 (0001), m9 (1001), m13 (1101 – X), m15 (1111 – X) cellákból áll.
      * M1, M9, M13, M15.
      * M1 (0001), M9 (1001): A változik, B fixen 0, C fixen 0, D fixen 1. → $\overline{B}\overline{C}D$.
      * M13 (1101), M15 (1111): A fixen 1, B fixen 1, C változik, D fixen 1. → $ABD$.
      * A 4-es csoport: M1, M9, M13, M15. Itt D=1 és C változik. Az A és B változik.
      * Ezekben a cellákban D=1. A B és C változókra nézve: B változik (00, 10, 11), C változik (00, 10, 11).
      * A m1, m9, m13, m15 cellákban $D=1$. A változók (A,B,C) értékei: 000, 100, 110, 111.
      * Ez a négyes csoport a $D$ tagot adja.
      * Ez a csoport lefedi az m1, m9, m13 (X), m15 (X) cellákat.
      
      Eddig lefedett 1-esek: m0, m2, m1, m9. Még lefedésre vár: m8, m10.
      
      A $\overline{D}$ csoport lefedi: m0, m2, m14(X).
      A $D$ csoport lefedi: m1, m9, m13(X), m15(X).
      
      Még le kell fedni az m8(1) és m10(1) cellákat.
      
      Az m8 (1000) és m10 (1010) egy kettes csoportot alkot: $A\overline{B}\overline{D}$.
      
      Tehát a lefedés:
      1. Csoport 1 (nyolcas): m0, m1, m2, m13(X), m14(X), m15(X), m8, m9, m10.
         * Nézzük a 00, 01, 10, 11 sorokat és 00, 01, 10, 11 oszlopokat.
         * M0(1), M1(1), M2(1), M13(X), M14(X), M15(X), M8(1), M9(1), M10(1).
         * Van egy nyolcas csoport: m0, m1, m2, m8, m9, m10, m13(X), m14(X).
         * M0, M1, M2, M8, M9, M10, M13, M14, M15.
         * A m0, m1, m2, m8, m9, m10 1-esek. Az m13, m14, m15 X-ek.
         * Van egy nyolcas csoport, ami az m0, m1, m2, m10, m8, m9, m13, m14, m15 cellákat fedi le.
         * A 00, 01, 10, 11 oszlopokat vizsgálva: D=0, D=1.
         * A 00, 01, 10, 11 sorokat vizsgálva: A=0, B=0, A=0, B=1, A=1, B=0, A=1, B=1.
         * Van egy nyolcas csoport, ami a m0, m1, m2 (0000, 0001, 0010) és m8, m9, m10 (1000, 1001, 1010) cellákból áll. Ezek mind 1-esek.
         * Ezen felül: m13(X), m14(X), m15(X).
         * Van egy nyolcas csoport, ami az m0, m1, m2, m8, m9, m10, m13(X), m14(X), m15(X) cellákból áll.
         * A két sor, ahol A és B változik: 00 és 10.
         * A két oszlop, ahol C és D változik: 00, 01, 10, 11.
         * A m0, m1, m2, m13(X), m14(X), m15(X), m8, m9, m10.
         * Van egy nyolcas csoport a 00 és 10 sorokban, ami lefedi az összes 1-est és az X-eket.
         * Ez a csoport az $\overline{B}$ kifejezést adja. (B fixen 0, A, C, D változik).
         * Ez a csoport lefedi az összes 1-est (m0, m1, m2, m8, m9, m10) és az összes X-et (m13, m14, m15).

      Tehát a minimalizált függvény mindössze egyetlen tagból áll:

      $F(A, B, C, D) = \overline{B}$

      Ez egy rendkívül egyszerűsített eredmény, amelyet a „don’t care” feltételek nélkül sokkal nehezebb lenne elérni.

   Elsődleges implicánsok és lényeges elsődleges implicánsok

   A Karnaugh-tábla használatakor a cél az, hogy a logikai függvényt a lehető legegyszerűbb SOP (Sum of Products) formában fejezzük ki. Ennek eléréséhez kulcsfontosságú az elsődleges implicánsok (Prime Implicants – PI) és a lényeges elsődleges implicánsok (Essential Prime Implicants – EPI) fogalmának megértése.

   Egy implicáns egy logikai kifejezés egy szorzati tagja (pl. $A\overline{B}C$), amely részhalmaza egy nagyobb mintermhalmaznak. A Karnaugh-tábla kontextusában egy implicáns egy olyan téglalap alakú, kettő hatványú csoport, amely csak 1-eseket (és esetleg ‘X’ don’t care-eket) tartalmaz.

   Egy elsődleges implicáns (PI) egy olyan implicáns, amelyet nem lehet egy nagyobb implicánsba foglalni. Más szóval, egy elsődleges implicáns egy olyan csoport az 1-esekből (és X-ekből), amelyet nem lehet megnövelni (sem sorban, sem oszlopban, sem a tábla „körbetekerésével”) anélkül, hogy 0-t is belevennénk, vagy anélkül, hogy elveszítenénk a kettő hatványú méretet. Ezek a legnagyobb lehetséges csoportok, amelyeket a táblán találhatunk.

   Egy lényeges elsődleges implicáns (EPI) egy olyan elsődleges implicáns, amely lefed legalább egy olyan 1-es cellát, amelyet semmilyen más elsődleges implicáns nem fed le. Ezek azok a csoportok, amelyeket feltétlenül bele kell vennünk a végső minimális SOP kifejezésbe, mert nélkülük nem fednénk le az összes szükséges 1-est.

   A minimalizálási folyamat lépései az implicánsok azonosításával:

   1. Keresd meg az összes elsődleges implicánst (PI): Azonosíts az összes lehetséges legnagyobb téglalap alakú, kettő hatványú csoportot, amely csak 1-eseket (és X-eket) tartalmaz. Ne hagyd ki az átfedő csoportokat sem, ha azok önmagukban is maximálisak.
   2. Azonosítsd a lényeges elsődleges implicánsokat (EPI): Vizsgálj meg minden 1-es cellát. Ha egy 1-es cellát csak egyetlen PI fed le, akkor az a PI lényeges. Jelöld meg ezeket az EPI-ket és a lefedett 1-es cellákat.
   3. Fedezd le a fennmaradó 1-eseket: Ha maradtak olyan 1-es cellák, amelyeket az EPI-k nem fedtek le, válassz további PI-ket, hogy lefedd őket. Válassz olyan PI-ket, amelyek a lehető legtöbb még lefedetlen 1-est fedik le, és a legkevesebb új tagot adják a kifejezéshez. Cél a lehető legkevesebb PI kiválasztása.
   4. Írd fel a minimális SOP kifejezést: Az EPI-k és a további kiválasztott PI-k logikai összege adja a minimális SOP kifejezést.

   Példa:

   $F(A, B, C, D) = \sum(0, 1, 3, 7, 11, 12, 14, 15)$

   AB\CD	00	01	11	10
   00	1 (m0)	1 (m1)	1 (m3)	0 (m2)
   01	0 (m4)	0 (m5)	1 (m7)	0 (m6)
   11	1 (m12)	0 (m13)	1 (m15)	1 (m14)
   10	0 (m8)	0 (m9)	1 (m11)	0 (m10)

   PI-k azonosítása:

   1. PI1 (Quad): m0, m1, m3. Nem quad. M0, M1 egy kettes csoport. M1, M3 egy kettes csoport.
      * Nézzük az m0, m1, m3. A 00 sorban van m0, m1, m3.
      * Az m0 (0000), m1 (0001) egy kettes csoport: $\overline{A}\overline{B}\overline{C}$.
      * Az m1 (0001), m3 (0011) egy kettes csoport: $\overline{A}\overline{B}D$.
      * Nézzük a 00 sorban lévő 1-eseket (m0, m1, m3). Van egy négyes csoport, ami az m0, m1, m3-at tartalmazza, ha az m2 is 1 lenne. De nem az.
      * Van egy kettes csoport: m0 (0000) és m1 (0001) → $\overline{A}\overline{B}\overline{C}$.
      * Van egy kettes csoport: m1 (0001) és m3 (0011) → $\overline{A}\overline{B}D$.
      * Van egy kettes csoport: m3 (0011) és m7 (0111) → $\overline{A}CD$.
      * Van egy kettes csoport: m7 (0111) és m15 (1111) → $BCD$.
      * Van egy kettes csoport: m11 (1011) és m15 (1111) → $ACD$.
      * Van egy négyes csoport: m12 (1100), m14 (1110), m15 (1111), m13 (0). Nem.
      * Van egy négyes csoport: m12 (1100), m14 (1110). Ezek egy kettes csoport: $AB\overline{D}$.
      * Van egy kettes csoport: m14 (1110) és m15 (1111) → $ABC$.
      * Van egy kettes csoport: m11 (1011) és m15 (1111) → $ACD$.
      
      PI-k listája:
      1. $P_1$: m0, m1 ($\overline{A}\overline{B}\overline{C}$)
      2. $P_2$: m1, m3 ($\overline{A}\overline{B}D$)
      3. $P_3$: m3, m7 ($\overline{A}CD$)
      4. $P_4$: m7, m15 ($BCD$)
      5. $P_5$: m11, m15 ($ACD$)
      6. $P_6$: m12, m14 ($AB\overline{D}$)
      7. $P_7$: m14, m15 ($ABC$)

      Most keressünk nagyobb, négyes csoportokat:

      1. Quad 1 (négyes): m3, m7, m11, m15. Ez egy 2×2-es csoport a tábla jobb oldalán.
         * M3 (0011), M7 (0111), M11 (1011), M15 (1111).
         * Ezekben a cellákban C=1 és D=1. A és B változik. Tehát ez a csoport a $CD$ kifejezést adja.
      2. Quad 2 (négyes): m0, m1. Nem quad.
         * M0 (0000), M1 (0001). C változik. D fixen 0. A fixen 0, B fixen 0. → $\overline{A}\overline{B}\overline{C}$. Nem.
         * M0 (0000), M1 (0001). Ez egy kettes csoport.
         * Nézzük a szélső 1-eseket. M0 (0000) és M12 (1100). Ez egy kettes csoport: $\overline{B}\overline{C}\overline{D}$.
      3. Quad 3 (négyes): m12, m14. Nem quad.
         * M12 (1100), M14 (1110). B fixen 1, D fixen 0. A fixen 1. C változik. → $AB\overline{D}$.
         * M12 (1100) és m0 (0000). Ez egy kettes csoport: $\overline{C}\overline{D}$.

      Az összes PI (lehető legnagyobb csoportok):

      1. $PI_1$: $CD$ (m3, m7, m11, m15) – négyes csoport
      2. $PI_2$: $\overline{A}\overline{B}\overline{C}$ (m0, m1) – kettes csoport
      3. $PI_3$: $AB\overline{D}$ (m12, m14) – kettes csoport
      4. $PI_4$: $\overline{C}\overline{D}$ (m0, m12) – kettes csoport (átfed az m0-val)

      EPI-k azonosítása:

      Nézzük meg, melyik 1-es cellákat csak egyetlen PI fedi le:

      1. m0 (1): Fedve van $PI_2$ ($\overline{A}\overline{B}\overline{C}$) és $PI_4$ ($\overline{C}\overline{D}$) által. Nem EPI.
      2. m1 (1): Fedve van $PI_2$ ($\overline{A}\overline{B}\overline{C}$) által. Igen, ez az egyetlen PI, ami lefedi az m1-et. Tehát $PI_2$ ($\overline{A}\overline{B}\overline{C}$) egy EPI. Lefedi m0, m1.
      3. m3 (1): Fedve van $PI_1$ ($CD$) által. Igen, ez az egyetlen PI, ami lefedi az m3-at. Tehát $PI_1$ ($CD$) egy EPI. Lefedi m3, m7, m11, m15.
      4. m7 (1): Fedve van $PI_1$ ($CD$) által. Már lefedve az EPI által.
      5. m11 (1): Fedve van $PI_1$ ($CD$) által. Már lefedve az EPI által.
      6. m12 (1): Fedve van $PI_3$ ($AB\overline{D}$) és $PI_4$ ($\overline{C}\overline{D}$) által. Nem EPI.
      7. m14 (1): Fedve van $PI_3$ ($AB\overline{D}$) által. Igen, ez az egyetlen PI, ami lefedi az m14-et. Tehát $PI_3$ ($AB\overline{D}$) egy EPI. Lefedi m12, m14.
      8. m15 (1): Fedve van $PI_1$ ($CD$) által. Már lefedve az EPI által.

      Lényeges elsődleges implicánsok (EPI):

      • $PI_1 = CD$ (lefedi: m3, m7, m11, m15)
      • $PI_2 = \overline{A}\overline{B}\overline{C}$ (lefedi: m0, m1)
      • $PI_3 = AB\overline{D}$ (lefedi: m12, m14)

      Fennmaradó 1-esek lefedése:

      Az EPI-k lefedték az összes 1-est. (m0, m1, m3, m7, m11, m12, m14, m15).
      Az m0-t (0000) lefedi a $PI_2$ ($\overline{A}\overline{B}\overline{C}$).
      Az m1-et (0001) lefedi a $PI_2$ ($\overline{A}\overline{B}\overline{C}$).
      Az m3-at (0011) lefedi a $PI_1$ ($CD$).
      Az m7-et (0111) lefedi a $PI_1$ ($CD$).
      Az m11-et (1011) lefedi a $PI_1$ ($CD$).
      Az m12-t (1100) lefedi a $PI_3$ ($AB\overline{D}$).
      Az m14-et (1110) lefedi a $PI_3$ ($AB\overline{D}$).
      Az m15-öt (1111) lefedi a $PI_1$ ($CD$).

      Minden 1-es lefedésre került az EPI-kkel. Nincs szükség további PI-kre.

      A minimális SOP kifejezés:

      $F(A, B, C, D) = CD + \overline{A}\overline{B}\overline{C} + AB\overline{D}$

      Ez a módszer biztosítja, hogy a lehető legkevesebb tagot tartalmazó és a lehető legegyszerűbb tagokból álló kifejezést kapjuk meg.

      A Karnaugh-tábla és a POS (Product of Sums) forma

      

      A Karnaugh-tábla nemcsak az SOP (Sum of Products) forma egyszerűsítésére alkalmas az 1-esek csoportosításával, hanem a POS (Product of Sums) forma minimalizálására is. A POS forma maxtermek szorzataként írható fel, ahol egy maxterm egy olyan összegezési tag, amely minden változót tartalmaz, vagy eredeti, vagy negált formában, és amelyre a függvény kimenete 0. A POS forma egyszerűsítéséhez a Karnaugh-táblában a 0-kat kell csoportosítani, nem az 1-eseket.

      A POS forma egyszerűsítésének lépései:

      1. Töltsd fel a Karnaugh-táblát a függvény kimeneti értékeivel (0-k és 1-esek).
      2. Azonosítsd a 0-ás cellákat.
      3. Csoportosítsd a 0-kat ugyanazokkal a szabályokkal, mint az 1-eseket: téglalap alakú, kettő hatványú csoportok, amelyek a lehető legnagyobbak. Használd a „don’t care” feltételeket (X) itt is, ha segítenek nagyobb csoportokat képezni (azaz tekintsük őket 0-nak, ha előnyös).
      4. Minden egyes 0-s csoportból írj fel egy összegezési tagot. Ennél a lépésnél a változók negált formában jelennek meg: ha egy változó 0 az adott csoportban, akkor az eredeti formájában szerepel (pl. A), ha 1, akkor negált formában (pl. $\overline{A}$). Ez a dualitás elvének következménye.
         * Ha a változó értéke 0 a csoportban, akkor a változó eredeti formája szerepel a maxtermben (pl. A=0 → A).
         * Ha a változó értéke 1 a csoportban, akkor a változó negált formája szerepel a maxtermben (pl. A=1 → $\overline{A}$).
      5. A végső minimalizált POS forma az összes kapott összegezési tag szorzata lesz.

      Példa POS forma egyszerűsítésére (3 változós):

      Egyszerűsítsük a következő függvényt POS formában: $F(A, B, C) = \prod(0, 2, 4, 6)$, ami azt jelenti, hogy a függvény 0 az m0, m2, m4, m6 mintermekre.

      1. lépés: A tábla feltöltése (a 0-kat jelölve):

      A\BC	00	01	11	10
      0	0 (m0)	1 (m1)	1 (m3)	0 (m2)
      1	0 (m4)	1 (m5)	1 (m7)	0 (m6)

      2. lépés: A 0-k csoportosítása:

      Látható, hogy az m0, m2, m4, m6 cellák mind 0-ák. Ezek egy négyes csoportot (Quad) alkotnak. Ez a csoport lefedi a tábla bal és jobb szélső oszlopait (BC=00 és BC=10), valamint mindkét sorát (A=0 és A=1). Ha egy változó értéke fix a csoporton belül, akkor az szerepel a maxtermben. Ha változik, akkor kiesik.

      • A: Változik (0-ról 1-re), tehát kiesik.
      • B: Fixen 0 (mind a 00, mind a 10 oszlopokban). Tehát B szerepel a maxtermben.
      • C: Változik (0-ról 1-re a 00 és 10 oszlopok között). Tehát kiesik.

      A csoport által reprezentált maxterm tehát: $B$.

      3. lépés: A minimalizált POS kifejezés:

      Mivel az összes 0-át lefedtük egyetlen csoporttal, a minimalizált POS kifejezés mindössze egyetlen tagból áll:

      $F(A, B, C) = B$

      Ez az eredmény intuitív is, hiszen a függvény akkor 0, ha a B változó 0 (m0, m2, m4, m6). A többi minterm (m1, m3, m5, m7) esetén B=1, és a függvény is 1. Ez ismételten megmutatja a Karnaugh-tábla erejét a logikai függvények egyszerűsítésében, függetlenül attól, hogy SOP vagy POS formát keresünk.

      A Karnaugh-tábla korlátai és alternatívái

      Bár a Karnaugh-tábla rendkívül hatékony és intuitív eszköz a logikai függvények egyszerűsítésére, megvannak a maga korlátai. A fő korlát a változók számában rejlik:

      • 5 változó (32 cella): Két 4×4-es táblával ábrázolható (az egyik tábla az E=0 esetre, a másik az E=1 esetre). A csoportosítás vizuálisan nehezebbé válik, mivel a két tábla közötti „szomszédságot” is figyelembe kell venni. Ez már sok gyakorlatot igényel.
      • 6 változó (64 cella): Négy 4×4-es táblával ábrázolható. Itt a vizuális csoportosítás már rendkívül bonyolulttá válik, és a hibalehetőség jelentősen megnő.
      • 7 vagy több változó: A Karnaugh-tábla már gyakorlatilag használhatatlanná válik vizuális módszerként. A többdimenziós elrendezés emberi szemmel már nem követhető.

      Ezen korlátok miatt, különösen nagyobb változószámú függvények esetén, más egyszerűsítési módszerekre van szükség. A leggyakoribb alternatívák a következők:

      1. Quine-McCluskey algoritmus: Ez egy algoritmikus módszer, amely képes tetszőleges számú változós logikai függvények minimalizálására. A módszer két fő lépésből áll:
         • Elsődleges implicánsok generálása: A mintermeket bináris formában listázzuk, és párokat keresünk, amelyek csak egy bitben különböznek. Ezt a folyamatot ismételjük, amíg már nem lehet több párt alkotni. Ez generálja az összes elsődleges implicánst.
         • Fedő táblázat (Prime Implicant Chart): Egy táblázatot hozunk létre, ahol a sorok az elsődleges implicánsok, az oszlopok pedig a lefedendő mintermek. Ebből a táblázatból választjuk ki a minimális számú elsődleges implicánst, amelyek lefedik az összes mintermet.
           
           A Quine-McCluskey algoritmus garantáltan megtalálja a minimális SOP (vagy POS) kifejezést, és automatizálható számítógépes programokkal. Bár manuálisan is alkalmazható, nagy számú változó esetén rendkívül időigényes és hibalehetőségeket rejt.
      2. Heurisztikus algoritmusok és szoftveres eszközök: A modern digitális tervezésben a logikai függvények minimalizálását gyakran speciális szoftverek végzik (pl. CAD eszközök, logikai szintézis programok). Ezek a programok komplex algoritmusokat (gyakran heurisztikus megközelítéseket) használnak a minimalizálásra, amelyek sokkal nagyobb és bonyolultabb függvényeket is képesek kezelni, mint a Quine-McCluskey algoritmus. Ezek az eszközök optimalizálják a logikai áramköröket a sebesség, méret és energiafogyasztás szempontjából.
      3. Bináris döntési diagramok (Binary Decision Diagrams – BDD): Bár nem közvetlenül egyszerűsítő algoritmusok, a BDD-k egy kompakt és hatékony módja a Boole-függvények ábrázolásának. Gyakran használják őket a logikai szintézis és ellenőrzés során, és implicit módon tartalmazhatnak egyszerűsítéseket.

      A Karnaugh-tábla továbbra is alapvető fontosságú a digitális logika oktatásában és a kisebb, 2-4 (esetleg 5) változós problémák gyors, kézi megoldásában. Segít az intuitív megértésben és a vizuális gondolkodás fejlesztésében, ami elengedhetetlen a digitális tervezés alapjainak elsajátításához. Nagyobb rendszerek esetén azonban a szoftveres eszközök és algoritmikus módszerek válnak nélkülözhetetlenné.

      Gyakori hibák és tippek a Karnaugh-tábla használatához

      A Karnaugh-tábla rendkívül hatékony eszköz, de a helytelen alkalmazás hibás eredményekhez vezethet. Íme néhány gyakori hiba és tipp, hogyan kerülhetjük el őket:

      Gyakori hibák:

      1. Helytelen Gray-kód sorrend: Ez az egyik leggyakoribb és legsúlyosabb hiba. Ha a sor- vagy oszlopfejléceket nem a Gray-kód szabályai szerint (azaz csak egy bit eltérés a szomszédos cellák között) rendezi el, akkor a táblázatban vizuálisan szomszédos cellák valójában nem lesznek logikailag szomszédosak, ami hibás csoportosításokhoz vezet.
      2. Nem maximális csoportok: A cél a lehető legnagyobb kettő hatványú csoportok (2, 4, 8, 16, stb.) képzése. Ha egy 1-est (vagy X-et) tartalmazó csoportot kisebb méretben hagyunk, mint amekkora lehetne, akkor a végső kifejezés nem lesz minimális. Például, ha egy négyes csoportot két kettes csoportra bontunk, az redundáns tagokat eredményez.
      3. Nem téglalap alakú vagy nem kettő hatványú csoportok: A csoportoknak szigorúan téglalap alakúaknak (beleértve a négyzeteket is) és kettő hatványú méretűeknek kell lenniük. Például egy 3 cellás vagy L-alakú csoport érvénytelen.
      4. Nem összefüggő csoportok: A csoportokat alkotó celláknak élükkel kell érintkezniük. Az átlósan szomszédos cellák nem számítanak összefüggőnek a Karnaugh-tábla szempontjából.
      5. Minden 1-es lefedésének elmulasztása: Minden 1-es cellát le kell fedni legalább egy csoporttal. Ha egy 1-es kimarad, a függvény nem lesz helyesen implementálva.
      6. „Don’t care” feltételek hibás kezelése: Az X-eket csak akkor szabad 1-esnek tekinteni, ha segítenek nagyobb csoportot képezni. Nem kötelező őket lefedni, és nem szabad 1-esnek tekinteni, ha ezzel kisebb vagy felesleges csoport jönne létre.
      7. Redundáns csoportok: Bár az átfedés megengedett, sőt néha szükséges, kerülni kell a teljesen redundáns csoportokat, azaz azokat a csoportokat, amelyekben minden 1-es cellát már lefedett egy másik csoport. A lényeges elsődleges implicánsok azonosítása segít elkerülni ezt.

      Tippek a sikeres Karnaugh-tábla használatához:

      1. Gyakorlás, gyakorlás, gyakorlás: Mint minden vizuális és logikai feladatnál, a gyakorlás a kulcs. Minél több Karnaugh-táblát old meg, annál gyorsabban és pontosabban fogja felismerni a mintázatokat és a maximális csoportokat.
      2. Kezdj a legnagyobb csoportokkal: Mindig a legnagyobb lehetséges csoportokkal (oktettek, négyesek) kezdd a keresést. Ez segít maximalizálni az egyszerűsítést és csökkenteni a szükséges csoportok számát.
      3. Kezdd a „magányos” 1-esekkel: Ha van egy 1-es, amelyet csak egyetlen szomszédos 1-es (vagy X) fedhet le, akkor valószínűleg ez a kettes csoport egy EPI része. Ezeket érdemes először lefedni. Hasonlóképpen, ha egy 1-esnek egyáltalán nincs szomszédja, akkor az önmagában egy 1-es méretű csoportot (vagyis egy mintermet) fog alkotni.
      4. Jelölj és kövess nyomon: Használj ceruzát vagy különböző színű tollakat a csoportok jelölésére. Jelöld meg azokat az 1-es cellákat, amelyeket már lefedtél. Ez segít elkerülni a hibákat és nyomon követni a folyamatot.
      5. Ne feledkezz meg a „körbetekerésről”: A tábla szélei (felső-alsó, bal-jobb) logikailag szomszédosak. Ezt a „körbetekerés” effektust kihasználva gyakran lehet nagyobb csoportokat képezni.
      6. Ellenőrizd az eredményt: Miután felírtad a minimalizált kifejezést, érdemes ellenőrizni azt. Visszahelyettesítheti a kifejezésbe a bemeneti kombinációkat, vagy felrajzolhatja az igazságtábláját, és összehasonlíthatja az eredeti függvény igazságtáblájával.
      7. Válaszd ki a legkevesebb számú csoportot: A cél a lehető legkevesebb számú elsődleges implicáns kiválasztása, amelyek lefedik az összes 1-est. Az EPI-k kiválasztása után a fennmaradó 1-esek lefedésére olyan PI-ket válassz, amelyek a legkevesebb „új” 1-est fedik le, de a legnagyobb méretűek.

      A Karnaugh-tábla elsajátítása egy alapvető készség a digitális elektronikában és a számítógépes architektúrában. A fenti tippek és a kitartó gyakorlás segítségével bárki mesterévé válhat ennek a vizuális egyszerűsítési technikának.

      A Karnaugh-tábla gyakorlati alkalmazásai

      A Karnaugh-tábla nem csupán egy elméleti eszköz, hanem a digitális rendszerek tervezésének alapvető, gyakorlati fontosságú eleme. Alkalmazási területei széleskörűek, az egyszerű logikai kapuk tervezésétől a komplexebb digitális áramkörök optimalizálásáig.

      1. Digitális áramkörök tervezése és optimalizálása:
      Ez a legkézenfekvőbb és leggyakoribb alkalmazási terület. A Karnaugh-tábla segítségével a tervezők minimalizálhatják a kombinációs logikai áramköröket, mint például:

      • Dekóderek: Olyan áramkörök, amelyek bináris bemeneti kódot alakítanak át egyedi kimeneti jelekké (pl. 2-ről 4-re dekóder, amely két bináris bemenet alapján négy kimenet közül egyet aktivál). A Karnaugh-tábla segít a dekóder belső logikájának egyszerűsítésében.
      • Multiplexerek (MUX): Adatválasztók, amelyek több bemeneti vonal közül egyet választanak ki a választóbitek alapján, és azt továbbítják egyetlen kimenetre. A Karnaugh-tábla optimalizálja a választó logika kialakítását.
      • Demultiplexerek (DEMUX): Egy bemeneti jelet irányítanak több kimeneti vonal közül az egyikre, a választóbitek alapján. Hasonlóan a MUX-hoz, itt is segít a logikai egyszerűsítésben.
      • Adderek (összeadók): A bináris összeadás alapvető művelet a digitális rendszerekben. A fél- és teljes összeadók, valamint a ripple-carry adderek logikája Karnaugh-táblával minimalizálható.
      • Komparátorok: Két bináris szám összehasonlítására szolgáló áramkörök. A kimenet jelzi, hogy az egyik szám nagyobb, kisebb vagy egyenlő a másikkal. A logikai minimalizálás itt is elengedhetetlen.
      • Paritásgenerátorok és -ellenőrzők: Hibajavító kódokhoz használt áramkörök, amelyek egy adatsor paritásbitjét generálják vagy ellenőrzik.

      Az egyszerűsítés révén kevesebb logikai kapura van szükség, ami kisebb chipméretet, alacsonyabb energiafogyasztást és gyorsabb működést eredményez. Ez különösen fontos a beágyazott rendszerekben és mobil eszközökben, ahol a hely és az energia korlátozott.

      2. Szekvenciális logikai áramkörök (állapotgépek) tervezése:
      Bár a Karnaugh-tábla elsősorban kombinációs logikához készült, a szekvenciális áramkörök (például számlálók, regiszterek, állapotgépek) tervezése során is hasznos lehet. Az állapotátmeneti diagramokból levezetett bemeneti és kimeneti függvények, valamint a következő állapot függvények egyszerűsítésére használható.

      3. Szoftveres optimalizálás (ritkábban):
      Bár a Karnaugh-tábla hardverközpontú eszköz, a mögötte lévő logikai egyszerűsítési elvek áthelyezhetők a szoftverfejlesztésbe is. Komplex feltételes utasítások (if-else if-else láncok) vagy logikai kifejezések optimalizálásában segíthet a mögöttes logikai függvény minimalizálásával. Például, ha egy szoftver modul több bináris bemenettől függő logikai döntéseket hoz, a Karnaugh-tábla segíthet a kód egyszerűsítésében és hatékonyabbá tételében, elkerülve a felesleges ellenőrzéseket.

      4. Hibakeresés és elemzés:
      Egy meglévő digitális áramkör vagy logikai rendszer elemzésekor a Karnaugh-tábla segíthet megérteni a benne rejlő logikát, és azonosítani a lehetséges redundanciákat vagy hibákat. A táblázat vizuális jellege megkönnyíti a logikai összefüggések átlátását.

      5. Oktatás és tanulás:
      A Karnaugh-tábla alapvető fontosságú a digitális logika és a számítógép-tudomány oktatásában. Segít a diákoknak megérteni a Boole-algebrai egyszerűsítés vizuális és intuitív oldalát, és hidat képez az elméleti matematika és a gyakorlati hardvertervezés között. A fogalom elsajátítása elengedhetetlen a mélyebb digitális tervezési elvek megértéséhez.

      Összességében a Karnaugh-tábla egy rendkívül sokoldalú és hatékony eszköz, amely a digitális mérnökök és informatikusok mindennapi munkájának szerves részét képezi. Bár léteznek fejlettebb, automatizált algoritmusok a nagyon nagy függvények kezelésére, a Karnaugh-tábla vizuális ereje és intuitív megközelítése továbbra is felbecsülhetetlen értékű, különösen a tervezési folyamat kezdeti fázisaiban és az oktatásban.