Minimizarea funcțiilor logice prin metoda Quine
Metoda Quine este o modalitate de a reprezenta o funcție într-un DNP sau CNF cu un număr minim de termeni și un set minim de variabile. [1] [2] [3]
Transformarea funcției poate fi împărțită în două etape:
- în prima etapă, o tranziție de la forma canonică (SDNF sau SKNF) la așa-numita formă abreviată;
- în a doua etapă - trecerea de la o formă redusă la o formă minimă.
Prima etapă (obținerea unei forme reduse)
Să ne imaginăm că funcția dată este reprezentată în SDNF. Pentru prima etapă, transformarea are două etape:
Operația de lipire este redusă la găsirea perechilor de termeni corespunzători formei și transformându-i în următoarele expresii :. Rezultatele lipirii au acum rolul de termeni suplimentari.
Apoi se efectuează o operație de absorbție. Se bazează pe egalitate (termenul absoarbe expresia). Ca o consecință a acestei acțiuni, toți termenii absorbiți de alte variabile sunt șterse din expresia logică, ale cărei rezultate sunt obținute în operația de lipire.
Ambele operații din prima etapă pot fi efectuate atâta timp cât se poate face acest lucru.
Aplicarea acestor operațiuni este prezentată în tabel:
Rezultatul operației de lipire este necesar pentru a transforma funcția în a doua etapă (absorbție)
Membrii rezultatului lipirii sunt
Un membru absoarbe acei membri ai expresiei originale care conțin, adică primul și al patrulea. Acești membri sunt șterși. Termenul absoarbe a doua și a treia, iar termenul este al cincilea termen al expresiei originale.
Repetarea ambelor operații conduce la următoarea expresie:
Aici o pereche de termeni sunt lipiți împreună și (prin lipirea împreună a unei perechi de termeni și rezultate în același rezultat), rezultatul lipirii absoarbe termenii 2-, 3-, 4- și 5 ai expresiei. Continuarea operațiunilor de lipire și absorbție este imposibilă, forma redusă a expresiei pentru o funcție dată (în acest caz coincide cu forma minimă)
Diagrama blocurilor de funcții
Membrii formularului abreviat (în cazul nostru, acest lucru este) se numesc implicați simpli ai funcției. În cele din urmă, avem cea mai simplă expresie, dacă o comparăm cu versiunea inițială - CDNF. Diagrama structurală a unui astfel de element este prezentată în figura din dreapta.
A doua etapă (obținerea formei minime)
Ca și în prima etapă, egalitatea rezultată poate conține membri ai căror eliminare nu va afecta în nici un fel rezultatul final. Următoarea etapă de minimizare este eliminarea unor astfel de variabile. Tabelul de mai jos conține valorile adevărului funcției, următorul CDNF va fi colectat de la acesta.
PDNF. Datele colectate din acest tabel sunt următoarele:
Expresia finală se realizează prin reutilizarea operațiilor de lipire și absorbție:
Membrii acestei expresii sunt simpli implicați ai expresiei. Trecerea de la o formă redusă la una minimă se realizează cu ajutorul unei matrici implicate.
Membrii CDNF ai funcției date se încadrează în coloane și în rânduri - implicați simpli, adică membri ai formei abreviate. Sunt marcate coloanele membrilor CDNF. Ele sunt absorbite de implicanții simpli individuali. În tabelul următor, un implicant simplu absoarbe membrii și (în prima și a doua coloană sunt plasate crucile).
Matricea implicită
Al doilea implicant absoarbe primul și al treilea membru al CDNF (indicat prin încrucișări), etc. Implicanții care nu fac obiectul excluderii formează un nucleu. Astfel de implicați sunt determinați din matricea de mai sus. Pentru fiecare dintre ele, există cel puțin o coloană care este suprapusă numai de acest implicant.
În exemplul nostru, nucleul este alcătuit din implicați și (se suprapun pe coloanele a doua și a șasea). Excluderea din forma redusă a tuturor implicanților care nu sunt inclusi în miez simultan este imposibilă, deoarece excluderea unuia dintre implicanți poate transforma cealaltă într-un termen de neînlocuit.
Pentru forma minimă este suficient pentru a alege din implicants, non-core, un astfel de număr minim, cu un număr minim de scrisori în fiecare dintre aceste implicants, care va oferi o suprapunere a tuturor coloanelor, nu membri de bază suprapuse. În acest exemplu, este necesar ca implicanții care nu fac parte din kernel să se suprapună coloanelor a treia și a patra a matricei. Acest lucru se poate realiza în mai multe moduri, dar întrucât este necesar să se aleagă numărul minim de implicați, atunci evident, pentru a suprapune aceste coloane, trebuie să alegeți persoana implicată.
Forma normală disjunctivă minimă (MDNF) a unei funcții date:
Faceți clic pe imagine pentru al mări.
Schema structurală corespunzătoare acestei expresii este prezentată în figura din stânga. Trecerea de la schema prescurtată la MDNF a fost realizată prin eliminarea membrilor inutili - implicit și. Să arătăm admisibilitatea unei astfel de excepții a membrilor de la o expresie logică.
Implicați și deveniți egali cu jurnalul. 1, respectiv pentru următoarele seturi de valori ale argumentului: = 0, = 0, = 0 și = 1, = 1, = 0.
Rolul acestor implicați în exprimarea formei abreviate a funcției este numai de a atribui valorile 1 seturilor de valori ale argumentului dat. Cu toate acestea, cu aceste seturi, funcția este 1 din cauza celorlalți implicați ai expresiei. Într-adevăr, înlocuind setul de valori indicat mai sus în formula (a). obținem:
- at = 0, = 0, = 0
;
- at = 1, = 1, = 0
;
Utilizarea metodei pentru a obține CNF minim
Pentru a obține forma normală conjunctivă minimă (ICPF), utilizând metoda Quine, sunt introduse următoarele criterii:
- minimizarea nu este luată de SDNF. dar funcțiile SKNF;
- Peretele lipit de elemente se schimbă la: sau;
- Regula de absorbție este următoarea:
Articole similare
Trimiteți-le prietenilor: