Definiția. Implantul g al unei funcții booleene f. care este o conjuncție elementară, se spune că este simplă dacă nici o parte a implicitului g nu este un implicant al funcției f.
Din exemplul respectiv se poate observa că implicanții și. sunt implicați simpli ai funcției f. Implicanții sunt g1. g2. g4. g6 nu sunt simple, deoarece părțile lor implică funcția f. de exemplu, g5 face parte din g1. Dăm fără dovadă două afirmații utile în obținerea DNF minimă.
1. Disjuncția oricărui număr Implicantul unei funcții booleene f este, de asemenea, un implicant al acestei funcții.
2. Orice funcție booleană f este echivalentă cu disjuncția tuturor implicanților săi simpli. Această formă de reprezentare a unei funcții booleene se numește DNP abreviat.
Căutarea tuturor implicanților posibili pentru funcția booleană f din exemplul respectiv face posibilă verificarea faptului că implicantul simplu este doar două: g3 și g5. În consecință, DNF abreviată a f este:
După cum se poate observa din tabel. 1, implicit g3. g5 acoperă colectiv toate unitățile funcției f prin unitățile lor. Obținerea DNP abreviată este primul pas în găsirea formelor minime de funcții booleene. După cum sa menționat deja, DNF abreviat include toți implicanții simpli ai funcției Boolean. Uneori, dintr-un DNP redus, unul sau mai mulți implicați simpli pot fi eliminați fără a încălca echivalența funcției inițiale. Astfel de implicați simpli vor fi numiți inutili. Eliminarea implicanților simpli simpli de la DNP abreviate este a doua etapă a minimizării.
Definiția. DNF-ul abreviat al unei funcții booleene se numește funcția "end-end" dacă nu există implicații suplimentare în ea.
Eliminarea implicanților simpli inuți de la DNF redus a unei funcții Boolean nu este un proces cu o singură valoare, adică o funcție booleană poate avea mai multe DNF-uri terminate.
Aprobarea. Deadlock DNF al funcției booleene f. care conțin numărul minim de litere sunt minime. DNF minimă poate fi, de asemenea, mai multe.
Să luăm în considerare mai multe metode de minimizare. Toate acestea diferă practic doar în prima etapă - etapa de obținere a unui DNF redus. Trebuie remarcat faptul că, din păcate, căutarea unui DNF minimal este întotdeauna legată de o sortare a soluțiilor. Există metode pentru a reduce această căutare, dar rămâne întotdeauna.
Metoda Quine se bazează pe aplicarea a două relații de bază.
1. Raportul de lipire
unde A este orice produs elementar.
2. Gradul de absorbție
Valabilitatea ambelor relații este ușor de verificat. Esența metodei constă în execuția secvențială a tuturor posibilelor lipiri și apoi la toate absorbțiile, ceea ce duce la un DNF scurtat. Metoda se aplică DNF perfectă. Din relația de absorbție rezultă că un produs elementar arbitrar este absorbit de orice parte a acestuia.
Pentru dovada este suficient să se arate că poate fi obținut un implicant arbitrar simplu. De fapt, aplicarea la p operația de desfășurare (inversul operației de lipire):
pentru toate variabilele lipsă ale funcției inițiale f, obținem mulțimea S a constituenților de unitate. Atunci când lipim împreună elementul S, obținem p. Aceasta din urmă este evidentă, deoarece operațiunea de lipire este inversă a operației de desfășurare. Un set S de constante este neapărat prezent în funcția DNF perfectă, deoarece p este implicit.
Un exemplu. Să existe o funcție booleană dată de o tabelă de adevăr (Tabelul 9.12). CDNF-ul său arată astfel:
Pentru comoditatea expunerii, subliniem fiecărui constituent al unității din SDNF funcția f un număr zecimal (arbitrar). Realizăm lipirea. Constituția 1 este lipită împreună numai cu constituentul 2 (în variabilă) și cu constituentul 3 (în variabilă) constituentul 2 cu constituentul 4 și așa mai departe.
Ca rezultat, obținem
Menționăm că rezultatul lipirii este întotdeauna un produs elementar, care este o parte comună a componentelor care urmează să fie lipite împreună.
Apoi, facem lipirea împreună a produselor elementare obținute. Doar acele lucrări care conțin aceleași variabile sunt lipite împreună. Există două cazuri de lipire:
cu apariția aceluiași produs elementar. Lipirea ulterioară este imposibilă. După realizarea absorbției (din DNF obținut, traversăm toate produsele elementare absorbite), obținem un DNF scurtat:
Trecem la a doua etapă. Pentru a obține DNF minim, este necesar să eliminați toți implicanții simpli simplifici de la DNF redus. Acest lucru se face cu ajutorul unei matrice speciale implicite a lui Quine. Rândurile unei astfel de matrice sunt marcate de implicanții simpli ai funcției booleene, adică de termenii DNF redus și de coloanele constituenților unității, adică de membrii CDNF al funcției booleene.
Exemplu (continuare). Matricea implicită are forma (Tabelul 3).
Așa cum am menționat deja, un implicit simplu absoarbe un element constitutiv al unității, dacă aceasta este partea sa. Celula corespunzătoare a matricei implicate la intersecția rândului (cu implicantul simplu în cauză) și coloana (cu componenta unității) este marcată cu o cruce (Tabelul 3). DNF-urile minime sunt construite din matricea implicată după cum urmează:
1) sunt căutate coloane ale unei matrice implicate cu o singură cruce. Corespunzător acestor încrucișări, implicații simpli sunt numiți implicanți de bază și constituie așa-numitul nucleu al funcției booleene. Miezul este inclus în mod necesar în DNF minim.
2) luați în considerare diverse opțiuni pentru alegerea unui set de implicați simpli care vor traversa coloanele rămase ale matricei implicate cu cruci și selectați opțiunile cu
numărul total minim de litere dintr-un astfel de agregat este implicit.
Exemplu (continuare). Miezul funcției noastre este implicarea; Implicantul este inutil, deoarece nucleul acoperă toate coloanele matricei implicate. Prin urmare, funcția are un DNF unic și un DNF minim:
Trebuie remarcat faptul că numărul de N încrucișări într-o singură linie este întotdeauna o putere de 2. Mai mult, cititorul poate verifica cu ușurință acest lucru
,unde k este numărul de litere conținute într-un implicant simplu.
Rețineți, de asemenea, că folosind relații diferite, putem extinde "domeniul de aplicare al metodei Quine dincolo de limitele DNF perfectă.
Un exemplu. Minimizați funcția Boolean f prin metoda lui Quine:
1. Scădem de negative și paranteze, folosind relațiile de mai sus
2. Restabiliți funcția SDNF f prin aplicarea operației de implementare
3. Să găsim DNF abreviată a funcției f, producând în SDNF toate lipirile posibile
4. Căutăm DNF minimă a funcției f din matricea implicantă (Tabelul 4). Kernel-ul funcției booleene :. . DNF minime: