Problema minimizării unei funcții booleene este găsirea unei formule echivalente care are o complexitate minimă. Sub complexitatea formulei se înțelege numărul de litere care intră în ea. Metodele de minimizare a funcțiilor biliare prezentate în DNF sunt cele mai bine dezvoltate. Aceste metode se bazează pe conceptul de implicați simpli.
Dacă există o funcție booleană # 966; este egal cu zero în aceleași seturi pe care o altă funcție F dispare și, de asemenea, pe alte seturi, atunci spunem că funcția # 966; intră în funcția F și este implicantă. Condiția de înscriere este scrisă după cum urmează: jÌF. De exemplu, ia în considerare funcția F = XÅY. Implicanții lui sunt funcții
Simplificanții implicați ai unei funcții booleene F sunt acele conjuncții elementare care intră într-o anumită funcție, dar nu este inclusă nici o parte corespunzătoare a acestor conjuncții în funcția F. O parte proprietară este o lucrare obținută prin excluderea unuia sau a mai multor factori dintr-o anumită lucrare. De exemplu, o lucrare are propriile părți:
De exemplu, pentru So și sunt implicați simpli ai funcției F.
Simplificații implică cele mai scurte conjuncții elementare care intră în această funcție booleană.
Orice funcție booleană poate fi reprezentată ca o disjuncție a tuturor implicanților ei simpli. Disjuncția tuturor implicanților simpli este numită DNF redusă a unei funcții booleene. Există mai mulți algoritmi pentru obținerea unei funcții Boolean DNF reduse. Una dintre cele mai dezvoltate este metoda Quine.
Metoda lui Quine. Această metodă se bazează pe transformarea CDNF printr-o operație incompletă de lipire și absorbție.
Funcționarea lipirii (completă) este determinată de relația
Se spune că doi membri ai XY sunt lipiți împreună în variabila Y.
Funcționarea lipirii incomplete este definită prin formula
În partea dreaptă, pe lângă termenul X. al lipirii rezultante, ambii termeni care participă la lipire sunt scrise.
Funcționarea absorbției este determinată de relația
Quote teorema. Dacă în CDNF a unei funcții booleene se efectuează toate operațiile de lipire incompletă și apoi toate operațiile de absorbție, atunci obținem un DNF abreviat al acestei funcții, adică disjuncția tuturor implicanților săi simpli.
Practic abreviat DNF este convenabil de a găsi într-o astfel de secvență.
Efectuați în CDNF toate operațiile posibile de lipire incompletă a unității constituente și toate operațiunile posibile de absorbție.
Apoi, efectuați toate operațiile posibile de lipire incompletă și absorbție a membrilor cu (n -1) litera.
Efectuați toate operațiile posibile pentru lipirea și absorbția incompletă a elementelor cu un număr de litere egal cu (n -2), etc.
Realizăm toate operațiile posibile de lipire și absorbție incompletă cu conjuncții în patru litere. Rezultatul este adăugat la tabel:
Numărul de rezultate lipite
Vom scrie formulele abreviate, care trebuie să includă conjuncțiile obținute ca rezultat al lipirii, și acele constituenți inițiale ale unității care nu s-au lipit împreună:
În expresia rezultată, efectuăm din nou toate operațiile posibile de lipire și absorbție:
Primul și al patrulea, al doilea și al treilea element sunt lipite împreună în perechi. Al cincilea și al șaselea membru rămân. Astfel, primim:
În această expresie, nu există termeni care să rămână împreună, deci este o formă normală disjunctivă abreviată. Pentru a găsi forma minimă disjunctivă, se poate folosi o matrice implicită. În matricea implicată, coloanele sunt marcate de constituenții unității unei funcții date, iar rândurile de implicanții obținute ca rezultat al lipirii (Tabelul 5).
Dacă implicantul este o parte intrinsecă a unei unități constitutive, atunci celula matricei corespunzătoare acestui implicant și constituent al unității este marcată cu o cruce. Pentru a obține forma normală disjunctivă minimă a unei funcții date, este necesar să se găsească numărul minim de implicați care acoperă împreună toate coloanele matricei implicate cu încrucișările. În exemplu, forma minimă disjunctivă a unei funcții date are forma
.
Se poate întâmpla ca funcția să aibă mai multe forme minime diferite, de aceeași complexitate.
Hărți ale lui Carnot (Veitch). Harta Carnot este un dreptunghi împărțit în celule, numărul cărora este egal cu numărul tuturor seturilor posibile de variabile independente ale unei funcții logice date. Pentru o funcție a două variabile, harta conține 4 celule, pentru o funcție de 3 variabile, 8 celule etc.
Luați în considerare o hartă pentru două variabile (Figura 21). Fiecare celulă de cartelă corespunde componentei unității.
Fig. 21. Harta Carnot pentru Fig. 22. Harta pentru Carnot pentru
funcțiile a 2 variabile ale unei funcții a 3 variabile
Prin adăugarea unei variabile, cardul se dublează. În Fig. 22 prezintă harta Carnot pentru o funcție de 3 variabile.
La construirea unei hărți se poate folosi următoarea regulă: harta Carnot pentru o funcție de variabile n este obținută de pe hartă pentru o funcție a variabilelor n-1, dacă aceasta este dublată adăugând la ea exact aceeași simetric față de fața lungă. În acest caz, o jumătate din noul card este marcat cu o nouă scrisoare în forma afirmativă, iar cealaltă jumătate cu aceeași literă, dar cu un negativ. În Fig. 23 prezintă harta Carnot pentru o funcție de 4 variabile, obținută din harta prezentată în Fig. 22. Într-o hartă marcată corespunzător, oricare două celule adiacente corespund
componentele lipite ale unității. În plus, oricare două celule situate la marginile hărții simetric pe partea stângă și pe dreapta sau pe partea superioară și inferioară, corespund, de asemenea, componentelor unității lipite împreună.
Minimizarea unei funcții logice date utilizând o cartelă Carnot este efectuată în această secvență.
1. Funcția specificată este convertită în CDNF.
2. Fiecare unitate constitutivă a unei funcții date este marcată cu o unitate în celula corespunzătoare a hărții Carnot.
3. Unitățile situate una lângă alta sau simetric pe marginea hărții sunt acoperite de dreptunghiuri regulate. Sunt îndeplinite următoarele cerințe:
- Numărul de unități acoperite de un dreptunghi trebuie să fie de 2 k. unde k este un număr întreg;
- Fiecare dreptunghi trebuie să acopere cât mai multe unități posibil și numărul de dreptunghiuri acoperitoare ar trebui să fie cât mai mic posibil;
- Una și aceeași unitate poate fi acoperită de mai multe ori cu diferite dreptunghiuri.
4. Pentru fiecare unitate care acoperă dreptunghi, vom scrie o conjuncție în care trebuie să intre literele care sunt comune pentru unitățile acoperite de acest dreptunghi.
5. Notați DNF minime. în care trebuie să pătrundă conjuncțiile corespunzătoare tuturor dreptunghiurilor de acoperire. Dacă pe hartă există unități care sunt izolate de celelalte și care nu sunt acoperite de dreptunghiuri, atunci componentele corespunzătoare ale unității sunt adăugate la disjuncția rezultată.
6. Dacă este posibil, scurtează formula care rezultă prin introducerea termenilor generali în paranteze.
Un exemplu. Luați în considerare o funcție a patru variabile. Să presupunem că SDNF-ul unei funcții date are forma:
Fiecare unitate constitutivă a funcției reduse este marcată de o unitate în celula corespunzătoare a hărții Carnot (a se vedea figura 23). Pentru claritate, dreptunghiurile care acoperă unitățile sunt marcate cu linii ovale. Valoarea DNF minimă a acestei funcții este:
Carnota Carnot pentru o funcție de cinci variabile este prezentată în Fig. 24. Pentru o funcție de șase variabile ¾ din Fig. 25. Hărțile Carnot pentru funcțiile a cinci și șase variabile au următoarele caracteristici. Conjuncțiile de legare corespund unităților situate în interiorul hărții simetric față de axele centrale ale simetriei.
Un exemplu. Fie funcția a cinci variabile reprezentate de unitățile marcate pe harta Carnot din Fig. 24. Ca rezultat al învelișului, obținem următoarea DNF minimă:
Considerăm minimizarea funcției a șase variabile utilizând exemplul unei funcții marcate cu unități în harta din Fig. 25. Ca urmare a acoperirii, obținem:
Când scrieți implicanții care rezultă din acoperirea unităților din harta Carnot, puteți folosi următoarele dependențe pentru control: l = n-k. m = 2 k. unde l este numărul de litere din implicitul obținut ca rezultat al acoperire, m este numărul de unități acoperite de acest dreptunghi, k este numărul de litere absorbite ca rezultat al lipirii și n este numărul de variabile independente din funcție.
Fig. 25. Carnot map pentru o funcție de 6 variabile
Articole similare
Trimiteți-le prietenilor: