O conjuncție elementară a variabilelor n este conjuncția variabilelor sau negările lor.
Conjuncția elementară a variabilelor n poate fi scrisă sub forma:
O formă normală disjunctivă (DNF) cu formula A este o formulă echivalentă cu aceasta, care este o disjuncție a conjuncțiilor elementare.
Pentru orice formula algebrică a logicii prin transformări echivalente se poate obține DNF-ul ei, și nu singurul.
De exemplu, pentru formula A º x (x ® y) avem
Evident, primul DNF nu satisface una din proprietățile (C), și anume cea de-a treia proprietate. Al doilea DNF satisface toate proprietățile (C).
Dintre numeroasele DNF-uri A, există un singur DNP A. pentru care sunt îndeplinite cele patru proprietăți ale perfecțiunii enumerate mai sus (proprietăți (C)).
O astfel de DNF A se numește o formă normală disjunctivă perfectă cu formula A (CDNF A), adică este un DNF pentru care sunt satisfăcute proprietățile perfecțiunii.
După cum sa menționat deja, SDNF-ul oricărei formule A poate fi obținut utilizând un tabel de adevăr. Să demonstrăm acest lucru prin exemplul formulării de mai sus x (x ® y) (tabelul 6, 10).
Tabelul de adevăr pentru formula x (X ®u)
Deoarece 1 există doar pentru un set (1, 1), SDNF va avea doar un singur termen, și anume x y.
O disjuncție elementară a variabilelor n este o disjuncție a variabilelor sau negările lor.
Disjuncția elementară a variabilelor n poate fi scrisă în formă
O formă normală conjunctivă (CNF) cu formula A este o formulă echivalentă cu aceasta, care este o combinație de disjuncții elementare.
Pentru orice formulă algebrică a logicii prin transformări echivalente, se poate obține CNF-ul său, și nu singurul.
De exemplu, pentru o formulă, folosind legile echivalenței, avem
Aceasta este una dintre formele CNF, care pot fi simplificate în continuare (de ex Úx º x. y Úy ºy).
Un CNF A se numește o formă normală conjunctivă perfectă cu formula A (SKNF A) dacă sunt îndeplinite următoarele condiții.
1. Toate disjunctiile elementare incluse in CNF A. sunt diferite.
2. Toate disjuncțiile elementare incluse în CNF A. conțin toate variabilele.
3. Fiecare disjuncție elementară inclusă în CNF A. nu conține două variabile identice.
4. Fiecare disjuncție elementară inclusă în CNF A. nu conține o variabilă și negarea ei.
Se poate arăta că fiecare formulă non-identică adevărată are un SKNF unic.
Una dintre modalitățile de a obține un CSCF este de a folosi o tabelă de adevăr pentru formula # 256; .
Într-adevăr, folosind tabelul cu adevărat al CDNF # 256; obținem SKNF A. prin refuzul CDNF # 256;
Să demonstrăm acest lucru cu exemplul aceleiași formulări (Tabelul 11).
Tabelul de adevăr pentru formula
Articole similare
Trimiteți-le prietenilor: