Zgjero funksionin f me një kolonë të caktuar vlerash. Zbërthimi i funksioneve Boolean në variabla

01.12.2020 Këshilla

Merrni parasysh çështjen e prezantimit 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 Algjebër Booleanf(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 për të gjitha variablat e 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ë e barabartë me , drejtë

që nga viti , nëse vetëm, nëse, atëherë termi logjik përkatës mund të hidhet poshtë.

Komentoni... Paraqitja e një funksioni të treguar në teoremë quhet zgjerimi i funksionit në terma të m variablave.

Përfundimi 1(zgjerimi në një variabël).

Në këtë rast, funksionet dhe quhen komponentët e dekompozimit.

Përfundimi 2(zgjerimi në të gjitha variablat).

Natyrisht, 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 (2) mund të thjeshtohet shumë. Dihet se çdo formulë e algjebrës së logjikës mund të reduktohet me transformime 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 i vetëm logjik nuk përmban si një ndryshore ashtu 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ë 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 së logjikës mund të rindërtohet 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 pohimeve të ndryshoreve elementare, duke marrë si termin lidhor 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 kuptimeve f 0 ju 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)

Ndani punën tuaj në rrjetet sociale

Nëse kjo punë nuk ju përshtatet në fund të faqes, ekziston një listë me vepra të ngjashme. Ju gjithashtu mund të përdorni butonin e kërkimit

Aranov Victor Pavlovich. Matematikë diskrete.

Seksioni 4. Sistemet funksionale me operacione. Algjebra e logjikës.

Leksioni 21. Parimi i dualitetit. Zbërthimi i funksioneve në variabla. DNF dhe CNF perfekte

Leksioni 21. PARIMI I DUALITETIT. ZBËRTHIMI I BOOLE

FUNKSIONET NË VARIABLA. PERFEKT DJUNKTIV DHE

FORMA NORMALE KONJUNKTIVE

Plani i leksionit:

Parimi i dualitetit.
Zbërthimi i funksioneve Boolean në variabla. Forma normale të përsosura disjunktive dhe lidhore.

Parimi i dualitetit

Një funksion i barabartë me quhet e dyfishtë funksion për të funksionuar.

Natyrisht, tabela e së vërtetës për funksionin e dyfishtë merret nga tabela e së vërtetës për funksionin duke përmbysur (d.m.th., duke zëvendësuar 0 me 1 dhe 1 me 0) të vlerave të variablave dhe funksionit. Për shembull,.

Është e lehtë të vendoset për funksionet 0, 1 që

funksioni 0 është i dyfishtë në 1;
funksioni 1 është i dyfishtë në 0;
funksioni është i dyfishtë;
funksioni është i dyfishtë;
funksioni është i dyfishtë;
funksioni është i dyfishtë.

Nga përkufizimi i dualitetit rezulton se

pra funksioni është i dyfishtë ndaj (vetia e reciprocitetit).

Parimi i dualitetit.Nëse një formulë zbaton një funksion, atëherë formula, domethënë formula e përftuar nga zëvendësimi i funksioneve me, përkatësisht, zbaton funksionin.

Formula do të quhet formula e dyfishtë për.

Për të vërtetuar këtë pohim, është e nevojshme të kontrollohet vlefshmëria e tij për hapat elementare të mbivendosjes dhe.

Për shembull, le të merret një funksion nga një funksion si rezultat i zëvendësimit të variablave të mëposhtëm:

Pastaj

dmth funksioni fitohet si rezultat i të njëjtit zëvendësim të ndryshoreve.

Le të provojmë vlefshmërinë e parimit të dualitetit për një hap duke përdorur një shembull. Le

Pastaj

pra funksioni merret nga dhe në të njëjtën mënyrë si funksioni nga dhe.

Parimi i dualitetit thjeshton derivimin e tautologjive bazë dhe ka një numër aplikimesh të dobishme, të cilat do të diskutohen më poshtë.

Shembulli 1. Identiteti rrjedh nga identiteti.

Vërtet,

;; .

Shembulli 2. Ndërtimi i një formule për mohimin e një funksioni.

Përkufizimi i funksionit të dyfishtë nënkupton

Ne marrim rregullin e mëposhtëm: le formula zbaton funksionin. Për të marrë një formulë për një funksion, duhet të zëvendësoni të gjitha variablat në formulë me negativet e tyre.

Le të gjejmë mohimin për funksionin.

Që atëherë.

Zbërthimi i funksioneve Boolean në variabla. Perfekte

Format normale disjunktive dhe lidhore

Le të prezantojmë shënimin

ku është një parametër i barabartë me 0 ose 1. Është e qartë se

Është e lehtë të shihet se 1 nëse dhe vetëm nëse.

Teorema mbi zgjerimin e funksioneve në variabla. Çdo funksion i algjebrës së logjikës për çdo () mund të përfaqësohet në formën e mëposhtme:

, (1)

ku disjunksioni merret mbi të gjitha grupet e mundshme të vlerave të variablave.

Kjo performancë quhetzgjerimi i funksionit në variabla.

Dëshmi. Konsideroni një grup arbitrar vlerash të ndryshoreve dhe tregoni se ana e majtë dhe e djathtë e relacionit (1) marrin të njëjtën vlerë në të. Ana e majtë jep. E drejta -

Si pasojë e teoremës, merrni parasysh dy raste të veçanta të zbërthimit.

Zgjerimi i ndryshueshëm:

Funksionon dhe quhenkomponentët e dekompozimit.Ky zbërthim është i dobishëm kur disa veti krijohen me induksion.

Zgjerimi në të gjitha variablat:

Nëse nuk është identikisht i barabartë me 0, ai mund të transformohet:

Si rezultat, më në fund arrijmë

. (2)

Një zbërthim i tillë quhettrajtë normale e përsosur ndarëse(përsosur dn. f.).

Drejtpërdrejt në konceptin e një D.N të përsosur. f. bashkohet teorema e mëposhtme.

Teorema. Çdo funksion i algjebrës së logjikës mund të përfaqësohet nga një formulë në bazë.

Vërtetim 1) Le. Pastaj padyshim

Le të mos jetë identike e barabartë me 0. Atëherë mund të paraqitet me formulën (2).

Kjo teoremë është konstruktive në natyrë, pasi lejon që çdo funksion të ndërtojë një formulë që e zbaton atë në formën e një DN të përsosur. f. Për ta bërë këtë, në tabelën e së vërtetës për secilin funksion, ne shënojmë të gjitha linjat në të cilat. Për secilën rresht të tillë, ne formojmë një produkt logjik dhe më pas lidhim të gjitha lidhjet që rezultojnë me një shenjë shkëputjeje.

Shembulli 3. Gjeni dn-në e përsosur. f. për funksionin.

Perfect d. N. f. është shprehje e tipit P. Le të tregojmë se për identikisht jo të barabartë me 1 mund të paraqitet në formë. Për një funksion të dyfishtë (natyrisht jo identikisht i barabartë me 0), ne e shkruajmë zgjerimin në formën e një DN të përsosur. f.:

Parimi i dualitetit nënkupton

Kështu, marrim një zbërthim, i cili quhettrajtë normale e përsosur lidhore(Ph.D. i përsosur):

. (3)

Shembulli 4. Ndërtoni doktoraturën perfekte. f. për funksionin.

Ne kemi.

Punime të tjera të ngjashme që mund t'ju interesojnë.Wshm>
200.		Format normale të funksioneve logjike	63,53 KB
	Format normale të funksioneve logjike Paraqitja e një funksioni Boolean në formën e një disjunksioni të termave lidhorë të përbërësve të njësisë Ki 2.7 quhet forma normale disjunktive e DNF-së së këtij funksioni. përmbajnë saktësisht një nga një të gjitha variablat logjike të marra me mohime ose pa to, atëherë kjo formë e paraqitjes së funksionit quhet forma normale e përsosur disjunktive e SDNF-së së këtij funksioni. Siç mund ta shihni, kur përpiloni funksionin SDNF, duhet të bëni një ndarje të të gjitha mintermave për të cilat funksioni merr vlerën 1.
9015.		METODAT PËR MINIMIZIMIN E FUNKSIONET BOOLEAN	81,74 KB
	Qarqet DNF dhe FE. Minimizimi i funksioneve Boolean bazuar në ndërtimin e DNF-ve pa rrugëdalje. Minimizimi i funksioneve Boolean bazuar në ndërtimin e DNF-ve pa fund DNF-të e reduktuara dhe ato minimale gjenden në marrëdhënien e mëposhtme. Një DNF në rrugë pa krye merret nga një i shkurtuar duke hequr disa nga anëtarët.
9017.		PROBLEMI I MINIMIZIMIT TË FUNKSIONIVE BOOLEAN. INTERPRETIMI GJEOMETRIK	109,86 KB
	Qarqet DNF dhe FE. INTERPRETIMI GJEOMETRIK Plani i leksionit: Koncepti i trajtës normale disjunktive DNF. Koncepti DNF. Shprehja për ku është një lidhje elementare e rangut quhet forma normale disjunktive e DNF.
14731.		Zbërthimi i sinjaleve në një seri të përgjithësuar Furier përsa i përket sistemeve të funksioneve ortogonale. Funksionet Walsh	38,95 KB
	Zbërthimi i sinjaleve në një seri të përgjithësuar Furier përsa i përket sistemeve të funksioneve ortogonale. Njihuni me karakteristikat themelore të sinjaleve dhe ndërhyrjeve. Të studiojë paraqitjen e sinjaleve në formën e një serie të përgjithësuar Furier për sistemet e funksioneve ortogonale. Zbërthimi i sinjaleve në një seri të përgjithësuar Furier përsa i përket sistemeve të funksioneve ortogonale.
6707.		Dizajni i bazës së të dhënave relacionale. Problemet e projektimit në qasjen klasike. Parimet e normalizimit, forma normale	70,48 KB
	Çfarë është një projekt i bazës së të dhënave relacionale Ky është një grup marrëdhëniesh të ndërlidhura në të cilat përcaktohen të gjitha atributet, specifikohen çelësat kryesorë të marrëdhënies dhe specifikohen disa veti shtesë të marrëdhënies që lidhen me parimet e ruajtjes së integritetit. Prandaj, dizajni i bazës së të dhënave duhet të jetë shumë i saktë dhe i verifikuar. Në fakt, projekti i bazës së të dhënave është themeli i paketës së ardhshme softuerike që do të përdoret për një kohë të gjatë dhe nga shumë përdorues.
4849.		Format dhe metodat e ushtrimit të funksioneve shtetërore	197.3 KB
	Termi "funksion" nuk ka të njëjtin kuptim në literaturën shkencore ruse dhe të huaj. Në aspektin filozofik dhe të përgjithshëm sociologjik, ai konsiderohet si "një shfaqje e jashtme e vetive të një objekti në një sistem të caktuar marrëdhëniesh"; si një tërësi veprimesh të zakonshme ose specifike të individëve ose organeve
1790.		Zbërthimi në terma	180.15 KB
	Vetë fjala algorithm i ngjan algoritmeve - forma latine të shkruara nga matematikani i madh i shekullit të 9-të. al-Khorezm, i cili ka formuluar rregullat për administrimin e diy aritmetike. Një përzgjedhje e algoritmeve dhe vetëm rregulla për shfaqjen e zgjidhjeve aritmetike mbi numrat e mëdhenj dixhitalë.
2690.		Studimi i performancës së stërvitjeve me një hap të ndryshueshëm të një spiraleje	18,85 KB
	Modelet e procesit të prerjes mund të përfaqësohen nga një sistem ekuacionesh matematikore që përcaktojnë, në çdo rast specifik, funksionin e vlerësimit ose kriteret për performancën e veglave prerëse, si dhe kufizimet teknike në kinematikën e makinës, ngurtësinë e prerjes. mjetet dhe të gjithë sistemin teknologjik.
17088.		PËRGJEGJËSIA PENALE PËR KRIMET E KRYERA BRENDA NJË GRUP TË ORGANIZUAR KRIMINALISTIK	50,97 KB
	Lomtev PËRSHKRIMI I PËRGJITHSHËM I PUNËS Rëndësia e temës kërkimore përcaktohet nga nevoja për zhvillim dhe përmirësim të mëtejshëm të teorisë dhe praktikës së zbatimit të përgjegjësisë penale për krimet e kryera si pjesë e një grupi kriminal të organizuar. Hulumtimet në fushën e luftimit të krimit të organizuar tregojnë se brenda grupeve kriminale të organizuara kryhen krimet më të rrezikshme dhe më të vështira për t'u zgjidhur. Si pjesë e zgjidhjes së problemit të rritjes së efektivitetit të ligjit penal në drejtim të luftimit të ...
11576.		Koncepti, llojet dhe format e transaksioneve. Pasojat e mosrespektimit të formës së kërkuar të transaksioneve	49,82 KB
	Njohja e një transaksioni të llojeve të pavlefshme të transaksioneve të pavlefshme. Vlera e aplikuar e punës së kursit qëndron në thjeshtimin e konceptit të një transaksioni, domethënë prezantimin e tij publik në një formë më të aksesueshme.

Vendosja e funksioneve Boolean të variablave duke përdorur një tabelë të vërtetësisë, përcaktimi i një formule, llojet e ekuivalencave (ligjeve) më të rëndësishme të algjebrës së logjikës. Formulat ekuivalente, ligjet e ekuivalencës, ekuacionet logjike. Zbërthimi i funksioneve Boolean në variabla.

Duke klikuar në butonin "Shkarko arkivin", do të shkarkoni skedarin që ju nevojitet falas.
Para se të shkarkoni këtë skedar, mbani mend për ato abstrakte të mira, teste, punime termike, teza, artikuj dhe dokumente të tjera që nuk janë kërkuar në kompjuterin tuaj. Kjo është puna juaj, ajo duhet të marrë pjesë në zhvillimin e shoqërisë dhe të përfitojë njerëzit. Gjeni këto vepra dhe dorëzojini bazës së njohurive.
Ne dhe të gjithë studentët, studentët e diplomuar, shkencëtarët e rinj që përdorin bazën e njohurive në studimet dhe punën e tyre do t'ju jemi shumë mirënjohës.

Për të shkarkuar një arkiv me një dokument, në fushën më poshtë, vendosni një numër pesëshifror dhe klikoni butonin "Shkarko arkivin".

Dokumente të ngjashme

Aksiomat dhe identitetet themelore të algjebrës së logjikës. Forma analitike e paraqitjes së funksioneve Boolean. Funksionet elementare të algjebrës së logjikës. Funksionet e algjebrës së logjikës së një argumenti dhe format e zbatimit të tij. Vetitë, veçoritë dhe llojet e operacioneve logjike.

abstrakt, shtuar më 12/06/2010

Koncepti i algjebrës së logjikës, thelbi dhe veçoritë e saj, konceptet dhe përkufizimet themelore, lënda dhe metoda e studimit. Ligjet e algjebrës së logjikës dhe pasojat e tyre, metodat për ndërtimin e formulave sipas një tabele të vërtetë të caktuar. Format e paraqitjes së funksioneve boolean.

tutorial, shtuar më 29/04/2009

Algjebrat e Bulit janë një lloj i veçantë grilë që përdoret në studimin e logjikës (si logjika e të menduarit njerëzor ashtu edhe logjika kompjuterike dixhitale), si dhe qarqet komutuese. Format minimale të polinomeve të Bulit. Teorema abstrakte të algjebrës së Bulit.

punim afatshkurtër, shtuar 05/12/2009

Veprimet mbi pohimet logjike: Funksionet Boolean dhe shprehja e disa prej këtyre varësive përmes të tjerave. Formulat propozicionale dhe disa ligje të logjikës së pohimeve. Përkthimi i shprehjeve të gjuhës natyrore në fjalimin simbolik të algjebrës së logjikës.

test, shtuar 26.04.2011

Logjika është shkenca e ligjeve dhe formave të të menduarit, dhe koncepti bazë i algjebrës së logjikës është një deklaratë. Konceptet dhe identitetet themelore të algjebrës së Bulit. Studimi i metodave për minimizimin e funksioneve Boolean. Metoda e Quine, e bazuar në aplikimin e dy marrëdhënieve themelore.

test, shtuar më 20.01.2011

Konceptet themelore të algjebrës së logjikës. Format normale disjunktive dhe lidhore. Thelbi i teoremës së Shannon-it. Funksionet Boolean të dy variablave. Lidhja serike dhe paralele e dy çelsave. Vetitë e funksioneve elementare të algjebrës së logjikës.

test, shtuar më 29.11.2010

Variabla Boolean në algjebër Boolean. Veprimet logjike: mohim, lidhëz, shkëputje, nënkuptim, ekuivalencë. Ligjet themelore të algjebrës së logjikës. Rregullat e minimizimit për një funksion logjik (duke hequr qafe operacionet e nënkuptimit dhe ekuivalencës).

punim term i shtuar 16.01.2012

Bashkësia B, në të cilën përcaktohen dy operacione binare (lidhëza dhe disjunksion) dhe një operacion unar (negacion) dhe janë zgjedhur dy elementë 0 dhe 1, quhet algjebër e Bulit.

Për më tepër, për këto operacione, karakteristikat e mëposhtme duhet të plotësohen:

Asociativiteti

Komutativiteti

Shpërndarja e një lidhjeje në lidhje me disjunksionin

Shpërndarja e një disjunksioni në lidhje me një lidhëz

Idempotenca

Dy herë jo

Vetitë konstante

Rregullat e De Morganit

Ligji i kontradiktës

Ligji i tretë i 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 = është çdo grup binar, dhe midis ndryshoreve Xi mund të ketë të përkojnë quhet lidhëz elementare.

Çdo ndarje e lidhëzave elementare quhet formë normale disjunktive (DNF).

Lidhja elementare quhet e saktë nëse secila ndryshore shfaqet në të maksimumi një herë (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) - lidhëza të rregullta elementare;

2) - ndryshorja x hyn një herë në vetvete 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.

Lidhja e rregullt elementare quhet e plotë në lidhje me ndryshoret x 1 ... .. x n nëse secila prej këtyre ndryshoreve hyn në të vetëm një herë (mund të jetë gjithashtu një shenjë negative).

Për shembull: nga lidhëzat e renditura në shembullin e mëparshëm, vetëm 4) është e plotë në lidhje me ndryshoret x, y, z, t; dhe në lidhje me ndryshoret x, y, z, vetëm 1) është i plotë.

Forma normale e përsosur disjunktive (SDNF) në lidhje me ndryshoret x 1 ... ..xn është një formë normale ndarëse 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 në variabla

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 i ndryshueshëm. x 1, ... x m. Për shembull, për n = 4, m = 2, zgjerimi është:

Teorema vërtetohet duke zëvendësuar në të dyja anët e barazisë (1) një koleksion arbitrar (b 1,…, b m, b m + 1,…, b n) të të gjithë n-ndryshoreve.

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, që jep:

ku disjuksioni merret mbi të gjitha tupat (b 1… b n) në të cilat f = 1. Për f = 0, grupi i lidhëzave në anën e djathtë është bosh. Ky zbërthim quhet forma normale e përsosur disjunktive. SDNF e një funksioni 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ë korrespondencë një-për-një midis tabelës së vërtetës së funksionit f dhe SDNF-së së tij, dhe, për rrjedhojë, SDNF është unik për çdo funksion logjik. Funksioni i vetëm që nuk ka 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.

3.1 Zbërthimi i funksioneve Boolean në variabla

3.2 Algjebra e Zhegalkinit

Ne treguam më lart se çdo funksion Boolean mund të specifikohet duke përdorur një tabelë të së vërtetës. Ky seksion përshkruan kalimin nga kalimi tabelor i cilësimit të funksionit në atë analitik.

3.1 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ë verifikohet kjo me anë të verifikimit x G = 1 nëse dhe vetëm nëse x = G. Nga kjo rrjedh se lidhëza
ë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, lidhëza
(në të cilën G 2 = G 1 = 0, G 3 = G 4 = 1) është e barabartë me 1 vetëm në rastin kur x 1 =x 2 = 0,x 3 =x 4 = 1.

Teorema 1Çdo funksion Booleanf(x 1 , x 2 ,…, x n ) mund të paraqitet në formën e mëposhtme:

ku 1 ≤k ≤ n, në disjunksion merren të gjitha grupet e vlerave të ndryshoreve.

Ky paraqitje quhet zgjerimi i një funksioni në terma të variablave.
... Për shembull, për n = 4, k = 2, zgjerimi (3.1) ka formën:

Le të vërtetojmë vlefshmërinë e zgjerimit (3.1). Për ta bërë këtë, merrni një grup arbitrar vlerash të variablave
... Le të tregojmë se ana e majtë dhe e djathtë e relacionit (3.1) marrin të njëjtën vlerë për të. Në të vërtetë, që nga x G = 1 nëse dhe vetëm nëse x = G, pastaj midis lidhëzës 2 К
në anën e djathtë të (3.1), vetëm një në të cilën
... Të gjitha lidhëzat e tjera
janë të barabarta me zero.

Kështu që . Si pasojë e zbërthimit (3.1), marrim dy zbërthimet e veçanta të mëposhtme.

Zgjerimi i ndryshueshëmx n :

Nëse funksioni Boolean nuk është një konstante 0, atëherë zgjerimi

Zgjerimi në të gjitha variablat:

,
(3.3)

ku disjuksioni merret mbi të gjitha grupet
për të cilën vlera e funksionit
është e barabartë me 1.

Zgjerimi (3.3) quhet forma normale e përsosur disjunktive (shkurtima për SDNF) e funksionit.

Zgjerimi (3.3) ofron një mënyrë për të ndërtuar SDNF. Për ta bërë këtë, shënoni të gjitha rreshtat në tabelën e së vërtetës
, në të cilën
... Për secilën rresht të tillë, ne formojmë lidhjen
dhe më pas i lidhim të gjitha lidhëzat që rezultojnë me një shenjë shkëputjeje.

Kështu, ekziston një korrespondencë një-për-një midis tabelës së vërtetës së funksionit
dhe SDNF e saj. Kjo do të thotë që SDNF për një funksion Boolean është unik.

Një funksion i vetëm Boolean që nuk ka SDNF është konstantja 0.

Shembulli 1 Gjeni formën e përsosur ndarëse për një funksion
.

Le të hartojmë një tabelë të së vërtetës për këtë funksion:

Nga këtu marrim:
==.

Zgjerimi i mëposhtëm i funksioneve Boolean luan një rol të rëndësishëm në algjebrën e logjikës.

Teorema 2Çdo funksion Boolean
mund të paraqitet në formën e mëposhtme:

ku 1≤k≤n, dhe është marrë lidhëza te gjitha mbi 2 k grupe vlerash të ndryshueshme.

Në të vërtetë, le
- një grup arbitrar vlerash të ndryshueshme. Le të tregojmë se ana e majtë dhe e djathtë e relacionit (3.4) marrin të njëjtën vlerë për të. Sepse
vetem kur
, pastaj midis 2 k ndarjeve
në anën e djathtë të (3.4), zhduket vetëm një, në të cilën
... Të gjitha klauzolat e tjera janë të barabarta me 1.

Kështu që
==
.

Zgjerimet e funksioneve Boolean pasojnë drejtpërdrejt nga zgjerimi (3.4):

Zbërthimi i fundit quhet forma normale e përsosur konjuktive (SKNF). Zgjerimi (3.6) jep një mënyrë për të ndërtuar SKNF. Për ta bërë këtë, shënoni të gjitha rreshtat në tabelën e së vërtetës
, në të cilën. Për secilën rresht të tillë, ne formojmë një ndarje
dhe më pas i lidhim të gjitha lidhëzat që rezultojnë me shenjën lidhore. Kështu, ekziston një korrespondencë një-për-një midis tabelës së vërtetës së funksionit
dhe SKNF e saj. Kjo do të thotë që SKNF për një funksion Boolean është unik.

Funksioni i vetëm Boolean që nuk ka SCNF është konstantja 1.

Shembulli 2 Gjeni formën e përsosur normale lidhore për funksionin
.

Le të hartojmë një tabelë të së vërtetës për këtë funksion.

Nga kjo 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, për shembull, shprehjet do të jenë:
,
.

Siç u përmend në pikën 2.2, të gjitha veprimet logjike mund të reduktohen në tre: lidhëza, shkëputje dhe mohim. Për më tepër, në funksion të ligjit të de Morganit, shenja e mohimit mund të supozohet se i atribuohet vetëm variablave.

Tani, duke përdorur ligjin shpërndarës, zgjerojmë kllapat dhe marrim formën normale disjunktive. Pra, teorema e mëposhtme është e vërtetë.

Teorema3 Për çdo formulë të algjebrës së logjikës, ekziston një formë normale disjunktive ekuivalente me të.

Vërtetimi i kësaj teoreme ofron një mënyrë për të ndërtuar një formë normale disjunktive për çdo formulë në algjebër e logjikës.

Shembulli 3 Gjeni formën normale ndarëse për formulën e mëposhtme:
.

Shenja përjashtuese
në 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 formularin
(hyrje e shkurtër ), ku
- 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 CNF nga DNF-ja e dhënë.

Pra, teorema e mëposhtme është e vërtetë.

Teorema 4Për çdo formulë të algjebrës së logjikës, ekziston një formë normale ekuivalente lidhore.

Vërtetimi i kësaj teoreme ofron një mënyrë për të ndërtuar një formë normale konjuktive për çdo formulë në algjebrën e logjikës.

Shembull4 Gjeni format normale disjunktive dhe lidhore për formulën e mëposhtme:
.

Duke përdorur ligjin
, përjashtoni shenjën
... Ne marrim formulën
.

Duke përdorur ligjin e de Morganit, marrim formulën
... Duke zgjeruar kllapat, marrim trajtën normale disjunktive

Për të marrë formën normale lidhore, ne zbatojmë formulën
ligjin shpërndarës, marrim:

Shprehja e fundit është forma normale lidhore. Sepse
dhe
, atëherë CNF-ja e përftuar ë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 zbërthimin (3), është e lehtë të shihet se forma normale e përsosur disjunktive e një formule algjebër logjike që përmban saktësisht n ndryshore të ndryshme është forma e saj normale disjunktive, në të cilën:

1) të gjitha lidhëzat janë të ndryshme në çift;

2) çdo lidhje përmban saktësisht n ndryshore;

3) çdo lidhje përmban të gjitha n variablat.

Duke përdorur shembullin 1, ne shqyrtuam një nga mënyrat për të ndërtuar 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ë një formule
.

Duke përdorur atë
, marrim
... Në funksion të ligjeve të de Morganit dhe mohimit të dyfishtë, ne kemi marrë formën normale disjunctive
... Ky DNF është ekuivalent me formulën.

Duke 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 një formule të algjebrës së Bulit 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 terma;

3) në çdo ndarje ka të gjitha n ndryshore.

Duke përdorur shembullin 2, ne shqyrtuam një nga mënyrat për të ndërtuar SCNF, bazuar në përpilimin e një tabele të së vërtetës. Mënyra tjetër për të ndërtuar SKNF bazohet në zbatimin e ligjeve të algjebrës së logjikës.

Shembulli 6 Gjeni formën e përsosur normale lidhore të formulës
.

Duke përdorur,
, marrim
.

Kjo formulë është formë normale lidhore. Është e barabartë me një formulë.

Duke përdorur ligjin e shpërndarjes, marrim:

Duke zbatuar ligjin e idempotencës, marrim formën e kërkuar normale lidhore të përsosur

identike e vërtetë nëse për të gjitha vlerat e variablave të përfshirë në të merr vlerën vërtetë.

Shembuj të formulave identike të vërteta janë:

Formula e algjebrës logjike quhet në mënyrë identike të rreme, nëse për të gjitha vlerat e variablave të përfshirë në të, ajo merr vlerën Gënjeshtra.

Shembuj të formulave identike të rreme janë:

Formula e algjebrës logjike quhet 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ë ekzekutueshme janë formulat e mëposhtme:

,
.

Në algjebrën e logjikës mund të shtrohet problemi i mëposhtëm: të tregohet një metodë (algoritmi) që bën të mundur që secila 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 (tabelare) Për të përcaktuar nëse një formulë e dhënë është identike e vërtetë apo jo, mjafton të hartohet tabela e saj e vërtetësisë.

Megjithatë, 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 logjike është identike e vërtetë nëse dhe vetëm nëse çdo disjunksion në formën e tij normale lidhore përmban disa 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
,
... Prandaj rrjedh se CNF është identikisht e vërtetë.

Tani le të jetë identike e vërtetë kjo formulë dhe le
ka disa ndarje në CNF të kësaj formule. Supozoni se disjunksioni i dhënë nuk përmban një ndryshore së bashku me mohimin e saj. Në këtë rast, çdo ndryshore jo nën shenjën negative mund t'i japim vlerën 0, dhe çdo ndryshoreje nën shenjën negative - vlerën 1. Pas këtij zëvendësimi, të gjitha disjuksionet bëhen të barabarta me 0, prandaj formula nuk është identike e vërtetë. Kemi një kontradiktë.

Shembulli 7 Zbuloni nëse formula

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 5 Një formulë e algjebrës së logjikës nëse dhe vetëm nëse është identike e gabuar kur çdo lidhëz në formën e saj ndarëse përmban disa ndryshore së bashku me mohimin e saj.