Vizualizare sursă pentru „Diagramă Karnaugh”

'''Diagramele Karnaugh''', numite și '''hărți Karnaugh'''<ref>{{citat carte|last=Kuphaldt|first=Tony R|other=Mihai Olteanu|title=Lessons In Electric Circuits|trans_title=Introducere în circuite electrice și electronice|volume=IV|year=2000-2007|url=http://www.circuiteelectrice.ro/electronica-digitala|ref=Kup06}}</ref>, au fost inventate în [[1950]] de Maurice Karnaugh, un inginer în telecomunicații de la [[Laboratoarele Bell]] pentru a facilita minimizarea [[expresie booleană|expresiilor algebrice booleene]]. 

În mod normal, pentru minimizarea acestor expresii este nevoie de calcule complicate, folosind formule și iterații, pe când Diagramele Karnaugh sunt mult mai simplu și mai rapid de utilizat pentru că folosesc capabilitățile [[creier]]ului uman de recunoaștere a formelor pentru a decide care termeni să fie combinați pentru a găsi expresiile cele mai simple.

Diagramele Karnaugh pot fi construite pentru oricât de multe variabile. Totuși, o diagramă Karnaugh poate fi de folos pentru simplificarea expresiilor de până la șase [[variabilă|variabile]]; cu mai multe variabile, devine mai greu pentru creierul nostru să vadă modelele, astfel că de obicei, pentru mai mult de patru variabile, se folosește [[algoritmul Quine-McCluskey]].

==Reducerea expresiilor==
[[Fișier:Fucion_logica_2.PNG|thumb|Diagrama Karnaugh pentru 2, 3 și 4 variabile]]
Diagrama Karnaugh se construiește punând valorile unor variabile pe linii și al celorlalte variabile pe coloane. Distribuția valorilor trebuie să respecte [[codul Gray|codului Gray]], astfel că între două căsuțe vecine există o diferență de un bit. Valoarea asociată unei căsuțe este valoarea [[funcție]]i pentru combinația respectivă de valori de intrare. Valorile posibile sunt '''1''', '''0''' sau '''X''' (nu contează). Diagramele pentru 2, 3 și 4 variabile sunt reprezentate în figura alăturată.

După ce am construit diagrama Karnaugh, trebuie să aflăm expresiile minimale care vor fi utilizate în expresia finală. Acest lucru va fi făcut prin încadrarea valorilor de '''1''', astfel încât figura reprezentată de acestea să aibă următoarele proprietăți:
* are formă dreptunghiulară
* conține 2<sup>n</sup> elemente, unde ''n'' este un număr natural (1, 2, 4, 8, 16 etc. elemente)
* este [[maximal]]ă, adică nu poate fi inclusă într-o altă figură cu aceste proprietăți, dar cu ''n'' mai mare. Dacă un mintermen are un vecin un alt mintermen de aceeași dimensiune, aceștia se pot uni, rezultând un mintermen cu mai puține variabile în componență.
* conține elemente '''X''' doar dacă zona rezultată este mai mare decât cea care putea fi obținută fără elementul respectiv (adică dacă se obține o reducere a termenului algebric echivalent).

Grupurile generate sunt convertite într-o expresie booleană prin:
* determinarea valorilor posibile ale variabilelor în grupul respectiv. Dacă figura se află pe o coloană unde A=1, se ia în considerare valoarea A. Dacă figura se află pe o coloană unde A=0, se ia în considerare valoarea <math>\overline{A}</math>
* se elimină variabilele care sunt prezente atât cu valoarea posibilă 1, cât și cea 0. 

Fiecare grup generează astfel un produs, iar valoarea expresiei booleene este suma acestor produse.

Funcția inversă se poate obține grupând valorile de '''0''', în locul celor de '''1'''.

==Exemplu==
===Enunț===
Fie o funcție f(A, B, C, D), cu următoarea tabelă de adevăr:
{| class="wikitable"
|-
! #!! <math>A</math> !! <math>B</math> !! <math>C</math> !! <math>D</math> !! <math>f(A, B, C, D)</math>
|-
| style="background: #eeeeee"|0
| 0 || 0 || 0 || 0
|  0
|-
| style="background: #eeeeee"|1
| 0 || 0 || 0 || style="background: #ffeeee" |1
| 0
|-
| style="background: #eeeeee"|2
| 0 || 0 || style="background: #ffeeee" |1 || 0
|  0
|-
| style="background: #eeeeee"|3
| 0 || 0 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1
|  0
|-
| style="background: #eeeeee"|4
| 0 || style="background: #ffeeee" |1 || 0 || 0
|  0
|-
| style="background: #eeeeee"|5
| 0 || style="background: #ffeeee" |1 || 0 || style="background: #ffeeee" |1
|  0
|-
| style="background: #eeeeee"|6
| 0 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || 0
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|7
| 0 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1
| 0
|-
| style="background: #eeeeee"|8
| style="background: #ffeeee" |1 || 0 || 0 || 0
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|9
| style="background: #ffeeee" |1 || 0 || 0 || style="background: #ffeeee" |1
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|10
| style="background: #ffeeee" |1 || 0 || style="background: #ffeeee" |1 || 0
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|11
| style="background: #ffeeee" |1 || 0 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|12
| style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || 0 || 0
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|13
| style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || 0 || style="background: #ffeeee" |1
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|14
| style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || 0
| style="background: #ffeeee" | 1
|-
| style="background: #eeeeee"|15
| style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1 || style="background: #ffeeee" |1
| 0
|}

Funcția dată cu parametrii mintermeni (adică valorile pentru care rezultatul funcției este 1 în tabela de adevăr) este:

<math>f(A, B, C, D) = \sum_{}m(6, 8, 9, 10, 11, 12, 13, 14) = (\overline{A}BC\overline{D}) + (A\overline{B}\overline{C}\overline{D}) + (A\overline{B}\overline{C}D) + (A\overline{B}C\overline{D}) + (A\overline{B}CD) +</math><br/><math>+ (AB\overline{C}\overline{D}) + (AB\overline{C}D) + (ABC\overline{D})</math>

Se dorește reducerea acestei expresii până la cea mai mică [[expresie algebrică]] echivalentă.

===Rezolvare===
Având 4 variabile de intrare, ele pot fi combinate în 16 feluri diferite, astfel că diagrama Karnaugh trebuie să aibă 16 poziții. Cel mai convenabil mod este să fie aranjate într-un tabel 4x4, după cum este ilustrat în figura de mai jos.

[[Imagine:K-map 6,8,9,10,11,12,13,14.svg]]

Valorile din diagramă reprezintă ieșirea funcției pentru combinația de valori de intrare corespunzătoare valorilor de pe linie și coloană. În colțul din stânga-sus avem 0 pentru f(0, 0, 0, 0) = 0, iar în dreapta sus f(1, 0, 0, 0) = 1.

Grupurile definite sunt marcate prin culori. Zona maro este obținută prin suprapunerea grupurilor roșu și verde. Aplicând regulile descrise mai sus, expresiile algebrice corespunzătoare grupurilor sunt:
{| class="wikitable"
|-
!Grup
!Variabile
!Expresie
|-
|style="background: #ff1111;color:white;"|'''roșu'''
|<math>A, B, \overline{B}, \overline{C}, D, \overline{D}</math> 
|<math>A\overline{C}</math>
|-
|style="background: #11ff00;color:white;"|'''verde'''
|<math>A, \overline{B}, C, \overline{C}, D, \overline{D}</math> 
|<math>A\overline{B}</math>
|-
|style="background: blue;color:white;"|'''albastru'''
|<math>A, \overline{A}, B, C, \overline{D}</math> 
|<math>BC\overline{D}</math>
|}

Rezultă deci:
<math>f(A, B, C, D) = A\overline{C} + A\overline{B} + BC\overline{D}</math>

Funcția inversă (obtinută prin grupare de zerouri - zonele gri):
<math>\overline{f}(A, B, C, D) = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD</math>

==Note==
<references/>

== Vezi și ==
* [http://www.circuiteelectrice.ro/electronica-digitala/harti-karnaugh Hărți Karnaugh] la circuiteelectrice.ro

[[Categorie:Logică binară]]
[[Categorie:matematică]]