Imath wiki - minimizarea funcțiilor booleene

Este clar că proiectarea de circuite logice, de nu de mică importanță este problema reducerii la minimum a numărului de elemente utilizate (cu alte cuvinte, operațiile logice).

În acest sens, există o problemă de minimizare a funcțiilor logice într-o clasă de formule. În special, clasele DNF si CNF.

Acest minim DNF DNF, care are cel mai mic număr total de apariții de variabile, în comparație cu toate echivalează cu DNF ei. Acest minim CNF CNF, care are cel mai mic număr total de apariții de variabile, în comparație cu toate CNF echivalent cu acesta.

Procesul de a găsi forme minime, de fapt, se numește minimizarea. În cazuri simple, suficient pentru a minimiza transformări identitare. În mai complexe - folosind algoritmi speciali.

Metoda de bază de minimizare funcții logice reprezentate ca PDNF SKNF sau este incomplet pairwise operație de lipire și absorbția elementară. Operația de lipire pereche are loc între cei doi termeni care conțin aceleași variabile care de intrare (cu și fără negație) sunt aceleași pentru toate variabilele, cu excepția uneia. În acest caz, toate variabilele, cu excepția unuia, pot fi scoase din paranteze, cu suporturile rămase în apariție directă și inversă a unui subiect de lipire variabilă. De exemplu:

În mod similar, pentru CNF:

Posibilitatea de absorbție rezultă din egalitatea evidentă

Astfel, principala sarcină în timp ce minimizarea PDNF și SKNF este de a găsi membri potrivit pentru lipirea cu absorbția ulterioară a acestei forme de mari pot fi destul de o provocare.

Metoda grafică pentru minimizarea funcțiilor booleene. Este o îmbinare incompletă operațiune Pairwise și absorbție elementar. hărți Karnaugh sunt considerate ca fiind construite în mod corespunzător funcția de tabelă de adevăr.

hărți Karnaugh poate fi privit ca un plan alezor n-dimensional cub boolean specifice.

Karnaugh hartă a fost inventat în 1952 de către Edward W. Veitch și îmbunătățit în 1953 Morisom Karno, un fizician de la «Bell Labs», și au fost concepute pentru a ajuta la simplificarea circuitele digitale.

Cele Karnaugh harta Variabilele booleene sunt transmise din tabelul de adevăr și aranjate cu ajutorul unui cod Gray, în care fiecare număr succesive diferă de cel precedent doar un singur bit.

Funcții booleene \ (N \) variabilele prezentate sub formă de PDNF SKNF sau poate fi compus din \ (2 ^ N \) diferiți membri elementare.

Membrii Elementare formă sau structură PDNF SKNF este topologic \ echivalent (N \) cub -dimensional. Într-adevăr, dacă luăm în considerare setul de valori ale funcției \ (x_1, \, \ ldots, \, x_N \) ca \ (N \) dimensional vector \ (\\). obținem un set de puncte pe versorii \ (N \), sistem de coordonate -dimensional, și la distanță unul față de celălalt \ (1 \). Cu alte cuvinte, obținem \ (N \) hipercub dimensionale cu margine \ (1 \).

De exemplu, pentru o funcție de două variabile definite de tabelul de adevăr:

puteți construi un pătrat echivalent:

01 1 11 0 0 00 1 10

Sau, dacă vom nota nodurile conjuncțiilor respective și de a evidenția noduri elementare, care sunt în conjuncție PDNF:

X̅₁x₂ x₁x₂ 0 1 0 1 x̅₁x̅₂ x₁x̅₂

X₁∨x̅₂ x̅₁∨x̅₂ 0 1 0 1 x₁∨x₂ x̅₁∨x₂

Se poate remarca faptul că membrii care sunt pe de o parte a pieței poate fi lipit. Prin urmare, în cazul în care se face DNP, operația este realizată numai pe vârfuri, în care funcția este setată la \ (1 \) (în conformitate cu regulile de construcție PDNF). Dacă preparați CNF, apoi peste vârfurile, în care funcția este setată la \ (0 \) (în conformitate cu regulile de construcție SKNF).

Astfel, variabilele sunt stocate, o valoare pe partea care este în mod constant.

În cazul unei funcții de trei variabile trebuie să se confrunte cu cub tridimensional. Este mai complicat și mai puțin transparentă, dar este posibil punct de vedere tehnic. Figura prezintă un exemplu al unui tabel de adevăr pentru o funcție booleană de trei variabile și cubul corespunzător.

După cum se vede din figură, cazul tridimensional pentru mai multe configurații complexe sunt posibile. De exemplu, patru membri care aparțin o față a cubului, sunt unite într-una cu absorbția a două variabile:

În general, putem spune că \ (2 ^ K \) membri care aparțin aceluiași \ (K \) hipercubului -face, lipit de un membru, cu variabilele absorbite \ (K \).

Karnaugh harta este o scanare a unui hipercub pe un plan. De exemplu, un cub tridimensional din exemplul anterior poate fi desfășurat după cum urmează:

X̅₁x̅₂x̅₃ x̅₁x̅₂x₃ 1 1 0 0 x̅₁x₂x̅₃ x̅₁x₂x₃ x₁x₂x₃ 0 0 1 x₁x₂x̅₃ x₁x̅₂x₃ 1 x₁x̅₂x̅₃

Karnaugh harta este o reprezentare a unei scanări bidimensională sub forma unui tabel.

În acest caz, toate celulele extreme sunt adiacente unul cu altul. Acesta poate fi imaginat, trăgând matura la pilier ( „gogoasa“):

De asemenea, este posibil să se construiască diagrame pentru funcțiile Carnot 5 și 6 variabile, dar care lucrează cu ei se face în mod semnificativ dificilă. Pentru un număr de variabile, mai mult de 6, utilizarea de hărți ale Carnot pur și simplu impracticabile.

Luați în considerare funcția având următorul tabel de adevăr:

\ (F (x_1, x_2, x_3, x_4) \)

Rescrie acest tabel ca o hartă Karnaugh:

Ușor împărțit în trei grupe. Prin urmare, DNP înregistrat:

Metoda Quine-MakKlassi se bazează pe aceeași mașină ca și harta Karnaugh, dar este mai practic pentru un număr mai mare de variabile.

Algoritmul este încleiere consecvent, iar apoi rezultatul reducerii.

În primul rând, membrii de bază ai forma perfectă este scris în formă binară la o masă, în cazul în care sunt grupate în funcție de numărul de unități.

Apoi, membrii care diferă într-o singură variabilă (un bit), pot fi lipite. În acest caz, unitatea se înlocuiește cu „-“. Evident, care pot fi lipite numai membrii grupurilor vecine

Membrii care nu se pot lipi împreună, indicate printr-un asterisc „*“.

Rezultante membrii legați pot, la rândul lor, de asemenea, să fie lipite. În acest caz, „-“ este interpretată ca valoare „a treia“.

Atunci când nici un membru nu mai poate fi legat, de membrii marcate cu „*“, forma scurtă se face. care nu este neapărat minimă. Aceasta este urmată de o reducere.

Pentru reducerea, un tabel în care rândurile incluse membrii ai forma redusă, și în coloanele - membri perfecte.

Celulele pune un marcaj (de exemplu, o cruce „x“), în cazul în care termenul corespunzător al formei reduse a elementului corespunzător absoarbe forma perfectă (adică, în cazul în antetul rândului face parte din titlul coloanei).

coloanele selectate care conțin doar un singur „ד. Sootvetsvtuyuschie membrii lor constituie nucleul formei reduse. și ar trebui să intre într-o formă minimă.

În cazul în care nucleul nu acoperă toate coloanele într-o formă minimă, deoarece a inclus mai mulți membri ai forma redusă de non-core, astfel încât membrii formează minime se suprapun toate coloanele din tabel.

Găsiți forma minimă a funcției