Kuptimi i mëposhtëm "inxhinierik-konstruktiv" mund t'i jepet paraqitjes së funksioneve të Bulit me formula. Ne do ta konsiderojmë formulën Ф (x 1, ..., xn) mbi një grup F të fiksuar në mënyrë arbitrare si një "kuti e zezë", një pajisje e caktuar, në hyrje të së cilës futen të gjitha grupet e mundshme të vlerave të variablave, dhe prodhimi që korrespondon me këto grupe vlerash të funksionit f të përfaqësuar me formulën Ф (Fig. 6.22).
Për të kuptuar se si funksionon "kutia e zezë", duhet të çmontojmë procesin e ndërtimit të një formule nga nënformula. Arritja në nënformulat "bazë", d.m.th. elementet e grupit F, vijmë te "blloqet e ndërtimit", elementët strukturorë nga të cilët është montuar "kutia e zezë", e cila llogarit funksionin f. Çdo funksion i "bazës" F llogaritet nga "nyja" përkatëse, e cila konsiderohet si njësia më e vogël strukturore e "kutisë së zezë" tonë dhe struktura e saj e brendshme nuk analizohet më.
Shembulli 6.22. Le të zgjedhim një bazë standarde për grupin F. Pastaj formula mbi bazën standarde, që përfaqëson funksionin ~ (ekuivalencë), ndërtohet si më poshtë:
Llogaritja sipas kësaj formule (dhe procesi i ndërtimit të saj nga elementët e bazës standarde) mund të përshkruhet në mënyrë skematike siç tregohet në Fig. 6.23.
Variabli x 1 (më saktë, vlera e kësaj ndryshoreje) futet në hyrjen e një elementi strukturor të quajtur inverter (Fig. 6.24, a) dhe duke llogaritur mohimin. Negativi x 1 i hequr nga dalja e inverterit, d.m.th. funksioni x 1, futet në një nga hyrjet e lidhësit (Fig. 6.24, b), në hyrjen e dytë të të cilit futet ndryshorja x 2. Funksioni x 1 x 2 shfaqet në daljen e lidhësit. Llogaritja e funksionit x 1 x 2 mund të gjurmohet në mënyrë të ngjashme, të dy këto funksione futen në hyrjet e ndarësit (Fig. 6.24, c), nga dalja e të cilit funksioni x 1 x 2 ∨ x 1 x 2 hiqet (kjo nuk është gjë tjetër veçse një modul shumës 2: x 1 ⊕ x 2). Dhe së fundi, ky funksion futet në hyrjen e inverterit, në daljen e të cilit tashmë është marrë funksioni ~ (ekuivalenca). #
Kështu, arrijmë në idenë e një "qarku" - një model matematikor i kalkulatorit të një funksioni Boolean, i përfaqësuar nga një formulë e caktuar, e mbledhur nga elementë strukturorë, secila prej të cilave llogarit një nga funksionet "bazë" Boolean. Në rastin e përgjithshëm, "qarku" llogarit një operator Boolean dhe çdo funksion koordinativ i këtij operatori hiqet nga një nga daljet e qarkut.
Matematikisht, një "skema" përkufizohet si një graf i drejtuar i një lloji të veçantë, në të cilin kulmet dhe harqet janë etiketuar.
Le të prezantojmë shënimin: nëse F është një grup funksionesh Boolean, atëherë me F (n) shënojmë nëngrupin e F që përbëhet nga të gjitha funksionet e n variablave (n≥0).
Përkufizimi 6.14. Le të fiksohen grupet: F (funksionet Boolean) dhe X (variablat Boolean).
Një diagram i elementeve funksionale mbi një bazë F ∪ X (C Φ E), ose thjesht i tkurrur mbi bazën F ∪ X, gjithashtu një skemë (F, X), quhet një graf i drejtuar me fund të hapur (dmth., një rrjet), secila kulm i të cilit është etiketuar nga një prej elementeve të grupit FU X në mënyrë që të plotësohen kërkesat e mëposhtme:
- çdo hyrje e rrjetit është etiketuar ose nga ndonjë ndryshore nga X, ose nga ndonjë konstante nga F (0);
- nëse një kulm v i rrjetit është etiketuar me një funksion f prej n variablash (dmth., f ∈ F (n)), atëherë gjysma e shkallës së hyrjes së tij është e barabartë me n, dhe në grupin e harqeve që hyjnë në kulmin v, jepet një numërim (një me një) i tillë që secili hark numërohet nga 1 në n.
Nëse nënkuptohet baza, atëherë do të themi thjesht "skema". Përveç kësaj, nëse grupi i variablave është fiksuar "një herë e përgjithmonë" dhe kur shqyrtojmë skema të ndryshme ne ndryshojmë vetëm grupin e funksioneve F, atëherë, siç bëmë, duke prezantuar konceptet e një formule dhe mbivendosjeje mbi një bazë të caktuar, ne do të flasë për një SFE mbi një bazë F, duke supozuar çdo herë, që do të thotë një herë një grup fiks të ndryshoreve X, i cili (nëse kjo nuk dëmton saktësinë) nuk përmendet.
Tani përcaktojmë me induksion nocionin Funksioni boolean i llogaritur nga pjesa e sipërme e qarkut .
Përkufizimi 6.15. Le të jepet CFE S mbi një bazë F ∪ X, bashkësia e kulmeve të së cilës është V.
- Supozohet se çdo hyrje e CFE llogarit funksionin Boolean me të cilin është etiketuar (d.m.th., disa ndryshore ose konstante).
- Nëse një kulm v ∈ V është etiketuar me një funksion f ∈ F (n), harku me numrin i (1≤i≤n) që hyn në të vjen nga kulmi ui ∈ V, i cili llogarit funksionin gi, atëherë kulmi v njehson mbivendosjen f (g 1, ..., gn).
Kështu, nëse çdo kulm i CFE mbi F njehson një funksion, atëherë renditja në të cilën numërohen funksionet g 1, ..., gn, të zëvendësuara në vendet e variablave të funksionit f, është thelbësor në rastin e përgjithshëm. . Është e natyrshme të quajmë një funksion Boolean f në n variabla komutativ nëse ai ruan vlerën e tij nën një ndryshim arbitrar të ndryshoreve të tij. Në këtë rast, nuk duhet të shqetësohemi për numërimin e harqeve që hyjnë në pjesën e sipërme të qarkut, të shënuar me një funksion të tillë.
Shembulli 6.23. Konsideroni SPE në Fig. 6.25. Kulmet v 1 dhe v 2 janë hyrjet e SFE. Këto kulme llogaritin përkatësisht funksionet x dhe y. Pastaj kulmi v 3, si dhe kulmi v 4, sipas përkufizimit 6.15, njehson funksionin x | y (goditja e Schaeffer-it), dhe kulmi v 5 (dalja e rrjetit) njehson funksionin (x | y) l (x | y), e cila, dihet se është e barabartë me lidhëzën x y.
SPE e paraqitur në Fig. 6.26 ka dy dalje që llogaritin funksionet (x | x) | (y | y) = x ∨ y dhe (x | y) | (x | y) = x y.
Përkufizimi 6.16. Funksioni Boolean i llogaritur nga CFE mbi një bazë F ∪ X, është një funksion i llogaritur nga ndonjë prej daljeve të tij.
Kështu, CFE llogarit saktësisht sa funksione Boolean, sa rezultate. SFE në Fig. 6.25 llogarit një funksion, dhe SPE në Fig. 6.26 - dy.
Në rastin e përgjithshëm, nëse (x 1, ..., x n) është bashkësia e të gjitha variablave që shërbejnë si etiketa për hyrjet e qarkut S mbi një bazë F ∪ X me m dalje, CFE S përcakton shfaqjen e një kubi boolean B n në kubin boolean B m, d.m.th. operator boolean.
Vërejtje 6.10. Në disa raste, funksioni i llogaritur nga një SFE e caktuar përcaktohet disi ndryshe, duke supozuar se është një funksion i llogaritur nga çdo kulm nga nëngrupi i kulmeve të zgjedhura SFE. Në veçanti, mund të jenë rezultate. Në çdo rast, le të pranojmë të vizatojmë një shigjetë "dalje" nga kulmet e zgjedhura (në kuptimin e sapo treguar) të qarkut. #
Kështu, çdo qark portash llogarit disa operatorë Boolean, në veçanti, nëse numri i daljeve të qarkut është i barabartë me 1, atëherë ai njehson disa funksione Boolean.
E kundërta mund të vërtetohet gjithashtu: për çdo operator Boolean, një SFE mund të ndërtohet mbi një bazë F, ku F është një grup i plotë që llogarit operatorin e dhënë.
Ne përfaqësojmë funksionin y 1 në bazën Zhegalkin. Duke përdorur ligjet e de Morganit, ne marrim
(kujtoni se shuma e modulit 2 të çdo numri çift të termave të barabartë është e barabartë me 0).
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE për operatorin Boolean të dhënë në tabelë. 6.9, mbi bazën Zhegalkin është paraqitur në Fig. 6.27.
Kur dizajnoni një SFE, është e dobishme të mbani parasysh një parametër numerik të quajtur kompleksiteti i tij.
Kompleksiteti i SFE është numri i kulmeve të tij që nuk janë hyrje.
Treguar në Fig. 6.27 CFE mbi bazën Zhegalkin ka kompleksitet 5.
Le të shqyrtojmë tani CFE për të njëjtin operator mbi bazën standarde.
Sipas tabelës (shih tabelën 6.9), ne ndërtojmë SDNF për funksionin y 2:
y 2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Harta Karnot për këtë funksion, e paraqitur në Fig. 6.28 tregon se nuk mund të minimizohet (më saktë, SDNF e shkruar më sipër është DNF minimale për këtë funksion). Por ju mund të shkoni në anën tjetër. Mund të marrim parasysh tabelën. 6.9 si një tabelë që përcakton një funksion të pjesshëm boolean y 2 = y 2 (x 1 x 2 x 3 y 1). Duke minimizuar këtë funksion nga
harta Karnot * e paraqitur në Fig. 6.29, marrim
* Në këtë hartë, ne shënuam grupet në të cilat funksioni merr vlerën 0, duke vendosur zero në qelizat përkatëse. Kështu, ne duam të tërheqim edhe një herë vëmendjen për faktin se nuk duhet ngatërruar zerat me vizat: një vizë në qelizën e hartës që specifikon një funksion të pjesshëm do të thotë që vlera e funksionit nuk është përcaktuar në këtë grup, d.m.th. nuk është as 0 as 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
CFE mbi bazën standarde për operatorin Boolean të konsideruar është paraqitur në Fig. 6.30. Kompleksiteti i këtij SFE është 11. Vini re se kulmi që llogarit funksionin y 1 nuk është një dalje.
Operatori Boolean në këtë shembull llogarit shumën dyshifrore (modulin 2) të tre termave njëshifrorë. Mund të mendohet gjithashtu si një grumbullues binar njëbitësh - një bllok funksional i një grumbulluesi binar shumë-bit - për dy terma. Pastaj funksioni y 1 interpretohet si një "sinjal mbajtës" në bitin më domethënës. Në fig. 6.31 tregon "lidhjen" e tre SFE-ve (siç është paraqitur në Fig. 6.30), me ndihmën e të cilave llogaritet shuma e dy numrave binarë treshifrorë. Konstanta 0 futet në hyrjen e tretë të grumbulluesit për bitin më pak të rëndësishëm, dhe "sinjali i bartjes" i bitit më domethënës është biti më domethënës i shumës, i cili në rastin e përgjithshëm do të jetë një numër katërshifror. .
Vërejtje 6.11. Nëse e projektojmë SFE-në mbi një bazë standarde dhe duam të minimizojmë kompleksitetin e saj, atëherë së pari duhet të ndërtojmë minimumin përkatës DNF. Në këtë rast, mund të marrim parasysh një kriter tjetër me të cilin minimizohet vetë DNF - numri i mohimeve. Ndër të gjitha DNF-të minimale (në kuptimin e përkufizimit 6.6), duhet zgjedhur ato në të cilat numri i shfaqjes së variablave nën shenjën negative është më i vogli. Nga pikëpamja e kompleksitetit të SFE, i cili do të ndërtohet mbi bazën e minimumit DNF, kjo do të thotë se minimizon numrin e "invertorëve" - kulmet SFE të etiketuara me funksionin mohues.
Për shembull, për funksionin e dhënë nga harta Karnot (Fig. 6.32), në bërthamën e përbërë nga implikantë të thjeshtë x 1 x 2 x 4 dhe x 1 x 3 x 4, duhet të shtoni një implikant të thjeshtë x 2 x 3 x 4. , dhe jo x 1 x 2 x 3 sepse nuk përmban negativë.
Në teknologjinë moderne të pajisjeve të kontrollit dhe llogaritjes, një vend të rëndësishëm zënë konvertuesit diskretë, domethënë pajisjet që kanë një numër të caktuar hyrjesh dhe daljesh. Grupet e sinjaleve që mbërrijnë në hyrje dhe që dalin në dalje i përkasin grupeve të kufizuara të njohura.
Ndani punën tuaj në rrjetet sociale
Nëse kjo punë nuk ju përshtatet në fund të faqes, ekziston një listë me vepra të ngjashme. Ju gjithashtu mund të përdorni butonin e kërkimit
Aranov Victor Pavlovich. Matematikë diskrete. Seksioni 5. Qarqet DNF dhe FE.
Leksioni 28. Diagramet e elementeve funksionale. Probleme të analizës dhe sintezës
Leksioni 28. DIAGRAME NGA ELEMENTET FUNKSIONALE.
PROBLEMET E ANALIZËS DHE SINTEZËS
Plani i leksionit:
1. Koncepti i një qarku të elementeve funksionale(FE).
2. Probleme të analizës dhe sintezës së qarqeve nga PV.
- Koncepti i një qarku nga PV
Në teknologjinë moderne, pajisjet e kontrollit dhe llogaritjes zënë një vend të rëndësishëmkonvertuesit diskrete, pra pajisje që kanë një numër të caktuar hyrjesh dhe daljesh. Grupet e sinjaleve që mbërrijnë në hyrje dhe që dalin në dalje i përkasin grupeve të kufizuara të njohura. Pajisjet konvertojnë grupet hyrëse të sinjaleve në dalje. Modeli matematikor i pajisjeve të tilla është i ashtuquajturidiagramet e elementeve funksionale(SFE).
Si shembull, merrni parasysh qarkun elektrik të tre diodave dhe rezistencën, të paraqitur në Fig. një.
Oriz. 1. Diagrami elektrik dhe simboli i tij
Në pikat e qarkut të treguar në një rreth, në kohë të ndryshme, mund të shfaqet ose një nivel i lartë, afërsisht i barabartë me 5 V, ose një nivel i ulët, afërsisht i barabartë me zero. Në pikën e qarkut të shënuar me vizë, niveli i tensionit mbahet vazhdimisht i ulët.
Pikat e shënuara do të interpretohen si hyrje, dhe pika - si dalje. Funksionimi i qarkut mund të përshkruhet si më poshtë: nëse të gjitha hyrjet kanë një nivel tensioni të ulët, atëherë dalja është gjithashtu e ulët, nëse të paktën një nga hyrjet ka një nivel të tensionit të lartë, atëherë dalja është e lartë. Nëse caktoni një gjendje me një nivel të tensionit të lartë si një, dhe me një nivel të ulët të tensionit - zero, atëherë varësia e daljes nga hyrjet mund të vendoset duke përdorur një funksion Boolean.
Në bazë të kësaj qarku i mësipërm quhet elementi logjik “OR”.
Qarqe të tilla mund të ndërtohen nga tuba elektronikë, ndërprerës elektromekanikë, elementë pneumatikë, etj. Varësia e daljes nga hyrjet mund të përshkruhet jo vetëm si një ndarje, por edhe duke përdorur lidhje, mohim dhe funksione më komplekse të Bulit.
Ne do të shqyrtojmë portat logjike me varësi të ndryshme të prodhimit nga inputet. Këta elementë mund të lidhen me njëri-tjetrin, duke ushqyer daljet e disa elementeve me hyrjet e të tjerëve. Si rezultat, ne marrim SFE.
Përkufizimi i konceptit të SFE-së mund të ndahet në dy faza. Në fazën e parë, zbulohet pjesa strukturore e këtij koncepti, në të dytën - ajo funksionale.
Unë fazë. Le ta ndajmë këtë fazë në disa pika.
1 ... Ekziston një grup i kufizuar objektesh () i quajturelementet logjike.Çdo element ka hyrje dhe një dalje. Elementi është paraqitur grafikisht siç tregohet në Fig. 2.
2 ... Me induksion, ne përcaktojmë konceptin rrjet logjik si objekt në të cilin ka një numër të caktuar hyrjesh dhe një numër të caktuar daljesh (Fig. 3).
a) Baza e induksionit. Një kulm i izoluar quhet një rrjet logjik i parëndësishëm. Sipas përkufizimit, ai është njëkohësisht hyrje dhe dalje (Fig. 4).
… …
…
Oriz. Fig. 2 Fig. 3 4
b) Tranzicioni induktiv. Kjo pjesë bazohet në përdorimin e tre operacioneve.
Unë ... Operacioni i kombinimit të rrjeteve të shkëputura. Le të jenë dhe dy rrjete të shkëputura (pa elementë të përbashkët, hyrje dhe dalje), që kanë përkatësisht hyrje dhe dalje. Ndërlidhja e rrjetit teorik të grupeve është një rrjet logjik që ka hyrje dhe dalje.
II ... Operacioni i lidhjes së një elementi. Le të jetë rrjeti dhe elementi i tillë që në daljet e përzgjedhura të ndryshme me numra. Atëherë figura quhet rrjetë logjike, e cila është rezultat i lidhjes së elementit me rrjetin. Inputet janë të gjitha hyrjet, daljet janë të gjitha daljet e rrjetit, me përjashtim të daljeve me numra, si dhe daljet e një elementi. Rrjeti ka hyrje dhe dalje (Fig. 5).
… …
Oriz. 6.
Oriz. 5
III ... Operacioni i ndarjes së daljes. Le të theksohet një prizë me një numër në rrjet. Atëherë figura quhet rrjeti logjik i përftuar nga ndarja e prodhimit. Inputet janë të gjitha hyrjet, daljet janë të gjitha daljet e rrjetit me numrat 1,…,…, dhe dy dalje të tjera që kanë dalë nga dalja me numrin e rrjetit (Fig. 6). Prandaj ka hyrje dhe dalje.
3 ... Le të jepen alfabetet.
Diagrami i elementeve funksionalequhet rrjet logjik me hyrje nga alfabeti dhe dalje nga alfabeti, i cili shënohet
. (1)
Këtu janë disa shembuj të qarqeve.
1. Le të përbëhet grupi nga tre elementë AND (lidhës), OSE (ndarës) dhe JO (inverter).
Atëherë figura (Fig. 6) do të jetë një diagram, pasi mund të ndërtohet duke përdorur operacionet I - III .
Oriz. 6 Fig. 7
2. Figura e paraqitur në fig. 7 është gjithashtu një skemë.
II fazë. Përcaktimi i funksionimit të qarkut.
4 ... Le të krahasojmë CFE (1) me sistemin e funksioneve të algjebrës së Bulit
(2)
quajtur edhepërçueshmëria e këtij qarku.
Shembull. a) Për skemën, kemi një sistem të përbërë nga një ekuacion
Ose.
b) Për qarkun, marrim në mënyrë të ngjashme
- Zbatimi i funksioneve Boolean nga qarqet FE. Probleme të analizës dhe sintezës
qarqet nga PV
Detyrë analize: për një SFE të dhënë (1) të përftohet një sistem ekuacionesh Boolean (2).
Algoritmi për zgjidhjen e problemit: ndjekja e operacioneve të ndërtimit të një rrjeti I - III , ne llogaritim në mënyrë sekuenciale funksionet në daljet e elementeve të rrjetit.
Problemi i sintezës: për një bazë të caktuar të elementeve funksionale dhe një sistem arbitrar të ekuacioneve të Bulit (2), ndërtoni një qark (1) nga FE e dhënë që zbaton këtë sistem ekuacionesh.
Ekzistenca e zgjidhjes së problemit të sintezës përcaktohet nga teorema e Postit, sipas së cilës sistemi i funksioneve që zbatojnë FE-të bazë duhet të jetë i plotë. Funksionet mund të përfaqësohen si një mbivendosje e funksioneve, dhe çdo hap i mbivendosjes korrespondon me një kombinim të caktuar të elementeve.
Shembull. Për funksionin
(3)
Diagrami që korrespondon me mbivendosjen në anën e djathtë të formulës (3) është paraqitur në Fig. tetë.
Oriz. tetë
Problemi i sintezës qëndron në faktin se për një sistem të caktuar ekuacionesh Boolean është e mundur të ndërtohen shumë qarqe FE që zbatojnë këtë sistem. Në këtë drejtim, lind problemi i sintezës optimale: nga të gjitha llojet e skemave që zbatojnë një funksion të caktuar, zgjidhni më të mirën sipas një ose një kriteri tjetër, për shembull, me numrin më të vogël të elementeve. Skema të tilla do të quhen minimale.
Deklarata e mëposhtme është e vërtetë.
Teorema. Ekziston një algoritëm që ndërton një qark minimal për çdo sistem të funksioneve Boolean.
Ky algoritëm për ndërtimin e qarqeve minimale i përket klasës së algoritmeve të tipit "brute force", pasi bazohet në shikimin e të gjitha qarqeve deri në një kompleksitet të caktuar. Algoritmet shteruese të kërkimit, si rregull, janë shumë të mundimshëm dhe të papërshtatshëm për qëllime praktike. Prandaj, ne konsiderojmë më poshtë një problem më të thjeshtë për të cilin sistemi origjinal i ekuacioneve përmban një ekuacion
dhe, për rrjedhojë, qarku i dëshiruar ka një dalje.
Kompleksiteti i qarkut minimal shënohet me. Ne do ta shqyrtojmë problemin e sintezës jo për një funksion të veçantë, por për të gjithë klasën e funksioneve të variablave. Cilësia e algoritmeve të sintezës krahasohet duke krahasuar të ashtuquajturat funksione Shannon. Le
- kompleksiteti minimal i skemave që zbatojnë, të cilat përftohen duke përdorur algoritmin.
Funksionet quhen funksione Shannon, dhe është e qartë se
Problemi i sintezës është të gjesh një algoritëm për të cilin do të ishte sa më afër që të jetë e mundur, dhe në mënyrë që kompleksiteti i algoritmit të ishte dukshëm më i vogël se kompleksiteti i algoritmit shterues të kërkimit. Me këtë formulim të problemit, nuk kërkohet që algoritmi të gjejë qarkun minimal për çdo funksion, është e nevojshme vetëm që qarku më i thjeshtë i marrë me ndihmë të ketë një kompleksitet që nuk e kalon shumë.
Punime të tjera të ngjashme që mund t'ju interesojnë.Wshm> |
|||
| 9013. | METODAT PËR SINTEZËN E SKEMAVE NGA FE. DIAGRAME TË DEKODERIT DHE SHTESËSVE BINARE | 153,07 KB | |
| Teoria e përgjithshme e sintezës CFE çon në përfundimin se shumica e funksioneve Boolean për vlera të mëdha kanë qarqe komplekse minimale. Kjo do të thotë se një klasë shumë e ngushtë e funksioneve të Bulit ka vlerë praktike nga pikëpamja e sintezës. | |||
| 5321. | Llojet dhe vlerat e parametrave të mbrojtjes automatike për elementë të ndryshëm të një skeme të caktuar të projektimit | 526.7 KB | |
| Për të siguruar funksionimin normal të sistemit elektroenergjetik dhe konsumatorëve të energjisë elektrike, është i nevojshëm identifikimi dhe veçimi i vendit të dëmtimit nga rrjeti i padëmtuar sa më shpejt që të jetë e mundur, duke rivendosur kushtet normale të funksionimit të sistemit elektroenergjetik dhe konsumatorëve. | |||
| 5384. | Zhvillimi i një qarku elektrik të stendës për të analizuar funksionimin e një dekoderi me orë për 4 hyrje dhe 16 dalje | 626,63 KB | |
| Për të përmirësuar funksionimin e mjeteve lëvizëse ATP, është zhvilluar struktura organizative e sistemit të mirëmbajtjes dhe riparimit të mjeteve lëvizëse ATP dhe është propozuar një grup pajisjesh për diagnostikim dhe mirëmbajtje. Detyra kryesore e funksionimit të objekteve të riparimit të ndërmarrjes është të sigurojë funksionimin e pandërprerë të pajisjeve. Ai përfshin: bazën e riparimit dhe restaurimit të ndërmarrjes, magazinat, dyqanet dhe departamentet e përgjithshme të objekteve të riparimit, pajisjet teknologjike, dispeçimin. Organizata... | |||
| 1886. | Fazat e analizës së sistemit, qëllimet e tyre kryesore, objektivat | 27,44 KB | |
| Teoria e sistemeve optimale na lejon të vlerësojmë kufirin që mund të arrihet në sistemin optimal, ta krahasojmë atë me treguesit e sistemit aktual jo optimal dhe të zbulojmë nëse është e këshillueshme në rastin në shqyrtim të zhvillohet një sistem optimal. Për një proces të kontrolluar automatikisht të një sistemi të kontrolluar automatikisht, dallohen dy faza optimizimi: statike dhe dinamike. Optimizimi statik zgjidh çështjet e krijimit dhe zbatimit të një modeli procesi optimal dhe dinamik ... | |||
| 5123. | Zhvillimi i strategjive funksionale | 35,44 KB | |
| Strategjia e BNJ. Funksionet dhe struktura e menaxhimit. Funksionet e menaxhmentit dhe roli i tyre në formimin e strukturave drejtuese. Lloji hierarkik i strukturës së menaxhimit. | |||
| 20368. | Ndikimi i përbërjes së përbërësve dhe teknologjive të recetës në vetitë e konsumatorit të produkteve funksionale | 742,05 KB | |
| Koncepti i të ushqyerit optimal është pranuar nga shkenca moderne mjekësore. Kjo do të thotë se është bërë një kalim nga koncepti i të ushqyerit adekuat, kur makronutrientët janë rregulluar dhe normalizuar kryesisht - burimet e yndyrës, burimet e energjisë, materiali plastik (lipidet, proteinat, yndyrnat), në konceptin e të ushqyerit optimal, kur. spektri i lëndëve ushqyese të nevojshme për aktivitetin jetësor të trupit dhe komponentëve të tjerë të vegjël që më parë ishin anashkaluar janë zgjeruar shumë. | |||
| 4706. | Metodat për sintezën e karboksilateve Me | 9.26 MB | |
| Thelbi i metodës është të shpërndajë një oksid metali, hidroksid ose karbonat në një zgjidhje ujore të acidit përkatës. Produkti izolohet me avullim të tretësirës përpara kristalizimit ose me filtrim të precipitatit nëse karboksilati është i patretshëm ose i tretshëm në mënyrë të kufizuar në ujë. | |||
| 15923. | Metodat bazë për sintezën e pirazolodiazepinave | 263,39 KB | |
| Metoda të reja për sintezën e derivateve të pirazolodiazepinës. Zhvillimi i strategjive të reja të sintezës është me interes të konsiderueshëm. Studime sistematike dhe përgjithësuese të sintezës së derivateve të pirazolodiazepinës nuk janë kryer, disa çështje mbeten të paprekura nga polemika ose plotësisht të pazgjidhura. | |||
| 11978. | Instalime të teknologjisë energjetike të bazuara në oksidimin hidrotermik të aluminit për prodhimin e energjisë elektrike, nxehtësisë, hidrogjenit dhe nanomaterialeve funksionale | 49,89 KB | |
| Zhvillimi bazohet në reaksionin e oksidimit hidrotermik të aluminit, gjatë të cilit lirohet një sasi e madhe energjie termike dhe formohen oksidet e aluminit dhe hidrogjeni: l2H2O → lOOH boehmite15H2415. Uji i distiluar dhe pluhurat e aluminit me madhësi mikron përdoren si reagentë fillestarë. Instalimi KEU10 Instalimi ETK100 Karakteristikat teknike të instalimit ETK100: Vlera e parametrit Konsumi i aluminit kg h 101 Konsumi i ujit në hyrje në pajisjen e trajtimit të ujit kg h 484 Produktiviteti për hidrogjen nm3 110 Fuqia termike ... | |||
| 6605. | Sistemet eksperte. Projektimi i TP me metodën e sintezës | 11,67 KB | |
| Përfaqësimi i akumulimit të njohurive dhe mbajtja e tij e përditësuar është një detyrë komplekse e hetuar në seksionin e informatikës që quhet inxhinieri e njohurive. Inxhinieri i njohurive merr pjesë në zhvillimin e bazës së njohurive - thelbi i sistemeve të quajtur inteligjente. Më shpesh, sistemet inteligjente përdoren për të zgjidhur probleme komplekse ku kompleksiteti kryesor i zgjidhjes ... | |||
Madhësia: px
Filloni të shfaqni nga faqja:
Transkripti
1 Leksion 2. Skemat e elementeve funksionale (SFE) në një bazë të caktuar. Kompleksiteti dhe thellësia e skemës. Shembuj. Metoda për sintezën e SFE nga DNP. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Leksione për matematikën diskrete 2. Viti 1, grupi 141, Fakulteti i Matematikës Kompjuterike dhe Kibernetikës, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në sit
2 Diagramet e elementeve funksionale Le të përcaktojmë diagramet e elementeve funksionale në një bazë të caktuar. Le të na jepet një grup funksionesh Boolean B = (g 1 (x 1, ..., x n1), ..., gs (x 1, ..., x ns)) P 2, ku n 1, .. ., ns 0. Le ta quajmë këtë grup një bazë. Vini re se ky koncept i një baze nuk ka asnjë lidhje me konceptin e një baze P 2, e cila u konsiderua në algjebrën e logjikës. Si rregull, ne do të konsiderojmë bazën standarde B 0 = (x & y, x y, x).
3 Përcaktimi i një qarku të elementeve funksionale Një qark i elementeve funksionale (CFE) në bazën B 0 = (x & y, xy, x) është 1) një graf aciklik i orientuar G = (V, E), secila kulm v V prej të cilave ka një gjysmë shkallë të hyrjes d (v ) jo më shumë se dy (d (v) 2); 2) çdo kulm v me gjysmë shkallë hyrjeje të barabartë me 0 (d (v) = 0) quhet hyrje (ose hyrje qarku) dhe asaj i është caktuar një variabël Boolean x i; 3) të gjitha nyjet e tjera (përveç hyrjeve) quhen nyje të brendshme të qarkut;
4 Përkufizimi i një qarku elementësh funksionalë (vazhdim) 4) çdo kulmi v me gjysmë shkallë hyrjeje të barabartë me 1 (d (v) = 1) i caktohet një element mohues (funksional); të gjitha kulmet e tilla quhen inverterë; 5) çdo kulm v me një gjysmë shkallë hyrjeje të barabartë me 2 (d (v) = 2) i caktohet ose një element lidhor (funksional) &, ose një element shkëputës (funksional); të gjitha kulmet të cilave u caktohen elementet lidhëse quhen lidhëse, të gjitha kulmet të cilave u caktohen elementet e ndarjes quhen disjunktorë;
5 Përkufizimi i një qarku elementësh funksionalë (vazhdim) 6) Përveç kësaj, disa nga kulmet u caktohen variabla të ndryshme dalëse y 1, ..., y m. Nëse jepet një SPE S, hyrjet e së cilës janë caktuar vetëm variablat x 1, ..., xn, dhe me variablat dalëse y 1, ..., ym, atëherë këtë SPE do ta shënojmë me S (x 1 , ..., xn; y 1, ..., ym).
6 Shembull i SFE Shembulli 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):
7 Shembull i SFE Shembulli 1. Si rregull, SFE-të përshkruhen si më poshtë S (x 1, x 2, x 3; y 1, y 2, y 3):
8 Përcaktimi i kompleksitetit të SFE Kompleksiteti L (S) i SFE S është numri i kulmeve të brendshme të kësaj SFE, d.m.th. numri i elementeve funksionale në SFE S.
9 Kompleksiteti i SFE Shembull 2. Kompleksiteti i SFE S:
10 Përcaktimi i thellësisë së kulmit të CFE Me induksion përcaktojmë thellësinë d (v) të kulmit v në CFE S. 1. Baza e induksionit. Çdo hyrje v SFE S ka një thellësi të barabartë me 0: d (v) = Tranzicion induktiv. 1) Nëse një hark nga kulmi v 1 çon në inverterin v të CFE S, atëherë d (v) = d (v 1)) Nëse harqet nga kulmet v 1 dhe v 2 çojnë në lidhësin ose ndarësin v të CFE S, atëherë d (v) = max (d (v 1), d (v 2)) + 1. Thellësia D (S) e SFE S quhet maksimumi i thellësive të kulmeve të tij.
11 Thellësia e SFE S Shembulli 3. Thellësia e majave të SFE S dhe thellësia e SFE S:
12 Përkufizimi i funksionimit të SFE-së Në çdo kulm të SFE-së realizohet (ose llogaritet) një funksion i caktuar Boolean. Me induksion, ne përcaktojmë një funksion Boolean që realizohet në kulmin v të CFE S. 1) Nëse v është kulmi i hyrjes dhe atij i është caktuar ndryshorja xi, atëherë funksioni fv = xi realizohet në kulmin v. . 2) Nëse një hark nga kulmi v 1 të çon në inverterin v, dhe funksioni f v1 realizohet në kulmin v 1, atëherë funksioni f v = f v1 realizohet në kulmin v. 3) Nëse harqet nga kulmet v 1 dhe v 2 çojnë në lidhësin (ose ndarësin) v, dhe funksionet f v1 dhe f v2 realizohen përkatësisht në kulmet v 1 dhe v 2, atëherë në kulmin v funksioni fv = f v1 & f v2 (përkatësisht fv = f v1 f v2).
13 Funksionimi i CFE Besohet se CFE S (x 1, ..., xn; y 1, ..., ym) zbaton sistemin e funksioneve Boolean FS = (f 1, ..., fm), të cilat realizohen në kulmet e tij dalëse y 1, ..., y m.
14 Funksionimi i SFE Shembulli 4. Funksionet Boolean të realizuara në kulmet e SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Programi linear Një program linear me hyrje x 1, ..., xn mbi një bazë B 0 = (x & y, xy, x) është një sekuencë z 1, z 2, ..., zt, në të cilën për secilin numri j, j = 1, ..., t, qëndron se 1) ose zj = xi; 2) ose z j = z k për k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 SFE dhe programet lineare Është e qartë se llogaritja në SFE mund të rishkruhet si një program linear. Në të kundërt, çdo program linear mund të përfaqësohet në formën e disa SFE.
17 CFE dhe programe lineare Shembulli 5. CFE S korrespondon me një program linear z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.
18 SFE dhe karakteristikat e tyre Skemat e elementeve funksionale janë një model llogaritës. Karakteristikat e CFE që kemi prezantuar tregojnë aspekte të ndryshme të efikasitetit llogaritës. Kompleksiteti i CFE korrespondon me kohën e llogaritjes sekuenciale. Thellësia CFE korrespondon me kohën e llogaritjes paralele. Numri maksimal i kulmeve me të njëjtën thellësi në SFE korrespondon me numrin e procesorëve në llogaritjen paralele.
19 Shembull: shuma e dy biteve Shembulli 6. Ndërtoni një SPE në një bazë standarde që zbaton (llogarit) shumën e dy biteve x dhe y. Zgjidhje. Le të shkruajmë një tabelë me shumën e dy biteve x dhe y. Kjo shumë mund të jetë një numër me dy shifra binare, kështu që ne prezantojmë dy variabla Boolean z 0, z 1, të tilla që x + y = 2z 1 + z 0: x y z 1 z
20 Shembull: shuma e dy biteve Zgjidhje (vazhdim). Atëherë z 0 = x y, z 1 = xy. Duke marrë parasysh se x y = (x y) (x y), marrim SPE: Është e qartë se L (S 1) = 3, dhe D (S 1) = 3.
21 SFE në një bazë arbitrare Koncepti i SFE në një bazë arbitrare B P 2 është prezantuar në mënyrë të ngjashme.
22 Shembull: shuma e tre biteve Shembulli 7. Ndërtoni CFE në bazën P2 2 (d.m.th., nga të gjitha funksionet Boolean në varësi të dy variablave), duke realizuar (llogaritur) shumën e tre biteve x, y dhe z.
23 Shembull: shuma e tre biteve Zgjidhje. Ngjashëm me shembullin 6, ne shkruajmë një tabelë me shumën e tre biteve x, y dhe z. Kjo shumë mund të jetë gjithashtu një numër me dy shifra binare, kështu që ne prezantojmë dy variabla Boolean u 0, u 1, të tilla që x + y + z = 2u 1 + u 0: x y z u 1 u
24 Shembull: shuma e tre biteve Zgjidhje (vazhdim). Atëherë u 0 = x y z, u 1 = xy xz yz. Duke marrë parasysh se xy xz yz = xy z (x y), marrim CFE: Shohim që L (S) = 5, dhe D (S) = 3.
25 Zbatimi i funksionit Boolean CFE A është e mundur të zbatohet një funksion arbitrar Boolean (ose një sistem funksionesh Boolean) në bazën B 0 = (x & y, x y, x)? Mund. Si mund të justifikohet kjo? Për shembull, si kjo. Sepse (x & y, x y, x) është një sistem i plotë në P 2, një funksion arbitrar Boolean f mund të përfaqësohet nga një formulë vetëm përmes lidhjes, disjunksionit dhe mohimit. Për shembull, në formën e një DNF të përsosur, nëse f 0, dhe në formën x & x, nëse f = 0. Dhe më pas, duke përdorur këtë DNF (formulë), ndërtoni SFE-në përkatëse. Kjo metodë e ndërtimit të CFE për funksionet Boolean quhet metoda e sintezës DNF.
26 Sinteza e SFE-ve nga DNF Dhe çfarë kompleksiteti është marrë nga SFE S nga DNF për një funksion Boolean f (x 1, ..., x n), në varësi të n variablave? Një DNF e përsosur për një funksion f do të përmbajë më së shumti 2 n lidhje elementare. Çdo lidhje elementare është lidhja e n ndryshoreve ose mohimeve të tyre.
27 Sinteza e SFE sipas DNF-së Prandaj, qarku do të ketë: n inverterë për të zbatuar të gjitha mohimet e variablave x 1, ..., x n; nga (n 1) lidhës për zbatimin e secilës prej më së shumti 2 n lidhjeve elementare në një DNF të përsosur; më së shumti (2 n 1) ndarës për të zbatuar ndarjen e lidhëzave elementare të DNF. Marrim se L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Kompleksiteti i një funksioni Boolean Kompleksiteti L (f) i një funksioni Boolean f (x 1, ..., x n) në klasën e CFE-ve është kompleksiteti minimal midis të gjitha CFE-ve që zbatojnë funksionin f. Kështu, kemi vërtetuar teoremën: Teorema 1. Për një funksion arbitrar f (x 1, ..., x n) P 2, L (f) n 2 n + n.
29 Problema për zgjidhje të pavarur 1. Për një funksion Boolean f (x 1, x 2, x 3) = (), ndërto një SPE në bazën standarde të kompleksitetit Për një funksion Boolean f (x 1, x 2, x 3 ) = (), ndërto një SPE në bazë standarde të kompleksitetit Për një funksion Boolean f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, ndërto CFE në bazën standarde të thellësisë Vërtetoni se në bazën standarde L (xy) = 4.
30 Literaturë për leksionin 4 1. Yablonskiy S.V. Një hyrje në matematikën diskrete. M .: Shkolla e Lartë, Pjesa V, Ch. 2, me Gavrilov G.P., Sapozhenko A.A. Probleme dhe ushtrime në matematikë diskrete. Moskë: Fizmatlit, Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.
31 Fundi i leksionit 4
Leksioni: Skemat e elementeve funksionale me vonesa (SPEZ), automatizimi i pasqyrimeve të kryera prej tyre. Përfaqësia e KAV SFEZ. Thjeshtimet e KAV. Dallimi dhe padallueshmëria e gjendjeve CAV. Teorema e Moore
Leksion: Teorema e Anselit mbi ndarjen e një kubi n-dimensionale në zinxhirë. Një teoremë mbi numrin e funksioneve monotone në algjebrën e logjikës. Një teoremë për dekodimin e funksioneve monotone të algjebrës së logjikës. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksion: Makinat me gjendje të fundme me dalje (KAV). Funksionet automatike, metodat e caktimit të tyre. Një teoremë mbi transformimin e sekuencave periodike nga funksionet automatike. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva
Ligjërata: Komplete të renditura pjesërisht (PNS). Diagrami CHUM. Artikujt maksimalë, minimalë, më të mëdhenj dhe më të vegjël. Zinxhirët dhe antizinxhirët, gjatësia dhe gjerësia e PLS përfundimtare. Një teoremë mbi zbërthimin e PN në antizinxhirë.
Leksioni 2. Vetitë e koeficientëve binomialë. Llogaritja e shumave dhe mënyra e gjenerimit të funksioneve (rasti përfundimtar). Koeficientët polinomialë. Vlerësimet për koeficientët binomialë dhe polinomialë. Vlerësimet e shumës
Ligjërata: Algoritmi për njohjen e plotësisë në P k. Klasa të mbyllura. Klasat e funksioneve që ruajnë grupet dhe ruajtjen e ndarjeve, mbyllja e tyre. Teorema e Kuznetsov mbi plotësinë funksionale. Klasat parapërfundojnë.
Leksioni 2. Kombinatorika. Vetitë e koeficientëve binomialë. Llogaritja e shumave dhe mënyra e gjenerimit të funksioneve. Koeficientët polinomialë. Vlerësimet për koeficientët binomialë dhe polinomialë. Asimptotike
Leksion: Funksionet me vlerë të fundme. Funksionet elementare me vlerë k. Metodat për përcaktimin e funksioneve me vlerë k: tabela, formula, forma 1 dhe 2, polinome. Plotësia. Teorema mbi plotësinë e sistemit Post. Funksioni Webb.
Leksioni 3. Sekuencat e përcaktuara nga relacionet e përsëritjes. Ekuacione lineare të përsëritura homogjene dhe johomogjene (LORU dhe LNRU). Zgjidhjet e përgjithshme të LORU dhe LNRU. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksioni 15. Funksionet e logjikave me vlera të fundme. Funksionet elementare të logjikës me vlerë k. Metodat për përcaktimin e funksioneve logjike me vlerë k: tabelat, formulat, format I dhe II, polinomet. Plotësia. Ligjërues - Profesor i Asociuar Selezneva
Leksion: Funksionet e logjikave me vlera të fundme. Funksionet elementare të logjikës me vlerë k. Metodat për përcaktimin e funksioneve logjike me vlerë k: tabelat, formulat, format I dhe II, polinomet. Plotësia. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksion: Funksioni Möbius në PLM. Funksioni Möbius në kubin n-dimensionale. Formula e përmbysjes së Mobius. Parimi përfshirje-përjashtim. Problemi i llogaritjes së numrit të permutacioneve-shqetësimeve. Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksioni 2. Vetitë e koeficientëve binomialë. Mënyra e gjenerimit të funksioneve, llogaritja e shumave dhe vërtetimi i identiteteve. Koeficientët polinomialë. Parimi përfshirje-përjashtim. Ligjërues - Profesor i asociuar Svetlana Selezneva
Ligjërata: Funksionet thelbësore. Tre lema mbi funksionet thelbësore. Kriteri i plotësisë së Yablonsky. Kriteri i plotësisë së Slupeckit. Funksionet Scheffer. Ligjërues Profesor i asociuar Svetlana Nikolaevna Selezneva [email i mbrojtur]
Ligjërata: Numrat bazë kombinues. Vlerësime dhe asimptotika për numrat kombinatorë. Lektor - Profesor i asociuar Svetlana Nikolaevna Selezneva, Fakulteti i Matematikës Kompjuterike dhe Kibernetikës, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në faqen e internetit http://mk.cs.msu.su
Ligjërata: Vetitë e koeficientëve binomialë. Llogaritja e shumave dhe mënyra e gjenerimit të funksioneve (rasti përfundimtar). Koeficientët polinomialë. Vlerësimet për koeficientët binomialë dhe polinomialë. Vlerësimet për shumat e binomit
Leksion: Makinat me gjendje të fundme me dalje. Transformimi i sekuencave periodike nga makinat me gjendje të fundme me dalje. Dallimi i gjendjeve në makinat me gjendje të fundme me dalje. Thjeshtimi i makinerive. Lektor Selezneva
Ligjërata: Mbulesa e kompletit dhe mbulimi me matricë. Veshje gradient. Lema e mbulesës së gradientit. Vlerësimet për kardinalitetin e grupit të hijeve të një kubi n-dimensionale. Vlerësimet për gjatësinë e formave normale polinomike të funksioneve
Leksioni 5. Mbulimi i një grupi dhe mbulimi i një matrice. Veshje gradient. Lema e mbulesës së gradientit. Vlerësimet për kardinalitetin e grupit të hijeve të kubit Boolean. Kufijtë e gjatësisë për format normale polinomiale Boolean
Leksioni 3. Sekuencat e përcaktuara nga relacionet e përsëritjes. Ekuacione lineare të përsëritura homogjene dhe johomogjene (LORU dhe LNRU). Zgjidhjet e përgjithshme të LORU dhe LNRU. Shembuj Ligjërues - Profesor i Asociuar Selezneva
Leksioni 3. Marrëdhëniet mbi grupet. Vetitë. Formula përfshirje-përjashtim. Marrëdhënie ekuivalente. Marrëdhënie e pjesshme e rendit. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata mbi Modele Diskrete.
Leksioni 4. Veçoritë e logjikave shumëvlerore. Klasa e mbyllur, baza e klasës së mbyllur. Teoremat e Yanov dhe Muchnik mbi ekzistencën në logjika shumëvlerëshe të klasave të mbyllura pa bazë dhe klasave të mbyllura me të numërueshme
Ligjërata. Funksionet e argumentit natyror (rendit). Ekuacione lineare të përsëritura homogjene dhe johomogjene (LORU dhe LNRU). Zgjidhjet e përgjithshme të LORU dhe LNRU. Shembuj Ligjërues - Profesor i asociuar Svetlana Selezneva
Leksion: Numri kromatik i një grafiku. Kriteri për grafikun me dy ngjyra. Teorema mbi kufijtë e sipërm dhe të poshtëm për numrin kromatik të një grafi. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata mbi Modele Diskrete.
Ligjërata: Grafikët dhe rrjetet. Vlerësimi i numrit të pseudografëve me skaje q. Vlerësimi për numrin e pemëve me q skaje. Grafikët planarë. Formula e Euler-it për grafikët planarë. Numri më i madh i skajeve në grafikët planarë. Joplanariteti
Leksioni 1. Kombinatorika. Vendosje, ndërrime, vendosje me përsëritje, kombinime, kombinime me përsëritje. Numri i tyre. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Departamenti i Kibernernetikës Matematikore
Ligjërata: Sekuenca. Ekuacione lineare të përsëritura homogjene dhe johomogjene. Zgjidhje të përgjithshme të ekuacioneve lineare të përsëritura homogjene dhe johomogjene. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva
Leksioni 8. Ngjyrosje. Ekuivalenca e ngjyrave në lidhje me grupin. Funksionet prodhuese. Një seri numërimi për forma dhe një seri numërimi për funksionet. Teorema e Polias. Lektor Selezneva Svetlana Nikolaevna
Ligjërata: Ngjyrosje. Ekuivalenca e ngjyrimeve në lidhje me një grup ndërrimi. Teorema e Polias (rast i veçantë). Funksionet prodhuese. Një seri numërimi për forma dhe një seri numërimi për funksionet. Teorema
Leksioni 2. Format normale lidhore. Implicente, një nënkuptim i thjeshtë i një funksioni. Funksioni i shkurtuar CNF i algjebrës së logjikës. Metodat për ndërtimin e një CNF të shkurtuar. Lektor Selezneva Svetlana Nikolaevna [email i mbrojtur]
Modelet dhe metodat matematikore të sintezës logjike të VLSI Vjeshtë 2015 Leksioni 4 Plani i leksionit Optimizimi logjik i qarqeve logjike kombinuese Mënyra të ndryshme të paraqitjes së funksioneve të algjebrës logjike (FAL)
Ligjërata: Automata të fundme jo-përcaktuese (NFA) pa dalje. Një teoremë mbi koincidencën e klasave të grupeve të fjalëve të pranuara nga automatet e fundme përcaktuese dhe jopërcaktuese të fundme. Procedura
Leksioni 1. Mostrat. Vendosjet, ndërrimet, vendosjet me përsëritje, kombinimet, kombinimet me përsëritjet, numri i tyre. Shembuj. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata në lëndën Diskrete
Leksioni 1. Objektet kombinuese: përzgjedhje, rregullime, ndërrime, rregullime me përsëritje, kombinime, kombinime me përsëritje, numri i tyre. Numrat kombinatorë: faktorial, faktorial në rënie, binom
LEKTURA 4 SKEMA NGA ELEMENTET FUNKSIONALE 1. Përkufizimet themelore Para së gjithash, është e nevojshme të merret parasysh përbërja. Një funksion mund të konsiderohet si një "kuti e zezë" që ka një hyrje dhe një dalje. Le
Leksioni 2. Algoritmi për njohjen e plotësisë në P k. Teorema e Kuznetsov. Klasa të mbyllura. Klasat e funksioneve të ruajtjes së grupeve. Klasat e funksioneve të ruajtjes së ndarjes. Klasat parapërfundojnë. Pedagog Doktor i Shkencave Fizike dhe Matematikore Selezneva
Leksioni 3. Polinomi Zhegalkin. Metodat për ndërtimin e polinomit Zhegalkin për një funksion. Implikimi linear i funksionit. Forma normale lidhore lineare (LCNF). Gjetja e të gjitha implikimeve lineare të funksionit. Ekzaminimi
Leksioni 2. Gjenerimi i funksioneve: llogaritja e shumave kombinuese dhe vërtetimi i identiteteve, numërimi i objekteve kombinuese. Parimi përfshirje-përjashtim. Numërimi i numrit të permutacioneve-shqetësimeve. Ligjërues -
Leksioni 5. Grafikët. Ngjyrosja e grafikut. Numri kromatik i grafikut. Kriteri për grafikun me dy ngjyra. Kufijtë e sipërm për numrin kromatik të një grafiku. Pedagog Doktor i Shkencave Fizike dhe Matematikore Selezneva Svetlana Nikolaevna [email i mbrojtur] Ligjërata
Ligjërata: Automat e fundme (KA) pa dalje (njohës të automatave të fundme). Diagramet e tranzicionit. Komplete (gjuhë) automatike. Lemë mbi vetitë e grupeve automatike. Një shembull i një grupi jo-automatik. Ligjërues
Leksioni 1. Funksionet me vlerë të fundme. Funksionet elementare me vlerë k. Metodat për përcaktimin e funksioneve me vlerë k: tabela, formula, forma 1 dhe 2, polinome. Plotësia. Teorema mbi plotësinë e sistemit Post. Funksioni Webb.
Leksioni 7. Problemi i zgjedhjes së rrugëve dhe rasti i veçantë i tij është problemi i shpërndarjes së fluturimeve sipas ditës. Modeli grafik për problemin e shpërndarjes së fluturimit. Numri kromatik i grafikut. Kriteri për dyngjyrosje të grafikut.
Lënda "Bazat e Kibernetikës" për studentët e specializimit 02/01/09/01 (matematikore dhe softuerike për kompjuterë) 1. Informacion i përgjithshëm (ngarkesa e studimit, format e kontrollit, etj.). Kursi është
Leksioni 6. Grafikët. Vetitë e trashëguara të grafikëve. Vlerësimi i numrit të skajeve në grafikët me veti trashëgimore. Grafikët ekstremë. Numri më i madh i skajeve në grafikët planar dhe pa trekëndësh me një të dhënë
Math-Net.Ru Portali Matematikor Gjith-Rus D. S. Romanov, Një metodë për sintezën e qarqeve lehtësisht të testueshme që pranojnë teste të vetme kontrolluese me gjatësi konstante, Diskr. Mat., 2014, Vëllimi 26, Numri 2,
Leksioni: Makinat e gjendjes së fundme pa dalje, përcaktuese dhe jopërcaktuese. Një teoremë mbi koincidencën e klasave të grupeve të fjalëve të pranuara nga automata të fundme përcaktuese dhe jopërcaktuese. Procedura
Punë praktike 2 Ndërtimi i trajtave normale të një funksioni logjik Qëllimi i punës: Të mësojë të ndërtojë trajta normale lidhore, veçuese, të përsosura të një funksioni logjik Përmbajtja e punës: Themelore.
Seminar mbi kompleksitetin e funksioneve Boolean Leksioni 1: Hyrje A. Kulikov Klubi i Shkencave Kompjuterike në POMI http://compsciclub.ru 09/25/2011 25/09/2011 1/26 Plani i leksionit 1 Funksionet Boolean 2 Qarqet Boolean 3 Pothuajse
Punë praktike 1 Analizë dhe sintezë e sistemeve të kontrollit logjik dhe stafetë HYRJE Pajisjet me veprim diskret të bëra në elementët e hidro-, pneumo- dhe elektroautomatikës dhe mikroprocesorët e kontrollit
Ligjërata: Shprehje të rregullta dhe grupe të rregullta. Teorema e Kleene mbi koincidencën e klasave të grupeve automatike dhe grupeve të rregullta. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata në matematikë diskrete
Leksioni 3 Algjebrat e Bulit dhe funksionet e Bulit Algjebrat e Bulit Koncepti i sistemeve algjebrike Sistemi algjebrik ose struktura algjebrike një grup simbolesh të një alfabeti të caktuar (mbështetje) me një të dhënë.
Leksioni 5. Grafikët. Shembuj të aplikimeve të grafikëve. Problemi i transportit. Rrjedha e rrjetit, teorema e Fordit dhe Fulkerson mbi rrjedhën maksimale të rrjetit. Algoritmi për ndërtimin e fluksit maksimal në rrjet. Ligjërues
Ligjërata: Grafikët. Shembuj të aplikimeve të grafikëve. Problemi i transportit. Rrjedha e rrjetit, teorema e Fordit dhe Fulkerson mbi rrjedhën maksimale të rrjetit. Algoritmi për ndërtimin e fluksit maksimal në rrjet. Ligjërues -
Mësimi 8 Kujtoni se për bashkësitë arbitrare A dhe B ka bashkësi A B = (x x A dhe x B); (kryqëzimi i A dhe B) A B = (x x A ose x B); (bashkimi i A dhe B) A \ B = (x x A dhe x / B) (diferenca e A dhe B).
Leksioni 7. Numrat Ramsey. Kufiri i sipërm për numrin Ramsey. Kufiri i poshtëm për numrin Ramsey. Lektor Selezneva Svetlana Nikolaevna [email i mbrojtur] Fakulteti i CMC, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në faqen e internetit http://mk.cs.msu.ru
Ligjërata: Grafikët. Konceptet bazë. Grafikët e lidhur. Pemët. Pemë që përfshin. Numri i kulmeve të varura në pemën që shtrihet. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata mbi Modele Diskrete. Mjeshtër,
Leksioni 11. Skemat Boolean. Matematikë diskrete, HSE, Fakulteti i Shkencave Kompjuterike (Vjeshtë 2014 Pranverë 2015) Me një qark Boolean në variablat x 1, ..., x n nënkuptojmë një sekuencë të funksioneve Boolean g
I MIRATUAR Zëvendës Rektori për Çështjet Akademike Yu. A. Samarskiy 10 qershor 2008 PROGRAM DHE DETYRA për lëndën STRUKTURA DISKRETE në drejtimin 010600 Fakulteti i FIET Departamenti i Analizës së të Dhënave Kursi II semestri 4 Dy
Lomonosov Universiteti Shtetëror i Moskës Fakulteti i Matematikës Kompjuterike dhe Kibernetikës S. A. Lozhkin ELEMENTET E TEORISË SINTEZËS SISTEMEVE DISKRETE TË KONTROLLIT Moskë 2016 Tabela e përmbajtjes
Leksion: Vetitë e trashëguara të grafikëve. Grafikët ekstremë. Numrat Ramsey. Lektor - Profesor i asociuar Svetlana Nikolaevna Selezneva, Fakulteti i Matematikës Kompjuterike dhe Kibernetikës, Universiteti Shtetëror i Moskës me emrin M.V. Lomonosov Ligjërata në faqen e internetit http://mk.cs.msu.su Trashëgimia
Leksion: Veprimet në grupe automatike të fundme. Plotësimi, bashkimi, kryqëzimi, produkti dhe përsëritja e kompleteve të automatëve, automatizimi i tyre. Ligjërues - Profesor i asociuar Svetlana Nikolaevna Selezneva Ligjërata
Ministria e Federatës Ruse për Komunikimet dhe Informatizimin e Rajonit të Vollgës Akademia Shtetërore e Telekomunikacionit dhe Departamentit të Matematikës së Lartë të Informatikës Miratuar nga Këshilli Metodik i PSATI më 29 mars 2002
Leksioni 5. Ngjyrosja e skajeve të grafikut. Indeksi kromatik i grafikut. Indeksi kromatik i grafikëve dypalësh. Kufijtë e sipërm dhe të poshtëm për indeksin kromatik të një grafiku. Lektor Selezneva Svetlana Nikolaevna [email i mbrojtur]
Math-Net.Ru Portali matematikor gjithë-rus NP Red'kin, Në qarqet që pranojnë teste të shkurtra diagnostike të vetme, Diskr. Mat., 1989, vëllimi 1, numri 3, 71 76 Përdorimi i All-rusit
LOGJIKA MATEMATIKE (1) Detyra për ushtrime praktike 1. Algjebra e pohimeve Pohimi është një sasi që mund të marrë dy kuptime: e vërtetë dhe e gabuar. Thëniet tregohen në latinisht të madh
Diagramet funksionale (FS) janë krijuar për të transformuar informacionin logjik. Informacioni fillestar, i koduar në formën e sinjaleve diskrete, futet në hyrjet e qarkut `x n... Më pas ky informacion përpunohet dhe në formë diskrete lexohet nga daljet e qarkut `në m(n, m- numri i hyrjeve dhe daljeve të tij). Konsideroni FS që funksionojnë në logjikë me dy vlera dhe kanë një dalje ( m= 1). Transformimi i informacionit në to mund të specifikohet si funksion i algjebrës së logjikës në=f(x n). Në vend të elementeve rele në FS, përdoren elementë funksionalë (FE), të cilët, si rregull, zbatojnë funksione elementare logjike.
Përkufizimi.Analiza quhet ndërtimi i një formule për algjebrën e logjikës (nëse është e nevojshme, tabela e saj e vërtetësisë) për një FS të dhënë.
Për të ndërtuar një formulë sipas një skeme të caktuar, është e nevojshme të përfaqësohet marrëdhënia midis FE në FS në formën e zëvendësimeve në funksionet elementare përkatëse. Supozohet se përpunimi i informacionit kryhet në faza nga inputet në outpute. Në qarqet reale, përdoren elementë shtesë për të siguruar koordinimin kohor të funksionimit të të gjitha FS.
Analiza FS mund të kryhet në dy mënyra - nga inputet tek outputet dhe nga outputet tek inputet. Le të shqyrtojmë metodën e parë, duke përdorur përcaktime shtesë për lidhjet e qarkut të ndërmjetëm.
Shembulli 1.(&, Ú, Ø) merren si FE. Analizoni FE, struktura fizike e të cilit është dhënë në figurën 1.19.
Zgjidhje. Duke përcaktuar lidhjet e ndërmjetme të PV siç tregohet në figurë, ne përcaktojmë sinjalet që u korrespondojnë atyre hap pas hapi . Në këtë rast, ne kalojmë nga hyrjet e qarkut në daljen e tij.
Figura 1.19
HAPI 1. R=`y, Q = `z.
HAPI 2. X=x&R= x&`y, P=x& y, W=P&P= x&y&`z.
HAPI 3. Y=X&z=x&`y& z, U=P&z = x&y&z.
HAPI 4. Z = YÚ U=x&`y&zÚ x&y&z.
HAPI 5. F = ZÚ W=x&`y& zÚ x&y&zÚ x&y&`z.
Kështu, FS e konsideruar zbaton formulën e mëposhtme të algjebrës së logjikës:
F(x,y,z) = x&`y&zÚ x&y&zÚ x&y&`z.
Formula e gjetur është SDNF. Vektori i vlerave të tij të së vërtetës ka formën (00000111) .
Në varësi të të dhënave fillestare, ndër detyrat e sintezës (projektimit) të FS mund të dallohen:
1) sinteza e qarqeve sipas formulave të dhëna,
2) sinteza e qarqeve për funksionet e dhëna.
Përkufizimi.Me sintezën e PS sipas formulës së dhënë quhet ndërtimi i strukturës FS që i përgjigjet një formule të caktuar të algjebrës së logjikës.
Zgjidhja e problemeve të tilla kryhet sipas algoritmit të kundërt me metodën e analizës. Siç u përmend në seksionin 1.7, struktura e formulave të Bulit lejon që vetëm sistemet me lidhje paralele dhe sekuenciale të elementeve të hartohen në mënyrë izomorfike. Prandaj, FS, e cila është izomorfike me formulën përkatëse, duhet të përmbajë vetëm komponime të këtij lloji.
Përkufizimi.Me sintezën e një PS për një funksion të caktuar quhet ndërtimi i një diagrami strukturor që zbaton një funksion të caktuar të algjebrës së logjikës.
Duke qenë se paraqitja e funksioneve me formula është e paqartë, ky problem ka një zgjidhje jo unike. Ashtu si në rastin e qarqeve rele, ato optimale janë FS, të përbërë nga një numër minimal i PV-ve dhe lidhjeve ndërmjet tyre. FS të tilla mund të merren duke përdorur formula me një numër minimal variablash.
Sa i përket PC-së, ne do të shqyrtojmë veçmas formulat që janë optimale në klasën e formave normale (të cilat janë të barabarta me format minimale përkatëse), si dhe formulat absolutisht optimale të marra nga format minimale normale duke i reduktuar më tej ato duke përdorur ligjet e algjebrës logjike. . Metodat për marrjen e formulave optimale janë të njëjta si në qarqet rele. Shembulli 1 merr në konsideratë FS që zbaton funksionin (00000111) . Ky FS nuk është optimal, pasi formula përkatëse përshkruan SDNF F = x`y z Ú x y zÚ x y`z e cila nuk është minimale. Duke e minimizuar atë, marrim një MDNF të formës së mëposhtme: F = x yÚ x z. Ai korrespondon me FS në Fig. 1.20.
Figura 1.20
Nëse zbatojmë ligjin shpërndarës në MDNF, atëherë marrim një formulë me edhe më pak variabla: f = x(yÚ z). Për këtë funksion, ajo përkoi me MCNF. Një skemë absolutisht optimale i korrespondon asaj.
Figura 1.21
Natyrisht, kjo skemë është shumë më e thjeshtë se ajo origjinale (Figura 1.19). Meqenëse sinteza e FS optimale reduktohet në ndërtimin e formulave minimale, skemat optimale në bazat e tjera gjithashtu ndërtohen në mënyrë të ngjashme. Analogët e ligjeve të parë dhe të dytë shpërndarës të algjebrës së logjikës për format Scheffer dhe Web mund të merren duke zëvendësuar në këto ligje:
&(x,y)= Ø ½ ( x,y) = ¯ (Ø x,Ø y);
Ú ( x,y)= ½ (Ø x, Ø y) =Ø ¯ ( x,y).
Shembulli 2. Ndërtoni një FS që zbaton një grumbullues binar njëbitësh të dy numrave duke përdorur një FE që korrespondon me bazën (Ø, ¯), si dhe në bazën (¯).
Zgjidhje. Le të shënojmë numra binarë njëbitësh të dhënë në hyrje përmes ( X,në). Prodhimi duhet të jetë shuma e tyre në sistemin binar. Nëse x = 1, y = 1, pastaj S = 2 10 = 10 2, prandaj, për ta shfaqur atë, në rastin e përgjithshëm, është e nevojshme të përdoren dy shenja binare, dhe FS duhet të ketë dy dalje. Le t'i shënojmë ato f(shifra më domethënëse e shumës) dhe g(pak i rëndësishëm). Tabelat e së vërtetës së funksionit f (X,në),g(X,në):
| x | y | f(x,y) | g(x,y) |
Ne ndërtojmë SVNF të funksioneve në bazë (Ø, ¯). f ka një njësi në vektorin e së vërtetës, prandaj forma e tij përbëhet nga një përbërës: f= ¯ (Ø x, Ø në). Funksioni g SVNF ka formën: g=د(¯( X,Ø në),¯(Ø X,në)). Këto forma janë minimale. Kur kombinohen hyrjet e elementeve, diagrami funksional mund të paraqitet si më poshtë:
Figura 1.22
Në shembullin e konsideruar, është e pamundur të thjeshtohen format normale të Uebit duke përdorur ligjet e algjebrës logjike. Në një bazë me një funksion (¯) FS, marrim, duke përdorur zëvendësimin Ø X= ¯ ( X,X). Qarku përkatës është paraqitur në figurën 1.23.
Figura 1.23
DETYRAT
1. Ndërtoni duke përdorur FE (&, Ú, Ø) optimale në klasën e formave normale dhe FS absolutisht optimale që zbatojnë funksionet e mëposhtme:
a) ( x® y)Å z y; b) ( xÅ y)|z,v) xy® yz;G) x|(yÚ z); e) x®( y® z) ;
f) (10011101); g) (01101011); h) (1110101111111110) .
2. Ndërtoni duke përdorur funksionet FE (Ú, Ø) FS 1.a) -g).
3. Ndërtoni duke përdorur funksionet FE (&, Ø) FS 1.a) -g).
4. Ndërtoni një FS që zbaton një grumbullues binar njëbitësh (Shembulli 2) duke përdorur një FE të formës së mëposhtme:
a) (&, Ú, Ø), b) (Ú, Ø) , c) (&, Ø), d) ( x | y} .
5. Me ndihmën e FE (&, Ú, Ø), ndërtoni FS-në e pajisjeve të mëposhtme:
a) një konvertues me hyrje binare ( X,në), dhe dilni f e cila funksionon kështu: kur ushqehet x = 0 në dalje f =në, dhe kur shërbeni x = 1 në hyrje f =`y;
b) një pajisje selektive me hyrje binare ( X,në) dhe daljet f 0 , f 1 , f 2 , f 3, i cili pranon në hyrje një kombinim vlerash ( x y) si një numër binar i, shtrirë në intervalin nga 0 në 3. Vlerat e rezultateve për secilën i në vijim: f i= 1, dhe të gjithë të tjerët f j= 0, (0 £ j 3 £, j¹ i).
6. A është e mundur të merren grupet e mëposhtme të funksioneve si bazë për ndërtimin e FS:
a) (1001), (10001110),
b) (0101), (1011), (1101),
c) (1010), (01110001)?
Arsyetoni përgjigjen.
7. Jepni shembuj të funksioneve të kontrollit, FS e të cilave nuk mund të ndërtohet vetëm nga FE e tipit (®).
8. Jepni shembuj të funksioneve të kontrollit, FS e të cilave nuk mund të ndërtohet vetëm nga FE e tipit (M, º).
9. Dana FS nga FE (&, Ú, Ø).
Figura 1.24
Nëse është e mundur të përjashtohen prej tij me anë të transformimeve ekuivalente:
a) të gjithë elementët (Ø)?
b) të gjithë elementët (&)?
c) të gjithë elementët (Ú)?
10. Optimizoni FS nga FE (&, Ú, Ø), të paraqitur në Fig. 1.25.
Figura 1.25
Ndërtoni FS:
a) optimale në klasën e formave normale dhe
b) absolutisht optimale.
31. Diagramet e elementeve funksionale, rregullat e ndërtimit dhe funksionimit, metoda e sintezës së SFE, bazuar në SDNF dhe SKNF.
PërkufizimiPërkufizimi. Një element funksional është një model matematikor i një konverteri elementar diskret, i cili, sipas një ligji të caktuar, konverton sinjalet që vijnë tek ai në hyrje në një sinjal në dalje të konvertuesit. Nga elementet funksionale, me ndihmën e disa rregullave, është e mundur të ndërtohen modele më komplekse në strukturë dhe funksionim - diagrame nga elementë funksionalë. Në këto modele, sinjalet hyrëse dhe dalëse janë të koduara me karakteret 0 dhe 1.
Rregullat e ndërtimit. Për të marrë SFE komplekse nga më të thjeshtat, zbatohen në mënyrë sekuenciale operacionet e ndarjes së hyrjes ose daljes së qarkut, lidhjes së elementit funksional me qarkun dhe lidhjes së elementit funksional me hyrjen ose daljen e qarkut. Këto operacione ngjajnë me rregullat për marrjen e një formule komplekse nga ato më të thjeshta duke përdorur mbivendosje.
Sinteza e SFE. Meqenëse disjunksioni, lidhja dhe mohimi formojnë një sistem të plotë në klasë R 2, pastaj çdo funksion Boolean të n argumentet mund të zbatohen nga një qark i elementeve funksionale - ndarës, lidhës dhe inverter - me n hyrjet dhe një dalje. Për ta bërë këtë, për shembull, mund të shprehni këtë funksion Boolean përmes SDNF ose SKNF dhe më pas të "sintetizoni" formulën që rezulton në formën e një qarku elementësh funksionalë, duke zbatuar në mënyrë sekuenciale operacionet e ndarjes, bashkimit dhe lidhjes së mësipërme.
32. Metoda e sintezës së SFE, bazuar në zbatimin kompakt të të gjitha lidhjeve duke përdorur një multipol universal, kompleksitetin e qarqeve që rezultojnë.
Përkufizimi... Një funksion argumenti quhet një funksion Boolean (ose një funksion Boolean) nëse i cakton një numër çdo grupi.
Për të përcaktuar funksionet Boolean, ne do të përdorim tabela, vektorë, formula dhe grafikë. Le të marrim shënimin e mëposhtëm: është bashkësia e të gjitha grupeve, ku.
Përkufizimi. Një element funksional është një model matematikor i një konverteri elementar diskret, i cili, sipas një ligji të caktuar, konverton sinjalet që vijnë tek ai në hyrje në një sinjal në dalje të konvertuesit. Nga elementet funksionale, me ndihmën e disa rregullave, është e mundur të ndërtohen modele më komplekse në strukturë dhe funksionim - diagrame nga elementë funksionalë. Në këto modele, sinjalet hyrëse dhe dalëse janë të koduara me karakteret 0 dhe 1.
Metoda për sintezën e SFE, bazuar në zbatimin kompakt të të gjitha lidhjeve duke përdorur një shumëpolësh universal. Kjo metodë bazohet gjithashtu në paraqitjen e një funksioni në formën e SDNF, por lejon që dikush të ndërtojë qarqe më pak komplekse për shkak të një zbatimi më kompakt të lidhjeve. Zbërthimi i një funksioni në SDNF mund të përmbajë lidhje që kanë faktorë të përbashkët. Nëse dy lidhje të tilla zbatohen në një nënqark në një bllok, atëherë kjo do të kërkojë të paktën një lidhës më pak seç kërkohej më parë, me zbatimin e pavarur të të gjitha lidhjeve me metodën e parë të sintezës. Një zbatim kompakt i të gjitha lidhjeve të mundshme të gjatësisë n mund të arrihet duke përdorur një shumëpolësh universal të ndërtuar në mënyrë induktive, i cili ka n hyrjet dhe 2 n daljet ku n = 1,2,3, ... Përparësitë e metodës janë veçanërisht të dukshme kur një qark duhet të zbatojë një sistem me disa funksione Boolean. Në këtë rast, do të ishte e mundur që të ndahen dhe më pas të kalohen përmes ndarësve ato dalje të multipolit universal që korrespondojnë me lidhëzat e përfshira në SDNF të funksioneve të sistemit të caktuar. Kjo do të bënte të mundur arritjen me më pak lidhorë sesa nëse secili funksion i një sistemi të caktuar do të zbatohej në mënyrë të pavarur nga nënqarku i tij.
Kompleksiteti i një multipoli të tillë është L() =.
Nëse një qark portash Σ përmban saktësisht r elementet funksionale, atëherë thonë se ka kompleksitet r dhe shkruajeni në formën e barazisë L(Σ) = r.
| " |
