Definiție 1. Disjuncția elementară a variabilelor n este disjuncția variabilelor sau negările lor.
Disjuncția elementară a variabilelor n poate fi scrisă sub forma:
Definiția 2. 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 formula avem:
Și de atunci. apoi CNF.
Definiția 3. 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 demonstra că fiecare dintre ele nu este la fel ca formula adevărată are un SKNF unic.
Una dintre modalitățile de a obține un CSCF este de a folosi un tabel de adevăr pentru formula A.
Într-adevăr, după ce am obținut folosind tabelul de adevăr al SDNF A. primim SKNF A. luând negarea. adică SKNF.
O altă metodă de obținere a SPCF, folosind transformări equipotențiale, este după cum urmează:
1. Prin transformări echivalente cu formula A se obține unul din CNF A.
2. Dacă disjuncția elementară B care intră în ea nu conține variabila xi, atunci, folosind echivalența, disjuncția elementară B este înlocuită de două disjuncții elementare și fiecare dintre acestea conține variabila xi.
3. Dacă CNF A include două disjuncții elementare B identice, atunci extra poate fi abandonată, folosind echivalența BBB.
4. Dacă o disjuncție elementară care apare în CNF A conține variabila xi de două ori, atunci cea extra poate fi aruncată folosind echivalența.
5. Dacă o disjuncție elementară care apare în CNF A. conține variabila xi și negarea ei, atunci, în consecință, întreaga disjuncție elementară are valoarea 1 și, prin urmare, ea poate fi aruncată ca termen unitar al conjuncției.
Este clar că după procedura descrisă vom obține SKNF A.
De exemplu, pentru formula CNF.
Deoarece ambele disjuncții elementare sunt distincte și conțin toate variabilele (x și y), prima și a doua condiție ale SKNF A sunt satisfăcute.
Disjuncția elementară conține variabila x de două ori, dar. și, prin urmare, CNF; și nici una dintre disjuncțiile elementare nu conține o variabilă și negarea ei. În mod semnificativ, acum toate condițiile ASNF A. și, în consecință, SKNF sunt îndeplinite.
Toate formulele algebrice ale logicii sunt împărțite în trei clase:
1) identic,
2) identic fals și
Definițiile formulelor identice și identice identice sunt date mai sus.
Formula A este numită satisfăcătoare dacă presupune valoarea "adevăr" pe cel puțin un set de valori ale variabilelor care intră în ea și nu este identic adevărat.
În acest sens, apare problema: la ce clasă aparțin această formulă?
Această problemă se numește problema de solvabilitate.
Evident, problema solvabilității algebrei logice este rezolvabilă.
Într-adevăr, pentru fiecare formulă algebrică a logicii, poate fi scris un tabel de adevăr care să răspundă la întrebarea pusă.
Cu toate acestea, utilizarea practică a tabelului de adevăr pentru formula A (x1, x2, xn) pentru nul mare este obscură.
Există o altă modalitate prin care, fără a folosi tabelul de adevăr, este posibil să determinăm la ce clasă se folosește formula A. Această metodă se bazează pe aducerea formulei la forma normală (CNF sau DNP) și folosind un algoritm care vă permite să determinați dacă formula dată identic adevărat sau nu. În același timp, se rezolvă problema dacă formula A este fezabilă.
Să presupunem că avem un criteriu pentru adevărul de identitate pentru formulele algebrei logice. Luați în considerare mecanismul aplicării sale.
Aplicăm criteriul adevărului identic cu formula A. Dacă se dovedește că formula A este identică, atunci problema este rezolvată. Dacă se dovedește că formula A nu este identică, atunci aplicăm criteriul adevărului identic cu formula. Dacă se dovedește că formula A este identică, atunci este clar că formula este identică, iar problema este rezolvată.
Dacă formula nu este identică, atunci rămâne singurul rezultat posibil: formula A este completă.
Acum stabilim un criteriu pentru identitatea unei formule arbitrare a algebrei logice. În acest scop, mai întâi formulăm și dovedim un criteriu pentru adevărul identității unei disjuncții elementare.
Teoremă 1. Pentru ca disjuncția elementară să fie identică, este necesar și suficient să conțină o variabilă și negarea ei.
Dovada. Necesitate. Fie ca disjuncția elementară să fie identică, dar în același timp unele variabile și negarea lor nu intră în ea. Dăm fiecărei variabile care intră în disjuncția elementară fără semnul negării, valoarea este falsă și fiecare variabilă care intră în disjuncția elementală sub semnul negării este valoarea "adevărată". Apoi, evident, întreaga disjuncție elementară va lua valoarea unei minciuni, care contrazice condiția.
Suficiență. Acum permiteți disjuncția elementară să conțină o variabilă și negarea ei. Deci, cum. atunci întreaga disjuncție elementară va fi identică.
Criteriul pentru adevărul identității unei disjuncții elementare ne permite să formăm și să dovedim criteriile pentru identitatea unei formule arbitrare a algebrului logicii.
Teorema 2. Pentru formula algebră a logicii A care să fie identică, este necesar și suficient ca orice disjuncție elementară care apare în CNF A să conțină o variabilă și negarea ei.
Dokazatelstvo.Neobhodimost. Fie A identic adevărat. Apoi CNF A este același cu adevărul. Dar CNF AA1 A2 . An, unde A, sunt disjuncții elementare (i = 1,2, N). Deoarece CNF A 1, atunci Ai 1 (i = 1,2, N). Dar apoi, prin Teorema 1, fiecare disjuncție elementară Ai conține o variabilă și negarea ei.
Suficiență. Fie orice disjuncție elementară Ai. Un membru al CNF A conține o variabilă și negarea ei. Apoi, prin Teorema 1 (i = 1,2. N). În acest caz, CNF.
De exemplu, vom afla dacă formula este identică.
Deoarece, este clar că fiecare disjuncție elementară și. Un membru al CNF A conține o variabilă și negarea ei. Prin urmare, A 1.
În mod similar, se poate stabili un criteriu pentru identitatea formulei algebrei logice care să fie identic falsă, folosind DNF-ul său.
Teorema 3. Pentru a se asigura că conjunctura elementară este identică, este necesar și suficient să conțină variabila și negarea ei.
Teorema 4. Pentru formula algebră a logicii A să fie identic falsă, este necesar și suficient ca orice conjuncție care apare în DNP A să conțină o variabilă și negarea ei.
Articole similare
Trimiteți-le prietenilor: