Transformările echivalente sunt transformări folosind relații echivalente și regula de înlocuire.
Două reguli de înlocuire:
1. Regula de substituire a formulei f în locul variabilei x. Atunci când formula f este înlocuită cu variabila x, toate aparițiile variabilei x în raportul original trebuie înlocuite simultan cu formula f.
2. Regula de substituire a subformulelor. Dacă orice formula f. descriind funcția # 966 ;. conține f1 ca subformula, apoi înlocuirea lui f1 cu un echivalent f2 (f1 = f2) nu schimbă funcția # 966; .
Relațiile de bază echivalente (legi) în algebra booleană.
Asociativitatea asocierii și disjuncției:
Comutativitatea conjuncției și a disjuncției:
Distributivitatea conjuncției în ceea ce privește disjuncția:
Distributivitatea disjuncției în raport cu conjuncția:
Legea dublei negări:
Proprietățile constantelor 0 și 1:
Regulile lui de Morgan:
Legea mediei excluse:
Relațiile de bază echivalente (1) - (10) diferă prin faptul că nu sunt deductibile una de cealaltă și că aceste relații sunt suficiente pentru efectuarea oricăror transformări echivalente.
Pentru a simplifica formulele, se folosesc următoarele relații echivalente care derivă din ecuațiile de bază prin transformări echivalente:
Reducerea la o formă normală disjunctivă.
O conjuncție elementară este o conjuncție a variabilelor sau negările lor, în care fiecare variabilă nu se întâmplă de mai multe ori.
Forma normală disjunctivă (DNF) este o formulă care are forma unei disjuncții a conjuncțiilor elementare.
Reducerea formulei la DNF se realizează în 4 etape:
1. toate negările "coboară" la variabile cu ajutorul (6) și (8);
2. Extindeți brațele folosind (1), (3), (4);
3. Îndepărtați conexiunile inutile și repetările variabilelor în conjuncție cu ajutorul (5), (9), (10);
4. Ștergeți constantele folosind (7).
Procedura de a aduce DNF la CDNF constă în împărțirea (folosind (12) în direcția opusă) a conjuncțiilor care nu conțin toate variabilele.
Reducerea la o formă normală conjunctivă.
Disjuncția elementară este o disjuncție a variabilelor sau negările lor, în care fiecare variabilă are loc nu mai mult de o dată.
Forma normală conjunctivă (CNF) este conjuncția disjuncțiilor elementare.
Să presupunem că DNF F are forma F = k1 Úk2 Ú...Úkm. unde k1, k2, ..., km sunt conjuncții elementare. Conversia DNP la CNF constă în două etape:
1. Aplicați regula de negare dublă la F și conduceți la DNF k ¢ 1 Ú k ¢ 2 Ú... k ¢ p unde k ¢ 1 Ú k ¢ 2 Ú... k ¢ p sunt conjuncții elementare. atunci
2. Cu ajutorul regulilor de Morgan pentru a scăpa de a doua negare și a transforma negările conjuncțiilor elementare în disjuncțiile elementare D1, D2, ... Dp Apoi
Perfect CNF (SKNF) este CNF, fiecare disjuncție elementară a căruia conține toate variabilele.
Articole similare
Trimiteți-le prietenilor: