08. Mintermeni şi maxtermeni

Acasă » Electronică digitala » 08 - Hărţi Karnaugh

Soluţia sub forma produsului de sume

Până în acest moment am căutat soluţii sub forma unei sume de produse la problemele de simplificare booleană. Pentru fiecare dintre aceste soluţii există o altă soluţie sub forma unui produs de sume. Acest tip de soluţie se poate dovedi a fi mai practică, în funcţie de aplicaţie. Dar, înainte de a scrie soluţiile sub forma unui produs de sume, trebuie să introducem câteva 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 comparaţie cu noua procedură pentru maxtermeni.

Analiza regiunilor ce conţin valori de 1 - mintermeni

Un mintermen este o expresie booleană rezultând într-o valoare de 1 pentru ieşirea unei singure regiuni dintr-o hartă Karnaugh. Toate celelalte regiuni ale hărţii Karnaugh sau ale tabelului de adevăr fiind 0 în acest caz. Dacă un mintermen conţine un singur 1, iar regiunile rămase sunt toate 0, aria minimă pe care acest mintermen o acoperă este 1.

Figura de mai jos (stânga) 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. Până în acest moment, nu am prezentat valorile de 0 pe hărţile Karnaugh considerate. Acestea se omit de obicei, excepţie făcând 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 stânga. Regiunea 010 corespunde la rândul ei mintermenului A'BC'. O expresie booleană sau o hartă poate avea mai mulţi mintermeni.

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

• Identificăm mintermenul (produsul) ce vrem să-l introducem pe hartă
• Scriem valoarea numerică corespunzătoare
• Ne folosim de valoarea binară ca şi adresă pe hartă
• Introducem un 1 la adresa respectivă
• Repetăm paşii 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 mulţi mintermeni, corespunzând mai multor regiuni pe o hartă Karnaugh, precum în exemplul de mai jos:

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 mulţi 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 A'BC'. În acest exemplu nu a existat nicio simplificare. Totuşi, 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 simplificării expresiei booleene sub forma unei sume de produse dintr-o hartă Karnaugh:

• Formăm grupuri de 1 cât mai mari posibile, acoperind toţi mintermenii de pe hartă. Grupurile trebuie să conţină un număr de regiuni sub forma puterii lui 2 (1, 2, 4, 8, etc.)
• Scriem valori numerice binare pentru fiecare grup
• Transformăm valoarea binară sub forma unui produs
• Repetăm paşii 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 până în acest moment. Am scris doar paşii de urmat în cazul mintermenilor. Acelaşi lucru îl vom face şi în cazul maxtermenilor.

Analiza regiunilor ce conţin valori de 0 - maxtermeni

Să considerăm acum o funcţie booleană ce este 0 pentru o singură regiune şi 1 în rest:

Un maxtermen este o expresie booleană a cărei valoare este 0 pentru o singură regiune, toate celelalte regiunii ale hărţii Karnaugh sau ale tabelului de adevăr fiind 0. Vedeţi şi explicaţia de la mintermen. Figura de sus stânga 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 hărţii fiind 1. Dacă un maxtermen are un singur 0, iar celelalte regiuni sunt 1, aria maximă pe care o acoperă este 1.

Există câteva diferenţe 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ă locaţia expresiei (termenului) (A + B + C) pe hartă este 000. Pentru ecuaţia „ieşire = (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 intrările sunt egale cu 0. Aceasta este singura posibilitate pentru a obţine valoarea de 0 pentru maxtermen. Toate celelalte regiuni conţin 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.

Luând în considerare figura de mai sus, paşii care trebuiesc urmaţi pentru introducerea unui maxtermen pe harta Karnaugh, sunt următorii:

• Identificăm termenul sub formă de sumă (maxtermenul) ce-l vom introduce pe hartă
• Scriem valoarea numerică binară corespunzătoare
• Formăm complementul
• Utilizăm complementul ca şi adresă pentru introducerea valorii de 0 pe harta Karnaugh
• Repetăm paşii de mai sus pentru toţi ceilalţi 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 hărţii Karnaugh de mai jos:

Scrierea expresiei booleene simplificate ca şi produs de sume

O expresie booleană sub formă produsului de sume poate avea mai mulţi maxtermeni, conform figurii de mai jos:

Maxtermenul (A + B + C) sub formă numerică este 111, iar complementat este 000. Plasăm prin urmare un 0 la adresa (0, 0, 0). Maxtermenul (A + B + C') sub formă numerică este 110, iar complementat este 001. Plasăm prin urmare un zero la adresa (0, 0, 1).

Acum că am construit harta Karnaugh, suntem interesaţi de modul în care putem scrie o formă simplificată a expresiei booleene iniţiale sub formă de produs de sume. Primul pas este gruparea termenilor de 0, precum grupul de mai jos:

Scriem apoi valoarea binară corespunzătoare termenului-sumă, ce arată astfel: (0, 0, X). Pentru grupul format, atât A cât şi B sunt 0. Dar C este atât 0 cât şi 1. Prin urmare, scriem un X în locul valorii lui C. Formăm complementul: (1, 1, X). Scriem termenul sumă (A + B) ignorând C-ul şi X-ul ce l-a înlocuit.

Să reluăm paşii necesari pentru reducerea unei expresii booleene la un produs de sume:

• Formăm grupuri de 0 cât mai mari posibile, incluzând toţi maxtermenii. Numărul termenilor trebuie să fie puteri ale lui 2
• Scriem valoarea numerică a grupului
• Complementăm această valoare numerică a grupului
• Transformăm valoarea complementată într-un termen sub formă de sumă
• Repetăm paşii de mai sus pentru toate grupurile rămase pe hartă. Rezultatul fiecărui grup este un termen sub formă de sumă, iar rezultatul final este produsul acestor termeni-sumă

Exemplul 1

Simplificaţi expresia booleană sub forma produsului de sume de mai jos. Scrieţi rezultatul final sub forma unui produs de sume:

Soluţie: completăm o hartă Karnaugh cu cei şapte maxtermeni de mai sus (introducem valori de 0). Reţineţi să complementaţi variabilele de intrare pentru găsirea adresei corespunzătoare:

După ce am introdus toţi maxtermenii în tabel, trecem la gruparea regiunilor, precum în figura de mai jos. Grupurile mai mari se traduc printr-un termen-sumă cu mai puţine intrări. Cu cât avem mai puţine grupuri, cu atât vom avea mai puţin termeni-sumă în expresia finală:

Avem trei grupuri, prin urmare, trebuie să avem trei termeni-sumă în rezultatul final. Detaliile simplificării sunt prezentate în figura de mai sus. Pentru oricare grup, scriem mai întâi adresa de intrare, o complementăm şi o transformăm într-un termen boolean sub formă de sumă. Rezultatul final este produsul acestor trei termeni-sumă.

Exemplul 2

Simplificaţi expresia booleană sub formă de produs de sume de mai jos, exprimând rezultatul sub forma unei sume de produse:

Această problemă este identică cu cea anterioară, cu diferenţa că expresia simplificată se cere sub formă de sumă de produse şi nu sub formă de produs de sume.

Trecem maxtermenii (0) din expresia iniţială pe harta Karnaugh de mai jos (stânga), exact ca în exemplul precedent:

Completăm apoi toate celelalte regiuni rămase libere cu valori de 1 (dreapta sus).

Formăm grupuri de 1 pentru toate regiunile ce conţin valori de 1. Scriem apoi rezultatul simplificat sub forma sumei de produse, conform secţiunii precedente a acestui capitol. Acest lucru este identic problemei precedente: