Efectuat în problemele 2 și 3 transformări echivalente arată că, prin efectuarea unor calcule matematice corecte (Boolean) poate fi simplificat în mod considerabil dispozitiv logic implementează funcția.
2.3. Forme normale disjunctive și conjunctive
Orice disjuncție a conjuncțiilor elementare este denumită formă normală disjunctivă (DNF).
Orice conjuncție de disjuncții elementare este denumită formă normală conjunctivă (CNF).
Orice funcție logică care nu este identică cu una poate fi reprezentată în DNF.
Orice funcție logică care nu este identică cu zero poate fi reprezentată în CNF.
Procedura de aducere la DNP:
1. Toate negările "coboară" la variabile cu ajutorul formulelor (6) și (8).
2. Extindeți brațele folosind (1), (3), (4).
3. Ștergeți conjuncțiile inutile și repetițiile în conjuncție cu ajutorul (5), (9), (10).
4. Ștergeți constantele folosind (7).
Problema 4. Dați formula DNF
deschideți brațele (3)
regula de Morgan (8, b)
regulile (9, 7, b, 8, a)
regulile (8, a și 8, b, 6)
aplicăm pasta generalizată (13, a),
prin introducerea notei. avem
deschideți parantezele și regula (9, 5, a)
scos din paranteze
regula generală de lipire (13, b)
Procedura de aducere a DNP la CNF:
Să presupunem că DNF F are forma
1. Aplicați regula de negare dublă la F
și conduc la DNP. unde sunt conjuncții elementare. apoi:
2. Cu ajutorul regulii lui de Morgan, scapă de a doua negare și transformă negările conjuncțiilor elementare în disjuncții elementare. apoi:
Problema 5. Dați formula la CNF
introducem o dublă negare
regula de Morgan (8, b)
regula de De Morgan (8, a)
deschideți parantezele și regula (5, 9)
deschideți parantezele și regula (5, 9)
regulă de lipire (12)
regula de Morgan (8, b)
Metoda de tranziție de la o alocare de tabele a funcțiilor logice la o formulă booleană.
Procedura de trecere la CDNF:
a) pentru fiecare set de valori ale variabilelor. pe care funcția este egală cu 1, conjuncțiile tuturor variabilelor sunt scrise;
b) se fac negări asupra acelor variabile care sunt egale cu 0 pe acest set;
c) toate aceste conjuncții sunt legate prin semne de disjuncție.
Formula obținută în acest fel este numită forma normală disjunctivă normală (SDNF) a unei funcții logice.
Procedura de trecere la SKNF:
a) pentru fiecare set de valori ale variabilelor. pe care funcția este egală cu 0, disjuncțiile tuturor variabilelor sunt scrise;
b) negări se fac asupra acelor variabile care sunt egale cu 1 pe acest set;
c) toate aceste disjuncții sunt legate de semnele unei conjuncții.
Formula astfel obținută este numită forma normală conjunctivă perfectă (SKNF) a unei funcții logice.
Problema 6. Funcția logică a trei variabile este reprezentată de o formulă booleană sub forma SDNF și SKNF:
Construim tabelul de adevăr în mod succesiv, în conformitate cu etapele de construire a formulei