Sljedeći "inženjersko-konstruktivni" smisao može se dati predstavljanju Bulovih funkcija formulama. Formulu F (x 1, ..., xn) nad nekim proizvoljno fiksnim skupom F smatraćemo "crnom kutijom", određenim uređajem, na čiji se ulaz unose svi mogući skupovi vrijednosti varijabli, i izlaz koji odgovara ovim skupovima vrijednosti funkcije f predstavljene formulom F (slika 6.22).
Da bismo razumjeli kako funkcionira "crna kutija", moramo rastaviti proces konstruiranja formule iz podformula. Dolazak do "osnovnih" podformula, tj. elemenata skupa F, dolazimo do "građevinskih blokova", strukturnih elemenata od kojih je sastavljena "crna kutija" koja izračunava funkciju f. Svaku funkciju "baze" F izračunava odgovarajući "čvor", koji se smatra najmanjom strukturnom jedinicom naše "crne kutije", a njena unutrašnja struktura se više ne analizira.
Primjer 6.22. Odaberimo standardnu osnovu za skup F. Tada se formula preko standardne baze, koja predstavlja funkciju ~ (ekvivalentnost), konstruira na sljedeći način:
Proračun prema ovoj formuli (i proces njegove konstrukcije od elemenata standardne osnove) može se shematski prikazati kao što je prikazano na sl. 6.23.
Varijabla x 1 (tačnije, vrijednost ove varijable) se dovodi na ulaz konstruktivnog elementa koji se zove inverter (slika 6.24, a) i izračunava negaciju. Negativni x 1 uklonjen sa izlaza pretvarača, tj. funkcija x 1, se dovodi na jedan od ulaza konjunkora (slika 6.24, b), na čiji se drugi ulaz dovodi varijabla x 2. Na izlazu spojnika pojavljuje se funkcija x 1 x 2. Izračunavanje funkcije x 1 x 2 može se pratiti na sličan način, obje ove funkcije se unose na ulaze disjunktora (slika 6.24, c), iz čijeg se izlaza dobija funkcija x 1 x 2 ∨ x 1 x 2 se uklanja (ovo nije ništa drugo do zbir po modulu 2: x 1 ⊕ x 2). I konačno, ova funkcija se dovodi na ulaz pretvarača, na čijem se izlazu već dobija funkcija ~ (ekvivalencija). #
Tako dolazimo do ideje "kola" - matematičkog modela kalkulatora Booleove funkcije, predstavljenog određenom formulom, sastavljenom od strukturnih elemenata, od kojih svaki izračunava jednu od "osnovnih" Booleovih funkcija. U opštem slučaju, "kolo" izračunava Boolean operator, a svaka koordinatna funkcija ovog operatora se uklanja iz jednog od izlaza kola.
Matematički, "šema" je definirana kao usmjereni graf posebne vrste, u kojem su označeni i vrhovi i lukovi.
Uvedemo oznaku: ako je F neki skup Bulovih funkcija, onda sa F (n) označavamo podskup F koji se sastoji od svih funkcija n varijabli (n≥0).
Definicija 6.14. Neka su skupovi fiksni: F (Booleove funkcije) i X (Booleove varijable).
Dijagram funkcionalnih elemenata na bazi F ∪ X (C Φ E), ili jednostavno kontrahovan preko baze F ∪ X, također (F, X) -šema, naziva se otvorenim usmjerenim grafom (tj. mrežom), čiji je svaki vrh označen jednim od elemenata skupa FU X tako da su ispunjeni sljedeći zahtjevi:
- svaki ulaz mreže je označen ili nekom promenljivom 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 polustepen ulaska jednak n, a na skupu lukova koji ulaze u vrh v, numeracija (jedan prema jedan) je data tako da je svaki luk numerisan od 1 do n.
Ako se osnova podrazumijeva, onda ćemo reći jednostavno "šema". Osim toga, ako je skup varijabli fiksiran "jednom za svagda" i kada se razmatraju različite sheme mijenjamo samo skup funkcija F, tada, kao što smo to učinili, uvodeći koncepte formule i superpozicije nad datom bazom, mi će govoriti o SFE preko baze F, pretpostavljajući svaki put, što znači jednom fiksni skup varijabli X, koji (ako to ne šteti tačnosti) se ne spominje.
Sada indukcijom definišemo pojam boolean funkcija izračunata od strane vrha kola .
Definicija 6.15. Neka se da CFE S preko baze F ∪ X, čiji je skup vrhova V.
- Pretpostavlja se da svaki ulaz CFE 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 sa brojem i (1≤i≤n) koji ulazi u njega dolazi iz vrha ui ∈ V, koji izračunava funkciju gi, tada je vrh v izračunava superpoziciju f (g 1, ..., gn).
Dakle, ako svaki vrh CFE-a nad F izračunava neku funkciju, tada je redoslijed kojim su funkcije g 1, ..., gn nabrojane, zamjenjene na mjestima varijabli funkcije f, bitan u općem slučaju . Prirodno je nazvati Bulovu funkciju f u n varijabli komutativnom ako čuva svoju vrijednost pod proizvoljnom permutacijom svojih varijabli. U ovom slučaju ne moramo brinuti o numeraciji lukova koji ulaze u vrh kruga, označenih takvom funkcijom.
Primjer 6.23. Razmotrite SPE na sl. 6.25. Vrhovi v 1 i v 2 su ulazi u SFE. Ovi vrhovi izračunavaju funkcije x i y, respektivno. Tada vrh v 3, kao i vrh v 4, prema definiciji 6.15, izračunava funkciju x | y (Schaefferov potez), a vrh v 5 (izlaz mreže) izračunava funkciju (x | y) l (x | y), za koju je poznato da je jednako konjunkciju x y.
SPE 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. Boolean funkcija izračunata CFE preko baze F ∪ X, je funkcija izračunata bilo kojim od njenih izlaza.
Dakle, CFE izračunava tačno koliko Booleovih funkcija, koliko izlaza. SFE na sl. 6.25 izračunava jednu funkciju, a SPE na sl. 6.26 - dva.
U opštem slučaju, ako je (x 1, ..., x n) skup svih varijabli koje služe kao oznake za ulaze kola S preko baze F ∪ X sa m izlaza, CFE S definira prikaz logičke kocke B n u logičku kocku B m, tj. boolean operator.
Napomena 6.10. U nekim slučajevima, funkcija izračunata datim SFE je nešto drugačije definirana, pod pretpostavkom da je to funkcija izračunata bilo kojim vrhom iz podskupa odabranih SFE vrhova. Konkretno, to mogu biti izlazi. U svakom slučaju, dogovorimo se da iz odabranih (u upravo naznačenom smislu) vrhova kola nacrtamo "izlaznu" strelicu. #
Dakle, svaki krug kapija izračunava neki Bulov operator, posebno, ako je broj izlaza kola jednak 1, onda izračunava neku Booleovu funkciju.
Može se dokazati i obrnuto: za bilo koji Bulov operator, SFE se može konstruisati preko baze F, gde je F kompletan skup koji izračunava dati operator.
Funkciju y 1 predstavljamo u Žegalkinovoj bazi. Koristeći de Morganove zakone, dobijamo
(podsjetimo da je zbir po modulu 2 bilo kojeg parnog broja jednakih članova jednak 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 Boolean operator dat u tabeli. 6.9, preko baze Žegalkina prikazana je na Sl. 6.27.
Prilikom dizajniranja SFE-a, korisno je imati na umu numerički parametar koji se zove njegova složenost.
Složenost SFE je broj njegovih vrhova koji nisu inputi.
Prikazano na sl. 6.27 CFE preko baze Žegalkina ima složenost 5.
Razmotrimo sada CFE za istog operatera preko standardne osnove.
Prema tabeli (vidi tabelu 6.9), konstruišemo 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.
Karnotova karta za ovu funkciju, prikazana na Sl. 6.28 pokazuje da se ne može minimizirati (tačnije, gore napisani SDNF je minimalni DNF za ovu funkciju). Ali možete ići drugim putem. Možemo uzeti u obzir tabelu. 6.9 kao tabela koja definiše parcijalnu logičku funkciju y 2 = y 2 (x 1 x 2 x 3 y 1). Minimiziranjem ove funkcije po
Karnotova karta * prikazana na sl. 6.29, dobijamo
* Na ovoj karti smo označili skupove na kojima funkcija uzima vrijednost 0, stavljajući nule u odgovarajuće ćelije. Stoga želimo još jednom skrenuti pažnju na činjenicu da ne treba brkati nule sa crticama: crtica u ćeliji karte koja navodi djelomičnu 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).
CFE preko standardne osnove za razmatrani Bulov operator prikazan je na Sl. 6.30. Složenost ovog SFE-a je 11. Imajte na umu da vrh koji izračunava funkciju y 1 nije izlaz.
Boolean operator u ovom primjeru izračunava dvocifreni zbir (modulo 2) tri jednocifrena člana. Takođe se može smatrati jednobitnim binarnim sabiračem — funkcionalnim blokom višebitnog binarnog sabirača — za dva pojma. Tada se funkcija y 1 tumači kao "prenosni signal" u najznačajnijem bitu. Na sl. 6.31 prikazuje "vezu" tri SFE-a (kao što je prikazano na slici 6.30), uz pomoć kojih se izračunava zbir dva trocifrena binarna broja. Konstanta 0 se dovodi na treći ulaz sabirača za najmanji bitni bit, a "prenosni signal" najznačajnijeg bita je najznačajniji bit sume, koji će u opštem slučaju biti četvorocifreni broj .
Napomena 6.11. Ako dizajniramo SFE na standardnoj osnovi i želimo da minimiziramo njegovu složenost, tada moramo prije svega 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 najmanji broj pojavljivanja varijabli pod negativnim predznakom. Sa stanovišta složenosti SFE-a, koji će se graditi na bazi minimalnog DNF-a, to znači da minimizira broj "invertera" - SFE vrhova označenih funkcijom negacije.
Na primjer, za funkciju definiranu Karnotovom mapom (slika 6.32), jezgru, koja se sastoji od jednostavnih implikanata x 1 x 2 x 4 i x 1 x 3 x 4, trebate dodati jednostavan implikant x 2 x 3 x 4, a ne x 1 x 2 x 3 jer ne sadrži negative.
U savremenoj tehnologiji upravljačkih i računarskih uređaja značajno mjesto zauzimaju diskretni pretvarači, odnosno uređaji koji imaju određeni broj ulaza i izlaza. Skupovi signala koji pristižu na ulaze i nastaju na izlazima pripadaju poznatim konačnim skupovima.
Podijelite svoj rad na društvenim mrežama
Ako vam ovaj rad nije odgovarao na dnu stranice nalazi se lista sličnih radova. Možete koristiti i dugme za pretragu
Aranov Viktor Pavlovič. Discrete Math. Odjeljak 5. DNF i FE kola.
Predavanje 28. Dijagrami funkcionalnih elemenata. Problemi analize i sinteze
Predavanje 28. DIJAGRAMI IZ FUNKCIONALNIH ELEMENTA.
PROBLEMI ANALIZE I SINTEZE
Plan predavanja:
1. Koncept kola funkcionalnih elemenata(FE).
2. Problemi analize i sinteze kola iz PV.
- Koncept kola iz PV
U savremenoj tehnologiji, upravljački i računarski uređaji zauzimaju značajno mjestodiskretni pretvarači, odnosno uređaji koji imaju određeni broj ulaza i izlaza. Skupovi signala koji pristižu na ulaze i nastaju na izlazima pripadaju poznatim konačnim skupovima. Uređaji pretvaraju ulazne skupove signala u izlazne. Matematički model ovakvih uređaja je tzvdijagrami funkcionalnih elemenata(SFE).
Kao primjer, razmotrite električni krug od tri diode i otpor, prikazan na sl. 1.
Rice. 1. Električni dijagram i njegov simbol
Na tačkama kola prikazanog u krugu, u različito vrijeme, može se pojaviti ili visok nivo, približno jednak 5 V, ili nizak nivo, približno jednak nuli. Na tački u krugu označenoj crticom, nivo napona je konstantno nizak.
Označene tačke će se tumačiti kao ulazi, a tačka - kao izlaz. Rad kola se može opisati na sljedeći način: ako svi ulazi imaju nizak napon, onda je i izlaz nizak, ako barem jedan od ulaza ima visoku razinu napona, onda je izlaz visok. Ako označite stanje s visokim naponskim nivoom kao jedan, a sa niskim naponskim nivoom - nula, tada se ovisnost izlaza o ulazima može postaviti pomoću Booleove funkcije.
Na osnovu toga, gornji sklop se naziva logički element "ILI".
Takva kola mogu biti izgrađena od elektronskih cijevi, elektromehaničkih prekidača, pneumatskih elemenata itd. Ovisnost izlaza o ulazima može se opisati ne samo kao disjunkcija, već i korištenjem konjunkcije, negacije i složenijih Booleovih funkcija.
Razmotrit ćemo logička vrata s različitim ovisnostima izlaza na ulazima. Ovi elementi se mogu povezati jedni s drugima, napajajući izlaze nekih elemenata ulazima drugih. Kao rezultat, dobijamo SFE.
Definicija pojma SFE može se podijeliti u dvije faze. U prvoj fazi otkriva se strukturni dio ovog koncepta, u drugoj - funkcionalni.
I pozornici. Podijelimo ovu fazu na nekoliko tačaka.
1 ... Postoji konačan skup objekata () koji se nazivajulogičkih elemenata.Svaki element ima ulaze i jedan izlaz. Element je grafički prikazan kao što je prikazano na sl. 2.
2 ... Indukcijom definišemo pojam logička mreža kao objekat u kome postoji određen broj ulaza i određeni broj izlaza (slika 3).
a) Osnova indukcije. Izolovani vrh se naziva trivijalna logička mreža. Po definiciji, to je i ulaz i izlaz (slika 4).
… …
…
Rice. sl. 2 Slika 3 4
b) Induktivna tranzicija. Ovaj dio se zasniva na korištenju tri operacije.
I ... Operacija kombinovanja disjunktnih mreža. Neka i budu dvije disjunktne mreže (bez zajedničkih elemenata, ulaza i izlaza), koje imaju ulaze i izlaze, respektivno. Mrežna interkonekcija teoretskih skupova je logička mreža koja ima ulaze i izlaze.
II ... Operacija pričvršćivanja elementa. Neka mreža i element budu takvi da su u odabranim različiti izlazi sa brojevima. Tada se figura naziva logičkom mrežom, koja je rezultat povezivanja elementa na mrežu. Ulazi su svi ulazi, izlazi su svi mrežni izlazi, osim izlaza sa brojevima, kao i izlaz elementa. Mreža ima ulaze i izlaze (slika 5).
… …
Rice. 6.
Rice. 5
III ... Operacija razdvajanja izlaza. Neka utičnica sa brojem bude istaknuta u mreži. Tada se broj naziva logičkom mrežom dobivenom cijepanjem izlaza. Ulazi su svi ulazi, izlazi su svi izlazi mreže sa brojevima 1,…,…, i još dva izlaza koja su nastala iz izlaza sa brojem mreže (slika 6). Stoga ima ulaze i izlaze.
3 ... Neka se abecede i daju.
Dijagram funkcionalnih elemenatanaziva se logička mreža sa ulazima iz abecede i izlazima iz abecede, što se označava
. (1)
Evo nekoliko primjera kola.
1. Neka se skup sastoji od tri elementa AND (konjuktor), OR (dizjunktor) i NE (invertor).
Tada će slika (slika 6) biti dijagram, budući da se može konstruisati pomoću operacija I - III .
Rice. 6 Fig. 7
2. Slika prikazana na sl. 7 je takođe šema.
II pozornici. Određivanje funkcionisanja kola.
4 ... Uporedimo CFE (1) sa sistemom funkcija Bulove algebre
(2)
takođe pozvanprovodljivost ovog kola.
Primjer. a) Za šemu imamo sistem koji se sastoji od jedne jednačine
Or.
b) Za kolo dobijamo slično
- Implementacija Booleovih funkcija pomoću FE kola. Problemi analize i sinteze
kola iz PV
Zadatak analize: za dati SFE (1) dobiti sistem Bulovih jednačina (2).
Algoritam za rješavanje problema: praćenje operacija izgradnje mreže I - III , sekvencijalno izračunavamo funkcije na izlazima elemenata mreže.
Problem sinteze: za datu osnovu funkcionalnih elemenata i proizvoljan sistem Bulovih jednačina (2), konstruisati kolo (1) iz datog FE koje implementira ovaj sistem jednačina.
Postojanje rješenja problema sinteze određeno je Postovom teoremom, prema kojoj sistem funkcija koje implementiraju osnovne FE mora biti potpun. Funkcije se mogu predstaviti kao superpozicija funkcija, a svaki korak superpozicije odgovara određenoj kombinaciji elemenata.
Primjer. Za funkciju
(3)
Dijagram koji odgovara superpoziciji na desnoj strani formule (3) prikazan je na Sl. osam.
Rice. osam
Problem sinteze leži u činjenici da je za dati sistem Bulovih jednačina moguće konstruisati mnogo FE kola koja implementiraju ovaj sistem. S tim u vezi, javlja se problem optimalne sinteze: iz svih vrsta shema koje implementiraju datu funkciju, odaberite najbolju prema jednom ili drugom kriteriju, na primjer, sa najmanjim brojem elemenata. Takve šeme će se zvati minimalno.
Sljedeća izjava je tačna.
Teorema. Postoji algoritam koji gradi minimalno kolo za svaki sistem Bulovih funkcija.
Ovaj algoritam za konstruisanje minimalnih kola spada u klasu algoritama tipa „brute sile“, jer se zasniva na pregledu svih kola do određene složenosti. Algoritmi iscrpnog pretraživanja, po pravilu, su veoma naporni i neprikladni za praktične svrhe. Stoga u nastavku razmatramo jednostavniji problem za koji originalni sistem jednačina sadrži jednu jednačinu
i, prema tome, željeno kolo ima jedan izlaz.
Složenost minimalnog kola se označava sa. Problem sinteze nećemo razmatrati za posebnu funkciju, već za cijelu klasu funkcija varijabli. Kvaliteta algoritama sinteze uspoređuje se poređenjem takozvanih Šenonovih funkcija. Neka bude
- minimalna složenost šema koje implementiraju, a koje se dobijaju korišćenjem algoritma.
Funkcije se zovu Šenonove funkcije i to je očigledno
Problem sinteze je pronaći algoritam kojem bi bio što bliži, a da bi složenost algoritma bila znatno manja od složenosti algoritma iscrpnog pretraživanja. Kod ove formulacije problema nije potrebno da algoritam pronađe minimalno kolo za svaku funkciju, potrebno je samo da najjednostavnije kolo dobijeno uz pomoć ima složenost koja ne prelazi mnogo.
Drugi slični radovi koji bi vas mogli zanimati. Wshm> |
|||
| 9013. | METODE ZA SINTEZU ŠEMA IZ FE. DEKODER I BINARNI DIJAGRAMI | 153,07 KB | |
| Opća teorija CFE sinteze dovodi do zaključka da većina Booleovih funkcija za velike vrijednosti ima složena minimalna kola. To znači da je vrlo uska klasa Bulovih funkcija od praktične vrijednosti sa stanovišta sinteze. | |||
| 5321. | Vrste i vrijednosti parametara automatske zaštite za različite elemente date projektne sheme | 526,7 KB | |
| Za normalan rad elektroenergetskog sistema i potrošača električne energije potrebno je što prije identifikovati i odvojiti mjesto oštećenja od neoštećene mreže, čime se uspostavljaju normalni uslovi rada elektroenergetskog sistema i potrošača. | |||
| 5384. | Izrada električnog kola postolja za analizu rada klokovanog dekodera za 4 ulaza i 16 izlaza | 626.63 KB | |
| Za unapređenje rada voznog parka ATP razvijena je organizaciona struktura sistema održavanja i popravke voznog parka ATP i predložen je set opreme za dijagnostiku i održavanje. Glavni zadatak funkcionisanja objekata za popravku preduzeća je osigurati nesmetan rad opreme. Obuhvata: popravnu i restauratorsku bazu preduzeća, skladišta, prodavnice i opšta odeljenja remontnih objekata, tehnološku opremu, otpremu. Organizacija... | |||
| 1886. | Faze analize sistema, njihovi glavni ciljevi, ciljevi | 27,44 KB | |
| Teorija optimalnih sistema nam omogućava da procijenimo granicu do koje se može doći u optimalnom sistemu, uporedimo je sa pokazateljima trenutnog neoptimalnog sistema i utvrdimo da li je u datom slučaju preporučljivo razvijati optimalni sistem. Za automatski kontrolisani proces automatski kontrolisanog sistema razlikuju se dve faze optimizacije: statička i dinamička. Statička optimizacija rješava probleme kreiranja i implementacije optimalnog modela procesa i dinamičkog ... | |||
| 5123. | Razvoj funkcionalnih strategija | 35,44 KB | |
| HR strategija. Funkcije i upravljačka struktura. Funkcije upravljanja i njihova uloga u formiranju upravljačkih struktura. Hijerarhijski tip strukture upravljanja. | |||
| 20368. | Utjecaj sastava komponenti recepture i tehnologija na potrošačka svojstva funkcionalnih proizvoda | 742,05 KB | |
| Koncept optimalne ishrane je prihvaćen od strane savremene medicinske nauke. To znači da je napravljen prelazak sa koncepta adekvatne ishrane, kada su se uglavnom regulisali i normalizovali makronutrijenti – izvori masti, izvori energije, plastični materijali (lipidi, proteini, masti), na koncept optimalne ishrane, kada se Spektar nutrijenata neophodnih za vitalnu aktivnost organizma i ostalih manjih komponenti koje su ranije bile zanemarene znatno je proširen. | |||
| 4706. | Metode za sintezu Me karboksilata | 9.26 MB | |
| Suština metode je otapanje metalnog oksida, hidroksida ili karbonata u vodenoj otopini odgovarajuće kiseline. Proizvod se izoluje isparavanjem rastvora pre kristalizacije ili filtracijom taloga ako je karboksilat nerastvorljiv ili ograničeno rastvorljiv u vodi. | |||
| 15923. | Osnovne metode za sintezu pirazalodiazepina | 263,39 KB | |
| Nove metode za sintezu derivata pirazolodiazepina. Razvoj novih strategija sinteze je od velikog interesa. Sistematske i generalizirajuće studije sinteze derivata pirazolodiazepina nisu rađene, neka pitanja ostaju nesporna ili potpuno neriješena. | |||
| 11978. | Instalacije energetske tehnologije zasnovane na hidrotermalnoj oksidaciji aluminijuma za proizvodnju električne energije, toplote, vodika i funkcionalnih nanomaterijala | 49,89 KB | |
| Razvoj se zasniva na reakciji hidrotermalne oksidacije aluminijuma, tokom koje se oslobađa velika količina toplotne energije i formiraju aluminijumski oksidi i vodonik: l2H2O → lOOH boehmite15H2415. Kao početni reagensi koriste se destilirana voda i aluminijski prah mikronske veličine. Instalacija KEU10 Instalacija ETK100 Tehničke karakteristike instalacije ETK100: Parametar Vrijednost Potrošnja aluminijuma kg h 101 Potrošnja vode na ulazu u uređaj za tretman vode kg h 484 Produktivnost za vodonik nm3 110 Toplotna snaga ... | |||
| 6605. | Ekspertni sistemi. Projektovanje TP metodom sinteze | 11,67 KB | |
| Predstavljanje akumulacije znanja i njegovo ažuriranje je složen zadatak koji se istražuje u dijelu informatike koji se zove inženjering znanja. Inženjer znanja učestvuje u razvoju baze znanja – jezgra sistema koji se naziva inteligentni. Najčešće se inteligentni sistemi koriste za rješavanje složenih problema gdje je glavna složenost rješenja ... | |||
Veličina: px
Počnite prikazivati sa stranice:
Transkript
1 Predavanje 2. Šeme funkcionalnih elemenata (SFE) u određenoj osnovi. Složenost i dubina sheme. Primjeri. Metoda za sintezu SFE iz DNP. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja iz diskretne matematike 2. 1. godina, grupa 141, Fakultet računarske matematike i kibernetike, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na sajtu
2 Dijagrami funkcionalnih elemenata Definirajmo dijagrame funkcionalnih elemenata u određenoj osnovi. Neka nam je dat neki skup Bulovih funkcija B = (g 1 (x 1, ..., x n1), ..., gs (x 1, ..., x ns)) P 2, gdje je n 1, .. ., ns 0. Ovaj skup nazivamo bazom. Imajte na umu da ovaj koncept baze nema nikakve veze sa konceptom baze P 2, koji je razmatran u algebri logike. Po pravilu ćemo uzeti u obzir standardnu bazu B 0 = (x & y, x y, x).
3 Određivanje kola funkcionalnih elemenata Kolo funkcionalnih elemenata (CFE) u bazi B 0 = (x & y, xy, x) je 1) orijentirani aciklički graf G = (V, E), svaki vrh v V od kojih ima polovinu stupnja ulaska d (v ) ne više od dva (d (v) 2); 2) svaki vrh v sa polustepenom ulaska jednakim 0 (d (v) = 0) naziva se ulaz (ili ulaz kola) i pripisuje mu se neka Bulova varijabla x i; 3) svi ostali čvorovi (osim ulaza) nazivaju se unutrašnjim čvorovima kola;
4 Definicija kola funkcionalnih elemenata (nastavak) 4) svakom vrhu v sa polustepenom ulaska jednakim 1 (d (v) = 1) dodjeljuje se (funkcionalni) element negacije; svi takvi vrhovi se nazivaju invertori; 5) svakom tjemenu v sa polustepenom ulaska jednakim 2 (d (v) = 2) dodjeljuje se ili (funkcionalni) konjunkcijski element &, ili (funkcionalni) element disjunkcije; svi vrhovi kojima su dodijeljeni elementi konjunkcije nazivaju se konjunktori, svi vrhovi kojima su dodijeljeni elementi disjunkcije nazivaju se disjunktori;
5 Definicija sklopa funkcionalnih elemenata (nastavak) 6) Osim toga, nekim od vrhova su dodijeljene parno različite izlazne varijable y 1, ..., y m. Ako je zadan SPE S, čiji su ulazi dodijeljeni samo varijable x 1, ..., xn, a sa izlaznim varijablama y 1, ..., ym, tada ćemo ovaj SPE označiti sa S (x 1 , ..., xn; y 1, ..., ym).
6 Primjer SFE Primjer 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):
7 Primjer SFE Primjer 1. Po pravilu, SFE se prikazuju na sljedeći način S (x 1, x 2, x 3; y 1, y 2, y 3):
8 Određivanje složenosti SFE Složenost L (S) SFE S je broj unutrašnjih vrhova ovog SFE, tj. broj funkcionalnih elemenata u SFE S.
9 Složenost SFE Primjer 2. Složenost SFE S:
10 Određivanje dubine vrha CFE Indukcijom određujemo dubinu d (v) vrha v u CFE S. 1. Osnova indukcije. Svaki ulaz v SFE S ima dubinu jednaku 0: d (v) = Induktivni prijelaz. 1) Ako luk iz vrha v 1 vodi do pretvarača v CFE S, tada je d (v) = d (v 1)) Ako lukovi iz vrhova v 1 i v 2 vode do konjuktora ili disjunktora v CFE S, onda je d (v) = max (d (v 1), d (v 2)) + 1. Dubina D (S) SFE S naziva se maksimumom dubina njegovih vrhova.
11 Dubina SFE Primjer 3. Dubina vrhova SFE S i dubina SFE S:
12 Definicija funkcioniranja SFE Na svakom vrhu SFE-a se realizuje (ili izračunava) određena Booleova funkcija. Indukcijom definiramo Booleovu funkciju koja se realizuje na vrhu v CFE S. 1) Ako je v ulazni vrh, a varijabla xi mu je dodijeljena, tada se funkcija fv = xi realizuje na vrhu v . 2) Ako luk iz vrha v 1 vodi do pretvarača v, a funkcija f v1 se realizuje na vrhu v 1, tada je funkcija f v = f v1 realizovana na vrhu v. 3) Ako lukovi iz vrhova v 1 i v 2 vode do konjunktora (ili disjunktora) v, a funkcije f v1 i f v2 se realizuju na vrhovima v 1 i v 2, tada na vrhu v funkcija fv = f v1 i f v2 (fv = f v1 f v2).
13 Funkcioniranje CFE Vjeruje se da CFE S (x 1, ..., xn; y 1, ..., ym) implementira sistem Booleovih funkcija FS = (f 1, ..., fm), koji se realizuju na njegovim izlaznim vrhovima y 1, ..., y m.
14 Funkcioniranje SFE Primjer 4. Booleove funkcije realizovane na vrhovima SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Linearni program Linearni program sa ulazima x 1, ..., xn preko baze B 0 = (x & y, xy, x) je niz z 1, z 2, ..., zt, u kojem za svaki broj j, j = 1, ..., t, važi da 1) ili zj = xi; 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 kao linearni program. Obrnuto, svaki linearni program može biti predstavljen u obliku nekog SFE.
17 CFE i linearni programi Primjer 5. CFE 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 Šeme funkcionalnih elemenata su računski model. Karakteristike CFE-a koje smo uveli pokazuju različite aspekte računske efikasnosti. Složenost CFE odgovara vremenu sekvencijalnog izračunavanja. Dubina CFE odgovara vremenu paralelnog izračunavanja. Maksimalan broj vrhova sa istom dubinom u SFE odgovara broju procesora u paralelnom izračunavanju.
19 Primjer: zbir dva bita Primjer 6. Konstruirajte SPE na standardnoj bazi koja implementira (izračunava) zbir dva bita x i y. Rješenje. Napišimo tabelu zbira dva bita x i y. Ovaj zbir može biti broj sa dvije binarne cifre, pa uvodimo dvije Bulove varijable z 0, z 1, tako da je x + y = 2z 1 + z 0: x y z 1 z
20 Primjer: zbir 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), dobijamo SPE: Jasno je da je L (S 1) = 3, a D (S 1) = 3.
21 SFE u proizvoljnoj osnovi Koncept SFE u proizvoljnoj bazi B P 2 uvodi se na sličan način.
22 Primjer: zbir tri bita Primjer 7. Konstruirajte CFE u bazi P2 2 (odnosno iz svih Bulovih funkcija u zavisnosti od dvije varijable), realizirajući (izračunavajući) zbir tri bita x, y i z.
23 Primjer: zbir tri bita Rješenje. Slično kao u primjeru 6, pišemo tablicu zbira tri bita x, y i z. Ovaj zbir može biti i broj sa dvije binarne cifre, pa uvodimo dvije Bulove varijable u 0, u 1, tako da je x + y + z = 2u 1 + u 0: x y z u 1 u
24 Primjer: zbir 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), dobijamo CFE: Vidimo da je L (S) = 5, a D (S) = 3.
25 Implementacija Bulove funkcije CFE Da li je moguće implementirati proizvoljnu Booleovu funkciju (ili sistem Bulovih funkcija) u bazi B 0 = (x & y, x y, x)? Može. Kako se to može opravdati? Na primjer, ovako. Jer (x & y, x y, x) je kompletan sistem u P 2, proizvoljna Bulova funkcija f može biti predstavljena formulom samo kroz konjunkciju, disjunkciju i negaciju. 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 ovu DNF (formulu), konstruirajte odgovarajući SFE. Ova metoda konstruisanja CFE-a za Bulove funkcije naziva se metoda DNF sinteze.
26 Sinteza SFE-ova iz DNF-a I koja je složenost dobivena iz SFE-a S iz DNF-a za Booleovu funkciju f (x 1, ..., x n), ovisno o n varijabli? Savršen DNF za funkciju f će sadržavati najviše 2 n elementarne konjunkcije. Svaka elementarna konjunkcija je konjunkcija n varijabli ili njihovih negacija.
27 Sinteza SFE prema DNF-u Dakle, kolo će sadržavati: n pretvarača za implementaciju svih negacija varijabli x 1, ..., x n; pomoću (n 1) konjuktora za implementaciju svake od najviše 2 n elementarnih konjunkcija u savršenom DNF; najviše (2 n 1) disjunktori za implementaciju disjunkcije elementarnih konjunkcija DNF-a. Dobijamo da je L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Složenost Bulove funkcije Složenost L (f) Bulove funkcije f (x 1, ..., x n) u klasi CFE je minimalna složenost među svim CFE-ovima koji implementiraju funkciju f. Dakle, dokazali smo teorem: Teorem 1. Za proizvoljnu funkciju f (x 1, ..., x n) P 2, L (f) n 2 n + n je tačno.
29 Zadaci za nezavisno rješenje 1. Za Bulovu funkciju f (x 1, x 2, x 3) = (), konstruirajte SPE u standardnoj bazi složenosti. Za Booleovu funkciju f (x 1, x 2, x 3 ) = (), konstruirajte SPE 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 CFE u standardnoj bazi dubine Dokazati da je u standardnoj bazi L (xy) = 4.
30 Literatura za predavanje 4 1. Yablonskiy S.V. Uvod u diskretnu matematiku. M.: Viša škola, dio V, gl. 2, sa Gavrilov G.P., Sapozhenko A.A. Zadaci i vježbe iz diskretne matematike. Moskva: Fizmatlit, Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
31 Kraj predavanja 4
Predavanje: Šeme funkcionalnih elemenata sa kašnjenjem (SPEZ), automatizam preslikavanja koje oni vrše. Zastupstvo KAV SFEZ. Pojednostavljenja KAV-a. Različitost i nerazlučivost CAV stanja. Moorova teorema
Predavanje: Anselova teorema o podjeli n-dimenzionalne kocke na lance. Teorema o broju monotonih funkcija u algebri logike. Teorema o dekodiranju monotonih funkcija algebre logike. Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Konačne mašine sa izlazom (KAV). Automatske funkcije, metode njihovog dodjeljivanja. Teorema o transformaciji periodičnih nizova automatskim funkcijama. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva
Predavanje: Djelomično uređeni skupovi (PNS). CHUM dijagram. Maksimalni, minimalni, najveći i najmanji artikli. Lanci i antilanci, dužina i širina konačnog PLS-a. Teorema o dekompoziciji PN na antilančeve.
Predavanje 2. Osobine binomnih koeficijenata. Izračunavanje suma i metoda generisanja funkcija (konačni slučaj). Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Zbroj procjena
Predavanje: Algoritam za prepoznavanje kompletnosti u P k. Zatvorena nastava. Klase funkcija koje čuvaju skupove i čuvaju particije, njihovu zatvorenost. Kuznjecovljev teorem o funkcionalnoj potpunosti. Predzavršena nastava.
Predavanje 2. Kombinatorika. Svojstva binomnih koeficijenata. Izračunavanje suma i metoda generiranja funkcija. Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Asymptotic
Predavanje: Konačne funkcije. Elementarne k-vrijedne funkcije. Metode za specifikaciju k-vrijednih funkcija: tabele, formule, 1. i 2. oblici, polinomi. Kompletnost. Teorema o potpunosti Post sistema. Webb funkcija.
Predavanje 3. Sekvence definirane rekurentnim relacijama. Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Opšta rješenja LORU i LNRU. Predavač - vanredni profesor Svetlana Selezneva
Predavanje 15. Funkcije logike konačnih vrijednosti. Elementarne funkcije k-vrijedne logike. Metode za specifikaciju k-vrijednih logičkih funkcija: tabele, formule, I i II oblici, polinomi. Kompletnost. Predavač - vanredni profesor Selezneva
Predavanje: Funkcije logike konačnih vrijednosti. Elementarne funkcije k-vrijedne logike. Metode za specifikaciju k-vrijednih logičkih funkcija: tabele, formule, I i II oblici, polinomi. Kompletnost. Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Möbiusova funkcija na PLM-u. Möbiusova funkcija na n-dimenzionalnoj kocki. Mobiusova formula za inverziju. Princip uključivanja-isključivanja. Problem izračunavanja broja permutacija-poremećaja. Predavač - vanredni profesor Svetlana Selezneva
Predavanje 2. Osobine binomnih koeficijenata. Metoda generisanja funkcija, izračunavanje suma i dokaz identiteta. Polinomski koeficijenti. Princip uključivanja-isključivanja. Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Osnovne funkcije. Tri leme o bitnim funkcijama. Jablonskijev kriterijum potpunosti. Slupeckijev kriterij potpunosti. Schefferove funkcije. Predavač vanredni profesor Svetlana Nikolaevna Selezneva [email protected]
Predavanje: Osnovni kombinatorni brojevi. Procjene i asimptotika kombinatornih brojeva. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva, Fakultet računarske matematike i kibernetike, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su
Predavanje: Osobine binomnih koeficijenata. Izračunavanje suma i metoda generisanja funkcija (konačni slučaj). Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Procjene za sume binoma
Predavanje: Konačne mašine sa izlazom. Transformacija periodičnih nizova pomoću konačnih mašina sa izlazom. Različitost stanja u mašinama konačnih stanja sa izlazom. Pojednostavljivanje mašina. Predavač Selezneva
Predavanje: Pokrivanje skupova i pokrivanje matrice. Gradijentni premaz. Gradient Cover Lema. Procjene kardinalnosti skupa sjenčanja n-dimenzionalne kocke. Procjene dužine polinomskih normalnih oblika funkcija
Predavanje 5. Pokrivanje skupa i pokrivanje matrice. Gradijentni premaz. Gradient Cover Lema. Procjene kardinalnosti skupa sjenčanja Booleove kocke. Granice dužine za normalne forme Boolean polinoma
Predavanje 3. Sekvence definirane rekurentnim relacijama. Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Opšta rješenja LORU i LNRU. Primjeri Predavač - vanredni profesor Selezneva
Predavanje 3. Relacije na skupovima. Svojstva. Formula za uključivanje-isključivanje. Relacija ekvivalencije. Parcijalni odnos poretka. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima.
Predavanje 4. Osobine viševrijednih logika. Zatvorena klasa, zatvorena klasa. Teoreme Yanova i Muchnika o postojanju zatvorenih klasa bez osnove i zatvorenih klasa sa prebrojivim u viševrijednim logikama
Predavanje. Funkcije prirodnog argumenta (sekvence). Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Opšta rješenja LORU i LNRU. Primeri Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Hromatski broj grafa. Kriterijum za dvobojni graf. Teoreme o gornjim i donjim granicama za kromatski broj grafa. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima.
Predavanje: Grafovi i mreže. Procjena broja pseudografa sa q ivicama. Procjena za broj stabala sa q rubovima. Planarni grafovi. Ojlerova formula za planarne grafove. Najveći broj ivica u planarnim grafovima. Neplanarnost
Predavanje 1. Kombinatorika. Položaji, permutacije, plasmani s ponavljanjima, kombinacije, kombinacije s ponavljanjima. Njihov broj. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Katedra za matematičku kibernetiku
Predavanje: Sekvence. Homogene i nehomogene linearne rekurentne jednadžbe. Opća rješenja linearnih rekurentnih homogenih i nehomogenih jednačina. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva
Predavanje 8. Bojanje. Ekvivalencija boja u odnosu na grupu. Produktivne funkcije. Niz nabrajanja za oblike i niz nabrajanja za funkcije. Polyin teorem. Predavač Selezneva Svetlana Nikolaevna
Predavanje: Bojanje. Ekvivalencija boja u odnosu na grupu permutacija. Polyin teorem (poseban slučaj). Produktivne funkcije. Niz nabrajanja za oblike i niz nabrajanja za funkcije. Teorema
Predavanje 2. Konjunktivni normalni oblici. Implikentna, jednostavna implikacija funkcije. Skraćena CNF funkcija algebre logike. Metode za izradu skraćenog CNF-a. Predavač Selezneva Svetlana Nikolaevna [email protected]
Matematički modeli i metode logičke sinteze VLSI jesen 2015. Predavanje 4 Plan predavanja Logička optimizacija kombinacionih logičkih kola Različiti načini predstavljanja funkcija logičke algebre (FAL)
Predavanje: Nedeterministički konačni automati (NFA) bez izlaza. Teorema o podudarnosti klasa skupova riječi koje priznaju konačni deterministički i konačni nedeterministički automati. Procedura
Predavanje 1. Uzorci. Položaji, permutacije, plasmani sa ponavljanjima, kombinacije, kombinacije sa ponavljanjima, njihov broj. Primjeri. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja na predmetu Diskretno
Predavanje 1. Kombinatorski objekti: odabiri, rasporedi, permutacije, rasporedi s ponavljanjima, kombinacije, kombinacije s ponavljanjima, njihov broj. Kombinatorni brojevi: faktorijalni, opadajući faktorijal, binom
PREDAVANJE 4 ŠEME IZ FUNKCIONALNIH ELEMENTA 1. Osnovne definicije Prije svega, potrebno je razmotriti sastav. Funkcija se može zamisliti kao "crna kutija" koja ima ulaz i izlaz. Neka bude
Predavanje 2. Algoritam za prepoznavanje kompletnosti u P k. Kuznjecovljev teorem. Zatvorena nastava. Klase funkcija koje čuvaju skup. Klase funkcija očuvanja split-a. Predzavršena nastava. Predavač Doktor fizičko-matematičkih nauka Selezneva
Predavanje 3. Žegalkinov polinom. Metode za konstruisanje polinoma Žegalkina za funkciju. Linearna implikacija funkcije. Linearna konjunktivna normalna forma (LCNF). Pronalaženje svih linearnih implikacija funkcije. Ispitivanje
Predavanje 2. Generirajuće funkcije: izračunavanje kombinatornih suma i dokazivanje identiteta, nabrajanje kombinatornih objekata. Princip uključivanja-isključivanja. Brojanje broja permutacija-poremećaja. Predavač -
Predavanje 5. Grafovi. Bojanje grafikona. Hromatski broj grafa. Kriterijum za dvobojni graf. Gornje granice za hromatski broj grafa. Predavač Doktor fizičko-matematičkih nauka Selezneva Svetlana Nikolaevna [email protected] Predavanja
Predavanje: Konačni automati (KA) bez izlaza (prepoznavači konačnih automata). Dijagrami prijelaza. Setovi automata (jezici). Lema o svojstvima automatskih skupova. Primjer neautomatskog seta. Predavač
Predavanje 1. Konačne funkcije. Elementarne k-vrijedne funkcije. Metode za specifikaciju k-vrijednih funkcija: tabele, formule, 1. i 2. oblici, polinomi. Kompletnost. Teorema o potpunosti Post sistema. Webb funkcija.
Predavanje 7. Problem izbora ruta i njegov poseban slučaj je problem raspodjele letova po danu. Grafički model za problem distribucije leta. Hromatski broj grafa. Kriterijum za dvobojnost grafa.
Kurs "Osnove kibernetike" za studente specijalizacije 01.02.01 (matematika i softver za računare) 1. Opšte informacije (nastavno opterećenje, oblici upravljanja i dr.). Kurs je
Predavanje 6. Grafovi. Naslijeđena svojstva grafova. Procjena broja rubova u grafovima s nasljednim svojstvom. Ekstremni grafovi. Najveći broj ivica u ravnim grafovima i grafovima bez trougla sa datim
Math-Net.Ru sve-ruski matematički portal D. S. Romanov, Metoda za sintezu lako testiranih kola koja dozvoljavaju jednokratne provjere konstantne dužine, Diskr. Mat., 2014, Svezak 26, Broj 2,
Predavanje: Konačne mašine bez izlaza, determinističke i nedeterminističke. Teorema o podudarnosti klasa skupova riječi koje priznaju konačni deterministički i nedeterministički automati. Procedura
Praktični rad 2 Konstrukcija normalnih oblika logičke funkcije Svrha rada: Naučiti graditi konjunktivne, disjunktivne, perfektne normalne oblike logičke funkcije Sadržaj rada: Osnovni
Seminar o složenosti Bulovih funkcija Predavanje 1: Uvod A. Kulikov Klub informatike u POMI http://compsciclub.ru 25.09.2011. 25.09.2011. 1/26 Plan predavanja 1 Bulove funkcije 2 Bulova kola 3 Gotovo
Praktični rad 1 Analiza i sinteza logičkih i relejnih upravljačkih sistema UVOD Uređaji diskretnog djelovanja izrađeni na elementima hidro-, pneumo- i elektroautomatike i upravljački mikroprocesori
Predavanje: Regularni izrazi i regularni skupovi. Kleeneova teorema o podudarnosti klasa automatskih skupova i regularnih skupova. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnoj matematici
Predavanje 3 Bulove algebre i Bulove funkcije Bulove algebre Pojam algebarskih sistema Algebarski sistem ili algebarska struktura skup simbola određene abecede (podrška) sa datim
Predavanje 5. Grafovi. Primjeri primjene grafova. Problem sa transportom. Mrežni tok, Fordova i Fulkersonova teorema o maksimalnom protoku mreže. Algoritam za konstruisanje maksimalnog protoka u mreži. Predavač
Predavanje: Grafovi. Primjeri primjene grafova. Problem sa transportom. Mrežni tok, Fordova i Fulkersonova teorema o maksimalnom protoku mreže. Algoritam za konstruisanje maksimalnog protoka u mreži. Predavač -
Lekcija 8 Podsjetimo da za proizvoljne skupove A i B postoje skupovi A B = (x x A i x B); (presecanje 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. Ramsey brojevi. Gornja granica za Ramsey broj. Donja granica za Ramsey broj. Predavač Selezneva Svetlana Nikolaevna [email protected] Fakultet CMC, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.ru
Predavanje: Grafovi. Osnovni koncepti. Povezani grafovi. Drveće. Spanning tree. Broj visećih vrhova u razapinjućem stablu. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima. majstore,
Predavanje 11. Bulove šeme. Diskretna matematika, HSE, Fakultet računarskih nauka (jesen 2014. proljeće 2015.) Pod Booleovim krugom u varijablama x 1, ..., x n podrazumijevamo niz Bulovih funkcija g
ODOBRENO Prorektor za nastavu Yu. A. Samarskiy 10.06.2008. PROGRAM I ZADACI za predmet DISKREtne strukture na smeru 010600 Fakultet FIET Katedra za analizu podataka Kurs II semestar 4 Dva
Lomonosov Moskovski državni univerzitet Fakultet računarske matematike i kibernetike S. A. Lozhkin ELEMENTI TEORIJE SINTEZE SISTEMA DISKRETNOG UPRAVLJANJA Moskva 2016 Sadržaj
Predavanje: Naslijeđene osobine grafova. Ekstremni grafovi. Ramsey brojevi. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva, Fakultet računarske matematike i kibernetike, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su Hereditary
Predavanje: Operacije nad skupovima konačnih automata. Komplement, unija, presek, proizvod i iteracija skupova automata, njihova automatizacija. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja
Ministarstvo Ruske Federacije za komunikacije i informatizaciju Povolška državna akademija za telekomunikacije i informatiku Katedra za višu matematiku Odobreno od strane Metodičkog vijeća PSATI 29. marta 2002.
Predavanje 5. Bojenje ivica grafa. Hromatski indeks grafa. Kromatski indeks bipartitnih grafova. Gornje i donje granice za hromatski indeks grafa. Predavač Selezneva Svetlana Nikolaevna [email protected]
Math-Net.Ru Sveruski matematički portal NP Red'kin, O krugovima koji dozvoljavaju kratke pojedinačne dijagnostičke testove, Diskr. Mat., 1989, svezak 1, broj 3, 71 76 Upotreba sveruskog
MATEMATIČKA LOGIKA (1) Zadaci za praktične vježbe 1. Algebra iskaza Tvrdnja je veličina koja može imati dva značenja: istinito i netačno. Izgovori su naznačeni velikom latinicom
Funkcionalni dijagrami (FS) su dizajnirani da transformišu logičke informacije. Početne informacije, kodirane u obliku diskretnih signala, unose se na ulaze kola `x n... Zatim se ova informacija obrađuje i u diskretnom obliku čita sa izlaza kola `na m(n, m- broj njegovih ulaza i izlaza). Razmotrimo FS koji rade u dvovrijednoj logici i imaju jedan izlaz ( m= 1). Transformacija informacija u njima može se odrediti kao funkcija algebre logike at=f(x n). Umjesto relejnih elemenata u FS se koriste funkcionalni elementi (FE) koji po pravilu implementiraju elementarne logičke funkcije.
Definicija.Analiza naziva se konstrukcija formule za algebru logike (ako je potrebno, njene tablice istinitosti) za dati FS.
Za konstruisanje formule prema datoj šemi potrebno je odnos između FE u FS prikazati u obliku supstitucija u odgovarajućim elementarnim funkcijama. Pretpostavlja se da se obrada informacija odvija u fazama od ulaza do izlaza. U stvarnim kolima, dodatni elementi se koriste kako bi se osigurala vremenska koordinacija rada svih FS.
FS analiza se može izvesti na dva načina - od ulaza do izlaza i od izlaza do ulaza. Razmotrimo prvu metodu, koristeći dodatne oznake za veze međukruga.
Primjer 1.(&, Ú, Ø) se uzimaju kao FE Analizirajte FE čija je fizička struktura data na slici 1.19.
Rješenje. Nakon što smo označili međuveze PV-a kao što je prikazano na slici, korak po korak određujemo signale koji im odgovaraju . U ovom slučaju prelazimo sa ulaza kola na njegov izlaz.
Slika 1.19
KORAK 1. R=`y, Q = `z.
KORAK 2. X=x&R= x&`y, P=x& y, W=P&Q= x&y&`z.
KORAK 3. Y=X&z=x&`y& z, U=P&z = x&y&z.
KORAK 4. Z = YÚ U=x&`y&zÚ x&y&z.
KORAK 5. F = ZÚ W=x&`y& zÚ x&y&zÚ x&y&`z.
Dakle, razmatrani FS implementira sljedeću formulu algebre logike:
F(x,y,z) = x&`y&zÚ x&y&zÚ x&y&`z.
Pronađena formula je SDNF. Vektor njegovih istinitih vrijednosti ima oblik (00000111) .
Ovisno o početnim podacima, među zadacima sinteze (dizajna) FS-a mogu se razlikovati:
1) sinteza kola prema datim formulama,
2) sinteza kola za date funkcije.
Definicija.Sintezom PS prema datoj formuli naziva se konstrukcija FS strukture koja odgovara datoj formuli algebre logike.
Rješavanje ovakvih problema izvodi se prema algoritmu inverznom metodi analize. Kao što je navedeno u Odjeljku 1.7, struktura Bulovih formula dozvoljava samo sisteme sa paralelnim i sekvencijalnim vezama elemenata da se izomorfno preslikaju. Prema tome, FS, koji je izomorfan odgovarajućoj formuli, treba da sadrži samo jedinjenja ovog tipa.
Definicija.Sintezom PS-a za datu funkciju naziva se konstrukcija strukturnog dijagrama koji implementira datu funkciju algebre logike.
Budući da je predstavljanje funkcija formulama dvosmisleno, ovaj problem ima nejedinstveno rješenje. Kao iu slučaju relejnih kola, optimalni su FS, koji se sastoji od minimalnog broja PV-a i veza između njih. Takav FS se može dobiti korištenjem formula sa minimalnim brojem varijabli.
Što se tiče PC-a, posebno ćemo razmatrati formule koje su optimalne u klasi normalnih oblika (koje su jednake odgovarajućim minimalnim oblicima), kao i apsolutno optimalne formule dobijene iz minimalnih normalnih oblika njihovim daljnjim redukcijom korištenjem zakona logičke algebre . Metode za dobivanje optimalnih formula su iste kao u relejnim krugovima. Primjer 1 razmatra FS koji implementira funkciju (00000111) . Ovaj FS nije optimalan, jer odgovarajuća formula opisuje SDNF F = x`y z Ú x y zÚ x y`zšto nije minimalno. Minimizirajući ga, dobijamo MDNF sljedećeg oblika: F = x yÚ x z. Odgovara FS na slici 1.20.
Slika 1.20
Ako primijenimo distributivni zakon na MDNF, onda ćemo dobiti formulu sa još manje varijabli: f = x(yÚ z). Za ovu funkciju se poklopila sa MCNF-om. Apsolutno optimalna shema joj odgovara.
Slika 1.21
Očigledno, ova shema je mnogo jednostavnija od originalne (slika 1.19). Kako se sinteza optimalnog FS svodi na konstrukciju minimalnih formula, na sličan način se konstruišu i optimalne šeme u drugim bazama. Analogi prvog i drugog distributivnog zakona algebre logike za Schefferove i Web forme mogu se dobiti zamjenom u ovim zakonima:
&(x,y)= Ø ½ ( x,y) = ¯ (Ø x,Ø y);
Ú ( x,y)= ½ (Ø x, Ø y) =Ø ¯ ( x,y).
Primjer 2. Konstruirajte FS koji implementira jednobitni binarni sabirač dva broja koristeći FE koji odgovara bazi (Ø, ¯), kao i bazi (¯).
Rješenje. Označimo jednobitne binarne brojeve koji se unose na ulaz preko ( NS,at). Izlaz bi trebao biti njihov zbir u binarnom sistemu. Ako x = 1, y = 1, zatim S = 2 10 = 10 2, dakle, za njegovo prikazivanje, u opštem slučaju, potrebno je koristiti dva binarna znaka, a FS mora imati dva izlaza. Označimo ih f(najznačajnija znamenka zbira) i g(najmanji značajan bit). Funkcionalne tablice istinitosti f (NS,at),g(NS,at):
| x | y | f(x,y) | g(x,y) |
Konstruišemo SVNF funkcija u bazi (Ø, ¯). f ima jednu jedinicu u vektoru istine, stoga se njegov oblik sastoji od jednog konstituenta: f= ¯ (Ø x, Ø at). Funkcija g SVNF ima oblik: g=د(¯( NS,Ø at),¯(Ø NS,at)). Ovi oblici su minimalni. Kada se kombinuju ulazi elemenata, funkcionalni dijagram se može predstaviti na sledeći način:
Slika 1.22
U razmatranom primjeru nemoguće je pojednostaviti Web normalne forme koristeći zakone logičke algebre. U bazi s jednom funkcijom (¯) FS dobijamo, koristeći supstituciju Ø NS= ¯ ( NS,NS). Odgovarajuće kolo je prikazano na slici 1.23.
Slika 1.23
ZADACI
1. Konstruirajte koristeći FE (&, Ú, Ø) optimalno u klasi normalnih oblika i apsolutno optimalno FS koji implementiraju sljedeće funkcije:
a) ( x® y)Å zy b) ( xÅ y)|z,v) xy® yz;G) x|(yÚ z); e) x®( y® z) ;
f) (10011101); g) (01101011); h) (1110101111111110) .
2. Konstruirajte koristeći FE (Ú, Ø) FS funkcije 1.a) -g).
3. Konstruirajte koristeći FE (&, Ø) FS funkcije 1.a) -g).
4. Konstruirajte FS koji implementira jednobitni binarni sabirač (Primjer 2) koristeći FE sljedećeg oblika:
a) (&, Ú, Ø), b) (Ú, Ø) , c) (&, Ø), d) ( x | y} .
5. Uz pomoć FE (&, Ú, Ø), konstruirajte FS sljedećih uređaja:
a) pretvarač sa binarnim ulazima ( NS,at), i izađite f koji funkcioniše ovako: prilikom hranjenja x = 0 na izlazu f =at, i prilikom serviranja x = 1 na ulazu f =`y;
b) selektivni uređaj sa binarnim ulazima ( NS,at) i izlazi f 0 , f 1 , f 2 , f 3, koji na ulazu prihvata kombinaciju vrijednosti ( x y) kao binarni broj i, koji se nalazi u rasponu od 0 do 3. Vrijednosti izlaza za svaki i sljedeće: f i= 1, i svi ostali f j= 0, (0 £ j£ 3, j¹ i).
6. Da li je moguće uzeti sljedeće skupove funkcija kao osnovu za konstruiranje FS:
a) (1001), (10001110),
b) (0101), (1011), (1101),
c) (1010), (01110001)?
Obrazložite odgovor.
7. Navedite primjere upravljačkih funkcija čiji se FS ne može konstruirati samo od FE tipa (®).
8. Navedite primjere upravljačkih funkcija čiji se FS ne može konstruirati samo od FE tipa (M, º).
9. Dana FS iz FE (&, Ú, Ø).
Slika 1.24
Da li je moguće isključiti iz njega ekvivalentnim konverzijama:
a) svi elementi (Ø)?
b) svi elementi (&)?
c) svi elementi (Ú)?
10. Optimizirajte FS iz FE (&, Ú, Ø), prikazanog na slici 1.25.
Slika 1.25
Izgradnja FS:
a) optimalno u klasi normalnih oblika i
b) apsolutno optimalno.
31. Dijagrami funkcionalnih elemenata, pravila konstrukcije i funkcionisanja, metoda sinteze SFE, zasnovana na SDNF i SKNF.
DefinicijaDefinicija. Funkcionalni element je matematički model elementarnog diskretnog pretvarača, koji, prema određenom zakonu, pretvara signale koji mu dolaze na ulazu u signal na izlazu pretvarača. Od funkcionalnih elemenata, uz pomoć nekih pravila, moguće je graditi modele složenije strukture i funkcionisanja - dijagrame od funkcionalnih elemenata. U ovim modelima, ulazni i izlazni signali su kodirani znakovima 0 i 1.
Pravila izgradnje. Za dobivanje složenih SFE-ova od jednostavnijih, sekvencijalno se primjenjuju operacije razdvajanja ulaza ili izlaza kola, povezivanja funkcionalnog elementa u kolo i povezivanja funkcionalnog elementa na ulaz ili izlaz kola. Ove operacije liče na pravila za dobivanje složene formule od jednostavnijih korištenjem superpozicije.
Sinteza SFE. Pošto disjunkcija, konjunkcija i negacija čine kompletan sistem u klasi R 2, zatim bilo koju Booleovu funkciju od n argumenti se mogu implementirati pomoću kola funkcionalnih elemenata - disjunktori, konjuktori i invertori - sa n ulaza i jednog izlaza. Da biste to učinili, možete, na primjer, izraziti ovu Booleovu funkciju kroz SDNF ili SKNF, a zatim "sintetizirati" rezultirajuću formulu u obliku kola funkcionalnih elemenata, uzastopno primjenjujući gore navedene operacije razdvajanja, spajanja i povezivanja.
32. Metoda sinteze SFE, zasnovana na kompaktnoj implementaciji svih konjunkcija pomoću univerzalnog multipola, složenost rezultirajućih kola.
Definicija... Funkcija argumenta naziva se Boolean funkcija (ili Boolean funkcija) ako svakom skupu dodjeljuje broj.
Za definiranje Booleovih funkcija koristit ćemo tabele, vektore, formule i grafikone. Uzmimo sljedeću notaciju: je skup svih skupova, gdje.
Definicija. Funkcionalni element je matematički model elementarnog diskretnog pretvarača, koji, prema određenom zakonu, pretvara signale koji mu dolaze na ulazu u signal na izlazu pretvarača. Od funkcionalnih elemenata, uz pomoć nekih pravila, moguće je graditi modele složenije strukture i funkcionisanja - dijagrame od funkcionalnih elemenata. U ovim modelima, ulazni i izlazni signali su kodirani znakovima 0 i 1.
Metoda za sintezu SFE, zasnovana na kompaktnoj implementaciji svih konjunkcija pomoću univerzalnog multipola. Ova metoda se također temelji na predstavljanju funkcije u obliku SDNF-a, ali omogućava izgradnju manje složenih kola zbog kompaktnije implementacije konjunkcija. Dekompozicija funkcije u SDNF-u može sadržavati konjunkcije koje imaju zajedničke faktore. Ako se dvije takve konjunkcije implementiraju s jednim potkolom u bloku, onda će to zahtijevati najmanje jedan konjunktor manje nego što je bilo potrebno prije, uz nezavisnu implementaciju svih konjunkcija prvom metodom sinteze. Kompaktna implementacija svih mogućih konjukcija dužina n može se postići korištenjem induktivno izgrađenog univerzalnog multipola, koji ima n ulazi i 2 n izlazi gdje n = 1,2,3, ... Prednosti metode su posebno uočljive kada jedno kolo treba da implementira sistem od nekoliko Bulovih funkcija. U ovom slučaju bilo bi moguće podijeliti i zatim kroz disjunktore proći one izlaze univerzalnog multipola koji odgovaraju konjunkcijama uključenim u SDNF funkcija datog sistema. Ovo bi omogućilo da se prođe sa manje konjuktora nego da je svaka funkcija datog sistema nezavisno implementirana od strane sopstvenog podkola.
Složenost takvog multipola je L() =.
Ako kolo kapija Σ sadrži tačno r funkcionalnih elemenata, onda kažu da ima složenost r i zapišite to u obliku jednakosti L(Σ) = r.
| " |
