Introducere în teoria automatelor digitale, reducerea la minimum a expresiilor algebrei booleene

Simplificarea boolean expresii funcționează atunci când proiectarea dispozitivelor de informare se face pentru a reduce cantitatea de echipamente necesare pentru punerea în aplicare a acestor funcții.

Forma preferată a expresiei rezultată este DNF, care a fost prezentat în secțiunea anterioară, este mai ușor decât cnf. De asemenea, sa demonstrat că DNP are o prezentare grafică convenabilă și DNP trecere de la baza tehnică a „AND-NU“ este foarte ușor.

DNF este numit minim. în cazul în care conține cel mai mic număr de litere, în comparație cu alte expresii echivalente, cum ar fi DNF. Sub „litera“ înseamnă fiecare apariție a argumentului în formula. De exemplu, expresia este format din opt litere, la toate cele trei argumente.

problema Minimalizarea dat formula logică poate fi rezolvată, în principiu, prin mijloace convenționale de algebrei booleene prin simplificarea treptată a acestei formule, folosind în principal operațiile de absorbție și de lipire. De exemplu:

DNF rezultat mai simplificat prin lipire și de absorbție, dar există un truc pentru a simplifica și mai mult:

Ultima expresie este DNF minimă, iar rezultatul intermediar nu se pretează la simplificare prin lipire și de absorbție se numește impas DNF.

Această modalitate de a minimaliza ineficiente. Este aproape imposibil să se demonstreze că formula simplificată rezultată este foarte minimă, și nu doar o fundătură. Prin urmare, minimizând operează una dintre metodele specifice, mai mult sau mai puțin formale care să garanteze obținerea minim DNF.

Toate aceste metode se bazează pe conceptul: implicants și implicants prime.

Dacă g = 1, atunci f neapărat = 1. Condiția inversă nu este atribuit. Unități de implicants ca unități aparțin funcției set f. De aici și numele implicants (implicire Latină -. Intră în ceva, se implica). De aceea se întâmplă, și numele funcției „implicare“.

Luați în considerare funcțiile de tabelă de adevăr din exemplul de mai sus și arată în același tabel oarecum implicants arbitrar selectate ale acestei funcții (Tabel. 2.6).

implicants Prime numit o astfel de funcție implicant dată, care este conjuncția unui număr de litere, și prin renunțarea la unele litere nu a primit expresia, care este, de asemenea, un implicant.

Unele implicants ale unei funcții booleene f (a, b, c)

In exemplul nostru simplu este doar implicant g 4 = a. Implicants g 1 și g 3 nu sunt conjuncții, și g 2 - nu este simplu, pentru că atunci când acesta se transformă într-o altă cădere, neidentificat ne implicant.

Ideea generală a metodelor formale de minimizare a expresiilor booleene este de a găsi un set minim de implicants prime pe care unitățile lor ar acoperi întregul set de unități ale unei funcții date. Găsirea unui set de implicants, este posibil să ne imaginăm o funcție dată ca o disjuncție

Metodele formale de minimalizare include următoarele etape de lucru executate succesiv:

a) reprezentare adecvată a datelor inițiale;

b) identificarea prim implicants;

c) implicants de reducere setat la minimul necesar;

g) a găsit forma minimă de prezentare conform cerințelor pentru lucrări suplimentare.

Când minimizarea printr-o reprezentare algebrică program de calculator a funcției original este înlocuit cu o intrare sub forma unui complex cub. O astfel de înregistrare poate fi utilizat și în unele algoritmi relativ simple (de exemplu - algoritmul Quine-McCluskey) destinat pentru a efectua manual.

Ne doar cunoștință cu una dintre metodele formale, cea mai simplă și limita sa concentrat exclusiv pe executie manuala. Metoda propusă în 1953 M. Carnot (M. Karnaugh) și se numește metoda hărților Karnaugh.

Karnaugh harta - a transformat tabelul de adevăr al unei funcții booleene, care conține celule 2n, unde n - numărul de argumente funcționale. Astfel, fiecare dintre seturile de valori ale argumentului corespunde o carte de celule, iar aceste celule se potrivesc zerouri sau cele, care reprezintă valorile funcției pe acest set.

Desemnări argumente luate în afara marginea hărții, dar principala diferență din tabelul de adevăr de obicei nu este cazul, și că poziția relativă a cardului este aliniat cu celulele nodurilor unitate de cub. Putem spune că carte Carnot este scanat pe planul n-dimensional unitate de cub. Prin urmare, celulele adiacente corespund carduri adiacente 0-cuburi, iar operația de lipire devine o reprezentare vizuală a modului în care celulele de asociere carte de operare.

Fig. 2.4 prezintă trei moduri de a face referire la argumentele de marginile cardului pentru funcția de două argumente.

Fig. 2.4. Modalități de desemnare a unui argumente funcției booleene

Alfabetice, cu denumiri grafice numerice și condiționale sunt moduri acceptabile la fel, dar un număr tot mai mare de argumente, sunt preferate în mod condiționat grafic ca cel mai compact.

Frame alocat unității joinable la efectuarea operației de lipire.

Fig. 2.5 Diagrama Veitch care prezintă funcțiile de trei argumente. Aceste carduri trebuie considerate ca o scanare tridimensională a cubului, adică Acesta trebuie să fie considerate ca fiind conectate între ele drept și marginea hărții la stânga.

Fig. 2.5. diagrame Veitch

Figura arată modul în care se pot combina celule pentru a efectua lipirea. Este evident faptul că aceeași unitate poate participa (dacă este necesar) într-un timp de lipire.

Atunci când un anumit număr de argumente n și m număr combinat cunoscut de celule este determinată cu ușurință de numărul de litere în l conjuncția rezultat (implicants prime): L = n - log2 m.

Se poate combina 2, 4, 8, și, în general, m = celule 2k, unde k £ m - un număr întreg egal cu numărul de coordonate în rezultat liber k cub -dimensional. Atunci când legătura nu se produce, adică, cu celula unitate este izolată, m = 1, k = 0, iar dacă toate cărțile sunt celulele lipite (acest lucru este posibil numai pentru „constanta 1“ funcția), atunci m = 2n; k = n și minimă FND nu conține nici o literă.

Karnaugh harta (Veitch și diagrame) sunt convenabile și pot fi utilizate în locul tabelelor de adevăr obișnuite în rezolvarea oricăror probleme practice, desigur, fără prea multe argumente pentru a funcționa.

Acoperirea cardului de zero, în loc de unități, vom obține o DNF minimă pentru inversarea unei funcții date.

Carduri de umplere Carnot nu impune desfășurarea unei anumite funcții indispensabile în PDNF ca la o anumită abilitate puteți completa cardul direct pe DNF formei arbitrare.

Fig. 2.6 este o diagramă Veitch umplut de expresia Þ .

Fig. 2.6. Diagrama Veitch pentru

Singurul dezavantaj al hărților Karnaugh este complexitatea lor rapidă în timp ce creșterea numărului de argumente. După numărul de celule este dublat atunci când numărul de argumente de către unul.

Un rol deosebit în procesul de minimizare a formulelor logice juca funcții parțiale - funcții booleene, determinarea suprafață este mai mică decât multitudinea completă de seturi de valori de n argumente. Tabelul de adevăr al funcției parțiale, în unele celule conțin liniuþe indicând faptul că setul de date de valoare funcție nu este definită (tabelul 2.7.).

EXEMPLU Funcția de tabelă de adevăr parțială

Funcții parțiale oferă oportunități suplimentare pentru minimizarea, astfel încât sinteza logică a dispozitivelor digitale încearcă să folosească fiecare ocazie pentru a reprezenta funcțiile utilizate sub forma funcțiilor parțiale. În acest scop, din următoarele motive pot fi implicate:

a) seturi irealizabil. De exemplu, când codificarea cifre zecimale binare tetradelor nu pot utiliza șase caiete de șaisprezece. În viitor, în cazul în care există încredere în imposibilitatea apariției unor seturi nevândute pot fi considerate indiferente la valoarea corespunzătoare a funcției;

b) seturi invalide. Există dispozitive care nu pot funcționa corect în anumite combinații de semnale de intrare. sursa de semnal în timp ce nu ar trebui să creeze astfel de combinații. Practic, aceasta înseamnă aceeași situație ca și în revendicări. "A";

c) indiferent literalmente valorile unora dintre seturile, în timp ce toate aceste seturi pot fi realizate (nou instalarea opțională sau resetare etc.).

Oricare dintre aceste baze pot fi folosite pentru a anunța unor seturi de valori ale argumentelor interzise. și valorile unităților opționale sau zerouri opționale corespunzătoare.

După ce a început să ia în considerare această funcție pe întregul interval de valori de argument (adică includ convențional domeniul seturilor interzise).

Această soluție vă permite să descrie funcția unei formule, cum ar fi PDNF concluzionând componentelor interzise în paranteze. Pentru arătate în tabelul. 2.7 Funcția acestor formule:

În prima formulă inclus în paranteze sunt unitatea opțională a funcției f. iar al doilea - opțional la zero sau, echivalent, o funcție inversă a unității.

Principalul lucru, cu toate acestea, nu este cazul, și prin aceea că, minimizarea poate redefini în mod arbitrar funcția, selectarea unor astfel de valori pe kituri sale interzise, ​​care permit acoperirea pentru a produce cele mai bune.

Deoarece determinarea funcției parțiale cele mai bune acoperiri încetează să mai existe, iar minim DNP găsit, și pe care se bazează circuitul logic este definit peste tot.

Atunci când se utilizează diagrame Veitch (cartografiere Carnot) problema pentru determinarea celei mai bune funcții parțiale de acoperire este ușor de rezolvat. Fig. 2.7 prezintă o diagramă pentru funcția filei. 2.7.

Fig. 2.7. Veitch grafic pentru f (a, b, c), o masă predeterminată. 2.7

elemente harta Localizare arată că trebuie să punem funcția egală cu unitatea pe platoul de filmare de 110 la zero și - la celelalte trei seturi interzise. Ca rezultat, funcția primește expresie foarte simplu.

În tehnicile formale, orientate spre mașină problema este rezolvata completari optime mult mai complicat.