Reducerea la SKNF. Algoritmul de reducere.
- a aduce formula prin transformări echivalente cu CNF.
- ștergeți membri ai conjuncției care conține o variabilă împreună cu negarea acesteia (dacă există);
- de la membri identici ai conjuncției (dacă există) pentru a elimina toate, cu excepția unuia;
- De la aceiași membri ai fiecărei disjuncții (dacă există), eliminați toate cu excepția unuia;
- dacă într-o anumită disjuncție nu conține variabila xi din numărul de variabile care intră în formula inițială, adăugați la această disjuncție termenul și aplicați legea distributivității disjuncției în raport cu conjuncția;
- dacă în conjuncția rezultată există aceiași termeni, folosiți prescripția de la §3.
Formula care rezultă este SKNF cu această formulă.
Dați următoarele formule SKNF folosind transformări echivalente:
Al doilea mod este tabular.
Compilam o tabelă de adevăr pentru o anumită funcție.
Construim tabelul valorilor formulei. Considerăm numai acele linii în care valoarea formulei este egală cu una. La fiecare astfel de linie corespunde o conjuncție a tuturor argumentelor (fără repetiții). Și argumentul care ia valoarea 0 o introduce cu un negativ, valoarea 1 - fără negare. În cele din urmă, formăm disjuncția tuturor conjuncțiilor rezultate.
Construiți un CDNF pentru aceste formule logice propoziționale.
Construim tabelul de adevăr (Tabelul 13) pentru formula F:
Trimiteți-le prietenilor: