Minimizarea functiilor booleene cu ajutorul diagramelor veitch-karnaugh

MINIMIZAREA FUNCTIILOR BOOLEENE CU AJUTORUL DIAGRAMELOR VEITCH-KARNAUGH

1 DIAGRAME VEITCH-KARNAUGH

Diagrama Veitch-Karnaugh este o expresie a conceptelor de tabel de adevar,diagrame Venn si mintermeni.Transformarea unei diagrame Venn intr-o diagrama Karnaugh se face urmand pasii aratati in figura de mai jos.

*Transformarea diagramelor Venn in diagrame Veitch-Karnaugh

Astfel diagrama Venn in figura a),in care cele doua variabile le corespund multimile A si B,este reprezentata in alta forma in figura b),in care se pun in evidenta multimile disjuncte AB,B,A,.Cum acestea au chiar expresia mintermenilor,diagrama poate fi redesenata ca in figura c (se considera ca A este variabila mai semnificativa).Alocand fiecarui mintermen aceeasi suprafata pe care o reprezentam la fel,diagrama ia forma din figura d).Pastrand numai indicii mintemenilor ,diagrama va arata ca in figura e),diagrama Veitch,sau ca in figura f),diagrama Karnaugh.Se poate spune ca diagrama Veitch-Karnaugh (V-K) este o forma particulara a tabelului de adevar.Daca in tabel de adevar fiecarui

mintermen ii corespunde o lini,asa cum se poate vedea in tabelele de mai sus,in diagrama V-K ii corespunde o celula(un patrat).

Observatie: Tabelele a,b,c au configuratia asemanatoare cu a diagramelor V-K dar,in cazul lor,mintermenii invecinati nu sunt adiacenti.

In cazul tabelului de mai jos a) este reprezentata o diagrama Veitch de 3 variabile.Diagrama Veitch de 4 variabile se obtine prin extensia diagramei Veitch de 3 variabile asa cum se poate observa in figura b).Cea mai semnificativa variabila este A iar cea mai putin semnificativa este C in cazul diagramei din figura a) respectiv D pentru diagrama din figura b).

*Diagrame Veitch de: a variabile

b)4 variabile

Formele canonice ale functiilor pot fi usor transpuse in diagrame V-K si invers.Pentru aceasta se asociaza functiei 1 logic pentru fiecare mintermen care apare in expresia in forma disjunctive (suma de produse) si 0 logic pentru fiecare mintermen care apare in expresia in forma conjunctiva (produs de sume) a functiei.

Exemplu:Sa se completeze diagrama Veitch pentru functia data prin expresia f(A,B,C)= =m+m+m==M+M+M+M+M

De regula,cand functia este reprezentata in forma canonica disjunctive,se omit maxtermenii deci implicit nu se marcheaza 0 in diagrama,iar atunci and functia este reprezentata in forma canonica conjunctiva se omit mintermenii,deci nu se incarca in diagrama decat 0.

a) b)

c)

*Transpunerea formelor canonice ale funciilor in diagrame Veitch.

Diagrama Veitch poate fi utilizata pentru realizarea listei mintermenilor sau maxtermenilor din formele normale disjunctive respective conjunctive ale functiei.

Exemplu:Sa se determine lista mintermenilor si maxtermenilor pentru functia logica: f(A,B,C)=AB+B.

Dupa cum se observa in figura a) de mai sus,termenul AB corespunde zonei din diagrama Veitch in care A=1 si B=1,adica celulele corespunzatoare mintermenilor 6 si 7,iar termenul B corespunde zonei din diagrama Veitch in care B=1 si C=0,adica celulele corespunzatoare mintermenilor 2 si 6.Pentru acesti mintermeni functia ia valoarea 1 deci in diagrama Veitch va apare valoarea 1 in celulele corespunzatoare,iar in celelalte celule va apare 0.Functia poate fi exprimata acum in forma canonica disjunctive si respectiv conjunctiva.

f(A,B,C)==

2 DIAGRAME VEITCH DE REFERINTA (STANDARD)

Pozitionarea variabilelor pe o diagrama Veitch se poate face in moduri diferite functie de dorinta utilizatorului.

In sectiunea de mai sus s-a utilizat o diagrama de referinta (cu A variabila cea mai semnifivativa) care are avantajul simplitatii,succesiunea mintermenilor (pe verticala) fiind usor de urmarit.

In figura de mai jos este reprezentata o alta diagrama V recomandata,in care variabila D este cea mai semnificativa si succesiunea mintermenilor se face pe orizontala.Expresia formala a functiei va fi deci f(D,C,B,A).

Putem consider o alta dispunere a variabilelor,ca in exemplele din figura de mai sus,pozitia valorilor associate modificandu-se in aceste cazuri:

   

* Variante de diagrame Veitch

Observatie: Acoladele corespunzatoare variabilelor s-au inlocuit cu bare care sunt mai usor de reprezentat.

3 REGULI DE MINIMIZARE A FUNCTIILOR BOOLEENE CU AJUTORUL DIGRAMELOR VEITCH-KARNAUGH

Simplificarea in cadrul diagramelor V-K se bazeaza pe faptul ca adiacenta logica corespunde adiacentei fizice.Doi mintermeni sunt adiacenti logic daca difera doar printr-o variabila.De exemplu AB si ABC sunt adiacenti,ei diferind doar prin variabila D.Conform teoremelor algebrei booleene AB si ABD=AB.In general,orice combinatie a doi termini adiacenti duce la eliminarea unei variabile.Diagrama V-K este construita astfel incat celulele invecinate (adiacente fizic) sa corespunda mintermenilor adiacenti logic.Gruparea a doi sau mai multi termini adiacenti se face intuitive prin incercuirea si duce in final la eliminarea uneia sau mai multor variabile.

Reguli de simplificare:

Fiecare patrat / celula (ce corespunde unui mintermen) a unei diagrame V-K de 2 variabile are 2 celule adiacente; fiecare celula a unei diagrame V-K de 3 variabile are 2 celule adiacente si asa mai departe.In general fiecare celula a unei diagrame V-K de n variabile are n cellule adiacente.

Gruparile de termini (celule) pot cuprinde un numar de celule,puterea a lui 2 (1,2,4,8,etc).Gruparea de 2 celule elimina o variabila,gruparea de 4 celule elimina 2 variabile s.a.m.d,in general gruparea a 2 celule elimina n variabile.

Se grupeaza impreuna un numar cat mai mare de celule eliminand in acest fel ca mai multe variabile din termenii expresiei functiei minimizate(fiecare grupare corespunzatoare unui termen al expresiei).

Se acopera (grupeaza) toate celulele ce contin 1,in cat mai putine grupari (grupari putine inseamna putini termini in forma normala a functiei minimizate).O celula este acoperita daca este inclusa in cel putin o grupare.O celula poate fi utilizata pentru a realiza mai multe grupari,daca este nevoie.

Gruparile din diagrama incep cu acele celule "singuratice" care au cele ,ai putine adiacente (celule adiacente ce contin 1).Mintermenii cu multe adiacente,au mau multe posibilitati grupare si vor fi lasati pentru a fi grupati mai tarziu.Multimea tuturor gruparilor obtinute se numeste acoperire (a diagramei).

Acoperirea este transpusa apoi in expresie tinand cont de urmatoarele reguli:

Factorii care compun termenii sunt variabilele simple sau negate ale functiei care isi pastreaza valoarea 1 sau 0,in cadrul gruparii;daca isi pastreaza valoarea 1 variabila apare simpla in cadrul termenului iar daca isi pastreaza valoarea 0 apare negate.Cu cat mai multe variabile isi pastreaza valoarea cu atat termenul va contine mai multi factori.La limita gruparii cu o singura celula ii corespunde un mintermen.

Daca gruparea cuprinde toti mintermenii din diagrama,functia este egala cu 1.

DIAGRAME VEITCH PENTRU FUNCTII DE 5 SI 6 VARIABILE

Diagrama Veitch pentru functii de 5 variabile contine 32 de celule si este practice formata din 2 diagrame de 4 variabile cu cate 16 celule.Variabila nou introdusa este E si o consideram cea mai semnificativa.

Diagrama poate fi reprezentata si spatial.Daca suprapunem (prin rabatare) cele doua diagrame de 4 variabile se pune in evidenta faptul ca celulele astfel suprapuse sunt adiacente.Astfel,celula 2 (corespunzatoare mintermenului 2) are 5 celule adiacente: 0,3,6,10 si 18.De asemenea celula 7 are 5 celule adiacente: 3,5,6,15 si 23,s.a.m.d.

* Diagrama Veitch de 5 variabile: a)reprezentarea standard

b)reprezentarea spatiala

Diagrama Veitch pentru functii de 6 variabile contine 64 de celule si este formata din 4 diagrame de 4 variabile cu cate 16 celule.Variabilele nou introduce sunt E si F,pe cea din urma considerand-o cea mai semnificativa.Ca si in cazul diagramei Veitch de 5 variabile,diagrama de 6 variabile poate fi reprezentata si spatial.

* Diagrama Veitch de 6 variabile: a) reprezentarea standard

b) reprezentarea spatiala

Prin suprapunerea (prin pliere) celor 4 diagrame partiale,doua cate doua,se evidentiaza celulele adiacente.De exemplu celula 15 este adiacenta cu celulele 7,11,13,14,31,47 si 63.

Exemplu: Sa se minimizeze functia f(A,B,C,D,E,F),o data prin diagrama Veitch din figura de mai jos.

Acoperirea diagramei cuprinde urmatoarele grupari:

Functia va fi:

f(A,B,C,D,E,F)= + + DE + E + BD

Observatie: Diagrame pentru mai mult de 6 variabile nu se utilizeaza ele nefiind practice datorita complexitatii.

5. MINIMIZAREA FUNCTIILOR BOOLEENE INCOMPLET DEFINITE,CU AJUTORUL DIAGRAMELOR VEITCH

O functie booleana incomplete definite este o functie care pentru cel putin un mintermen (deci pentru cel putin o combinatie a variabilelor de intrare) nu are o valoare certa.Valoarea functiei se considera a fi 0 sau 1 functie de necesitati.In tebele si diagrame valoarea nedefinita (incerta) este notata,de regula,cu X.

In diagramele Veitch,celulele cu X pot fi grupate daca ajuta la formarea unor grupari maiximale,dar nu trebuie urmarita gruparea lor ci doar a celulelor ce contin 1,in cazul formelor disjunctive,sau ce contin 0 in cazul formelor conjunctive.

Exemplu: Sa se minimizeze functia f(A,B,C) incomplet definita data prin diagrama Veitch in figura a) de mai jos,in forma disjunctiva.Dupa cum se poate observa,X-ul de pe prima linie nu a fost grupat,iar cei doi de pe linia a doua,pentru ca au ajutat la formarea de grupari maximale,au fost utilizati.Functia in forma normala disjunctive este f(A,B,C)= + C

• Diagramele Veitch ale functiilor incomplete definite