Lăsa s ia valorile 0 sau 1, adică s {0, 1}.
Să introducem notația:
x s = Ø X, dacă s = 0, x s = X, dacă s = 1.
Acestea. X 0 = Ø X, X 1 = X.
Este evident că x s= 1 dacă X = sși x s= 0 dacă X s.
Teorema 4.5(despre extinderea unei funcții booleene în variabile).
Fiecare funcție booleană f(X 1 , X 2 , ... , x n) poate fi reprezentat ca:
f(X 1 , X 2 , ... , x n) = f(X 1 , X 2 , ... , x m, x m +1 , ... , x n) =
V X 1 s 1 &X 2 s 2 &...&x m sm& f(s 1 , s 2 , ... s m, x m +1 , ... , x n), (4.1)
m n, unde disjuncția este preluată peste toate mulțimile ( s 1 , s 2 , ... , s m) (sunt 2 m).
De exemplu, pentru m = 2, n= 4 extinderea (4.1) include patru (2 m= 2 2 =4) conjuncție și are forma:
f(X 1 , X 2 , X 3 , X 4) = X &X &f(0, 0, X 3 , X 4) V X &X &f(0, 1, X 3 , X 4) V X & X &f(1, 0, X 3 , X 4) V X & X &f(1, 1, X 3 , X 4) = Ø X 1&Ø X 2 &f(0, 0, X 3 , X 4) V X 1 &X 2 &f(0, 1, X 3 , X 4) V X 1&Ø X 2 &f(1, 0, X 3 , X 4) V X 1 &X 2 &f(1, 1, X 3 , X 4).
Demonstrarea teoremei 4.5.
Teorema va fi demonstrată dacă arătăm că egalitatea (4.1) este valabilă pentru un set arbitrar de variabile ( y 1, y 2 , ... , y m, y m +1 , ... , y n) .
Inlocuim acest set arbitrar de variabile in laturile stanga si dreapta ale egalitatii (4.1).
Pe partea stângă ajungem f (y 1, y 2 , ... , y n) .
T. la. y s= 1 numai când y = s, apoi printre 2 m conjuncţii y 1 s 1 &y 2 s 2 &...&y m smîn partea dreaptă a (4.1) doar unul se transformă în 1 - cel în care y 1 = s 1 ,…, y m = s m. Toate celelalte conjuncții sunt egale cu 0. Prin urmare, în partea dreaptă a (4.1) obținem:
y 1 y 1 &y 2 y 2 &...&aa aa&f(y 1, y 2 , ... , y m, y m +1 , ... , y n) = f(y 1, y 2 , ... , y n) .
Teorema 4.5 este demonstrată.
Teorema 4.6(despre reprezentarea unei funcții booleene printr-o formulă în SDNF),
Orice funcție booleană f(X 1 , X 2 , ... , x n), care nu este identic egal cu 0, poate fi reprezentat printr-o formulă în SDNF, care este determinată în mod unic până la o permutare a termenilor disjunctivi.
Dovada.
La m = n obținem un corolar important al teoremei 4.5:
f(X 1 , X 2 , ... , x n) = V X 1 s 1 &X 2 s 2 &...&x n sn, (4.2)
f(s 1 , s 2 , ... , s n) = 1
unde disjuncția este preluată peste toate mulțimile ( s 1 , s 2 , ... , s n), Unde f = 1.
Este evident că expansiunea (4.2) nu este altceva decât SDNF-ul formulei f, care conține atâtea conjuncții câte unități există în tabelul de valori f. În consecință, SDNF pentru orice funcție booleană este unică până la o permutare a termenilor săi disjunctivi.
De asemenea, este evident că pentru funcția booleană f(X 1 , X 2 , ... , x n) identic egal cu 0, expansiunea (2) nu există.
Având în vedere cele de mai sus, pentru a obține formula funcției booleene f(X 1 , X 2 , ... , x n) în SDNF, putem folosi următorul algoritm.
Algoritmul 4.3. (Algoritm pentru reprezentarea unei funcții booleene dată de un tabel, o formulă în SDNF).
Pasul 1. s 1 , s 2 , ... , s n, pentru care valoarea f este egal cu 1, adică f (s 1 , s 2 , ... , s n) = 1.
Pasul 2 Pentru fiecare astfel de set (rânduri ale tabelului), compunem o conjuncție X 1 s 1 &X 2 s 2 &...&x n sn, Unde x i si = x i, dacă s i= 1 și x i si =Ø x i, dacă s i = 0, i = 1, 2, ... ,n.
Pasul 3 Facem o disjuncție a tuturor conjuncțiilor rezultate. Rezultatul este o formulă pentru această funcție în SDNF.
Exemplul 4.15.
Găsiți o formulă în SDNF pentru funcție f(X 1 , X 2 , X 3) dat de Tabelul 4.4.
f(X 1 , X 2 , X 3) =1. Acesta este al 4-lea, al 5-lea. a 6-a și a 8-a rânduri.
2. Pentru fiecare rând selectat facem conjuncții după regula specificată la pasul 2. Obținem, respectiv, pentru cele patru rânduri selectate:
X 1 0 &X 2 1 &X 3 1 = Ø X 1 &X 2 &X 3 .
X 1 1 &X 2 0 &X 3 0 = X 1&Ø X 2&Ø X 3 .
X 1 1 &X 2 0 &X 3 1 = X 1&Ø X 2 &X 3 .
X 1 1 &X 2 1 &X 3 1 = X 1 &X 2 &X 3 .
3. Facem o disjuncție a tuturor conjuncțiilor rezultate și găsim SDNF:
f(X 1 , X 2 , X 3) = Ø X 1 &X 2 &X 3V X 1&Ø X 2&Ø X 3V X 1&Ø X 2 &X 3V X 1 &X 2 &X 3 .
Ne asigurăm că această expresie coincide cu reprezentarea formulei noastre în SDNF obținută mai devreme în Exemplul 4.13.
Cometariu. Dacă o funcție booleană este dată de o formulă în SDNF, atunci aplicând algoritmul 4.3 în ordine inversă, putem obține cu ușurință un tabel de valori pentru această funcție.
Teorema 4.7(despre reprezentarea unei funcții booleene printr-o formulă în SKNF),
Orice funcție booleană f(X 1 , X 2 , ... , x n), care nu este identic egal cu 1, poate fi reprezentat printr-o formulă în SKNF, care este determinată în mod unic până la o permutare a termenilor disjunctivi.
Dovada.
Luați în considerare funcția Ø f(X 1 , X 2 , ... , x n). Conform teoremei 4.6, dacă nu este identic egal cu 0, atunci există o formulă pentru el în SDNF. Să notăm această formulă F unu . Evident, condiția ca funcția Ø f(X 1 , X 2 , ... , x n) nu este identic egal cu 0, este echivalent cu condiția ca funcția f(X 1 , X 2 , ... , x n) nu este identic egal cu 1. În plus, conform legii de Morgan, formula F 2ºØ F 1 este în SKNF (negația unei conjuncții este o disjuncție a negațiilor). Conform legii dublei negaţii
F 2ºØ F 1ºØØ f(X 1 , X 2 , ... , x n) º f(X 1 , X 2 , ... , x n),
care demonstrează teorema.
Pentru a obține formula funcției booleene f(X 1 , X 2 , ... , x n) în SKNF, ar trebui utilizat următorul algoritm.
Algoritmul 4.4. (Algoritm pentru reprezentarea unei funcții booleene dată de un tabel, o formulă în SKNF)
Pasul 1. Selectați toate seturile de variabile din tabel s 1 , s 2 , ... , s n, pentru care valoarea f (s 1 , s 2 , ... , s n) = 0.
Pasul 2 Pentru fiecare astfel de set (rânduri ale tabelului), compunem o disjuncție
X 1Ø s 1V X 2 Ø s 2V...V x n Ø sn, Unde x i Ø si = x i, dacă s i= 0 și x i Ø si = Ø x i, dacă s i = 1, i = 1, 2, ... , n.
Pasul 3 Compunem conjuncția tuturor disjuncțiilor rezultate. Rezultatul este SKNF.
Exemplul 4.16.
Găsiți o formulă în SKNF pentru funcție f(X 1 , X 2 , X 3) dat de Tabelul 4.4.
1. Selectați rândurile din tabel unde f(X 1 , X 2 , X 3) = 0. Acestea sunt liniile 1, 2 și 3 și 7.
2. Pentru fiecare rând selectat facem disjuncții după regula specificată la pasul 2. Obținem, respectiv, pentru cele trei rânduri selectate:
X 1 1V X 2 1V X 3 1 = X 1V X 2V X 3 .
X 1 1V X 2 1V X 3 0 = X 1V X 2V X 3 .
X 1 1V X 20 V X 3 1 = X 1V X 2V X 3 .
X 1 0V X 20 V X 3 1 = Ø X 1V X 2V X 3 .
3. Facem o conjuncție a tuturor disjuncțiilor obținute și găsim SKNF:
f(X 1 , X 2 , X 3) = (X 1V X 2V X 3)&(X 1V X 2V X 3)&(X 1V X 2V X 3)&(Ø X 1V X 2V X 3).
Această expresie coincide cu reprezentarea formulei noastre în SKNF obținută mai devreme în Exemplul 4.14.
Cometariu. Pentru că există 2 rânduri în tabelul de funcții n, atunci dacă numărul de termeni disjunctivi din SDNF este egal cu p, iar numărul de termeni conjunctivi din SKNF este egal cu q, atunci p+q=2n.
Deci, pentru funcția considerată în exemplele 4.15 și 4.16, n = 3, p = 4, q = 4, p + q = 8 = 2 3 .
Luați în considerare problema reprezentării n-funcția booleană locală f(X 1 ,X 2 ,…,X n) printr-o formulă de algebră propozițională.
Să introducem notația, unde este un parametru egal cu 0 sau 1.
Este evident că 
Teorema 1.1. Fiecare funcție a algebrei logiciif(X 1 , X 2 ,…, X n ) pentru oricem(1£ m £ n) poate fi reprezentat sub următoarea formă:
unde disjuncția este preluată peste toate seturile posibile de valori ale variabilelor.
Dovada. Luați în considerare un set arbitrar de valori ale tuturor variabilelor unei anumite funcții. Să arătăm că pe acest set părțile din stânga și din dreapta ale formulei (1) au aceeași valoare. Partea stângă este 
, dreapta
deoarece , dacă numai , dacă , atunci termenul logic corespunzător poate fi aruncat.
cometariu. Reprezentarea funcției specificate în teoremă se numește extinderea funcției în termeni de m variabile .
Corolarul 1(extindere într-o variabilă).
În acest caz, funcțiile 
și 
numit componente de descompunere.
Consecința 2(extindere în toate variabilele).
Este evident că dacă 
, atunci
Deci, dacă funcția f(X 1 ,X 2 ,…,X n) nu este o funcție falsă identic, atunci poate fi exprimată printr-o formulă echivalentă, care este o sumă logică a diferiților produse de forma , iar o astfel de reprezentare este unică.
Forma formulei (2) poate fi foarte simplificată. Se știe că orice formulă a algebrei logicii poate fi redusă prin intermediul transformărilor echivalente la o formulă care conține numai conjuncție și negație sau disjuncție și negație. Ca urmare a efectuării transformărilor echivalente, pot fi obținute mai multe formule, însă numai una dintre ele va avea următoarele proprietăți:
1. Fiecare termen logic conține toate variabilele incluse în formulă f(X 1 ,X 2 ,…,X n).
2. Niciun termen logic nu conține atât o variabilă, cât și negația acesteia.
3. Toți termenii logici din formulă sunt diferiți.
4. Niciun termen logic nu conține aceeași variabilă de două ori.
Aceste patru proprietăți sunt numite proprietăți ale perfecțiunii(sau proprietățile lui C).
Dacă f(X 1 ,X 2 ,…,X n) este dat de tabelul de adevăr, atunci formula de algebră logică corespunzătoare poate fi restaurată destul de simplu. Pentru toate valorile argumentului X 1 ,X 2 ,…,X n, la care f ia valoarea 1, trebuie să scrieți conjuncția variabilelor elementare ale propozițiilor, luând pentru termenul conjuncției x i, dacă x i=1, iar dacă x i=0. Disjuncția tuturor conjuncțiilor înregistrate va fi formula necesară. Despre valori f 0 nu trebuie să vă faceți griji, pentru că termenul corespunzător din formulă va fi egal cu 0 și poate fi aruncat din cauza echivalenței fÚ 0 ≡ f.
De exemplu, lăsați funcția f(X, y, z) are următorul tabel de adevăr:
|
X |
y |
z |
f(X, y, z) |
Selectăm variabila x 1 și considerăm funcția f în raport cu aceasta.
Întregul set de seturi tabelul de adevăr este împărțit în două subseturi, fiecare având patru seturi<0, a 2 , a 3 >și<1, a 2 , a 3 >.
Atunci funcția f(x 1, x 2, x 3) poate fi reprezentată ca o disjuncție a două funcții a două variabile, iar această formulă va arăta astfel:
Luați în considerare următoarele formule:
Partea stângă a primei formule este echivalentă cu cea dreaptă, deoarece pentru x 1 =0 și în conformitate cu operația de conjuncție. Valabilitatea celei de-a doua formule poate fi arătată în mod similar. Astfel, punând aceste formule în disjuncția anterioară, obținem:
Această expresie se numește extinderea funcției f(x 1 ,x 2 ,x 3) în raport cu variabila x 1 .
Acum, în mod similar, putem extinde funcțiile f(0,x 2 ,x 3) și f(1,x 2 ,x 3) în x 2 . obține
Înlocuind aceste formule în cele anterioare, obținem
În conformitate cu distributivitatea operației &, introducem variabila x 1 și inversarea acesteia între paranteze, obținem
În general, pentru o funcție f(x 1 ,x 2 ,..,x n) a n variabile, expansiunea în m variabile (m £ n) are forma
unde disjuncția este preluată pe toate cele 2 m seturi de variabile x 1 ,x 2 ,..,x m .
Se consideră descompunerea (*4) în cazul extrem când m=n. (vezi exemplul (*3)).
Apoi, în toate conjuncțiile, valorile funcției f pe fiecare mulțime fixă au valori egale cu zero sau unu. Înlăturând toate conjuncțiile zero, obținem o nouă descompunere, iar în această nouă descompunere eliminăm factorii funcțiilor din conjuncții, deoarece sunt egale cu 1. Expresia rămasă se numește CDNF (forma normală disjunctivă perfectă).
Să facem toate acestea de exemplu (*3).
După eliminarea din (*3) conjuncții cu valori zero ale funcției f pe mulțimile date, obținem:
Din moment ce conform tabelului de adevăr
f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1
apoi din conjuncții eliminăm factorii funcțiilor, după care obținem:
Aceasta este forma normală disjunctivă perfectă a funcției booleene f.
Lema. Orice funcție booleană (cu excepția constantei „0”) are un PDNF și doar unul.
În mod similar, puteți introduce forma conjunctivă,
Construcția SDNF pentru o funcție dată de un tabel
Acest corolar este constructiv, deoarece conform tabelului de funcții, vă permite să construiți o formulă care este SDNF (dacă).
funcții sdnf f conține exact atâtea conjuncții câte sunt în tabel f; la fiecare set „singur”. (d 1 ,…,d n), acestea. multimea la care valoarea functiei este egala cu 1 corespunde conjunctiei tuturor variabilelor in care x i luat cu un negativ dacă d i=0, și fără negație dacă d i =1.
Mulțimea B, pe care sunt definite două operații binare (conjuncție și disjuncție) și o operație unară (negație) și sunt alocate două elemente 0 și 1, se numește algebră booleană.
În plus, pentru aceste operațiuni, trebuie îndeplinite următoarele proprietăți:
Asociativitatea
comutativitatea
Distributivitatea conjuncției în raport cu disjuncția
Distributivitatea disjuncției în raport cu conjuncția
Idempotenta
De două ori nu
Proprietăți constante
De Morgan guvernează
Legea contradicției
Legea mijlocului exclus
În algebra logicii, aceste legi se numesc echivalențe.
Forme normale perfecte
Forma normală disjunctivă perfectă
Să introducem notația:
; A A =1; X A =1 dacă X=A, X A =0 dacă XA.
Formula X A 1…… X A n , unde A=- orice mulțime binară, iar dintre variabilele Xi poate fi aceeași se numește conjuncție elementară.
Orice disjuncție a conjuncțiilor elementare se numește formă normală disjunctivă (DNF).
O conjuncție elementară se numește corectă dacă fiecare variabilă apare cel mult o dată în ea (inclusiv apariția ei sub semnul negației).
De exemplu: 1) (pictograma conjuncție este omisă în acest caz).
1),4) sunt conjuncții elementare regulate;
2) - variabila x intra o data de la sine si a doua oara sub semnul negatiei;
Variabila y apare de trei ori: o dată singură și de două ori sub semnul negației.
O conjuncție elementară corectă se numește completă față de variabilele x 1 ... .. x n dacă include fiecare dintre aceste variabile și o singură dată (poate exista și un semn de negație).
De exemplu: dintre conjuncțiile enumerate în exemplul anterior, doar 4) sunt complete față de variabilele x, y, z, t; iar în ceea ce privește variabilele x,y,z doar 1 este complet).
O formă normală disjunctivă perfectă (PSNF) cu privire la variabilele x 1 ..... xn este o formă normală disjunctivă în care nu există conjuncții elementare identice și toate conjuncțiile elementare sunt corecte și complete în ceea ce privește variabilele x 1... ..xn
Expansiune variabilă
Teorema 1. Orice funcție logică poate fi reprezentată în SDNF:
unde m, iar disjuncția este preluată peste toate cele 2 m seturi de valori ale variabilelor x 1 ,…x m . Funcția f este extinsă în primele n-variabile. Această egalitate se numește expansiune în variabile. x 1 ,... x m . De exemplu, pentru n=4, m=2, descompunerea arată astfel:
teorema se demonstrează prin înlocuirea unei mulțimi arbitrare (b 1 ,…,b m , b m+1 ,…,b n) a tuturor n-variabilelor în ambele părți ale egalității (1).
Pentru m = 1, din (1) obținem extinderea funcției într-o variabilă:
Evident, o expansiune similară este valabilă pentru oricare dintre n-variabile.
Un alt caz important este atunci când n=m. În acest caz, toate variabilele din partea dreaptă a (1) obțin valori fixe, iar funcțiile din conjuncția părții drepte devin egale cu 0 sau 1, ceea ce dă:
unde disjuncția este preluată peste toate mulțimile (b 1 …b n) pe care f=1. Pentru f=0, mulțimea de conjuncții din partea dreaptă este goală. O astfel de descompunere se numește formă normală disjunctivă perfectă. SDNF al funcției f conține exact atâtea conjuncții câte există în tabelul de adevăr al lui f. Fiecare mulțime de unități (b 1 ,…, b n) corespunde conjuncției tuturor variabilelor, în care x i este luat cu negație dacă b i =0 b , și fără negație dacă b i =1. Astfel, există o corespondență unu-la-unu între tabelul de adevăr al funcției f și SDNF-ul acesteia și, prin urmare, SDNF pentru orice funcție logică este unic. Singura funcție care nu are un SDNF este constanta 0.
Teorema 2. Orice funcție logică poate fi reprezentată ca o formulă booleană.
Într-adevăr, pentru orice funcție, cu excepția constantei 0, SDNF-ul său poate servi ca o astfel de reprezentare. Constanta 0 poate fi reprezentată printr-o formulă booleană.
Descompunerea funcţiilor booleene în variabile.
Fie G un parametru egal cu 0 sau 1. Să introducem notația:
Este ușor de verificat verificând asta X G = 1 dacă și numai dacă X= G. Rezultă că conjuncția este egală cu 1 (aici G este egal cu 0 sau 1) dacă și numai dacă 
. De exemplu, conjuncția (în care G 2 \u003d G 1 \u003d 0, G 3 \u003d G 4 \u003d 1) este 1 numai dacă X 1 = X 2 = 0, X 3 = X 4 = 1.
Teorema 1Orice funcție booleană f(x 1 ,x 2 ,…,x n) trebuie reprezentată în următoarea formă:
unde 1 ≤ k ≤ n, în disjuncție este preluată toate seturile de valori variabile.
Această reprezentare se numește extinderea funcției în termeni de variabile. De exemplu, pentru n = 4, k = 2, expansiunea (3.1) are forma:
.
Să demonstrăm expansiunea (3.1). Pentru a face acest lucru, luați un set arbitrar de valori variabile 
. Să arătăm că laturile stângă și dreaptă ale relației (3.1) iau aceeași valoare. Într-adevăr, din moment ce X G = 1 dacă și numai dacă X= G, atunci dintre 2 o singură conjuncție a părții din dreapta a (3.1) se transformă în unitate, în care 
. Toate celelalte conjuncții sunt egale cu zero.
Din acest motiv . Ca un corolar al expansiunii (3.1), obținem următoarele două expansiuni speciale.
Expansiune variabilă X n:
Dacă funcția booleană nu este o constantă 0, atunci expansiunea este validă
Extindere în toate variabilele:
, 
(3.3)
unde disjuncţia este preluată asupra tuturor mulţimilor 
, pentru care valoarea funcției 
este egal cu 1.
Descompunerea (3.3) este de obicei numită forma normală disjunctivă perfectă (notația abreviată SDNF) a funcției.
Descompunerea (3.3) oferă o modalitate de a construi un SDNF. Pentru a face acest lucru, în tabelul de adevăr, marcați toate rândurile , in care . Pentru fiecare astfel de rând, formăm o conjuncție și apoi conectăm toate conjuncțiile rezultate cu un semn de disjuncție.
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, există o corespondență unu-la-unu între tabelul de adevăr al unei funcții și SDNF-ul ei. Și aceasta înseamnă că SDNF pentru funcția booleană este unică.
O singură funcție booleană care nu are un sdnf este constanta 0.
Exemplul 1 Găsiți forma disjunctivă perfectă pentru o funcție 
.
Să facem un tabel de adevăr pentru această funcție:
| |
|||||
De aici obținem: = = .
Un rol important în algebra logicii îl joacă următoarea descompunere a funcțiilor booleene.
Teorema 2Orice funcție booleană trebuie prezentat sub următoarea formă:
unde 1≤k≤n și se ia conjuncția peste toate cele 2 k seturi de valori variabile.
Într-adevăr, să este un set arbitrar de valori variabile. Să arătăm că părțile din stânga și din dreapta relației (3.4) iau aceeași valoare. Din moment ce numai când , atunci printre 2 k disjuncții 
în partea dreaptă a (3.4) dispare doar unul, în care . Toate celelalte disjuncții sunt egale cu 1.
Din acest motiv 
= = .
Expansiunile funcțiilor booleene decurg direct din extinderea (3.4):
Ultima descompunere se numește forma normală conjunctivă perfectă (CKNF). Descompunerea (3.6) oferă o modalitate de a construi SKNF. Pentru a face acest lucru, în tabelul de adevăr, marchem toate rândurile în care. Pentru fiecare astfel de rând, formăm o disjuncție 
și apoi conectăm toate conjuncțiile rezultate cu un semn de conjuncție. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, există o corespondență unu-la-unu între tabelul de adevăr al unei funcții și SKNF-ul ei. Și aceasta înseamnă că SKNF pentru funcția booleană este unică.
Singura funcție booleană care nu are SKNF este constanta 1.
Exemplul 2 Găsiți forma normală conjunctivă perfectă pentru o funcție 
.
Să facem un tabel de adevăr pentru această funcție.
| |
|||||
De aici obținem SKNF
Formula formular (notație scurtă), unde 
- conjuncţii 
numit forma normală disjunctivă (DNF).
În virtutea definiției de mai sus a DNF, vor exista, de exemplu, expresii: , .
După cum s-a menționat în paragraful 2.2, toate operațiile logice pot fi reduse la trei: conjuncții, disjuncții și negări. Mai mult, având în vedere legea lui de Morgan, se poate presupune că semnul de negație se aplică doar variabilelor.
Acum, folosind legea distributivă, deschidem parantezele și obținem forma normală disjunctivă. Deci, următoarea teoremă este adevărată.
Teorema 3 Pentru orice formulă a algebrei logicii, există o formă normală disjunctivă echivalentă cu aceasta.
Demonstrarea acestei teoreme oferă o modalitate de a construi o formă normală disjunctivă pentru orice formulă din algebra logicii.
Exemplul 3 Găsiți forma normală disjunctivă pentru următoarea formulă: 
.
Excluzând semnul prin lege 
și aplicând legile lui de Morgan și negația dublă, obținem:
Apoi, aplicând legea distributivității, extindem parantezele
Ultima expresie este forma normală disjunctivă.
Vizualizare formular 
(notație scurtă), unde sunt disjuncțiile 
numit forma normală conjunctivă (CNF).
Acestea sunt, de exemplu, expresii:
, .
După cum se arată mai sus, pentru orice formulă a algebrei logicii există o formă disjunctivă echivalentă cu aceasta. Folosind legea distributivă, este ușor să obțineți un CNF de la un DNF dat.
Deci, următoarea teoremă este adevărată.
Teorema 4 Pentru orice formulă a algebrei logicii, există o formă normală conjunctivă echivalentă cu aceasta.
Demonstrarea acestei teoreme oferă o modalitate de a construi o formă normală conjunctivă pentru orice formulă din algebra logicii.
Exemplul 4 Găsiți forme normale disjunctive și conjunctive pentru următoarea formulă: .
Folosind legea 
, excludem semnul . Primim formula.
Folosind legea lui de Morgan, obținem formula 
. Extinzând parantezele, obținem forma normală disjunctivă
.
Pentru a obține forma conjunctivă normală, aplicați formulei legea distributivă, obținem:
Ultima expresie este forma normală conjunctivă. Deoarece și , CNF rezultat este echivalent cu următorul CNF:
Dintre toate formulele normale ale acestei formule, evidențiem forma normală perfectă, atât disjunctivă, cât și conjunctivă. Având în vedere expansiunea (3), este ușor de observat că forma normală disjunctivă perfectă a unei formule a algebrei logicii care conține exact n variabile distincte este forma sa normală disjunctivă, în care:
1) toate conjuncțiile sunt distincte perechi;
2) fiecare conjuncție conține exact n variabile;
3) în fiecare conjuncție există toate n variabile.
În Exemplul 1, am luat în considerare una dintre modalitățile de a construi un SDNF bazat pe compilarea unui tabel de adevăr. Următorul mod de a construi SDNF se bazează pe aplicarea legilor algebrei logicii.
Exemplul 5 Găsiți forma disjunctivă perfectă a formulei.
Folosind asta , primim . Având în vedere legile lui de Morgan și dubla negație, am obținut o formă normală disjunctivă. Acest DNF este echivalent cu formula .
Extinzând parantezele, obținem: .
Folosind legea idempotentei, obținem SDNF necesar:
Ținând cont de descompunerea (3.6), este ușor de observat că forma normală conjunctivă perfectă a formulei algebrei logicii care conține exact n diferite variabile, există forma sa normală conjunctivă, în care:
1) toate disjuncțiile sunt distincte perechi;
2) fiecare disjuncție conține exact n membri; identic adevărat, dacă capătă valoarea Adevărat.
Exemple de formule identice adevărate sunt formulele:
identic fals, dacă acesta, cu toate valorile variabilelor incluse în el, ia valoarea Minciuna.
Exemple de formule identice false sunt formulele:
Formula algebrei logicii este de obicei numită realizabil, dacă pentru unele valori ale variabilelor incluse în acesta, ia valoarea Adevărat.
Exemple de formule fezabile sunt următoarele formule:
În algebra logicii, se poate pune următoarea problemă: a indica o metodă (algoritm) care să permită fiecărei formule a algebrei logicii să afle dacă este identic adevărată sau nu. Sarcina este numită probleme de rezolvare.
Luați în considerare următoarele două moduri de a rezolva această problemă.
Metoda 1 (tabel) Pentru a determina dacă o formulă dată este identic adevărată sau nu, este suficient să compilați tabelul său de adevăr.
În același timp, această metodă, deși oferă o soluție fundamentală la problema solubilității, este destul de greoaie.
Metoda 2 pe baza reducerii formulelor la forma normală.
Teorema 4O formulă a algebrei logicii este identic adevărată dacă și numai dacă fiecare disjuncție în forma sa normală conjunctivă conține o variabilă împreună cu negația sa.
Într-adevăr, dacă fiecare disjuncție în formă normală conjunctivă conține o variabilă împreună cu negația ei, atunci toate disjuncțiile sunt egale cu 1, deoarece , . Rezultă că CNF este identic adevărat.
Fie acum formula dată să fie identic adevărată și fie 
există o oarecare disjuncție în CNF a acestei formule. Să presupunem că disjuncția dată nu conține o variabilă împreună cu negația ei. În acest caz, putem da valoarea 0 fiecărei variabile care nu se află sub semnul negației și valoarea 1 fiecărei variabile care se află sub semnul negației. După această înlocuire, toate disjuncțiile vor deveni egale cu 0, prin urmare, formula nu este identic adevărată. Avem o contradicție.
Exemplul 7 Aflați dacă formula este identic adevărată
.
Folosind asta , primim .
Aplicând legea distributivității obținem CNF:
Deoarece fiecare disjuncție conține o variabilă împreună cu negația ei, formula este identic adevărată.
Similar cu teorema anterioară, se demonstrează următoarea teoremă:
Teorema 5O formulă a algebrei logicii este în mod identic falsă dacă și numai dacă fiecare conjuncție în forma sa disjunctivă conține o variabilă împreună cu negația ei..
Descompunerea funcţiilor booleene în variabile. - concept și tipuri. Clasificarea și caracteristicile categoriei „Descompunerea funcțiilor booleene în variabile”. 2017, 2018.
