Analiza și sinteza dispozitivelor logice. Metode de minimizare a funcțiilor și circuitelor logice. Metode de minimizare a funcțiilor algebrică logică

pentru primul – X 3 X 4;

pentru al doilea – X 1 X 3;

pentru al treilea – X 2 X 3;

pentru al patrulea – X 1 X 2 X 4;

pentru al cincilea – X 1 X 2 X 4;

Un DNF minim ar arăta astfel:

Comparând metoda hărții Karnaugh cu alte metode de minimizare a funcției, putem concluziona că prima este cea mai potrivită pentru execuția manuală. Timp făcut singur este semnificativ redusă (datorită reprezentare vizuala implicanţi adezivi). Implementare software Această metodă are propriile sale dificultăți. Deci, va fi foarte greu de implementat alegere optimă dreptunghiuri regulate, mai ales pentru un număr mare de argumente.

1.3.5 Metoda coeficienților incerti

Această metodă poate fi folosită pentru orice număr de argumente. Dar, deoarece această metodă este destul de greoaie, este utilizată numai în cazurile în care numărul de argumente nu este mai mare de 5-6.

Metoda coeficienților nedeterminați folosește legile mulțimilor universale și nule și legile repetiției. La început, toți coeficienții sunt incerti (de unde și denumirea metodei).

Să construim o matrice de coeficienți nesiguri pentru patru argumente. În acest caz, vom avea un sistem de 16 ecuații.

Sistemul este prezentat pe pagina următoare.

Să echivalăm toți coeficienții cu 0 în acele rânduri care corespund cu 0 în coloana vectorială. Apoi echivalăm coeficienții corespunzători din alte rânduri la 0. După aceste transformări, sistemul va lua următoarea formă:

V = 1 VVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1

Acum, în fiecare linie, trebuie să selectați coeficientul rangului minim și să-l echivalați cu unul, iar coeficienții rămași la 0. După aceea, tăiați linii identice, în timp ce lăsăm unul dintre ele (sînt barate și acele linii pentru care toți coeficienții sunt egali cu 0).

= 1 = 1 = 1 = 1 = 1

Să notăm acum conjuncțiile corespunzătoare coeficienților egali cu unitatea. Vom obține DNF minim.

F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .

Deci, am obținut DNF-ul minim în mai multe moduri.În toate cazurile s-a dovedit a fi același, adică oricare dintre metodele descrise poate fi folosită pentru a minimiza funcția. Cu toate acestea, aceste metode diferă semnificativ între ele atât în principiul găsirii MDNF, cât și în timpul de execuție. Metoda hărții Karnaugh este foarte convenabilă pentru calcule manuale. Este vizual și nu necesită operațiuni de rutină, iar alegerea locației optime a dreptunghiurilor corecte nu este dificilă. În timp ce implementarea pe mașină a acestei metode este complicată de necesitatea de a găsi aranjamentul optim al dreptunghiurilor. Desigur, utilizarea altor metode (metoda Quine, metoda Quine-McCluskey, metoda coeficienților nedeterminați) pentru calculele manuale este inadecvată. Sunt mai potrivite pentru implementarea mașinii, deoarece conțin un număr mare de operații simple repetate.

Sarcina 2.

2.1 Diagrama algoritmului pentru metoda lui Quine

1. Început.

2. Introduceți matricea DSNF a funcției originale.

3. Verificați liniile i-a (i=1,m-1: unde m este numărul de linii din DSNF) și j-a (j=i+1, m) linii pentru lipire. Dacă liniile sunt lipite împreună, treceți la pasul 6, în caz contrar treceți la pasul 5.

4. Formați o matrice de implicanți simpli, având în prealabil marcat cu simbolul ‘*’ variabila prin care aceste șiruri sunt lipite între ele.

5. Treceți la pasul 2.

6. Scrieți o linie care nu este îmbinată cu nicio altă linie în tabloul final.

7. Treceți la pasul 2.

8. Ieșirea matricei rezultate.

Diagrama logică a algoritmului în notația Lyapunov

V H V 1 Z 1 V 2 ¯ V 3 V 4 V K

V H – început.

V 1 – introduceți matricea DSNF a funcției originale.

V 2 – formează o matrice de implicanți simpli, având în prealabil marcat cu simbolul ‘*’ variabila prin care aceste șiruri sunt lipite între ele.

V 3 – un șir care nu este îmbinat cu niciun alt șir este scris în tabloul final.

V 4 – ieșirea matricei rezultate.

Z 1 – dacă liniile sunt lipite împreună, treceți la pasul 3, în caz contrar treceți la pasul 5.

V K – sfârşit.

Diagrama grafică a algoritmului.

Descriere mașinărie proceduri

Procedură blocată (S1, S2: Diz; IndexS1, IndexS2: octet);

Această procedură lipește împreună cele două disjuncte trecute la acesta. Clauzele sunt specificate în parametrii S1, S2. Indicii IndexS1, IndexS2 determină indicii acestor clauze în tabloul principal de lucru. Algoritmul procedurii este următorul: mai întâi, se caută numărul de caractere care sunt lipite. Dacă există 0 dintre ele, atunci sunt la fel și doar unul dintre ei este scris în tabloul final. Dacă 1, atunci locația simbolului este determinată de care aceste două disjuncții sunt lipite împreună și înlocuim acest simbol cu „*”. Toate rezultatele obținute sunt introduse în matricea REZ.

Toate celelalte funcții și proceduri ale programului sunt legate de acțiuni pe matrice, adică nu sunt direct legate de această metodă de găsire a MDNF. Prin urmare, nu are rost să le descriem.

2.2 Diagrama algoritmului pentru metoda lui Petrik

1. Început.

2. Introduceți matricea DSNF a funcției originale și implicanții simpli obținuți în metoda lui Quine.

3. Creați un tabel de etichete.

4. Folosind tabelul de etichete, construiți o conjuncție de disjuncții, fiecare dintre acestea fiind un set de implicanți care sunt în această coloană au semne.

Cea mai des folosită operație la minimizarea funcțiilor este operația de lipire.

AB+ ВB=B (A+ В)=B.

Să ne uităm la cele mai comune trei metode de minimizare.

1. Să fie date numerele de mulțimi de patru variabile, pe care funcția logică ia o valoare unitară: f (2,5,6,7,10,12,13,14)=1.

Să exprimăm această funcție logică în SDNF (nu vom scrie simbolul conjuncției):

f(0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

În prima etapă de minimizare, SDNF-ul original poate fi simplificat folosind legea lipirii, apoi obținem:

Atragem atenția asupra faptului că același constituent (implicant) poate fi lipit împreună cu alți constituenți (implicanți) de multe ori, deoarece în logica lui Boole se aplică legea idempotității:

prin urmare, orice constituent poate fi multiplicat.

În a doua etapă, vom folosi tabelul lui Quine (Tabelul 8), conform căruia aceasta metoda minimizarea și-a primit numele - metoda lui Quine. Tabelul prezintă toți implicanții obținuți în prima etapă de simplificare pe verticală, iar constituenții inițiali pe orizontală. Unitatea din tabel 8 se află acolo unde implicantul „acoperă” constituentul. Faptul este că constituentul poate fi întotdeauna înlocuit cu un implicant sau chiar un termen separat conform legii absorbției:

Tabelul 8

După ce am completat tabelul lui Quine, am ajuns să avem două unități în aproape fiecare coloană; Între timp, este suficient să aveți o unitate în grafic. Prin urmare, ori de câte ori este posibil, unitățile redundante ar trebui eliminate. Alegerea unităților se face pe baza numărului minim de termeni (unitățile selectate sunt umbrite). Ca rezultat, s-a dovedit că ne putem descurca cu doar trei implicanți în loc de șase:

Folosind tabele de adevăr, este ușor de verificat dacă funcția obținută în MNF reproduce toate valorile funcției originale. Rețineți că în caz general Pot exista mai multe soluții bazate pe criteriul termenelor minime.

2. Nu mai puțin mod eficient minimizarea funcțiilor logice este o metodă de combinare a indicilor. Pentru a o prezenta, să facem un tabel. 9, în coloanele cărora sunt scrise posibile combinații de indici. Ultima coloană conține valorile funcției. Analiza tabelului începe din stânga de-a lungul coloanelor. Principiul excluderii i, j_code este următorul. La intersecția coloanei i_, de exemplu, cu o combinație de indici 23, și j_row, de exemplu, 3_th, există codul 10, care corespunde implicantului. Prin urmare, în această coloană, oriunde apare codul 10, adică în rândurile 2, 3, 10 și 11, aceste coduri sunt excluse, deoarece valoarea funcției din a treia linie este zero. Acum să luăm o coloană cu o combinație de indici 124. Aici, codurile 010 sunt lăsate în rândurile a 2-a și a 6-a, iar codul 011 în rândurile a 10-a și a 14-a. Acest lucru a fost făcut deoarece aceste coduri se găsesc numai pe liniile cu o valoare a funcției. egal cu unu. Dimpotrivă, codul 110 al aceleiași coloane apare atât cu valori cu o singură funcție, cât și cu valori zero.

Tabelul 9

Deci, toate codurile de pe liniile care se termină cu valori ale funcției nule sunt excluse automat. Dacă aceste coduri cad pe linii care se termină cu o singură valoare a funcției, atunci nu sunt luate în considerare. Rămân doar acele coduri care sunt situate pe linii cu o singură valoare a funcției (aceste coduri sunt întunecate).

Apoi urmați următoarea regulă. Pentru ca o funcție să ia o valoare, egal cu unu, este suficient ca un singur implicant de pe linie să ia valoarea unitară. În primul rând, lăsăm implicantul minim, care se suprapune pe cele din rândurile 2, 6, 10 și 14. Apoi, bineînțeles, trecem la a 12-a linie. Aici lăsăm singurul cod de pe linie, 011, care corespunde implicantului. Același implicant este responsabil pentru a 13-a linie, care se termină și cu o unitate. Rămâne să luăm în considerare rândurile a 5-a și a 7-a. Ceea ce au în comun este implicatul: . Astfel, cu trei implicanți am acoperit toate valorile unice ale funcției, ceea ce coincide cu rezultatul obținut pe baza tabelelor lui Quine.

3. Există metoda grafica lipirea, care se numește metoda hărții Karnaugh (prezentată în Tabelul 10). Selectăm unități adiacente, aceștia vor fi termenii funcției noastre.

Tabelul 10

Avem două mandate

Deși de masă 9 este mai greoi decât masa. 8, metoda de combinare a indicilor nu este considerată mai complexă decât metoda lui Quine, dacă ne amintim că înainte de alcătuirea tabelelor lui Quine este necesar să se facă numeroase concatenări de constituenți și implicanți. Implementarea algoritmului metodei de combinare a indicilor pe un computer se dovedește a fi relativ simplă. Și dimpotrivă, simplitatea și claritatea externă a celei de-a treia metode de minimizare a funcțiilor logice folosind hărțile Karnaugh se dovedește a fi program complex la implementarea algoritmului pe un computer.

Tabelul 11

Tabelul 12

Harta Karnaugh pentru patru variabile este prezentată sub forma unui tabel. 11. Fiecare celulă a hărții corespunde unui constituent. Harta completată este prezentată în tabel. 12 (funcția este aceeași ca în primele două metode). Conform legii lipirii, doi constituenți adiacenți cu valori unitare pot fi întotdeauna combinați pentru a obține implicantul corespunzător. Mai mult, cele care se află la granițele hărții sunt considerate și adiacente. Unitățile care trebuie combinate pentru a obține un implicant adecvat pot fi determinate cu ușurință vizual. De asemenea, trebuie amintit că, în conformitate cu legea idempotității, aceeași unitate a mesei. 12 poate fi lipit de două sau trei unități adiacente.

Toate funcțiile logice sunt specificate fie ca formulă, fie ca tabel de valori. Uneori este necesar să se determine cea mai simpla formaînregistrarea acestei funcții cu un număr minim de funcții logice elementare ȘI, SAU, NU pentru ușurință în utilizare. Pentru aceasta se folosesc toate operatiile considerate incepand de la nr. 4 si metodele Quine si Veitch.

Metoda lui Quine ne permite să găsim cel mai simplu normal formă disjunctivă expresie logică, adică scrie expresie logică sub formă de disjuncție sau conjuncție, în timp ce semnul de inversare poate apărea doar peste un argument sau deloc. Algoritmul este dat în literatura de specialitate.

Metoda Veitch (hărți Karnaugh)

În această metodă, pentru a descrie o funcție de n variabile, este desenat un tabel special care conține 2n celule. Fiecare celulă corespunde unuia dintre seturile de n variabile. Celula înregistrează valoarea acceptată de funcție pentru acest set de argumente. Toate celulele corespunzătoare seturilor care conțin o variabilă fără semn de inversare formează o zonă de 2 n -1 celule. Această zonă se numește aria unei variabile date(de exemplu, domeniul de aplicare al variabilei x). Celulele rămase formează regiunea acestei variabile inverse. Seturile posibile de argumente sunt distribuite pe celule astfel încât limitele zonelor tuturor variabilelor și inversiunile acestora să fie clare, iar apartenența oricărei celule la o anumită zonă să fie ușor de identificat vizual.

1) Funcția unei variabile:

2) Funcția a două variabile:

3) Diagrama pentru disjuncție:

4) Diagrama pentru conjuncție:

5) Pentru trei argumente:

6) Pentru patru argumente:

Puteți minimiza o anumită expresie booleană prin grupare stând în apropiere unități și în același timp exclude variabila care trece de la starea directă la starea inversă. Puteți combina nu numai vertical și orizontal, ci și de-a lungul marginilor, deoarece, în general, harta Karnaugh formează un torus. Exemplu:

Algebre de logică

3.3.1. Minimizarea FAL folosind matricea Carnot

Matricea Carnot este un fel de tabel de adevăr FAL, care este împărțit în celule. Numărul de celule ale matricei este 2 n, Unde n– numărul de argumente FAL. Coloanele și rândurile unei matrice sunt desemnate prin seturi de argumente. Fiecare celulă a matricei corespunde unui constituent al unității FAL (număr binar). Numărul binar al unei celule constă dintr-un set de argumente de rând și coloană. Matricea Carnot pentru FAL, în funcție de două argumente, este prezentată sub forma tabelului 3.3., din trei argumente din tabelul 3.4. iar din patru argumente tabelul 3.5.

Tabelul 3.3.

Tabelul 3.5.

X 3 X 4 X 1 X 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Celulele matricelor (Tabelele 3.3., 3.4. și 3.5.) sunt numerotate cu echivalente zecimale ale numerelor binare ale celulelor. Celulele matricei adiacente, atât pe orizontală, cât și pe verticală, conțin numere binare adiacente. În plus, numerele binare adiacente se găsesc în toate coloanele rândurilor de sus și de jos, precum și în toate rândurile coloanelor cele mai exterioare.

Procesul de minimizare a FAL folosind matricea Carnot se bazează pe legea lipirii numerelor binare adiacente. Puteți lipi împreună numere binare ale celulelor adiacente, dar se recomandă să lipiți împreună seturi de argumente care indică rândurile și coloanele matricelor. Să luăm în considerare lipirea numerelor binare ale celulelor primei coloane a matricei (Tabelul 3.5.).

Celulele 0 și 4, numere binare 0000 și, respectiv, 0100, rezultatul lipirii este 0-00.

Celulele 8 și 12, numere binare 1000 și 1100, rezultat 1-00. Implicanții rezultați sunt lipiți împreună, deoarece Linia este în același loc și numerele binare implicante sunt adiacente, rezultatul final este - 00.

Celulele 8 și 12

Astfel, dacă toate numerele binare ale unei coloane sunt lipite împreună, atunci acei biți care indică rândurile dispar. În mod similar, dacă toate numerele binare ale unui rând sunt lipite împreună, de exemplu 4, 5, 7, 6, atunci toate cifrele care indică coloanele dispar, adică. rezultatul va fi următorul 01- -.

Dacă numerele binare ale oricăror două celule sunt lipite împreună, atunci este plasată o liniuță în locul acelei cifre a numerelor binare ale unui rând sau al unei coloane care se va schimba atunci când celulele se mută de la o linie la alta (sau de la o coloană la alta) . De exemplu, numerele celulelor 5 și 13 sunt lipite împreună, obținem rezultatul -101, sau celulele 7 și 6 rezultatul este 011-.

La lipirea numerelor binare a opt celule adiacente, trei variabile dispar, de exemplu, pentru celulele 3, 7, 15, 11, 2, 6, 14, 10, variabilele dispar X 1 , X 2 , X 3. Variabile X 1 , X 2 dispar pentru că toate celulele coloanelor sunt lipite între ele și X 3 deoarece ultimele două coloane sunt lipite între ele.

Înainte de a lua în considerare exemple de minimizare a FAL folosind matricea Carnot, este necesar să se clasifice seturile de argumente cu care sunt determinate funcțiile algebrei logicii.

Se știe că pentru fiecare FAL există 2 seturi de argumente n, Unde n– numărul de argumente de care depinde o funcție sau o expresie logică.

Seturile de argumente sunt împărțite în trei tipuri

1. Mulțimile de argumente pe care funcția este egală cu unu se numesc lucrătoare.

2. Se numesc interzise seturile de argumente pe care funcția este egală cu zero.

3. Setul de argumente pentru care o funcție poate fi egală fie cu unu, fie cu zero se numesc indiferente.

Dacă un FAL dat nu are mulțimi indiferente, atunci poate fi reprezentat în expresie literală sub forma SDNF. Dacă într-un FAL dat există mulțimi indiferente, reprezentarea acestuia poate avea următoarea formă.

unde sunt echivalente zecimale seturi de lucru,

– echivalente zecimale ale multimilor interzise.

Seturile de argumente care nu sunt printre cele funcționale și interzise vor fi indiferente.

Exemplul 3.3. Minimizați FAL-ul dat sub formă de SDNF folosind matricea Carnot.

Prin urmare, funcția este specificată numai de seturile de lucru. Restul va fi interzis. Funcția depinde doar de trei argumente. Construim o matrice Carnot și punem unele în celulele sale care corespund seturilor de lucru și punem zerouri în celulele rămase.

Tabelul 3.5.

X 2 X 3 X 1
	0

Pentru a minimiza, celulele matricei care le conțin sunt combinate în contururi. Circuitul poate include două celule, patru sau toate cele opt. ÎN în acest exemplu conturul include patru celule adiacente ale aceluiași rând. Implicantul conturului dat va fi 1 - -. Rezultatul minimizării este următorul, adică. a existat o reducere funcţie datăîn SDNF cu 11 litere.

Exemplul 3.4. Minimizați expresia booleană dată de seturile de lucru și interzise folosind matricea Carnot.

Construim o matrice Carnot pentru patru variabile și umplem celulele cu unu și, respectiv, zero, pentru seturile de lucru și interzise.

Tabelul 3.6.

X 3 X 4 X 1 X 2	00
		(1)

	(1)	(1)

Când se combină celule cu unități în contururi, este de dorit ca fiecare contur să includă cel mai mare număr celule de la maximum posibil. Pentru a face acest lucru, folosim celulele unor seturi indiferente ca celule de seturi de lucru, substituind în ele pe cele din paranteze. Ca rezultat, obținem trei contururi care conțin câte 4 celule fiecare. În codul de circuit generalizat, care include toate celulele unei linii, variabilele dispar X 2 X 3 (10 - -). În codul de circuit generalizat, care include toate celulele unei coloane, variabilele dispar X 1 X 2 (- - 11) și pentru un contur care conține două celule de două linii, variabilele dispar X 2 (la trecerea de la o linie la alta intr-un contur) si X 3 (la trecerea de la o coloană la alta). Ca rezultat, obținem DNF minim în urmatoarea forma

Opțiuni posibile combinația celulelor matricei Carnot în contururi este prezentată în Figura 3.4.

X 3 X 4 X 1 X 2

A = 0 - 0 -

Z = - 0 - 0

B = 1 - 1 -

K = - - - 1

B = - - 0 0

L = - 1 - -

Г = 1 0 - -

M = - - - 0

D = - 0 0 1

H = - 0 - -

E = - 0 1 -

F = - 1 - 1

Orez. 3.1. Opțiuni posibile pentru combinarea celulelor matricei Carnot în contururi

3.3.2. Minimizarea funcțiilor de algebră logică folosind o matrice de cinci variabile

Matricea de minimizare pentru cinci variabile este construită în mod similar cu matricea Carnot, i.e. în această matrice, coloanele și rândurile adiacente ar trebui să fie desemnate adiacente numere binare seturi de variabile

Într-o matrice cu cinci variabile (Tabelul 3.7.), rândurile corespund unor seturi de variabile X 1 X 2 X 3, iar coloanele sunt seturi de variabile X 4 X 5 . Fiecare celulă a matricei corespunde unui număr binar de cinci biți. Celulele matricei (Tabelul 3.7.) conțin echivalentele zecimale ale numerelor binare corespunzătoare.

Tabelul 3.7.

X 4 X 5 X 1 X 2 X 3

Minimizarea FAL folosind o matrice de cinci variabile constă în combinarea celulelor cu seturi de lucru (inclusiv, dacă este necesar, celule cu seturi indiferente) în contururi și obținerea de coduri generalizate corespunzătoare acestor contururi.

Particularitatea aici este că, în coloanele unei matrice de cinci variabile, puteți combina patru celule numai în contururi, sau patru celule în partea de sus, sau patru celule în jos sau patru celule în mijloc. De exemplu, pentru ultima coloană a matricei, contururile pot consta din celule 2, 6, 14, 10 sau 26, 30, 22, 18 sau 14, 10, 26, 30.

Exemplul 3.6. Utilizați o matrice cu cinci variabile pentru a minimiza următoarea expresie logică

Construim o matrice de cinci variabile și umplem celulele mulțimilor de lucru cu unu, iar celulele mulțimilor interzise cu zerouri.

Combinăm celulele cu seturi de lucru în contururi, inclusiv celulele necesare de seturi indiferente. Pentru fiecare circuit definim un cod generalizat.

Tabelul 3.8.

X 4 X 5 X 1 X 2 X 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Primim DNF minim

Întrebări de control

1. Definiți DNF prescurtat.

2. Ce este un DNF fără margini?

3. Cum este selectat DNF-ul minim dintre DNF-urile fără margini?

4. Pentru ce este folosit tabelul implicant și cum este construit?

5. Explicați metoda analitică pentru minimizarea FAL Quine-McClassky.

6. Cum se construiește matricea Carnot pentru trei și patru variabile?

7. Minimizați analitic următoarele expresii logice date numai de seturile de lucru

8. Folosind matricea Carnaugh, minimizați expresiile logice specificate de seturile de lucru și interzise

Informații conexe.

La proiectarea automatelor digitale, metodele de minimizare a funcțiilor booleene sunt utilizate pe scară largă pentru a obține circuite rentabile. Sarcina generală minimizarea funcțiilor booleene poate fi formulată după cum urmează: găsiți o expresie analitică pentru o funcție booleană dată într-o formă care conține numărul minim posibil de litere.

Metodele de minimizare se bazează pe operația de lipire (un algoritm pentru combinarea numerelor binare adiacente):

unde A este o conjuncție elementară.

În expresie, termenii sunt numere binare adiacente care diferă unul de celălalt doar printr-o cifră. La efectuarea unei operații de lipire pe două numere adiacente, o variabilă este exclusă din set, care distinge un număr de altul, pe patru numere adiacente perechi - două variabile, pe opt - trei variabile etc.

Forma normală disjunctivă minimă (MDNF) a unei funcții booleene este DNF care conține cel mai mic număr de litere (față de toate celelalte DNF-uri care reprezintă o funcție booleană dată).

Puteți minimiza funcțiile, adică găsiți cea mai simplă expresie pentru funcția originală diverse metode. Toate diferă practic doar în prima etapă - etapa obținerii DNF prescurtat. De menționat că, din păcate, căutarea MDNF este întotdeauna asociată cu o anumită căutare de soluții. Să ne uităm la unele dintre ele.

Minimizarea expresiilor booleene complexe folosind matricea Carnot

Pentru a implementa algoritmul de fuziune, este necesar să se găsească învecinați din întregul set de constituenți obligatorii în forma normală disjunctivă perfectă a unei funcții algebrică logică. Pentru a găsi constituenți învecinați, sunt utilizate matrice Carnot, o rețea de numere învecinate și tabele de constituenți învecinați.

Este recomandabil să folosiți matrice Carnot pentru a minimiza FAL pe seturi de 2,3,4,5 și 6 variabile. Numerele coloanelor din matricele Carnot formează cifrele cele mai puțin semnificative, iar numerele de rând formează cifrele cele mai semnificative ale mulțimilor. Numerele celulelor sunt alcătuite din numere de rând și coloane și corespund unor seturi de variabile.

Să luăm în considerare matricea Carnot pentru o funcție de algebră logică pe seturi de 4 variabile (Tabelul 1).

Tabelul 1. Matricea Carnot

Coloanele și rândurile din această matrice sunt desemnate prin numere binare adiacente: 00-0I-II-I0. Prin urmare, numerele de celule adiacente orizontal și vertical, precum și celulele cele mai exterioare din rânduri și coloane, sunt numere adiacente, de exemplu:

celule cu numere și;

celule cu numere;

celule cu numere.

Pentru a minimiza o funcție de algebră logică specificată în formă normală disjunctivă perfectă folosind matricea Carnot, este necesar să: pregătiți matricea Carnot prin scrierea de unități în celulele corespunzătoare constituenților obligatorii, combinați celulele cu unitățile în „subcuburi”, scrieți cele minimizate. funcția algebrică logică în formă normală disjunctivă.

„Subcuburile” se combină:

- două celule cu numere care sunt numere adiacente, în timp ce o variabilă este exclusă;
- patru celule (rând, coloană, pătrat, celule de colț), în timp ce două variabile sunt excluse;
- opt celule (două rânduri (coloane) adiacente sau extreme), cu trei variabile excluse.

Este posibil să se ofere o excepție Mai mult variabile, dimensiunile „subcuburilor” ar trebui să fie cât mai mari posibil și numărul acestora cât mai puțin posibil. În acest scop, puteți utiliza aceeași celulă cu o unitate de mai multe ori, incluzând-o în diferite „subcuburi”. Numărul de termeni dintr-o funcție de algebră logică minimizată este egal cu numărul de subcuburi și celule cu unități care nu sunt combinate în subcuburi.

Să fie necesar să se minimizeze următoarea funcție de algebră logică:

Matricea Carnot, completată conform acestei formule, poate fi prezentată sub forma tabelului 2:

Tabelul 2. Matricea Carnot

În această matrice, se pot distinge două subcuburi cu două celule. Ca rezultat al minimizării, se va obține următoarea funcție de algebră logică:

metoda lui Quine

Pentru a obține forma minimă a unei funcții logice, este necesar să se efectueze toate lipirea și absorbția posibile în forma normală disjunctivă perfectă a funcției (SDNF), astfel încât rezultatul să fie un disjunctiv redus. forma normala funcții. (DNF) DNF redus în cazul general poate conține implicanți primari suplimentari, care trebuie identificați în a doua etapă de minimizare.

În prima etapă, se face o tranziție de la o funcție specificată sub formă de DNF la un DNF redus. Esența metodei este de a efectua secvenţial toate lipirile posibile și apoi toate absorbțiile, ceea ce duce la un DNF redus. Metoda este aplicabilă DNF perfect. Din relația de absorbție rezultă că un produs elementar arbitrar este absorbit de orice parte a acestuia. Pentru a o demonstra, este suficient să arătăm că un implicant prim arbitrar p = x i1 X i2... X în pot fi primite. Într-adevăr, aplicând operația de extindere ( operare inversă lipire):

pentru toate variabilele lipsă x ik , ..., x Sunt funcția originală f, obținem mulțimea S de constituenți ai unității. Prin lipirea tuturor constituenților din S obținem implicantul p. Aceasta din urmă este evidentă, deoarece operația de lipire este inversa operației de desfășurare. Mulțimea S de constituenți este în mod necesar prezentă într-un DNF perfect al unei funcții f, deoarece p este implicantul acesteia.

Ca rezultat al lipirii, se obține o conjuncție de rang n-1, iar conjuncțiile rămân în expresia originală și participă în comparație cu alți membri ai SDNF. Astfel, este posibil să se reducă rangul termenilor.

Lipirea și absorbția sunt efectuate atâta timp cât există membri care nu au participat la comparația pe perechi. Sunt marcați termenii care au suferit operația de lipire. Termenii nemarcați sunt implicanți principali și sunt incluși în DNF abreviat. Toate conjuncțiile marcate de rang n-1 sunt din nou supuse operației de lipire până la obținerea termenilor de rang n-2 și așa mai departe până când numărul de conjuncții nemarcate este mai mare de 2. Ca urmare a primei etape, un DNF redus este obținut.

Expresia logică rezultată nu este întotdeauna minimă. În cea de-a doua etapă, ei trec de la DNF redus la DNF-uri fără fund și selectează MDNF printre ele.

Pentru a forma DNF-uri fără margini, se construiește un tabel implicant (matrice), ale cărui rânduri sunt marcate cu implicanții simpli ai DNF abreviat, iar coloanele cu constituenții unității SDNF-ului original. În linia opusă fiecărui implicant simplu, sub acele mulțimi (constituenți ai unității) se pune un semn pe care ia valoarea 1. Constituenții corespunzători sunt absorbiți (acoperiți) de acest implicant simplu.

Din numărul total implicanții primi trebuie să își aleagă numărul minim, eliminându-i pe cei suplimentari. Formarea formelor de fund și selectarea acoperirii minime începe cu identificarea implicanților primi obligatorii, adică a celor care (și numai aceștia) acoperă un set inițial. Să ne uităm la exemplul de minimizare a unei funcții logice:

f SDNF = V (1,2,5,6,7)=x 1 X 2 X 3 +x 1 X 2 X 3 +x 1 X 2 X 3 +x 1 X 2 X 3 +x 1 X 2 X 3

1 2 3 4 5

Să efectuăm operația de lipire:

1 - 3 (x 1 )X 2 X 3 1
2 - 4 (X 1 )X 2 X 3 2
3 - 5 (x 2 )X 1 X 3 3
4 - 5 (x 3 )X 1 X 2 4

Ca rezultat al primului pas de lipire, obținem patru noi conjuncții; nu au fost identificați implicați simpli. Conjuncțiile rezultate nu se mai lipesc și formează un DNF scurtat.

f abbr SDNF =x 2 X 3 +x 2 X 3 +x 1 X 3 +x 1 X 2

Pentru a identifica implicanții simpli obligatorii și pentru a formula acoperirea minimă pe baza acestora, se construiește un tabel de implicante (Tabelul 3). Implicanții simpli sunt scrieți în rândurile tabelului de implicante, iar constituenții unității sunt scriși în coloane. Este dat un asterisc dacă implicantul prim acoperă constituentul.

Tabelul 3. Tabelul implicat

x 1 x 2 x3	X 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3

Implicanții primi sunt obligatorii, deoarece numai aceștia acoperă constituenții și sunt incluse în acoperirea minimă. Rămâne un constituent neacoperit x 1 X 2 X 3 care poate fi acoperit de unul dintre cei doi implicanți primi rămași. Acest lucru are ca rezultat două forme de fund.

metoda Blake-Poretsky

Metoda permite obținerea unui DNF redus al unei funcții booleene f din DNF-ul său arbitrar. Pe baza aplicării formulei generalizate de lipire:

a cărui validitate este ușor de dovedit. Într-adevăr,

Prin urmare,

Metoda se bazează pe următoarea afirmație: dacă într-un DNF arbitrar al unei funcții booleene f realizăm toate lipirile generalizate posibile și apoi efectuăm toate absorbțiile, atunci rezultatul este un DNF redus al funcției f.

Să ne uităm la un exemplu. Fie o funcție booleană f dată de un DNF arbitrar.

Este necesar să se obțină un DNF scurtat al funcției f folosind metoda Blake-Poretsky. Executăm lipire generală. Este ușor de observat că primul și al doilea element ale DNF original admit lipirea generalizată în raport cu variabila x 1 . Ca rezultat al lipirii obținem:

Primul și al treilea element din DNF original admit lipirea generalizată atât în ceea ce privește variabila x 1 cât și x 2 . După lipirea de-a lungul x 1 avem:

După lipirea de-a lungul x 2 avem:

Al doilea și al treilea element al DNF admit lipirea generalizată în raport cu variabila x 2 . După lipire obținem:

După ce am efectuat ultima lipire generalizată, ajungem la DNF:

După efectuarea absorbțiilor obținem:

Încercările de a aplica în continuare operația de lipire și absorbție generalizate nu dau rezultate. În consecință, se obține un DNF redus al funcției f. În continuare, problema găsirii unui DNF minim este rezolvată folosind o matrice implicantă exact în același mod ca în metoda lui Quine.

Minimizarea FAL incomplet definite

Dacă în timpul sintezei circuit logic, implementând unele FAL de n variabile, rezultă că unele seturi din numărul total 2 n nu poate apărea niciodată la intrările circuitului, atunci această funcție logică nu este definită pe aceste seturi. Apoi 2 n seturile de variabile pot fi împărțite în trei grupe: mulțimi pe care funcția ia o singură valoare L, valoare nulă D și un grup de mulțimi pe care funcția nu este definită N (mulțimi nedefinite). Un FAL care conține seturi nedefinite se numește definit incomplet sau parțial. Seturile nedefinite pot fi folosite pentru a îmbunătăți calitatea minimizării. În acest caz, mulțimile incerte (atunci când sunt minimizate, de exemplu, de hărți Veitch, Carnaugh) pot participa la formarea contururilor atât cu seturi de unități, cât și cu zero. Acest lucru are ca rezultat formarea unei funcții logice minimizate mai simple.

O metodă universală de minimizare este utilizarea legilor și relațiilor algebrei logice, care permit minimizarea FAL pentru orice număr de variabile.