Dns redus și minim

DNF abreviat (forma normală disjunctivă engleză) este o formă de înregistrare a funcției cu următoarele proprietăți:

oricare doi termeni diferă în cel puțin două poziții,
nici unul dintre conjuncturi nu este conținut în celălalt.

De exemplu: este conținut în.

Funcția poate fi scrisă cu DNP abreviat, și nu numai.

Vom scrie funcția (mediană) sub forma unui DNF perfect. . Se știe că această expresie este echivalentă cu următoarea :. Înfăptuiește în fiecare suport comun conjuncte (de exemplu, în primul. De atunci conjunct nu afectează valoarea expresiei, și poate fi omisă. Obține în cele din urmă o formulă.

[edit] DNP minim

DNF minimă (forma normală disjunctivă minimă în engleză) este un DNF abreviat care conține numărul minim de apariții de variabile.

Fiecare minim DNF este abreviat, dar nu fiecare abreviat este minim. De exemplu, înregistrarea este DNF minimă pentru mediană (se scurtează, așa cum se vede în exemplul de mai sus); iar înregistrarea nu este un DNF minimal dar abreviat.

[edit] Minificarea DNF

Luați în considerare mai multe moduri de a minimiza formele disjunctive normale:

[edit] Vizualizarea cu hipercuburi

Această metodă funcționează cu numărul de variabile care nu depășesc trei (altfel trebuie să introduceți a patra sau următoarele măsurători pentru a reprezenta cifrele). În primul rând, tragem un cub în cadrul de referință (numele axelor de coordonate corespund numelor variabilelor). Apoi procesăm fiecare vertex după cum urmează:

Dacă avem un conjunct, ale cărui variabile sunt egale cu coordonatele corespondente ale vârfului, atunci vom pune acest cerc umplut cu un cerc negru.

Un vertex cu coordonate corespunde unui conjunct, este egal cu unitatea pentru u)

În caz contrar, plasăm un cerc alb în partea superioară.

Pentru un astfel de DNF: obținem următorul hypercube (vezi figura)

Apoi, hypercube-ul este procesat după cum urmează:

în timp ce avem de top neumplute, vom alege fata sau vârful, sau marginea, pe care cele mai multe topuri negre pictate și nu au fost încă procesate nodurile.

În cazul în care acest lucru hipercub este o fata, toate nodurile care sunt vopsite negru, atunci putem scrie ca o conjunctie, care va doar variabilă invariabilă Coordonata corespunzătoare acesteia.

Fața pe care se găsesc vârfurile pictate și o putem scrie în conjuncție.

Acum ne uităm dacă topurile care au fost pictate și care nu au fost marcate de noi în DNF au rămas pe marginea cubului. Dacă - da, atunci putem scrie marginile cu astfel de noduri ca conjunct, unde vor exista doar variabile cu coordonate invariabile corespunzătoare

Marginea care leagă vârfurile umplute și o putem scrie în conjuncție.

Și dacă după o astfel de procesare avem noduri libere, pur și simplu rescriem coordonatele fiecărui vertex într-un conjunct separat, egal cu.

Vom rescrie vârful ca conjunct.

Ca rezultat, DNF-ul nostru original poate fi scris ca.

[edit] Hărți ale Carnot

Să construim următorul tabel, unde este numărul de variabile:

Acum, acoperă casetele (lungimea laturilor de care - o putere de două ()) sunt Karnaugh hărți celulele care conțin unitatea (fiecare rândul său, vom alege un dreptunghi pentru a acoperi cel mai mare număr de care nu sunt încă acoperite de celule), atâta timp cât acesta va acoperi toate astfel de celule.

Pentru hărțile Carnot, de exemplu, ar arăta astfel:

Atât conexiunile elementare la acest pas sunt elemente ale DNF abreviat.

Ca urmare a algoritmului, obținem următoarea DNF abreviată:

Tranziția de la formularul abreviat la minim:

Unități DNF acoperite cu elemente sau marcate cu "+". Perechile și, care intră în kernel, sunt marcate cu "*".
Unitățile funcției, care sunt acoperite doar de un conjunct din sistemul de elemente ale DNP abreviat, sunt marcate cu ">".
Unitățile funcției acoperite de kernel, dar care nu sunt acoperite de un singur conjunct din sistemul de elemente ale unui DNF scurtat, sunt marcate cu ">>".

Articole similare

Pagina anterioară