Predstavljanju Booleovih funkcija formulama može se dati sljedeće “inženjersko-konstruktivno” značenje. Promatrat ćemo formulu F(x 1 ,..., x n) nad nekim proizvoljno fiksnim skupom F kao “crnu kutiju”, određeni uređaj na čiji ulaz dolaze svi mogući skupovi varijabilnih vrijednosti, a na na izlazu se pojavljuju vrijednosti funkcije f koje odgovaraju ovim skupovima, predstavljene formulom F (Sl. 6.22).
Da bismo razumjeli kako "crna kutija" radi, moramo analizirati proces konstruiranja formule iz podformula. Doći do "osnovnih" podformula, tj. elemenata skupa F, dolazimo do “cigli”, strukturnih elemenata od kojih se sastavlja “crna kutija”, računajući funkciju f. Svaku “baznu” funkciju F izračunava odgovarajući “čvor”, koji se smatra najmanjom strukturnom jedinicom naše “crne kutije”, a njegova se unutarnja struktura više ne analizira.
Primjer 6.22. Izaberimo standardnu bazu kao skup F. Tada se formula preko standardne baze koja predstavlja funkciju ~ (ekvivalencija) konstruira na sljedeći način:
Proračun pomoću ove formule (i proces njezine konstrukcije od elemenata standardne osnove) može se shematski prikazati kao što je prikazano na Sl. 6.23.
Varijabla x 1 (točnije, vrijednost ove varijable) dovodi se na ulaz strukturnog elementa koji se naziva pretvarač (slika 6.24, a) i izračunava negaciju. Negativni x 1 uklonjen s izlaza pretvarača, tj. funkcija x 1 dovodi se na jedan od ulaza konjunktora (sl. 6.24, b), čiji se drugi ulaz dovodi u varijablu x 2. Na izlazu konjunktora pojavljuje se funkcija x 1 x 2. Na sličan način može se pratiti izračun funkcije x 1 x 2. Obje se ove funkcije dovode na ulaze disjunktora (sl. 6.24, c), s čijeg izlaza funkcija x 1 x 2 ∨ x 1 x 2 se uklanja (ovo nije ništa drugo nego zbroj modulo 2: x 1 ⊕ x 2). I konačno, ova funkcija se dovodi na ulaz pretvarača, na čijem se izlazu već dobiva funkcija ~ (ekvivalencija). #
Tako dolazimo do ideje "sheme" - matematičkog modela kalkulatora Booleove funkcije, predstavljene određenom formulom, sastavljene od strukturnih elemenata, od kojih svaki izračunava jednu od "osnovnih" Booleovih funkcija. U općem slučaju, "krug" izračunava Boolean operator, a svaka koordinatna funkcija ovog operatora uzima se iz jednog od izlaza kruga.
Matematički, "krug" je definiran kao usmjereni graf posebne vrste u kojem su i vrhovi i lukovi opremljeni nekim oznakama.
Uvedimo oznaku: ako je F neki skup Booleovih funkcija, tada s F (n) označavamo podskup F koji se sastoji od svih funkcija od n varijabli (n≥0).
Definicija 6.14. Neka su skupovi F (Booleove funkcije) i X (Booleove varijable) fiksni.
Krug funkcionalnih elemenata iznad baze F ∪ X (S F E), ili jednostavno kontrahirani F ∪ X preko baze, također (F, X)-shema, je nekonturno usmjeren graf (tj. mreža), čiji je svaki vrh označen s jednim elemenata skupa F U X tako da su ispunjeni sljedeći zahtjevi:
- svaki ulaz mreže je označen ili nekom varijablom iz X, ili nekom konstantom iz F (0);
- ako je vrh v mreže označen funkcijom f od n varijabli (tj. f ∈ F (n)), tada je njegov polustupanj jednak n, a na skupu lukova koji ulaze u vrh v, a (jedan -na-jedan) numeriranje je dano tako da svaki luk dobije broj od 1 do n.
Ako se podrazumijeva osnova, onda ćemo jednostavno reći "shema". Osim toga, ako je skup varijabli fiksiran “jednom zauvijek” i kada razmatramo različite sheme mijenjamo samo skup funkcija F, tada ćemo, kao što smo učinili kada smo uveli koncepte formule i superpozicije nad danom bazom, govorimo o SFE preko baze F, stavljajući svaki puta, što implicira jednom fiksni skup varijabli X, koji (ako ne šteti točnosti) nije spomenut.
Definirajmo sada pojam indukcijom Booleova funkcija izračunata vrhom kruga .
Definicija 6.15. Neka se da SFE S nad bazom F ∪ X čiji je skup vrhova V.
- Pretpostavlja se da svaki ulaz SFE izračunava Booleovu funkciju kojom je označen (tj. neku varijablu ili konstantu).
- Ako je vrh v ∈ V označen funkcijom f ∈ F (n), luk koji ulazi u njega s brojem i (1≤i≤n) dolazi iz vrha u i ∈ V, koji vrednuje funkciju g i , tada vrh v procjenjuje superpoziciju f(g 1 , ... ,g n).
Dakle, ako svaki vrh SFE nad F izračunava određenu funkciju, tada je redoslijed kojim su funkcije g 1 , ... , g n navedene i zamijenjene varijablama funkcije f, u općem slučaju, značajan. Prirodno je Booleovu funkciju f od n varijabli nazvati komutativnom ako zadržava svoju vrijednost pri bilo kojoj permutaciji svojih varijabli. U ovom slučaju ne moramo brinuti o numeriranju lukova koji ulaze u vrh dijagrama označen takvom funkcijom.
Primjer 6.23. Razmotrimo SFE na sl. 6.25. Vrhovi v 1 i v 2 su ulazi SFE-a. Ovi vrhovi izračunavaju funkcije x odnosno y. Tada vrh v 3, kao i vrh v 4, prema definiciji 6.15, izračunava funkciju x|y (Schaefferov hod), a vrh v 5 (mrežni izlaz) izračunava funkciju (x|y)l(x|y) , koja je, kao što je poznato, jednaka konjunkciji x · y.
SFE prikazan na sl. 6.26, ima dva izlaza koji izračunavaju funkcije (x|x)|(y|y) =x ∨ y i (x|y)|(x|y) =x·y.
Definicija 6.16. Booleova funkcija koju izračunava SFE nad bazom F ∪ X, je funkcija izračunata bilo kojim od svojih izlaza.
Dakle, SFE izračunava točno onoliko Booleovih funkcija koliko ima izlaza. SFE na sl. 6.25 izračunava jednu funkciju, a SFE na sl. 6.26 - dva.
Općenito, ako je (x 1 ,..., x n ) skup svih varijabli koje služe kao oznake ulaza kruga S preko baze F ∪ X, s m izlaza, SFE S definira prikaz Booleove kocke B n Booleovoj kocki B m, tj. Booleov operator.
Napomena 6.10. U nekim slučajevima, funkcija izračunata danim SFE definirana je nešto drugačije, uz pretpostavku da je to funkcija izračunata bilo kojim vrhom iz podskupa odabranih vrhova SFE. Konkretno, to mogu biti izlazi. U svakom slučaju, dogovorit ćemo se da iz odabranih (u upravo naznačenom smislu) vrhova dijagrama povučemo “izlaznu” strelicu. #
Dakle, svaki sklop funkcionalnih elemenata izračunava neki Booleov operator, posebice, ako je broj izlaza sklopa 1, tada izračunava neku Booleovu funkciju.
Može se dokazati i suprotno: za bilo koji Booleov operator, SFE se može konstruirati preko baze F, gdje je F potpuni skup koji vrednuje ovaj operator.
Zamislimo funkciju y 1 u Zhegalkinovoj bazi. Koristeći De Morganove zakone, dobivamo
(podsjetimo se da je zbroj modulo 2 bilo kojeg parnog broja jednakih članova 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 za Booleov operator naveden u tablici. 6.9, iznad Zhegalkinove baze prikazana je na sl. 6.27.
Prilikom dizajniranja SPV-a korisno je imati na umu numerički parametar koji se naziva njegova složenost.
Složenost SFE je broj njegovih vrhova koji nisu ulazi.
Prikazano na sl. 6.27 SFE preko Zhegalkinove baze ima složenost 5.
Razmotrimo sada SFE za istog operatora na standardnoj osnovi.
Pomoću tablice (vidi tablicu 6.9) konstruiramo SDNF za funkciju 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 .
Karnaughova karta za ovu funkciju, prikazana na sl. 6.28 pokazuje da se ne može minimizirati (točnije, gore napisani SDNF je minimalni DNF za ovu funkciju). Ali možete krenuti drugačijim putem. Možemo razmotriti tablicu. 6.9 kao tablica koja definira djelomičnu Booleovu funkciju y 2 = y 2 (x 1 x 2 x 3 y 1). Minimiziranjem ove funkcije za
Carnotova karta* prikazana na sl. 6.29, dobivamo
* Na ovoj karti označili smo skupove na kojima funkcija ima vrijednost 0, stavljajući nule u odgovarajuće ćelije. Stoga još jednom želimo skrenuti pozornost na činjenicu da se nule ne smiju brkati s crticama: crtica u ćeliji mape koja definira parcijalnu funkciju znači da vrijednost funkcije nije definirana na ovom skupu, tj. nije ni 0 ni 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
SFE preko standardne baze za Boolean operator koji se razmatra prikazan je na slici. 6.30. Složenost ovog SFE-a je 11. Imajte na umu da vrh koji procjenjuje funkciju y 1 nije izlaz.
Booleov operator o kojem se govori u ovom primjeru izračunava dvoznamenkasti zbroj (modulo 2) triju jednoznamenkastih izraza. Također se može smatrati jednobitnim binarnim zbrajačem - funkcionalnim blokom višebitnog binarnog zbrajala - za dva člana. Zatim se funkcija y 1 tumači kao "prijenosni signal" do bita najveće važnosti. Na sl. Slika 6.31 prikazuje "vezu" tri SFE-a (poput onih prikazanih na slici 6.30), uz pomoć kojih se izračunava zbroj dva trobitna binarna broja. Treći ulaz zbrajala za bit nižeg reda ima konstantu 0, a "signal prijenosa" bita višeg reda je najznačajniji bit zbroja, koji će u općenitom slučaju biti četiri- broj bita.
Napomena 6.11. Ako dizajniramo SFE preko standardne baze i želimo minimizirati njegovu složenost, tada prvo trebamo konstruirati odgovarajući minimalni DNF. U ovom slučaju možemo uzeti u obzir još jedan kriterij po kojem se sam DNF minimizira - broj negacija. Među svim minimalnim (u smislu definicije 6.6) DNF-ovima treba odabrati one u kojima je broj pojavljivanja varijabli pod predznakom negacije najmanji. Sa stajališta složenosti SFE-a, koji će se graditi korištenjem minimalnog DNF-a, to znači da minimizira broj "invertera" - vrhova SFE-a, označenih funkcijom negacije.
Na primjer, za funkciju zadanu Carnaughovom mapom (sl. 6.32), jezgri koja se sastoji od prostih implikanti x 1 x 2 x 4 i x 1 x 3 x 4, treba dodati prostu implikantu x 2 x 3 x 4 nego x 1 x 2 x 3 budući da ne sadrži negacije.
31. Sheme funkcionalnih elemenata, pravila konstrukcije i rada, metoda sinteze SFE, na temelju SDNF i SKNF.
DefinicijaDefinicija. Funkcionalni element je matematički model elementarnog diskretnog pretvarača, koji prema određenom zakonu pretvara signale primljene na njegov ulaz u signal na izlazu iz pretvarača. Od funkcionalnih elemenata, uz pomoć određenih pravila, moguće je graditi složenije modele po strukturi i funkcioniranju - dijagrame od funkcionalnih elemenata. U ovim modelima ulazni i izlazni signali kodirani su simbolima 0 i 1.
Pravila gradnje. Da bi se dobili složeni SFE-ovi od jednostavnijih, na njih se uzastopno primjenjuju operacije razdvajanja ulaza ili izlaza sklopa, pričvršćivanja funkcionalnog elementa na krug i povezivanja funkcionalnog elementa s ulazom ili izlazom sklopa. Ove operacije nalikuju pravilima za dobivanje složene formule od jednostavnijih pomoću superpozicije.
Sinteza SFE. Jer disjunkcija, konjunkcija i negacija čine cjelovit sustav u učionici R 2 , tada bilo koja Booleova funkcija od n argumenti se mogu implementirati sklopom funkcionalnih elemenata - disjunktori, konjunktori i invertori - s n ulazi i jedan izlaz. Da biste to učinili, možete, na primjer, izraziti danu Booleovu funkciju kroz SDNF ili SCNF, a zatim "sintetizirati" rezultirajuću formulu u obliku kruga funkcionalnih elemenata, uzastopno primjenjujući gore navedene operacije cijepanja, zbrajanja i povezivanja.
32. Metoda za sintezu sfe, temeljena na kompaktnoj implementaciji svih konjunkcija pomoću univerzalne višeportne mreže, složenost rezultirajućih sklopova.
Definicija. Funkcija od n argumenata naziva se Booleova funkcija (ili funkcija logičke algebre) ako dodjeljuje broj svakom skupu.
Za specificiranje Booleovih funkcija koristit ćemo se tablicama, vektorima, formulama i grafikonima. Prihvatimo sljedeću oznaku: – je skup svih skupova, gdje je.
Definicija. Funkcionalni element je matematički model elementarnog diskretnog pretvarača, koji prema određenom zakonu pretvara signale primljene na njegov ulaz u signal na izlazu iz pretvarača. Od funkcionalnih elemenata, uz pomoć određenih pravila, moguće je graditi složenije modele po strukturi i funkcioniranju - dijagrame od funkcionalnih elemenata. U ovim modelima ulazni i izlazni signali kodirani su simbolima 0 i 1.
Metoda za sintetiziranje SFE-ova temeljena na kompaktnoj implementaciji svih konjunkcija korištenjem univerzalne mreže s više priključaka. Ova se metoda također temelji na predstavljanju funkcije u obliku SDNF-a, ali vam omogućuje izgradnju manje složenih sklopova zbog kompaktnije implementacije konjunkcija. Proširenje funkcije u SDNF može sadržavati konjunkcije koje imaju zajedničke faktore. Ako su dvije takve konjunkcije implementirane jednim podsklopom u bloku, tada će to zahtijevati barem jedan konektor manje nego što je bilo potrebno prije, uz neovisnu implementaciju svih konjunkcija prvom metodom sinteze. Kompaktna izvedba svih mogućih spojnica dužine n može se postići uporabom induktivno konstruirane univerzalne višeportne mreže koja ima n ulazi i 2 n izlazi gdje n = 1,2,3,... Prednosti metode su posebno uočljive kada jedan sklop treba implementirati sustav od nekoliko Booleovih funkcija. U ovom bi slučaju bilo moguće razdvojiti i zatim provući kroz disjunktore one izlaze univerzalne višeportne mreže koji odgovaraju konjunkcijama uključenim u SDNF funkcija danog sustava. To bi omogućilo korištenje manje konjunktora nego da je svaka funkcija danog sustava neovisno implementirana vlastitim podsklopom.
Složenost takve višeportne mreže jednaka je L() =.
Ako krug funkcionalnih elemenata Σ sadrži točno r funkcionalnih elemenata, onda kažu da ima složenost r i zapiši to kao jednakost L(Σ) = r.
| " |
Predavanje 2. Strujni krugovi funkcionalnih elemenata
(SFE) u nekoj osnovi. Složenost i dubina
shema. Primjeri. Metoda sinteze SFE pomoću DNP.
Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna
Predavanja iz predmeta “Diskretna matematika 2”.
1. godina grupa 141,
Fakultet računalne matematike i matematike Moskovskog državnog sveučilišta nazvan po M.V. Lomonosov
Predavanja na web stranici http://mk.cs.msu.su
SFE Primjeri Sinteza SFE korištenjem DNF
Sheme funkcionalnih elemenata
Definirajmo sklopove funkcionalnih elemenata u određenoj bazi.
Neka nam je dan određeni skup Booleovih funkcija B = (g1 (x1,..., xn1),..., gs (x1,..., xns)) P2, gdje je n1,..., ns 0 .
Nazovimo ovaj skup bazom.
Imajte na umu da ovaj koncept baze nije ni na koji način povezan s konceptom baze P2, koji je razmatran u algebri logike.
U pravilu ćemo razmatrati standardnu bazu B0 = (x&y, x y, x ).
SFE Primjeri Sinteza SFE pomoću DNF-a Definicija kruga funkcionalnih elemenata Krug funkcionalnih elemenata (SFE) u bazi B0 = (x&y, x y, x) je
1) usmjereni aciklički graf G = (V, E), čiji svaki vrh v V ima polustupanj d (v) koji ne prelazi dva (d (v) 2);
2) svaki vrh v s polustupnjem jednakim 0 (d (v) = 0) naziva se ulaz (ili ulaz sklopa) i pridružuje mu se neka Booleova varijabla xi;
3) svi ostali vrhovi (osim ulaza) nazivaju se unutarnjim vrhovima sklopa;
4) svakom vrhu v s polustupnjem jednakim 1 (d (v) = 1) pridružuje se (funkcionalni) element negacije; svi takvi vrhovi nazivaju se inverteri;
5) svakom vrhu v s polustupnjem jednakim 2 (d (v) = 2) dodijeljen je ili (funkcionalni) element konjunkcije & ili (funkcionalni) element disjunkcije; svi vrhovi kojima su pridruženi elementi konjunkcije nazivaju se konjunktori, svi vrhovi kojima su pridruženi elementi disjunkcije nazivaju se disjunktori;
SFE Primjeri Sinteza SFE korištenjem DNF Određivanje sklopa iz funkcionalnih elemenata (nastavak)
6) dodatno, nekim od vrhova pridružene su po paru različite izlazne varijable y1,..., ym.
Ako je zadan SFE S, čijim ulazima su dodijeljene samo varijable x1,..., xn, a s izlaznim varijablama y1,..., ym, tada ćemo taj SFE označiti sa S(x1,..., xn; y1,..., ym).
SFE Primjeri Sinteza SFE korištenjem DNF
– – –
Određivanje dubine vrha SFE Indukcijom određujemo dubinu d(v) vrha v u SFE S.
1. Osnova indukcije. Svaki ulaz v SFE S ima dubinu jednaku 0: d(v) = 0.
– – –
SFE i njihove karakteristike Krugovi funkcionalnih elemenata su računski model.
SFE karakteristike koje smo predstavili pokazuju različite aspekte računalne učinkovitosti.
Složenost SFE odgovara vremenu sekvencijalnog izračuna.
Dubina SFE odgovara vremenu paralelnog izračuna.
Maksimalni broj vrhova s istom dubinom u SFE odgovara broju procesora u paralelnom računanju.
SFE primjeri Sinteza SFE korištenjem DNF Primjer: zbroj tri bita Rješenje. Slično primjeru 6, napišimo tablicu za zbroj tri bita x, y i z. Taj zbroj također može biti broj s dvije binarne znamenke, pa uvodimo dvije Booleove varijable
u0, u1, tako da je x + y + z = 2u1 + u0:
– – –
Literatura za predavanje 4
1. Yablonsky S.V. Uvod u diskretnu matematiku. M.:
Viša škola, 2001. V. dio, gl. 2, str. 336-355 (prikaz, ostalo).
2. Gavrilov G.P., Sapozhenko A.A. Zadaci i vježbe iz diskretne matematike. M.: Fizmatlit, 2004. Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
SFE Primjeri Sinteza SFE korištenjem DNF
Predstavljanju Booleovih funkcija formulama može se dati sljedeće “inženjersko-konstruktivno” značenje. Formulu nad nekim proizvoljno fiksnim skupom smatrat ćemo "crnom kutijom", određenim uređajem, na čiji ulaz dolaze svi mogući skupovi varijabilnih vrijednosti, a na izlazu vrijednosti funkcije predstavljene formulom koji odgovaraju ovim skupovima (slika 6.22).
Da bismo razumjeli kako "crna kutija" radi, moramo analizirati proces konstruiranja formule iz podformula. Doći do "osnovnih" podformula, tj. elemenata skupa, dolazimo do “cigli”, strukturnih elemenata od kojih je sastavljena “crna kutija”, izračunavanje funkcije . Svaku “osnovnu” funkciju izračunava odgovarajući “čvor”, koji se smatra najmanjom strukturnom jedinicom naše “crne kutije”, a njegova se unutarnja struktura više ne analizira.
Primjer 6.22. Izaberimo standardnu osnovu kao skup. Tada se formula preko standardne baze koja predstavlja funkciju (ekvivalencija) konstruira na sljedeći način:
Proračun pomoću ove formule (i proces njezine konstrukcije od elemenata standardne osnove) može se shematski prikazati kao što je prikazano na Sl. 6.23.
Varijabla (točnije, vrijednost ove varijable) dovodi se na ulaz strukturnog elementa koji se naziva pretvarač (slika 6.24, a) i izračunava negaciju. Minus uklonjen s izlaza pretvarača, tj. funkcija , dostavlja se na jedan od ulaza konjunktora (sl. 6.24.5), čiji se drugi ulaz dovodi s varijablom. Funkcija se pojavljuje na izlazu konjunktora. Izračun funkcije može se pratiti na sličan način. Obje ove funkcije dovode se na ulaze disjunktora (sl. 6.24, c), s čijeg se izlaza funkcija uklanja (ovo nije ništa više od sume modulo 2:). I konačno, ova funkcija se dovodi na ulaz pretvarača, na čijem je izlazu funkcija (ekvivalencija) već dobivena.
Tako dolazimo do ideje "sheme" - matematičkog modela kalkulatora Booleove funkcije, predstavljene određenom formulom, sastavljene od strukturnih elemenata, od kojih svaki izračunava jednu od "osnovnih" Booleovih funkcija. U općem slučaju, "krug" izračunava Boolean operator, a svaka koordinatna funkcija ovog operatora uzima se iz jednog od izlaza kruga.
Matematički, "krug" je definiran kao usmjereni graf posebne vrste u kojem su i vrhovi i lukovi opremljeni nekim oznakama.
Uvedimo oznaku: ako je neki skup Booleovih funkcija, tada sa označavamo podskup koji se sastoji od svih funkcija varijabli .
Definicija 6.14. Neka su skupovi (Booleovih funkcija) i (Booleovih varijabli) fiksni.
Krug funkcionalnih elemenata preko baze (SFE), ili jednostavno krug preko baze, također (F,X)-shema, je nekonturno usmjeren graf (tj. mreža), čiji je svaki vrh označen s jednim od elemenata skupa tako da su zadovoljeni: zahtjevi:
1) svaki ulaz mreže označen je ili nekom varijablom iz , ili nekom konstantom iz ;
2) ako je vrh mreže v označen funkcijom varijabli (tj.), tada je njegov polustupanj jednak , a na skupu lukova koji ulaze u vrh, dano je numeriranje (jedan na jedan). , u kojem svaki luk dobiva broj od 1 do .
Kod prikaza sklopova ulazi su označeni kružićima, a vrhovi koji nisu ulazi označeni su trokutićima unutar kojih je ispisana oznaka funkcije koja označava taj vrh. Izlazi su označeni strelicama "izlaz". Na sl. Slika 6.25 prikazuje SFE preko baze.
Ako se podrazumijeva osnova, onda ćemo jednostavno reći "shema". Osim toga, ako je skup varijabli fiksiran "jednom zauvijek" i pri razmatranju raznih shema mijenjamo samo skup funkcija, tada ćemo, kao što smo učinili prilikom uvođenja pojmova formule i superpozicije nad danom bazom, govoriti o SFE preko baze, uz pretpostavku svakog vremena, što implicira jednom fiksni skup varijabli, koji (ako ne šteti preciznosti) nije spomenut.
Definirajmo sada indukcijom koncept Booleove funkcije izračunate vrhom kruga.
Definicija 6.15. Neka je SFE zadan preko baze čiji je skup vrhova .
1. Pretpostavlja se da svaki ulaz SFE-a izračunava Booleovu funkciju kojom je označen (tj. neku varijablu ili konstantu).
2. Ako je vrh označen funkcijom, luk koji u njega ulazi s brojem dolazi iz vrha koji izračunava funkciju, tada vrh v izračunava superpoziciju.
Prema tome, ako svaki vrh SFE izračunava određenu funkciju, tada je redoslijed kojim su funkcije navedene, zamijenjene umjesto varijabli funkcije, u općem slučaju značajan. Prirodno je nazvati Booleovu funkciju varijabli komutativnom ako zadržava svoju vrijednost pri bilo kojoj permutaciji svojih varijabli. U ovom slučaju ne moramo brinuti o numeriranju lukova koji ulaze u vrh dijagrama označen takvom funkcijom.
Primjer 6.23. Razmotrimo SFE na sl. 6.25. Vrhovi i su ulazi SFE. Ovi vrhovi izračunavaju funkcije i respektivno. Tada vrh , kao i vrh , prema definiciji 6.15, izračunava funkciju (Schaefferov potez), a vrh (mrežni izlaz) izračunava funkciju , koja je, kao što je poznato, jednaka konjunkciji .
SFE prikazan na sl. 6.26, ima dva izlaza, računske funkcije i.
Definicija 6.16. Booleova funkcija koju izračunava SFE preko baze je funkcija izračunata bilo kojim od njegovih izlaza.
Dakle, SFE izračunava točno onoliko Booleovih funkcija koliko ima izlaza. SFE na sl. 6.25 izračunava jednu funkciju, a SFE na sl. 6.26 - dva.
U općem slučaju, ako je skup svih varijabli koje služe kao oznake ulaza kruga preko baze koja ima izlaze, SFE određuje preslikavanje Booleove kocke u Booleovu kocku, tj. Booleov operator.
Napomena 6.10. U nekim slučajevima, funkcija izračunata danim SFE definirana je nešto drugačije, uz pretpostavku da je to funkcija izračunata bilo kojim vrhom iz podskupa odabranih vrhova SFE. Konkretno, to mogu biti izlazi. U svakom slučaju, dogovorit ćemo se da iz odabranih (u upravo naznačenom smislu) vrhova dijagrama povučemo “izlaznu” strelicu.
Dakle, svaki sklop funkcionalnih elemenata izračunava neki Booleov operator, posebice, ako je broj izlaza sklopa 1, tada izračunava neku Booleovu funkciju.
Može se dokazati i suprotno: za bilo koji Booleov operator, SFE se može konstruirati preko baze , gdje je potpuni skup koji procjenjuje ovaj operator.
Primjer 6.24. Definirajmo Boolean operator s tablicom koja se preslikava na (tablica 6.9).
Iz tablice je to lako vidjeti (funkcija nije ništa više od većinske funkcije varijabli, a minimalni DNF za nju je napisan gore, vidi primjer 6.12). Zamislimo funkciju u Zhegalkinovoj bazi. Koristeći De Morganove zakone, dobivamo
S obzirom na to, imat ćemo
(podsjetimo se da je zbroj modulo 2 bilo kojeg parnog broja jednakih članova 0). Tako,
SFE za Booleov operator naveden u tablici. 6.9, iznad Zhegalkinove baze prikazana je na sl. 6.27.
Prilikom dizajniranja SPV-a korisno je imati na umu numerički parametar koji se naziva njegova složenost.
Složenost SFE-a je broj njegovih vrhova koji nisu ulazi.
Prikazano na sl. 6.27 SFE preko Zhegalkinove baze ima složenost 5.
Razmotrimo sada SFE za istog operatora na standardnoj osnovi. Pomoću tablice (vidi tablicu 6.9) gradimo SDNF za funkciju
Karnaughova karta za ovu funkciju, prikazana na sl. 6.28 pokazuje da se ne može minimizirati (točnije, gore napisani SDNF je minimalni DNF za ovu funkciju).
Ali možete krenuti drugačijim putem. Možemo razmotriti tablicu. 6.9 kao tablica koja definira djelomičnu Booleovu funkciju. Minimiziranjem ove funkcije pomoću Karnaughove karte* prikazane na Sl. 6.29, dobivamo
*Na ovoj mapi smo eksplicitno naznačili skupove na kojima funkcija ima vrijednost 0 stavljanjem nula u odgovarajuće ćelije. Stoga još jednom želimo skrenuti pozornost na činjenicu da se nule ne smiju brkati s crticama: crtica u ćeliji mape koja definira parcijalnu funkciju znači da vrijednost funkcije nije definirana na ovom skupu, tj. nije ni 0 ni 1.
SFE preko standardne baze za Boolean operator koji se razmatra prikazan je na slici. 6.30. Složenost ovog SFE-a je 11. Imajte na umu da vrh koji izračunava funkciju nije izlaz.
Booleov operator o kojem se govori u ovom primjeru izračunava dvoznamenkasti zbroj (modulo 2) triju jednoznamenkastih izraza. Također se može smatrati jednobitnim binarnim zbrajačem - funkcionalnim blokom višebitnog binarnog zbrajala - za dva člana. Zatim se funkcija r/1 tumači kao "prijenosni signal" do bita najveće važnosti. Na sl. Slika 6.31 prikazuje "vezu" tri SFE-a (poput onih prikazanih na slici 6.30), uz pomoć kojih se izračunava zbroj dva trobitna binarna broja. Treći ulaz zbrajala za bit nižeg reda ima konstantu 0, a "signal prijenosa" bita višeg reda je najznačajniji bit zbroja, koji će u općenitom slučaju biti četiri- broj bita.
Veličina: px
Počnite prikazivati sa stranice:
Prijepis
1 Predavanje 2. Sklopovi funkcionalnih elemenata (SFE) u određenoj bazi. Složenost i dubina sheme. Primjeri. Metoda sinteze SFE pomoću DNP. Predavač - izvanredni profesor Svetlana Nikolaevna Selezneva Predavanja iz diskretne matematike 2. 1. godina, grupa 141, Fakultet računalne matematike Moskovskog državnog sveučilišta nazvanog po M.V. Lomonosov predavanja na web stranici
2 Sklopovi iz funkcionalnih elemenata Definirajmo sklopove iz funkcionalnih elemenata u određenoj bazi. Neka nam je zadan određeni skup Booleovih funkcija B = (g 1 (x 1,..., x n1),..., g s (x 1,..., x ns)) P 2, gdje je n 1 ,.. ., n s 0. Nazovimo ovaj skup bazom. Imajte na umu da ovaj koncept baze nije ni na koji način povezan s konceptom baze P 2, koji je razmatran u algebri logike. U pravilu ćemo razmatrati standardnu bazu B 0 = (x&y, x y, x).
3 Definicija kruga funkcionalnih elemenata Krug funkcionalnih elemenata (SFE) u bazi B 0 = (x&y, x y, x) je 1) usmjereni aciklički graf G = (V, E), čiji je svaki vrh v V ima pola stupnja d (v), koji ne prelazi dva (d (v) 2); 2) svaki vrh v s polustupnjem jednakim 0 (d (v) = 0) naziva se ulaz (ili ulaz sklopa) i pridružuje mu se neka Booleova varijabla x i ; 3) svi ostali vrhovi (osim ulaza) nazivaju se unutarnjim vrhovima sklopa;
4 Definicija kruga funkcionalnih elemenata (nastavak) 4) svakom vrhu v s polustupnjem jednakim 1 (d (v) = 1) pridružuje se (funkcionalni) element negacije; svi takvi vrhovi nazivaju se inverteri; 5) svakom vrhu v s polustupnjem jednakim 2 (d (v) = 2) dodijeljen je ili (funkcionalni) element konjunkcije & ili (funkcionalni) element disjunkcije; svi vrhovi kojima su pridruženi elementi konjunkcije nazivaju se konjunktori, svi vrhovi kojima su pridruženi elementi disjunkcije nazivaju se disjunktori;
5 Definicija sklopa iz funkcionalnih elemenata (nastavak) 6) dodatno, nekim od vrhova pridružuju se po paru različite izlazne varijable y 1,..., y m. Ako je zadan SFE S, čijim ulazima su dodijeljene samo varijable x 1,..., x n, a s izlaznim varijablama y 1,..., y m, tada ćemo taj SFE označiti sa S(x 1,. .., x n ; y 1,..., y m).
6 Primjer SFE Primjer 1. SFE S(x 1, x 2, x 3; y 1, y 2, y 3):
7 Primjer SFE Primjer 1. U pravilu, SFE su prikazani na sljedeći način S(x 1, x 2, x 3; y 1, y 2, y 3):
8 Određivanje složenosti SFE-a Složenost L(S) SFE-a S je broj unutarnjih vrhova ovog SFE-a, tj. broj funkcionalnih elemenata u SFE S.
9 Složenost SFE Primjer 2. Složenost SFE S:
10 Određivanje dubine vrha SFE S Indukcijom određujemo dubinu d(v) vrha v u SFE S. 1. Indukcijska baza. Svaki ulaz v SFE S ima dubinu jednaku 0: d(v) = Induktivni spoj. 1) Ako luk iz vrha v 1 vodi do invertora v SFE S, tada je d(v) = d(v 1)) Ako luk iz vrha v 1 i v 2 vodi do konjunktora ili disjunktora v SFE S, tada je d(v ) = max(d(v 1), d(v 2)) + 1. Dubina D(S) SFE S je maksimum dubina njegovih vrhova.
11 Dubina SFE Primjer 3. Dubina vrhova SFE S i dubina SFE S:
12 Određivanje funkcioniranja SFE-a Na svakom vrhu SFE-a implementirana je (ili izračunata) određena Booleova funkcija. Indukcijom definiramo Booleovu funkciju koja je implementirana u vrhu v SFE S. 1) Ako je v ulazni vrh i varijabla x i mu je dodijeljena, tada je u vrhu v implementirana funkcija f v = x i. 2) Ako luk vodi do invertora v iz vrha v 1, au vrhu v 1 je implementirana funkcija f v1, tada je u vrhu v implementirana funkcija f v = f v1. 3) Ako lukovi iz vrhova v 1 i v 2 vode do konjunktora (ili disjunktora) v, a funkcije f v1 i f v2 implementirane su u vrhove v 1 odnosno v 2, tada je u vrhu v funkcija f v = f v1 &f v2 (prema tome f v = f v1 f v2).
13 Djelovanje SFE-a Vjeruje se da SFE S(x 1,..., x n; y 1,..., y m) implementira sustav Booleovih funkcija F S = (f 1,..., f m), implementiran u svoje izlazne vrhove y 1,..., y m.
14 Funkcioniranje SFE Primjer 4. Booleove funkcije implementirane na vrhovima SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3 ).
15 Linearni program Linearni program s ulazima x 1,..., x n preko baze B 0 = (x&y, x y, x) je niz z 1, z 2,..., z t, u kojem za svaki broj j , j = 1,..., t, vrijedi da je 1) ili z j = x i ; 2) ili z j = z k za 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 i linearni programi Jasno je da se proračun u SFE može prepisati u obliku linearnog programa. Obrnuto, svaki linearni program može se predstaviti kao neki SFE.
17 SFE i linearni programi Primjer 5. SFE S odgovara linearnom programu z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.
18 SFE i njihove karakteristike Krugovi funkcionalnih elemenata su računski model. SFE karakteristike koje smo predstavili pokazuju različite aspekte računalne učinkovitosti. Složenost SFE odgovara vremenu sekvencijalnog izračuna. Dubina SFE odgovara vremenu paralelnog izračuna. Maksimalni broj vrhova s istom dubinom u SFE odgovara broju procesora u paralelnom računanju.
19 Primjer: zbroj dva bita Primjer 6. Konstruirajte SFE u standardnoj bazi koja realizira (izračunava) zbroj dva bita x i y. Riješenje. Napišimo tablicu zbroja dva bita x i y. Taj zbroj može biti broj s dvije binarne znamenke, pa uvodimo dvije Booleove varijable z 0, z 1, tako da je x + y = 2z 1 + z 0: x y z 1 z
20 Primjer: zbroj dva bita Rješenje (nastavak). Tada je z 0 = x y, z 1 = xy. Uzimajući u obzir da je x y = (x y) (x y), dobivamo CFE: Jasno je da je L(S 1) = 3, a D(S 1) = 3.
21 SFE u proizvoljnoj bazi Pojam SFE u proizvoljnoj bazi B P 2 uvodi se na sličan način.
22 Primjer: zbroj tri bita Primjer 7. Konstruirajte SFE u bazi P2 2 (tj. od svih Booleovih funkcija koje ovise o dvije varijable), realizirajući (izračunavajući) zbroj tri bita x, y i z.
23 Primjer: zbroj tri bita Rješenje. Slično primjeru 6, napišimo tablicu za zbroj tri bita x, y i z. Taj zbroj također može biti broj s dvije binarne znamenke, pa uvodimo dvije Booleove varijable u 0, u 1, tako da je x + y + z = 2u 1 + u 0: x y z u 1 u
24 Primjer: zbroj tri bita Rješenje (nastavak). Tada je u 0 = x y z, u 1 = xy xz yz. Uzimajući u obzir da je xy xz yz = xy z(x y), dobivamo CFE: Vidimo da je L(S) = 5, a D(S) = 3.
25 Implementacija Booleove funkcije SFE-a Je li moguće implementirati proizvoljnu Booleovu funkciju (ili sustav Booleovih funkcija) SFE-a u bazi B 0 = (x&y, x y, x)? Limenka. Kako se to može opravdati? Na primjer, ovako. Jer (x&y, x y, x) kompletan sustav u P 2, proizvoljna Booleova funkcija f može se prikazati formulom samo pomoću konjunkcije, disjunkcije i negacije. Na primjer, u obliku savršenog DNF-a, ako je f 0, i u obliku x& x, ako je f = 0. I onda, koristeći ovaj DNF (formulu), konstruirajte odgovarajući SFE. Ova metoda konstruiranja SFE za Booleove funkcije naziva se metoda DNF sinteze.
26 Sinteza SFE pomoću DNF-a A koja će se složenost SFE S dobiti pomoću DNF-a za Booleovu funkciju f (x 1,..., x n), ovisno o n varijabli? Savršen DNF za funkciju f neće sadržavati više od 2 n elementarnih konjunkcija. Svaka elementarna konjunkcija je konjunkcija n varijabli ili njihovih negacija.
27 Sinteza SFE pomoću DNF-a Prema tome, sklop će imati: n pretvarača za implementaciju svih negacija varijabli x 1,..., x n; pomoću (n 1) konjunktora za implementaciju svake od najviše 2 n elementarnih konjunkcija u savršenom DNF; najviše (2 n 1) disjunktor za provedbu disjunkcije elementarnih DNF konjunkcija. Dobivamo da je L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Složenost Booleove funkcije Složenost L(f) Booleove funkcije f (x 1,..., x n) u klasi SFE-ova je minimalna složenost među svim SFE-ovima koji implementiraju funkciju f. Dakle, dokazali smo teorem: Teorem 1. Za proizvoljnu funkciju f (x 1,..., x n) P 2 vrijedi L(f) n 2 n + n.
29 Zadaci za samostalno rješavanje 1. Za Booleovu funkciju f (x 1, x 2, x 3) = () konstruirajte SFE u standardnoj bazi složenosti. Za Booleovu funkciju f (x 1, x 2, x 3) = ( ) konstruirajte SFE u standardnoj bazi složenosti. Za Booleovu funkciju f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, konstruirajte SFE u standardnoj dubinskoj bazi. Dokažite da u standardnoj baza L(x y) = 4.
30 Literatura za predavanje 4 1. Yablonsky S.V. Uvod u diskretnu matematiku. M.: Viša škola, V. dio, Ch. 2, s Gavrilov G.P., Sapozhenko A.A. Zadaci i vježbe iz diskretne matematike. M.: Fizmatlit, Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
31 Kraj predavanja 4
Predavanje: Sklopovi funkcionalnih elemenata s kašnjenjem (FES), automatizam preslikavanja koja provode. Prezentacija KAV SFEZ. Pojednostavljenja CAV-a. Razlikovnost i nerazlučivost CAV stanja. Mooreov teorem
Predavanje: Anselov teorem o rastavljanju n-dimenzionalne kocke na lance. Teorem o broju monotonih funkcija logičke algebre. Teorem o dešifriranju monotonih funkcija logičke algebre. Predavač - izvanredni profesor Selezneva Svetlana
Predavanje: Konačni automati s izlazom (FSM). Automatske funkcije, metode za njihovo određivanje. Teorem o transformaciji periodičkih nizova funkcijama automata. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna
Predavanje: Djelomično uređeni skupovi (PSU). CHUM dijagram. Maksimalni, minimalni, najveći i najmanji elementi. Lanci i antilanci, duljina i širina završnih plagova. Teorem o podjeli kuge na antilance.
Predavanje 2. Svojstva binomnih koeficijenata. Izračunavanje zbroja i način generiranja funkcija (konačni slučaj). Koeficijenti polinoma. Procjene binomnih i polinomnih koeficijenata. Procjene iznosa
Predavanje: Algoritam za prepoznavanje potpunosti u P k. Zatvorena nastava. Klase funkcija koje čuvaju skupove i čuvaju particije, njihova zatvorenost. Kuznjecovljev teorem o funkcionalnoj potpunosti. Predkompletna nastava.
Predavanje 2. Kombinatorika. Svojstva binomnih koeficijenata. Izračunavanje zbroja i način generiranja funkcija. Koeficijenti polinoma. Procjene binomnih i polinomnih koeficijenata. Asimptotski
Predavanje: Konačnovrijedne funkcije. Elementarne k-vrijedne funkcije. Metode zadavanja k-vrijednih funkcija: tablice, formule, 1. i 2. oblik, polinomi. Potpunost. Teorem o potpunosti Postovog sustava. Webbova funkcija.
Predavanje 3. Nizovi definirani relacijama ponavljanja. Homogene i nehomogene linearne rekurentne jednadžbe (LORE i LNRU). Opće odluke LORU i LNRU. Predavač - izvanredni profesor Selezneva Svetlana
Predavanje 15. Funkcije konačnovrijednih logika. Elementarne funkcije k-vrijedne logike. Metode zadavanja funkcija k-vrijedne logike: tablice, formule, I i II oblici, polinomi. Potpunost. Predavač - izvanredni profesor Selezneva
Predavanje: Funkcije konačnovrijednih logika. Elementarne funkcije k-vrijedne logike. Metode zadavanja funkcija k-vrijedne logike: tablice, formule, I i II oblici, polinomi. Potpunost. Predavač - izvanredni profesor Selezneva Svetlana
Predavanje: Möbiusova funkcija na kugu. Möbiusova funkcija na n-dimenzionalnoj kocki. Möbiusova formula inverzije. Načelo uključivanja-isključivanja. Problem brojanja broja permutacija-poremećaja. Predavač - izvanredni profesor Selezneva Svetlana
Predavanje 2. Svojstva binomnih koeficijenata. Metoda generiranja funkcija, izračunavanja zbroja i dokazivanja identiteta. Koeficijenti polinoma. Načelo uključivanja-isključivanja. Predavač - izvanredni profesor Selezneva Svetlana
Predavanje: Bitne funkcije. Tri leme o bitnim funkcijama. Yablonskijev kriterij potpunosti. Slupeckijev kriterij potpunosti. Schaefferove funkcije. Predavač izvanredni profesor Selezneva Svetlana Nikolaevna [e-mail zaštićen]
Predavanje: Osnovni kombinatorni brojevi. Procjene i asimptotike za kombinatorne brojeve. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna Fakultet računalne matematike i matematike Moskovskog državnog sveučilišta nazvan po M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su
Predavanje: Svojstva binomnih koeficijenata. Izračunavanje zbroja i način generiranja funkcija (konačni slučaj). Koeficijenti polinoma. Procjene binomnih i polinomnih koeficijenata. Procjene za sume binoma
Predavanje: Konačni automati s izlazom. Transformacija periodičkih nizova pomoću konačnih automata s izlazom. Posebnost stanja u konačnim automatima s izlazom. Pojednostavljivanje strojeva. Predavač Selezneva
Predavanje: Pokrivanje skupa i pokrivanje matrice. Gradijentni premaz. Lema o gradijentnom pokrivanju. Procjene za kardinalnost skupa sjenčanja n-dimenzionalne kocke. Procjene duljine polinomskih normalnih oblika funkcija
Predavanje 5. Pokrivanje skupa i pokrivanje matrice. Gradijentni premaz. Lema o gradijentnom pokrivanju. Procjene za kardinalnost skupa sjenčanja Booleove kocke. Procjene duljine polinomskih normalnih oblika Booleana
Predavanje 3. Nizovi definirani relacijama ponavljanja. Homogene i nehomogene linearne rekurentne jednadžbe (LORE i LNRU). Opće odluke LORU i LNRU. Primjeri Predavač - izvanredni profesor Selezneva
Predavanje 3. Relacije na skupovima. Svojstva. Formula uključivanja-isključivanja. Relacija ekvivalencije. Odnos djelomičnog reda. Predavač - izvanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima.
Predavanje 4. Značajke višeznačnih logika. Zatvoreni razred, osnova zatvorenog razreda. Teoremi Yanova i Muchnika o postojanju u viševrijednim logikama zatvorenih klasa bez baze i zatvorenih klasa s prebrojivim
Predavanje. Funkcije prirodnog argumenta (niza). Homogene i nehomogene linearne rekurentne jednadžbe (LORE i LNRU). Opće odluke LORU i LNRU. Primjeri Predavač - izvanredni profesor Selezneva Svetlana
Predavanje: Kromatski broj grafa. Kriterij za dvobojni graf. Teoremi o gornjoj i donjoj granici za kromatski broj grafa. Predavač - izvanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima.
Predavanje: Grafovi i mreže. Procjena broja pseudografa s q bridova. Procjena broja stabala s q bridova. Planarni grafovi. Eulerova formula za planarne grafove. Najveći broj bridova u planarnim grafovima. Neplanarnost
Predavanje 1. Kombinatorika. Postavljanja, permutacije, postavljanja s ponavljanjima, kombinacije, kombinacije s ponavljanjima. Njihov broj. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna Katedra za matematičku kibernetiku
Predavanje: Nizovi. Homogene i nehomogene linearne rekurentne jednadžbe. Opća rješenja linearnih rekurentnih homogenih i nehomogenih jednadžbi. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna
Predavanje 8. Bojanke. Ekvivalencija bojanja u odnosu na skupinu. Generirajuće funkcije. Redak za nabrajanje za brojke i red za nabrajanje za funkcije. Polyin teorem. Predavač Svetlana Nikolaevna Selezneva
Predavanje: Bojanke. Ekvivalencija bojanja s obzirom na skupinu permutacija. Polyin teorem (poseban slučaj). Generirajuće funkcije. Redak za nabrajanje za brojke i red za nabrajanje za funkcije. Teorema
Predavanje 2. Konjunktivni normalni oblici. Implicenta, jednostavna implicenta funkcije. Reducirana CNF funkcija logičke algebre. Metode konstruiranja skraćene CNF. Predavač Svetlana Nikolaevna Selezneva [e-mail zaštićen]
Matematički modeli i metode logičke sinteze VLSI-a Jesen 2015. Predavanje 4 Plan predavanja Logička optimizacija kombinacijskih logičkih sklopova Razni načini predstavljanja funkcija logičke algebre (FAL)
Predavanje: Nedeterministički konačni automati (NFA) bez izlaza. Teorem o podudarnosti klasa skupova riječi koje dopuštaju konačni deterministički i konačni nedeterministički automati. Postupak
Predavanje 1. Uzorci. Postavci, permutacije, postavljanja s ponavljanjima, kombinacije, kombinacije s ponavljanjima, njihov broj. Primjeri. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna Predavanja na kolegiju Diskretno
Predavanje 1. Kombinatorski objekti: izbori, postavljanja, permutacije, postavljanja s ponavljanjima, kombinacije, kombinacije s ponavljanjima, njihov broj. Kombinatorni brojevi: faktorijel, opadajući faktorijel, binom
PREDAVANJE 4 DIJAGRAMI IZ FUNKCIONALNIH ELEMENATA 1. Osnovne definicije Prije svega potrebno je razmotriti sastav. Funkcija se može smatrati "crnom kutijom" koja ima ulaz i izlaz. Neka
Predavanje 2. Algoritam za prepoznavanje potpunosti u P k. Kuznjecovljev teorem. Zatvorena nastava. Klase funkcija koje čuvaju skup. Klase particijskih funkcija. Predkompletna nastava. Predavač Doktor fizikalno-matematičkih znanosti Selezneva
Predavanje 3. Zhegalkinov polinom. Metode konstruiranja polinoma Zhegalkinove funkcije. Linearna implicitna funkcija. Linearni konjunktivni normalni oblik (LCNF). Pronalaženje svih linearnih implicitnih funkcija. Ispitivanje
Predavanje 2. Generirajuće funkcije: izračunavanje kombinatornih zbrojeva i dokazivanje identiteta, navođenje kombinatornih objekata. Načelo uključivanja-isključivanja. Brojanje broja permutacija-poremećaja. Predavač -
Predavanje 5. Grafovi. Stranice za bojanje grafikona. Kromatski broj grafa. Kriterij da graf bude dvobojan. Gornje granice za kromatski broj grafa. Predavač Doktor fizikalno-matematičkih znanosti Selezneva Svetlana Nikolaevna [e-mail zaštićen] Predavanja
Predavanje: Konačni automati (FSM) bez izlaza (konačni automati-prepoznavači). Prijelazni dijagrami. Automatski postavlja (jezici). Lema o svojstvima automatskih skupova. Primjer neautomatskog skupa. Predavač
Predavanje 1. Konačne funkcije. Elementarne k-vrijedne funkcije. Metode zadavanja k-vrijednih funkcija: tablice, formule, 1. i 2. oblik, polinomi. Potpunost. Teorem o potpunosti Postovog sustava. Webbova funkcija.
Predavanje 7. Problem izbora ruta i njegov poseban slučaj - problem raspodjele letova po danima. Grafički model za problem distribucije leta. Kromatski broj grafa. Kriterij dvobojnosti grafa.
Kolegij “Osnove kibernetike” za studente smjera 01.02.09.01 (matematički i računalni softver) 1. Opće informacije (opterećenje studija, oblici kontrole, itd.). Tečaj je
Predavanje 6. Grafovi. Nasljedna svojstva grafova. Procjena broja bridova u grafovima s nasljednim svojstvom. Ekstremni grafikoni. Najveći broj bridova u ravninskim grafovima i grafovima bez trokuta sa zadanim
Math-Net.Ru Sveruski matematički portal D. S. Romanov, Metoda za sintezu lako testiranih sklopova koji dopuštaju pojedinačne verifikacijske testove konstantne duljine, Diskr. Mat., 2014, svezak 26, broj 2,
Predavanje: Konačni automati bez izlaza, deterministički i nedeterministički. Teorem o podudarnosti klasa skupova riječi koje dopuštaju konačni deterministički i nedeterministički automati. Postupak
Praktičan rad 2. Konstrukcija normalnih oblika logičke funkcije Cilj rada: Naučiti konstruirati konjunktivne, disjunktivne, perfektne normalne forme logičke funkcije Sadržaj rada: Osnovni.
Seminar o složenosti Booleovih funkcija Predavanje 1: Uvod A. Kulikov Computer Science club na POMI http://compsciclub.ru 25.09.2011. 25.09.2011. 1 / 26 Plan predavanja 1 Booleove funkcije 2 Booleovi sklopovi 3 Gotovo
Praktični rad 1. Analiza i sinteza logičkih i relejnih sustava upravljanja UVOD Uređaji s diskretnim djelovanjem izrađeni na elementima hidrauličke, pneumatske i električne automatike te upravljačkih mikroprocesora.
Predavanje: Regularni izrazi i regularni skupovi. Kleeneov teorem o podudarnosti klasa automatskih skupova i regularnih skupova. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna Predavanja iz diskretne matematike
Predavanje 3 Booleove algebre i Booleove funkcije Booleove algebre Pojam algebarskih sustava Algebarski sustav ili algebarska struktura skup je simbola neke abecede (nositelja) sa zadanim
Predavanje 5. Grafovi. Primjeri primjene grafova. Problem transporta. Protok u mreži, Fordov i Fulkersonov teorem o vrijednosti maksimalnog protoka u mreži. Algoritam za konstruiranje maksimalnog protoka u mreži. Predavač
Predavanje: Grafovi. Primjeri primjene grafova. Problem transporta. Protok u mreži, Fordov i Fulkersonov teorem o vrijednosti maksimalnog protoka u mreži. Algoritam za konstruiranje maksimalnog protoka u mreži. Predavač -
Lekcija 8 Prisjetimo se da za proizvoljne skupove A i B postoje skupovi A B = (x x A i x B); (presjek A i B) A B = (x x A ili x B); (unija A i B) A\B = (x x A i x / B) (razlika A i B).
Predavanje 7. Ramseyevi brojevi. Gornja granica za Ramseyev broj. Donja granica za Ramseyev broj. Predavač Svetlana Nikolaevna Selezneva [e-mail zaštićen] Fakultet računalne matematike i matematike Moskovskog državnog sveučilišta nazvan po M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.ru
Predavanje: Grafovi. Osnovni koncepti. Povezani grafovi. Drveće. Razapinjuće stablo. Broj visećih vrhova u razapinjućem stablu. Predavač - izvanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima. Magisterij,
Predavanje 11. Booleovi sklopovi. Diskretna matematika, Viša ekonomska škola, Fakultet računarstva (jesen 2014. proljeće 2015.) Booleov sklop u varijablama x 1,..., x n nazvat ćemo nizom Booleovih funkcija g
ODOBRENO od strane prorektora za nastavu Yu.A.Samarsky 10. lipnja 2008. PROGRAM I ZADATKE za predmet DISKRETNE STRUKTURE smjera 010600 Fakultet FIVT Katedra za analizu podataka Kolegij II semestar 4 Dva
Moskovski državni sveučilište Lomonosov Fakultet računalne matematike i kibernetike S. A. Lozhkin ELEMENTI TEORIJE SINTEZE DISKRETNIH UPRAVLJAČKIH SUSTAVA Moskva 2016. Sadržaj
Predavanje: Nasljedna svojstva grafova. Ekstremni grafikoni. Ramseyevi brojevi. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna Fakultet računalne matematike i matematike Moskovskog državnog sveučilišta nazvan po M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su Nasljedno
Predavanje: Operacije na konačno automatskim skupovima. Komplement, unija, presjek, produkt i iteracija automatskih skupova, njihovi automati. Predavač - izvanredni profesor Selezneva Svetlana Nikolaevna Predavanja
Ministarstvo Ruske Federacije za komunikacije i informacije Državna akademija za telekomunikacije i informatiku Povolške regije Odjel za višu matematiku Odobreno od strane Metodološkog vijeća PGATI 29. ožujka 2002.
Predavanje 5. Bojanje bridova grafova. Kromatski indeks grafa. Kromatski indeks bipartitnih grafova. Gornje i donje granice za kromatski indeks grafa. Predavač Svetlana Nikolaevna Selezneva [e-mail zaštićen]
Math-Net.Ru Sveruski matematički portal N. P. Redkin, O shemama koje omogućuju kratke pojedinačne dijagnostičke testove, Diskr. Mat., 1989, svezak 1, broj 3, 71 76 Upotreba sveruskog
MATEMATIČKA LOGIKA(1) Zadaci za praktičnu nastavu 1. Algebra iskaza Tvrdnja je veličina koja može imati dvije vrijednosti: istinitu i netočnu. Izjave su označene velikim latiničnim slovima.
