Metoda Quine se bazează pe scrierea nu a tuturor conjuncțiilor posibile pentru o funcție, ci numai a celor care pot fi prezente în DNF a unei funcții date. Se presupune că funcția este dată sub forma unui CDNF. În această metodă, conjuncțiile elementare de rang n în DNP sunt numite minterme de rang n.
Soluția problemei minimizării funcției booleene prin metoda Quine și metoda îmbunătățită Quine-McCluskey se bazează pe conceptele implicate și sistemele lor.
Algoritmul de obținere a formei normale disjunctive minime a MDNF a unei funcții logice:
1. Funcția logică este reprezentată în CDNF. Mai mult, dacă este specificată printr-un tabel de adevăr, atunci ele sunt reprezentate prin scrierea "pe unități"; dacă este dată printr-o formă disjunctivă arbitrară algebrică - prin aplicarea operațiunilor de desfășurare, formulele lui De Morgan etc.
2. În CDNF-ul primit, se efectuează toate operațiile posibile de lipire incompletă și apoi absorbție. Ca rezultat, se obține o formă normală disjunctivă redusă, adică disjuncția celui mai scurt dintre toate produsele elementare posibile (implicații simpli) care intră într-o funcție logică dată.
Fie funcția dată să fie reprezentată în SDNF. Trecerea la forma scurtată se bazează pe aplicarea consecventă a două operațiuni: operațiile de lipire și operațiunile de absorbție.
Pentru a efectua operația de lipire în expresie, o pereche de termeni ai formularului și. diferă doar prin faptul că unul dintre argumente este reprezentat într-unul dintre termeni fără inversiune, iar în celălalt cu inversiune. Apoi lipim împreună astfel de perechi de termeni :. iar rezultatele lipirii sunt introduse în expresia funcției ca termeni suplimentari. Apoi se efectuează operația de absorbție. Se bazează pe expresia: (membrul absoarbe). În comportamentul acestei operații, toți membrii absorbiți de termenii care au intrat în expresie ca rezultat al operației de lipire sunt șterși din expresia logică. Operațiile de lipire și absorbție sunt efectuate secvențial cât mai mult posibil.
3. Găsiți formele normale disjunctive minime (MDNF) din matricea implicată.
Matricea implicită este o tabelă a cărei intrări verticale și orizontale sunt înregistrate de membrii CDNF și de implicanții simpli ai funcției logice date.
Celulele matricei implicate, formate prin intersecția rândurilor cu implicanții și coloanele cu membrii absorbanți ai CDNF, sunt marcate cu cruci [5].
MDNF se găsește ca o disjuncție a numărului minim de implicați, care acoperă împreună toate coloanele matricei implicate cu cruci.
Exemplul 4.1. Minimizați funcția logică:
Soluție: 1. Funcția este dată în formă algebrică, folosind operațiile de implementare
primiți un CDNF care conține șase membri:
2. Operațiunile de lipire se efectuează în următoarea ordine:
1) toate lipirile posibile dintre primul termen și celelalte;
2) orice eventuală lipire a celui de-al doilea termen cu restul, cu excepția primului;
3) toate lipirile posibile ale celui de-al treilea termen cu restul, cu excepția primului și a celui de-al doilea etc., sunt efectuate.
Numai acei membri pot fi lipiți împreună, pentru care numărul de variabile cu negări diferă de unul.
Rezultatele lipirii și absorbției:
Asteriscurile sunt marcate de acei membri ai CDNF, care sunt absorbiți de produsele formate după lipire.
În exemplul considerat, toți cei șase termeni inițiali sunt absorbiți, deci SDNF al funcției date are forma:
La această expresie, operațiunile de lipire și absorbție nu pot fi aplicate și, prin urmare, este o formă normală disjunctivă abreviată a unei funcții logice, iar termenii ei sunt simpli implicați.
3. O matrice implicită este construită pentru funcția dată (Tabelul 4.1).
Simplificatori (minteri)
Pentru a obține MDNF, este necesar să se găsească numărul minim de implicați care acoperă împreună toate coloanele matricei implicate cu cruci:
Complexitatea unei funcții logice este determinată de numărul de variabile care intră în expresia sa: într-o funcție dată 14, în funcția minimă 9.
Primul algoritm pentru obținerea formei normale conjunctive minime (ICPF) a unei funcții logice:
1. Funcția logică este reprezentată în SKNF. În plus, dacă este dată de o tabelă de adevăr, atunci este scrisă "cu zero"; în cazul în care este definit algebric sub orice formă conjunctivă, pentru înregistrarea SKNF efectua toate posibila desfășurare a unei operațiuni.
2. În SKNF obținut se efectuează toate operațiile posibile de lipire incompletă și apoi absorbție. Ca urmare, ele primesc o formă normală conjunctivă normală, ale cărei membri sunt măști simple.
3. ICPF se găsește prin matricea muckstrom.
Exemplul 4.2. O funcție logică este specificată de un tabel de adevăr. Găsiți ICPF pentru această funcție.
5. ICPF a funcției logice :.
Al doilea algoritm pentru obținerea funcției logice ICNF:
1. Funcția logică este reprezentată în SDNF printr-o funcție dată, luată cu negarea.
Dacă funcția este specificată de o tabelă de adevăr, atunci scrieți un număr de produse din toate argumentele și le conectați cu semnele de disjuncție; numărul de produse trebuie să fie egal cu numărul seturilor pe care dispare funcția dată; sub fiecare produs scrieți un set de argumente pe care funcția este zero și peste argumentele egale cu zero, puneți semnele de negare.
Dacă funcția este dată algebric într-o formă arbitrară, atunci mai întâi se găsește în CDNF, și apoi este scrisă disjuncția tuturor produselor de argumente care nu sunt incluse în SDNF.
2. Găsiți MDNF prin algoritmul considerat mai sus.
3. Din care rezultă MDNF ia negare și, după transformare cu formule De Morgan MKNF obținute.
Exemplul 4.3. Găsiți ICNF, funcțiile date de tabelul de adevăr.
3. MDNF, luată cu o valoare negativă:
4. Utilizarea pe ambele părți ale acestei ecuații și negare folosind formula lui De Morgan, pentru a primi funcția logică MKNF:
În metoda lui Quine, există un inconvenient semnificativ asociat cu necesitatea unei comparații complete pereche a mintermelor în stadiul de construire a unui micron. DNF. În 1956, McCluskey a sugerat modernizarea primei etape a metodei Quine, care reduce semnificativ numărul de comparații ale mintermelor [17].
Ideea metodei McCluskey este după cum urmează. Toate mintermele sunt scrise sub formă de numere binare, de exemplu, ca 1010. Aceste numere sunt împărțite în grupuri în funcție de numărul de unități din cameră, adică în grupa i există numere având în unitățile lor înregistrate i. Comparația pereche se face numai între grupurile învecinate după număr, deoarece Mintermia, potrivită pentru lipire, diferă una de alta numai într-o singură descărcare. Atunci când mintermele sunt formate dintr-un rang mai mare decât zero, o cratimă este plasată în cifre corespunzătoare variabilelor excluse.
Metoda oferă următoarea secvență de acțiuni pentru obținerea unui DNF redus.
1. Găsirea implicanților primari. Fiecare minterm al funcției este privit secvențial și o operație este realizată prin lipirea acesteia împreună cu toate mintermele cu care este posibil. Ca urmare a lipirii mintermelor de rangul n, se obțin minterele (n-1) -ga. Minstrele de gradul n, care au participat la operația de lipire, sunt marcate, de exemplu, cu un asterisc. Apoi sunt luate în considerație minterele (n-1) și se aplică operația de lipire. Minterurile de lipire (n-1) se vor suprapune, adezivul minterm (n-2) rezultat, etc., va fi înregistrat. Etapa se termină dacă minstrele nou obținute nu se mai adună împreună. Toate mintermele nemarcate sunt numite implicante primare. Disjuncția lor este o funcție scurtă a DNF.
Apoi minturile din al patrulea rang sunt lipite impreuna si din nou mintermele lipite sunt marcate cu asteriscuri:
Minterurile de gradul doi se formează:
Participanții primari (simpli) sunt:
2. Aranjarea mărcilor. Pentru această funcție, DNP abreviat este:
Pentru construcția DNF și Sokr. DNF trebuie să arunce intervale suplimentare. Se construiește un tabel, liniile cărora corespund implicanților primari și coloanele miniștrilor SDNF. Dacă unele din minterm include oricare dintre implicants, la intersecția rândului respectiv și eticheta coloanei este plasată.
3. Găsirea implicanților esențiali. Dacă există o singură unitate într-o coloană, implicantul principal care definește această linie este numit esențial. De exemplu, un implicant esențial este. Un implicant esențial nu poate fi înlăturat din Socrate. DNF, t. Numai ea este capabilă să acopere pe unii dintre miniștrii CDNF. Prin urmare, rândurile care corespund acestor implicați și coloanele care au unități în aceste rânduri sunt excluse din tabel.
În acest exemplu, rândurile și coloanele sunt excluse
Ca rezultat, obținem tabelul:
4. Ștergerea coloanelor și rândurilor suplimentare. Dacă tabelul rezultat are aceleași coloane, atunci toate cu excepția unuia sunt șterse. Dacă în tabel există apoi linii goale, acestea sunt, de asemenea, șterse.
5. Selectarea unei acoperire minimă cu intervale maxime. În tabelul rezultat, selectați o colecție de rânduri care conține unitățile din toate coloanele. Cu mai multe variante posibile ale acestei opțiuni, preferința este dată variantei cu numărul minim de litere în liniile care formează capacul. Acoperirea minimă a mesei este formată din linii corespunzătoare participanților. Apoi MDNF arata astfel:
Exemplul 4.4. Minimizați funcția specificată în tabel.
și comparații ale membrilor (fiecare membru, cu toate ulterioare-yuschimi) sunt lipite împreună dezvăluie o pereche de membri:
Primii și al patrulea membri (rezultatul lipirii)
Al doilea și al treilea membru (rezultat al lipirii)
Al doilea și al patrulea membru (rezultatul lipirii)
Al 3-lea și al 5-lea membru (rezultatul lipirii)
Al 4-lea și al 5-lea membru (rezultatul lipirii)
Rezultatele operației de lipire sunt introduse în expresia funcției și efectuăm operația de absorbție a termenilor expresiei originale de către ei:
Repetăm operațiunile de lipire și absorbție.
Aici operația de lipire este realizată cu două perechi: și. și. și lipirea ulterioară este imposibilă, aceasta este o formă scurtă (și în acest exemplu forma minimă)
În această funcție sunt simpli implicați
Articole similare
Trimiteți-le prietenilor: