Minimizarea funcțiilor booleene prin metoda diagramelor Karnaugh

Minimizați cu ajutorul diagramelor Karnaugh funcția logică: Σ(0, 2, 6, 7, 11, 13) + Σ*(3, 8, 9, 14), unde prin Σ* sunt notate combinațiile imposibile.

Pentru aceste tipuri de exerciții trebuie să știm că o diagramă Karnaugh este un tablou bidimensional cu 2ⁿ locații, unde n reprezinta numărul de variabile pe care le are funcția. De asemenea trebuie să mai știm sa generăm codul Gray pentru diagrama noastră. Avem nevoie de codul Gray deoarece in diagramele Karnaugh etichetele nu se scriu în ordinea naturală, ci în ordinea Gray.

O modalitate simpla de a genera codul Gray este metoda asa numită "oglindire + completare". În tabelul de mai jos aveți un exemplu despre cum se generează codul Gray pentru o funcție cu 3 variabile.

z	y	x		y	x		x
0	0	0		0	0		0
0	0	1		0	1		1
0	1	1		1	1
0	1	0		1	0
1	1	0
1	1	1
1	0	1
1	0	0

Rosu - Partea inițială Albastru - Oglidirea Verde - Completarea;

Acum că avem codul lui Gray trebuie să deteminăm câte variabile are funcția noastră. În cazul în care funcția este dată sub forma Σ-notație atunci trebuie să scriem cel mai mare număr ce apare în Σ-notație în baza 2, iar numărul de cifre pe care îl va avea reprezintă numărul de variabile. Observăm că cel mai mare număr din Σ-notație este 14 care în baza 2 este scris sub forma: 0110, deci funcția noastră este de 4 variabile.

Desenăm diagrama Karnaugh pentru 4 variabile și introducem valorile care se dau:

Acum încercăm să cautăm blocuri conţinând numai valori 1 și ajutându-ne de combinațiile imposibile, astfel încât:

• fiecare valoare 1 să fie inclusă în cel puţin un bloc;
• blocurile să fie cât mai mari şi mai puţine;
• un bloc să conţină un număr de locaţii egal cu o putere a lui 2, eventual puterea 0;

Trebuie reținut că minimizările rezultate nu sunt unice!

O posibilă variată de minimizare este reprezentată de următoarea diagramă.

Trebuie doar să scriem funcția rezultată din diagrama Karnaugh de mai sus. Pentru asta trebuie să ținem de următoarele lucruri:

• în termen apar acele variabile ale căror etichete sunt constante pentru toate locațiile din bloc, adică dacă o variabilă apare etichetată cu 1 și apoi apare etichetată și cu 0 nu se mai scrie;
• o variabilă apare negată dacă eticheta sa constantă este 0 și nenegată altfel;
• termenii astfel obținuți (după considerarea tuturor blocurilor) sunt legați prin disjuncție.

După ce considerăm toate blocurile, funcția noastră va arăta cam așa:

F = !A*C + !B*!C*!D + A*!B*D + A*!C*D;