Reprezentaciji Booleovih funkcija formulama može se dati sljedeće "inženjersko-konstruktivno" značenje. Formulu F(x 1 ,..., xn) nad nekim proizvoljno fiksnim skupom F smatrat ćemo "crnom kutijom", svojevrsnim uređajem koji na ulaz prima sve moguće skupove varijabilnih vrijednosti, a vrijednosti funkcije f koja odgovara tim skupovima pojavljuju se na izlazu, predstavljene formulom F (slika 6.22).
Da bismo razumjeli kako funkcionira "crna kutija", moramo analizirati proces izgradnje formule iz podformula. Dolazak do "osnovnih" podformula, t.j. elemenata skupa F, dolazimo do "cigli", strukturnih elemenata od kojih se sastavlja "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 njezina se unutarnja struktura više ne analizira.
Primjer 6.22. Odaberimo standardnu bazu kao skup F. Tada se formula nad standardnom bazom koja predstavlja funkciju ~ (ekvivalentnost) konstruira na sljedeći način:
Izračun po 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 (točnije, vrijednost ove varijable) se dovodi na ulaz konstrukcijskog elementa koji se naziva inverter (slika 6.24, a) i izračunava negaciju. Negacija x 1 uklonjena s izlaza pretvarača, t.j. funkcija x 1, dovodi se na jedan od ulaza spojnika (slika 6.24, b), čiji se drugi ulaz opskrbljuje varijablom x 2. Na izlazu spojnika pojavljuje se funkcija x 1 x 2. Slično se prati izračun funkcije x 1 x 2. Obje ove funkcije se unose na ulaze disjunktora (slika 6.24, c), iz čijeg se izlaza dobiva funkcija x 1 x 2 ∨ x 1 x 2 je uklonjen (ovo nije ništa drugo do zbroj po modulu 2: x 1 ⊕ x 2). I konačno, ova funkcija se dovodi na ulaz pretvarača, na čijem se izlazu već dobiva funkcija ~ (ekvivalentnost). #
Tako dolazimo do ideje "sheme" - matematičkog modela kalkulatora Booleove funkcije, predstavljenog nekom formulom, sastavljenom 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 posebna vrsta usmjerenog grafa u kojem su i vrhovi i lukovi opremljeni nekim oznakama.
Uvedemo oznaku: ako je F neki skup Booleovih funkcija, tada s 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).
Shema funkcionalnih elemenata na bazi F ∪ X (S F É), ili jednostavno kontrakcija preko baze F ∪ X, također (F,X)-shema, naziva se bezkonturno orijentirani graf (tj. mreža), čiji je svaki vrh označen s jedan od elemenata skupa FU X kako slijedi da su ispunjeni sljedeći zahtjevi:
- svaki ulaz mreže označen je 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 in-stupanj n, a na skupu lukova koji ulaze u vrh v, postoji ( jedan prema jedan) numeriranje tako da svaki luk dobije broj od 1 do n.
Ako se osnova podrazumijeva, onda ćemo jednostavno reći "shema". Osim toga, ako je skup varijabli fiksiran "jednom zauvijek" i, kada se razmatraju različite sheme, mijenjamo samo skup funkcija F, tada, kao što smo to učinili prilikom uvođenja pojmova formule i superpozicije nad danom bazom, govorit ćemo o CFE-u preko baze F, postavljajući svaki put, što podrazumijeva jednom fiksni skup varijabli X, koji se (ako ne šteti točnosti) ne spominje.
Sada indukcijom definiramo pojam Booleova funkcija izračunata vrhom kruga .
Definicija 6.15. Neka se daje SFE S preko baze F ∪ X čiji je skup vrhova V.
- Pretpostavlja se da svaki SFE ulaz izračunava Booleovu funkciju s kojom je označen (tj. neka varijabla ili konstanta).
- Ako je vrh v ∈ V označen funkcijom f ∈ F (n) , a luk s 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 CFE vrh nad F izračunava neku funkciju, tada je redoslijed kojim su navedene funkcije g 1 , ..., g n, koje su supstituirane za varijable funkcije f, općenito značajan. Prirodno je nazvati Booleovu funkciju f od n varijabli komutativnom ako čuva svoju vrijednost pod proizvoljnom permutacijom svojih varijabli. U ovom slučaju, možda nas nije briga za numeriranje lukova koji ulaze u vrh kruga označen takvom funkcijom.
Primjer 6.23. Razmotrimo SFE na sl. 6.25. Vrhovi v 1 i v 2 su ulazi u SFE. Ovi vrhovi izračunavaju funkcije x i y. Tada vrh v 3 , kao i vrh v 4 , prema definiciji 6.15, izračunava funkciju x|y (Schaefferov potez), a vrh v 5 (mrežni izlaz) izračunava funkciju (x|y)l( x|y), za koje je poznato da je jednako konjunkciji x · y.
SFE prikazan na sl. 6.26, ima dva izlaza, računajući funkcije (x|x)|(y|y) = x ∨ y i (x|y)|(x|y) = x·y.
Definicija 6.16. Booleova funkcija koju izračunava SFE preko baze F ∪ X, je funkcija izračunata bilo kojim od njezinih izlaza.
Dakle, SFE izračunava točno stmko Booleove funkcije, koliko izlaza ima. 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 za ulaze u krug S preko baze F ∪ H, koja ima m izlaza, CFE S definira prikaz booleove kocke B n u booleovu kocku B m , tj. boolean operator.
Napomena 6.10. U nekim slučajevima, funkcija koju izračunava dani CFE definira se nešto drugačije, pod pretpostavkom da je to funkcija izračunata bilo kojim vrhom iz podskupa odabranih CFE vrhova. Konkretno, to mogu biti izlazi. U svakom slučaju, dogovorimo se da iz odabranih (u upravo naznačenom smislu) vrhova sheme nacrtamo "izlaznu" strelicu. #
Dakle, svaki sklop funkcionalnih elemenata izračunava neki Booleov operator, posebno ako je broj izlaza kruga 1, tada izračunava neku Booleovu funkciju.
Može se dokazati i obrnuto: za bilo koji Boolean operator, SFE se može konstruirati na bazi F, gdje je F potpuni skup koji vrednuje zadani operator.
Predstavimo funkciju y 1 u Zhegalkinovoj bazi. Koristeći de Morganove zakone, dobivamo
(sjetimo se da je zbroj po modulu 2 bilo kojeg parnog broja jednakih članova 0).
y 1 \u003d x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 \u003d x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE za Boolean operator naveden u tablici. 6.9, preko Zhegalkinove baze prikazano je na Sl. 6.27.
Prilikom projektiranja 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 inputi.
Prikazano na sl. 6.27 CFE preko baze Zhegalkin ima složenost 5.
Razmotrimo sada CFE za istog operatera preko standardne osnove.
Prema tablici (vidi tablicu 6.9), gradimo SDNF za funkciju y 2:
y 2 \u003d x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Carnotova 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 ići drugim putem. Možemo razmotriti tablicu. 6.9 kao tablicu koja definira djelomičnu Booleovu funkciju y 2 = y 2 (x 1 x 2 x 3 y 1). Minimiziranjem ove funkcije
Carnotova karta* prikazana na sl. 6.29, dobivamo
* Na ovoj karti smo označili skupove na kojima funkcija poprima vrijednost 0 stavljanjem nula u odgovarajuće ćelije. Stoga želimo još jednom skrenuti pozornost na činjenicu da nule ne treba brkati s crticama: crtica u ćeliji karte koja definira djelomičnu funkciju znači da vrijednost funkcije nije definirana na ovom skupu, t.j. nije ni 0 ni 1.
y 2 \u003d x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
SFE iznad standardne baze za razmatrani Boolean operator prikazan je na Sl. 6.30. Složenost ovog CFE-a je 11. Imajte na umu da čvor koji izračunava funkciju y 1 nije izlaz.
Booleov operator o kojem se raspravlja u ovom primjeru izračunava dvoznamenkasti zbroj (modulo 2) tri jednoznamenkasta člana. Također se može smatrati jednobitnim binarnim zbrajačem – funkcionalnim blokom višebitnog binarnog zbrajača – za dva pojma. Tada se funkcija y 1 tumači kao "prenosni signal" u visoki red. Na sl. Slika 6.31 prikazuje "vezu" tri CFE-a (kao što je prikazano na slici 6.30), koja izračunava zbroj dva troznamenkasta binarna broja. Konstanta 0 primjenjuje se na treći ulaz zbrojivača za najmanji bitni bit, a "prenosni signal" najznačajnijeg bita je najznačajniji bit zbroja, koji će u općem slučaju biti četveroznamenkasti broj .
Napomena 6.11. Ako projektiramo SFE na standardnoj bazi i želimo minimizirati njegovu složenost, tada prvo moramo 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 predznakom negacije. Sa stajališta složenosti CFE-a, koji će se graditi prema minimalnom DNF-u, to znači da minimizira broj "invertera" - CFE vrhova označenih funkcijom negacije.
Na primjer, za funkciju koju je dala Carnotova mapa (slika 6.32), jezgri koja se sastoji od jednostavnih implikanata x 1 x 2 x 4 i x 1 x 3 x 4, trebali biste dodati jednostavan implikant x 2 x 3 x 4 , a ne x 1 x 2 x 3 jer ne sadrži negacije.
U suvremenoj tehnologiji upravljačkih i računalnih uređaja važno mjesto zauzimaju diskretni pretvarači, odnosno uređaji koji imaju određeni broj ulaza i izlaza. Skupovi signala koji pristižu na ulaze i pojavljuju se na izlazima pripadaju poznatim konačnim skupovima.
Podijelite rad na društvenim mrežama
Ako vam ovaj rad ne odgovara, na dnu stranice nalazi se popis sličnih radova. Također možete koristiti gumb za pretraživanje
Aranov Viktor Pavlovič Diskretna matematika. Odjeljak 5. DNF i sheme iz FE.
Predavanje 28 Problemi analize i sinteze
Predavanje 28 SHEME IZ FUNKCIONALNIH ELEMENTA.
PROBLEMI ANALIZE I SINTEZE
Plan predavanja:
1. Pojam sklopa funkcionalnih elemenata(FE).
2. Problemi analize i sinteze sklopova iz FE.
- Koncept strujnog kruga iz FE
U suvremenoj tehnologiji upravljačkih i računalnih uređaja važno mjesto zauzimajudiskretni pretvarači, tj. uređaji koji imaju određeni broj ulaza i izlaza. Skupovi signala koji pristižu na ulaze i pojavljuju se na izlazima pripadaju poznatim konačnim skupovima. Uređaji pretvaraju skupove ulaznih signala u izlazne. Matematički model takvih uređaja su tzvsklopovi iz funkcionalnih elemenata(SFE).
Kao primjer, razmotrite električni krug od tri diode i otpora prikazan na Sl. jedan.
Riža. 1. Električni krug i njegov simbol
Na točkama kruga prikazanim krugom, u različito vrijeme, može se pojaviti ili visoka razina, približno jednaka 5 V, ili niska razina, približno jednaka nuli. Na točki kruga označenoj crticom održava se konstantno niska razina napona.
Označene točke će se tumačiti kao ulazi, a točka kao izlaz. Rad sklopa može se opisati na sljedeći način: ako svi ulazi imaju nisku razinu napona, tada je i izlaz nizak, ako barem jedan od ulaza ima visoku razinu napona, tada je izlaz visok. Ako stanje s visokom razinom napona označimo kao jedan, a s niskom razinom napona kao nulu, tada se ovisnost izlaza o ulazima može specificirati pomoću Booleove funkcije.
Na temelju toga, gornji sklop naziva se logički element "ILI".
Slični sklopovi mogu se izgraditi od vakuumskih cijevi, elektromehaničkih sklopki, pneumatskih elemenata itd. Ovisnost izlaza o ulazima može se opisati ne samo kao disjunkcija, već i uz pomoć konjunkcije, negacije i složenijih Booleovih funkcija.
Razmotrit ćemo logičke elemente s različitom ovisnošću izlaza o ulazima. Ovi elementi se mogu međusobno povezati napajanjem izlaza nekih elemenata na ulaze drugih. Kao rezultat, dobivamo SFE.
Definicija pojma SFE može se podijeliti u dvije faze. U prvoj fazi otkriva se strukturni dio ovog koncepta, u drugoj - funkcionalni.
ja pozornica. Podijelimo ovaj korak na nekoliko koraka.
1 . Postoji konačan skup objekata () tzvlogičke elemente.Svaki element ima ulaze i jedan izlaz. Element je grafički prikazan kao što je prikazano na sl. 2.
2 . Indukcijom definiramo pojam logička mreža kao objekt koji ima određen broj ulaza i određeni broj izlaza (slika 3).
a) Osnova indukcije. Izolirani vrh naziva se trivijalna logička mreža. Po definiciji je i ulaz i izlaz (slika 4.).
… …
…
Riža. 2 sl. 3 sl. 4
b) Induktivni prijelaz. Ovaj dio se temelji na korištenju tri operacije.
I . Operacija kombiniranja disjunktnih mreža. Neka i budu dvije mreže koje se ne sijeku (bez zajedničkih elemenata, ulaza i izlaza) koje imaju i ulaze i izlaze, respektivno. Teoretsko skupova unija mreža je logička mreža koja ima ulaze i izlaze.
II . Operacija pričvršćivanja elementa. Neka mreža i element budu takvi da se biraju različiti izlazi s brojevima. Tada se lik naziva logičkom mrežom, što je rezultat povezivanja elementa s mrežom. Ulazi su svi ulazi, izlazi su svi izlazi mreže, osim izlaza s brojevima, kao i izlaz elementa. Mreža ima ulaze i izlaze (slika 5.).
… …
Riža. 6.
Riža. pet
III . Operacija dijeljenja izlaza. Neka se u mreži odabere izlaz s brojem. Tada se figura naziva logičkom mrežom dobivenom dijeljenjem izlaza. Svi ulazi su ulazi, izlazi su svi izlazi mreže s brojevima 1, ..., ... i još dva izlaza koja proizlaze iz izlaza s brojem mreže (slika 6.). Stoga ima ulaze i izlaze.
3 . Neka se abecede i daju.
Dijagram funkcionalnih elemenatanaziva se logička mreža s ulazima iz abecede i izlazima iz abecede, što se označava
. (1)
Dajemo primjere shema.
1. Neka se skup sastoji od tri elementa AND (konjuktor), OR (dizjunktor) i NE (inverter).
Tada će slika (slika 6) biti dijagram, budući da se može izgraditi pomoću operacija I - III .
Riža. 6 sl. 7
2. Slika prikazana na sl. 7, također je dijagram.
II pozornica. Određivanje rada strujnog kruga.
4 . Usporedimo SFE (1) sa sustavom funkcija algebre logike
(2)
također zovevodljivost ovog kruga.
Primjer. a) Za strujni krug imamo sustav koji se sastoji od jedne jednadžbe
Ili.
b) Za shemu dobivamo slično
- Implementacija Booleovih funkcija pomoću FE sklopova. Problemi analize i sinteze
sheme iz PV
Zadatak analize: za dati SFE (1) dobiti sustav Booleovih jednadžbi (2).
Algoritam rješavanja zadatka: praćenje operacija izgradnje mreže I-III , sekvencijalno izračunavamo funkcije na izlazima elemenata mreže.
Zadatak sinteze: za zadanu bazu funkcionalnih elemenata i proizvoljni sustav Booleovih jednadžbi (2), konstruirati sklop (1) iz zadanih FE koji implementira ovaj sustav jednadžbi.
Postojanje rješenja problema sinteze određeno je Postovim teoremom prema kojem sustav funkcija koje implementiraju osnovni FE mora biti potpun. Funkcije se mogu predstaviti kao superpozicija funkcija, a svaki korak superpozicije odgovara određenoj kombinaciji elemenata.
Primjer. Za funkciju
(3)
Shema koja odgovara superpoziciji na desnoj strani formule (3) prikazana je na sl. 8.
Riža. 8
Problem sinteze leži u činjenici da je za dati sustav Booleovih jednadžbi moguće konstruirati mnogo sklopova iz FE koji implementiraju ovaj sustav. S tim u vezi javlja se problem optimalne sinteze: iz svih mogućih shema koje implementiraju zadanu funkciju, odaberite najbolju prema jednom ili drugom atributu, na primjer, s najmanjim brojem elemenata. Takve sheme će se zvati minimalno .
Točna je sljedeća tvrdnja.
Teorema. Postoji algoritam koji za svaki sustav Booleovih funkcija gradi minimalni sklop.
Ovaj algoritam za konstruiranje minimalnih sklopova pripada klasi algoritama tipa "brute force", budući da se temelji na pregledu svih sklopova do određene složenosti. Brute force algoritmi su, u pravilu, vrlo naporni i neprikladni za praktične svrhe. Stoga ćemo dalje razmatrati jednostavniji problem za koji izvorni sustav jednadžbi sadrži jednu jednadžbu
i, prema tome, željeni krug ima jedan izlaz.
Označite složenost minimalnog kruga sa . Problem sinteze nećemo razmatrati za jednu funkciju, već za cijelu klasu funkcija varijabli. Kvaliteta algoritama sinteze uspoređuje se usporedbom takozvanih Shannonovih funkcija. Neka bude
– minimalna složenost sklopova koji implementiraju, a koji se dobivaju pomoću algoritma.
Funkcije se nazivaju Shanonovim funkcijama i očito je da
Problem sinteze je pronaći algoritam za koji bi bio što bliži, a kako bi složenost algoritma bila znatno manja od složenosti algoritma iscrpnog pretraživanja. Uz takvu formulaciju problema nije potrebno da algoritam za svaku funkciju pronađe minimalni sklop, potrebno je samo da najjednostavniji sklop dobiven uz pomoć ima složenost koja ne prelazi mnogo.
Ostali povezani radovi koji bi vas mogli zanimati.vshm> |
|||
| 9013. | METODE SINTEZE SHEMA IZ FE. SHEME DEKODERA I BINARNOG ZBIRNIKA | 153,07 KB | |
| Opća teorija SFE sinteze dovodi do zaključka da većina Booleovih funkcija za velike vrijednosti ima složene minimalne sheme. To znači da je vrlo uska klasa Booleovih funkcija od praktične vrijednosti sa stajališta sinteze. | |||
| 5321. | Vrste i vrijednosti parametara automatske zaštite za različite elemente zadane sheme dizajna | 526,7 KB | |
| Za normalan rad elektroenergetskog sustava i potrošača električne energije potrebno je što prije identificirati i odvojiti mjesto oštećenja od neoštećene mreže, čime se uspostavljaju normalni uvjeti rada elektroenergetskog sustava i potrošača. | |||
| 5384. | Izrada električnog kruga postolja za analizu rada dekodera s taktom za 4 ulaza i 16 izlaza | 626,63 KB | |
| Za poboljšanje rada ATP željezničkih vozila razvijena je organizacijska struktura sustava održavanja i popravka za ATP željeznička vozila te je predložen set opreme za dijagnostiku i održavanje. Glavni cilj funkcioniranja pogona za popravak poduzeća je osigurati neprekidan rad opreme. Uključuje: popravnu i restauratorsku bazu poduzeća, skladišta, radionice i opće tvorničke odjele popravnih objekata, tehnološku opremu, dispečera. Organizacija... | |||
| 1886. | Faze analize sustava, njihovi glavni ciljevi, zadaci | 27,44 KB | |
| Teorija optimalnih sustava omogućuje nam da procijenimo granicu koja se može postići u optimalnom sustavu, usporediti je s pokazateljima postojećeg neoptimalnog sustava i utvrditi je li u razmatranom slučaju preporučljivo razvijati optimalni sustav. Za automatski kontrolirani proces automatski upravljanog sustava razlikuju se dvije faze optimizacije: statički i dinamički. Statička optimizacija rješava probleme kreiranja i implementacije optimalnog modela procesa, dok dinamička... | |||
| 5123. | Razvoj funkcionalnih strategija | 35,44 KB | |
| Strategija upravljanja osobljem. Funkcije i struktura upravljanja. Funkcije upravljanja i njihova uloga u formiranju upravljačkih struktura. Hijerarhijski tip strukture upravljanja. | |||
| 20368. | Utjecaj sastava komponenti i tehnologija na recept na potrošačka svojstva funkcionalnih proizvoda | 742,05 KB | |
| Moderna medicinska znanost usvojila je koncept optimalne prehrane. To znači da je napravljen prijelaz od koncepta adekvatne prehrane, kada su se uglavnom regulirali i normalizirali makronutrijenti - izvori masti, izvori energije, plastični materijali (lipidi, proteini, masti), na koncept optimalne prehrane, kada su raspon hranjivih tvari i drugih hranjivih tvari potrebnih za život sporednih komponenti tijela, na koje se prije nije obraćala pozornost, značajno je proširen. | |||
| 4706. | Metode za sintezu Me karboksilata | 9,26 MB | |
| Bit metode je otapanje metalnog oksida, hidroksida ili karbonata u vodenoj otopini odgovarajuće kiseline. Produkt se izolira isparavanjem otopine prije početka kristalizacije ili filtriranjem taloga ako je karboksilat netopiv ili slabo topiv u vodi. | |||
| 15923. | Osnovne metode za sintezu pirazalodiazepina | 263,39 KB | |
| Nove metode za sintezu derivata pirazolodiazepina. Razvoj novih strategija sinteze od velikog je interesa. Sustavna i generalizirajuća istraživanja sinteze derivata pirazolodiazepina nisu provedena, neka pitanja ostaju netaknuta, kontroverzna ili nisu u potpunosti razriješena. | |||
| 11978. | Instalacije energetske tehnologije temeljene na hidrotermalnoj oksidaciji aluminija za proizvodnju električne energije, topline, vodika i funkcionalnih nanomaterijala | 49,89 KB | |
| Razvoj se temelji na reakciji hidrotermalne oksidacije aluminija tijekom koje se oslobađa velika količina toplinske energije te nastaju aluminijevi oksidi i vodik: l2H2O→lOOH boehmite15H2415. Kao početni reagensi koriste se destilirana voda i mikronski aluminijski prah. KEU10 instalacija ETK100 instalacija Tehničke karakteristike instalacije ETK100: Parametar Vrijednost Potrošnja aluminija kg h 101 Potrošnja vode na ulazu u uređaj za obradu vode kg h 484 Kapacitet vodika nm3 110 Toplinska snaga ... | |||
| 6605. | Ekspertni sustavi. Projektiranje TP metodom sinteze | 11,67 KB | |
| Predstavljanje akumulacije znanja i njegovo ažuriranje složen je zadatak koji se istražuje u dijelu računalne znanosti koji se zove inženjering znanja. Inženjer znanja uključen je u razvoj baze znanja – jezgre sustava koji se naziva inteligentni. Najčešće se inteligentni sustavi koriste za rješavanje složenih problema gdje je glavna složenost rješenja ... | |||
Veličina: px
Započni pojavljivanje sa stranice:
prijepis
1 Predavanje 2. Sheme funkcionalnih elemenata (SFE) u nekoj bazi. Složenost i dubina sheme. Primjeri. Metoda za sintezu SFE pomoću DNF. Predavač - izvanredna profesorica Svetlana N. Selezneva Predavanja diskretna matematika 2. 1. godina, grupa 141 Lomonosov Predavanja na web stranici
2 Sklopovi iz funkcionalnih elemenata Definirajmo sklopove iz funkcionalnih elemenata u nekoj bazi. Neka nam je dat neki skup Booleovih funkcija B = (g 1 (x 1,..., x n1),..., gs (x 1,..., x ns)) P 2, gdje je n 1, .. ., ns 0. Taj skup nazivamo bazom. Imajte na umu da ovaj koncept baze ni na koji način nije povezan s konceptom baze P 2, koji je razmatran u algebri logike. U pravilu ćemo uzeti u obzir standardnu bazu B 0 = (x&y, x y, x).
3 Definicija sklopa funkcionalnih elemenata Krug funkcionalnih elemenata (SFE) u bazi B 0 = (x&y, xy, x) je 1) usmjereni aciklički graf G = (V, E), čiji je svaki vrh v V ima stupanj d (v) koji ne prelazi dva (d (v) 2); 2) svaki vrh v s in-stupnjem jednakim 0 (d (v) = 0) naziva se ulaz (ili ulaz kruga) i pripisuje mu se neka Booleova varijabla x i; 3) svi ostali vrhovi (osim ulaza) nazivaju se unutarnjim vrhovima kruga;
4 Definiranje sklopa iz funkcionalnih elemenata (nastavak) 4) svakom vrhu v s in-stupanj jednakim 1 (d (v) = 1) dodijeljen je (funkcionalni) element negacije; svi takvi vrhovi nazivaju se inverteri; 5) svakom vrhu v s in-stupanj jednakim 2 (d (v) = 2) dodijeljen je ili (funkcionalni) element konjunkcije & 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 strujnog kruga iz funkcionalnih elemenata (nastavak) 6) Osim toga, nekim od vrhova dodijeljene su parno različite izlazne varijable y 1,..., y m. Ako je zadan CFE S, čijim su ulazima dodijeljene samo varijable x 1,..., xn, a s izlaznim varijablama y 1,..., ym, tada ćemo ovaj CFE 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. U 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 CFE-a Složenost L(S) CFE-a S je broj unutarnjih vrhova ovog CFE-a, t.j. broj funkcionalnih elemenata u SFE S.
9 Složenost SPE Primjer 2. Složenost SPE S:
10 Određivanje dubine CFE vrha Indukcijom određujemo dubinu d(v) vrha v u CFE S. 1. Osnova indukcije. Svaki ulaz v SPS-a 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 konjunktora ili disjunktora v CFE S, tada je d (v) = max(d(v 1), d(v 2)) + 1. Dubina D(S) CFE S je najveća od dubina njegovih vrhova.
11 Dubina SPE Primjer 3. Dubina SPE vrha S i SPE dubina S:
12 Određivanje funkcioniranja SFE-a U svakom vrhu SFE-a implementirana je (ili izračunata) određena Booleova funkcija. Indukcijom definiramo Booleovu funkciju koja se implementira na vrhu v CFE S. 1) Ako je v ulazni vrh, a varijabla xi mu je dodijeljena, tada se funkcija fv = xi ostvaruje na vrhu v . 2) Ako luk iz vrha v 1 vodi do pretvarača v, a funkcija f v1 se ostvaruje na vrhu v 1, tada se funkcija f v = f v1 ostvaruje 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 implementiraju se na vrhovima v 1 i v 2, tada je funkcija fv = f v1 &f v2 (odnosno fv = f v1 f v2).
13 Funkcioniranje SFE Vjeruje se da SFE S(x 1,..., xn ; y 1,..., ym) implementira sustav Booleovih funkcija FS = (f 1,..., fm ) implementiran u svojim izlaznim vrhovima y 1,..., ym.
14 Funkcioniranje SFE Primjer 4. Booleove funkcije implementirane u vrhove 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,..., 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, 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 CFE i linearni programi Jasno je da se izračun u CFE može prepisati u obliku linearnog programa. I obrnuto, svaki linearni program može se predstaviti kao određeni CFE.
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 Sheme funkcionalnih elemenata su računski model. SPE karakteristike koje smo uveli pokazuju različite aspekte računalne učinkovitosti. Složenost SFE odgovara vremenu sekvencijalnog izračuna. Dubina SPE odgovara vremenu paralelnog računanja. Maksimalni broj vrhova s istom dubinom u CFE-u odgovara broju procesora u paralelnom računanju.
19 Primjer: zbroj dva bita Primjer 6. Konstruirajte SFE u standardnoj bazi koja implementira (izračunava) zbroj dva bita x i y. Riješenje. Napišimo tablicu zbroja dva bita x i y. Ovaj 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 CFE u proizvoljnoj bazi Slično, uvodi se koncept CFE u proizvoljnoj bazi B P 2.
22 Primjer: zbroj tri bita Primjer 7. Konstruirajte SFE u bazi P2 2 (tj. od svih Booleovih funkcija ovisno o dvije varijable) realizirajući (izračunavajući) zbroj tri bita x, y i z.
23 Primjer: zbroj tri bita Rješenje. Slično kao u primjeru 6, zapisujemo tablicu zbroja tri bita x, y i z. Ovaj zbroj može biti i 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 CFE Je li moguće implementirati proizvoljnu Booleovu funkciju (ili sustav Booleovih funkcija) CFE u bazi B 0 = (x&y, x y, x)? Limenka. Kako se to može opravdati? Na primjer, da. Jer (x&y, x y, x) je potpuni sustav u P 2, proizvoljna Booleova funkcija f može se predstaviti 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 zatim, koristeći ovu DNF (formulu), konstruirajte odgovarajući CFE. Ova metoda konstruiranja SFE za Booleove funkcije naziva se metoda DNF sinteze.
26 Sinteza CFE pomoću DNF-a. Koja će složenost CFE S po DNF-u 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 elementarnih konjukcija. Svaka elementarna konjunkcija je konjunkcija n varijabli ili njihovih negacija.
27 Sinteza SFE pomoću DNF-a Dakle, sklop će imati: 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 elementarne konjukcije u savršenom DNF-u; najviše (2 n 1) disjunktor za provedbu disjunkcije elementarnih konjunkcija DNF-a. 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 CFE klasi 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 vrijedi L(f) n 2 n + n.
29 Zadaci za neovisno rješenje 1. Za Booleovu funkciju f (x 1, x 2, x 3) = (), konstruirajte CFE u bazi standardne složenosti Za Booleovu funkciju f (x 1, x 2, x 3) = (), konstruirajte CFE u 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 bazi standardne dubine Dokažite da u standardnoj bazi L(xy) = 4.
30 Literatura za predavanje 4 1. Yablonsky S.V. Uvod u diskretnu matematiku. M .: Viša škola, V. dio, pogl. 2, s 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: Sheme funkcionalnih elemenata s kašnjenjem (SFES), automatizam njihovih preslikavanja. Zastupstvo KAV FEZ-a. Pojednostavljenja CAV-a. Različitost i nerazlučivost CAV stanja. Mooreov teorem
Predavanje: Anselov teorem o rastavljanju n-dimenzionalne kocke na lance. Teorem o broju monotonih funkcija algebre logike. Teorem o dešifriranju monotonih funkcija algebre logike. Predavač - izvanredna profesorica Selezneva Svetlana
Predavanje: Konačni automati s izlazom (KAV). Funkcije automata, metode za njihovo dodjeljivanje. Teorem o transformaciji periodičnih nizova automatskim funkcijama. Predavač - izvanredna profesorica Svetlana Nikolaevna Selezneva
Predavanje: Djelomično uređeni skupovi (POS). CHUM dijagram. Maksimalni, minimalni, najveći i najmanji elementi. Lanci i protulanci, duljina i širina kraja kuge. Teorem o cijepanju PL na antilance.
Predavanje 2. Svojstva binomnih koeficijenata. Zbrajanje i način generiranja funkcija (konačni slučaj). Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Procjene iznosa
Predavanje: Algoritam za prepoznavanje potpunosti u P k. zatvorene nastave. Klase funkcija koje čuvaju skupove i čuvaju particije, njihovu zatvorenost. Kuznjecovljev teorem o funkcionalnoj potpunosti. Predzavršena nastava.
Predavanje 2. Kombinatorika. Svojstva binomnih koeficijenata. Brojanje zbroja i način generiranja funkcija. Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Asimptotski
Predavanje: Konačne funkcije. Elementarne k-vrijedne funkcije. Načini zadavanja k-vrijednih funkcija: tablice, formule, 1. i 2. oblici, polinomi. Potpunost. Teorem o potpunosti sustava Post. Webb funkcija.
Predavanje 3. Sekvence određene rekurentnim odnosima. Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Zajedničke odluke LORU-a i LNRU-a. Predavač - izvanredna profesorica Selezneva Svetlana
Predavanje 15. Funkcije logike konačnih vrijednosti. Elementarne funkcije k-vrijedne logike. Metode za određivanje k-vrijednih logičkih funkcija: tablice, formule, I i II oblici, polinomi. Potpunost. Predavač - izvanredna profesorica Selezneva
Predavanje: Funkcije logike konačnih vrijednosti. Elementarne funkcije k-vrijedne logike. Metode za određivanje k-vrijednih logičkih funkcija: tablice, formule, I i II oblici, polinomi. Potpunost. Predavač - izvanredna profesorica Selezneva Svetlana
Predavanje: Möbiusova funkcija na CCM-u. Möbiusova funkcija na n-dimenzionalnoj kocki. Möbiusova formula za inverziju. Načelo uključivanja-isključivanja. Problem brojanja permutacija-poremećaja. Predavač - izvanredna profesorica Selezneva Svetlana
Predavanje 2. Svojstva binomnih koeficijenata. Način generiranja funkcija, izračunavanje zbroja i dokaz identiteta. Polinomski koeficijenti. Načelo uključivanja-isključivanja. Predavač - izvanredna profesorica Selezneva Svetlana
Predavanje: Bitne funkcije. Tri leme o bitnim funkcijama. Yablonskijev kriterij potpunosti. Slupetsky kriterij potpunosti. Schaefferove funkcije. Predavač izvanredni profesor Svetlana Nikolaevna Selezneva [e-mail zaštićen]
Predavanje: Osnovni kombinatorni brojevi. Procjene i asimptotika kombinatornih brojeva. Predavač - izvanredna profesorica Svetlana Nikolaevna Selezneva, fakultet CMC Moskovskog državnog sveučilišta po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su
Predavanje: Svojstva binomnih koeficijenata. Zbrajanje i način generiranja funkcija (konačni slučaj). Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Procjene za sume binoma
Predavanje: Konačni automati s izlazom. Transformacija periodičnih nizova konačnim automatima s izlazom. Različitost stanja u konačnim automatima s izlazom. Pojednostavljivanje strojeva. Predavač Selezneva
Predavanje: Poklopac kompleta i poklopac matrice. Gradijentna pokrivenost. Lema o pokrivanju gradijenta. Procjene kardinalnosti skupa sjenčanja n-dimenzionalne kocke. Procjene duljine polinomskih normalnih oblika funkcija
Predavanje 5. Poklopac kompleta i pokrov matrice. Gradijentna pokrivenost. Lema o pokrivanju gradijenta. Procjene kardinalnosti skupa sjenčanja Booleove kocke. Procjene duljine polinomskih Booleovih normalnih oblika
Predavanje 3. Sekvence određene rekurentnim odnosima. Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Zajedničke odluke LORU-a i LNRU-a. Primjeri Predavač - izvanredna profesorica Selezneva
Predavanje 3. Relacije na skupovima. Svojstva. Formula za uključivanje-isključivanje. Relacija ekvivalencije. Odnos djelomične narudžbe. Predavač - izvanredna profesorica Svetlana N. Selezneva Predavanja o diskretnim modelima.
Predavanje 4. Značajke viševrijednih logika. Zatvorena klasa, osnova zatvorene klase. Teoremi Yanova i Muchnika o postojanju u mnogovrijednim logikama zatvorenih klasa bez osnove i zatvorenih klasa s prebrojivim
Predavanje. Funkcije prirodnog argumenta (sekvencije). Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Zajedničke odluke LORU-a i LNRU-a. Primjeri Predavač - izvanredna profesorica Svetlana Selezneva
Predavanje: Kromatski broj grafa. Kriterij za dvobojni graf. Teoremi o gornjim i donjim granicama za kromatski broj grafa. Predavač - izvanredna profesorica Svetlana N. Selezneva Predavanja o diskretnim modelima.
Predavanje: Grafovi i mreže. Procjena broja pseudografa s q rubovima. Procjena za broj stabala s q rubovima. Planarni grafovi. Eulerova formula za planarne grafove. Najveći broj bridova u planarnim grafovima. neplanarnost
Predavanje 1. Kombinatorika. Položaji, permutacije, plasmani s ponavljanjima, kombinacije, kombinacije s ponavljanjima. Njihov broj. Predavač - izvanredna profesorica Svetlana N. Selezneva Katedra za matematičku kibernetiku
Predavanje: Sekvence. Homogene i nehomogene linearne rekurentne jednadžbe. Opća rješenja linearnih rekurentnih homogenih i nehomogenih jednadžbi. Predavač - izvanredna profesorica Svetlana Nikolaevna Selezneva
Predavanje 8. Stranice za bojanje. Ekvivalencija boja s obzirom na grupu. Generiranje funkcija. Niz nabrajanja za brojke i niz nabrajanja za funkcije. Poyin teorem. Predavač Selezneva Svetlana Nikolaevna
Predavanje: Bojanje. Ekvivalencija boja s obzirom na permutacijske grupe. Polyin teorem (poseban slučaj). Generiranje funkcija. Niz nabrajanja za brojke i niz nabrajanja za funkcije. Teorema
Predavanje 2. Konjunktivni normalni oblici. Implicitna, jednostavna implikacija funkcije. Skraćene CNF funkcije algebre logike. Metode za konstruiranje skraćenog CNF-a. Predavač Selezneva Svetlana Nikolaevna [e-mail zaštićen]
Matematički modeli i metode logičke sinteze VLSI jesen 2015. Predavanje 4 Plan predavanja Logička optimizacija kombinacijskih logičkih sklopova Različiti načini predstavljanja funkcija algebre logike (FAL)
Predavanje: Nedeterministički konačni automati (NFA) bez izlaza. Teorem o podudarnosti klasa skupova riječi dopuštenih konačnim determinističkim i konačnim nedeterminističkim automatima. Postupak
Predavanje 1. Selekcije. Položaji, permutacije, rasporedi s ponavljanjima, kombinacije, kombinacije s ponavljanjima, njihov broj. Primjeri. Predavač - izvanredni profesor Svetlana Nikolaevna Selezneva Predavanja na predmetu Diskretno
Predavanje 1. Kombinatorski objekti: odabiri, smještaji, permutacije, položaji s ponavljanjima, kombinacije, kombinacije s ponavljanjima, njihov broj. Kombinatorni brojevi: faktorijalni, opadajući faktorijal, binom
PREDAVANJE 4 SHEME IZ FUNKCIONALNIH ELEMENTA 1. Osnovne definicije Prije svega potrebno je razmotriti sastav. Funkcija se može predstaviti kao "crna kutija" koja ima ulaz i izlaz. Neka bude
Predavanje 2. Algoritam za prepoznavanje potpunosti u P k. Kuznjecovljev teorem. zatvorene nastave. Klase funkcija koje čuvaju skup. Klase funkcija koje čuvaju particiju. Predzavršena nastava. Predavač Seleznjeva
Predavanje 3. Zhegalkin polinom. Metode za konstruiranje polinoma Zhegalkinove funkcije. Linearna implicitna funkcija. Linearni konjunktivni normalni oblik (LCNF). Pronalaženje svih linearnih implicitnih funkcija. Ispitivanje
Predavanje 2. Generirajuće funkcije: prebrojavanje kombinatornih zbroja i dokazivanje identiteta, navođenje kombinatornih objekata. Načelo uključivanja-isključivanja. Brojenje broja permutacija-poremećaja. Predavač -
Predavanje 5. Grafovi. Stranice za bojanje grafikona. Kromatski broj grafa. Kriterij bikromatičnosti za graf. Gornje granice za kromatski broj grafa. Predavač Selezneva Svetlana Nikolajevna [e-mail zaštićen] Predavanja
Predavanje: Konačni automati (KA) bez izlaza (konačni automati-prepoznavači). Prijelazni dijagrami. Skupovi automata (jezici). Lema o svojstvima skupova automata. Primjer neautomatskog skupa. Predavač
Predavanje 1. Konačne funkcije. Elementarne k-vrijedne funkcije. Načini zadavanja k-vrijednih funkcija: tablice, formule, 1. i 2. oblici, polinomi. Potpunost. Teorem o potpunosti sustava Post. Webb funkcija.
Predavanje 7 Grafički model za zadatak raspodjele letova. Kromatski broj grafa. Kriterij da graf bude dvobojan.
Kolegij "Osnove kibernetike" za studente smjera 01.02.09.01 (matematički i računalni softver) 1. Opći podaci (opterećenje, oblici upravljanja i sl.). Tečaj je
Predavanje 6. Grafovi. Nasljedna svojstva grafova. Procjena broja bridova u grafovima s nasljednim svojstvom. Ekstremni grafovi. Najveći broj bridova u ravnim grafovima i grafovima bez trokuta s danim
Math-Net.Ru Sveruski matematički portal DS Romanov, Metoda za projektiranje lakih za testiranje sklopova koji dopuštaju testove provjere jedinica 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 dopuštenih konačnim determinističkim i nedeterminističkim automatima. Postupak
Praktični rad 2 Konstrukcija normalnih oblika logičke funkcije Svrha rada: Naučiti graditi konjunktivne, disjunktivne, savršene normalne oblike logičke funkcije Sadržaj rada: Osnovni
Seminar o složenosti Booleovih funkcija Predavanje 1: Uvod A. Kulikov Klub informatike 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 upravljačkih sustava
Predavanje: Regularni izrazi i regularni skupovi. Kleeneov teorem o podudarnosti klasa automatskih skupova i regularnih skupova. Predavač - izvanredna profesorica Svetlana Nikolaevna Selezneva Predavanja o diskretnoj matematici
Predavanje 3 Booleove algebre i Booleove funkcije Booleove algebre Pojam algebarskih sustava Algebarski sustav ili algebarska struktura je skup simbola neke abecede (nosača) s danim
Predavanje 5. Grafovi. Primjeri primjene grafova. transportni zadatak. 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. transportni zadatak. 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. Podsjetimo da za proizvoljne skupove A i B postoje skupovi A B = (x x A i x B); (sjecište 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č Selezneva Svetlana Nikolaevna [e-mail zaštićen] fakultet CMC Moskovskog državnog sveučilišta po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.ru
Predavanje: Grafovi. Osnovni koncepti. Povezani grafovi. Drveće. Jezgro stabla. Broj visećih vrhova u razdvojnom stablu. Predavač - izvanredna profesorica Svetlana N. Selezneva Predavanja o diskretnim modelima. magistrat,
Predavanje 11. Booleovi sklopovi. Diskretna matematika, HSE, Fakultet računarskih znanosti (jesen 2014. proljeće 2015.) Booleov sklop u varijablama x 1,..., x n je niz Booleovih funkcija g
ODOBRENO Prorektor za nastavu Yu. A. Samarsky 10. lipnja 2008. PROGRAM I ZADACI za predmet DISKREtne strukture na smjeru 010600 fakultet FIVT Odsjek za analizu podataka kolegij II semestar 4 dva
Moskovsko državno sveučilište Lomonosov Odsjek za računsku matematiku i kibernetiku S. A. Lozhkin ELEMENTI TEORIJE SINTEZE DISKRETNIH UPRAVLJAČKIH SUSTAVA Moskva 2016. Sadržaj
Predavanje: Nasljedna svojstva grafova. Ekstremni grafovi. Ramseyevi brojevi. Predavač - izvanredna profesorica Svetlana Nikolaevna Selezneva, fakultet CMC Moskovskog državnog sveučilišta po imenu M.V. Lomonosov Predavanja na stranici http://mk.cs.msu.su Nasljedno
Predavanje: Operacije nad skupovima konačnih automata. Komplementacija, unija, presjek, proizvod i iteracija skupova automata, njihov automatizam. Predavač - izvanredni profesor Svetlana Nikolaevna Selezneva Predavanja
Ministarstvo za komunikacije i informatizaciju Ruske Federacije Povolška državna akademija za telekomunikacije i informatiku Odsjek za višu matematiku Odobreno od strane Metodološkog vijeća PGATI 29. ožujka 2002.
Predavanje 5. Boje bridova grafova. Kromatski indeks grafa. Kromatski indeks bipartitnih grafova. Gornje i donje granice za kromatski indeks grafa. Predavač Selezneva Svetlana Nikolaevna [e-mail zaštićen]
Math-Net.Ru Sveruski matematički portal NP Red'kin, O sklopovima koji dopuštaju 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 vrijednost koja može imati dvije vrijednosti: istinito i netočno. Izjave su označene velikim slovima
Funkcionalni dijagrami (FS) dizajnirani su za pretvaranje logičkih informacija. Početna informacija, kodirana u obliku diskretnih signala, dovodi se na ulaze kruga `x n. Zatim se ta informacija obrađuje i čita u diskretnom obliku s izlaza kruga `y m(n, m su brojevi njegovih ulaza i izlaza). Razmotrimo kako FS funkcionira u dvovrijednoj logici i ima jedan izlaz ( m=1). Transformacija informacija u njima može se dati kao funkcija algebre logike na=f(x n). Umjesto relejnih elemenata u FS koriste se funkcionalni elementi (FE) koji u pravilu implementiraju elementarne logičke funkcije.
Definicija.Analiza naziva se konstrukcija formule algebre logike (ako je potrebno - njezina tablica istinitosti) za dani FS.
Za izgradnju formule prema zadanoj shemi potrebno je prikazati veze između FE u FS kao zamjene u elementarnim funkcijama koje im odgovaraju. Pretpostavlja se da se obrada informacija odvija u fazama od ulaza do izlaza. U stvarnim shemama koriste se dodatni elementi kako bi se osiguralo vrijeme rada svih FS-ova.
FS analiza se može izvesti na dva načina - od ulaza do izlaza i od izlaza do ulaza. Razmotrimo prvu metodu, koristeći dodatnu notaciju za veze međukruga.
Primjer 1(& , Ú , Ø ) se prihvaćaju kao PE. Analizirajte FS čija je fizička struktura data na slici 1.19.
Riješenje. Nakon što smo označili međupriključke PV-a kao što je prikazano na slici, korak po korak određujemo signale koji im odgovaraju . U ovom slučaju prelazimo s ulaza kruga na njegov izlaz.
sl.1.19
KORAK 1. R=`y , Q = `z.
KORAK 2. x=x&R= x&`y, P=x& y, W=P&P= x&y&`z.
KORAK 3. Y=x&z=x&`y& z, U=P&z = x&y&z.
4. KORAK. 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 logičke algebre:
F(x,y,z) = x&`y&zÚ x&y&zÚ x&y&`z.
Pronađena formula je SDNF. Vektor njegovih istinitosti ima oblik (00000111) .
Ovisno o početnim podacima, među zadacima sinteze (dizajna) FS može se izdvojiti:
1) sinteza sklopova prema zadanim formulama,
2) sinteza sklopova prema zadanim funkcijama.
Definicija.Sinteza FS prema zadanoj formuli naziva se konstrukcija strukture FS koja odgovara zadanoj formuli algebre logike.
Rješenje takvih problema provodi se prema algoritmu, inverznom metodom analize. Kao što je navedeno u odjeljku 1.7, struktura formula u algebri logike dopušta izomorfni prikaz samo sustava s paralelnim i serijskim vezama elemenata. Stoga bi u FS izomorfnom odgovarajućoj formuli trebali postojati samo spojevi ovog tipa.
Definicija.Sinteza FS prema zadanoj funkciji naziva se konstrukcija blok dijagrama koji implementira zadanu funkciju algebre logike.
Budući da je prikaz funkcija formulama dvosmislen, ovaj problem ima nejedinstveno rješenje. Kao iu slučaju relejnih krugova, optimalni su FS-ovi koji se sastoje od minimalnog broja PV-a i veza između njih. Takav FS može se dobiti pomoću formula s minimalnim brojem varijabli.
Što se tiče RS, posebno ćemo razmatrati formule koje su optimalne u klasi normalnih oblika (koji su jednaki odgovarajućim minimalnim oblicima), kao i apsolutno optimalne formule dobivene iz minimalnih normalnih oblika daljnjom redukcijom korištenjem zakona algebre logika. Metode za dobivanje optimalnih formula su iste kao u relejnim krugovima. Primjer 1 razmatra FS koji implementira funkciju (00000111) . Ovaj FS nije optimalan, budući da formula koja mu odgovara opisuje SDNF F = x`yz Ú x y zÚ x y`z, što nije minimalno. Minimizirajući ga, dobivamo MDNF sljedećeg oblika: F = x yÚ xz. Odgovara FS na slici 1.20
sl.1.20
Ako primijenimo distributivni zakon na MDNF, dobivamo formulu s još manje varijabli: f = x(yÚ z). Za ovu funkciju poklopila se s MCNF-om. Odgovara apsolutno optimalnoj shemi
Slika 1.21
Očito je ova shema mnogo jednostavnija od izvorne (slika 1.19). Budući da se sinteza optimalnog FS svodi na konstrukciju minimalnih formula, optimalne sheme se slično konstruiraju i u drugim bazama. Analogi prvog i drugog distributivnog zakona algebre logike za Schefferove i Webbove oblike 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 zbrajač dvaju brojeva koristeći FE koji odgovara bazi (Ø,¯), kao i bazi (¯).
Riješenje. Označimo jednoznamenkaste binarne brojeve dostavljene na ulaz kroz ( x,na). Izlaz bi trebao biti njihov zbroj u binarnom obliku. Ako x= 1, y= 1, zatim S = 2 10 \u003d 10 2 , dakle, za njegovu sliku, u općem slučaju, potrebno je koristiti dva binarna znaka, a FS mora imati dva izlaza. Označimo ih f(najznačajnija znamenka zbroja) i g(najniža ocjena). Funkcionalne tablice istinitosti f (x,na),g(x,na):
| x | y | f(x,y) | g(x,y) |
Konstruiramo SWNF funkcija u bazi (Ø ,¯). f ima jednu jedinicu u vektoru istine, pa se njegov oblik sastoji od jednog konstituenta: f=¯ (Ø x,Ø na). Funkcija g SVNF ima oblik: g=د(¯( x,Ø na),¯(Ø x,na)). Ovi oblici su minimalni. Prilikom kombiniranja ulaza elemenata, funkcionalni dijagram se može prikazati na sljedeći način:
sl.1.22
U razmatranom primjeru nemoguće je pojednostaviti Webbove normalne oblike korištenjem zakona algebre logike. U jednofunkcionalnoj bazi (¯) dobivamo FS primjenom supstitucije Ø x= ¯ ( x,x). Odgovarajuća shema data je na slici 1.23.
sl.1.23
ZADACI
1. Konstruirajte koristeći FE (& ,Ú ,Ø )optimalni u klasi normalnih oblika i apsolutno optimalni FS koji implementiraju sljedeće funkcije:
ali) ( x® y)Å zy;b)( xÅ y)|z,u) xy® yz;G) x|(yÚ z); e) x®( y® z) ;
f) (10011101) ;g) (01101011) ;h) (1110101111111110) .
2. Konstruirajte pomoću FE (Ú,Ø )FS funkcija 1.a) -g).
3. Konstruirajte pomoću FE (&,Ø )FS funkcija 1.a)-g).
4. Izgradite FS koji implementira jednobitni binarni zbrajač (Primjer 2) koristeći FE sljedećeg oblika:
a) (& ,Ú ,Ø), b) (Ú ,Ø ) , c) (& ,Ø), d) ( x| y} .
5. Koristeći FE (& ,Ú ,Ø ) izgradite FS sljedećih uređaja:
a) Pretvarač s binarnim ulazima ( x,na), i izlaz f, koji funkcionira ovako: prilikom prijave x= 0 na izlazu f =na, a prilikom podnošenja x = 1 na ulazu f =`y;
b) uređaj za biranje s binarnim ulazima ( x,na) i izlazi f 0 , f 1 , f 2 , f 3, koji kao ulaz uzima kombinaciju vrijednosti ( x y) kao binarni broj i, koji se nalazi u rasponu od 0 do 3. Izlazne vrijednosti za svaku i sljedeće: fi= 1, a sve ostalo fj= 0, (0 £ j£3, j¹ i).
6. Je li moguće uzeti sljedeće skupove funkcija kao osnovu za izgradnju FS-a:
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 izgraditi samo iz jednog FE tipa (®).
8. Navedite primjere upravljačkih funkcija čiji se FS ne može izgraditi samo iz jednog FE tipa (Å, º).
9. Zadan je FS iz FE (& ,Ú ,Ø ).
sl.1.24
Je li moguće iz njega isključiti ekvivalentnim transformacijama:
a) svi elementi (Ø)?
b) svi elementi (&)?
c) svi elementi (Ú)?
10. Optimizirajte FS iz FE (& , Ú , Ø ), prikazanog na slici 1.25.
sl.1.25
Izrada FS:
a) optimalno u klasi normalnih oblika i
b) apsolutno optimalno.
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 signale koje prima na ulazu pretvara u signal na izlazu pretvarača. Od funkcionalnih elemenata, uz pomoć nekih pravila, moguće je graditi modele složenije strukture i funkcioniranja – dijagrame funkcionalnih elemenata. U ovim modelima ulazni i izlazni signali su kodirani simbolima 0 i 1.
Pravila građenja. Za dobivanje složenih SPE od jednostavnijih, na njih se uzastopno primjenjuju operacije cijepanja ulaza ili izlaza kruga, pričvršćivanja funkcionalnog elementa u krug i povezivanja funkcionalnog elementa s ulazom ili izlazom kruga. Ove operacije nalikuju pravilima za dobivanje složene formule od jednostavnijih pomoću superpozicije.
Sinteza SFE. Budući da disjunkcija, konjunkcija i negacija čine potpuni sustav u razredu R 2 , zatim bilo koju Booleovu funkciju iz n Argumenti se mogu implementirati pomoću sklopa funkcionalnih elemenata - disjunktori, konjuktori i invertori - s n ulaza i jednog izlaza. Da biste to učinili, možete, na primjer, izraziti danu Booleovu funkciju u terminima SDNF ili SKNF, a zatim "sintetizirati" rezultirajuću formulu u obliku kruga funkcionalnih elemenata, uzastopno primjenjujući navedene operacije cijepanja, spajanja i povezivanja iznad.
32. Metoda SPE sinteze koja se temelji na kompaktnoj implementaciji svih konjunkcija pomoću univerzalnog multipola, složenosti rezultirajućih sklopova.
Definicija. Funkcija od n argumenata naziva se booleova funkcija (ili funkcija algebre logike) ako svakom skupu pridružuje broj.
Za postavljanje Booleovih funkcija koristit ćemo tablice, 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 signale koje prima na ulazu pretvara u signal na izlazu pretvarača. Od funkcionalnih elemenata, uz pomoć nekih pravila, moguće je graditi modele složenije strukture i funkcioniranja – dijagrame funkcionalnih elemenata. U ovim modelima ulazni i izlazni signali su kodirani simbolima 0 i 1.
Metoda SPE sinteze temelji se na kompaktnoj implementaciji svih konjunkcija pomoću univerzalnog multipola. Ova se metoda također temelji na predstavljanju funkcije u obliku SDNF-a, ali omogućuje izgradnju manje složenih sklopova zbog kompaktnije implementacije konjunkcija. Dekompozicija funkcije u SDNF-u može sadržavati konjukcije koje imaju zajedničke faktore. Ako su dvije takve konjukcije implementirane od strane jednog potkruga u bloku, tada će to zahtijevati konjunktore barem za jedan manje nego što su prije bili potrebni, uz neovisnu implementaciju svih konjukcija prvom metodom sinteze. Kompaktna implementacija svih mogućih konjukcija duljina n može se postići korištenjem induktivno konstruiranog univerzalnog multipola koji ima n ulazi i 2 n izlazi, gdje n = 1,2,3,… Prednosti metode posebno su uočljive kada je potrebno implementirati sustav od nekoliko Booleovih funkcija pomoću jednog sklopa. U tom 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 zadanog sustava. To bi omogućilo proći s manje konjunkora nego da je svaka funkcija danog sustava neovisno implementirana od strane vlastitog potkruga.
Složenost takvog multipola jednaka je L() =.
Ako sklop funkcionalnih elemenata Σ sadrži točno r funkcionalnih elemenata, onda kažemo da ima složenost r i zapiši to kao jednadžbu L(Σ) = r.
| " |
