Definiția 4. Disjuncția elementară a variabilelor n este disjuncția variabilelor sau negările lor.
5. Determinarea forma normală conjunctivă (FNC) cu formula A este echivalentă cu aceasta formula care reprezintă o conjuncție disjuncțiilor elementare.
Definiția 6. O formulă normală conjunctivă perfectă A (SKNF A) se numește CNF A. îndeplinind următoarele condiții:
1. toate disjuncțiile elementare incluse în CNF A. conțin toate variabilele;
2. Toate disjunctiile elementare care fac parte din CNF A. sunt diferite;
3. Fiecare disjuncție elementară inclusă în CNF A. conține o singură variabilă;
4. Nici una din disjuncțiile elementare incluse în CNF A. nu conține o variabilă și negarea ei.
SKNF A poate fi obținut în două moduri:
a) folosind un tabel de adevăr (folosind legea dualității) (a se vedea 5.1);
b) prin transformări echivalente.
Regula pentru obținerea SKNF de la formula A folosind transformări echivalente.
1. Pentru formula A, obținem orice CNF A.
2. Din CNF A, prin transformări echivalente, obținem SKNF A. realizând succesiv realizarea celor patru proprietăți ale FCNF A.
1) Dacă disjuncția elementară B din CNF A. nu conține o variabilă. apoi înlocuim B cu.
2) Dacă o variabilă intră de două ori într-o disjuncție elementară B, atunci variabila suplimentară trebuie eliminată, deoarece.
3) Dacă CNF A conține două disjuncții elementare identice, atunci se poate renunța, deoarece.
4) Dacă există o pereche în disjuncția elementară. atunci poate fi aruncat ca. și adevărata afirmație a conjuncției poate fi aruncată (în virtutea echivalenței).
Exemplul 1. Pentru formula, găsiți CDNF și SKNF, fiecare în două moduri.
Trimiteți-le prietenilor: