Cuprins

Minimizare

Formele normale conjunctivă (FNC) şi disjuntivă (FND) pot avea expresii complexe, pentru care există uneori variante mai simple cu aceeaşi semnificaţie. Odată obţinută FNC sau FND, minimizarea se face cu ajutorul axiomelor şi teoremelor prezentate mai sus. În practică, cel mai des se folosesc unificarea, absorbţia şi idempotenţa.

Metoda Karnaugh

Este o formă vizuală de detectare a posibilităţilor de unificare.

Aşa cum am arătat mai sus, x y + x y = y. în general, x E + x E = E, unde E este o expresie booleană oarecare. Ideea este să detectăm astfel de situaţii, cu scopul de a reduce complexitatea expresiei funcţiilor.

În exemplul de mai sus, de pildă, aveam:

f(x, y, z) = x y z + x y z + x y z + x y z

Observam că putem unifica, conform formulei de mai sus, primul şi ultimul termen, obţinând:

x y z + x y z = y z

Similar putem unifica termenii 1 şi 2 eliminând y, sau 2 şi 3 eliminând z (un termen poate fi implicat în mai multe unificări, conform axiomei de idempotenţă).

De observat că vor putea participa la unificare perechi de termeni a căror reprezentare binară diferă printr-un singur bit:

x y z - 0 0 0

x y z - 1 0 0

Aceasta conduce la ideea aranjării termenilor astfel încât termenii care se pot reduce să fie, pe cât posibil, vecini (topologic). Codul Grey îndeplineşte această condiţie. Algoritmul de obţinere a codului Grey pe n biţi este:

  1. se porneşte cu codul Grey pe 1 bit: 0 1
  2. se oglindeşte codificarea de la pasul curent: 0 1 1 0
  3. codificările din prima jumătate se prefixează cu 0, celelalte cu 1: 00 01 11 10
  4. se repetă paşii 2 şi 3 pâna se ajunge la numărul de biţi dorit.

Se poate arăta prin inducţie că vecinii diferă printr-un singur bit, inclusiv primul şi ultimul (circular).

O diagramă Karnaugh pentru o funcţie booleană se construieşte astfel:
  • se împart variabile de intrare în două mulţimi X1 şi X2 egale sau cât mai apropiate ca dimensiune (| |X1| - |X2| | <= 1)
  • se construieşte un tabel cu 2|X1| linii şi 2|X2| coloane
  • se scriu pe fiecare din cele doua dimensiuni ale diagramei toate combinaţiile posibile pentru setul corespunzător de variabile de intrare, în cod Grey
  • în tabel se marchează cu 1 celulele corespunzătoare combinaţiilor pentru care funcţia are valoarea 1.

De exemplu, pentru funcţia de mai sus, se obţine diagrama:

\x y
\
z\		0 00 11 11 0
011 1
1 1

În diagrama astfel construită vom căuta blocuri de celule de dimensiune 2k, în care k dintre variabile descriu toate combinaţiile posibile pe k biţi, în timp ce toate celelalte pastrează aceeaşi valoare în toate celulele blocului (deci nu din orice bloc de dimensiune 2k putem obţine o expresie simplificată). Unui astfel de bloc îi va corespunde un termen în care apar în conjuncţie acele variabile care au aceeaşi valoare în toate celulele blocului, direct daca valoare este 1 şi negat dacă valoarea este 0. Toate blocurile trebuie să producă un termen în forma finală a funcţiei (în cazul cel mai nefavorabil, o celula face parte dintr-un bloc de 1 = 20, reducându-se 0 variabile). O celula, aşa cum am arătat mai sus, poate fi inclusă în mai multe blocuri dacă este necesar.

Pentru funcţia de mai sus, blocurile pot fi:

\x y
\
z\		0 00 11 11 0
011 1
1 1

obţinându-se expresia:

f(x,y,z) = y z + x y

Pentru o funcţie de forma:

\x y
\
z t\		0 00 11 11 0
0 011
0 1
1 1
1 011

analizând combinaţiile care apar:

x y z t

0 0 0 0

0 0 0 1

1 0 0 0

1 0 0 1

observăm că putem elimina x şi t, obţinând

f(x,y,z,t) = y z

Nu orice bloc de 2k va produce o unificare. Un exemplu este blocul de 4 din diagrama de mai jos. în schimb, în cazul în care avem mai mult de 4 variabile de intrare, există termeni care se pot unifica deşi celulele corespunzătoare nu sunt vecine în diagramă. O regulă mai generală pentru unificare este considerarea celulelor plasate simetric faţă de axele de simetrie ale diagramei.

\x y z
\
t u\		0 0 00 0 10 1 10 1 01 1 01 1 11 0 11 0 0
0 0 1111
0 1
1 1 1 1
1 0
Minimizare pentru FNC
Se poate extinde uşor metoda prezentată mai sus la minimizare pentru FNC astfel:
  • Se vor completa - cu 0 - în diagramă (construită aşa cum s-a arătat mai sus) doar locaţiile ale căror etichete codifică intrările pentru care funcţia este 0
  • Se va căuta o acoperire cu blocuri de 0, cu aceleaşi proprietăţi ca ale blocurilor de 1 pentru FND
  • Fiecărui bloc îi va corespunde un factor în care apar doar variabilele a căror etichetă este aceeaşi pentru toate celulele blocului
    • negate dacă au eticheta 1
    • ne-negate dacă au eticheta 0
    • legate prin sau (+)
  • Factorii astfel obţinuţi se leagă prin şi.

Exerciţii

Să se minimizeze următoarele funcţii:

  • ∑(1,2,3,4,9,15)
  • ∑(0,2,6,8,10)
  • ∑(0,2,5,7,13,16,21,23,29)
  • ∑(11,15,18,20,22,28,43,47,50,54,58)
  • ∑(1,5,7,8,9,10)
  • ∑(0,1,5,7,8,9,10)
  • ∑(0,2,9,13,18,19,22,23,25,29)