Tema. Minimizarea funcțiilor Boolean.
Curs 6. Problema minimizării. Generarea implicanților simpli. Quine și algoritmul McCloski Problema minimizării
Definiția.
formă normală disjunctivă # 106; se numește funcția f
a) minimal (minimal în literali) dacă are cel mai mic număr de simboluri variabile printre celelalte DNF ale funcției f;
c) cel mai scurt (minimal în conjuncții) dacă are numărul minim de conjuncții elementare.
Numărul de conjuncții elementare distincte ale n variabilelor este egal cu 3 n. deoarece orice variabilă poate fie să intre în conjuncție, fie să nu intre sau să intre cu o negare. Apoi, DNF a variabilelor n este determinată în mod unic de un vector cu lungimea 3 n. constând din zerouri și unul, în care 1 înseamnă că legătura elementară corespunzătoare este inclusă în DNF și 0 nu este inclusă. Prin urmare, numărul tuturor DNP-urilor din variabilele "n" este.
Pentru o funcție arbitrară a algebrei logice se pot scrie multe DNF-uri. Problema minimizării este aceea de a construi un DNF minim în sensul definit mai sus pentru funcția f. Această problemă permite o soluție trivială constând în căutarea tuturor DNF-urilor, dar este evident că o astfel de soluție este extrem de consumatoare de timp chiar și pentru valorile mici ale lui n.
Definiția. formulă # 89; implică formula # 70; (denumire
# 89; # 70; ). dacă ( # 89; # 70; ) 1, adică Nu există un set de valori pentru variabilele la care să se facă # 121; ia valoarea 1. a # 70; este valoarea 0.
Definiția. Conjunctura elementară K este numită implicantă a funcției f. dacă K f.
Exemplul 6.1.
Fie și lasă K = x = x 1 y 0. K = 1 # 219; x = 1, y = 0. Deoarece f (1,0, z) = 1 × 1 × z # 218; 1 × 1 × = z # 218; 1. atunci K = x este un implicant al funcției f.
Fie f (x, y, z, t) = x z # 218; x t și let K = x = x 1 y 0. K = 1 # 219; x = 1, y = 0. Deoarece f (1,0, z, t) = z # 218; t 1. Din moment ce dacă z = 0 și t = 0. apoi z # 218; t = 0, adică K = x nu este un implicant al lui f.
TEOREM 6.1. Dacă formula # 70;. care realizează funcția f. Arată ca - DNP, atunci.
Dovada. Fie funcția ki = 1 în DNF. Apoi și, în consecință, f = 1.
Definiția. Funcția implicită P din f se spune că este simplă. dacă, la îndepărtarea oricărei variabile de la P, rezultatul conjunctural elementar nu este implicit.
În Exemplul 6.1. - Un implicant simplu, pentru că nici x, nici implicanții nu sunt.
TEOREM 6.2. Fiecare functie este reprezentata in forma, unde Pi sunt implicanti simpli.
Dovada. Este necesar să se arate că f = 1 dacă și numai dacă. Evident, dacă, atunci f = 1.
Acum, să presupunem că există un set de valori ale variabilelor. În acest caz, și din Teorema 6.1. rezultă că ki este un implicant. Reducem acest implicant la unul simplu. Repetăm această procedură pentru toate seturile de valori ale variabilelor pentru care f = 1.
Definiția. DNF-ul unei funcții f se numește non-redundant dacă:
Evident, DNF minim este inaccesibil. Prin urmare, DNF minimal ar trebui să fie căutat printre cele care nu sunt redundante. Astfel, problema minimizării poate fi împărțită în următoarele etape:
1) găsirea tuturor implicanților simpli ai funcției f;
2) găsirea DNF-urilor non-redundante ale funcției f;
3) alegerea funcției minime DNF f.
Generarea implicanților simpli
Definiția. Legătură elementară # 97; acoperite de o conjunctură elementară # 98;. dacă fiecare variabilă este inclusă în # 98;. este inclus în # 97; (luând în considerare negarea).
Exemplul 6.2.
conjuncție # 97; = xyz este acoperit de conjuncții # 98; = xy.
conjuncție # 97; = x z nu este acoperit de conjuncții # 98; = x.
Definiția. Legătură elementară # 97; se numește complementul conjuncției elementare # 98; în legătură cu DNP # 70; . în cazul în care:
Exemplul 6.3.
lăsa # 70; = xy # 218; # 218; ZT # 218; . Apoi, conjuncțiile # 97; 1 = xyzt. # 97; 2 = xyz, # 97; 3 = xy t, # 97; 4 = xy sunt complemente ale conjuncției # 98; = xy cu privire la # 70; .
THEOREM 6.3. lăsa # 70; - Funcția CDNF f. În cazul în care # 98; - implicit f. atunci toate complementele combinației elementare # 98; în legătură cu # 70; sunt incluse în # 70; .
Dovada. Să fie implicantul f și să fie completarea lui # 98; în legătură cu # 70;. Să presupunem asta # 97; nu este inclus în # 70;. Luați în considerare un set de valori ale unor astfel de variabile # 97; = 1. și anume am setat xi = # 100; i. i = 1, ..., n. Atunci u # 98; = 1. și # 70; = 0 de atunci # 97; prin ipoteză nu este inclusă în # 70;. Dar acest lucru contrazice faptul că # 98; este un implicant al f.
Din teorema rezultă că combinarea în CDNF # 70; funcțiile f în mod corespunzător unei perechi de conjuncții elementare și aplicarea egalității succesive, se poate obține, prin urmare, toți implicanții simpli ai funcției f.
Exemplul 6.4.
Să presupunem că f = xyzt # 218; x # 218; x zt.
Prima și a treia conjuncție dau xyzt # 218; x zt = xzt. A doua și a treia conjuncție dau x z # 218; x zt = x z. Expresiile rezultate sunt implicați simpli și, prin urmare, f = xzt # 218; x z.
Algoritmul Quine și McCloskey (enumerarea implicanților simpli)
Sistematizăm ideea de mai sus.
1) Se scrie pentru funcția f CDNF # 70; .
2) În fiecare conjuncție elementară toate variabilele vor fi scrise în aceeași ordine.
3) Fiecare conjuncție elementară poate fi reprezentată ca o secvență de 1. 0 și -. plasarea pe i-loc 1. dacă variabila i intră într-o conjuncție fără negare, 0 - dacă cu negare și -. dacă nu sunt incluse.
De exemplu, xyz # 218; x # 218; x va fi scris ca 111- # 218; 1-0- # 218; 1-0.
4) Formăm din conjuncțiile elementare ale unui grup, inclusiv într-un grup de seturi cu același număr de unități (grupuri în care numărul de unități este diferit de 1. se numește vecinătate); aranjați grupurile în ordinea crescândă a numărului de unități.
De exemplu, pentru o funcție
conexiunile elementare sunt reprezentate ca 1101, 1001, 1100, 1000, 0010, 0001, 0000, iar lista grupurilor va fi după cum urmează:
5) Egalitatea poate fi aplicată numai perechilor potrivite de seturi din grupurile învecinate. O pereche adecvată este formată din două seturi care diferă într-o poziție și nu există linie în această poziție. Perechile potrivite vor fi marcate cu asteriscuri (*).
6) Am pus o cratimă în poziția divergentă a unei perechi potrivite și plasăm setul rezultat în următoarea listă de grupuri.
7) Repetați procesul descris cât mai mult posibil. Seturile nesemnate formează implicații simpli.
În acest exemplu, pașii 6 și 7 arată astfel.
Articole similare
Trimiteți-le prietenilor: