Transformarea diagramelor Venn in harti Karnaugh

Transformarea diagramelor Venn in harti Karnaugh

Harti Karnaugh cu doua variabile

Incepem transformarea unei diagrame Venn intr-o harta Karnaugh prin desenarea unei multimi A in universul A' (figura de mai jos, a):

Extindem apoi cercul A (b si c), modificam forma lui la punctul (d), si transformam A intr-un dreptunghi (e). Tot ceea ce nu se afla in A este A'. Desenam un dreptunghi si pentru A' (f). De asemenea, nu folosim hasuri pentru hartile Karnaugh. Ceea ce avem pana in acest moment este o harta Karnaugh cu o singura variabila. Acest lucru nu ne ajuta insa. Avem nevoie de variabile multiple.

Figura (a) de mai jos este identica diagramei Venn precedente, cu diferenta ca notatiile A si A' se afla deasupra diagramei si nu in interior. Urmand un proces similar, putem construi "o diagrama Venn dreptunghiulara" pentru B si B' (b). Vom trece acum la suprapunerea diagramelor de la (a) si (b) pentru obtinerea rezultatului (c), la fel cum am facut pentru diagramele Venn. Motivul pentru care realizam acest lucru este pentru a observa ceea ce este comun celor doua regiuni suprapuse - de exemplu, locul in care A se suprapune cu B. Patratul din dreapta jos (c) corespunde relatiei AB, unde A se suprapune cu B:

Totusi, nu vom pierde vremea desenand harti Karnaugh precum cea de mai sus (c), ci vom folosi o versiune simplificata:

Coloana formata din cele doua celule de sub A' este asociata multimii A' (stanga); similar pentru celelalte multimi. Pentru simplitate, regiunile nu vor fi delimitate atat de clar precum in cazul diagramelor Venn.

Harta Karnaugh din dreapta este o forma alternativa utilizata in majoritatea textelor. Numele variabilelor sunt trecute langa linia diagonala. A-ul de deasupra diagonalei indica faptul ca variabila A (si A') apartine coloanelor. 0 este folosit pentru A' iar 1 pentru A. B-ul de sub diagonala este asociat cu liniile: 0 pentru B' si 1 pentru B.

Exemplu

Marcati casutele corespunzatoare expresiei booleene AB in diagrama Karnaugh de mai sus cu 1. Solutie: hasuram sau incercuim regiunea corespunzatoare lui A; marcam apoi regiunea corespunzatoare lui B. Intersectia celor doua regiuni reprezinta AB; trecem un 1 in aceasta casuta. Nu este insa necesar sa incercuim propriu-zis regiunile A si B:

Harti Karnaugh cu trei variabile

Trecem acum la dezvoltarea unei harti Karnaugh pornind de la diagrame Venn. Universul (interiorul dreptunghiului negru) este impartit in doua regiuni inguste A' si A. B si B' impart universul in doua regiuni patrate. C-ul ocupa o regiune patrata in mijlocul dreptunghiului, iar C' este impartit in doua dreptunghiuri verticale de fiecare parte a patratului C:

In figura finala suprapunem toate cele trei variabile, incercand sa delimitam clar fiecare regiune. Aceasta harta Karnaugh cu 3 variabile are 2³ = 8 regiuni, casutele din interiorul hartii. Fiecare regiune este unic determinata prin intermediul celor trei variabile booleene (A, B si C). De exemplu ABC' reprezinta regiunea din dreapta jos (*), iar A'B'C' reprezinta regiunea din stanga sus (x):

Totusi, in mod normal nu vom nota o harta Karnaugh conform figurii de mai sus stanga. Notarea hartilor Karnaugh se va face conform figurii din dreapta. Fiecare regiune este unic determinata printr-un produs de 3 variabile, o expresie booleana SI.

Cele doua forme diferite de mai sus sunt echivalente, si reprezinta forma finala a acestora. Versiunea din dreapta este putin mai usor de folosit, din moment ce nu suntem nevoiti sa scriem toate variabilele de fiecare data, ci doar 1 si 0. Notatia B'C', B'C, BC si BC' din stanga este echivalenta cu 00, 01, 11 respectiv 10 din dreapta. A si A' sunt echivalente cu 0 respectiv 1.