Neka s uzima vrijednosti 0 ili 1, tj. s {0, 1}.
Uvedimo oznaku:
x s = Ø x, ako s = 0, x s = x, ako s = 1.
Oni. x 0 = Ø x, x 1 = x.
Očito je da x s= 1 ako x = s i x s= 0 ako x s.
Teorem 4.5(o proširenju Booleove funkcije u varijablama).
Svaka Booleova funkcija f(x 1 , x 2 , ... , x n) može se predstaviti kao:
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, gdje se disjunkcija preuzima na sve skupove ( s 1 , s 2 , ... , s m) (postoje 2 m).
Na primjer, za m = 2, n= 4 proširenje (4.1) uključuje četiri (2 m= 2 2 =4) konjunkcija i ima oblik:
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).
Dokaz teorema 4.5.
Teorem ćemo dokazati ako pokažemo da jednakost (4.1) vrijedi za proizvoljan skup varijabli ( g 1, g 2 , ... , y m, y m +1 , ... , y n) .
Zamjenjujemo ovaj proizvoljni skup varijabli u lijevu i desnu stranu jednakosti (4.1).
S lijeve strane dobivamo f (g 1, g 2 , ... , y n) .
T. do. y s= 1 samo kada g = s, zatim među 2 m veznici g 1 s 1 &g 2 s 2 &...&y m sm na desnoj strani (4.1) samo jedan prelazi u 1 - onaj u kojem g 1 = s 1 ,…, y m = s m. Sve ostale konjunkcije jednake su 0. Stoga na desnoj strani (4.1) dobivamo:
g 1 g 1 &g 2 g 2 &...&ym ym&f(g 1, g 2 , ... , y m, y m +1 , ... , y n) = f(g 1, g 2 , ... , y n) .
Teorem 4.5 je dokazan.
Teorem 4.6(o predstavljanju Booleove funkcije formulom u SDNF-u),
Bilo koja Booleova funkcija f(x 1 , x 2 , ... , x n), koji nije identički jednak 0, može se predstaviti formulom u SDNF-u, koja je jedinstveno određena do permutacije disjunktivnih članova.
Dokaz.
Na m = n dobivamo važan korolar iz teoreme 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
gdje se disjunkcija preuzima na sve skupove ( s 1 , s 2 , ... , s n), gdje f = 1.
Očito je da proširenje (4.2) nije ništa drugo nego SDNF formule f, koji sadrži onoliko veznika koliko ima jedinica u tablici vrijednosti f. Posljedično, SDNF za bilo koju Booleovu funkciju je jedinstven do permutacije svojih disjunktivnih članova.
Također je očito da za Booleovu funkciju f(x 1 , x 2 , ... , x n) identički jednaka 0, dekompozicija (2) ne postoji.
S obzirom na navedeno, da bi se dobila formula Booleove funkcije f(x 1 , x 2 , ... , x n) u SDNF-u, možemo koristiti sljedeći algoritam.
Algoritam 4.3. (Algoritam za predstavljanje Booleove funkcije zadane tablicom, formula u SDNF-u).
Korak 1. s 1 , s 2 , ... , s n, za koju vrijednost f jednako 1, tj. f (s 1 , s 2 , ... , s n) = 1.
Korak 2 Za svaki takav skup (redove tablice) sastavljamo veznik x 1 s 1 &x 2 s 2 &...&x n sn, gdje x i si = x i, ako s i= 1 i x i si =Ø x i, ako s i = 0, ja = 1, 2, ... ,n.
3. korak Pravimo disjunkciju svih nastalih konjunkcija. Rezultat je formula za ovu funkciju u SDNF-u.
Primjer 4.15.
Pronađite formulu u SDNF-u za funkciju f(x 1 , x 2 , x 3) dano tablicom 4.4.
f(x 1 , x 2 , x 3) =1. Ovo je 4., 5. 6. i 8. redak.
2. Za svaki odabrani red pravimo veznike prema pravilu navedenom u koraku 2. Za četiri odabrana retka dobivamo:
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. Napravimo disjunkciju svih rezultirajućih konjunkcija i nađemo 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 .
Pazimo da se ovaj izraz podudara s prikazom naše formule u SDNF-u dobivenom ranije u primjeru 4.13.
Komentar. Ako je Booleova funkcija dana formulom u SDNF-u, a zatim primjenom algoritma 4.3 obrnutim redoslijedom, lako možemo dobiti tablicu vrijednosti za ovu funkciju.
Teorem 4.7(o predstavljanju Booleove funkcije formulom u SKNF-u),
Bilo koja Booleova funkcija f(x 1 , x 2 , ... , x n), koji nije identički jednak 1, može se predstaviti formulom u SKNF, koja je jedinstveno određena do permutacije disjunktivnih članova.
Dokaz.
Razmotrimo funkciju Ø f(x 1 , x 2 , ... , x n). Prema teoremu 4.6, ako nije identički jednak 0, onda za to postoji formula u SDNF. Označimo ovu formulu F jedan . Očito, uvjet da funkcija Ø f(x 1 , x 2 , ... , x n) nije identički jednaka 0, ekvivalentan je uvjetu da funkcija f(x 1 , x 2 , ... , x n) nije identički jednak 1. Osim toga, prema de Morganovom zakonu, formula F 2ºØ F 1 je u SKNF (negacija konjunkcije je disjunkcija negacija). Prema zakonu dvostruke negacije
F 2ºØ F 1ºØØ f(x 1 , x 2 , ... , x n) º f(x 1 , x 2 , ... , x n),
što dokazuje teorem.
Da biste dobili formulu Booleove funkcije f(x 1 , x 2 , ... , x n) u SKNF-u treba koristiti sljedeći algoritam.
Algoritam 4.4. (Algoritam za predstavljanje Booleove funkcije dane tablicom, formula u SKNF-u)
Korak 1. Odaberite sve skupove varijabli u tablici s 1 , s 2 , ... , s n, za koju vrijednost f (s 1 , s 2 , ... , s n) = 0.
Korak 2 Za svaki takav skup (redove tablice) sastavljamo disjunkciju
x 1Ø s 1V x 2 Ø s 2V...V x n Ø s n, gdje x i Ø si = x i, ako s i= 0 i x i Ø si = Ø x i, ako s i = 1, ja = 1, 2, ... , n.
3. korak Od svih nastalih disjunkcija sastavljamo konjunkciju. Rezultat je SKNF.
Primjer 4.16.
Pronađite formulu u SKNF-u za funkciju f(x 1 , x 2 , x 3) dano tablicom 4.4.
1. Odaberite retke u tablici gdje f(x 1 , x 2 , x 3) = 0. Ovo su 1., 2. i 3. i 7. redak.
2. Za svaki odabrani red pravimo disjunkcije prema pravilu navedenom u koraku 2. Za tri odabrana retka dobivamo:
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 20V x 3 1 = x 1V x 2V x 3 .
x 1 0V x 20V x 3 1 = Ø x 1V x 2V x 3 .
3. Napravimo konjunkciju svih dobivenih disjunkcija i nađemo 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).
Ovaj izraz podudara se s prikazom naše formule u SKNF-u dobivenom ranije u primjeru 4.14.
Komentar. Budući da u tablici funkcija postoje 2 retka n, onda ako je broj disjunktivnih članova u SDNF jednak str, a broj konjunktivnih članova u SKNF jednak je q, onda str+q=2n.
Dakle, za funkciju razmatranu u primjerima 4.15 i 4.16, n = 3, str = 4, q = 4, str + q = 8 = 2 3 .
Razmotrimo pitanje reprezentacije n-lokalna Booleova funkcija f(x 1 ,x 2 ,…,x n) nekom formulom propozicijske algebre.
Uvedimo oznaku, gdje je parametar jednak 0 ili 1.
Očito je da 
Teorem 1.1. Svaka funkcija algebre logikef(x 1 , x 2 ,…, x n ) za bilo kojim(1£ m £ n) može se predstaviti u sljedećem obliku:
gdje se disjunkcija preuzima na sve moguće skupove vrijednosti varijabli.
Dokaz. Razmotrite proizvoljan skup vrijednosti svih varijabli dane funkcije. Pokažimo da na tom skupu lijevi i desni dio formule (1) imaju istu vrijednost. Lijeva strana je 
, točno
jer , ako samo , ako , tada se odgovarajući logički termin može odbaciti.
Komentar. Prikaz funkcije navedene u teoremu naziva se proširenje funkcije u smislu m varijable .
Korolar 1(proširenje u jednoj varijabli).
U ovom slučaju funkcije 
i 
nazvao komponente razgradnje.
Posljedica 2(proširenje u svim varijablama).
Očito je da ako 
, onda
Dakle, ako funkcija f(x 1 ,x 2 ,…,x n) nije identično lažna funkcija, tada se može izraziti ekvivalentnom formulom, koja je logički zbroj različitih proizvoda oblika , a takav prikaz je jedinstven.
Oblik formule (2) može se znatno pojednostaviti. Poznato je da se bilo koja formula logičke algebre može reducirati pomoću ekvivalentnih transformacija na formulu koja sadrži samo konjunkciju i negaciju ili disjunkciju i negaciju. Kao rezultat provođenja ekvivalentnih transformacija može se dobiti nekoliko formula, ali samo jedna od njih će imati sljedeća svojstva:
1. Svaki logički termin sadrži sve varijable uključene u formulu f(x 1 ,x 2 ,…,x n).
2. Nijedan logički termin ne sadrži i varijablu i njezinu negaciju.
3. Svi logički pojmovi u formuli su različiti.
4. Nijedan logički termin ne sadrži istu varijablu dva puta.
Ova četiri svojstva nazivaju se svojstva savršenstva(ili svojstva C).
Ako a f(x 1 ,x 2 ,…,x n) dana tablicom istine, tada se odgovarajuća formula logičke algebre može vrlo jednostavno obnoviti. Za sve vrijednosti argumenata x 1 ,x 2 ,…,x n, na kojem f ima vrijednost 1, potrebno je zapisati konjunkciju elementarnih varijabli iskaza, uzimajući za termin konjunkcije x i, ako x i=1, a ako x i=0. Disjunkcija svih zabilježenih veznika bit će potrebna formula. O vrijednostima f 0 ne morate brinuti, jer odgovarajući član u formuli bit će jednak 0 i može se odbaciti zbog ekvivalencije fÚ 0 ≡ f.
Na primjer, neka funkcija f(x, g, z) ima sljedeću tablicu istinitosti:
|
x |
g |
z |
f(x, g, z) |
Odaberemo varijablu x 1 i promatramo funkciju f s obzirom na nju.
Cijeli set kompleta tablica istine je podijeljena u dva podskupa, od kojih svaki ima četiri skupa<0, a 2 , a 3 >i<1, a 2 , a 3 >.
Tada se funkcija f(x 1, x 2, x 3) može prikazati kao disjunkcija dviju funkcija dviju varijabli, a ova formula će izgledati ovako:
Razmotrite sljedeće formule:
Lijeva strana prve formule je ekvivalentna desnoj, jer je za x 1 =0 iu skladu s operacijom konjunkcije. Valjanost druge formule može se pokazati na sličan način. Dakle, stavljajući ove formule u prethodnu disjunkciju, dobivamo:
Taj se izraz naziva proširenje funkcije f(x 1 ,x 2 ,x 3) s obzirom na varijablu x 1 .
Sada, slično, možemo proširiti funkcije f(0,x 2 ,x 3) i f(1,x 2 ,x 3) u x 2 . Dobiti
Zamjenom ovih formula u prethodne, dobivamo
U skladu s distributivnošću operacije &, uvodimo varijablu x 1 i njezinom inverzijom u zagradu dobivamo
Općenito, za funkciju f(x 1 ,x 2 ,..,x n) od n varijabli, proširenje u m varijabli (m £ n) ima oblik
gdje je disjunkcija preuzeta preko svih 2 m skupova varijabli x 1 ,x 2 ,..,x m .
Razmotrimo dekompoziciju (*4) u ekstremnom slučaju kada je m=n. (vidi primjer (*3)).
Tada u svim konjunkcijama vrijednosti funkcije f na svakom fiksnom skupu imaju vrijednosti jednake nuli ili jedinici. Uklanjanjem svih nultih konjunkcija dobivamo novu dekompoziciju, au toj novoj dekompoziciji uklanjamo faktore funkcija u konjunkcijama, jer jednaki su 1. Preostali izraz naziva se CDNF (savršena disjunktivna normalna forma).
Napravimo sve ovo na primjer (*3).
Nakon uklanjanja iz (*3) konjunkcija s nultim vrijednostima funkcije f na danim skupovima, dobivamo:
Budući da prema tablici istine
f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1
zatim iz konjunkcija izbacimo faktore funkcija, nakon čega dobijemo:
Ovo je savršeni disjunktivni normalni oblik Booleove funkcije f.
Lema. Svaka Booleova funkcija (osim konstante "0") ima PDNF, i to samo jedan.
Slično, možete unijeti konjunktivni oblik,
Konstrukcija SDNF-a za funkciju zadanu tablicom
Ova posljedica je konstruktivna, jer prema funkcijskoj tablici, omogućuje vam konstruiranje formule koja je SDNF (ako je ).
sdnf funkcije f sadrži točno onoliko veznika koliko ih ima u tablici f; na svaki "pojedinačni" set (d 1 ,…,d n), oni. skup na kojem je vrijednost funkcije jednaka 1 odgovara konjunkciji svih varijabli u kojoj x i uzeto s negativnom ako d i=0, i bez negacije if d i =1.
Skup B na kojem su definirane dvije binarne operacije (konjunkcija i disjunkcija) i jedna unarna operacija (negacija) i odabrana dva elementa 0 i 1 naziva se Booleova algebra.
Štoviše, za ove operacije moraju biti zadovoljena sljedeća svojstva:
Asocijativnost
komutativnost
Distributivnost konjunkcije u odnosu na disjunkciju
Distributivnost disjunkcije u odnosu na konjunkciju
Idempotencija
Dvaput ne
Konstantna svojstva
De Morgan vlada
Zakon kontradikcije
Zakon isključene sredine
U logičkoj algebri ti se zakoni nazivaju ekvivalencije.
Savršene normalne forme
Savršeni disjunktivni normalni oblik
Uvedimo oznaku:
; A A = 1; X A =1 ako je X=A, X A =0 ako je XA.
Formula X A 1…… X A n, gdje je A=- bilo koji binarni skup, a među varijablama Xi može biti ista, naziva se elementarna konjunkcija.
Svaka disjunkcija elementarnih konjunkcija naziva se disjunktivna normalna forma (DNF).
Elementarna se konjunkcija naziva ispravnom ako se svaka varijabla u njoj pojavljuje najviše jednom (uključujući i pojavljivanje pod znakom negacije).
Na primjer: 1) (ikona veznika je u ovom slučaju izostavljena).
1),4) pravilni su elementarni veznici;
2) - varijabla x jednom ulazi sama, a drugi put pod predznakom negacije;
Varijabla y pojavljuje se tri puta: jednom sama i dva puta pod znakom negacije.
Ispravna elementarna konjunkcija naziva se potpunom s obzirom na varijable x 1 ... .. x n ako uključuje svaku od tih varijabli i samo jednom (može postojati i znak negacije).
Na primjer: od veznika navedenih u prethodnom primjeru samo su 4) potpune u odnosu na varijable x, y, z, t; a u odnosu na varijable x,y,z samo je 1 potpuna).
Savršena disjunktivna normalna forma (PDNF) s obzirom na varijable x 1 .....x n je disjunktivna normalna forma u kojoj nema identičnih elementarnih konjunkcija i sve su elementarne konjunkcije točne i potpune s obzirom na varijable x 1 . ....x n
Varijabilna ekspanzija
Teorem 1. Bilo koja logička funkcija može se predstaviti u SDNF:
gdje je m, a disjunkcija se preuzima preko svih 2 m skupova vrijednosti varijabli x 1 ,…x m . Funkcija f je proširena u prvih n-varijabli. Ova jednakost se naziva proširenje u varijablama. x 1 ,… x m . Na primjer, za n=4, m=2, dekompozicija izgleda ovako:
teorem se dokazuje zamjenom proizvoljnog skupa (b 1 ,…,b m , b m+1 ,…,b n) svih n-varijabli u obje strane jednakosti (1).
Za m = 1, iz (1) dobivamo proširenje funkcije u jednoj varijabli:
Očito, slično proširenje vrijedi za bilo koju od n-varijabli.
Drugi važan slučaj je kada je n=m. U ovom slučaju sve varijable s desne strane (1) dobivaju fiksne vrijednosti i funkcije u konjunkciji s desne strane postaju jednake 0 ili 1, što daje:
gdje se disjunkcija preuzima na sve skupove (b 1 …b n) na kojima je f=1. Za f=0, skup konjunkcija na desnoj strani je prazan. Takva se dekompozicija naziva savršena disjunktivna normalna forma. SDNF funkcije f sadrži točno onoliko konjunkcija koliko ih ima u tablici istinitosti funkcije f. Svaki skup jedinica (b 1 ,…, b n) odgovara konjunkciji svih varijabli, u kojoj se x i uzima s negacijom ako je b i =0 b , a bez negacije ako je b i =1. Dakle, postoji korespondencija jedan-na-jedan između tablice istinitosti funkcije f i njezinog SDNF-a, te je, prema tome, SDNF za bilo koju logičku funkciju jedinstven. Jedina funkcija koja nema SDNF je konstanta 0.
Teorem 2. Bilo koja logička funkcija može se prikazati kao Booleova formula.
Doista, za bilo koju funkciju, osim za konstantu 0, njezin SDNF može poslužiti kao takav prikaz. Konstanta 0 može se prikazati Booleovom formulom.
Dekompozicija Booleovih funkcija u varijablama.
Neka je G parametar jednak 0 ili 1. Uvedimo oznaku:
To je lako provjeriti provjerom toga x G = 1 ako i samo ako x= G. Slijedi da je konjunkcija jednaka 1 (ovdje je G jednako 0 ili 1) ako i samo ako 
. Na primjer, konjunkcija (u kojoj je G 2 \u003d G 1 \u003d 0, G 3 \u003d G 4 \u003d 1) je 1 samo ako x 1 = x 2 = 0, x 3 = x 4 = 1.
Teorem 1Bilo koja Booleova funkcija f(x 1 ,x 2 ,…,x n) mora biti predstavljena u sljedećem obliku:
gdje je 1 ≤ k ≤ n, u disjunkciji se preuzimaju svi skupovi vrijednosti varijable.
Taj se prikaz naziva proširenje funkcije u smislu varijabli. Na primjer, za n = 4, k = 2, proširenje (3.1) ima oblik:
.
Dokažimo proširenje (3.1). Da biste to učinili, uzmite proizvoljan skup vrijednosti varijabli 
. Pokažimo da lijeva i desna strana relacije (3.1) imaju istu vrijednost. Doista, budući da x G = 1 ako i samo ako x= G, tada između 2 samo jedna konjunkcija desne strane (3.1) prelazi u jedinicu, u kojoj 
. Sve ostale konjunkcije jednake su nuli.
Zbog ovog razloga . Kao korolar proširenja (3.1), dobivamo sljedeća dva posebna proširenja.
Varijabilna ekspanzija x n:
Ako Booleova funkcija nije konstanta 0, tada je proširenje valjano
Ekspanzija u svim varijablama:
, 
(3.3)
gdje se disjunkcija preuzima na sve skupove 
, za koju je vrijednost funkcije 
jednako 1.
Dekompozicija (3.3) obično se naziva savršeni disjunktivni normalni oblik (skraćeni zapis SDNF) funkcije.
Dekompozicija (3.3) daje način za konstrukciju SDNF-a. Da biste to učinili, označite sve retke u tablici istine , u kojem . Za svaki takav red formiramo veznik, a potom sve nastale veznike povezujemo disjunkcijskim znakom.
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, postoji podudarnost jedan na jedan između tablice istinitosti funkcije i njezin SDNF. A to znači da je SDNF za Booleovu funkciju jedinstven.
Jedna booleova funkcija koja nema sdnf je konstanta 0.
Primjer 1 Pronađite savršeni disjunktivni oblik za funkciju 
.
Napravimo tablicu istine za ovu funkciju:
| |
|||||
Odavde dobivamo: = = .
Važnu ulogu u algebri logike igra sljedeća dekompozicija Booleovih funkcija.
Teorem 2Bilo koja Booleova funkcija moraju biti predstavljeni u sljedećem obliku:
gdje je 1≤k≤n, a konjunkcija je uzeta preko svih 2 k skupova varijabilnih vrijednosti.
Doista, neka je proizvoljan skup vrijednosti varijable. Pokažimo da lijevi i desni dio relacije (3.4) imaju istu vrijednost. Budući da samo kada , tada među 2 k disjunkcija 
na desnoj strani (3.4) nestaje samo jedan, u kojem . Sve ostale disjunkcije jednake su 1.
Zbog ovog razloga 
= = .
Proširenja Booleovih funkcija slijede izravno iz proširenja (3.4):
Posljednja dekompozicija naziva se savršena konjunktivna normalna forma (CKNF). Dekompozicija (3.6) daje način da se konstruira SKNF. Da bismo to učinili, u tablici istine označimo sve retke u kojima . Za svaki takav red formiramo disjunkciju 
a zatim sve nastale veznike povezujemo vezničkim znakom. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, postoji podudarnost jedan na jedan između tablice istinitosti funkcije i njezin SKNF. A to znači da je SKNF za Booleovu funkciju jedinstven.
Jedina Booleova funkcija koja nema SKNF je konstanta 1.
Primjer 2 Pronađite savršeni konjunktivni normalni oblik za funkciju 
.
Napravimo tablicu istine za ovu funkciju.
| |
|||||
Odavde dobivamo SKNF
Formula oblika (kratka notacija), gdje 
- veznici 
nazvao disjunktivni normalni oblik (DNF).
Na temelju dane definicije DNF postojat će npr. izrazi: , .
Kao što je navedeno u paragrafu 2.2, sve logičke operacije mogu se svesti na tri: konjunkcija, disjunkcija i negacija. Štoviše, s obzirom na de Morganov zakon, može se pretpostaviti da se znak negacije primjenjuje samo na varijable.
Sada, koristeći zakon distribucije, otvaramo zagrade i dobivamo disjunktivnu normalnu formu. Dakle, sljedeća teorema je istinita.
Teorem 3 Za svaku formulu logičke algebre postoji disjunktivna normalna forma koja joj je ekvivalentna.
Dokaz ovog teorema daje način da se konstruira disjunktivni normalni oblik za bilo koju formulu u logičkoj algebri.
Primjer 3 Pronađite disjunktivni normalni oblik za sljedeću formulu: 
.
Zakonom se isključuje znak 
i primjenom de Morganovih zakona i dvostruke negacije, dobivamo:
Zatim, primjenom zakona distributivnosti, raširimo zagrade
Posljednji izraz je disjunktivni normalni oblik.
Prikaži obrazac 
(kratka notacija), gdje su disjunkcije 
nazvao konjunktivni normalni oblik (CNF).
To su, na primjer, izrazi:
, .
Kao što je gore pokazano, za bilo koju formulu logičke algebre postoji disjunktivni oblik koji joj je ekvivalentan. Koristeći zakon distribucije, lako je dobiti CNF iz zadane DNF.
Dakle, sljedeća teorema je istinita.
Teorem 4 Za svaku formulu algebre logike postoji konjunktivna normalna forma koja joj je ekvivalentna.
Dokaz ovog teorema daje način da se konstruira konjunktivni normalni oblik za bilo koju formulu u logičkoj algebri.
Primjer 4 Pronađite disjunktivne i konjunktivne normalne forme za sljedeću formulu: .
Korištenje zakona 
, isključujemo znak . Dobili smo formulu.
Koristeći de Morganov zakon dobivamo formulu 
. Proširivanjem zagrada dobivamo disjunktivnu normalnu formu
.
Da biste dobili konjunktivni normalni oblik, primijenite na formulu zakon distribucije, dobivamo:
Posljednji izraz je konjunktivni normalni oblik. Budući da je i , rezultirajuća CNF je ekvivalentna sljedećoj CNF:
Među svim normalnim formulama ove formule izdvajamo savršeni normalni oblik, disjunktivni i konjunktivni. Uzimajući u obzir dekompoziciju (3), lako je vidjeti da je savršeni disjunktivni normalni oblik formule algebre logike koja sadrži točno n različitih varijabli njezin disjunktivni normalni oblik, u kojem:
1) svi su veznici parno različiti;
2) svaka konjunkcija sadrži točno n varijabli;
3) u svakoj konjunkciji ima svih n varijabli.
U primjeru 1 razmotrili smo jedan od načina konstruiranja SDNF-a na temelju kompilacije tablice istinitosti. Sljedeći način konstruiranja SDNF-a temelji se na primjeni zakona algebre logike.
Primjer 5 Pronađite savršeni disjunktivni oblik formule.
Koristeći se time , dobivamo . S obzirom na de Morganove zakone i dvostruku negaciju, dobili smo disjunktivnu normalnu formu. Ovaj DNF je ekvivalentan formuli .
Proširivanjem zagrada dobivamo: .
Koristeći zakon idempotencije, dobivamo traženi SDNF:
Uzimajući u obzir dekompoziciju (3.6), lako je vidjeti da savršeni konjunktivni normalni oblik formule algebre logike sadrži točno n različitih varijabli, postoji njegov konjunktivni normalni oblik, u kojem:
1) sve su disjunkcije parno različite;
2) svaka disjunkcija sadrži točno n članova; identično je istinita ako poprima vrijednost pravi.
Primjeri identično istinitih formula su formule:
identično lažna, ako za sve vrijednosti varijabli koje su u njemu uključene, uzima vrijednost lažno.
Primjeri identično lažnih formula su formule:
Formula algebre logike obično se naziva izvodljiv, ako za neke vrijednosti varijabli koje su u njemu uključene, uzima vrijednost pravi.
Primjeri izvedivih formula su sljedeće formule:
U algebri logike može se postaviti sljedeći problem: naznačiti metodu (algoritam) koja omogućuje da se za svaku formulu algebre logike otkrije je li identično istinita ili ne. Zadatak se zove rješavanje problema.
Razmotrite sljedeća dva načina za rješavanje ovog problema.
Metoda 1 (tablica) Da bismo utvrdili je li određena formula identično istinita ili ne, dovoljno je sastaviti njezinu tablicu istinitosti.
U isto vrijeme, ova metoda, iako daje temeljno rješenje problema rješivosti, prilično je glomazna.
Metoda 2 na temelju svođenja formula na normalan oblik.
Teorem 4Formula algebre logike identično je istinita ako i samo ako svaka disjunkcija u svom konjunktivnom normalnom obliku sadrži neku varijablu zajedno sa svojom negacijom.
Doista, ako svaka disjunkcija u konjunktivnom normalnom obliku sadrži varijablu zajedno sa svojom negacijom, tada su sve disjunkcije jednake 1, jer , . Slijedi da je CNF identično istinit.
Neka je sada dana formula identično istinita i neka 
postoji neka disjunkcija u CNF ove formule. Pretpostavimo da dana disjunkcija ne sadrži varijablu zajedno s njezinom negacijom. U tom slučaju svakoj varijabli koja nije negativna možemo dati vrijednost 0, a svakoj varijabli koja je negativna vrijednost 1. Nakon ove zamjene sve će disjunkcije postati 0, dakle formula nije identično istinita. Imamo kontradikciju.
Primjer 7 Utvrdite je li formula identično istinita
.
Koristeći se time , dobivamo .
Primjenom zakona distributivnosti dobivamo CNF:
Budući da svaka disjunkcija sadrži neku varijablu zajedno sa svojom negacijom, formula je identično istinita.
Slično prethodnom teoremu, dokazuje se i sljedeći teorem:
Teorem 5Formula algebre logike je identično lažna ako i samo ako svaka konjunkcija u svom disjunktivnom obliku sadrži neku varijablu zajedno sa svojom negacijom.
Dekompozicija Booleovih funkcija u varijablama. - pojam i vrste. Klasifikacija i značajke kategorije "Dekompozicija Booleovih funkcija u varijablama." 2017., 2018. godine.
