Le te jete s merr vlerat 0 ose 1, d.m.th. s {0, 1}.
Le të prezantojmë shënimin:
x s = Ø x, nëse s = 0, x s = x, nëse s = 1.
ato. x 0 = Ø x, x 1 = x.
Është e qartë se x s= 1 nëse x = s Dhe x s= 0 nëse x s.
Teorema 4.5(mbi zgjerimin e një funksioni Boolean në variabla).
Çdo funksion boolean f(x 1 , x 2 , ... , x n) mund të përfaqësohet si:
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, ku disjuksioni merret mbi të gjitha grupet ( s 1 , s 2 , ... , s m) (janë 2 m).
Për shembull, për m = 2, n= 4 zgjerimi (4.1) përfshin katër (2 m= 2 2 =4) lidhëza dhe ka formën:
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).
Vërtetimi i teoremës 4.5.
Teorema do të vërtetohet nëse tregojmë se barazia (4.1) vlen për një grup arbitrar ndryshoresh ( y 1, y 2 , ... , y m, y m +1 , ... , y n) .
Ne e zëvendësojmë këtë grup arbitrar të ndryshoreve në anën e majtë dhe të djathtë të barazisë (4.1).
Në anën e majtë marrim f (y 1, y 2 , ... , y n) .
T. te. y s= 1 vetëm kur y = s, pastaj midis 2 m lidhëzat y 1 s 1 &y 2 s 2 &...&y m sm në anën e djathtë të (4.1) vetëm njëri kthehet në 1 - ai në të cilin y 1 = s 1 ,…, y m = s m. Të gjitha lidhëzat e tjera janë të barabarta me 0. Prandaj, në anën e djathtë të (4.1) marrim:
y 1 y 1 &y 2 y 2 &...&ym ym&f(y 1, y 2 , ... , y m, y m +1 , ... , y n) = f(y 1, y 2 , ... , y n) .
Teorema 4.5 vërtetohet.
Teorema 4.6(mbi paraqitjen e një funksioni Boolean me një formulë në SDNF),
Çdo funksion boolean f(x 1 , x 2 , ... , x n), e cila nuk është identike e barabartë me 0, mund të përfaqësohet nga një formulë në SDNF, e cila përcaktohet në mënyrë unike deri në një ndërrim të termave disjunktive.
Dëshmi.
Në m = n marrim një përfundim të rëndësishëm të Teoremës 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
ku disjuksioni merret mbi të gjitha grupet ( s 1 , s 2 , ... , s n), ku f = 1.
Është e qartë se zgjerimi (4.2) nuk është gjë tjetër veçse SDNF e formulës f, i cili përmban aq lidhëza sa ka njësi në tabelën e vlerave f. Rrjedhimisht, SDNF për çdo funksion Boolean është unik deri në një ndërrim të termave të tij ndarës.
Është gjithashtu e qartë se për funksionin Boolean f(x 1 , x 2 , ... , x n) identikisht e barabartë me 0, zgjerimi (2) nuk ekziston.
Duke pasur parasysh sa më sipër, për të marrë formulën e funksionit Boolean f(x 1 , x 2 , ... , x n) në SDNF, ne mund të përdorim algoritmin e mëposhtëm.
Algoritmi 4.3. (Algoritmi për paraqitjen e një funksioni Boolean të dhënë nga një tabelë, një formulë në SDNF).
Hapi 1. s 1 , s 2 , ... , s n, për të cilën vlera fështë e barabartë me 1, d.m.th. f (s 1 , s 2 , ... , s n) = 1.
Hapi 2 Për çdo grup të tillë (rreshta të tabelës), ne krijojmë një lidhje x 1 s 1 &x 2 s 2 &...&x n sn, ku x i si = x i, nëse s i= 1 dhe x i si =Ø x i, nëse s i = 0, i = 1, 2, ... ,n.
Hapi 3 Ne bëjmë një ndarje të të gjitha lidhëzave që rezultojnë. Rezultati është një formulë për këtë funksion në SDNF.
Shembulli 4.15.
Gjeni një formulë në SDNF për funksionin f(x 1 , x 2 , x 3) dhënë nga Tabela 4.4.
f(x 1 , x 2 , x 3) = 1. Kjo është e 4-ta, e 5-ta. Linjat e 6-të dhe të 8-të.
2. Për çdo rresht të zgjedhur, ne bëjmë lidhje sipas rregullit të specifikuar në hapin 2. Ne marrim, përkatësisht, për katër rreshtat e zgjedhur:
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. Ne bëjmë një ndarje të të gjitha lidhëzave që rezultojnë dhe gjejmë 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 .
Sigurohemi që kjo shprehje të përputhet me paraqitjen e formulës sonë në SDNF të marrë më parë në Shembullin 4.13.
Koment. Nëse një funksion Boolean jepet nga një formulë në SDNF, atëherë duke aplikuar Algoritmin 4.3 në rend të kundërt, mund të marrim lehtësisht një tabelë vlerash për këtë funksion.
Teorema 4.7(mbi paraqitjen e një funksioni Boolean me një formulë në SKNF),
Çdo funksion boolean f(x 1 , x 2 , ... , x n), e cila nuk është identike e barabartë me 1, mund të përfaqësohet nga një formulë në SKNF, e cila përcaktohet në mënyrë unike deri në një ndërrim të termave disjunktive.
Dëshmi.
Merrni parasysh funksionin Ø f(x 1 , x 2 , ... , x n). Sipas teoremës 4.6, nëse nuk është identikisht i barabartë me 0, atëherë ekziston një formulë për të në SDNF. Le të shënojmë këtë formulë F një. Natyrisht, kushti që funksioni Ø f(x 1 , x 2 , ... , x n) nuk është identikisht e barabartë me 0, është ekuivalente me kushtin që funksioni f(x 1 , x 2 , ... , x n) nuk është identikisht e barabartë me 1. Përveç kësaj, sipas ligjit de Morgan, formula F 2ºØ F 1 është në SKNF (negacioni i një lidhëz është një shkëputje e mohimeve). Sipas ligjit të mohimit të dyfishtë
F 2ºØ F 1ºØØ f(x 1 , x 2 , ... , x n) º f(x 1 , x 2 , ... , x n),
që vërteton teoremën.
Për të marrë formulën e funksionit Boolean f(x 1 , x 2 , ... , x n) në SKNF, duhet të përdoret algoritmi i mëposhtëm.
Algoritmi 4.4. (Algoritmi për paraqitjen e një funksioni Boolean të dhënë nga një tabelë, një formulë në SKNF)
Hapi 1. Zgjidhni të gjitha grupet e variablave në tabelë s 1 , s 2 , ... , s n, për të cilën vlera f (s 1 , s 2 , ... , s n) = 0.
Hapi 2 Për çdo grup të tillë (rreshta të tabelës), ne krijojmë një ndarje
x 1Ø s 1V x 2 Ø s 2V...V x n Ø sn, ku x i Ø si = x i, nëse s i= 0 dhe x i Ø si = Ø x i, nëse s i = 1, i = 1, 2, ... , n.
Hapi 3 Ne krijojmë lidhëzën e të gjitha ndarjeve që rezultojnë. Rezultati është SKNF.
Shembulli 4.16.
Gjeni një formulë në SKNF për funksionin f(x 1 , x 2 , x 3) dhënë nga Tabela 4.4.
1. Zgjidhni rreshtat në tabelën ku f(x 1 , x 2 , x 3) = 0. Këto janë rreshtat 1, 2 dhe 3 dhe 7.
2. Për çdo rresht të zgjedhur, ne bëjmë ndarje sipas rregullit të specifikuar në hapin 2. Marrim, përkatësisht, për tre rreshtat e zgjedhur:
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 10V x 20 V x 3 1 = Ø x 1V x 2V x 3 .
3. Bëjmë një lidhje të të gjitha ndarjeve të marra dhe gjejmë 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).
Kjo shprehje përkon me paraqitjen e formulës sonë në SKNF të marrë më parë në Shembullin 4.14.
Koment. Sepse ka 2 rreshta në tabelën e funksioneve n, atëherë nëse numri i termave disjunktive në SDNF është i barabartë me fq, dhe numri i termave lidhorë në SKNF është i barabartë me q, pastaj fq+q=2n.
Pra, për funksionin e konsideruar në shembujt 4.15 dhe 4.16, n = 3, fq = 4, q = 4, fq + q = 8 = 2 3 .
Merrni parasysh çështjen e përfaqësimit n-funksioni boolean lokal f(x 1 ,x 2 ,…,x n) nga disa formulë algjebër propozicionale.
Le të prezantojmë shënimin, ku një parametër është i barabartë me 0 ose 1.
Është e qartë se 
Teorema 1.1. Çdo funksion i algjebrës së logjikësf(x 1 , x 2 ,…, x n ) për çdom(1£ m £ n) mund të përfaqësohet në formën e mëposhtme:
ku disjunksioni merret mbi të gjitha grupet e mundshme të vlerave të variablave.
Dëshmi. Konsideroni një grup vlerash arbitrare të të gjitha variablave të një funksioni të caktuar. Le të tregojmë se në këtë grup anët e majta dhe të djathta të formulës (1) marrin të njëjtën vlerë. Ana e majtë është 
, drejtë
sepse , nëse vetëm , nëse , atëherë termi logjik përkatës mund të hidhet poshtë.
Komentoni. Paraqitja e funksionit të specifikuar në teoremë quhet zgjerimi i funksionit në terma të m variablat .
Përfundimi 1(zgjerimi në një variabël).
Në këtë rast, funksionet 
Dhe 
thirrur komponentët e dekompozimit.
Pasoja 2(zgjerimi në të gjitha variablat).
Është e qartë se nëse 
, pastaj
Pra, nëse funksioni f(x 1 ,x 2 ,…,x n) nuk është një funksion identikisht i rremë, atëherë mund të shprehet me një formulë ekuivalente, e cila është një shumë logjike e produkteve të ndryshme të formës , dhe një paraqitje e tillë është unike.
Formula e formulës (2) mund të thjeshtohet shumë. Dihet se çdo formulë e algjebrës së logjikës mund të reduktohet me anë të transformimeve ekuivalente në një formulë që përmban vetëm lidhjen dhe mohimin ose disjunksionin dhe mohimin. Si rezultat i kryerjes së transformimeve ekuivalente, mund të merren disa formula, megjithatë, vetëm njëra prej tyre do të ketë vetitë e mëposhtme:
1. Çdo term logjik përmban të gjitha variablat e përfshira në formulë f(x 1 ,x 2 ,…,x n).
2. Asnjë term logjik nuk përmban edhe një ndryshore edhe mohimin e saj.
3. Të gjithë termat logjikë në formulë janë të ndryshëm.
4. Asnjë term logjik nuk përmban të njëjtën variabël dy herë.
Këto katër veti quhen vetitë e përsosmërisë(ose vetitë e C).
Nëse f(x 1 ,x 2 ,…,x n) jepet nga tabela e së vërtetës, atëherë formula përkatëse e algjebrës logjike mund të rikthehet mjaft thjesht. Për të gjitha vlerat e argumentit x 1 ,x 2 ,…,x n, në të cilën f merr vlerën 1, ju duhet të shkruani lidhjen e ndryshoreve elementare të deklaratave, duke marrë për termin e lidhjes x i, nëse x i=1, dhe nëse x i=0. Ndarja e të gjitha lidhëzave të regjistruara do të jetë formula e nevojshme. Rreth vlerave f 0 nuk keni pse të shqetësoheni, sepse termi përkatës në formulë do të jetë i barabartë me 0 dhe mund të hidhet poshtë për shkak të ekuivalencës fÚ 0 ≡ f.
Për shembull, le të funksionojë f(x, y, z) ka tabelën e mëposhtme të së vërtetës:
|
x |
y |
z |
f(x, y, z) |
Ne zgjedhim ndryshoren x 1 dhe marrim parasysh funksionin f në lidhje me të.
I gjithë grupi i kompleteve tabela e së vërtetës ndahet në dy nënbashkësi, secila prej të cilave ka katër grupe<0, a 2 , a 3 >Dhe<1, a 2 , a 3 >.
Atëherë funksioni f(x 1, x 2, x 3) mund të përfaqësohet si një ndarje e dy funksioneve të dy ndryshoreve, dhe kjo formulë do të duket si:
Merrni parasysh formulat e mëposhtme:
Ana e majtë e formulës së parë është ekuivalente me atë të djathtë, pasi për x 1 =0 dhe në përputhje me veprimin e lidhjes. Vlefshmëria e formulës së dytë mund të tregohet në mënyrë të ngjashme. Kështu, duke i vendosur këto formula në ndarjen e mëparshme, marrim:
Kjo shprehje quhet zgjerimi i funksionit f(x 1 ,x 2 ,x 3) në lidhje me ndryshoren x 1 .
Tani, në mënyrë të ngjashme, ne mund të zgjerojmë funksionet f(0, x 2, x 3) dhe f(1, x 2, x 3) në x 2. Marr
Duke i zëvendësuar këto formula në ato të mëparshmet, marrim
Në përputhje me shpërndarjen e operacionit &, ne futim variablin x 1 dhe përmbysjen e saj në kllapa, marrim
Në përgjithësi, për një funksion f(x 1 ,x 2 ,..,x n) të n variablave, zgjerimi në m variabla (m £ n) ka formën
ku disjunksioni merret mbi të gjitha grupet 2 m të ndryshoreve x 1 ,x 2 ,..,x m .
Konsideroni zbërthimin (*4) në rastin ekstrem kur m=n. (shih shembullin (*3)).
Pastaj në të gjitha lidhjet vlerat e funksionit f në çdo grup fiks kanë vlera të barabarta me zero ose një. Duke hequr të gjitha lidhëzat zero, marrim një zbërthim të ri dhe në këtë zbërthim të ri heqim faktorët e funksioneve në lidhëza, sepse ato janë të barabarta me 1. Shprehja e mbetur quhet CDNF (formë normale disjunctive e përsosur).
Le t'i bëjmë të gjitha këto për shembull (*3).
Pas heqjes nga (*3) lidhjet me vlera zero të funksionit f në grupet e dhëna, marrim:
Meqenëse sipas tabelës së së vërtetës
f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1
atëherë nga lidhëzat heqim faktorët e funksioneve, pas së cilës marrim:
Kjo është forma normale e përsosur disjunktive e funksionit Boolean f.
Lemë.Çdo funksion Boolean (përveç konstantës "0") ka një PDNF, dhe vetëm një.
Në mënyrë të ngjashme, mund të futni formën lidhore,
Ndërtimi i SDNF për një funksion të dhënë nga një tabelë
Kjo përfundim është konstruktive, pasi sipas tabelës së funksioneve, ju lejon të ndërtoni një formulë që është SDNF (nëse ).
funksionet sdnf f përmban saktësisht po aq lidhëza sa ka në tabelë f; për çdo grup "të vetëm". (d 1,…,d n), ato. bashkësia në të cilën vlera e funksionit është e barabartë me 1 korrespondon me lidhjen e të gjitha ndryshoreve në të cilat x i merret me një negativ nëse d i=0, dhe pa mohim nëse d i =1.
Bashkësia B, në të cilën përcaktohen dy operacione binare (lidhëza dhe disjuksioni) dhe një operacion unar (negacion) dhe janë ndarë dy elementë 0 dhe 1, quhet algjebër e Bulit.
Për më tepër, për këto operacione, duhet të plotësohen karakteristikat e mëposhtme:
Asociativiteti
komutativiteti
Shpërndarja e lidhëzës në lidhje me disjunksionin
Shpërndarja e disjunksionit në lidhje me lidhëzën
Idempotenca
Dy herë jo
Vetitë konstante
De Morgan rregullon
Ligji i kontradiktës
Ligji i mesit të përjashtuar
Në algjebrën e logjikës, këto ligje quhen ekuivalenca.
Forma normale perfekte
Forma normale e përsosur ndarëse
Le të prezantojmë shënimin:
; A A = 1; X A =1 nëse X=A, X A =0 nëse XA.
Formula X A 1…… X A n , ku A=- çdo grup binar, dhe midis ndryshoreve Xi mund të jetë i njëjtë quhet lidhëz elementare.
Çdo ndarje e lidhëzave elementare quhet formë normale disjunktive (DNF).
Lidhëza elementare quhet e saktë nëse secila variabël ndodh më së shumti një herë në të (duke përfshirë paraqitjen e saj nën shenjën e mohimit).
Për shembull: 1) (ikona e lidhjes është lënë jashtë në këtë rast).
1),4) janë lidhëza të rregullta elementare;
2) - ndryshorja x hyn një herë më vete dhe herën e dytë nën shenjën e mohimit;
Ndryshorja y shfaqet tre herë: një herë në vetvete dhe dy herë nën shenjën e mohimit.
Një lidhje e saktë elementare quhet e plotë në lidhje me ndryshoret x 1 ... .. x n nëse përfshin secilën nga këto ndryshore dhe vetëm një herë (mund të ketë edhe një shenjë mohimi).
Për shembull: nga lidhëzat e renditura në shembullin e mëparshëm, vetëm 4) janë të plota në lidhje me ndryshoret x, y, z, t; dhe në lidhje me ndryshoret x,y,z vetëm 1 është i plotë).
Një formë normale disjunktive e përsosur (PSNF) në lidhje me ndryshoret x 1 .....xn është një formë normale disjunktive në të cilën nuk ka lidhëza elementare identike dhe të gjitha lidhëzat elementare janë të sakta dhe të plota në lidhje me ndryshoret x 1 . ....xn
Zgjerimi i ndryshueshëm
Teorema 1. Çdo funksion logjik mund të përfaqësohet në SDNF:
ku m, dhe disjuksioni merret mbi të gjitha grupet 2 m të vlerave të ndryshoreve x 1 ,…x m . Funksioni f është zgjeruar në n-ndryshoret e para. Kjo barazi quhet zgjerim në variabla. x 1,… x m. Për shembull, për n=4, m=2, zbërthimi duket si:
Teorema vërtetohet duke zëvendësuar një bashkësi arbitrare (b 1,…,b m, b m+1,…,b n) të të gjitha n-ndryshoreve në të dy anët e barazisë (1).
Për m = 1, nga (1) marrim zgjerimin e funksionit në një ndryshore:
Natyrisht, një zgjerim i ngjashëm është i vlefshëm për cilindo prej n-ndryshoreve.
Një rast tjetër i rëndësishëm është kur n=m. Në këtë rast, të gjitha variablat në anën e djathtë të (1) marrin vlera fikse dhe funksionet në lidhjen e anës së djathtë bëhen të barabarta me 0 ose 1, gjë që jep:
ku disjunksioni merret mbi të gjitha bashkësitë (b 1 …b n) në të cilat f=1. Për f=0, bashkësia e lidhëzave në anën e djathtë është bosh. Një zbërthim i tillë quhet një formë normale e përsosur disjunktive. SDNF e funksionit f përmban saktësisht po aq lidhëza sa ka në tabelën e vërtetësisë së f. Çdo grup njësi (b 1 ,…, b n) korrespondon me lidhjen e të gjitha ndryshoreve, në të cilat x i merret me mohim nëse b i =0 b , dhe pa mohim nëse b i =1. Kështu, ekziston një korrespodencë një-për-një ndërmjet tabelës së vërtetës së funksionit f dhe SDNF-së së tij, dhe, për rrjedhojë, SDNF për çdo funksion logjik është unik. Funksioni i vetëm që nuk ka një SDNF është konstantja 0.
Teorema 2. Çdo funksion logjik mund të përfaqësohet si një formulë Boolean.
Në të vërtetë, për çdo funksion, përveç konstantës 0, SDNF-ja e tij mund të shërbejë si një paraqitje e tillë. Konstanta 0 mund të përfaqësohet me një formulë Boolean.
Zbërthimi i funksioneve boolean në variabla.
Le të jetë G një parametër i barabartë me 0 ose 1. Le të prezantojmë shënimin:
Është e lehtë të kontrollohet duke e kontrolluar atë x G = 1 nëse dhe vetëm nëse x= G. Nga kjo rrjedh se lidhja është e barabartë me 1 (këtu G është e barabartë me 0 ose 1) nëse dhe vetëm nëse 
. Për shembull, lidhja (në të cilën G 2 \u003d G 1 \u003d 0, G 3 \u003d G 4 \u003d 1) është 1 vetëm nëse x 1 = x 2 = 0, x 3 = x 4 = 1.
Teorema 1Çdo funksion Boolean f(x 1, x 2,…, x n) duhet të përfaqësohet në formën e mëposhtme:
ku 1 ≤ k ≤ n, në disjuksion merren të gjitha grupet e vlerave të ndryshoreve.
Ky paraqitje quhet zgjerimi i funksionit në terma të variablave. Për shembull, për n = 4, k = 2, zgjerimi (3.1) ka formën:
.
Le të vërtetojmë zgjerimin (3.1). Për ta bërë këtë, merrni një grup arbitrar vlerash të ndryshueshme 
. Le të tregojmë se ana e majtë dhe e djathtë e relacionit (3.1) marrin të njëjtën vlerë. Në të vërtetë, që nga x G = 1 nëse dhe vetëm nëse x= G, atëherë midis 2 vetëm një lidhëz i anës së djathtë të (3.1) kthehet në unitet, në të cilin 
. Të gjitha lidhëzat e tjera janë të barabarta me zero.
Per kete arsye . Si rrjedhojë e zgjerimit (3.1), marrim dy zgjerimet speciale të mëposhtme.
Zgjerimi i ndryshueshëm x n:
Nëse funksioni Boolean nuk është një konstante 0, atëherë zgjerimi është i vlefshëm
Zgjerimi në të gjitha variablat:
, 
(3.3)
ku disjuksioni merret mbi të gjitha grupet 
, për të cilin vlera e funksionit 
është e barabartë me 1.
Zbërthimi (3.3) zakonisht quhet forma normale e përsosur disjunktive (shënimi i shkurtuar SDNF) i funksionit.
Zbërthimi (3.3) jep një mënyrë për të ndërtuar një SDNF. Për ta bërë këtë, në tabelën e së vërtetës, shënoni të gjitha rreshtat , në të cilën . Për çdo rresht të tillë, ne formojmë një lidhje dhe më pas lidhim të gjitha lidhëzat që rezultojnë me një shenjë shkëputjeje.
Tᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, ekziston një korrespondencë një-për-një ndërmjet tabelës së vërtetës së një funksioni dhe SDNF e saj. Dhe kjo do të thotë që SDNF për funksionin Boolean është unik.
Një funksion i vetëm boolean që nuk ka një sdnf është konstantja 0.
Shembulli 1 Gjeni formën e përsosur ndarëse për një funksion 
.
Le të bëjmë një tabelë të së vërtetës për këtë funksion:
| |
|||||
Nga këtu marrim: = = .
Një rol të rëndësishëm në algjebrën e logjikës luan zbërthimi i mëposhtëm i funksioneve të Bulit.
Teorema 2Çdo funksion boolean duhet të paraqitet në formën e mëposhtme:
ku 1≤k≤n, dhe është marrë lidhëza mbi të gjitha 2 k grupe vlerash të ndryshueshme.
Në të vërtetë, le është një grup arbitrar vlerash të ndryshueshme. Le të tregojmë se pjesa e majtë dhe e djathtë e relacionit (3.4) marrin të njëjtën vlerë. Që vetëm kur , atëherë midis 2 k ndarjeve 
në anën e djathtë të (3.4) zhduket vetëm një, në të cilën . Të gjitha ndarjet e tjera janë të barabarta me 1.
Per kete arsye 
= = .
Zgjerimet e funksioneve Boolean pasojnë drejtpërdrejt nga zgjerimi (3.4):
Zbërthimi i fundit quhet forma normale e përsosur konjuktive (CKNF). Zbërthimi (3.6) jep një mënyrë për të ndërtuar SKNF. Për ta bërë këtë, në tabelën e së vërtetës, ne shënojmë të gjitha linjat në të cilat. Për çdo rresht të tillë, ne formojmë një ndarje 
dhe më pas i lidhim të gjitha lidhëzat që rezultojnë me një shenjë lidhore. Tᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, ekziston një korrespondencë një-për-një ndërmjet tabelës së vërtetës së një funksioni dhe SKNF e saj. Dhe kjo do të thotë që SKNF për funksionin Boolean është unik.
Funksioni i vetëm boolean që nuk ka SKNF është konstanta 1.
Shembulli 2 Gjeni formën e përsosur normale lidhore për një funksion 
.
Le të bëjmë një tabelë të vërtetësisë për këtë funksion.
| |
|||||
Nga këtu marrim SKNF
Formula e formularit (shënim i shkurtër), ku 
- lidhëzat 
thirrur forma normale disjunctive (DNF).
Në bazë të përkufizimit të mësipërm të DNF, do të ketë, për shembull, shprehjet: , .
Siç u theksua në paragrafin 2.2, të gjitha veprimet logjike mund të reduktohen në tre: lidhjet, ndarjet dhe mohimet. Për më tepër, në funksion të ligjit të de Morganit, shenja e mohimit mund të supozohet se zbatohet vetëm për variablat.
Tani, duke përdorur ligjin shpërndarës, hapim kllapat dhe marrim formën normale disjunktive. Pra, teorema e mëposhtme është e vërtetë.
Teorema 3 Për çdo formulë të algjebrës së logjikës, ekziston një formë normale disjunktive ekuivalente me të.
Vërtetimi i kësaj teoreme jep një mënyrë për të ndërtuar një formë normale disjunktive për çdo formulë në algjebrën e logjikës.
Shembulli 3 Gjeni formën normale ndarëse për formulën e mëposhtme: 
.
Shenja e përjashtuar me ligj 
dhe duke zbatuar ligjet e de Morganit dhe mohimin e dyfishtë, marrim:
Më pas, duke zbatuar ligjin e shpërndarjes, zgjerojmë kllapat
Shprehja e fundit është forma normale disjunktive.
Shiko formën 
(shënim i shkurtër), ku janë ndarjet 
thirrur forma normale konjuktive (CNF).
Këto janë, për shembull, shprehjet:
, .
Siç u tregua më lart, për çdo formulë të algjebrës së logjikës ekziston një formë disjunktive ekuivalente me të. Duke përdorur ligjin shpërndarës, është e lehtë të merret një CNF nga një DNF e caktuar.
Pra, teorema e mëposhtme është e vërtetë.
Teorema 4 Për çdo formulë të algjebrës së logjikës, ekziston një formë normale konjuktive ekuivalente me të.
Vërtetimi i kësaj teoreme jep një mënyrë për të ndërtuar një formë normale konjuktive për çdo formulë në algjebër e logjikës.
Shembulli 4 Gjeni trajtat normale disjunktive dhe lidhore për formulën e mëposhtme: .
Duke përdorur ligjin 
, e përjashtojmë shenjën . Ne marrim formulën.
Duke përdorur ligjin e de Morganit, marrim formulën 
. Duke zgjeruar kllapat, marrim formën normale ndarëse
.
Për të marrë formën normale lidhore, zbatojeni formulën ligjin shpërndarës, marrim:
Shprehja e fundit është forma normale lidhore. Meqenëse dhe , CNF-ja që rezulton është ekuivalente me CNF-në e mëposhtme:
Ndër të gjitha formulat normale të kësaj formule veçojmë formën normale të përsosur, si disjunktive ashtu edhe lidhore. Duke marrë parasysh zgjerimin (3), është e lehtë të shihet se forma normale e përsosur disjunktive e një formule të algjebrës logjike që përmban saktësisht n ndryshore të dallueshme është forma e saj normale disjunktive, në të cilën:
1) të gjitha lidhëzat janë të dallueshme në çift;
2) çdo lidhje përmban saktësisht n ndryshore;
3) në çdo lidhje ka të gjitha n ndryshore.
Në shembullin 1, ne kemi shqyrtuar një nga mënyrat për të ndërtuar një SDNF bazuar në përpilimin e një tabele të së vërtetës. Mënyra tjetër për të ndërtuar SDNF bazohet në zbatimin e ligjeve të algjebrës së logjikës.
Shembulli 5 Gjeni formën e përsosur ndarëse të formulës.
Duke përdorur atë , marrim . Në funksion të ligjeve të de Morganit dhe mohimit të dyfishtë, ne kemi marrë një formë normale disjunctive. Ky DNF është ekuivalent me formulën .
Duke i zgjeruar kllapat, marrim: .
Duke përdorur ligjin e idempotencës, marrim SDNF-në e kërkuar:
Duke marrë parasysh zbërthimin (3.6), është e lehtë të shihet se forma normale e përsosur konjuktive e formulës së algjebrës së logjikës që përmban saktësisht n variabla të ndryshëm, ekziston forma e saj normale lidhore, në të cilën:
1) të gjitha ndarjet janë të dallueshme në çift;
2) çdo ndarje përmban saktësisht n anëtarë; identike e vërtetë, nëse merr vlerën e vërtetë.
Shembuj të formulave identike të vërteta janë formulat:
në mënyrë identike të rreme, nëse ajo, me të gjitha vlerat e variablave të përfshira në të, merr vlerën I rremë.
Shembuj të formulave identike të rreme janë formulat:
Zakonisht quhet formula e algjebrës së logjikës e realizueshme, nëse për disa vlera të variablave të përfshirë në të, ajo merr vlerën e vërtetë.
Shembuj të formulave të realizueshme janë formulat e mëposhtme:
Në algjebrën e logjikës, mund të parashtrohet problemi i mëposhtëm: të tregohet një metodë (algoritmi) që lejon që çdo formulë e algjebrës së logjikës të zbulojë nëse është identike e vërtetë apo jo. Detyra quhet problemet e zgjidhjes.
Konsideroni dy mënyrat e mëposhtme për të zgjidhur këtë problem.
Metoda 1 (tabela) Për të përcaktuar nëse një formulë e dhënë është identike e vërtetë apo jo, mjafton të përpilohet tabela e saj e vërtetësisë.
Në të njëjtën kohë, kjo metodë, megjithëse ofron një zgjidhje themelore për problemin e zgjidhshmërisë, është mjaft e rëndë.
Metoda 2 bazuar në reduktimin e formulave në formë normale.
Teorema 4Një formulë e algjebrës së logjikës është identike e vërtetë nëse dhe vetëm nëse çdo disjunksion në formën e tij normale lidhore përmban një ndryshore së bashku me mohimin e saj.
Në të vërtetë, nëse çdo disjunksion në formën normale lidhore përmban një ndryshore së bashku me mohimin e saj, atëherë të gjitha disjunksionet janë të barabarta me 1, sepse , . Nga kjo rrjedh se CNF është identikisht e vërtetë.
Tani formula e dhënë le të jetë identike e vërtetë dhe le 
ka disa ndarje në CNF të kësaj formule. Le të supozojmë se disjunksioni i dhënë nuk përmban një ndryshore së bashku me mohimin e saj. Në këtë rast, ne mund t'i japim vlerën 0 çdo ndryshoreje që nuk është nën shenjën e mohimit dhe vlerën 1 për çdo ndryshore që është nën shenjën e mohimit. Pas këtij zëvendësimi, të gjitha disjuksionet do të bëhen të barabarta me 0, pra formula nuk është identike e vërtetë. Kemi një kontradiktë.
Shembulli 7 Zbuloni nëse formula është identike e vërtetë
.
Duke përdorur atë , marrim .
Duke zbatuar ligjin e shpërndarjes, marrim CNF:
Meqenëse çdo ndarje përmban disa ndryshore së bashku me mohimin e saj, formula është identike e vërtetë.
Ngjashëm me teoremën e mëparshme, vërtetohet teorema e mëposhtme:
Teorema 5Një formulë e algjebrës së logjikës është identike e gabuar nëse dhe vetëm nëse çdo lidhëz në formën e saj ndarëse përmban një ndryshore së bashku me mohimin e saj..
Zbërthimi i funksioneve boolean në variabla. - koncepti dhe llojet. Klasifikimi dhe veçoritë e kategorisë "Zbërthimi i funksioneve Boolean në variabla". 2017, 2018.
