Kuptimi i mëposhtëm "inxhinierik-konstruktiv" mund t'i jepet paraqitjes së funksioneve të Bulit me formula. Ne do ta konsiderojmë formulën Ф (x 1, ..., xn) mbi një grup F të fiksuar në mënyrë arbitrare si një "kuti e zezë", një pajisje e caktuar, në hyrje të së cilës futen të gjitha grupet e mundshme të vlerave të variablave, dhe prodhimi që korrespondon me këto grupe vlerash të funksionit f të përfaqësuar me formulën Ф (Fig. 6.22).
Për të kuptuar se si funksionon "kutia e zezë", duhet të çmontojmë procesin e ndërtimit të një formule nga nënformula. Arritja në nënformulat "bazë", d.m.th. elementet e grupit F, vijmë te "blloqet e ndërtimit", elementët strukturorë nga të cilët është montuar "kutia e zezë", e cila llogarit funksionin f. Çdo funksion i "bazës" F llogaritet nga "nyja" përkatëse, e cila konsiderohet si njësia më e vogël strukturore e "kutisë së zezë" tonë dhe struktura e saj e brendshme nuk analizohet më.
Shembulli 6.22. Le të zgjedhim një bazë standarde për grupin F. Pastaj formula mbi bazën standarde, që përfaqëson funksionin ~ (ekuivalencë), ndërtohet si më poshtë:
Llogaritja sipas kësaj formule (dhe procesi i ndërtimit të saj nga elementët e bazës standarde) mund të përshkruhet në mënyrë skematike siç tregohet në Fig. 6.23.
Variabli x 1 (më saktë, vlera e kësaj ndryshoreje) futet në hyrjen e një elementi strukturor të quajtur inverter (Fig. 6.24, a) dhe duke llogaritur mohimin. Negativi x 1 i hequr nga dalja e inverterit, d.m.th. funksioni x 1, futet në një nga hyrjet e lidhësit (Fig. 6.24, b), në hyrjen e dytë të të cilit futet ndryshorja x 2. Funksioni x 1 x 2 shfaqet në daljen e lidhësit. Llogaritja e funksionit x 1 x 2 mund të gjurmohet në mënyrë të ngjashme, të dy këto funksione futen në hyrjet e ndarësit (Fig. 6.24, c), nga dalja e të cilit funksioni x 1 x 2 ∨ x 1 x 2 hiqet (kjo nuk është gjë tjetër veçse një modul shumës 2: x 1 ⊕ x 2). Dhe së fundi, ky funksion futet në hyrjen e inverterit, në daljen e të cilit tashmë është marrë funksioni ~ (ekuivalenca). #
Kështu, arrijmë në idenë e një "qarku" - një model matematikor i kalkulatorit të një funksioni Boolean, i përfaqësuar nga një formulë e caktuar, e mbledhur nga elementë strukturorë, secila prej të cilave llogarit një nga funksionet "bazë" Boolean. Në rastin e përgjithshëm, "qarku" llogarit një operator Boolean dhe çdo funksion koordinativ i këtij operatori hiqet nga një nga daljet e qarkut.
Matematikisht, një "skema" përkufizohet si një graf i drejtuar i një lloji të veçantë, në të cilin kulmet dhe harqet janë etiketuar.
Le të prezantojmë shënimin: nëse F është një grup funksionesh Boolean, atëherë me F (n) shënojmë nëngrupin e F që përbëhet nga të gjitha funksionet e n variablave (n≥0).
Përkufizimi 6.14. Le të fiksohen grupet: F (funksionet Boolean) dhe X (variablat Boolean).
Një diagram i elementeve funksionale mbi një bazë F ∪ X (C Φ E), ose thjesht i tkurrur mbi bazën F ∪ X, gjithashtu një skemë (F, X), quhet një graf i drejtuar me fund të hapur (dmth., një rrjet), secila kulm i të cilit është etiketuar nga një prej elementeve të grupit FU X në mënyrë që të plotësohen kërkesat e mëposhtme:
- çdo hyrje e rrjetit është etiketuar ose nga ndonjë ndryshore nga X, ose nga ndonjë konstante nga F (0);
- nëse një kulm v i rrjetit është etiketuar me një funksion f në n variabla (d.m.th., f ∈ F (n)), atëherë gjysma e shkallës së hyrjes së tij është e barabartë me n, dhe në grupin e harqeve që hyjnë në kulmin v , jepet një numërim (një-për-një) i tillë që secili hark numërohet nga 1 në n.
Nëse nënkuptohet baza, atëherë do të themi thjesht "skema". Përveç kësaj, nëse grupi i variablave është fiksuar "një herë e përgjithmonë" dhe kur shqyrtojmë skema të ndryshme ne ndryshojmë vetëm grupin e funksioneve F, atëherë, siç bëmë, duke prezantuar konceptet e një formule dhe mbivendosjeje mbi një bazë të caktuar, ne do të flasë për një SFE mbi një bazë F, duke supozuar çdo herë, që do të thotë një herë një grup fiks të ndryshoreve X, i cili (nëse kjo nuk dëmton saktësinë) nuk përmendet.
Tani përcaktojmë me induksion nocionin Funksioni boolean i llogaritur nga pjesa e sipërme e qarkut .
Përkufizimi 6.15. Le të jepet CFE S mbi një bazë F ∪ X, bashkësia e kulmeve të së cilës është V.
- Supozohet se çdo hyrje e CFE llogarit funksionin Boolean me të cilin është etiketuar (d.m.th., disa ndryshore ose konstante).
- Nëse një kulm v ∈ V është etiketuar me një funksion f ∈ F (n), harku me numrin i (1≤i≤n) që hyn në të vjen nga kulmi ui ∈ V, i cili njehson funksionin gi, pastaj kulmin v njehson mbivendosjen f (g 1, ..., gn).
Kështu, nëse çdo kulm i CFE mbi F njehson një funksion, atëherë renditja në të cilën numërohen funksionet g 1, ..., gn, të zëvendësuara në vendet e variablave të funksionit f, është thelbësor në rastin e përgjithshëm. . Është e natyrshme të quajmë një funksion Boolean f në n variabla komutativ nëse ai ruan vlerën e tij nën një ndryshim arbitrar të ndryshoreve të tij. Në këtë rast, nuk duhet të shqetësohemi për numërimin e harqeve që hyjnë në pjesën e sipërme të qarkut, të shënuar me një funksion të tillë.
Shembulli 6.23. Konsideroni SPE në Fig. 6.25. Kulmet v 1 dhe v 2 janë hyrjet e SFE. Këto kulme llogaritin përkatësisht funksionet x dhe y. Pastaj kulmi v 3, si dhe kulmi v 4, sipas përkufizimit 6.15, njehson funksionin x | y (goditja e Schaeffer-it), dhe kulmi v 5 (dalja e rrjetit) njehson funksionin (x | y) l (x | y), e cila, dihet se është e barabartë me lidhëzën x y.
SPE e paraqitur në Fig. 6.26 ka dy dalje që llogaritin funksionet (x | x) | (y | y) = x ∨ y dhe (x | y) | (x | y) = x y.
Përkufizimi 6.16. Funksioni Boolean i llogaritur nga CFE mbi një bazë F ∪ X, është një funksion i llogaritur nga ndonjë prej daljeve të tij.
Kështu, CFE llogarit saktësisht sa funksione Boolean, sa rezultate. SFE në Fig. 6.25 llogarit një funksion, dhe SPE në Fig. 6.26 - dy.
Në rastin e përgjithshëm, nëse (x 1, ..., x n) është bashkësia e të gjitha variablave që shërbejnë si etiketa për hyrjet e qarkut S mbi një bazë F ∪ X me m dalje, CFE S përcakton shfaqjen e një kubi boolean B n në kubin boolean B m, d.m.th. operator boolean.
Vërejtje 6.10. Në disa raste, funksioni i llogaritur nga një SFE e caktuar përcaktohet disi ndryshe, duke supozuar se është një funksion i llogaritur nga çdo kulm nga nëngrupi i kulmeve të zgjedhura SFE. Në veçanti, mund të jenë rezultate. Në çdo rast, le të pranojmë të vizatojmë një shigjetë "dalje" nga kulmet e zgjedhura (në kuptimin e sapo treguar) të qarkut. #
Kështu, çdo qark portash llogarit disa operatorë Boolean, në veçanti, nëse numri i daljeve të qarkut është i barabartë me 1, atëherë ai njehson disa funksione Boolean.
E kundërta mund të vërtetohet gjithashtu: për çdo operator Boolean, një SFE mund të ndërtohet mbi një bazë F, ku F është një grup i plotë që llogarit operatorin e dhënë.
Ne përfaqësojmë funksionin y 1 në bazën Zhegalkin. Duke përdorur ligjet e de Morganit, ne marrim
(kujtoni se shuma e modulit 2 të çdo numri çift të termave të barabartë është e barabartë me 0).
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE për operatorin Boolean të dhënë në tabelë. 6.9, mbi bazën Zhegalkin është paraqitur në Fig. 6.27.
Kur dizajnoni një SFE, është e dobishme të mbani parasysh një parametër numerik të quajtur kompleksiteti i tij.
Kompleksiteti i SFE është numri i kulmeve të tij që nuk janë hyrje.
Treguar në Fig. 6.27 CFE mbi bazën Zhegalkin ka kompleksitet 5.
Le të shqyrtojmë tani CFE për të njëjtin operator mbi bazën standarde.
Sipas tabelës (shih tabelën 6.9), ne ndërtojmë SDNF për funksionin y 2:
y 2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Harta Karnot për këtë funksion, e paraqitur në Fig. 6.28 tregon se nuk mund të minimizohet (më saktë, SDNF e shkruar më sipër është DNF minimale për këtë funksion). Por ju mund të shkoni në anën tjetër. Mund të marrim parasysh tabelën. 6.9 si një tabelë që përcakton një funksion të pjesshëm boolean y 2 = y 2 (x 1 x 2 x 3 y 1). Duke minimizuar këtë funksion nga
harta Karnot * e paraqitur në Fig. 6.29, marrim
* Në këtë hartë, ne shënuam grupet në të cilat funksioni merr vlerën 0, duke vendosur zero në qelizat përkatëse. Kështu, ne duam të tërheqim edhe një herë vëmendjen për faktin se nuk duhet ngatërruar zerat me vizat: një vizë në qelizën e hartës që specifikon një funksion të pjesshëm do të thotë që vlera e funksionit nuk është përcaktuar në këtë grup, d.m.th. nuk është as 0 as 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
CFE mbi bazën standarde për operatorin Boolean të konsideruar është paraqitur në Fig. 6.30. Kompleksiteti i këtij SFE është 11. Vini re se kulmi që llogarit funksionin y 1 nuk është një dalje.
Operatori Boolean në këtë shembull llogarit shumën dyshifrore (modulin 2) të tre termave njëshifrorë. Mund të mendohet gjithashtu si një grumbullues binar njëbitësh - një bllok funksional i një grumbulluesi binar shumë-bit - për dy terma. Pastaj funksioni y 1 interpretohet si një "sinjal mbajtës" në bitin më domethënës. Në fig. 6.31 tregon "lidhjen" e tre SFE-ve (siç është paraqitur në Fig. 6.30), me ndihmën e të cilave llogaritet shuma e dy numrave binarë treshifrorë. Konstanta 0 futet në hyrjen e tretë të grumbulluesit për bitin më pak të rëndësishëm, dhe "sinjali i bartjes" i bitit më domethënës është biti më domethënës i shumës, i cili në rastin e përgjithshëm do të jetë një numër katërshifror. .
Vërejtje 6.11. Nëse e projektojmë SFE-në mbi një bazë standarde dhe duam të minimizojmë kompleksitetin e saj, atëherë së pari duhet të ndërtojmë minimumin përkatës DNF. Në këtë rast, mund të marrim parasysh një kriter tjetër me të cilin minimizohet vetë DNF - numri i mohimeve. Ndër të gjitha DNF-të minimale (në kuptimin e përkufizimit 6.6), duhet zgjedhur ato në të cilat numri i shfaqjes së variablave nën shenjën negative është më i vogli. Nga pikëpamja e kompleksitetit të SFE-së, e cila do të ndërtohet mbi bazën e minimumit DNF, kjo do të thotë se minimizon numrin e "invertorëve" - kulmet SFE të shënuara me funksionin mohues.
Për shembull, për funksionin e dhënë nga harta Karnot (Fig. 6.32), në bërthamën e përbërë nga implikantë të thjeshtë x 1 x 2 x 4 dhe x 1 x 3 x 4, duhet të shtoni një implikant të thjeshtë x 2 x 3 x 4. , dhe jo x 1 x 2 x 3 sepse nuk përmban negativë.
31. Diagramet e elementeve funksionale, rregullat e ndërtimit dhe funksionimit, metoda e sintezës së SFE, bazuar në SDNF dhe SKNF.
PërkufizimiPërkufizimi. Një element funksional është një model matematikor i një konverteri elementar diskret, i cili, sipas një ligji të caktuar, konverton sinjalet që vijnë tek ai në hyrje në një sinjal në dalje të konvertuesit. Nga elementet funksionale, me ndihmën e disa rregullave, është e mundur të ndërtohen modele më komplekse në strukturë dhe funksionim - diagrame nga elementë funksionalë. Në këto modele, sinjalet hyrëse dhe dalëse janë të koduara me karakteret 0 dhe 1.
Rregullat e ndërtimit. Për të marrë SFE komplekse nga më të thjeshtat, zbatohen në mënyrë sekuenciale operacionet e ndarjes së hyrjes ose daljes së qarkut, lidhjes së elementit funksional me qarkun dhe lidhjes së elementit funksional me hyrjen ose daljen e qarkut. Këto operacione ngjajnë me rregullat për marrjen e një formule komplekse nga ato më të thjeshta duke përdorur mbivendosje.
Sinteza e SFE. Meqenëse disjunksioni, lidhja dhe mohimi formojnë një sistem të plotë në klasë R 2, pastaj çdo funksion Boolean të n argumentet mund të zbatohen nga një qark i elementeve funksionale - ndarës, lidhës dhe inverter - me n hyrjet dhe një dalje. Për ta bërë këtë, për shembull, mund të shprehni këtë funksion Boolean përmes SDNF ose SKNF dhe më pas të "sintetizoni" formulën që rezulton në formën e një qarku elementësh funksionalë, duke zbatuar në mënyrë sekuenciale operacionet e ndarjes, bashkimit dhe lidhjes së mësipërme.
32. Metoda e sintezës së SFE, bazuar në zbatimin kompakt të të gjitha lidhjeve duke përdorur një multipol universal, kompleksitetin e qarqeve që rezultojnë.
Përkufizimi... Një funksion argumenti quhet një funksion Boolean (ose një funksion Boolean) nëse i cakton një numër çdo grupi.
Për të përcaktuar funksionet Boolean, ne do të përdorim tabela, vektorë, formula dhe grafikë. Le të marrim shënimin e mëposhtëm: është bashkësia e të gjitha grupeve, ku.
Përkufizimi. Një element funksional është një model matematikor i një konverteri elementar diskret, i cili, sipas një ligji të caktuar, konverton sinjalet që vijnë tek ai në hyrje në një sinjal në dalje të konvertuesit. Nga elementet funksionale, me ndihmën e disa rregullave, është e mundur të ndërtohen modele më komplekse në strukturë dhe funksionim - diagrame nga elementë funksionalë. Në këto modele, sinjalet hyrëse dhe dalëse janë të koduara me karakteret 0 dhe 1.
Metoda për sintezën e SFE, bazuar në zbatimin kompakt të të gjitha lidhjeve duke përdorur një shumëpolësh universal. Kjo metodë bazohet gjithashtu në paraqitjen e një funksioni në formën e SDNF, por lejon që dikush të ndërtojë qarqe më pak komplekse për shkak të një zbatimi më kompakt të lidhjeve. Zbërthimi i një funksioni në SDNF mund të përmbajë lidhje që kanë faktorë të përbashkët. Nëse dy lidhje të tilla zbatohen në një nënqark në një bllok, atëherë kjo do të kërkojë të paktën një lidhës më pak seç kërkohej më parë, me zbatimin e pavarur të të gjitha lidhjeve me metodën e parë të sintezës. Një zbatim kompakt i të gjitha lidhjeve të mundshme të gjatësisë n mund të arrihet duke përdorur një shumëpolësh universal të ndërtuar në mënyrë induktive, i cili ka n hyrjet dhe 2 n daljet ku n = 1,2,3, ... Përparësitë e metodës janë veçanërisht të dukshme kur një qark duhet të zbatojë një sistem me disa funksione Boolean. Në këtë rast, do të ishte e mundur që të ndahen dhe më pas të kalohen përmes ndarësve ato dalje të shumëpolit universal që korrespondojnë me lidhëzat e përfshira në SDNF të funksioneve të sistemit të caktuar. Kjo do të bënte të mundur arritjen me më pak lidhorë sesa nëse secili funksion i një sistemi të caktuar do të zbatohej në mënyrë të pavarur nga nënqarku i tij.
Kompleksiteti i një multipoli të tillë është L() =.
Nëse një qark portash Σ përmban saktësisht r elementet funksionale, atëherë thonë se ka kompleksitet r dhe shkruajeni në formën e barazisë L(Σ) = r.
| " |
Leksioni 2. Diagramet e elementeve funksionale
(SFE) në një bazë të caktuar. Kompleksiteti dhe thellësia
skema. Shembuj. Metoda për sintezën e SFE nga DNP.
Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva
Leksione me temë “Matematika diskrete 2”.
Viti i parë, grupi 141,
Fakulteti i CMC, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov
Ligjërata në faqen http://mk.cs.msu.su
Shembuj SFE Sinteza e SFE nga DNP
Diagramet e elementeve funksionale
Le të përcaktojmë qarqet e elementeve funksionale në një bazë të caktuar.
Le të na jepet një grup i funksioneve Boolean B = (g1 (x1, ..., xn1), ..., gs (x1, ..., xns)) P2, ku n1, ..., ns 0.
Le ta quajmë këtë grup një bazë.
Vini re se ky koncept i një baze nuk ka të bëjë fare me konceptin e një baze P2, i cili u konsiderua në algjebrën e logjikës.
Si rregull, ne do të konsiderojmë bazën standarde B0 = (x & y, x y, x).
Shembuj SFE Sinteza e SFE sipas DNF Përcaktimi i një qarku nga elementet funksionale Një qark nga elementët funksionalë (SFE) në bazën B0 = (x & y, x y, x) është
1) grafiku aciklik i drejtuar G = (V, E), secila kulm v V e të cilit ka një gjysmë shkallë hyrjeje d (v) jo më shumë se dy (d (v) 2);
2) çdo kulm v me gjysmë shkallë hyrjeje të barabartë me 0 (d (v) = 0) quhet hyrje (ose hyrje qarku) dhe asaj i është caktuar një variabël Boolean xi;
3) të gjitha nyjet e tjera (përveç hyrjeve) quhen nyje të brendshme të qarkut;
4) çdo kulmi v me gjysmë shkallë afrimi të barabartë me 1 (d (v) = 1) i caktohet një element mohues (funksional); të gjitha kulmet e tilla quhen inverterë;
5) çdo kulm v me një gjysmë shkallë hyrjeje të barabartë me 2 (d (v) = 2) i caktohet ose një element lidhor (funksional) &, ose një element shkëputës (funksional); të gjitha kulmet të cilave u caktohen elementet lidhëse quhen lidhëse, të gjitha kulmet të cilave u caktohen elementet e ndarjes quhen disjunktorë;
Shembuj SFE Sinteza e SFE sipas DNF Përcaktimi i një qarku nga elementët funksionalë (vazhdim)
6) përveç kësaj, variabla të ndryshme dalëse në çift y1, ..., ym u caktohen disa kulmeve.
Nëse jepet një SPE S, hyrjet e së cilës janë caktuar vetëm variablat x1, ..., xn, dhe me variablat dalëse y1, ..., ym, atëherë këtë SPE do ta shënojmë me S (x1, .. ., xn; y1, .. ., ym).
Shembuj SFE Sinteza e SFE nga DNP
- & nbsp– & nbsp–
Përcaktimi i thellësisë së kulmit SPE Me induksion, ne përcaktojmë thellësinë d (v) të kulmit v në SPE S.
1. Baza e induksionit. Çdo hyrje v e SFE S ka një thellësi të barabartë me 0: d (v) = 0.
- & nbsp– & nbsp–
SFE dhe karakteristikat e tyre Skemat e elementeve funksionale janë një model llogaritës.
Karakteristikat e CFE që kemi prezantuar tregojnë aspekte të ndryshme të efikasitetit llogaritës.
Kompleksiteti i CFE korrespondon me kohën e llogaritjes sekuenciale.
Thellësia CFE korrespondon me kohën e llogaritjes paralele.
Numri maksimal i kulmeve me të njëjtën thellësi në SFE korrespondon me numrin e procesorëve në llogaritjen paralele.
Shembuj SFE Sinteza e SFE nga DNF Shembull: shuma e tre biteve Zgjidhje. Ngjashëm me shembullin 6, ne shkruajmë një tabelë me shumën e tre biteve x, y dhe z. Kjo shumë mund të jetë gjithashtu një numër me dy shifra binare, kështu që ne prezantojmë dy ndryshore boolean
u0, u1 të tillë që x + y + z = 2u1 + u0:
- & nbsp– & nbsp–
Literatura për leksionin 4
1. Yablonsky S.V. Një hyrje në matematikën diskrete. M.:
Shkolla e Lartë, 2001. Pjesa V, Ch. 2, fq. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Probleme dhe ushtrime në matematikë diskrete. Moskë: Fizmatlit, 2004. Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.
Shembuj SFE Sinteza e SFE nga DNP
Kuptimi i mëposhtëm "inxhinierik-konstruktiv" mund t'i jepet paraqitjes së funksioneve të Bulit me formula. Ne do të konsiderojmë një formulë mbi disa grupe të fiksuara në mënyrë arbitrare si një "kuti të zezë", një lloj pajisjeje, në hyrjen e së cilës futen të gjitha llojet e grupeve të vlerave të ndryshueshme, dhe daljen që korrespondon me këto grupe vlerash. të funksionit të paraqitur nga formula (Fig. 6.22).
Për të kuptuar se si funksionon "kutia e zezë", duhet të çmontojmë procesin e ndërtimit të një formule nga nënformula. Arritja në nënformulat "bazë", d.m.th. elementet e një grupi, vijmë te "blloqe ndërtimi", elementë strukturorë nga të cilët është montuar një "kuti e zezë" që llogarit një funksion. Çdo funksion i "bazës" llogaritet nga "nyja" përkatëse, e cila konsiderohet si njësia më e vogël strukturore e "kutisë së zezë" tonë dhe struktura e saj e brendshme nuk analizohet më.
Shembulli 6.22. Le të zgjedhim një bazë standarde si një grup. Pastaj një formulë mbi një bazë standarde që përfaqëson një funksion (ekuivalencë) ndërtohet si më poshtë:
Llogaritja sipas kësaj formule (dhe procesi i ndërtimit të saj nga elementët e bazës standarde) mund të përshkruhet në mënyrë skematike siç tregohet në Fig. 6.23.
Një variabël (më saktë, vlera e kësaj ndryshoreje) futet në hyrjen e një elementi strukturor të quajtur inverter (Fig. 6.24, a) dhe duke llogaritur mohimin. Negativi i hequr nga dalja e inverterit, d.m.th. Funksioni futet në një nga hyrjet e lidhësit (Fig. 6.24.5), në hyrjen e dytë të të cilit futet një ndryshore. Një funksion shfaqet në daljen e lidhësit. Llogaritja e funksionit mund të gjurmohet në një mënyrë të ngjashme. Të dy këta funksione futen në hyrjet e ndarësit (Fig. 6.24, c), nga dalja e të cilit hiqet funksioni (kjo nuk është asgjë më shumë se një modul shumës 2:). Së fundi, ky funksion futet në hyrjen e inverterit, dalja e të cilit tashmë është një funksion (ekuivalencë).
Kështu, arrijmë në idenë e një "qarku" - një model matematikor i kalkulatorit të një funksioni Boolean, i përfaqësuar nga një formulë e caktuar, e mbledhur nga elementë strukturorë, secila prej të cilave llogarit një nga funksionet "bazë" Boolean. Në rastin e përgjithshëm, "qarku" llogarit një operator Boolean dhe çdo funksion koordinativ i këtij operatori hiqet nga një nga daljet e qarkut.
Matematikisht, një "skema" përkufizohet si një graf i drejtuar i një lloji të veçantë, në të cilin kulmet dhe harqet janë etiketuar.
Le të prezantojmë shënimin: nëse është një grup funksionesh Boolean, atëherë me shënon nëngrupin që përbëhet nga të gjitha funksionet e variablave.
Përkufizimi 6.14. Le të jenë të fiksuara grupet: (funksionet Boolean) dhe (ndryshoret Boolean).
Një qark i elementeve funksionale mbi një bazë (SFE), ose thjesht një qark mbi një bazë, gjithashtu një skemë (F, X), është një graf i drejtuar me fund të hapur (d.m.th., një rrjet), çdo kulm i të cilit është etiketuar me një nga elementët e grupit në mënyrë që kërkesat e mëposhtme:
1) çdo hyrje e rrjetit është etiketuar ose nga ndonjë variabël nga, ose nga ndonjë konstante nga;
2) nëse një kulm v i rrjetit është etiketuar me një funksion të ndryshoreve (dmth.), atëherë gjysma e shkallës së hyrjes së tij është e barabartë, dhe në grupin e harqeve që hyjnë në kulm, një numërim (një me një) është dhënë, në të cilën çdo hark merr një numër nga 1 në.
Gjatë vizatimit të diagrameve, hyrjet shënohen me rrathë, kurse kulmet që nuk janë hyrje shënohen me trekëndësha, brenda të cilëve shkruhet emërtimi i funksionit që shënon këtë kulm. Daljet janë shënuar me shigjeta "dalje". Në fig. 6.25 tregon SPE mbi bazën.
Nëse nënkuptohet baza, atëherë do të themi thjesht "skema". Përveç kësaj, nëse grupi i variablave fiksohet "një herë e përgjithmonë" dhe kur shqyrtojmë skema të ndryshme ne ndryshojmë vetëm një grup funksionesh, atëherë, siç bëmë, duke prezantuar konceptet e një formule dhe mbivendosjeje mbi një bazë të caktuar, ne do të flasim për një SFE mbi një bazë, duke supozuar çdo herë, që nënkupton një grup variablash të fiksuar dikur, të cilat (nëse kjo nuk dëmton saktësinë) nuk përmendet.
Le të përcaktojmë tani me induksion nocionin e një funksioni Boolean të llogaritur nga një kulm i një qarku.
Përkufizimi 6.15. Le të jepet CFE mbi bazën, bashkësia e kulmeve të së cilës është.
1. Supozohet se çdo hyrje e CFE llogarit funksionin Boolean me të cilin është etiketuar (d.m.th., disa ndryshore ose konstante).
2. Nëse një kulm shënohet me një funksion, një hark me një numër që hyn në të vjen nga kulmi që vlerëson funksionin, atëherë kulmi v njehson mbivendosjen.
Kështu, nëse çdo kulm i CFE mbi llogarit një funksion të caktuar, atëherë rendi në të cilin janë numëruar funksionet e zëvendësuara në vend të variablave të funksionit është thelbësor në rastin e përgjithshëm. Është e natyrshme të quajmë një funksion Boolean të variablave komutativ nëse ai ruan vlerën e tij nën një ndryshim arbitrar të variablave të tij. Në këtë rast, nuk duhet të shqetësohemi për numërimin e harqeve që hyjnë në pjesën e sipërme të qarkut, të shënuar me një funksion të tillë.
Shembulli 6.23. Konsideroni SPE në Fig. 6.25. Kulmet dhe janë hyrjet e SFE. Këto kulme llogaritin funksionet dhe, përkatësisht. Pastaj kulmi, si dhe kulmi, sipas përkufizimit 6.15, llogarit funksionin (goditja e Schaeffer-it), dhe kulmi (dalja e rrjetit) llogarit funksionin, i cili dihet se është i barabartë me lidhëzën.
SPE e paraqitur në Fig. 6.26, ka dy dalje që llogaritin funksionet dhe.
Përkufizimi 6.16. Një funksion Boolean i llogaritur nga CFE mbi një bazë është një funksion i llogaritur nga ndonjë prej daljeve të tij.
Kështu, CFE llogarit saktësisht aq funksione Boolean sa ka dalje. SFE në Fig. 6.25 llogarit një funksion, dhe SPE në Fig. 6.26 - dy.
Në rastin e përgjithshëm, nëse është grupi i të gjitha variablave që shërbejnë si etiketa për hyrjet e një qarku mbi një bazë që ka g dalje, CFE përcakton një hartë nga një kub Boolean në një kub Boolean, d.m.th. operator boolean.
Vërejtje 6.10. Në disa raste, funksioni i llogaritur nga një SFE e caktuar përcaktohet disi ndryshe, duke supozuar se është një funksion i llogaritur nga çdo kulm nga nëngrupi i kulmeve të zgjedhura SFE. Në veçanti, mund të jenë rezultate. Në çdo rast, le të pranojmë të vizatojmë një shigjetë "dalje" nga kulmet e zgjedhura (në kuptimin e sapo treguar) të qarkut.
Kështu, çdo qark portash llogarit disa operatorë Boolean, në veçanti, nëse numri i daljeve të qarkut është i barabartë me 1, atëherë ai njehson disa funksione Boolean.
E kundërta mund të vërtetohet gjithashtu: për çdo operator Boolean, një SFE mund të ndërtohet mbi një bazë, ku është grupi i plotë që njehson operatorin e dhënë.
Shembulli 6.24. Le ta vendosim tabelën në një operator Boolean që lidhet me (Tabela 6.9).
Është e lehtë të shihet nga tabela se (një funksion nuk është gjë tjetër veçse një funksion i shumicës së variablave, dhe minimumi DNF për të është shkruar më lart, shih Shembullin 6.12). Ne përfaqësojmë funksionin në bazën Zhegalkin. Duke përdorur ligjet e de Morganit, ne marrim
Duke pasur parasysh këtë, ne do të kemi
(kujtoni se shuma e modulit 2 të çdo numri çift të termave të barabartë është e barabartë me 0). Kështu që,
SFE për operatorin Boolean të dhënë në tabelë. 6.9, mbi bazën Zhegalkin është paraqitur në Fig. 6.27.
Kur dizajnoni një SFE, është e dobishme të mbani parasysh një parametër numerik të quajtur kompleksiteti i tij.
Kompleksiteti i SPE është numri i kulmeve të tij që nuk janë hyrje.
Treguar në Fig. 6.27 CFE mbi bazën Zhegalkin ka kompleksitet 5.
Le të shqyrtojmë tani CFE për të njëjtin operator mbi bazën standarde. Duke përdorur tabelën (shih tabelën 6.9), ne ndërtojmë SDNF për funksionin
Harta Karnot për këtë funksion, e paraqitur në Fig. 6.28 tregon se nuk mund të minimizohet (më saktë, SDNF e shkruar më sipër është DNF minimale për këtë funksion).
Por ju mund të shkoni në anën tjetër. Mund të marrim parasysh tabelën. 6.9 si një tabelë që përcakton një funksion të pjesshëm Boolean. Duke minimizuar këtë funksion sipas hartës Karnot * të paraqitur në Fig. 6.29, marrim
* Në këtë hartë, ne kemi shënuar në mënyrë eksplicite grupet në të cilat funksioni merr vlerën 0 duke vendosur zero në qelizat përkatëse. Kështu, ne duam të tërheqim edhe një herë vëmendjen për faktin se nuk duhet ngatërruar zerat me vizat: një vizë në qelizën e hartës që specifikon një funksion të pjesshëm do të thotë që vlera e funksionit nuk është përcaktuar në këtë grup, d.m.th. nuk është as 0 as 1.
CFE mbi bazën standarde për operatorin Boolean të konsideruar është paraqitur në Fig. 6.30. Kompleksiteti i këtij SFE është 11. Vini re se kulmi që llogarit funksionin nuk është një dalje.
Operatori Boolean në këtë shembull llogarit shumën dyshifrore (modulin 2) të tre termave njëshifrorë. Mund të mendohet gjithashtu si një grumbullues binar njëbitësh - një bllok funksional i një grumbulluesi binar shumë-bit - për dy terma. Pastaj funksioni r / 1 interpretohet si një "sinjal mbajtës" në bitin më domethënës. Në fig. 6.31 tregon "lidhjen" e tre SFE-ve (siç është paraqitur në Fig. 6.30), me ndihmën e të cilave llogaritet shuma e dy numrave binarë treshifrorë. Konstanta 0 futet në hyrjen e tretë të grumbulluesit për bitin më pak të rëndësishëm, dhe "sinjali i bartjes" i bitit më domethënës është biti më domethënës i shumës, i cili në rastin e përgjithshëm do të jetë një numër katërshifror. .
Madhësia: px
Filloni të shfaqni nga faqja:
Transkripti
1 Leksion 2. Skemat e elementeve funksionale (SFE) në një bazë të caktuar. Kompleksiteti dhe thellësia e skemës. Shembuj. Metoda për sintezën e SFE nga DNP. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Leksione për matematikën diskrete 2. Viti 1, grupi 141, Fakulteti i Matematikës Kompjuterike dhe Kibernetikës, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në sit
2 Diagramet e elementeve funksionale Le të përcaktojmë diagramet e elementeve funksionale në një bazë të caktuar. Le të na jepet një grup funksionesh Boolean B = (g 1 (x 1, ..., x n1), ..., gs (x 1, ..., x ns)) P 2, ku n 1, .. ., ns 0. Le ta quajmë këtë grup një bazë. Vini re se ky koncept i një baze nuk ka asnjë lidhje me konceptin e një baze P 2, e cila u konsiderua në algjebrën e logjikës. Si rregull, ne do të konsiderojmë bazën standarde B 0 = (x & y, x y, x).
3 Përkufizimi i një qarku të elementeve funksionale Një qark i elementeve funksionale (CFE) në bazën B 0 = (x & y, xy, x) është 1) një graf jociklik i drejtuar G = (V, E), secila kulm v V prej të cilave ka një gjysmë shkallë të hyrjes d (v ) jo më shumë se dy (d (v) 2); 2) çdo kulm v me gjysmë shkallë hyrjeje të barabartë me 0 (d (v) = 0) quhet hyrje (ose hyrje qarku) dhe asaj i është caktuar një variabël Boolean x i; 3) të gjitha nyjet e tjera (përveç hyrjeve) quhen nyje të brendshme të qarkut;
4 Përkufizimi i një qarku elementësh funksionalë (vazhdim) 4) çdo kulmi v me gjysmë shkallë hyrjeje të barabartë me 1 (d (v) = 1) i caktohet një element mohues (funksional); të gjitha kulmet e tilla quhen inverterë; 5) çdo kulm v me një gjysmë shkallë hyrjeje të barabartë me 2 (d (v) = 2) i caktohet ose një element lidhor (funksional) &, ose një element shkëputës (funksional); të gjitha kulmet të cilave u caktohen elementet lidhëse quhen lidhëse, të gjitha kulmet të cilave u caktohen elementet e ndarjes quhen disjunktorë;
5 Përkufizimi i një qarku elementësh funksionalë (vazhdim) 6) Përveç kësaj, disa nga kulmet u caktohen variabla të ndryshme dalëse y 1, ..., y m. Nëse jepet një SPE S, hyrjet e së cilës janë caktuar vetëm variablat x 1, ..., xn, dhe me variablat dalëse y 1, ..., ym, atëherë këtë SPE do ta shënojmë me S (x 1 , ..., xn; y 1, ..., ym).
6 Shembull i SFE Shembulli 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):
7 Shembull i SFE Shembulli 1. Si rregull, SFE-të përshkruhen si më poshtë S (x 1, x 2, x 3; y 1, y 2, y 3):
8 Përcaktimi i kompleksitetit të SFE Kompleksiteti L (S) i SFE S është numri i kulmeve të brendshme të kësaj SFE, d.m.th. numri i elementeve funksionale në SFE S.
9 Kompleksiteti i SFE Shembull 2. Kompleksiteti i SFE S:
10 Përcaktimi i thellësisë së kulmit të CFE Me induksion përcaktojmë thellësinë d (v) të kulmit v në CFE S. 1. Baza e induksionit. Çdo hyrje v SFE S ka një thellësi të barabartë me 0: d (v) = Tranzicion induktiv. 1) Nëse një hark nga kulmi v 1 çon në inverterin v të CFE S, atëherë d (v) = d (v 1)) Nëse harqet nga kulmet v 1 dhe v 2 çojnë në lidhësin ose ndarësin v të CFE S, atëherë d (v) = max (d (v 1), d (v 2)) + 1. Thellësia D (S) e SFE S quhet maksimumi i thellësive të kulmeve të tij.
11 Thellësia e SFE S Shembulli 3. Thellësia e majave të SFE S dhe thellësia e SFE S:
12 Përkufizimi i funksionimit të SFE-së Në çdo kulm të SFE-së realizohet (ose llogaritet) një funksion i caktuar Boolean. Me induksion, ne përcaktojmë një funksion Boolean që realizohet në kulmin v të CFE S. 1) Nëse v është kulmi i hyrjes dhe i është caktuar ndryshorja xi, atëherë funksioni fv = xi realizohet në kulmin v. . 2) Nëse një hark nga kulmi v 1 të çon në inverterin v, dhe funksioni f v1 realizohet në kulmin v 1, atëherë funksioni f v = f v1 realizohet në kulmin v. 3) Nëse harqet nga kulmet v 1 dhe v 2 çojnë në lidhësin (ose ndarësin) v, dhe funksionet f v1 dhe f v2 realizohen përkatësisht në kulmet v 1 dhe v 2, atëherë në kulmin v funksioni fv = f v1 & f v2 (përkatësisht fv = f v1 f v2).
13 Funksionimi i CFE Besohet se CFE S (x 1, ..., xn; y 1, ..., ym) zbaton sistemin e funksioneve Boolean FS = (f 1, ..., fm), të cilat realizohen në kulmet e tij dalëse y 1, ..., y m.
14 Funksionimi i SFE Shembulli 4. Funksionet Boolean të realizuara në kulmet e SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Programi linear Një program linear me hyrje x 1, ..., xn mbi një bazë B 0 = (x & y, xy, x) është një sekuencë z 1, z 2, ..., zt, në të cilën për secilin numri j, j = 1, ..., t, qëndron se 1) ose zj = xi; 2) ose z j = z k për k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 SFE dhe programet lineare Është e qartë se llogaritja në SFE mund të rishkruhet si një program linear. Në të kundërt, çdo program linear mund të përfaqësohet në formën e disa SFE.
17 CFE dhe programe lineare Shembulli 5. CFE S korrespondon me një program linear z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.
18 SFE dhe karakteristikat e tyre Skemat e elementeve funksionale janë një model llogaritës. Karakteristikat e CFE që kemi prezantuar tregojnë aspekte të ndryshme të efikasitetit llogaritës. Kompleksiteti i CFE korrespondon me kohën e llogaritjes sekuenciale. Thellësia CFE korrespondon me kohën e llogaritjes paralele. Numri maksimal i kulmeve me të njëjtën thellësi në SFE korrespondon me numrin e procesorëve në llogaritjen paralele.
19 Shembull: shuma e dy biteve Shembulli 6. Ndërtoni një SPE në një bazë standarde që zbaton (llogarit) shumën e dy biteve x dhe y. Zgjidhje. Le të shkruajmë një tabelë me shumën e dy biteve x dhe y. Kjo shumë mund të jetë një numër me dy shifra binare, kështu që ne prezantojmë dy variabla Boolean z 0, z 1, të tilla që x + y = 2z 1 + z 0: x y z 1 z
20 Shembull: shuma e dy biteve Zgjidhje (vazhdim). Atëherë z 0 = x y, z 1 = xy. Duke marrë parasysh se x y = (x y) (x y), marrim SPE: Është e qartë se L (S 1) = 3, dhe D (S 1) = 3.
21 SFE në një bazë arbitrare Koncepti i SFE në një bazë arbitrare B P 2 është prezantuar në mënyrë të ngjashme.
22 Shembull: shuma e tre biteve Shembulli 7. Ndërtoni CFE në bazën P2 2 (d.m.th., nga të gjitha funksionet Boolean në varësi të dy variablave), duke realizuar (llogaritur) shumën e tre biteve x, y dhe z.
23 Shembull: shuma e tre biteve Zgjidhje. Ngjashëm me shembullin 6, ne shkruajmë një tabelë me shumën e tre biteve x, y dhe z. Kjo shumë mund të jetë gjithashtu një numër me dy shifra binare, kështu që ne prezantojmë dy variabla Boolean u 0, u 1, të tilla që x + y + z = 2u 1 + u 0: x y z u 1 u
24 Shembull: shuma e tre biteve Zgjidhje (vazhdim). Atëherë u 0 = x y z, u 1 = xy xz yz. Duke marrë parasysh se xy xz yz = xy z (x y), marrim CFE: Shohim që L (S) = 5, dhe D (S) = 3.
25 Zbatimi i funksionit Boolean CFE A është e mundur të zbatohet një funksion arbitrar Boolean (ose një sistem funksionesh Boolean) në bazën B 0 = (x & y, x y, x)? Mund. Si mund të justifikohet kjo? Për shembull, si kjo. Sepse (x & y, x y, x) është një sistem i plotë në P 2, një funksion arbitrar Boolean f mund të përfaqësohet nga një formulë vetëm përmes lidhjes, disjunksionit dhe mohimit. Për shembull, në formën e një DNF të përsosur, nëse f 0, dhe në formën e x & x, nëse f = 0. Dhe më pas, duke përdorur këtë DNF (formulë), ndërtoni SFE-në përkatëse. Kjo metodë e ndërtimit të CFE për funksionet Boolean quhet metoda e sintezës DNF.
26 Sinteza e SFE-ve nga DNF Dhe çfarë kompleksiteti është marrë nga SFE S nga DNF për një funksion Boolean f (x 1, ..., x n), në varësi të n variablave? Një DNF e përsosur për një funksion f do të përmbajë më së shumti 2 n lidhje elementare. Çdo lidhje elementare është lidhja e n ndryshoreve ose mohimeve të tyre.
27 Sinteza e SFE sipas DNF-së Prandaj, qarku do të përmbajë: n inverterë për të zbatuar të gjitha mohimet e variablave x 1, ..., x n; nga (n 1) lidhës për zbatimin e secilës prej më së shumti 2 n lidhjeve elementare në një DNF të përsosur; më së shumti (2 n 1) ndarës për të zbatuar ndarjen e lidhëzave elementare të DNF. Marrim se L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Kompleksiteti i një funksioni Boolean Kompleksiteti L (f) i një funksioni Boolean f (x 1, ..., x n) në klasën e CFE-ve është kompleksiteti minimal midis të gjitha CFE-ve që zbatojnë funksionin f. Kështu, kemi vërtetuar teoremën: Teorema 1. Për një funksion arbitrar f (x 1, ..., x n) P 2, L (f) n 2 n + n është e vërtetë.
29 Problema për zgjidhje të pavarur 1. Për një funksion Boolean f (x 1, x 2, x 3) = (), ndërto një SPE në bazën standarde të kompleksitetit Për një funksion Boolean f (x 1, x 2, x 3 ) = (), ndërto një SPE në bazë standarde të kompleksitetit Për një funksion Boolean f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, ndërto CFE në bazën standarde të thellësisë Vërtetoni se në bazën standarde L (xy) = 4.
30 Literaturë për leksionin 4 1. Yablonskiy S.V. Një hyrje në matematikën diskrete. M .: Shkolla e Lartë, Pjesa V, Ch. 2, me Gavrilov G.P., Sapozhenko A.A. Probleme dhe ushtrime në matematikë diskrete. Moskë: Fizmatlit, Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.
31 Fundi i leksionit 4
Leksioni: Skemat e elementeve funksionale me vonesa (SPEZ), automatizimi i pasqyrimeve të kryera prej tyre. Përfaqësia e KAV SFEZ. Thjeshtimet e KAV. Dallimi dhe padallueshmëria e gjendjeve CAV. Teorema e Moore
Leksion: Teorema e Anselit mbi ndarjen e një kubi n-dimensionale në zinxhirë. Një teoremë mbi numrin e funksioneve monotone në algjebrën e logjikës. Një teoremë për dekodimin e funksioneve monotone të algjebrës së logjikës. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksion: Makinat me gjendje të fundme me dalje (KAV). Funksionet automatike, metodat e caktimit të tyre. Një teoremë mbi transformimin e sekuencave periodike nga funksionet automatike. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva
Ligjërata: Komplete të renditura pjesërisht (PNS). Diagrami CHUM. Artikujt maksimalë, minimalë, më të mëdhenj dhe më të vegjël. Zinxhirët dhe antizinxhirët, gjatësia dhe gjerësia e PLS përfundimtare. Një teoremë mbi zbërthimin e PN në antizinxhirë.
Leksioni 2. Vetitë e koeficientëve binomialë. Llogaritja e shumave dhe mënyra e gjenerimit të funksioneve (rasti përfundimtar). Koeficientët polinomialë. Vlerësimet për koeficientët binomialë dhe polinomialë. Vlerësimet e shumës
Ligjërata: Algoritmi për njohjen e plotësisë në P k. Klasa të mbyllura. Klasat e funksioneve që ruajnë grupet dhe ruajtjen e ndarjeve, mbyllja e tyre. Teorema e Kuznetsov mbi plotësinë funksionale. Klasat parapërfundojnë.
Leksioni 2. Kombinatorika. Vetitë e koeficientëve binomialë. Llogaritja e shumave dhe mënyra e gjenerimit të funksioneve. Koeficientët polinomialë. Vlerësimet për koeficientët binomialë dhe polinomialë. Asimptotike
Leksion: Funksionet me vlerë të fundme. Funksionet elementare me vlerë k. Metodat për përcaktimin e funksioneve me vlerë k: tabela, formula, forma 1 dhe 2, polinome. Plotësia. Teorema mbi plotësinë e sistemit Post. Funksioni Webb.
Leksioni 3. Sekuencat e përcaktuara nga relacionet e përsëritjes. Ekuacione lineare të përsëritura homogjene dhe johomogjene (LORU dhe LNRU). Zgjidhjet e përgjithshme të LORU dhe LNRU. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksioni 15. Funksionet e logjikave me vlera të fundme. Funksionet elementare të logjikës me vlerë k. Metodat për përcaktimin e funksioneve logjike me vlerë k: tabelat, formulat, format I dhe II, polinomet. Plotësia. Ligjërues - Profesor i Asociuar Selezneva
Leksion: Funksionet e logjikave me vlera të fundme. Funksionet elementare të logjikës me vlerë k. Metodat për përcaktimin e funksioneve logjike me vlerë k: tabelat, formulat, format I dhe II, polinomet. Plotësia. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksion: Funksioni Möbius në PLM. Funksioni Möbius në kubin n-dimensionale. Formula e përmbysjes së Mobius. Parimi përfshirje-përjashtim. Problemi i llogaritjes së numrit të permutacioneve-shqetësimeve. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksioni 2. Vetitë e koeficientëve binomialë. Mënyra e gjenerimit të funksioneve, llogaritja e shumave dhe vërtetimi i identiteteve. Koeficientët polinomialë. Parimi përfshirje-përjashtim. Ligjërues - Profesor i asociuar Svetlana Selezneva
Ligjërata: Funksionet thelbësore. Tre lema mbi funksionet thelbësore. Kriteri i plotësisë së Yablonsky. Kriteri i plotësisë së Slupeckit. Funksionet Scheffer. Ligjërues Profesor i asociuar Svetlana Nikolaevna Selezneva [email i mbrojtur]
Ligjërata: Numrat bazë kombinues. Vlerësime dhe asimptotika për numrat kombinatorë. Lektor - Profesor i asociuar Svetlana Nikolaevna Selezneva, Fakulteti i Matematikës Kompjuterike dhe Kibernetikës, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në faqen e internetit http://mk.cs.msu.su
Ligjërata: Vetitë e koeficientëve binomialë. Llogaritja e shumave dhe mënyra e gjenerimit të funksioneve (rasti përfundimtar). Koeficientët polinomialë. Vlerësimet për koeficientët binomialë dhe polinomialë. Vlerësimet për shumat e binomit
Leksion: Makinat me gjendje të fundme me dalje. Transformimi i sekuencave periodike nga makinat me gjendje të fundme me dalje. Dallimi i gjendjeve në makinat me gjendje të fundme me dalje. Thjeshtimi i makinerive. Lektor Selezneva
Ligjërata: Mbulesa e kompletit dhe mbulimi me matricë. Veshje gradient. Lema e mbulesës së gradientit. Vlerësimet për kardinalitetin e grupit të hijeve të një kubi n-dimensionale. Vlerësimet për gjatësinë e formave normale polinomike të funksioneve
Leksioni 5. Mbulimi i një grupi dhe mbulimi i një matrice. Veshje gradient. Lema e mbulesës së gradientit. Vlerësimet për kardinalitetin e grupit të hijeve të kubit Boolean. Kufijtë e gjatësisë për format normale polinomiale Boolean
Leksioni 3. Sekuencat e përcaktuara nga relacionet e përsëritjes. Ekuacione lineare të përsëritura homogjene dhe johomogjene (LORU dhe LNRU). Zgjidhjet e përgjithshme të LORU dhe LNRU. Shembuj Ligjërues - Profesor i Asociuar Selezneva
Leksioni 3. Marrëdhëniet mbi grupet. Vetitë. Formula përfshirje-përjashtim. Marrëdhënie ekuivalente. Marrëdhënie e pjesshme e rendit. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata mbi Modele Diskrete.
Leksioni 4. Veçoritë e logjikave shumëvlerore. Klasa e mbyllur, baza e klasës së mbyllur. Teoremat e Yanov dhe Muchnik mbi ekzistencën në logjika shumëvlerëshe të klasave të mbyllura pa bazë dhe klasave të mbyllura me të numërueshme
Ligjërata. Funksionet e argumentit natyror (rendit). Ekuacione lineare të përsëritura homogjene dhe johomogjene (LORU dhe LNRU). Zgjidhjet e përgjithshme të LORU dhe LNRU. Shembuj Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksion: Numri kromatik i një grafiku. Kriteri për grafikun me dy ngjyra. Teorema mbi kufijtë e sipërm dhe të poshtëm për numrin kromatik të një grafi. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata mbi Modele Diskrete.
Ligjërata: Grafikët dhe rrjetet. Vlerësimi i numrit të pseudografëve me skaje q. Vlerësimi për numrin e pemëve me q skaje. Grafikët planarë. Formula e Euler-it për grafikët planarë. Numri më i madh i skajeve në grafikët planarë. Joplanariteti
Leksioni 1. Kombinatorika. Vendosje, ndërrime, vendosje me përsëritje, kombinime, kombinime me përsëritje. Numri i tyre. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Departamenti i Kibernernetikës Matematikore
Ligjërata: Sekuenca. Ekuacione lineare të përsëritura homogjene dhe johomogjene. Zgjidhje të përgjithshme të ekuacioneve lineare të përsëritura homogjene dhe johomogjene. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva
Leksioni 8. Ngjyrosje. Ekuivalenca e ngjyrave në lidhje me grupin. Funksionet prodhuese. Një seri numërimi për forma dhe një seri numërimi për funksionet. Teorema e Polias. Lektor Selezneva Svetlana Nikolaevna
Ligjërata: Ngjyrosje. Ekuivalenca e ngjyrimeve në lidhje me një grup ndërrimi. Teorema e Polias (rast i veçantë). Funksionet prodhuese. Një seri numërimi për forma dhe një seri numërimi për funksionet. Teorema
Leksioni 2. Format normale lidhore. Implicente, një nënkuptim i thjeshtë i një funksioni. Funksioni i shkurtuar CNF i algjebrës së logjikës. Metodat për ndërtimin e një CNF të shkurtuar. Lektor Selezneva Svetlana Nikolaevna [email i mbrojtur]
Modelet dhe metodat matematikore të sintezës logjike të VLSI Vjeshtë 2015 Leksioni 4 Plani i leksionit Optimizimi logjik i qarqeve logjike kombinuese Mënyra të ndryshme të paraqitjes së funksioneve të algjebrës logjike (FAL)
Ligjërata: Automata të fundme jo-përcaktuese (NFA) pa dalje. Një teoremë mbi koincidencën e klasave të grupeve të fjalëve të pranuara nga automatet e fundme përcaktuese dhe jopërcaktuese të fundme. Procedura
Leksioni 1. Mostrat. Vendosjet, ndërrimet, vendosjet me përsëritje, kombinimet, kombinimet me përsëritjet, numri i tyre. Shembuj. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata në lëndën Diskrete
Leksioni 1. Objektet kombinuese: përzgjedhje, rregullime, ndërrime, rregullime me përsëritje, kombinime, kombinime me përsëritje, numri i tyre. Numrat kombinatorë: faktorial, faktorial në rënie, binom
LEKTURA 4 SKEMA NGA ELEMENTET FUNKSIONALE 1. Përkufizimet themelore Para së gjithash, është e nevojshme të merret parasysh përbërja. Një funksion mund të konsiderohet si një "kuti e zezë" që ka një hyrje dhe një dalje. Le
Leksioni 2. Algoritmi për njohjen e plotësisë në P k. Teorema e Kuznetsov. Klasa të mbyllura. Klasat e funksioneve të ruajtjes së grupeve. Klasat e funksioneve të ruajtjes së ndarjes. Klasat parapërfundojnë. Pedagog Doktor i Shkencave Fizike dhe Matematikore Selezneva
Leksioni 3. Polinomi Zhegalkin. Metodat për ndërtimin e polinomit Zhegalkin për një funksion. Implikimi linear i funksionit. Forma normale lidhore lineare (LCNF). Gjetja e të gjitha implikimeve lineare të funksionit. Ekzaminimi
Leksioni 2. Gjenerimi i funksioneve: llogaritja e shumave kombinuese dhe vërtetimi i identiteteve, numërimi i objekteve kombinuese. Parimi përfshirje-përjashtim. Numërimi i numrit të permutacioneve-shqetësimeve. Ligjërues -
Leksioni 5. Grafikët. Ngjyrosja e grafikut. Numri kromatik i grafikut. Kriteri për grafikun me dy ngjyra. Kufijtë e sipërm për numrin kromatik të një grafiku. Pedagog Doktor i Shkencave Fizike dhe Matematikore Selezneva Svetlana Nikolaevna [email i mbrojtur] Ligjërata
Ligjërata: Automat e fundme (KA) pa dalje (njohës të automatave të fundme). Diagramet e tranzicionit. Komplete (gjuhë) automatike. Lemë mbi vetitë e grupeve automatike. Një shembull i një grupi jo-automatik. Ligjërues
Leksioni 1. Funksionet me vlerë të fundme. Funksionet elementare me vlerë k. Metodat për përcaktimin e funksioneve me vlerë k: tabela, formula, forma 1 dhe 2, polinome. Plotësia. Teorema mbi plotësinë e sistemit Post. Funksioni Webb.
Leksioni 7. Problemi i zgjedhjes së rrugëve dhe rasti i veçantë i tij është problemi i shpërndarjes së fluturimeve sipas ditës. Modeli grafik për problemin e shpërndarjes së fluturimit. Numri kromatik i grafikut. Kriteri për dyngjyrosje të grafikut.
Lënda "Bazat e Kibernetikës" për studentët e specializimit 02/01/09/01 (matematikore dhe softuerike për kompjuterë) 1. Informacion i përgjithshëm (ngarkesa e studimit, format e kontrollit, etj.). Kursi është
Leksioni 6. Grafikët. Vetitë e trashëguara të grafikëve. Vlerësimi i numrit të skajeve në grafikët me veti trashëgimore. Grafikët ekstremë. Numri më i madh i skajeve në grafikët planar dhe pa trekëndësh me një të dhënë
Math-Net.Ru Portali Matematikor Gjith-Rus D. S. Romanov, Një metodë për sintezën e qarqeve lehtësisht të testueshme që pranojnë teste të vetme kontrolluese me gjatësi konstante, Diskr. Mat., 2014, Vëllimi 26, Numri 2,
Leksioni: Makinat e gjendjes së fundme pa dalje, përcaktuese dhe jopërcaktuese. Një teoremë mbi koincidencën e klasave të grupeve të fjalëve të pranuara nga automata të fundme përcaktuese dhe jopërcaktuese. Procedura
Punë praktike 2 Ndërtimi i trajtave normale të një funksioni logjik Qëllimi i punës: Të mësojë të ndërtojë trajta lidhore, veçuese, normale të përsosura të një funksioni logjik Përmbajtja e punës: Themelore.
Seminar mbi kompleksitetin e funksioneve Boolean Leksioni 1: Hyrje A. Kulikov Klubi i Shkencave Kompjuterike në POMI http://compsciclub.ru 09/25/2011 25/09/2011 1/26 Plani i leksionit 1 Funksionet Boolean 2 Qarqet Boolean 3 Pothuajse
Punë praktike 1 Analizë dhe sintezë e sistemeve të kontrollit logjik dhe rele HYRJE Pajisjet me veprim diskret të bëra në elementet e hidro-, pneumo- dhe elektroautomatike, dhe mikroprocesorët e kontrollit
Ligjërata: Shprehje të rregullta dhe grupe të rregullta. Teorema e Kleene mbi koincidencën e klasave të grupeve automatike dhe grupeve të rregullta. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata në matematikë diskrete
Leksioni 3 Algjebrat e Bulit dhe funksionet e Bulit Algjebrat e Bulit Koncepti i sistemeve algjebrike Sistemi algjebrik ose struktura algjebrike një grup simbolesh të një alfabeti të caktuar (mbështetje) me një të dhënë.
Leksioni 5. Grafikët. Shembuj të aplikimeve të grafikëve. Problemi i transportit. Rrjedha e rrjetit, teorema e Fordit dhe Fulkerson mbi rrjedhën maksimale të rrjetit. Algoritmi për ndërtimin e fluksit maksimal në rrjet. Ligjërues
Ligjërata: Grafikët. Shembuj të aplikimeve të grafikëve. Problemi i transportit. Rrjedha e rrjetit, teorema e Fordit dhe Fulkerson mbi rrjedhën maksimale të rrjetit. Algoritmi për ndërtimin e fluksit maksimal në rrjet. Ligjërues -
Mësimi 8 Kujtoni se për bashkësitë arbitrare A dhe B ka bashkësi A B = (x x A dhe x B); (kryqëzimi i A dhe B) A B = (x x A ose x B); (bashkimi i A dhe B) A \ B = (x x A dhe x / B) (diferenca e A dhe B).
Leksioni 7. Numrat Ramsey. Kufiri i sipërm për numrin Ramsey. Kufiri i poshtëm për numrin Ramsey. Lektor Selezneva Svetlana Nikolaevna [email i mbrojtur] Fakulteti i CMC, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në faqen e internetit http://mk.cs.msu.ru
Ligjërata: Grafikët. Konceptet bazë. Grafikët e lidhur. Pemët. Pemë që përfshin. Numri i kulmeve të varura në pemën që shtrihet. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata mbi Modele Diskrete. Mjeshtër,
Leksioni 11. Skemat Boolean. Matematikë diskrete, HSE, Fakulteti i Shkencave Kompjuterike (Vjeshtë 2014 Pranverë 2015) Me një qark Boolean në variablat x 1, ..., x n nënkuptojmë një sekuencë të funksioneve Boolean g
I MIRATUAR Zëvendës Rektori për Çështjet Akademike Yu. A. Samarskiy 10 qershor 2008 PROGRAM DHE DETYRA për lëndën STRUKTURA DISKRETE në drejtimin 010600 Fakulteti FIET Departamenti i Analizës së të Dhënave Kursi II semestri 4 Dy
Lomonosov i Universitetit Shtetëror të Moskës Fakulteti i Matematikës Kompjuterike dhe Kibernetikës S. A. Lozhkin ELEMENTET E TEORISË SINTEZËS SISTEMEVE DISKRETE TË KONTROLLIT Moskë 2016 Tabela e përmbajtjes
Leksion: Vetitë e trashëguara të grafikëve. Grafikët ekstremë. Numrat Ramsey. Lektor - Profesor i asociuar Svetlana Nikolaevna Selezneva, Fakulteti i Matematikës Kompjuterike dhe Kibernetikës, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në faqen e internetit http://mk.cs.msu.su Trashëgimia
Leksion: Veprimet në grupe automatike të fundme. Plotësimi, bashkimi, kryqëzimi, produkti dhe përsëritja e kompleteve të automatëve, automatizimi i tyre. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata
Ministria e Federatës Ruse për Komunikimet dhe Informatizimin e Rajonit të Vollgës Akademia Shtetërore e Telekomunikacionit dhe Departamentit të Informatikës së Matematikës së Lartë Miratuar nga Këshilli Metodik i PSATI më 29 mars 2002
Leksioni 5. Ngjyrosja e skajeve të grafikut. Indeksi kromatik i grafikut. Indeksi kromatik i grafikëve dypalësh. Kufijtë e sipërm dhe të poshtëm për indeksin kromatik të një grafiku. Lektor Selezneva Svetlana Nikolaevna [email i mbrojtur]
Math-Net.Ru Portali matematikor gjithë-rus NP Red'kin, Në qarqet që pranojnë teste të shkurtra diagnostike të vetme, Diskr. Mat., 1989, vëllimi 1, numri 3, 71 76 Përdorimi i All-rusit
LOGJIKA MATEMATIKE (1) Detyra për ushtrime praktike 1. Algjebra e pohimeve Pohim është një madhësi që mund të marrë dy kuptime: e vërtetë dhe e gabuar. Thëniet tregohen në latinisht të madh
