- Definiția. conjuncție elementară K este implicants funcției f, dacă pentru orice set a = (a1, a2, ..., an) de 0 și 1, condiția R (a) = 1 implică f (a) = 1.
- Definiție: Un aplicator pentru o funcție f este numit simplu. dacă expresia obținută din ea prin aruncarea oricăror factori nu mai este implicarea funcției f.
- Orice implicant al funcției f este o parte a funcției f.
- Teorema. Fiecare funcție este realizată prin disjuncția tuturor implicanților ei simpli.
- Definirea unui DNF redus al unei funcții f este o disjuncție a tuturor implicanților simpli ai funcției f.
- Aprobarea. Fiecare funcție f este realizată prin DNF abreviat.
- Pentru fiecare funcție care nu este identic cu zero, există un DNF abreviat unic.
- Teorema (Quine). Dacă în funcția SDNF f se efectuează toate operațiile de lipire incompletă și apoi toate operațiile de absorbție și eliminare a membrilor duplicat, atunci în consecință obținem un DNF abreviat al funcției f.
Algoritmul lui Quine pentru construirea unui DNP redus
1. Obțineți funcția CDNF.
2. Efectuați toate operațiile de lipire incomplete.
3. Realizați toate operațiunile de absorbție.
Un exemplu. Minimizați funcția f = 1111010010101111.
Soluția.
1. Construim un tabel de valori pentru o funcție dată (Tabel). Construim funcțiile SDNF. Summandrele sunt numerotate și scrise într-o coloană (Tabel).
2. Realizăm toate operațiile de lipire incompletă.
Prima etapă a lipirii (tabel):
În prima etapă a lipirii, toți termenii CDNF au participat, ceea ce înseamnă că nici unul din termenii originali nu va fi inclus în DNF abreviat. După prima etapă de lipire (și posibilă absorbție), obținem acest lucru
Numim termenii disjunctivi în DNF obținut în ordinea succesiunii lor de la 1 la 15 (tabel).
A doua etapă a lipirii:
În procedeul de lipire în a doua etapă, componentele nr. 5 și 8 nu au luat parte din etapa anterioară, prin urmare, după a doua etapă de pastrare și absorbție ulterioară, obținem că
Deoarece lipirea ulterioară este imposibilă, aceasta va fi DNF abreviată a funcției inițiale.
Articole similare
-
T-Wilcoxon Criterion, Statistici matematice, Exemple de rezolvare a problemelor
-
Bazele teoretice ale minimizării funcțiilor booleene prin metoda Quine
Trimiteți-le prietenilor: