4.8-Harti-Karnaugh.pdf

www.circuiteelectrice.ro Electronic digital Hri Karnaugh

135

8 Hri Karnaugh

8.1 De ce hri Karnaugh

La ce ne folosesc hrile Karnaugh? Harta Karnaugh, asemenea algebrei booleene, este o metod de

simplificare a circuitelor logice digitale. Vedei exemplul incineratorului de deeuri toxice ca i metod de

simplificare boolean a unui circuit logic. Harta Karnaugh va simplifica circuitul mult mai rapid i mai uor n

majoritatea cazurilor.

Simplificarea boolean este de fapt mai rapid n cazul n care avem maxim dou variabile booleene. Putem

folosi aceast metod chiar i n situaia n care avem trei variabile, dar metoda boolean este mai greoaie n acest

caz. Cu patru variabile de intrare, algebra boolean devine imposibil. Hrile Karnaugh sunt mai rapide i mai

uor de implementat. Acestea pot fi folosite cu succes n situaiile n care avem pn la ase variabile de intrare.

ntre ase i opt, mai putem nc folosi aceste hri. Peste aceast valoare, este indicat s folosim un program

software specializat pentru realizarea simplificrilor logice.

8.2 Diagrame Venn

Matematicienii utilizeaz diagramele Venn pentru reprezentarea relaiilor logice dintre mulimi (colecii de

obiecte). Ne vom folosi de diagramele Venn pentru a face tranziia dintre algebra boolean i hrile Karnaugh.

8.2.1 Mulimi i submulimi

O mulime este o colecie de obiecte dintr-un univers dat. Elementele mulimii sunt obiecte ce aparin

mulimii. Elementele unei mulimi au de obicei ceva n comun, dei acest lucru nu este neaprat necesar. Din

universul numerelor reale, de exemplu, mulimea tuturor numerelor ntregi pozitive {1, 2, 3 ...}, este o mulime.

Mulimea {3, 4, 5} este o mulime mai mic, sau o submulime a mulimii numerelor ntregi pozitive. Un alt

exemplu este mulimea tuturor bieilor dintr-o clas, unde numrul elevilor din clas reprezint universul discuiei.

V putei gndi i la alte mulimi?

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/aritmeticahttp://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/transformarea-tabelelor-de-adevar


136

8.2.2 Diagrame Venn - exemple

Diagrama Venn din figura de mai jos stnga, reprezint mulimea A (n interiorul cercului) din universul U

(aria dreptunghiular). Dac tot ceea ce se afl n interiorul cercului este A, atunci tot ceea ce se afl n exteriorul

cercului nu este A (A-negat sau A'). Prin urmare, n figura de mai jos centru, am denumit aria dreptunghiular din

afara cercului A cu A' n loc de U. B i B' se reprezint similar (figura de mai jos dreapta).

Fig. 8-1 diagrame Venn; exemple

Ce se ntmpl dac i A i B se afl n acelai univers? Exist patru posibiliti:

Fig. 8-2 diagrame Venn; cazuri

S relum fiecare din cele patru posibiliti n parte:

Fig. 8-3 mulimi disjuncte

Primul exemplu indic faptul c mulimile A i B nu au niciun element comun (disjuncte), conform

diagramei Venn. Regiunile celor dou mulimi nu se suprapun n niciun punct. De exemplu, s presupunem c

http://www.circuiteelectrice.ro/


137

mulimile A i B ar conine urmtoarele elemente: A = {1, 2, 3, 4}, B = {5, 6, 7, 8}. Niciunul dintre elementele

mulimii A nu este inclus n mulimea B sau invers. Prin urmare, cele dou cercuri nu se suprapun.

Fig. 8-4 mulimea A inclus n mulimea B

n cel de al doilea exemplu, mulimea A este inclus total n mulimea B. Cum putem explica aceast

situaie? S presupunem c mulimile A i B conin urmtoarele elemente: A = {1, 2} i B = {1, 2, 3, 4, 5, 6, 7, 8}.

Toate elementele din A se regsesc i n B. Prin urmare, mulimea A este o submulime a mulimii B, iar cercul A

este inclus n cercul B.

Fig. 8-5 mulimi suprapuse perfect

n cel de al treilea caz, mulimile A i B se suprapun perfect. Din diagrama Venn, putem deduce c cele

dou mulimi conin exact aceleai elemente. S presupunem c mulimile arat astfel: A = {1, 2, 3, 4} i B = {1, 2,

3, 4}. Prin urmare A = B. Cele dou mulimi sunt identic egale deoarece conin exact aceleai elemente.

Fig. 8-6 mulimi suprapuse parial



138

n ultimul caz, cele dou mulimi se suprapun, dar nu complet ci doar parial. Acest lucru ne spune c exist

elemente comune celor dou mulimi, dar c fiecare mulime are i elementele sale unice. S presupunem c cele

dou mulimi ar arta astfel: A = {1, 2, 3, 4} i B = {3, 4, 5, 6}. Ambele mulimi conin elementele 3 i 4. Acesta

este i motivul pentru care cele dou cercuri sunt suprapuse.

8.3 Relaii booleene cu diagrame Venn

8.3.1 Funcia logic SAU (adunarea boolean)

n ultimul exemplu din seciunea precedent, mulimile A i B s-au suprapus parial. Iniial, ne vom

concentra atenia asupra ntregii regiuni haurate de mai jos, abia apoi vom trece la analizarea regiunii comune

celor dou mulimi. S utilizm expresii booleene pentru desemnarea regiunilor diagramelor Venn, conform figurii

de mai jos:

Fig. 8-7 funcia logic SAU; reprezentarea prin diagrame Venn

Aria mulimii A este haurat cu rou, iar cea a mulimii B cu albastru. Dac analizm ntreaga aria

haurat (suma total a tuturor ariilor haurate), indiferent de culoare sau stil, obinem figura din dreapta sus.

Aceasta corespunde funciei logice SAU, iar expresia boolean este A + B, aria fiind cea haurat cu linii diagonale.

Tot ceea ce se afl n afar ariei haurate reprezint (A + B)'.

8.3.2 Funcia logic I (nmulirea boolean)

O alt metod de interpretare a diagramei Venn cu regiuni suprapuse, este analizarea regiunii comune att

mulimii A ct i mulimii B, aria dublu haurat de mai jos (stnga). Aceast arie corespunde funciei logice I, iar

expresia boolean este AB (jos dreapta). Tot ceea ce se afl n afara ariei dublu haurate AB reprezint (AB)':

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh/diagrame-vennhttp://www.circuiteelectrice.ro/electronica-digitala/porti-logice/porti-logice-cu-doua-intrari


139

Fig. 8-8 funcia logic SAU; reprezentarea prin diagrame Venn

Observai c unele elemente ale mulimilor A i B de sus, sunt elemente ale mulimii (AB)', dar niciunul

dintre elementele mulimii (AB)' nu se afl n interiorul ariei dublu haurate AB.

8.3.3 Expresii booleene cu diagrame Venn

8.3.3.1 Diagrama Venn pentru A'B

Vom trece acum la dezvoltarea unor expresii booleene. De exemplu, s presupunem c dorim reprezentarea

prin diagrame Venn a expresiei booleene A'B (A' I B).

Paii sunt urmtorii: haurarea ariei A'; haurarea ariei B; realizarea funciei I (A'B) prin suprapunerea

celor dou regiuni precedente. Am putea s ne oprim aici, dar, pentru claritate, putem pstra doar aria dublu

haurat:

Fig. 8-9 diagrama Venn pentru A'B



140

Expresia A'B reprezint regiunea n care A' i B se suprapun. Regiunea nehaurat din afara ariei A'B este

(A'B)'.

8.3.3.2 Diagrama Venn pentru B' + A

Putem ncerca acelai lucru cu expresia boolean SAU. De exemplu, s presupunem c dorim s

reprezentm prin diagrame Venn expresia B' + A.

Paii sunt urmtorii: ncepem cu haurarea lui B, i apoi a regiunii B'; suprapunem A peste B'. Din moment

ce suntem interesai de realizarea funciei SAU, vom cuta s reprezentm ntreaga arie format de cele dou

mulimi, indiferent de stilul haurrii. Prin urmare A + B' reprezint ntreaga arie haurat:

Fig. 8-10 diagrama Venn pentru B'+A

Pentru claritate, putem reprezenta ntreaga regiune printr-o singur haur (jos stnga):

Fig. 8-11 diagrama Venn pentru B'+A

8.3.3.3 Diagrama Venn pentru (A + B')'

Aria haurat cu verde de mai sus este rezultatul expresiei A + B'. Trecnd la (A + B')', cutam

complementul expresiei A + B', reprezentat prin aria nehaurat din figura de mai sus stnga. Aplicnd teorema lui

DeMorgan i negarea dubl (A'' = A), ajungem la rezultatul (A + B')' = AB'. Prin urmare, cele dou regiuni sunt

identice.

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/teoremele-lui-demorganhttp://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/teoremele-lui-demorganhttp://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/teoremele-lui-demorgan


141

Putem face acum observaia c diagramele Venn nu demonstreaz nimic. Avem nevoie de algebra boolean

pentru acest lucru. Totui, diagramele Venn pot fi utilizate pentru verificare i vizualizare. n exemplul de mai sus,

am verificat i vizualizat teorema lui DeMorgan cu ajutorului unei diagrame Venn.

8.3.3.4 Diagrama Venn pentru A' + B' i (A' + B')'

Fig. 8-12 diagrama Venn pentru A' + B' i (A' + B')'

8.3.3.5 Artai c A' + B' = AB

Fig. 8-13 diagrama Venn pentru A' + B'

8.3.4 Diagrame Venn cu 3 variabile



142

Diagrama Venn de mai jos conine trei regiuni haurate, A (rou), B (albastru) i C (verde). Intersecia

tuturor regiunilor n centru reprezint expresia boolean ABC. Exist o alt regiune unde A i B se intersecteaz,

reprezentnd expresia boolean AB. Similar, intersecia ariei A cu C i B cu C reprezint expresia boolean AC,

respectiv BC.

Fig. 8-14 diagrama Venn pentru trei variabile

Observnd mrimea regiunilor descrise de funcia I de mai sus, putem vedea c mrimea regiunii variaz

cu numrul variabilelor asociate expresiei I.

8.4 Transformarea diagramelor Venn n hri Karnaugh

8.4.1 Hri Karnaugh cu dou variabile

ncepem transformarea unei diagrame Venn ntr-o hart Karnaugh prin desenarea unei mulimi A n

universul A' (figura de mai jos, a):

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh/diagrame-venn


143

Fig. 8-15 procesul de transformarea a diagramei Venn n hart Karnaugh

Extindem apoi cercul A (b i c), modificm forma lui la punctul (d), i transformm A ntr-un dreptunghi

(e). Tot ceea ce nu se afl n A este A'. Desenm un dreptunghi i pentru A' (f). De asemenea, nu folosim hauri

pentru hrile Karnaugh. Ceea ce avem pn n acest moment este o hart Karnaugh cu o singur variabil. Acest

lucru nu ne ajut ns. Avem nevoie de variabile multiple.

Figura (a) de mai jos este identic diagramei Venn precedente, cu diferena c notaiile A i A' se afla

deasupra diagramei i nu n interior. Urmnd un proces similar, putem construi o diagram Venn dreptunghiular

pentru B i B' (b). Vom trece acum la suprapunerea diagramelor de la (a) i (b) pentru obinerea rezultatului (c), la

fel cum am fcut pentru diagramele Venn. Motivul pentru care realizm acest lucru este pentru a observa ceea ce

este comun celor dou regiuni suprapuse - de exemplu, locul n care A se suprapune cu B. Ptratul din dreapta jos

(c) corespunde relaiei AB, unde A se suprapune cu B:

Fig. 8-16 procesul de transformarea a diagramei Venn n hart Karnaugh



144

Totui, nu vom pierde vremea desennd hri Karnaugh precum cea de mai sus (c), ci vom folosi o versiune

simplificat:

Fig. 8-17 versiunea simplificat a unei hri Karnaugh

Coloana format din cele dou celule de sub A' este asociat mulimii A' (stnga); similar pentru celelalte

mulimi. Pentru simplitate, regiunile nu vor fi delimitate att de clar precum n cazul diagramelor Venn.

Harta Karnaugh din dreapta este o form alternativ utilizat n majoritatea textelor. Numele variabilelor

sunt trecute lng linia diagonal. A-ul de deasupra diagonalei indic faptul c variabila A (i A') aparine

coloanelor. 0 este folosit pentru A' iar 1 pentru A. B-ul de sub diagonal este asociat cu liniile: 0 pentru B' i 1

pentru B.

8.4.2 Exemplu

Marcai csuele corespunztoare expresiei booleene AB n diagrama Karnaugh de mai sus cu 1. Soluie:

haurm sau ncercuim regiunea corespunztoare lui A; marcm apoi regiunea corespunztoare lui B. Intersecia

celor dou regiuni reprezint AB; trecem un 1 n aceast csu. Nu este ns necesar s ncercuim propriu-zis

regiunile A i B:

Fig. 8-18 exemplu de utilizare a hrilor Karnaugh

8.4.3 Hri Karnaugh cu trei variabile

Trecem acum la dezvoltarea unei hri Karnaugh pornind de la diagrame Venn. Universul (interiorul

dreptunghiului negru) este mprit n dou regiuni nguste A' i A. B i B' mpart universul n dou regiuni ptrate.

C-ul ocup o regiune ptrat n mijlocul dreptunghiului, iar C' este mprit n dou dreptunghiuri verticale de

fiecare parte a ptratului C:



145

Fig. 8-19 hart Karnaugh cu trei variabile

n figura final suprapunem toate cele trei variabile, ncercnd s delimitm clar fiecare regiune. Aceast

hart Karnaugh cu 3 variabile are 23

Fig. 8-20 hart Karnaugh cu trei variabile

Totui, n mod normal nu vom nota o hart Karnaugh conform figurii de mai sus stnga. Notarea hrilor

Karnaugh se va face conform figurii din dreapta. Fiecare regiune este unic determinat printr-un produs de 3

variabile, o expresie boolean I.

Cele dou forme diferite de mai sus sunt echivalente, i reprezint forma final a acestora. Versiunea din

dreapta este puin mai uor de folosit, din moment ce nu suntem nevoii s scriem toate variabilele de fiecare dat,

ci doar 1 i 0. Notaia B'C', B'C, BC i BC' din stnga este echivalent cu 00, 01, 11 respectiv 10 din dreapta. A i

A' sunt echivalente cu 0 respectiv 1.

= 8 regiuni, csuele din interiorul hrii. Fiecare regiune este unic determinat

prin intermediul celor trei variabile booleene (A, B i C). De exemplu ABC' reprezint regiunea din dreapta jos (*),

iar A'B'C' reprezint regiunea din stnga sus (x):



146

8.5 Hri Karnaugh, tabele de adevr i expresii booleene

8.5.1 Metode diferite de reprezentare a funciilor logice

Hrile Karnaugh simplific funciile logice mult mai rapid i mai uor n comparaie cu algebra boolean.

Dorim simplificarea circuitelor logice spre cel mai mic cost posibil prin eliminarea componentelor. Definim cel mai

mic cost ca fiind cel mai mic numr de pori cu cel mai mic numr de intrri pe poarta.

Mai jos am reprezentat cinci metode diferite de reprezentare a aceluiai lucru: o funcie logic aleatoare cu

dou intrri. Metodele sunt: logica ladder, pori logice, tabel de adevr, hart Karnaugh i ecuaie boolean. Ceea ce

vrem s subliniem este c toate acestea sunt echivalente. Dou intrri A i B pot lua valori de 0 sau 1, nalt sau jos,

deschis sau nchis, adevrat sau fals, n funcie de caz. Exist 22

Fig. 8-21 reprezentarea unei funcii logice prin diferite metode

= 4 combinaii pentru generarea unei ieiri. Acest

lucru se aplic tuturor celor cinci exemple.

Aceste patru ieiri pot fi observate prin intermediul unei lmpi la ieirea circuitului ce utilizeaz logica

ladder. Aceste ieiri pot fi nregistrate ntr-un tabel de adevr sau ntr-o hart Karnaugh. Privii harta Karnaugh ca i



147

un tabel de adevr cosmetizat. Ieirea ecuaiei booleene poate fi obinut cu ajutorul legilor algebrei booleene i

transferat tabelului de adevr sau hrii Karnaugh. Care din cele cinci metode echivalente de reprezentare ar trebui

s o folosim? Cea mai folositoare pentru situaia n cauz.

Ieirile unui tabel de adevr corespund unu-la-unu elementelor unei hri Karnaugh. ncepnd cu partea de

sus a tabelului de adevr, intrrile A = 0 i B = 0 produc ieirea . Observai c aceiai ieire, , se regsete pe

harta Karnaugh la adresa A = 0, B = 0, n partea de sus stnga, la intersecia coloanei B = 0 cu rndul A = 0.

Celelalte ieiri ale tabelului de adevr, , respectiv , corespunztoare intrrilor AB = 01, 10 respectiv 11 au de

asemenea corespondent pe harta Karnaugh:

Fig. 8-22 corespondena tabel de adevr - harta Karnaugh

8.5.2 Structura hrilor Karnaugh

Pentru uurina expunerii, prezentm mai jos regiunile adiacente ale hrii Karnaugh cu dou variabile

folosind metoda dreptunghiular a diagramei Venn din seciunea precedent:



148

Fig. 8-23 hri Karnaugh

Regiunile i sunt adiacente pe harta Karnaugh. Nu putem spune acelai lucru despre tabelul de adevr

precedent, ntruct exist o alt valoare () ntre ele. Acesta este i motivul organizrii hrilor Karnaugh sub form

de matrice ptrat. Regiunile cu variabile booleene comune trebuie s se afla una lng cealalt. Aceast structur

este i trebuie s fie uor de recunoscut cnd privim o astfel de hart, din moment ce i au variabila B' n comun.

tim acest lucru deoarece B este 0 (identic cu B') pentru coloana de deasupra celor dou regiuni. Comparai acest

lucru cu diagrama Venn de deasupra hrii Karnaugh.

n aceiai ordine de idei, putem observa c i au ca i variabil comun B (B = 1). Prin urmare, i au

n comun variabila boolean A' (A = 0), iar i variabila A (A = 1).

Pe scurt, am ncercat s grupm variabilele booleene pe regiuni astfel nct s reias elementele lor

comune. Hrile Karnaugh sunt organizate pentru a ne oferi exact aceast imagine.

8.5.3 Exemple de utilizare a hrilor Karnaugh

8.5.3.1 Exemplul 1

Tabelul de adevr de mai jos conine dou valori de 1. Harta Karnaugh trebuie s conin i ea tot dou

valori de 1:

Lum prima valoare de 1 din rndul al doilea al tabelului de adevr

Observm adresa AB a tabelului de adevr

Localizm regiunea hrii Karnaugh ce conine aceiai adres

Scriem un 1 n acea regiune



149

Repetm procesul pentru valoarea 1 din ultima linie a tabelului de adevr

Fig. 8-24 transformarea tabelului de adevr n harta Karnaugh

S ncercm s scriem acum pentru harta Karnaugh de mai sus i expresia boolean. Soluia este prezentat

mai jos:

Fig. 8-25 scrierea expresiei booleene folosind harta Karnaugh

Cutam regiuni adiacente (regiunile diagonale nu sunt adiacente), ntruct acestea vor avea una sau mai

multe variabile booleene n comun

Grupm cele dou valori de 1 din coloan

Cutm acea sau acele variabile ce sunt comune pentru grup i scriem acest lucru ca i rezultat boolean (n

cazul nostru acesta este B)

Ignorm variabilele ce nu sunt identice pentru un grup de regiuni (n cazul nostru, A variaz, este att 1 ct

i 0, prin urmare, ignorm A)

Ignorm de asemenea orice variabil ce nu este asociat cu regiunile ce conin 1 (B' nu conine niciun 1,

prin urmare, ignorm B')

Rezultatul final i prin urmare expresia boolean asociat hrii Karnaugh precedente este B

Acest lucru poate fi observat mai uor comparnd diagramele Venn din dreapta, n mod special coloana B.



150

8.5.3.2 Exemplul 2

Scriei expresia boolean asociat hrii Karnaugh de mai jos:

Fig. 8-26 scrierea expresiei booleene asociat hrii Karnaugh

Urmnd o logic asemntoare celei de mai sus, grupm toate valorile de 1 i gsim variabila comun

ntregului grup astfel format; rezultatul este A'.

8.5.3.3 Exemplul 3

Pentru tabelul de adevr de mai jos, gsii harta Karnaugh corespunztoare i scriei apoi expresia boolean

folosind rezultatul obinut. Soluia este prezentata mai jos:

Fig. 8-27 scrierea expresiei booleene asociat hrii Karnaugh

Transferm valorile de 1 din tabelul de adevr n locaiile corespunztoare pe harta Karnaugh

Grupm cele dou valori de 1 pe coloana de sub B = 1

Grupm cele dou valori de 1 de pe rndul A = 1

Scriem rezultatul produsului primului grup (B)

Scriem rezultatul produsului celui de al doilea grup (A)

Scriem suma produselor celor doi termeni de mai sus (A + B)

Soluia din mijloc este cea mai simpl i prezint cel mai mic cost. O soluie mai puin dorit este cea din

dreapta. Dup gruparea valorilor 1, facem greeala de a forma un grup cu o singur regiune. Motivul pentru care



151

acest lucru nu este de dorit este urmtorul: acest grup ce conine o singur regiune are termenul produsului egal cu

AB'; soluia ntregii hrii este n acest caz AB' + B, iar aceasta nu reprezint cea mai simpl soluie.

Metoda corect const n gruparea acestui 1 singur cu regiunea din dreapta lui, regiune ce conine la rndul

ei o valoare de 1, chiar dac aceasta a fost deja inclus ntr-un alt grup. (coloana B). Putem refolosi regiuni pentru a

forma grupuri mai mari. De fapt, este chiar indicat s facem acest lucru ntruct conduce la rezultate mai simple.

Trebuie s facem observaia c oricare dintre soluiile de mai sus, att cea corect ct i cea greit sunt

de fapt corecte din punct de vedere logic. Ambele circuite vor genera aceiai ieire. Pur i simplu, circuitul corect

presupune un cost mai redus de implementare fizic.

8.5.3.4 Exemplul 4

Completai o hart Karnaugh folosind expresia boolean de mai jos. Scriei apoi expresia boolean a

rezultatului:

Fig. 8-28 simplificarea expresiei boolene folosind harta Karnaugh

Expresia boolean conine trei sume de produse. Va exista cte o valoare de 1 pe harta Karnaugh pentru

fiecare produs. Dei, n general, numrul valorilor de 1 pe produs variaz cu numrul variabilelor produsului n

comparaie cu mrimea hrii Karnaugh. Termenul produsului reprezint adresa regiunii unde vom introduce

valoare de 1. Primul termen este A'B i corespunde adresei 01 a hrii. Introducem un 1 n aceast regiune. Similar,

introducem i ceilali doi termeni de 1.

Trecem apoi la gruparea termenilor i simplificarea rezultatului conform exemplului precedent.

8.5.3.5 Exemplul 5

Simplificai circuitul logic de mai jos:



152

Fig. 8-29 circuit logic iniial (nesimplificat)

Scriem expresia boolean pentru circuitul logic iniial

Transferm expresia boolean rezultat ntr-o hart Karnaugh

Grupm regiunile precum n exemplele precedente

Scriem expresii booleene pentru fiecare grup, conform exemplelor precedente

Redesenm circuitul logic simplificat

Fig. 8-30 circuit logic simplificat cu ajutorul hrii Karnaugh

8.5.3.6 Exemplul 6

Simplificai circuitul logic de mai jos:

Fig. 8-31 simplificarea circuitului logic



153

Scriem expresia boolean pentru circuitul logic iniial

Completm harta Karnaugh

Observm c nu putem forma niciun grup care s conin mai mult de dou regiuni 1

Prin urmare, simplificarea nu este posibil, iar expresia final este identic cu cea iniial (SAU-exclusiv)

8.6 Simplificarea circuitelor logice cu hri Karnaugh

Exemplele de simplificare a circuitelor logice de pn acum puteau fi realizate la fel de bine i cu ajutorul

algebrei booleene. Problemele de simplificare logic reale implic ns utilizarea unor hri Karnaugh mai mari. n

aceast seciune vom concepe cteva exemple imaginare, lsnd aplicaiile practice pentru capitolul de logic

combinaional. Aceste exemple sunt concepute doar pentru a ilustra tehnicile de simplificare.

Vom folosi harta Karnaugh dezvoltat anterior, mai exact forma din dreapta:

Fig. 8-32 hri Karnaugh; variante

8.6.1 Codul Gray

Observai secvena numerelor din partea superioar a hrii. Aceasta nu este o secvena binar (00, 01, 10,

11), ci este o secven de tipul 00, 01, 11, 10. Aceast secven este cunoscut sub numele de cod Gray. Secvena

de tip cod Gray modific doar un singur bit pe msur ce trecem de la un numr la urmtorul numr din secven.

Acest lucru nu este valabil ntr-o secvena binar. Regiunile adiacente difer doar printr-un singur bit, sau variabil

boolean. Acest lucru este necesar dac dorim organizarea ieirilor unei funcii logice pentru observarea

elementelor lor comune.

Mai mult, antetul coloanelor i rndurilor trebuie s fie n ordinea codului Gray, altfel, harta nu se va

comporta precum o hart Karnaugh. Regiunile ce au n comun variabile booleene nu vor mai fi adiacente i nu vom

mai putea identifica caracteristicile specifice funciei pe cale vizual. Regiunile adiacente variaz cu un singur bit,

deoarece secvena de cod Gray variaz la rndul ei doar cu un singur bit.



154

8.6.2 Hri Karnaugh cu 3 variabile - exemple de simplificare

S folosim n continuare hrile Karnaugh cu 3 variabile pentru simplificarea unor expresii booleene. Vom

arta cum s trecem termenii produs ai ecuaiei nesimplificate n harta Karnaugh. Vom ilustra i modul de

identificare a grupurilor de regiuni adiacente ce duc la formarea sumei de produse simplificate a circuitului logic

(expresiei booleene).

Fig. 8-33 simplificarea expresiei booleene cu harta Karnaugh

Dndu-se expresia (A'B'C' + A'B'C), primul pas este introducerea valorilor de 1 pe harta Karnaugh

corespunztor poziiei fiecrui produs al sumei (A'B'C' este echivalent cu 000, iar A'B'C este echivalent cu 001).

Identificm apoi un grup de regiuni alturate ce conin valori de 1 (n cazul de fa, avem doar dou astfel de

regiuni). Scriem apoi produsul de termeni pentru acest grup, ceea ce reprezint rezultatul simplificat.


Grupnd cei patru termeni de 1 pe harta Karnaugh, rezultatul este asigurat de expresia A'.



155


Identic, grupnd cei patru termeni de 1, putem foarte uor observa c singura variabil ce acoper toate cele

patru regiuni este C.


Din moment ce avem dou grupuri pe harta Karnaugh de mai sus, rezultatul va fi o sum de produse, i

anume, A' + B.


Cele dou produse de mai sus formeaz un grup de doi termeni ce se simplific la BC.



156


Variabila comun celor patru termeni grupai mai sus este B


Cei patru termeni de mai sus formeaz un singur grup. Putem vizualiza acest grup dac ndoim

extremitile hrii pentru a forma un cilindru. n acest caz, regiunile sunt adiacente. n mod normal, un astfel de

grup se noteaz conform figurii din stnga. Din ntregul set de variabile (A, B, C), singura variabil comun este C'.

C' este zero n toate cele patru regiuni. Acesta este atunci rezultatul final al simplificrii.




157

Cele ase regiuni rezultate din ecuaia nesimplificat pot fi organizate n dou grupuri de cte patru

elemente. Aceste grupuri trebuie s rezulte ntr-o sum de dou produse, i anume A' + C'.

8.6.3 Incinerator deeuri toxice - reconsiderare

S relum mai jos exemplul incineratorului de deeuri toxice studiat ntr-un capitol precedent. Vom ncerca

simplificarea circuitului logic folosind o hart Karnaugh:

Fig. 8-41 incinerator deeuri toxice - simplificarea circuitului logic folosind hri Karnaugh

Ecuaia boolean de ieire este o sum de patru produse. Prin urmare, vom avea patru regiuni de 1 pe harta

Karnaugh. Grupnd regiunile adiacente, avem trei grupuri de cte doi termeni. Vom avea prin urmare o sum de

trei produse, fiecare produs coninnd doi termeni. Circuitul logic simplificat, identic cu cel obinut cu ajutorul

regulilor de simplificare boolean, este redat mai jos:

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/transformarea-tabelelor-de-adevar


158

Fig. 8-42 incinerator deeuri toxice - circuitul logic simplificat

Fcnd o comparaie ntre regulile booleene folosite pentru simplificarea circuitului logic al

incineratorului...



159

Fig. 8-43 incinerator deeuri toxice - simplificarea boolean

...i harta Karnaugh, care duce la exact acelai rezultat...



160

Fig. 8-44 incinerator deeuri toxice - simplificarea circuitului logic folosind hri Karnaugh

Putem lesne vedea motivul pentru care hrile Karnaugh sunt preferate pentru simplificarea circuitelor

logice n detrimentul simplificrii booleene.

8.7 Hri Karnaugh cu patru variabile

Folosindu-ne de codul Gray, putem construi hri Karnaugh mai mari. O hart Karnaugh cu patru variabile

arat precum cea de mai jos:

Fig. 8-45 hart Karnaugh cu 4 variabile

Exemplele de mai jos ilustreaz simplificarea expresiilor booleene ce sunt prea greu de realizat prin

intermediul regulilor de simplificare boolean. Aceste expresii pot fi simplificate cu algebra boolean. Totui,

utilizarea hrilor Karnaugh este un procedeu mult mai rapid i mai uor, mai ales dac exist multe simplificri

logice de realizat.

8.7.1 Exemple de simplificare logic cu hri Karnaugh de patru variabile

8.7.1.1 Exemplul 1

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh/simplificarea-circuitelor-logice


161


Expresia boolean de mai sus conine 7 produse. Aceti termeni sunt grupai de sus n jos i de la stnga la

dreapta pe harta Karnaugh de mai sus. De exemplu, primul termen, A'B'CD, se regsete pe rndul 1, csua a 3-a,

i corespunde locaiei A = 0, B = 0, C = 1, D = 1. Ceilali termeni sunt poziionai ntr-o manier similar. Grupul

orizontal (albastru) corespunde termenului AB, iar grupul vertical (rou) corespunde expresiei booleene CD. Din

moment ce avem dou grupuri, rezultatul trebuie s fie o sum de dou produse, prin urmare, AB + CD.

8.7.1.2 Exemplul 2


n cazul de mai sus, mpturim cele patru coluri ale hrii Karnaugh, precum un erveel, pentru a

observa mai bine adiacena celor patru regiuni. B = 0 i D = 0 pentru toate regiunile. Celelalte variabile, A i B,

sunt 0 n unele cazuri i 1 n altele. Prin urmare, aceste variabile nu se vor regsi n rezultatul final al expresiei

simplificate.



162

8.7.1.3 Exemplul 3


Pentru o vizualizare mai bun, ne putem imagina c ndoim marginile de jos i de sus a hrii sub forma

unui cilindru. n acest caz, ambele grupuri sunt adiacente i formeaz practic un singur grup. Acest lucru ne spune

c rezultatul este un singur termen. Singura variabil comun a acestui grup de 8 variabile este B = 0. Rezultatul

simplificrii este prin urmare B'.

8.7.1.4 Exemplul 4




163

Expresia boolean de mai sus conine 9 termeni de produse, dintre care trei au doar trei variabile booleene

n loc de patru. Diferena const n faptul c, dei termenii ce conin patru variabile booleene acoper o singur

regiune, termenii cu trei variabile booleene acoper o pereche de regiuni fiecare.

Trecnd la simplificare, formm dou grupuri de cte opt termeni. Regiunile ce se regsesc n col sunt

comune ambelor grupuri. Acest lucru este corect. De fapt, aceast strategie conduce la o soluie mai bun dect

dac am fi format un grup de opt i un grup de patru regiuni, fr nicio regiune comun celor dou. Soluia final

este B' + D'.

8.7.1.5 Exemplul 5


n exemplul de mai sus, trei regiuni formeaz dou grupuri de cte dou. O a patra regiune nu poate fi

combinat cu nicio alt regiune, ceea ce se ntmpl frecvent n situaiile reale. n acest caz, termenul ABCD

rmne neschimbat n cadrul procesului de simplificare a expresiei booleene iniiale. Rezultatul este B'C'D' +

A'B'D' + ABCD.

8.7.1.6 Exemplul 6

Adeseori, exist mai mult de o singur soluie cu cost minim pentru expresia nesimplificat. Un astfel de

caz este cel de mai jos:



164


Ambele rezultate de mai sus conin patru termeni, cu trei variabile booleene fiecare. Ambele soluii sunt

valide din punct de vedere al minimizrii costurilor. Diferena dintre cele dou soluii finale const n modul de

grupare al regiunilor. Reamintim faptul c o soluie cu cost minim este acea soluie ce permite o implementare

fizic a circuitului logic cu un numr ct mai mic de pori logice i numr de intrri.

8.7.1.7 Exemplul 7




165

n urmtorul exemplu, cel de mai sus, dup ce trecem toate valorile de 1 pe hart Karnaugh, realizm

primul pas al simplificrii, i anume, gruparea primelor patru regiuni (stnga). n acest punct, s-ar putea s nu fie

foarte evident cum am putea grupa regiunile rmase.

La pasul al doilea (centru), grupm nc patru regiuni. Mai rmn n acest moment nc dou regiuni

negrupate. Soluia cu cost minim este s grupm aceste dou regiuni, ca i grupuri de patru, conform figurii din

dreapta.

Atenie, nu ncercai s realizai grupuri de cte trei. Gruprile trebuie s fie sub forma puterilor lui 2, i

anume, 1, 2, 4, 8, etc.

8.7.1.8 Exemplul 8


Avem din nou mai sus un exemplu ce suport dou soluii cu cost minim. Formm iniial cele dou grupuri

de cte patru regiuni (rou i albastru). Soluia final depinde de modul n care grupm regiunea rmas liber.

Dac o introducem n grupul din stnga (rou), soluia este ABC'. Dac o introducem n grupul din dreapta

(albastru), soluia este ABD. Indiferent de alegerea fcut, ambele soluii sunt corecte din punct de vedere al

minimizrii costurilor de implementare.

8.7.1.9 Exemplul 9



166


Mai sus este un exemplu de simplificare cu hri Karnaugh (stnga) precum i cu regulile algebrei booleene

(dreapta). C' (C = 0) reprezint aria format de cele opt regiuni din stnga. Regiunea rmas negrupat este

echivalent cu expresia ABCD. Grupnd aceast regiune cu cea din stnga ei, simplific termenul ABCD la ABD.

Rezultatul final este prin urmare C' + ABD.

Cazul de mai sus este un exemplu rar a unei probleme cu patru variabile ce poate fi redus destul de uor i

cu algebra boolean. Asta n cazul n care v amintii teoremele de simplificare boolean.

8.8 Mintermeni i maxtermeni

8.8.1 Soluia sub forma produsului de sume

Pn n acest moment am cutat soluii sub forma unei sume de produse la problemele de simplificare

boolean. Pentru fiecare dintre aceste soluii exist o alt soluie sub forma unui produs de sume. Acest tip de

soluie se poate dovedi a fi mai practic, n funcie de aplicaie. Dar, nainte de a scrie soluiile sub forma unui

produs de sume, trebuie s introducem cteva concepte noi. Procedura de mai jos pentru extragerea termenilor sub

form de produs nu este nou. Vrem doar s stabilim o procedur formal pentru mintermeni, ca mai apoi, s putem

face o comparaie cu noua procedur pentru maxtermeni.

8.8.2 Analiza regiunilor ce conin valori de 1 - mintermeni

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/reguli-de-simplificare


167

Un mintermen este o expresie boolean rezultnd ntr-o valoare de 1 pentru ieirea unei singure regiuni

dintr-o hart Karnaugh. Toate celelalte regiuni ale hrii Karnaugh sau ale tabelului de adevr fiind 0 n acest caz.

Dac un mintermen conine un singur 1, iar regiunile rmase sunt toate 0, aria minim pe care acest mintermen o

acoper este 1.

Figura de mai jos (stnga) prezint mintermenul ABC, un singur termen sub form de produs, ca i o

singur valoare de 1 pe o hart Karnaugh unde toate celelalte regiuni sunt 0. Pn n acest moment, nu am prezentat

valorile de 0 pe hrile Karnaugh considerate. Acestea se omit de obicei, excepie fcnd cazurile speciale. Un alt

mintermen, A'BC' este cel din dreapta. Ceea ce vrem s subliniem este faptul c adresa regiunii corespunde direct

cu mintermenul extras de pe hart. Regiunea 111 corespunde mintermenului ABC din stnga. Regiunea 010

corespunde la rndul ei mintermenului A'BC'. O expresie boolean sau o hart poate avea mai muli mintermeni.

Referindu-ne la figura de mai sus, putem scrie procedura introducerii unui mintermen pe o hart Karnaugh:

Identificm mintermenul (produsul) ce vrem s-l introducem pe hart

Scriem valoarea numeric corespunztoare

Ne folosim de valoarea binar ca i adres pe hart

Introducem un 1 la adresa respectiv

Repetm paii de mai sus pentru un nou mintermen (termenii produs dintr-o sum de produse)

O expresie boolean este format de cele mai multe ori din mai muli mintermeni, corespunznd mai multor

regiuni pe o hart Karnaugh, precum n exemplul de mai jos:

Fig. 8-55 hart Karnaugh; mintermeni

Mintermenii multiplii de pe aceast hart sunt mintermenii individuali ce i-am analizat mai sus. Ceea ce

vrem s reamintim este faptul c valorile de 1 sunt traduse de pe harta Karnaugh ca i o adres binar

transformat direct ntr-unul sau mai muli termeni sub form de produs. Prin direct, ne referim la faptul c 0

corespunde unei variabile negate, iar 1 corespunde unei variabile pure. De exemplu, 010 se transform direct n



168

A'BC'. n acest exemplu nu a existat nicio simplificare. Totui, avem ca i rezultat o sum de produse prin

intermediul mintermenilor.

Referindu-ne la figura de mai sus, putem rezuma pe scurt procedura de urmat n cazul simplificrii

expresiei booleene sub forma unei sume de produse dintr-o hart Karnaugh:

Formm grupuri de 1 ct mai mari posibile, acoperind toi mintermenii de pe hart. Grupurile trebuie s

conin un numr de regiuni sub forma puterii lui 2 (1, 2, 4, 8, etc.)

Scriem valori numerice binare pentru fiecare grup

Transformm valoarea binar sub forma unui produs

Repetm paii de mai sus pentru toate grupurile formate. Din fiecare grup va rezulta un termen sub form

de produs

Expresia simplificat reprezint suma acestor termeni sub form de produs

Nimic nou pn n acest moment. Am scris doar paii de urmat n cazul mintermenilor. Acelai lucru l

vom face i n cazul maxtermenilor.

8.8.3 Analiza regiunilor ce conin valori de 0 - maxtermeni

S considerm acum o funcie boolean ce este 0 pentru o singur regiune i 1 n rest:

Fig. 8-56 hart Karnaugh; maxtermeni

Un maxtermen este o expresie boolean a crei valoare este 0 pentru o singur regiune, toate celelalte

regiunii ale hrii Karnaugh sau ale tabelului de adevr fiind 0. Vedei i explicaia de la mintermen. Figura de sus

stnga prezint un maxtermen (A + B + C), o sum de trei termeni simplii. Pe hart, aceast sum este reprezentat

printr-un singur 0, toate celelalte regiunii ale hrii fiind 1. Dac un maxtermen are un singur 0, iar celelalte regiuni

sunt 1, aria maxim pe care o acoper este 1.



169

Exist cteva diferene acum c am introdus i maxtermenii. Maxtermenul este un 0, nu un 1 pe harta

Karnaugh. Un maxtermen este un termen sub form de sum, A + B + C n cazul nostru, i nu un termen sub form

de produs (ABC, de exemplu).

Pare ciudat c locaia expresiei (termenului) (A + B + C) pe hart este 000. Pentru ecuaia ieire = (A + B

+ C) = 0, toate cele trei variabile (A, B, C) trebuie s fie egale cu 0. Doar expresia (0 + 0 + 0) = 0 va fi egal cu 0.

Prin urmare, trecem singurul nostru maxtermen (A + B + C) n regiunea ce se afl la adresa A,B,C = 000 pe harta

Karnaugh, unde toate intrrile sunt egale cu 0. Aceasta este singura posibilitate pentru a obine valoarea de 0 pentru

maxtermen. Toate celelalte regiuni conin valori de 1 pentru c orice alte valori de intrare diferite de (0, 0, 0) pentru

expresia (A + B + C) au ca i rezultat 1.

Lund n considerare figura de mai sus, paii care trebuiesc urmai pentru introducerea unui maxtermen pe

harta Karnaugh, sunt urmtorii:

Identificm termenul sub form de sum (maxtermenul) ce-l vom introduce pe hart

Scriem valoarea numeric binar corespunztoare

Formm complementul

Utilizm complementul ca i adres pentru introducerea valorii de 0 pe harta Karnaugh

Repetm paii de mai sus pentru toi ceilali maxtermeni (termeni-sum dintr-o expresie sub forma de

produs de sume)

Un alt maxtermen este prezentat n figura de mai jos. Valoarea numeric 000 corespunde termenului A' +

B' + C'. Complementul este 111. Introducem o valoare de 0 pentru maxtermenul (A' + B' + C') la aceast adres (1,

1, 1) a hrii Karnaugh de mai jos:


8.8.4 Scrierea expresiei booleene simplificate ca i produs de sume



170

O expresie boolean sub form produsului de sume poate avea mai muli maxtermeni, conform figurii de

mai jos:


Maxtermenul (A + B + C) sub form numeric este 111, iar complementat este 000. Plasm prin urmare un

0 la adresa (0, 0, 0). Maxtermenul (A + B + C') sub form numeric este 110, iar complementat este 001. Plasm

prin urmare un zero la adresa (0, 0, 1).

Acum c am construit harta Karnaugh, suntem interesai de modul n care putem scrie o form simplificat

a expresiei booleene iniiale sub form de produs de sume. Primul pas este gruparea termenilor de 0, precum grupul

de mai jos:




171

Scriem apoi valoarea binar corespunztoare termenului-sum, ce arat astfel: (0, 0, X). Pentru grupul

format, att A ct i B sunt 0. Dar C este att 0 ct i 1. Prin urmare, scriem un X n locul valorii lui C. Formm

complementul: (1, 1, X). Scriem termenul sum (A + B) ignornd C-ul i X-ul ce l-a nlocuit.

S relum paii necesari pentru reducerea unei expresii booleene la un produs de sume:

Formm grupuri de 0 ct mai mari posibile, incluznd toi maxtermenii. Numrul termenilor trebuie s fie

puteri ale lui 2

Scriem valoarea numeric a grupului

Complementm aceast valoare numeric a grupului

Transformm valoarea complementat ntr-un termen sub form de sum

Repetm paii de mai sus pentru toate grupurile rmase pe hart. Rezultatul fiecrui grup este un termen

sub form de sum, iar rezultatul final este produsul acestor termeni-sum

8.8.4.1 Exemplul 1

Simplificai expresia boolean sub forma produsului de sume de mai jos. Scriei rezultatul final sub forma

unui produs de sume:

Soluie: completm o hart Karnaugh cu cei apte maxtermeni de mai sus (introducem valori de 0). Reinei

s complementai variabilele de intrare pentru gsirea adresei corespunztoare:

Fig. 8-60 simplificarea expresiei booleene folosind harta Karnaugh



172

Dup ce am introdus toi maxtermenii n tabel, trecem la gruparea regiunilor, precum n figura de mai jos.

Grupurile mai mari se traduc printr-un termen-sum cu mai puine intrri. Cu ct avem mai puine grupuri, cu att

vom avea mai puin termeni-sum n expresia final:

Fig. 8-61 harta Karnaugh; gruparea regiunilor

Avem trei grupuri, prin urmare, trebuie s avem trei termeni-sum n rezultatul final. Detaliile simplificrii

sunt prezentate n figura de mai sus. Pentru oricare grup, scriem mai nti adresa de intrare, o complementm i o

transformm ntr-un termen boolean sub form de sum. Rezultatul final este produsul acestor trei termeni-sum.

8.8.4.2 Exemplul 2

Simplificai expresia boolean sub form de produs de sume de mai jos, exprimnd rezultatul sub forma

unei sume de produse:

Aceast problem este identic cu cea anterioar, cu diferena c expresia simplificat se cere sub form de

sum de produse i nu sub form de produs de sume.

Trecem maxtermenii (0) din expresia iniial pe harta Karnaugh de mai jos (stnga), exact ca n exemplul

precedent:



173

Fig. 8-62 simplificarea expresiei booleene folosind harta Karnaugh

Completm apoi toate celelalte regiuni rmase libere cu valori de 1 (dreapta sus).

Formm grupuri de 1 pentru toate regiunile ce conin valori de 1. Scriem apoi rezultatul simplificat sub

forma sumei de produse, conform seciunii precedente a acestui capitol. Acest lucru este identic problemei

precedente:

Fig. 8-63 harta Karnaugh; gruparea regiunilor

8.9 Exemplu de implementare practic a circuitelor logice

8.9.1 Comparaie ntre soluiile cu mintermeni i maxtermeni

n figura de mai jos sunt ambele soluii ale exemplelor din seciunea precedent, pentru comparaie:

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh/mintermeni-si-maxtermeni


174

Fig. 8-64 hri Karnaugh; comparaie ntre soluiile obinute cu mintermeni respectiv maxtermeni

Care soluie este mai simpl? Dac ar fi s implementm fizic rezultatul sub form de produs de sume, am

avea nevoie de trei pori logice SAU i o poart logic I. Invers, dac ar fi s implementm rezultatul sub form de

sum de produse, am avea nevoie de trei pori I i o poart SAU. n ambele situaii am avea nevoie de patru pori.

S lum n considerare atunci i numrul de intrri ale porilor. Prima variant utilizeaz 8 intrri, iar a doua 7

intrri. Din definiia costului minim, soluia sub forma sumei de produse este mai simpl. Acesta este un exemplu

tehnic corect, dar care nu ne este de prea mare folos n realitate.

Soluia corect depinde de complexitate i de familia de pori logice folosite. Soluia sumei de produse

este mai bun fac folosim circuite TTL, a cror pori principale sunt porile I-negat. Acestea sunt foarte bune

pentru implementri sub forma de sum de produse. Pe de alt parte, soluia produsului de sume este acceptabil

dac folosim circuite CMOS, deoarece avem astfel la dispoziie pori SAU-negat de toate mrimile.

8.9.2 Echivalena circuitelor I-SAU cu circuitele I-negat-I-negat

Circuitele cu pori logice pentru ambele cazuri sunt prezentate mai jos, produsul de sume n stnga i suma

de produse n dreapta:



175

Fig. 8-65 echivalena circuitelor I-SAU cu circuitele I-negat-I-negat

Relum mai jos (stnga) circuitul sub forma sumei de produse:


Dac nlocuim toate porile logice I din stnga cu pori logice I-negat, obinem rezultatul din dreapta sus.

Poarta SAU de la intrare este nlocuit de asemenea cu o poart I-negat. Pentru a demonstra c logica I-SAU este

echivalent cu logica I-negat-I-negat, este suficient s mutm cerculeele inversoare de la ieirea celor trei

pori I-negat la intrarea porii finale I-negat, conform figurii de mai jos:



176


n figura de mai sus (dreapta), putem observa c ieirea unei pori I-negat cu intrri inversate este

echivalent din punct de vedere logic cu o poart SAU, conform teoremei lui DeMorgan i a negaiei duble.

Aceast informaie ne este de ajutor n implementarea fizic a circuitelor digitale atunci cnd dispunem de circuite

logice TTL cu pori I-negat.

Paii necesari construirii logicii I-negat-I-negat n locul logicii I-SAU, sunt urmtorii:

Realizm un circuit logic (teoretic) sub form de sum de produse

Cnd desenm diagrama logic, nlocuim toate porile logice (I i SAU) cu pori logice I-negat

Intrrile nefolosite trebuie legate la valoarea logic nalt

n caz de defect, nodurile interne de la primul nivel de ieire al porilor I-negat nu sunt identice cu valorile

diagramei I-SAU, ci sunt inversate. Folosim diagrama logic I-negat-I-negat. Totui, intrrile i ieirile

finale sunt identice

Notm fiecare capsul (circuit integrat) cu U1, U2 Folosim catalogul productorului pentru conectarea corect a pinilor circuitului integrat la intrrile i

ieirile porilor din circuit

, etc.

8.9.3 Exemplu

S relum o problem precedent ce implic o simplificare sub forma sumei de produse. Vom realiza o

simplificare sub forma unui produs de sume de aceast dat. Putem compara cele dou soluii la final.

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/algebra-booleana/teoremele-lui-demorganhttp://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh/harti-karnaugh-cu-patru-variabile/#exemplul-7


177

Fig. 8-68 simplificarea unui produs de sume

Soluie: n figura de sus stnga avem problema iniial, o expresie boolean cu 9 mintermeni nesimplificat.

Recapitulnd, am format patru grupuri de cte patru regiuni fiecare. Rezultatul a fost o sum de patru produse

(partea din stnga, jos).

n figura din mijloc, completm regiunile rmase libere cu valori de 0. Formm dou grupuri de cte patru

regiuni. Grupul de jos (albastru) este A' + B, iar grupul din dreapta (rou) este C' + D. Rezultatul este prin urmare

un produs de dou sume, (A' + B)(C' + D).

Comparnd cele dou soluii de mai sus, putem observa c soluia produsului de sume reprezint soluia cu

cel mai mic cost. Pentru implementarea primei soluii am avea nevoie de 5 porii, iar pentru soluia produsului de

sume am avea nevoie doar de 3. Folosind circuite logice TTL, aceasta din urm este i atractiv datorit simplitii

rezultatului. Putem gsim pori logice I i SAU cu 2 intrri. Mai jos sunt prezentate circuitele logice pentru ambele

soluii:



178

Fig. 8-69 soluia sub forma circuitelor logice

S presupunem c avem la dispoziie circuitele logice TTL de mai jos. n acest caz, cunoatem i

poziionarea porilor logice n interiorul acestora, precum n figura de mai jos:

Fig. 8-70 circuite TTL



179

Circuitele integrate folosite (trei la numr) vor fi identificate prin notaia U1, U2 respectiv U3. Pentru a

face distincie ntre porile individuale din fiecare capsul, acestea vor fi identificate prin a, b, c, d, etc. Circuitul

inversor 7404 va fi U1

Fig. 8-71 numerotarea porilor

Putem gsi cu uurin pori logice I cu dou intrri (7408, stnga). Totui, este mai greu s gsim o

poart logic SAU cu patru intrri. Singurul tip de poart cu patru intrri este un circuit TTL 7420 cu pori I-negat

(dreapta):

. Porile inversoare individuale sunt U1-a, U1-b, U1-c, etc. Circuitul SAU 7432 va fi notat cu

U2, iar U3 este notaia folosit pentru circuitul I 7408.

Lund n considerare piningul circuitelor logice folosite mai sus, vom desemna toate intrrile i ieirile

circuitului logic ce vrem s-l construim, conform figurii de mai jos (intrrile porilor nefolosite se vor lega la mas):

Fig. 8-72 circuite TTL

Putem transforma poarta logic I-negat cu patru intrri ntr-o poart logic SAU cu patru intrri prin

inversarea intrrilor acesteia:



180

Fig. 8-73 transformarea porii I-negat n poart logic SAU

Putem prin urmare folosi circuitul 7420 cu pori logice I-negat cu patru intrri ca i poart SAU prin

negarea (inversarea) intrrilor.

Nu vom folosi pori logice inversoare discrete pentru inversarea intrrilor circuitului 7420. Vom folosi n

schimb pori logice I-negat cu dou intrri n locul porilor I din soluia boolean cu mintermeni (sum de

produse). Inversarea ieirii porilor I-negat cu dou intrri este suficient pentru inversarea necesar realizrii

porii logice SAU cu patru intrri:

Fig. 8-74 soluia expresiei folosind circuite TTL

Rezultatul de mai sus este singura modalitate practic de realizarea a circuitului folosind TTL cu pori

logice I-negat-I-negat n locul porilor I-SAU.



181

8.10 Notaia (sum) i notaia (produs)

Ca i referin, aceast seciune introduce terminologia folosit n unele texte pentru descrierea

mintermenilor i maxtermenilor aparinnd hrilor Karnaugh. Mai departe de att, aceast seciune nu conine

nimic nou.

8.10.1 Notaia (sum) pentru mintermeni

Simbolul (sigma) indic o sum iar litera m indic mintermenii. Prin urmare, m reprezint o sum de

mintermeni. Urmtorul exemplu ilustreaz afirmaia de mai sus. n loc de ecuaia boolean, am ales s enumerm

mintermenii:

sau

Indicii termenilor indic locaia regiunii, sau adresa, dintr-o hart Karnaugh. Acesta este cu sigurana un

mod mult mai compact pentru descrierea mintermenilor sau regiunilor unei hri Karnaugh.



182

Fig. 8-75 notaia sum pentru mintermeni

Soluia exprimat sub forma sumei de produse nu este afectat prin utilizarea acestei terminologii.

Mintermenii de pe hart (valorile de 1) sunt grupai ca de obicei, iar mai apoi putem scrie o soluie sub forma sumei

de produse.

8.10.2 Notaia (produs) pentru maxtermeni

Mai jos lum n considerare i terminologia folosit pentru descrierea unei liste de maxtermeni. Produsul

este indicat prin litera (pi), iar M indic maxtermenii. Pr in urmare, P indic un produs de maxtermeni. Putem

folosi acelai exemplu pentru ilustrarea celor spuse mai sus. Ecuaia logic boolean nesimplificat este nlocuit cu

o list de maxtermeni:

sau



183

Din nou, numerele indic adresa sau locaia pe harta Karnaugh. Pentru maxtermeni, acestea reprezint

locaiile valorilor de 0. Soluia sub forma produsului de sume se scrie ca de obicei.

Fig. 8-76 notaia produs pentru maxtermeni

8.11 Hri Karnaugh de 5 i 6 variabile

Pentru reducerea circuitelor logice mai mari se folosesc, evident, hri Karnaugh mai mari. Dar care este

mrimea maxim (practic) a unei hri Karnaugh? Acest lucru depinde de numrul de intrri a circuitului logic

considerat. Practic, se poate constata c aceast limit este de 6 intrri. Prezentm mai jos aadar hrile Karnaugh

de 5 i 6 variabile.

8.11.1 Harta Karnaugh de 5 variabile

Prima variant a hrii Karnaugh de 5 variabile este modelul n oglind. Desigur, numerotarea se realizeaz

n cod Gray (partea de sus). Acesta se reflect la mijlocul hrii. Acest stil este folosit de textele mai vechi:

http://www.circuiteelectrice.ro/http://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh/simplificarea-circuitelor-logice


184

Fig. 8-77 hart Karnaugh de 5 variabile

Varianta preferat, cea cu suprapunere, este prezentat mai jos:

Fig. 8-78 hart Karnaugh de 5 variabile; varianta utilizat

Aceast variant const pur i simplu din dou (patru pentru o hart Karnaugh de 6 variabile) hri identice,

cu excepia bitului cel mai semnificativ din adresa de 3 bii din partea superioar. Dac ne uitm n partea de sus a

hrii, observm c numerotaia este diferit fa de harta precedent (n cod Gray). Dac ignorm bitul cel mai

semnificativ, precum am spus mai sus, secvena 00, 01, 11, 10 se regsete n partea superioar a ambelor sub-hri.

Secvena format din cele opt numere de 3 bii nu este cod Gray.

8.11.1.1 Harta Karnaugh cu 5 variabile - exemplu

S proiectm un circuit cu 5 intrri binare (A, B, C, D, E), A fiind bit-ul cel mai semnificativ. Circuitul va

trebui s produc o ieire nalt pentru orice numr prim detectat la intrare:

Prezentm mai jos o soluie sub forma hrii Karnaugh de 5 variabile n oglind, folosind cod Gray:



185

Fig. 8-79 hart Karnaugh de 5 variabile; exemplu

Numerele prime sunt (1,2,3,5,7,11,13,17,19,23,29,31). Introducem o valoare de 1 n fiecare regiune

corespunztoare. Trecem apoi la gruparea regiunilor i scrierea rezultatului simplificat. Observai c grupul de patru

regiuni A'B'E conine dou perechi de cte dou regiuni aflate de fiecare parte a liniei de reflexie. Acelai lucru este

valabil i pentru grupul format din dou regiuni AB'DE. Aceste grupuri se formeaz prin reflexie. Atunci cnd

folosim acest stil de hart Karnaugh, va trebui s cutm astfel de grupuri reflectate. Expresia boolean simplificat

mai sus este urmtoarea:

S considerm i varianta hrii Karnaugh cu 5 variabile, cu suprapunere:



186


Dac facem o comparaie ntre cele dou variante de sus, anumite regiuni din partea dreapt a hrii i

modific locaia, din moment ce adresele din partea de sus a hrii s-au modificat. Trebuie de asemenea s gsim o

alt modalitate de grupare a termenilor din cele dou jumtii ale hrii. Soluia const n suprapunerea (imaginar)

a celor dou jumti. Orice suprapunere a hrii de deasupra cu harta de dedesubt prezint o posibil grupare.

Figura de mai jos indic faptul c grupul AB'DE este compus din dou regiuni suprapuse. Grupul A'B'E este format

din dou perechi de regiuni suprapuse:



187


Pentru grupul A'B'E de patru regiuni, ABCDE = 00xx1. Cu alte cuvinte, variabilele A, B i E sunt aceleai

(001) pentru grup. Pe de alt parte, CD = xx (aceste variabile nu sunt identice pentru grup). Din moment ce

ABCDE = 00xx1, grupul de patru regiuni este acoperit de A'B'XXE = A'B'E.

8.11.2 Hart Karnaugh de 6 variabile

Lum acum un exemplu de utilizare a unei hri Karnaugh de 6 variabile. Am suprapus (imaginar) cele

patru sub-hri pentru a putea vizualiza gruparea de patru regiuni corespunztoare ieirii C'F':



188

Fig. 8-82 hart Karnaugh de 6 variabile

Un comparator de amplitudine (utilizat pentru ilustrarea utilizrii hrii Karnaugh de 6 variabile) compar

dou numere binare. Acesta indic dac cele dou numere sunt egale, mai mici sau mai mari unul fa de cellalt.

Un astfel de comparator are trei ieiri:

Fig. 8-83 comparator de amplitudine

Un comparator de amplitudine pe trei bii are dou intrri: A2A1A0 i B2B1B0

Pentru simplificarea logicii comparatorului de amplitudine pe 3 bii, folosim harta Karnaugh cu 6 variabile

de mai jos. Aceast variant este cea cu suprapunere. Codul binar folosit nu este cod Gray. Gsim expresiile

redundante prin suprapunerea celor patru sub-hri, precum am artat mai sus. Am putea gsi regiuni comune

. Un comparator de

amplitudine sub forma unui circuit integrat (7485) are practic patru intrri. Totui, harta Karnaugh de mai jos

trebuie meninut la o mrime rezonabil. Vom rezolva problema doar pentru ieirea A>B.



189

tuturor celor patru hri, dei, n exemplul de mai jos nu este cazul. Putem observa totui c exist regiuni comune

sub-hrilor:


Ieirea A>B este reprezentat de ABC>XYZ pe harta de mai sus. Ori de cte ori ABC este mai mare dect

XYZ, avem o valoare de 1 pe hart. Pe prima linie, ABC = 000 nu poate fi mai mare dect nicio valoare a lui XYZ.

Nu avem nici o valoare de 1 pe aceast linie. Pe linia a doua, ABC = 001, i doar n prima regiune, ABCXYZ =

001000, ABC este mai mare dect XYZ. Avem un un singur 1 n prima regiune a celei de a doua linii. Pe linia a

treia, ABC = 011 i avem trei valori de 1. Pe linia a patra, ABC = 010, exist o pereche de 1. Prin urmare, harta este

completat cu valori de unu ori de cte ori ABC este mai mare dect XYZ.

Pentru gruparea regiunilor, acolo unde este posibil, ncercm s formm grupuri cu sub-hrile adiacente.

Toate grupurile n afar de un grup de 16 regiuni sunt formate din regiuni aparinnd sub-hrilor adiacente.

Rezultatul este: 1 grup de 16 regiuni; 2 grupuri de 8 regiuni; 4 grupuri de 4 regiuni. Grupul de 16 regiuni, AX',

ocup toat sub-harta din partea de jos-stnga a hrii Karnaugh, dei, n figura de mai sus, aceasta nu este

ncercuit.



190

Numrnd valorile de 1 de pe hart, ajungem la un total de 16 + 6 + 6 = 28. nainte de reducerea logic

folosind harta Karnaugh de mai sus, soluia logic sub form de sum de produse ar fi avut 28 de termeni, fiecare

cu 6 intrri. Simplificarea logic cu ajutorul hrii Karnaugh de mai sus, a redus numrul termenilor la apte, fiecare

cu un numr de patru sau mai puin de patru intrri. Acesta este de fapt scopul hrilor Karnaugh!


4.8-Harti-Karnaugh.pdf

Documents

Transcript of 4.8-Harti-Karnaugh.pdf