Veľkosť: px

Začnite zobrazovať zo stránky:

Prepis

1 Prednáška 2. Schémy funkčných prvkov (SFE) v určitom základe. Zložitosť a hĺbka schémy. Príklady. Spôsob syntézy SFE z DNP. Prednášajúca - docentka Svetlana Nikolaevna Selezneva Prednášky z diskrétnej matematiky 2. 1. ročník, skupina 141, Fakulta výpočtovej matematiky a kybernetiky Moskovskej štátnej univerzity pomenovaná po M.V. Lomonosov Prednášky na stránke

2 Schémy funkčných prvkov Definujme schémy funkčných prvkov v určitom základe. Dajme nám nejakú množinu booleovských funkcií B = (g 1 (x 1, ..., x n1), ..., gs (x 1, ..., x ns)) P 2, kde n 1, .. ., ns 0. Nazvime túto množinu základom. Všimnite si, že tento koncept bázy nemá nič spoločné s pojmom bázy P 2, o ktorej sa uvažovalo v algebre logiky. Spravidla budeme uvažovať štandardný základ B 0 = (x & y, x y, x).

3 Definícia obvodu funkčných prvkov Obvod funkčných prvkov (CFE) v báze B 0 = (x & y, xy, x) je 1) orientovaný acyklický graf G = (V, E), každý vrchol v V z ktorých má polovičný stupeň vstupu d (v ) nepresahujúci dva (d (v) 2); 2) každý vrchol v s polovičným stupňom vstupu rovným 0 (d (v) = 0) sa nazýva vstup (alebo vstup obvodu) a je mu priradená nejaká booleovská premenná x i; 3) všetky ostatné uzly (okrem vstupov) sa nazývajú vnútorné uzly obvodu;

4 Definícia okruhu funkčných prvkov (pokračovanie) 4) každému vrcholu v s polstupňom vstupu rovným 1 (d (v) = 1) je priradený (funkčný) negačný prvok; všetky takéto vrcholy sa nazývajú invertory; 5) každému vrcholu v s polovičným stupňom vstupu rovným 2 (d (v) = 2) je priradený buď (funkčný) spojkový prvok &, alebo (funkčný) disjunkčný prvok; všetky vrcholy, ku ktorým sú priradené prvky spojky, sa nazývajú spojky, všetky vrcholy, ku ktorým sú priradené prvky spojky, sa nazývajú spojky;

5 Definícia obvodu funkčných prvkov (pokračovanie) 6) k niektorým vrcholom sú navyše priradené párovo rôzne výstupné premenné y 1, ..., y m. Ak je daná SPE S, ktorej vstupom sú priradené len premenné x 1, ..., xn a pri výstupných premenných y 1, ..., ym, potom túto SPE označíme S (x 1 , ..., xn; y 1, ..., ym).

6 Príklad SFE Príklad 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):

7 Príklad SFE Príklad 1. SFE sú spravidla znázornené nasledovne S (x 1, x 2, x 3; y 1, y 2, y 3):

8 Stanovenie zložitosti SZZ Zložitosť L (S) SZZ je počet vnútorných vrcholov tejto SZZ, t.j. počet funkčných prvkov v SFE S.

9 Zložitosť SFE Príklad 2. Zložitosť SFE S:

10 Určenie hĺbky vrcholu CFE Indukciou určíme hĺbku d (v) vrcholu v v CFE S. 1. Základ indukcie. Každý vstup v SFE S má hĺbku rovnú 0: d (v) = indukčný prechod. 1) Ak oblúk z vrcholu v 1 vedie k meniču v CFE S, potom d (v) = d (v 1)) Ak oblúky z vrcholov v 1 a v 2 vedú do konjunktora alebo disjunktora v CFE S, potom d (v) = max (d (v 1), d (v 2)) + 1. Hĺbka D (S) SFE S sa nazýva maximum hĺbok jeho vrcholov.

11 Hĺbka SFE Príklad 3. Hĺbka vrcholov SFE S a hĺbka SFE S:

12 Definícia fungovania SFE V každom vrchole SFE sa realizuje (alebo vypočítava) určitá booleovská funkcia. Indukciou definujeme booleovskú funkciu, ktorá je realizovaná vo vrchole v CFE S. 1) Ak je v vstupný vrchol a je mu priradená premenná xi, potom je vo vrchole v realizovaná funkcia fv = xi. . 2) Ak oblúk z vrcholu v 1 vedie k meniču v, a funkcia f v1 je realizovaná vo vrchole v 1, potom je vo vrchole v realizovaná funkcia f v = f v1. 3) Ak oblúky z vrcholov v 1 a v 2 vedú do spojky (alebo disjunktora) v a funkcie f v1 a f v2 sú realizované vo vrcholoch v 1 a v 2, potom vo vrchole v funkcia fv = f v1 & f v2 (v tomto poradí fv = f v1 f v2).

13 Fungovanie CFE Predpokladá sa, že CFE S (x 1, ..., xn; y 1, ..., ym) implementuje systém booleovských funkcií FS = (f 1, ..., fm), ktoré sa realizujú na jej výstupných vrcholoch y 1, ..., y m.

14 Fungovanie SFE Príklad 4. Booleovské funkcie realizované vo vrcholoch SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).

15 Lineárny program Lineárny program so vstupmi x 1, ..., xn na báze B 0 = (x & y, xy, x) je postupnosť z 1, z 2, ..., zt, v ktorej pre každý číslo j, j = 1, ..., t, platí, že 1) buď zj = xi; 2) buď z j = z k pre 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 a lineárne programy Je zrejmé, že výpočet v SFE je možné prepísať ako lineárny program. Naopak, každý lineárny program môže byť reprezentovaný vo forme nejakého SFE.

17 CFE a lineárne programy Príklad 5. CFE S zodpovedá lineárnemu programu z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.

18 SFE a ich charakteristika Schémy funkčných prvkov sú výpočtovým modelom. Charakteristiky CFE, ktoré sme zaviedli, ukazujú rôzne aspekty výpočtovej efektívnosti. Zložitosť CFE zodpovedá času sekvenčného výpočtu. Hĺbka CFE zodpovedá času paralelného výpočtu. Maximálny počet vrcholov s rovnakou hĺbkou v SFE zodpovedá počtu procesorov pri paralelnom výpočte.

19 Príklad: súčet dvoch bitov Príklad 6. Zostrojte SPE na štandardnom základe, ktorý implementuje (vypočíta) súčet dvoch bitov x a y. Riešenie. Napíšme tabuľku súčtu dvoch bitov x a y. Tento súčet môže byť číslo s dvoma binárnymi číslicami, preto zavedieme dve booleovské premenné z 0, z 1, takže x + y = 2z 1 + z 0: x y z 1 z

20 Príklad: súčet dvoch bitov Riešenie (pokračovanie). Potom z 0 = x y, z 1 = xy. Ak vezmeme do úvahy, že x y = (x y) (x y), dostaneme SPE: Je jasné, že L (S 1) = 3 a D (S 1) = 3.

21 SZZ na ľubovoľnom základe Pojem SZZ na ľubovoľnom základe B P 2 je zavedený podobným spôsobom.

22 Príklad: súčet troch bitov Príklad 7. Zostrojte CFE na báze P2 2 (teda zo všetkých booleovských funkcií v závislosti od dvoch premenných), realizujte (vypočítajte) súčet troch bitov x, y a z.

23 Príklad: súčet troch bitov Riešenie. Podobne ako v príklade 6 napíšeme tabuľku súčtu troch bitov x, y a z. Tento súčet môže byť aj číslo s dvoma binárnymi číslicami, preto zavedieme dve booleovské premenné u 0, u 1 tak, že x + y + z = 2u 1 + u 0: x y z u 1 u

24 Príklad: súčet troch bitov Riešenie (pokračovanie). Potom u 0 = x y z, u 1 = xy xz yz. Ak vezmeme do úvahy, že xy xz yz = xy z (x y), dostaneme CFE: Vidíme, že L (S) = 5 a D (S) = 3.

25 Implementácia booleovskej funkcie CFE Je možné implementovať ľubovoľnú boolovskú funkciu (alebo systém boolovských funkcií) v báze B 0 = (x & y, x y, x)? Môcť. Ako sa to dá ospravedlniť? Napríklad takto. Pretože (x & y, x y, x) je úplný systém v P 2, ľubovoľná booleovská funkcia f môže byť reprezentovaná formulou iba prostredníctvom konjunkcie, disjunkcie a negácie. Napríklad vo forme dokonalého DNF, ak f 0, a vo forme x & x, ak f = 0. A potom pomocou tohto DNF (vzorca) zostrojte zodpovedajúcu SFE. Táto metóda konštrukcie CFE pre booleovské funkcie sa nazýva metóda syntézy DNF.

26 Syntéza SFE z DNF A akú zložitosť získame zo SFE S z DNF pre boolovskú funkciu f (x 1, ..., x n), závislú od n premenných? Dokonalý DNF pre funkciu f bude obsahovať najviac 2 n elementárnych spojok. Každá elementárna konjunkcia je konjunkcia n premenných alebo ich negácií.

27 Syntéza SFE podľa DNF Preto obvod bude obsahovať: n invertorov na realizáciu všetkých negácií premenných x 1, ..., x n; pomocou (n 1) spojky na realizáciu každého z najviac 2 n elementárnych spojok v dokonalom DNF; najviac (2 n 1) disjunktory na realizáciu disjunkcie elementárnych konjunkcií DNF. Dostaneme, že L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.

28 Zložitosť booleovskej funkcie Zložitosť L (f) boolovskej funkcie f (x 1, ..., x n) v triede CFE je minimálna zložitosť spomedzi všetkých CFE, ktoré implementujú funkciu f. Dokázali sme teda nasledujúcu vetu: Veta 1. Pre ľubovoľnú funkciu f (x 1, ..., x n) P 2, L (f) n 2 n + n.

29 Úlohy na nezávislé riešenie 1. Pre boolovskú funkciu f (x 1, x 2, x 3) = () zostrojte SPE v štandardnom základe zložitosti.Pre boolovskú funkciu f (x 1, x 2, x 3 ) = (), zostrojte SPE na štandardnom základe zložitosti Pre booleovskú funkciu f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4 zostrojte CFE na štandardnom základe hĺbky Dokážte, že v štandardnom základe L (xy) = 4.

30 Literatúra k prednáške 4 1. Yablonskiy S.V. Úvod do diskrétnej matematiky. M .: Vyššia škola, V. časť, Ch. 2, s Gavrilov G.P., Sapozhenko A.A. Úlohy a cvičenia z diskrétnej matematiky. Moskva: Fizmatlit, Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.

31 Koniec prednášky 4

Prednáška: Schémy funkčných prvkov s oneskorením (SPEZ), automatizácia nimi realizovaných mapovaní. Zastúpenie KAV SFEZ. Zjednodušenia KAV. Odlišnosť a nerozoznateľnosť štátov CAV. Moorova veta

Prednáška: Anselova veta o rozdelení n-rozmernej kocky na reťazce. Veta o počte monotónnych funkcií v algebre logiky. Veta o dekódovaní monotónnych funkcií algebry logiky. Prednášajúca - docentka Svetlana Selezneva

Prednáška: Konečné automaty s výstupom (KAV). Automatické funkcie, spôsoby ich priraďovania. Veta o transformácii periodických postupností automatickými funkciami. Prednášajúca - docentka Svetlana Nikolaevna Selezneva

Prednáška: Čiastočne usporiadané množiny (PNS). CHUM diagram. Maximum, minimum, najväčšie a najmenšie položky. Reťaze a antichains, dĺžka a šírka finálneho PLS. Veta o rozklade PN na antireťazce.

Prednáška 2. Vlastnosti binomických koeficientov. Výpočet súčtov a spôsob generovania funkcií (konečný prípad). Polynomické koeficienty. Odhady pre binomické a polynomické koeficienty. Sumárne odhady

Prednáška: Algoritmus na rozpoznávanie úplnosti v P k. Uzavreté triedy. Triedy funkcií zachovávajúce množiny a zachovávajúce partície, ich uzavretosť. Kuznecovova veta o funkčnej úplnosti. Preddokončené triedy.

Prednáška 2. Kombinatorika. Vlastnosti binomických koeficientov. Výpočet súčtov a spôsob generovania funkcií. Polynomické koeficienty. Odhady pre binomické a polynomické koeficienty. Asymptotické

Prednáška: Funkcie konečných hodnôt. Elementárne k-hodnotové funkcie. Metódy špecifikovania k-hodnotových funkcií: tabuľky, vzorce, 1. a 2. tvar, polynómy. Úplnosť. Veta o úplnosti systému Post. Funkcia Webb.

Prednáška 3. Postupnosti definované rekurentnými vzťahmi. Homogénne a nehomogénne lineárne rekurentné rovnice (LORU a LNRU). Všeobecné riešenia LORU a LNRU. Prednášajúca - docentka Svetlana Selezneva

Prednáška 15. Funkcie konečnej logiky. Elementárne funkcie k-hodnotovej logiky. Metódy špecifikácie k-hodnotových logických funkcií: tabuľky, vzorce, tvary I a II, polynómy. Úplnosť. Lektor - docent Selezneva

Prednáška: Funkcie konečnej logiky. Elementárne funkcie k-hodnotovej logiky. Metódy špecifikácie k-hodnotových logických funkcií: tabuľky, vzorce, tvary I a II, polynómy. Úplnosť. Prednášajúca - docentka Svetlana Selezneva

Prednáška: Möbiova funkcia na PLM. Möbiova funkcia na n-rozmernej kocke. Vzorec Mobiusovej inverzie. Princíp inklúzie-vylúčenia. Problém výpočtu počtu permutácií-poruch. Prednášajúca - docentka Svetlana Selezneva

Prednáška 2. Vlastnosti binomických koeficientov. Spôsob generovania funkcií, výpočet súčtov a preukazovanie totožnosti. Polynomické koeficienty. Princíp inklúzie-vylúčenia. Prednášajúca - docentka Svetlana Selezneva

Prednáška: Základné funkcie. Tri lemmy o základných funkciách. Yablonskyho kritérium úplnosti. Slupeckého kritérium úplnosti. Schefferove funkcie. Prednášajúca docentka Svetlana Nikolaevna Selezneva [e-mail chránený]

Prednáška: Základné kombinatorické čísla. Odhady a asymptotika pre kombinatorické čísla. Prednášajúca - docentka Svetlana Nikolaevna Selezneva, Fakulta výpočtovej matematiky a kybernetiky, Moskovská štátna univerzita pomenovaná po M.V. Lomonosov Prednášky na webovej stránke http://mk.cs.msu.su

Prednáška: Vlastnosti binomických koeficientov. Výpočet súčtov a spôsob generovania funkcií (konečný prípad). Polynomické koeficienty. Odhady pre binomické a polynomické koeficienty. Odhady pre binomické súčty

Prednáška: Konečné automaty s výstupom. Transformácia periodických sekvencií pomocou konečných automatov s výstupom. Rozlišovanie stavov v konečných automatoch s výstupom. Zjednodušenie strojov. Prednášajúca Selezneva

Prednáška: Krytie súpravy a krytie matrice. Gradientný náter. Gradient Cover Lemma. Odhady mohutnosti množiny tieňovania n-rozmernej kocky. Odhady dĺžky polynomických normálnych foriem funkcií

Prednáška 5. Krytie množiny a krytie matrice. Gradientný náter. Gradient Cover Lemma. Odhady mohutnosti množiny tieňovania booleovskej kocky. Hranice dĺžky pre booleovské polynomické normálne formy

Prednáška 3. Postupnosti definované rekurentnými vzťahmi. Homogénne a nehomogénne lineárne rekurentné rovnice (LORU a LNRU). Všeobecné riešenia LORU a LNRU. Príklady Prednášajúci - docent Selezneva

Prednáška 3. Vzťahy na množinách. Vlastnosti. Vzorec zahrnutia-vylúčenia. Vzťah ekvivalencie. Čiastočný vzťah objednávky. Lektorka - docentka Svetlana Nikolaevna Selezneva Prednáša o diskrétnych modeloch.

Prednáška 4. Vlastnosti viachodnotových logík. Uzavretá trieda, základ uzavretej triedy. Yanovove a Muchnikove teorémy o existencii vo viachodnotových logikách uzavretých tried bez bázy a uzavretých tried so spočítateľnými

Prednáška. Funkcie prirodzeného argumentu (sekvencie). Homogénne a nehomogénne lineárne rekurentné rovnice (LORU a LNRU). Všeobecné riešenia LORU a LNRU. Príklady Lektor - docent Svetlana Selezneva

Prednáška: Chromatické číslo grafu. Kritérium pre dvojfarebný graf. Vety o hornej a dolnej hranici pre chromatické číslo grafu. Lektorka - docentka Svetlana Nikolaevna Selezneva Prednáša o diskrétnych modeloch.

Prednáška: Grafy a siete. Odhad počtu pseudografov s q okrajmi. Odhad počtu stromov s q okrajmi. Rovinné grafy. Eulerov vzorec pre rovinné grafy. Najväčší počet hrán v rovinných grafoch. Nerovinnosť

Prednáška 1. Kombinatorika. Umiestnenia, permutácie, umiestnenia s opakovaniami, kombinácie, kombinácie s opakovaniami. Ich počet. Prednášajúca - docentka Svetlana Nikolaevna Selezneva Katedra matematickej kybernernetiky

Prednáška: Sekvencie. Homogénne a nehomogénne lineárne rekurentné rovnice. Všeobecné riešenia lineárnych rekurentných homogénnych a nehomogénnych rovníc. Prednášajúca - docentka Svetlana Nikolaevna Selezneva

Prednáška 8. Farbenie. Ekvivalencia sfarbenia vzhľadom na skupinu. Produktívne funkcie. Enumeračný rad pre tvary a enumeračný rad pre funkcie. Polyova veta. Lektorka Selezneva Svetlana Nikolaevna

Prednáška: Farbenie. Ekvivalencia zafarbení vzhľadom na permutačné skupiny. Polyova veta (špeciálny prípad). Produktívne funkcie. Enumeračný rad pre tvary a enumeračný rad pre funkcie. Veta

Prednáška 2. Konjunktívne normálne formy. Implicitný, jednoduchý implicitný z funkcie. Skrátená funkcia CNF algebry logiky. Metódy konštrukcie skráteného CNF. Lektorka Selezneva Svetlana Nikolaevna [e-mail chránený]

Matematické modely a metódy logickej syntézy VLSI jeseň 2015 Prednáška 4 Plán prednášok Logická optimalizácia kombinačných logických obvodov Rôzne spôsoby reprezentácie funkcií logickej algebry (FAL)

Prednáška: Nedeterministické konečné automaty (NFA) bez ukončenia. Veta o koincidencii tried množín slov, ktoré pripúšťajú konečné deterministické a konečné nedeterministické automaty. Postup

Prednáška 1. Ukážky. Umiestnenia, permutácie, umiestnenia s opakovaniami, kombinácie, kombinácie s opakovaniami, ich počet. Príklady. Lektorka - docentka Svetlana Nikolaevna Selezneva Prednášky na kurze Diskrétne

Prednáška 1. Kombinatorické objekty: výbery, usporiadania, permutácie, usporiadania s opakovaniami, kombinácie, kombinácie s opakovaniami, ich počet. Kombinatorické čísla: faktoriál, klesajúci faktoriál, binomický

PREDNÁŠKA 4 SCHÉMY Z FUNKČNÝCH PRVKOV 1. Základné definície V prvom rade je potrebné zvážiť zloženie. Funkciu si možno predstaviť ako „čiernu skrinku“, ktorá má vstup a výstup. Nechať byť

Prednáška 2. Algoritmus na rozpoznávanie úplnosti v P k. Kuznecovova veta. Uzavreté triedy. Triedy funkcií zachovávajúcich množinu. Triedy delených konzervačných funkcií. Preddokončené triedy. Prednášajúci doktor fyzikálnych a matematických vied Selezneva

Prednáška 3. Zhegalkinov polynóm. Metódy konštrukcie Zhegalkinovho polynómu pre funkciu. Lineárna implikácia funkcie. Lineárna konjunktívna normálna forma (LCNF). Nájdenie všetkých lineárnych implikácií funkcie. Vyšetrenie

Prednáška 2. Generovanie funkcií: výpočet kombinatorických súčtov a dokazovanie identít, enumerácia kombinatorických objektov. Princíp inklúzie-vylúčenia. Počítanie počtu permutácií-poruch. lektor -

Prednáška 5. Grafy. Farbenie grafu. Chromatické číslo grafu. Kritérium pre dvojfarebný graf. Horné hranice pre chromatické číslo grafu. Prednášajúci doktor fyzikálnych a matematických vied Selezneva Svetlana Nikolaevna [e-mail chránený] Prednášky

Prednáška: Konečné automaty (KA) bez ukončenia (rozpoznávače konečných automatov). Prechodové diagramy. Sady automatov (jazykov). Lema o vlastnostiach automatických súprav. Príklad neautomatickej súpravy. Prednášajúci

Prednáška 1. Funkcie konečných hodnôt. Elementárne k-hodnotové funkcie. Metódy špecifikovania k-hodnotových funkcií: tabuľky, vzorce, 1. a 2. tvar, polynómy. Úplnosť. Veta o úplnosti systému Post. Funkcia Webb.

Prednáška 7. Problém výberu trás a jeho špeciálny prípad je problém rozloženia letov podľa dňa. Grafický model pre problém rozloženia letu. Chromatické číslo grafu. Kritérium pre dvojfarebnosť grafu.

Kurz „Základy kybernetiky“ pre študentov špecializácie 01.02.09/01 (matematické a softvérové ​​vybavenie pre počítače) 1. Všeobecné informácie (študijná záťaž, formy riadenia a pod.). Kurz je

Prednáška 6. Grafy. Zdedené vlastnosti grafov. Odhad počtu hrán v grafoch s dedičnou vlastnosťou. Extrémne grafy. Najväčší počet hrán v rovinných a bez trojuholníkových grafoch s daným

Math-Net.Ru All-Russian Mathematical Portal D. S. Romanov, Metóda na syntézu ľahko testovateľných obvodov, ktoré umožňujú jednoduché kontrolné testy konštantnej dĺžky, Diskr. Mat., 2014, ročník 26, číslo 2,

Prednáška: Konečné automaty bez ukončenia, deterministické a nedeterministické. Veta o zhode tried množín slov, ktoré pripúšťajú konečné deterministické a nedeterministické automaty. Postup

Praktická práca 2 Konštrukcia normálnych tvarov logickej funkcie Cieľ práce: Naučiť sa zostavovať konjunktívne, disjunktívne, dokonalé normálne tvary logickej funkcie Obsah práce: Zákl.

Seminár o zložitosti booleovských funkcií Prednáška 1: Úvod Klub informatiky A. Kulikov v POMI http://compsciclub.ru 09/25/2011 09/25/2011 1/26 Plán prednášky 1 Booleovské funkcie 2 Booleovské obvody 3 Takmer

Praktická práca 1 Analýza a syntéza logických a reléových riadiacich systémov ÚVOD Diskrétne činné zariadenia vyrobené na prvkoch hydro-, pneumo- a elektroautomatiky a riadiacich mikroprocesorov

Prednáška: Regulárne výrazy a regulárne množiny. Kleeneho veta o koincidencii tried automatických množín a regulárnych množín. Prednášajúca - docentka Svetlana Nikolaevna Selezneva Prednášky z diskrétnej matematiky

Prednáška 3 Booleovské algebry a boolovské funkcie Booleovské algebry Pojem algebraických systémov Algebraický systém alebo algebraická štruktúra množina symbolov určitej abecedy (podpora) s daným

Prednáška 5. Grafy. Príklady aplikácií grafov. Problém s dopravou. Tok siete, Fordova a Fulkersonova veta o maximálnom toku siete. Algoritmus na zostavenie maximálneho toku v sieti. Prednášajúci

Prednáška: Grafy. Príklady aplikácií grafov. Problém s dopravou. Tok siete, Fordova a Fulkersonova veta o maximálnom toku siete. Algoritmus na zostavenie maximálneho toku v sieti. lektor -

Lekcia 8 Pripomeňme si, že pre ľubovoľné množiny A a B existujú množiny A B = (x x A a x B); (priesečník A a B) A B = (x x A alebo x B); (zjednotenie A a B) A \ B = (x x A a x / B) (rozdiel A a B).

Prednáška 7. Ramseyho čísla. Horná hranica pre Ramseyho číslo. Dolná hranica pre Ramseyho číslo. Lektorka Selezneva Svetlana Nikolaevna [e-mail chránený] Fakulta CMC Moskovskej štátnej univerzity pomenovaná po M.V. Lomonosov Prednášky na webovej stránke http://mk.cs.msu.ru

Prednáška: Grafy. Základné pojmy. Prepojené grafy. Stromy. Spanning tree. Počet visiacich vrcholov v kostre. Lektorka - docentka Svetlana Nikolaevna Selezneva Prednáša o diskrétnych modeloch. majster,

Prednáška 11. Booleovské schémy. Diskrétna matematika, HSE, Fakulta informatiky (jeseň 2014 jar 2015) Booleovským obvodom v premenných x 1, ..., x n rozumieme postupnosť booleovských funkcií g

SCHVÁLENÝ prorektor pre akademické záležitosti Yu.A. Samarskiy 10.6.2008 PROGRAM A ÚLOHY predmetu DISKRÉTNE ŠTRUKTÚRY v smere 010600 Fakulta FIET Katedra analýzy dát Predmet II semester 4 2

Moskovská štátna univerzita Lomonosova Fakulta výpočtovej matematiky a kybernetiky S. A. Ložkin PRVKY TEÓRIE SYNTÉZY DISKRÉTNYCH SYSTÉMOV RIADENIA Moskva 2016 Obsah

Prednáška: Zdedené vlastnosti grafov. Extrémne grafy. Ramseyho čísla. Prednášajúca - docentka Svetlana Nikolaevna Selezneva, Fakulta výpočtovej matematiky a kybernetiky, Moskovská štátna univerzita pomenovaná po M.V. Lomonosov Prednášky na webovej stránke http://mk.cs.msu.su Dedičné

Prednáška: Operácie na množinách konečných automatov. Doplnenie, spojenie, prienik, súčin a iterácia množín automatov, ich automatizácia. Prednáša - docentka Svetlana Nikolaevna Selezneva Prednášky

Ministerstvo Ruskej federácie pre komunikácie a informatizáciu Región Volga Štátna akadémia telekomunikácií a informatiky Katedra vyššej matematiky Schválené Metodickou radou PSATI 29. marca 2002

Prednáška 5. Farbenie hrán grafu. Chromatický index grafu. Chromatický index bipartitných grafov. Horná a dolná hranica chromatického indexu grafu. Lektorka Selezneva Svetlana Nikolaevna [e-mail chránený]

Math-Net.Ru All-ruský matematický portál NP Red'kin, O obvodoch, ktoré pripúšťajú krátke jednotlivé diagnostické testy, Diskr. Mat., 1989, ročník 1, číslo 3, 71 76 Použitie všerus.

MATEMATICKÁ LOGIKA (1) Úlohy na praktické cvičenia 1. Algebra výrokov Výrok je veličina, ktorá môže nadobúdať dva významy: pravdivý a nepravdivý. Výroky sú označené veľkou latinkou

V modernej technológii riadiacich a výpočtových zariadení zaujímajú dôležité miesto diskrétne prevodníky, to znamená zariadenia, ktoré majú určitý počet vstupov a výstupov. Množiny signálov prichádzajúcich na vstupy a vznikajúcich na výstupoch patria medzi známe konečné množiny.

Zdieľajte svoju prácu na sociálnych sieťach

Ak vám táto práca nevyhovovala, v spodnej časti stránky je zoznam podobných prác. Môžete tiež použiť tlačidlo vyhľadávania

Aranov Viktor Pavlovič. Diskrétna matematika. Časť 5. DNF a FE obvody.

Prednáška 28. Schémy funkčných prvkov. Problémy analýzy a syntézy

Prednáška 28. DIAGRAMY Z FUNKČNÝCH PRVKOV.

PROBLÉMY ANALÝZY A SYNTÉZY

Plán prednášok:

1. Pojem obvod funkčných prvkov(FE).

2. Problémy analýzy a syntézy obvodov z FV.

1. Koncept obvodu z FV

V moderných technológiách zaujímajú dôležité miesto riadiace a výpočtové zariadeniadiskrétne meniče, teda zariadenia, ktoré majú určitý počet vstupov a výstupov. Množiny signálov prichádzajúcich na vstupy a vznikajúcich na výstupoch patria medzi známe konečné množiny. Zariadenia konvertujú vstupné sady signálov na výstup. Matematickým modelom takýchto zariadení je tzvschémy funkčných prvkov(SFE).

Ako príklad uvažujme elektrický obvod troch diód a odporu, znázornený na obr. 1.

Ryža. 1. Elektrická schéma a jej symbol

V bodoch obvodu znázornených v kruhu sa v rôznych časoch môže objaviť buď vysoká úroveň, približne rovná 5 V, alebo nízka úroveň, približne rovná nule. V bode obvodu označenom pomlčkou je úroveň napätia neustále udržiavaná na nízkej úrovni.

Označené body budú interpretované ako vstupy a bod - ako výstup. Činnosť obvodu možno opísať nasledovne: ak všetky vstupy majú nízku úroveň napätia, potom je výstup tiež nízky, ak aspoň jeden zo vstupov má vysokú úroveň napätia, potom je výstup vysoký. Ak označíte stav s vysokou úrovňou napätia ako jedna a s úrovňou nízkeho napätia - nula, potom je možné nastaviť závislosť výstupu na vstupoch pomocou booleovskej funkcie.

Na základe toho sa vyššie uvedený obvod nazýva logický prvok „ALEBO“.

Takéto obvody môžu byť zostavené z elektronických elektrónok, elektromechanických spínačov, pneumatických prvkov atď. Závislosť výstupu na vstupoch možno opísať nielen ako disjunkciu, ale aj pomocou konjunkcie, negácie a zložitejších booleovských funkcií.

Budeme uvažovať logické hradla s rôznymi závislosťami výstupu od vstupov. Tieto prvky môžu byť navzájom prepojené, čím sa výstupy niektorých prvkov napájajú na vstupy iných. V dôsledku toho dostaneme SFE.

Vymedzenie pojmu SFE možno rozdeliť do dvoch etáp. V prvej fáze je odhalená štrukturálna časť tohto konceptu, v druhej - funkčná.

ja etapa. Rozdeľme túto fázu do niekoľkých bodov.

1  ... Existuje konečná množina objektov () tzvlogické prvky.Každý prvok má vstupy a jeden výstup. Prvok je graficky znázornený, ako je znázornené na obr. 2.

2  ... Indukciou definujeme pojem logická sieť ako objekt, v ktorom je určitý počet vstupov a určitý počet výstupov (obr. 3).

a) Základ indukcie. Izolovaný vrchol sa nazýva triviálna logická sieť. Podľa definície ide o vstup aj výstup (obr. 4).

… …

…

Ryža. Obr Obr 4

b) Indukčný prechod. Táto časť je založená na použití troch operácií.

Ja  ... Operácia kombinovania disjunktných sietí. Nech a sú dve disjunktné siete (bez spoločných prvkov, vstupov a výstupov), ktoré majú vstupy a výstupy. Sieťové prepojenie teoretických množín je logická sieť, ktorá má vstupy a výstupy.

II  ... Operácia pripevnenia prvku. Nech je sieť a prvok také, že vo vybraných rôznych výstupoch s číslami. Potom sa obrazec nazýva logická sieť, ktorá je výsledkom pripojenia prvku do siete. Vstupy sú všetky vstupy, výstupy sú všetky sieťové výstupy, okrem výstupov s číslami, ako aj výstup prvku. Sieť má vstupy a výstupy (obr. 5).

… …

Ryža. 6.

Ryža. 5

III  ... Operácia delenia výstupu. Nechajte v sieti zvýrazniť zásuvku s číslom. Potom sa obrázok nazýva logická sieť získaná rozdelením výstupu. Vstupy sú všetky vstupy, výstupy sú všetky výstupy siete s číslami 1,…,… a ďalšie dva výstupy, ktoré vznikli z výstupu s číslom siete (obr. 6). Má teda vstupy a výstupy.

3  ... Nechajte abecedy a budú dané.

Schéma funkčných prvkovsa nazýva logická sieť so vstupmi z abecedy a výstupmi z abecedy, ktorá sa označuje

. (1)

Tu je niekoľko príkladov obvodov.

1. Nech sa množina skladá z troch prvkov AND (konjunktor), OR (disjunktor) a NOT (invertor).

Potom bude obrázok (obr. 6) diagramom, pretože ho možno zostrojiť pomocou operácií I  - III .

 

Ryža. 6 Obr. 7

2. Obrázok znázornený na obr. 7 je tiež schéma.

II etapa. Stanovenie funkčnosti obvodu.

4  ... Porovnajme CFE (1) so systémom funkcií Booleovej algebry

(2)

tiež nazývanývodivosť tohto obvodu.

Príklad. a) Pre schému máme systém pozostávajúci z jednej rovnice

Alebo.

b) Pre obvod získame podobne

1. Implementácia booleovských funkcií obvodmi FE. Problémy analýzy a syntézy

obvodov z FV

Úloha analýzy: pre danú SFE (1) získať systém booleovských rovníc (2).

Algoritmus na riešenie problému: sledovanie operácií budovania siete I - III sekvenčne vypočítame funkcie na výstupoch sieťových prvkov.

Úloha syntézy: pre danú bázu funkčných prvkov a ľubovoľný systém booleovských rovníc (2) zostrojte z danej MKP obvod (1), ktorý túto sústavu rovníc implementuje.

Existenciu riešenia problému syntézy určuje Postova veta, podľa ktorej musí byť systém funkcií, ktoré implementujú základné FE, úplný. Funkcie môžu byť reprezentované ako superpozícia funkcií a každý krok superpozície zodpovedá určitej kombinácii prvkov.

Príklad. Pre funkciu

(3)

Diagram zodpovedajúci superpozícii na pravej strane vzorca (3) je znázornený na obr. osem.

  

Ryža. osem

Problém syntézy spočíva v tom, že pre daný systém booleovských rovníc je možné zostrojiť mnoho obvodov MKP, ktoré tento systém implementujú. V tomto ohľade vzniká problém optimálnej syntézy: zo všetkých druhov schém, ktoré implementujú danú funkciu, vyberte tú najlepšiu podľa jedného alebo druhého kritéria, napríklad s najmenším počtom prvkov. Takéto schémy budú tzv minimálne.

Nasledujúce tvrdenie je pravdivé.

Veta. Existuje algoritmus, ktorý vytvára minimálny obvod pre každý systém booleovských funkcií.

Tento algoritmus na konštruovanie minimálnych obvodov patrí do triedy algoritmov typu "brute force", keďže je založený na prezeraní všetkých obvodov do určitej zložitosti. Vyčerpávajúce vyhľadávacie algoritmy sú spravidla veľmi pracné a nevhodné na praktické účely. Preto nižšie uvažujeme o jednoduchšom probléme, pre ktorý pôvodný systém rovníc obsahuje jednu rovnicu

a preto má požadovaný obvod jeden výstup.

Zložitosť minimálneho obvodu je označená. Nebudeme uvažovať o probléme syntézy pre samostatnú funkciu, ale pre celú triedu funkcií premenných. Kvalita syntéznych algoritmov sa porovnáva porovnaním takzvaných Shannonových funkcií. Nechať byť

- minimálna zložitosť implementovaných schém, ktoré sa získajú pomocou algoritmu.

Funkcie sa nazývajú Shannonove funkcie a je to zrejmé

Problémom syntézy je nájsť algoritmus, ktorému by sa čo najviac približoval, a tak, aby zložitosť algoritmu bola podstatne menšia ako zložitosť algoritmu vyčerpávajúceho vyhľadávania. Pri tejto formulácii problému sa nevyžaduje, aby algoritmus našiel minimálny obvod pre každú funkciu, je len potrebné, aby najjednoduchší obvod získaný s pomocou mal zložitosť, ktorá výrazne nepresahuje.

Ďalšie podobné diela, ktoré by vás mohli zaujímať.Wshm>
9013.		METÓDY SYNTÉZY SCHÉM Z FE. DIAGRAMY DEKODÉRA A BINÁRNEJ Sčítačky	153,07 kB
	Všeobecná teória syntézy CFE vedie k záveru, že väčšina booleovských funkcií pre veľké hodnoty má zložité minimálne obvody. To znamená, že veľmi úzka trieda booleovských funkcií má praktickú hodnotu z hľadiska syntézy.
5321.		Typy a hodnoty parametrov automatickej ochrany pre rôzne prvky danej konštrukčnej schémy	526,7 kB
	Na zabezpečenie normálnej prevádzky elektrizačnej sústavy a spotrebiteľov elektriny je potrebné čo najskôr identifikovať a oddeliť miesto poškodenia od nepoškodenej siete, čím sa obnovia normálne prevádzkové podmienky pre elektrickú sústavu a spotrebiteľov.
5384.		Vývoj elektrického obvodu stojana na analýzu činnosti taktovaného dekodéra pre 4 vstupy a 16 výstupov	626,63 kB
	Pre skvalitnenie prevádzky železničných koľajových vozidiel ATP bola vypracovaná organizačná štruktúra systému údržby a opráv železničných koľajových vozidiel ATP a navrhnutý súbor zariadení na diagnostiku a údržbu. Hlavnou úlohou fungovania opravárenských zariadení podniku je zabezpečiť nepretržitú prevádzku zariadení. Zahŕňa: opravárenskú a reštaurátorskú základňu podniku, sklady, predajne a všeobecné oddelenia opravárenských zariadení, technologické vybavenie, dispečing. Organizácia...
1886.		Etapy systémovej analýzy, ich hlavné ciele, ciele	27,44 kB
	Teória optimálnych systémov nám umožňuje odhadnúť hranicu dosiahnuteľnú v optimálnom systéme, porovnať ju s ukazovateľmi súčasného neoptimálneho systému a zistiť, či je v posudzovanom prípade vhodné vyvinúť optimálny systém. Pre automaticky riadený proces automaticky riadeného systému sa rozlišujú dva stupne optimalizácie: statický a dynamický. Statická optimalizácia rieši otázky tvorby a implementácie optimálneho modelu procesu a dynamického ...
5123.		Rozvoj funkčných stratégií	35,44 kB
	HR stratégie. Funkcie a štruktúra riadenia. Manažérske funkcie a ich úloha pri formovaní riadiacich štruktúr. Hierarchický typ štruktúry riadenia.
20368.		Vplyv zloženia komponentov receptúry a technológií na spotrebiteľské vlastnosti funkčných produktov	742,05 kB
	Koncept optimálnej výživy je akceptovaný modernou medicínou. To znamená, že došlo k prechodu od konceptu adekvátnej výživy, kedy boli hlavne regulované a normalizované makronutrienty - zdroje tukov, zdroje energie, plastické hmoty (lipidy, bielkoviny, tuky), ku konceptu optimálnej výživy, kedy Spektrum živín potrebných pre životne dôležitú činnosť organizmu a ďalšie vedľajšie zložky, ktoré boli predtým prehliadané, sa výrazne rozširuje.
4706.		Spôsoby syntézy Me karboxylátov	9,26 MB
	Podstatou metódy je rozpustenie oxidu, hydroxidu alebo uhličitanu kovu vo vodnom roztoku zodpovedajúcej kyseliny. Produkt sa izoluje odparením roztoku pred kryštalizáciou alebo filtráciou zrazeniny, ak je karboxylát nerozpustný alebo obmedzene rozpustný vo vode.
15923.		Základné metódy syntézy pyrazalodiazepínov	263,39 kB
	Nové metódy syntézy pyrazolodiazepínových derivátov. Vývoj nových stratégií syntézy je veľmi zaujímavý. Systematické a zovšeobecňujúce štúdie syntézy pyrazolodiazepínových derivátov sa neuskutočnili, niektoré otázky zostávajú nedotknuté kontroverziou alebo sú úplne nevyriešené.
11978.		Zariadenia energetických technológií na báze hydrotermálnej oxidácie hliníka na výrobu elektriny, tepla, vodíka a funkčných nanomateriálov	49,89 kB
	Vývoj je založený na reakcii hydrotermálnej oxidácie hliníka, pri ktorej sa uvoľňuje veľké množstvo tepelnej energie a vznikajú oxidy hliníka a vodík: l2H2O → lOOH boehmit15H2415. Ako počiatočné činidlá sa používajú destilovaná voda a mikrónové hliníkové prášky. Inštalácia KEU10 Inštalácia ETK100 Technické vlastnosti inštalácie ETK100: Parameter Hodnota Spotreba hliníka kg h 101 Spotreba vody na vstupe do zariadenia na úpravu vody kg h 484 Produktivita pre vodík nm3 110 Tepelný výkon ...
6605.		Expertné systémy. Návrh TP metódou syntézy	11,67 kB
	Reprezentovať hromadenie znalostí a udržiavať ich v aktuálnom stave je komplexná úloha skúmaná v sekcii informatiky nazývanej znalostné inžinierstvo. Znalostný inžinier sa podieľa na rozvoji znalostnej bázy – jadra systémov nazývaných inteligentný. Inteligentné systémy sa najčastejšie používajú na riešenie zložitých problémov, kde je hlavná zložitosť riešenia ...

5. Priebežné grafy: Eulerove reťazce a cykly, nevyhnutné a postačujúce podmienky ich existencie, Fleuryho algoritmus.

6. Priebežné grafy: Hamiltonovské reťazce a cykly, dostatočné podmienky pre ich existenciu.

7. Stromy, ich vlastnosti, kódovanie stromov, kostry.

8. Extrémne problémy v teórii grafov: minimálny kostra, Prim a Kruskalov algoritmus.

9. Extrémne problémy v teórii grafov: problém obchodného cestujúceho, "chamtivý" algoritmus

10. Extrémne problémy v teórii grafov: problém najkratšej cesty, Dijkstrov algoritmus.

11. Izomorfizmus a homeomorfizmus grafov, metódy dokazovania izomorfizmu a neizomorfizmu grafov.

12. Zbalenie rovinných grafov, rovinné grafy, Pontryagin-Kuratovského kritérium.

13. Nevyhnutné podmienky pre rovinnosť, Eulerov vzorec pre rovinné grafy.

14. Pravidelné zafarbenie vrcholov grafov, chromatické číslo, nerovnosti pre chromatické číslo.

15. Päťfarebná veta, štvorfarebná domnienka, "chamtivý" algoritmus.

16. Chromatický polynóm, jeho nájdenie a vlastnosti.

17. Problém hľadania východu z bludiska, vyfarbenie okrajov grafu.

19. Plánovanie realizácie komplexu prác v čo najkratšom čase s využitím metód teórie grafov.

20. Elementárne booleovské funkcie a metódy ich priraďovania (tabuľkové, vektorové, vzorce, grafické, Karnotova mapa).

21. Esenciálne a fiktívne premenné booleovských funkcií, základné identity, ekvivalentné transformácie vzorcov.

22. Lineárne a nelineárne Zhegalkinove polynómy, rozšírenie booleovských funkcií v Zhegalkinovom polynóme metódou nedefinovaných koeficientov.

23. Lineárne a nelineárne Zhegalkinove polynómy, rozšírenie booleovských funkcií v Zhegalkinovom polynóme metódou ekvivalentných transformácií.

24. Dekompozícia booleovských funkcií v sdnf a sknf.

25. Minimalizácia dnf a knf metódou ekvivalentných transformácií.

26. Minimalizácia dnf a knf pomocou Karnotových máp.

27. Uzavreté triedy booleovských funkcií m0, m1, l, lemma na nelineárnej funkcii.

28. Uzavreté triedy booleovských funkcií s a m, lemy o nesamoduálnych a nemonotónnych funkciách.

29. Úplný systém funkcií, veta o dvoch systémoch booleovských funkcií.

30. Postova veta o úplnosti systému booleovských funkcií, algoritmus na kontrolu úplnosti systému, základ.

31. Schémy funkčných prvkov, pravidlá konštrukcie a fungovania, spôsob syntézy SFE na báze SDNF a SKNF.

32. Metóda syntézy SFE, založená na kompaktnej realizácii všetkých konjunkcií pomocou univerzálneho multipólu, zložitosť výsledných obvodov.

33. Základné kombinatorické operácie, kombinácie a umiestnenie (s návratom a bez návratu prvkov).

34. Kombinatorické princípy sčítania, násobenia, sčítania, inklúzie-vylúčenia.

35. Binomické koeficienty, ich vlastnosti, Newtonov binom.

36. Pascalov trojuholník, polynomický vzorec.

37. Abecedné kódovanie: nevyhnutné a postačujúce podmienky pre jednoznačnosť dekódovania.

38. Abecedné kódovanie: Markovova veta, Markovov algoritmus.

39. Kódy s minimálnou redundanciou (Huffmanove kódy), metóda konštrukcie.

40. Lineárne kódy, generujúca matica, duálny kód.

41. Samoopravné kódy (Hammingove kódy), konštrukčná metóda.

42. Definícia, schéma a fungovanie abstraktného automatu, metódy priraďovania automatov.

43. Typy konečných automatov, Mealyho a Mooreove automaty, generátorové automaty.

44. Slová a jazyky, operácie s nimi, ich vlastnosti.

45. Regulárne výrazy a regulárne jazyky, Kleenova veta.

46.Problém analýzy automatických rozpoznávačov.

47. Problém syntézy rozpoznávačov.

48. Ekvivalentné stavy rozpoznávača automatov, ekvivalentné rozpoznávače automatov, minimalizácia rozpoznávačov automatov, Mealyho algoritmus.

49. Ekvivalentné stavy automat-konvertor, ekvivalentné automaty-prevodníky, minimalizácia automat-konvertorov, Mealyho algoritmus.

50. Deterministické a nedeterministické funkcie, príklady, metódy priraďovania.

51. Obmedzené deterministické (automatické) funkcie, spôsoby ich priraďovania.

52. Logické automaty, metódy ich priraďovania, syntéza binárnej sčítačky.

53. Operácie na logických automatoch: superpozícia a zavedenie spätnej väzby.

31. Schémy funkčných prvkov, pravidlá konštrukcie a fungovania, spôsob syntézy SFE na báze SDNF a SKNF.

Definícia

Definícia. Funkčný prvok je matematický model elementárneho diskrétneho prevodníka, ktorý podľa určitého zákona premieňa signály prichádzajúce k nemu na vstupe na signál na výstupe prevodníka. Z funkčných prvkov je možné pomocou niektorých pravidiel zostaviť štruktúrou a fungovaním zložitejšie modely - diagramy z funkčných prvkov. V týchto modeloch sú vstupné a výstupné signály kódované znakmi 0 a 1.

Stavebné pravidlá. Na získanie zložitých SFE z jednoduchších sa postupne aplikujú operácie rozdelenia vstupu alebo výstupu obvodu, pripojenie funkčného prvku k obvodu a pripojenie funkčného prvku k vstupu alebo výstupu obvodu. Tieto operácie sa podobajú pravidlám na získanie zložitého vzorca z jednoduchších pomocou superpozície.

Syntéza SFE. Keďže disjunkcia, konjunkcia a negácia tvoria ucelený systém v triede R 2, potom ľubovoľná booleovská funkcia n argumenty môžu byť implementované obvodom funkčných prvkov - disjunktorov, konjunktorov a invertorov - s n vstupy a jeden výstup. Aby ste to dosiahli, môžete napríklad vyjadriť túto booleovskú funkciu prostredníctvom SDNF alebo SKNF a potom „syntetizovať“ výsledný vzorec vo forme obvodu funkčných prvkov, pričom postupne použijete vyššie uvedené operácie rozdelenia, pripojenia a pripojenia.

32. Metóda syntézy SFE, založená na kompaktnej realizácii všetkých konjunkcií pomocou univerzálneho multipólu, zložitosť výsledných obvodov.

Definícia... Funkcia argumentov sa nazýva boolovská funkcia (alebo boolovská funkcia), ak každej množine priraďuje číslo.

Na definovanie boolovských funkcií použijeme tabuľky, vektory, vzorce a grafy. Zoberme si nasledujúci zápis: je množina všetkých množín, kde.

Definícia. Funkčný prvok je matematický model elementárneho diskrétneho prevodníka, ktorý podľa určitého zákona premieňa signály prichádzajúce k nemu na vstupe na signál na výstupe prevodníka. Z funkčných prvkov je možné pomocou niektorých pravidiel zostaviť štruktúrou a fungovaním zložitejšie modely - diagramy z funkčných prvkov. V týchto modeloch sú vstupné a výstupné signály kódované znakmi 0 a 1.

Metóda syntézy SFE, založená na kompaktnej implementácii všetkých konjunkcií pomocou univerzálneho multipólu. Táto metóda je tiež založená na reprezentácii funkcie vo forme SDNF, ale umožňuje vytvárať menej zložité obvody vďaka kompaktnejšej implementácii konjunkcií. Dekompozícia funkcie v SDNF môže obsahovať konjunkcie, ktoré majú spoločné faktory. Ak sú dve takéto konjunkcie implementované s jedným podobvodom v bloku, potom to bude vyžadovať aspoň o jeden menej konjunktorov, ako bolo požadované predtým, s nezávislou implementáciou všetkých konjunkcií prvou metódou syntézy. Kompaktná implementácia všetkých možných konjunkcií dĺžky n možno dosiahnuť pomocou indukčne stavaného univerzálneho multipólu, ktorý má n vstupy a 2 n výstupy kde n = 1,2,3, ... Výhody metódy sú viditeľné najmä vtedy, keď jeden obvod potrebuje implementovať systém niekoľkých booleovských funkcií. V tomto prípade by bolo možné rozdeliť a potom cez disjunktory prejsť tie výstupy univerzálneho multipólu, ktoré zodpovedajú konjunkciám zahrnutým v SDNF funkcií daného systému. To by umožnilo vystačiť si s menším počtom konjunktorov, ako keby bola každá funkcia daného systému samostatne implementovaná vlastným podobvodom.

Zložitosť takéhoto multipólu je L() =.

Ak obvod brán Σ obsahuje presne r funkčné prvky, potom hovoria, že to má zložitosť r a napíšte to vo forme rovnosti L(Σ) = r.

"

Reprezentácii booleovských funkcií pomocou vzorcov možno dať nasledujúci „inžiniersko-konštruktívny“ zmysel. Vzorec Ф (x 1, ..., xn) nad nejakou ľubovoľne fixnou množinou F budeme považovať za „čiernu skrinku“, určité zariadenie, do ktorého vstupu sa privádzajú všetky možné množiny hodnôt premenných, a výstup zodpovedajúci týmto množinám hodnôt funkcie f reprezentovanej vzorcom Ф (obr. 6.22).

Aby sme pochopili, ako funguje „čierna skrinka“, musíme rozobrať proces vytvárania vzorca z podvzorcov. Dostať sa k „základným“ podvzorcom, t.j. prvkov množiny F sa dostávame k "stavebným blokom", konštrukčným prvkom, z ktorých je zostavená "čierna skrinka", ktorá vypočíta funkciu f. Každá funkcia „základne“ F je vypočítaná zodpovedajúcim „uzlom“, ktorý sa považuje za najmenšiu štruktúrnu jednotku našej „čiernej skrinky“ a jeho vnútorná štruktúra sa už neanalyzuje.

Príklad 6.22. Zvoľme štandardný základ pre množinu F. Potom sa vzorec nad štandardným základom, ktorý predstavuje funkciu ~ (ekvivalencia), zostaví takto:

Výpočet podľa tohto vzorca (a proces jeho konštrukcie z prvkov štandardného základu) možno schematicky znázorniť tak, ako je znázornené na obr. 6.23.

Premenná x 1 (presnejšie hodnota tejto premennej) sa privádza na vstup konštrukčného prvku nazývaného invertor (obr. 6.24, a) a počítajúcu negáciu. Záporné x 1 odstránené z výstupu meniča, t.j. funkcia x 1, sa privádza na jeden zo vstupov spojky (obr. 6.24, b), na druhý vstup ktorého sa privádza premenná x 2. Na výstupe spojky sa objaví funkcia x 1 x 2. Výpočet funkcie x 1 x 2 možno sledovať podobným spôsobom, Obe tieto funkcie sú privádzané na vstupy disjunktora (obr. 6.24, c), z ktorého výstupom je funkcia x 1 x 2 ∨ x 1 x 2 sa odstráni (toto nie je nič iné ako súčet modulo 2: x 1 ⊕ x 2). A nakoniec je táto funkcia privedená na vstup meniča, na výstupe ktorého je už získaná funkcia ~ (ekvivalencia). #

Dostávame sa teda k myšlienke „obvodu“ - matematického modelu kalkulačky booleovskej funkcie, reprezentovanej určitým vzorcom, zostaveným zo štruktúrnych prvkov, z ktorých každý počíta jednu zo „základných“ booleovských funkcií. Vo všeobecnom prípade „obvod“ vypočítava booleovský operátor a každá súradnicová funkcia tohto operátora je odstránená z jedného z výstupov obvodu.

Matematicky je „schéma“ definovaná ako orientovaný graf špeciálneho druhu, v ktorom sú označené vrcholy aj oblúky.

Zavedme si zápis: ak F je nejaká množina booleovských funkcií, potom F (n) označujeme podmnožinu F pozostávajúcu zo všetkých funkcií n premenných (n≥0).

Definícia 6.14. Nech sú pevné množiny: F (boolovské funkcie) a X (boolovské premenné).

Schéma funkčných prvkov na základe F ∪ X (C Φ E), alebo jednoducho kontrahované na základe F ∪ X, tiež schéma (F, X), sa nazýva orientovaný graf s otvoreným koncom (tj sieť), ktorého každý vrchol je označený jedným z prvkov zostavy FU X tak, aby boli splnené tieto požiadavky:

1. každý vstup siete je označený buď nejakou premennou z X, alebo nejakou konštantou z F (0);
2. ak je vrchol v siete označený funkciou f n premenných (tj f ∈ F (n)), potom sa jeho polovičný stupeň vstupu rovná n a na množine oblúkov vstupujúcich do vrcholu v, číslovanie (jedna k jednej) je dané tak, že každý oblúk je očíslovaný od 1 do n.

Ak je naznačený základ, potom povieme jednoducho „schéma“. Okrem toho, ak je množina premenných pevne stanovená „raz a navždy“ a pri zvažovaní rôznych schém meníme iba množinu funkcií F, potom, ako sme to urobili, zavádzaním pojmov vzorca a superpozície nad daný základ, bude hovoriť o SFE na základe F, za predpokladu, že každý raz, čo znamená raz pevnú množinu premenných X, ktorá (ak to nezhorší presnosť) nie je uvedená.

Teraz definujeme pojem indukciou booleovská funkcia vypočítaná vrcholom obvodu .

Definícia 6.15. Nech sa dáva CFE S nad bázou F ∪ X, ktorej množina vrcholov je V.

1. Predpokladá sa, že každý vstup CFE vypočítava booleovskú funkciu, ktorou je označený (t. j. nejaká premenná alebo konštanta).
2. Ak je vrchol v ∈ V označený funkciou f ∈ F (n), oblúk s číslom i (1≤i≤n), ktoré do neho vstupuje, pochádza z vrcholu ui ∈ V, ktorý vypočítava funkciu gi, potom vrchol v vypočíta superpozíciu f (g 1, ..., gn).

Ak teda každý vrchol CFE nad F vypočíta nejakú funkciu, potom je vo všeobecnom prípade podstatné poradie, v ktorom sú vymenované funkcie g 1, ..., gn, dosadené na miesta premenných funkcie f. . Je prirodzené nazývať boolovskú funkciu f v n premenných komutatívnou, ak si zachováva svoju hodnotu pod ľubovoľnou permutáciou svojich premenných. V tomto prípade sa nemusíme obávať číslovania oblúkov vstupujúcich do hornej časti obvodu, označeného takouto funkciou.

Príklad 6.23. Zvážte SPE na obr. 6.25. Vrcholy v 1 a v 2 sú vstupmi SFE. Tieto vrcholy vypočítavajú funkcie x a y. Potom vrchol v 3, ako aj vrchol v 4 podľa definície 6.15 vypočíta funkciu x | y (Schaefferov zdvih) a vrchol v 5 (výstup siete) vypočíta funkciu (x | y) l (x | y), o ktorej je známe, že sa rovná spojke x y.

SPE znázornená na obr. 6.26 má dva výstupy, ktoré počítajú funkcie (x | x) | (y | y) = x ∨ y a (x | y) | (x | y) = x y.

Definícia 6.16. Booleovská funkcia vypočítaná pomocou CFE na základe F ∪ X, je funkcia vypočítaná ľubovoľným z jej výstupov.

CFE teda presne vypočíta, koľko booleovských funkcií, koľko výstupov. SFE na obr. 6.25 vypočíta jednu funkciu a SPE na obr. 6,26 - dva.

Vo všeobecnom prípade, ak (x 1, ..., x n) je množina všetkých premenných, ktoré slúžia ako označenia pre vstupy obvodu S na báze F ∪ X s m výstupmi, CFE S definuje zobrazenie booleovskej kocky B n na booleovskú kocku B m, t.j. booleovský operátor.

Poznámka 6.10. V niektorých prípadoch je funkcia vypočítaná danou SFE definovaná trochu inak, za predpokladu, že ide o funkciu vypočítanú ktorýmkoľvek vrcholom z podmnožiny vybratých vrcholov SFE. Môže ísť najmä o výstupy. V každom prípade sa dohodnime, že z vybraných (v práve naznačenom zmysle) vrcholov obvodu nakreslíme „výstupnú“ šípku. #

Každý obvod brán teda počíta nejaký booleovský operátor, najmä ak je počet výstupov obvodu rovný 1, tak vypočíta nejakú boolovskú funkciu.

Dá sa dokázať aj opak: pre ľubovoľný booleovský operátor možno SFE zostrojiť na základe F, kde F je úplná množina, ktorá počíta daný operátor.

Reprezentujeme funkciu y 1 v Zhegalkinovom základe. Pomocou de Morganových zákonov dostaneme

(pripomeňme, že súčet modulo 2 akéhokoľvek párneho počtu rovnakých členov sa rovná 0).

y1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).

SFE pre booleovský operátor uvedený v tabuľke. 6.9, nad základom Zhegalkin je znázornený na obr. 6.27.

Pri navrhovaní SFE je užitočné mať na pamäti číselný parameter nazývaný jeho zložitosť.

Zložitosť SFE je počet jeho vrcholov, ktoré nie sú vstupmi.

Na obr. 6.27 CFE na báze Zhegalkin má zložitosť 5.

Uvažujme teraz CFE pre toho istého operátora nad štandardným základom.

Podľa tabuľky (pozri tabuľku 6.9) zostrojíme SDNF pre funkciu y 2:

y2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.

Karnotova mapa pre túto funkciu, znázornená na obr. 6.28 ukazuje, že sa nedá minimalizovať (presnejšie vyššie napísané SDNF je minimálna DNF pre túto funkciu). Ale môžete ísť aj inou cestou. Môžeme zvážiť tabuľku. 6.9 ako tabuľku definujúcu čiastočnú booleovskú funkciu y 2 = y 2 (x 1 x 2 x 3 y 1). Minimalizáciou tejto funkcie o

Karnotova mapa * znázornená na obr. 6.29, dostávame

* Na tejto mape sme označili množiny, na ktorých má funkcia hodnotu 0, pričom do príslušných buniek vložíme nuly. Chceme teda ešte raz upozorniť na to, že si netreba zamieňať nuly s pomlčkami: pomlčka v bunke mapy špecifikujúca čiastkovú funkciu znamená, že na tejto množine nie je definovaná hodnota funkcie, t.j. nie je ani 0, ani 1.

y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).

CFE nad štandardným základom pre uvažovaný booleovský operátor je znázornený na obr. 6.30. Zložitosť tohto SFE je 11. Všimnite si, že vrchol počítajúci funkciu y 1 nie je výstup.

Booleovský operátor v tomto príklade vypočíta dvojciferný súčet (modulo 2) troch jednociferných členov. Možno si to predstaviť aj ako jednobitovú binárnu sčítačku – funkčný blok viacbitovej binárnej sčítačky – na dva pojmy. Potom sa funkcia y 1 interpretuje ako "nosný signál" v najvýznamnejšom bite. Na obr. 6.31 je znázornené „spojenie“ troch SFE (ako je znázornené na obr. 6.30), pomocou ktorých sa vypočíta súčet dvoch trojciferných binárnych čísel. Konštanta 0 sa privádza na tretí vstup sčítačky pre najmenej významný bit a „nosný signál“ najvýznamnejšieho bitu je najvýznamnejším bitom súčtu, ktorý vo všeobecnom prípade bude štvormiestne číslo. .

Poznámka 6.11. Ak navrhujeme SFE na štandardnom základe a chceme minimalizovať jeho zložitosť, musíme najskôr skonštruovať zodpovedajúce minimálne DNF. V tomto prípade môžeme vziať do úvahy ešte jedno kritérium, ktorým sa minimalizuje samotná DNF - počet negácií. Spomedzi všetkých minimálnych (v zmysle definície 6.6) DNF by sa mali vybrať tie, v ktorých je počet výskytov premenných pod záporným znamienkom najmenší. Z hľadiska komplexnosti SFE, ktorý bude vybudovaný na základe minimálneho DNF, to znamená, že minimalizuje počet "invertorov" - vrcholov SFE označených negačnou funkciou.

Napríklad pre funkciu danú Karnotovou mapou (obr. 6.32) by ste do jadra pozostávajúceho z jednoduchých implikantov x 1 x 2 x 4 a x 1 x 3 x 4 mali pridať jednoduchý implikant x 2 x 3 x 4 , a nie x 1 x 2 x 3, pretože neobsahuje negatívy.

Funkčné diagramy (FS) sú určené na transformáciu logických informácií. Počiatočné informácie, zakódované vo forme diskrétnych signálov, sa privádzajú na vstupy obvodu `x n... Potom sa tieto informácie spracujú a v diskrétnej forme sa načítajú z výstupov obvodu 'na m(n, m- počet jeho vstupov a výstupov). Zvážte FS, ktoré fungujú v dvojhodnotovej logike a majú jeden výstup ( m= 1). Transformáciu informácií v nich možno špecifikovať ako funkciu algebry logiky pri=f(x n). Namiesto reléových prvkov vo FS sa používajú funkčné prvky (FE), ktoré spravidla realizujú elementárne logické funkcie.

Definícia.Analýza sa nazýva konštrukcia vzorca pre algebru logiky (v prípade potreby jej pravdivostná tabuľka) pre daný FS.

Na zostavenie vzorca podľa danej schémy je potrebné znázorniť vzťah medzi KP vo FS vo forme substitúcií v zodpovedajúcich elementárnych funkciách. Predpokladá sa, že spracovanie informácií sa uskutočňuje v etapách od vstupov po výstupy. V reálnych okruhoch sa využívajú prídavné prvky na zabezpečenie časovej koordinácie chodu všetkých FS.

Analýza FS môže byť vykonaná dvoma spôsobmi – od vstupov k výstupom a od výstupov k vstupom. Uvažujme o prvej metóde s použitím dodatočných označení pre medziobvodové spojenia.

Príklad 1(&, Ú, Ø) sú brané ako FE Analyzujte FE, ktorej fyzikálna štruktúra je znázornená na obr.

Riešenie. Po označení medziľahlých spojení PV, ako je znázornené na obrázku, určujeme signály, ktoré im zodpovedajú, krok za krokom . V tomto prípade prejdeme od vstupov obvodu k jeho výstupu.

Obrázok 1.19

KROK 1. R=`y, Q = `z.

KROK 2. X=X&R= X&'y, P=X& y, W=P&Q= X&r&`z.

KROK 3. Y=X&z=X&'y& z, U=P&z = X&r&z.

KROK 4. Z = YÚ U=X&'y&zÚ X&r&z.

5. KROK F = ZÚ W=X&'y& zÚ X&r&zÚ X&r&`z.

Uvažovaný FS teda implementuje nasledujúci vzorec algebry logiky:

F(X,r,z) = X&'y&zÚ X&r&zÚ X&r&`z.

Nájdený vzorec je SDNF. Vektor jeho pravdivostných hodnôt má tvar (00000111) .

V závislosti od počiatočných údajov možno medzi úlohami syntézy (návrhu) FS rozlíšiť:

1) syntéza obvodov podľa daných vzorcov,

2) syntéza obvodov pre dané funkcie.

Definícia.Syntézou PS podľa uvedeného vzorca sa nazýva konštrukcia štruktúry FS zodpovedajúcej danému vzorcu algebry logiky.

Riešenie takýchto problémov sa vykonáva podľa inverzného algoritmu k metóde analýzy. Ako je uvedené v časti 1.7, štruktúra booleovských vzorcov umožňuje izomorfné mapovanie iba systémov s paralelnými a sekvenčnými spojeniami prvkov. Preto FS, ktorý je izomorfný so zodpovedajúcim vzorcom, by mal obsahovať iba zlúčeniny tohto typu.

Definícia.Syntézou PS pre danú funkciu sa nazýva konštrukcia štruktúrneho diagramu, ktorý implementuje danú funkciu algebry logiky.

Keďže reprezentácia funkcií pomocou vzorcov je nejednoznačná, tento problém má nejedinečné riešenie. Rovnako ako v prípade reléových obvodov sú optimálne FS, pozostávajúce z minimálneho počtu PV a spojení medzi nimi. Takéto FS možno získať pomocou vzorcov s minimálnym počtom premenných.

Pokiaľ ide o PC, osobitne zvážime vzorce, ktoré sú optimálne v triede normálnych foriem (ktoré sa rovnajú zodpovedajúcim minimálnym formám), ako aj absolútne optimálne vzorce získané z minimálnych normálnych foriem ich ďalšou redukciou pomocou zákonov logickej algebry. . Metódy na získanie optimálnych vzorcov sú rovnaké ako v reléových obvodoch. Príklad 1 uvažuje FS, ktorý implementuje funkciu (00000111) . Tento FS nie je optimálny, pretože zodpovedajúci vzorec popisuje SDNF F = x`y z Ú x y zÚ x y`zčo nie je minimálne. Ak ho minimalizujeme, dostaneme MDNF v nasledujúcom tvare: F = x yÚ x z. Zodpovedá FS na obr. 1.20.

Obrázok 1.20

Ak aplikujeme distributívny zákon na MDNF, dostaneme vzorec s ešte menším počtom premenných: f = X(rÚ z). Pre túto funkciu sa zhodoval s MCNF. Tomu zodpovedá absolútne optimálna schéma.

Obrázok 1.21

Je zrejmé, že táto schéma je oveľa jednoduchšia ako pôvodná (obrázok 1.19). Keďže syntéza optimálnej FS je redukovaná na konštrukciu minimálnych vzorcov, sú optimálne schémy aj v iných bázach konštruované podobným spôsobom. Analógy prvého a druhého distribučného zákona algebry logiky pre Schefferovu a webovú formu je možné získať nahradením týchto zákonov:

&(X,r)= Ø ½ ( X,r) = ¯ (Ø X,Ø r);

Ú ( X,r)= ½ (Ø X, Ø r) =Ø ¯ ( X,r).

Príklad 2 Zostrojte FS, ktorý implementuje jednobitovú binárnu sčítačku dvoch čísel pomocou FE zodpovedajúcej základu (Ø, ¯), ako aj základu (¯).

Riešenie. Označme jednobitové binárne čísla dodávané na vstup cez ( NS,pri). Výstupom by mal byť ich súčet v dvojkovej sústave. Ak x = 1, y = 1, potom S = 2 10 = 10 2, preto je na jeho zobrazenie vo všeobecnom prípade potrebné použiť dva binárne znaky a FS musí mať dva výstupy. Označme ich f(najdôležitejšia číslica súčtu) a g(najmenej významný bit). Funkčné pravdivostné tabuľky f (NS,pri),g(NS,pri):

X	r	f(X,r)	g(X,r)

Konštruujeme SVNF funkcií v základe (Ø, ¯). f má jednu jednotku vo vektore pravdy, preto jeho forma pozostáva z jedného prvku: f= ¯ (Ø x, Ø pri). Funkcia g SVNF má tvar: g=د(¯( NS,Ø pri),¯(Ø NS,pri)). Tieto formy sú minimálne. Pri kombinácii vstupov prvkov môže byť funkčný diagram znázornený takto:

Obrázok 1.22

V uvažovanom príklade nie je možné zjednodušiť normálne formy webu pomocou zákonov logickej algebry. V jednofunkčnom základe (¯) FS získame pomocou substitúcie Ø NS= ¯ ( NS,NS). Príslušný obvod je znázornený na obrázku 1.23.

Obrázok 1.23

ÚLOHY

1. Konštruujte pomocou FE (&, Ú, Ø) optimálne v triede normálnych foriem a absolútne optimálne FS, ktoré implementujú nasledujúce funkcie:

a) ( X® r)Å zy b) ( XÅ r)|z,v) xy® yz;G) X|(rÚ z); e) X®( r® z) ;

f) (10011101); g) (01101011); h) (1110101111111110) .

2. Zostrojte pomocou funkcií FE (Ú, Ø) FS 1.a) -g).

3. Zostrojte pomocou FE (&, Ø) FS funkcií 1.a) -g).

4. Zostavte FS, ktorý implementuje jednobitovú binárnu sčítačku (príklad 2) pomocou FE nasledujúceho tvaru:

a) (&, Ú, Ø), b) (Ú, Ø) , treska) ( x | r} .

5. Pomocou FE (&, Ú, Ø) zostrojte FS nasledujúcich zariadení:

a) prevodník s binárnymi vstupmi ( NS,pri) a ukončite f ktorý funguje takto: pri kŕmení x = 0 na výstupe f =pri a pri podávaní x = 1 pri vchode f =`y;

b) selektívne zariadenie s binárnymi vstupmi ( NS,pri) a výstupy f 0 , f 1 , f 2 , f 3, ktorý na vstupe akceptuje kombináciu hodnôt ( x y) ako binárne číslo i, ležiace v rozsahu od 0 do 3. Hodnoty výstupov pre každý i nasledujúci: f i= 1 a všetky ostatné f j= 0, (0 £ j 3 £, j¹ i).

6. Je možné vziať nasledujúce sady funkcií ako základ pre konštrukciu FS:

a) (1001), (10001110),

b) (0101), (1011), (1101),

c) (1010), (01110001)?

Odpoveď zdôvodnite.

7. Uveďte príklady riadiacich funkcií, ktorých FS nemožno zostrojiť len z FE typu (®).

8. Uveďte príklady riadiacich funkcií, ktorých FS nemožno zostrojiť len z FE typu (M,º).

9. Dana FS z FE (&, Ú, Ř).

Obrázok 1.24

Je možné z neho vylúčiť ekvivalentnými prevodmi:

a) všetky prvky (Ø)?

b) všetky prvky (&)?

c) všetky prvky (Ú)?

10. Optimalizujte FS z FE (&, Ú, Ø), znázorneného na obr. 1.25.

Obrázok 1.25

Zostavte FS:

a) optimálne v triede normálnych foriem a

b) absolútne optimálne.