Logikai függvények egyszerűsítése Karnaugh-tábla segítségével

Szerzők: Dr. Mingesz Róbert, Mellár János, Makan Gergely és Somogyi Anikó
Tananyag elsajátításához szükséges idő: 45 perc.

A lecke (olvasó és videólecke) bemutatja a Karnaug-táblála alapú logikai egyszerűsítés módszerét. A tananyagban számos példa látható, ez alapján el lehet sajátítani a legfontosabb lépéseket. A készségszíntű elsajátításhoz érdemes példákat megoldani, így mélyítve el a tudást. A tananyag egy rövid videóval indul, a videó tartalmának lényege pedig később szövegesen is részletezve van.

Tartalom

Videó: Logikai függvények egyszerűsítése Karnaugh-tábla segítségével
Példa algebrai egyszerűsítésre
A Karnaugh-tábla használata függvények egyszerűsítésére
Speciális esetek kezelése

Videólecke

Olvasólecke

Logikai függvények egyszerűsítésére egy módszer az algebrai egyszerűsítés. Itt a Boole-algebra azonosságait felhasználva alakítjuk át a függvényeket azon célból, hogy kevesebb tagból álljon a felírás vagy egyszerűbb legyen a fizikai megvalósítás.

Példa algebrai egyszerűsítésre

#	$A$	$B$	$C$	$Q$
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	0

A következő példákban felhasznált igazságtáblázat

A fenti igazságtáblázatnak megfelelő függvény egyszerűsítésének lehetséges lépései:

1) Kiinduló állapot a diszjunktív normálalak:
$Q=\bar{A}B\bar{C}+A\bar{B}\bar{C}+AB\bar{C}$
2) Az utolsó tagot megkettőzzük az „ $A+A=A$ ” azonosságnak megfelelően:
$Q=\bar{A}B\bar{C}+A\bar{B}\bar{C}+AB\bar{C}+AB\bar{C}$
3) Az egyenletet átrendezzük a kommutativitás szabályának megfelelően:
$Q=\bar{A}B\bar{C}+AB\bar{C}+A\bar{B}\bar{C}+AB\bar{C}$
4) A disztribbutivitás azonosságát felhasználva:
$Q=\left( \bar{A}+A \right) B\bar{C}+A \left(\bar{B}+B \right) \bar{C}$
5) Az „ $A+\bar{A}=1$ ” azonosság alapján:
$Q=B\bar{C}+A\bar{C}$
6) Utolsó lépésként kiemeljük $\bar{C}$ -t, és átrendezzük az $A$ és $B$ tagot:
$Q=\left( B+A \right) \bar{C}$

Az algebrai egyszerűsítések kivitelezése komoly odafigyelést és gyakorlatot igényel, ezért számos olyan módszer létezik, melyek valamilyen szempontból egyszerűbbé vagy automatizálhatóvá teszik az egyszerűsítés menetét. A következőben bemutatott Karnaugh-táblás módszer, valamint a Quine- McCluskey eljárás a fenti egyszerűsítés 1-5 pontját alkalmazza a háttérben, ezt a részletet érdemes megjegyezni, mivel így egyszerűbb lesz a módszerek megértése.

A Karnaugh-tábla használata függvények egyszerűsítésére

A Karnaugh-tábla olyan grafikus egyszerűsítési módszer, mely négy változói egyszerűen alkalmazható. Magasabb változószám esetén ritkán alkalmazzák. A Karnaugh-tábla felírásakor a változók sorrendje tetszőleges, azonban a táblázat felírása egyszerűbb, hogy ha az igazságtáblázatban megadott sorrendet követjük.

A korábbi példában szereplő három változós függvény Karnaugh-táblája (balra), valamint Veitch-táblája (jobbra). A két ábra ekvivalens. A Veitch-tábla esetén a tábla szélén lévő vonalak jelzik azt, hogy az adott változó hol vesz fel egyes értéket. A Karnaugh-tábla esetén ugyanezt a táblázat oldalai mentén szereplő bináris számok jelölik.

A Karnaugh-tábla megértésében segít, hogy ha beírjuk a minterm sorszámát, vagy akár az adott mintermhez tartozó biteket (lásd következő ábra). Hogy ha megnézzük az oszlopokat, feltűnik, hogy az utolsó két oszlop fel van cserélve. Így, az összes egymás melletti oszlop csak egy változóban különbözik egymástól.

Balra: Karnaugh-tábla a megfelelő mintermek sorszámával. Jobbra: szürkével jelölve a mintermek sorszámát valamint bitmintáját (feladatok megoldásánál ez nem szükséges).

Az egyszerűsítés során a táblában olyan tömböket jelölünk ki, melyek kettő hatványa számú egyest tartalmaznak (pl. 1, 2, 4, 8). Az összes egyest le kell fedni legalább egyszer, 0-kat pedig nem szabad lefedni. A tábla szélén lévő cellák szomszédosak a túloldalon lévő cellákkal. Egy-egy egyest tartalmazó minterm akár többször is felhasználható.

Hogy ha a fenti ábrát részletesen megfigyeljük, észrevehetjük, hogy az m6-os mintermet kétszer is felhasználtuk, hasonlóan az algebrai egyszerűsítés 2) lépéséhez. Az m2-es és m6-os a következő miatt vonható össze:

$\bar{A}B\bar{C}+AB\bar{C}=\left( \bar{A}+A \right) B\bar{C}=B\bar{C}$

Az $A$ változó, mely a kijelölt tömb mentén különböző értékeket vehet fel, kiesik. Az m4 és m6-os mintermek hasonló módon vonhatok össze:

$A\bar{B}\bar{C}+AB\bar{C}=A \left( \bar{B}+B \right) \bar{C}=A\bar{C}$

Ebben az esetben a $B$ változó esik ki. A fenti példa alapján látható, hogy az egyszerűsítés módszere lényegében megfelel a korábban bemutatott algebrai egyszerűsítés 2)-5) lépéseinek. A később tárgyalt Quine- McCluskey módszer is ugyanezt követi. Az utolsó két oszlop cseréjét is érthetjük ez alapján: a cél az, hogy egy-egy szomszédos cella (minterm) csak egy változóban különbözhessen, így azokat össze lehessen vonni.

Az egyszerűsítés utolsó lépése, a Karnaugh-tábla alapján felírni a primimplikánsokat tartalmazó algebrai alakot, ahol minden egyest tartalmazó mintermet legalább egyszer lefedtünk, de nincsenek benne „felesleges” tömbök. Az egyes tagok felírása egyszerű: minden olyan változó, melynek értéke változik a tömbön belül kiesik.

$Q=B\bar{C}+A\bar{C}$

A kapott függvény nem feltétlenül a legegyszerűbb alak (kiemelhető a $\bar{C}$ ). Ez nem minden esetben jelent problémát, van, amikor ennek az alaknak az áramköri megvalósítása a legegyszerűbb.

A kapott végeredmény megvalósítása logikai kapukkal

A fenti ábrán látható, hogy hogyan lehet megvalósítani a végeredményként kapott függvényt logikai kapukkal. A kapcsolás három fajta logikai kaput igényel. A De-Morgan azonosságoknak megfelelően, azonban a VAGY kaput helyettesíthetjük ÉS kapuval is, amennyiben a bemeneteket és a kimeneteket is negáljuk. Az ennek megfelelő, egyszerűsített végeredménye a következő ábrán látható.

A végeredmény megvalósítésa kizárólag NEM-VAGY kapukkal

Vegyük a következő példát: $Q=\bar{A}B\bar{C}+\bar{A}BC+A\bar{B}\bar{C}+AB\bar{C} = \sum^3 (2,3,4,6)$

Az egyszerűsítés eredménye: $Q=\bar{A}B+A\bar{C}+B\bar{C}$ . Figyeljük meg, hogy az ábrán zölddel jelölt implikáns olyan mintermeket fed le, melyeket a másik kettő is lefed, a tag redundáns. Így ez a tag elhagyható, a végeredmény egyszerűbb lesz: $Q=\bar{A}B+A\bar{C}$ .

A Karnaugh-tábla a redundáns implikáns elhagyását követően.

A Karnaugh tábla négy változó esetén 4×4-es méretű lesz. Itt az utolsó két oszlop van megcserélve, ennek oka szintén az, hogy így a szomszédos mintermek csak egyetlen változóban térnek el. Szintén két módszer terjedt el a változók jelölésére (Karnaugh- és Veitch-féle), a feladatok megoldásánál bármelyik használható.

Példaként tekintsük a következő függvényt: $Q=\bar{A}\bar{B}\bar{C}D+\bar{A}\bar{B}CD+\bar{A}BCD+A\bar{B}CD$ .

Példa négy változós Karnaugh-táblás egyszerűsítésre.

Az egyszerűsítés eredménye: $Q=\bar{A}\bar{B}D+BCD+\bar{A}CD$ . Az utolsó, az ábrán zölddel jelölt tag redundáns, így elhagyható.

A Karnaugh táblában a 0 jelöléseket gyakran elhagyjuk, gyorsítva az eljárást. A következő példában is ezt követjük. A példában láthatjuk, hogy mindig a legnagyobb egybefüggő, kettő hatványú mintermet tartalmazó implikánsokat keressük, jelen esetben egyetlen egyet.

A tábla szélein lévő mintermek, illetve a sarkon lévő mintermek is egymással szomszédosak, ahogy a következő két példában lehet látni.

Példa egymással szomszédos, a tábla szélén lévő mintermekre. A bal oldali végeredmény: $Q=B\bar{D}$ , a jobboldali: $Q=\bar{B}\bar{D}$

Balra: $Q=\sum^4(1,3,5,6,7,8,9,10,11,14,15)=\bar{A}D+BC+A\bar{B}$
Jobbra: *$Q=\sum^4(1,3,5,6,14,15)=\bar{A}\bar{B}D+\bar{A}\bar{C}D+BC\bar{D}+ABC$*

Balra: $Q=\sum^4(1,3,5,6,7,8,9,10,11,14,15)=\bar{A}D+BC+A\bar{B}$
Jobbra: *$Q=\sum^4(1,3,5,6,14,15)=\bar{A}\bar{B}D+\bar{A}\bar{C}D+BC\bar{D}+ABC$*

Vannak olyan esetek, amikor valamilyen okból, adott bemeneti kombináció mellett nem határozzuk meg a kimenet értékét (közömbös kombinációk, don’t care). Ezeket a sorokat X-el jelöljük mind az igazságtáblázatban, mind pedig a Karnaugh-táblában. Summával kifejezett algebrai alak esetén ezeket a mintermeket általában $d$ -vel jelöljük: $Q=\sum^4(1,3,5,6,14,15)+d(7,8,9,10,11)$

Az egyszerűsítés során szabadon eldönthetjük, hogy a táblában X-el jelölt, közömbös kombinációkat bevesszük-e a tömbök kialakításába, vagy nem. A cél mindig az, hogy a legegyszerűbb végeredményt kapjuk:

Az egyszerűsítés menete közömbös mintermek esetén

Az egyszerűsítés során a 7. mintermet figyelembe vesszük, a 8-11-es mintermeket viszont nem. A végeredmény: $Q=\bar{A}D+BC$ . Hasonlítsuk össze a végeredményt azzal, mint amikor az összes X helyén egyes van, vagy az összes X helyén nulla van (lásd korábban).

Összefoglalva az egyes lépéseket:

1. lépés
A Karnaugh táblában egyest írunk be azon mintermek helyésre, ahol az igazságtáblázatban is egyes szerepel.
2. lépés
A karnaugh táblában megkeressük a lehetséges legnagyobb implikánsokat. Az implikánsok kettő hatvány darab mintermet tartalmazhatnak. Az összes egyest legalább egyszer bekarikázzuk.
3. lépés
Megkeressük a redundáns implikánsokat, ezek kihagyhatók a végeredményből
4. lépés
Felirjuk a végeredményt függvény alakjában. Szükség esetén felrajzoljuk a függvényt megvalósító kapcsolási rajzot.

Előző anyag: Logikai függvények kanonikus alakja
Digitális architektúrák tananyag | Digitális laboratóriumi gyakorlatok tananyag

Ajánlott irodalom

Matijevics István: Digitális technika példatár, Typotex Kiadó, 2011, elérhető: Digitális tankönyvtár.
Interaktív program Matijevics István példatárához:
http://www.inf.u-szeged.hu/projectdirs/digipeldatar/digitalis_peldatar.html
(A program használata a flash bővítmény engedélyezését igényli)
David Money Harris, Sarah L. Harris: Digital Design and Computer Architecture (elérhető elektronikusan a SZTE Klebesberg Könyvtárban)
SULiNET: A logikai függvények szabályos alakjai

Jelen tananyag a Szegedi Tudományegyetemen készült az Európai Unió támogatásával. Projekt azonosító: EFOP-3.4.3-16-2016-00014

Mingesz Róbert

hivatalos oldal

Logikai függvények egyszerűsítése Karnaugh-tábla segítségével

Tartalom

Videólecke

Olvasólecke

Példa algebrai egyszerűsítésre

A Karnaugh-tábla használata függvények egyszerűsítésére

#1. Az alábbiak közül melyik helyesen kiválasztott implikáns?

#2. Melyik tábla felel meg az fenti képletnek?

#3. Melyik végeredmény felel meg az fenti függvénynek?

Results

Ajánlott irodalom