Reprezentării funcțiilor booleene prin formule i se poate da următorul sens „ingineresc-constructiv”. Vom considera formula Ф(x 1 ,..., x n) peste o mulțime F fixă ​​arbitrar ca o „cutie neagră”, un fel de dispozitiv care primește toate seturile posibile de valori variabile la intrare și valorile ​​a funcției f corespunzătoare acestor mulțimi apar la ieșire , reprezentată prin formula Ф (Fig. 6.22).

Pentru a înțelege cum funcționează „cutia neagră”, trebuie să analizăm procesul de construire a unei formule din subformule. A ajunge la subformulele „de bază”, de ex. elemente ale mulțimii F, ajungem la „cărămizi”, elementele structurale din care este asamblată „cutia neagră”, care calculează funcția f. Fiecare funcție a „bazei” F este calculată de „nodul” corespunzător, care este considerat cea mai mică unitate structurală a „cutiei negre” noastre, iar structura sa internă nu mai este analizată.

Exemplul 6.22. Să alegem o bază standard ca mulțime F. Apoi formula pe baza standard reprezentând funcția ~ (echivalență) este construită după cum urmează:

Calculul prin această formulă (și procesul construcției sale din elementele bazei standard) poate fi reprezentat schematic așa cum se arată în Fig. 6.23.

Variabila x 1 (mai precis, valoarea acestei variabile) este alimentată la intrarea unui element structural numit invertor (Fig. 6.24, a) și calculând negația. Negația x 1 eliminată de la ieșirea invertorului, adică. funcția x 1, este alimentată la una dintre intrările conjunctorului (Fig. 6.24, b), a cărei a doua intrare este alimentată cu o variabilă x 2. Funcția x 1 x 2 apare la ieșirea conjunctorului. În mod similar, se urmărește calculul funcției x 1 x 2. Ambele aceste funcții sunt alimentate la intrările disjunctorului (Fig. 6.24, c), de la ieșirea căruia funcția x 1 x 2 ∨ x 1 x 2 este eliminat (aceasta nu este altceva decât suma modulo 2: x 1 ⊕ x 2). Și în final, această funcție este alimentată la intrarea invertorului, la ieșirea căruia funcția ~ (echivalență) este deja obținută. #

Astfel, ajungem la ideea unui „circuit” - un model matematic al unui calculator cu funcții booleene, reprezentat de o formulă, asamblată din elemente structurale, fiecare dintre acestea calculând una dintre funcțiile booleene „de bază”. În cazul general, „circuitul” calculează un operator boolean, iar fiecare funcție de coordonată a acestui operator este preluată de la una dintre ieșirile circuitului.

Din punct de vedere matematic, un „circuit” este definit ca un tip special de graf direcționat în care atât vârfurile, cât și arcele sunt prevăzute cu niște etichete.

Să introducem notația: dacă F este o mulțime de funcții booleene, atunci prin F (n) notăm submulțimea lui F, constând din toate funcțiile a n variabile (n≥0).

Definiția 6.14. Să fie fixe mulțimile: F (funcții booleene) și X (variabile booleene).

O schemă de elemente funcționale pe o bază F ∪ X (С Ф Э), sau pur și simplu o contracție asupra bazei F ∪ X, de asemenea o schemă (F,X), se numește un graf direcționat fără contur (adică o rețea), fiecare vârf al căruia este etichetat cu unul dintre elementele mulțimii F U X, astfel că sunt îndeplinite următoarele cerințe:

1. fiecare intrare a rețelei este etichetată fie cu o variabilă din X, fie cu o constantă din F (0);
2. dacă un vârf v al unei rețele este etichetat printr-o funcție f de n variabile (adică f ∈ F (n)), atunci gradul său este egal cu n, iar pe mulțimea de arce care intră în vârful v, a ( numerotarea unu-la-unu) este dată astfel încât fiecare arc să primească un număr de la 1 la n.

Dacă baza este implicită, atunci vom spune pur și simplu „schemă”. În plus, dacă setul de variabile este fix „o dată pentru totdeauna” și, când luăm în considerare diverse scheme, schimbăm doar setul de funcții F, atunci, așa cum am făcut atunci când am introdus conceptele de formulă și suprapunere pe o bază dată, vom vorbi despre CFE pe baza F, setarea de fiecare dată, ceea ce implică un set fix de variabile X, care (dacă nu dăunează preciziei) nu este menționat.

Definim acum prin inducție noțiunea funcţie booleană calculată de vârful circuitului .

Definiția 6.15. Să fie dat SFE S pe o bază F ∪ X a cărei mulțime de vârfuri este V.

1. Se presupune că fiecare intrare SFE calculează o funcție booleană cu care este etichetată (adică o variabilă sau constantă).
2. Dacă un vârf v ∈ V este etichetat de o funcție f ∈ F (n) , un arc cu numărul i (1≤i≤n) care intră în el provine dintr-un vârf u i ∈ V care calculează funcția g i , atunci vârful v calculează suprapunerea f(g 1 , ... ,gn).

Astfel, dacă fiecare vârf CFE peste F calculează o funcție, atunci ordinea în care sunt enumerate funcțiile g 1 , ...,g n, care sunt înlocuite cu variabilele funcției f, este în general semnificativă. Este firesc să numim comutativă o funcție booleană f de n variabile dacă își păstrează valoarea sub o permutare arbitrară a variabilelor sale. În acest caz, s-ar putea să nu ne pese de numerotarea arcelor care intră în vârful circuitului etichetat cu o astfel de funcție.

Exemplul 6.23. Să luăm în considerare SFE în fig. 6.25. Vârfurile v 1 și v 2 sunt intrările SFE. Aceste vârfuri calculează funcțiile x și respectiv y. Apoi vârful v 3 , precum și vârful v 4 , conform definiției 6.15, calculează funcția x|y (cursa Schaeffer), iar vârful v 5 (ieșirea rețelei) calculează funcția (x|y)l( x|y), care se știe a fi egală cu conjuncția x · y.

SFE prezentat în Fig. 6.26, are două ieșiri, calculând funcțiile (x|x)|(y|y) = x ∨ y și (x|y)|(x|y) = x·y.

Definiția 6.16. Funcție booleană calculată de SFE pe baza F ∪ X, este o funcție calculată de oricare dintre ieșirile sale.

Astfel, SFE calculează exact funcțiile booleene stmko, câte ieșiri are. SFE în fig. 6.25 calculează o funcție, iar SFE din fig. 6.26 - doi.

În general, dacă (x 1 ,..., x n ) este mulțimea tuturor variabilelor care servesc ca etichete pentru intrările circuitului S pe baza F ∪ Х, care are m ieșiri, CFE S definește afișarea unui cub boolean B n cub boolean B m , adică operator boolean.

Observația 6.10.În unele cazuri, funcția calculată de un anumit CFE este definită oarecum diferit, presupunând că este o funcție calculată de orice vârf dintr-un subset de vârfuri CFE selectate. În special, pot fi ieșiri. În orice caz, să fim de acord să desenăm o săgeată de „ieșire” din vârfurile selectate (în sensul tocmai indicat) ale schemei. #

Astfel, fiecare circuit de elemente funcționale calculează un anumit operator boolean, în special, dacă numărul de ieșiri ale circuitului este 1, atunci calculează o funcție booleană.

Se poate demonstra și invers: pentru orice operator boolean, un SFE poate fi construit pe baza F, unde F este mulțimea completă care evaluează operatorul dat.

Să reprezentăm funcția y 1 în baza Zhegalkin. Folosind legile lui de Morgan, obținem

(amintim că suma modulo 2 a oricărui număr par de termeni egali este 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 pentru operatorul boolean specificat în tabel. 6.9, peste baza Zhegalkin este prezentată în Fig. 6.27.

Când proiectați un SPV, este util să aveți în vedere un parametru numeric numit complexitatea acestuia.

Complexitatea SFE este numărul vârfurilor sale care nu sunt intrări.

Arată în fig. 6.27 CFE pe baza Zhegalkin are complexitate 5.

Să luăm acum în considerare CFE pentru același operator pe baza standard.

Conform tabelului (vezi Tabelul 6.9), construim SDNF pentru funcția 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.

Harta Carnot pentru această funcție, prezentată în Fig. 6.28 arată că nu poate fi minimizat (mai precis, SDNF scris mai sus este DNF minim pentru această funcție). Dar poți merge pe altă cale. Putem lua în considerare Tabelul. 6.9 ca un tabel care definește o funcție booleană parțială y 2 = y 2 (x 1 x 2 x 3 y 1). Prin minimizarea acestei funcții

harta Carnot* reprezentată în fig. 6.29, obținem

* Pe această hartă am marcat mulțimile pe care funcția ia valoarea 0 punând zerouri în celulele corespunzătoare. Astfel, dorim să atragem încă o dată atenția asupra faptului că zerourile nu trebuie confundate cu liniuțele: o liniuță într-o celulă a unei hărți care definește o funcție parțială înseamnă că valoarea funcției nu este definită pe această mulțime, adică. nu este nici 0, nici 1.

y 2 \u003d x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).

SFE peste baza standard pentru operatorul boolean considerat este prezentat în Fig. 6.30. Complexitatea acestui CFE este 11. Rețineți că nodul care calculează funcția y 1 nu este o ieșire.

Operatorul boolean discutat în acest exemplu calculează suma de două cifre (modulo 2) a trei termeni de o cifră. De asemenea, poate fi considerat un sumator binar pe un singur bit - un bloc funcțional al unui sumator binar pe mai mulți biți - pentru doi termeni. Apoi funcția y 1 este interpretată ca un „semnal de transport” la cel mai înalt nivel. Pe fig. Figura 6.31 prezintă o „conexiune” a trei SFE (cum ar fi figura 6.30), care calculează suma a două numere binare de trei cifre. O constantă 0 este aplicată celei de-a treia intrări a sumatorului pentru bitul cel mai puțin semnificativ, iar „semnalul de transport” al bitului cel mai semnificativ este bitul cel mai semnificativ al sumei, care în cazul general va fi un număr de patru cifre .

Observația 6.11. Dacă proiectăm un SFE pe o bază standard și dorim să îi minimizăm complexitatea, atunci trebuie mai întâi să construim DNF-ul minim corespunzător. În acest caz, putem lua în considerare încă un criteriu prin care DNF-ul în sine este minimizat - numărul de negații. Dintre toate DNF-urile minime (în sensul Definiției 6.6), ar trebui să se selecteze cele în care numărul de apariții ale variabilelor sub semnul negației este cel mai mic. Din punct de vedere al complexității CFE, care va fi construit conform DNF minim, aceasta înseamnă că minimizează numărul de „invertoare” - vârfuri CFE etichetate cu o funcție de negație.

De exemplu, pentru o funcție dată de harta Carnot (Fig. 6.32), la nucleul format din implicanți simpli x 1 x 2 x 4 și x 1 x 3 x 4, ar trebui să adăugați un implicant simplu x 2 x 3 x 4 , și nu x 1 x 2 x 3 deoarece nu conține negații.

Dimensiune: px

Începeți impresia din pagină:

transcriere

1 Curs 2. Scheme de elemente funcționale (SFE) în anumite baze. Complexitatea și profunzimea schemei. Exemple. Metodă pentru sinteza SFE prin DNF. Lector - Conf. univ. Svetlana N. Selezneva Prelegeri de matematică discretă 2. Anul I, grupa 141 Lomonosov Prelegeri pe site

2 Circuite din elemente funcționale Să definim circuite din elemente funcționale într-o anumită bază. Să ne dăm un set de funcții booleene B = (g 1 (x 1,..., x n1),..., g s (x 1,..., x ns)) P 2, unde n 1, .. ., n s 0. Numim acest set o bază. Rețineți că acest concept de bază nu este în nici un fel legat de conceptul de bază P 2, care a fost considerat în algebra logicii. De regulă, vom lua în considerare baza standard B 0 = (x&y, x y, x).

3 Definiția unui circuit de elemente funcționale Un circuit de elemente funcționale (SFE) în baza B 0 = (x&y, x y, x) este 1) un grafic aciclic direcționat G = (V, E), fiecare vârf v V din care are un grad în d (v ) care nu depășește doi (d (v) 2); 2) fiecare vârf v cu un grad în egal cu 0 (d (v) = 0) se numește intrare (sau intrare în circuit) și îi este atribuită o variabilă booleană x i; 3) toate celelalte vârfuri (cu excepția intrărilor) sunt numite vârfuri interne ale circuitului;

4 Definirea unui circuit din elemente funcţionale (continuare) 4) fiecărui vârf v cu un grad în egală cu 1 (d (v) = 1) i se atribuie un element de negaţie (funcţional); toate astfel de vârfuri se numesc invertoare; 5) fiecărui vârf v cu un grad în egală cu 2 (d (v) = 2) i se atribuie fie un element de conjuncție (funcțional) & fie un element de disjuncție (funcțional); toate vârfurile cărora le sunt alocate elemente ale unei conjuncții se numesc conjunctori, toate vârfurile cărora le sunt alocate elemente ale unei conjuncții se numesc disjunctori;

5 Definirea unui circuit din elemente funcționale (continuare) 6) în plus, unora dintre vârfuri sunt atribuite diferite variabile de ieșire y 1,..., y m în perechi. Dacă este dat un CFE S, ale cărui intrări sunt alocate doar variabile x 1,..., x n, și cu variabile de ieșire y 1,..., y m, atunci vom nota acest CFE prin S(x 1,. .., x n ; y 1,..., ym).

6 Exemplu de SFE Exemplul 1. SFE S(x 1, x 2, x 3 ; y 1, y 2, y 3):

7 Exemplu de SFE Exemplul 1. De regulă, SFE sunt reprezentate după cum urmează S(x 1, x 2, x 3; y 1, y 2, y 3):

8 Determinarea complexității CFE Complexitatea L(S) a CFE S este numărul de vârfuri interne ale acestui CFE, i.e. numărul de elemente funcționale din SFE S.

9 Complexitatea SPE Exemplul 2. Complexitatea SPE S:

10 Determinarea adâncimii unui vârf CFE Prin inducție, determinăm adâncimea d(v) a unui vârf v în CFE S. 1. Baza inducției. Fiecare intrare v a SPS are o adâncime egală cu 0: d(v) = tranziție inductivă. 1) Dacă un arc de la vârful v 1 duce la invertorul v CFE S, atunci d(v) = d(v 1)) Dacă arcurile de la vârfurile v 1 și v 2 duc la conjunctorul sau disjunctorul v CFE S, atunci d (v) = max(d(v 1), d(v 2)) + 1. Adâncimea D(S) a unui CFE S este maximul adâncimii vârfurilor sale.

11 Adâncimea SPE Exemplul 3. Adâncimea vârfului SPE S și adâncimea SPE S:

12 Determinarea funcționării SFE În fiecare vârf al SFE, o anumită funcție booleană este implementată (sau calculată). Prin inducție, definim o funcție booleană care este implementată la vârful v al CFE S. 1) Dacă v este un vârf de intrare și i se atribuie variabila x i, atunci funcția f v = x i este realizată la vârful v . 2) Dacă un arc de la vârful v 1 duce la invertorul v, iar funcția f v1 se realizează la vârful v 1, atunci funcția f v = f v1 se realizează la vârful v. 3) Dacă arcuri de la vârfurile v 1 și v 2 duc la conjunctor (sau disjunctor) v, iar funcțiile f v1 și f v2 sunt realizate la vârfurile v 1 și, respectiv, v 2, atunci funcția f v = f v1 &f v2 este realizată la vârful v ( respectiv f v = f v1 f v2).

13 Funcționarea SFE Se crede că SFE S(x 1,..., x n ; y 1,..., y m) implementează un sistem de funcții booleene F S = (f 1,..., f m ) implementat în vârfurile sale de ieșire y 1,..., ym.

14 Funcționarea SFE Exemplu 4. Funcții booleene implementate în vârfurile SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3 ).

15 Program liniar Program liniar cu intrări x 1,..., x n peste bază B 0 = (x&y, x y, x) este o succesiune z 1, z 2,..., z t, în care pentru fiecare număr j, j = 1,..., t, 1) fie z j = x i ; 2) fie z j = z k pentru 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 programe liniare Este clar că calculul în CFE poate fi rescris sub forma unui program liniar. Și invers, fiecare program liniar poate fi reprezentat ca un anumit CFE.

17 SFE și programe liniare Exemplul 5. SFE S corespunde unui program liniar z 1 = x 1 &x 2, z 2 = x 3, z 3 = z 1 z 2.

18 SFE și caracteristicile lor Schemele elementelor funcționale sunt un model de calcul. Caracteristicile SPE introduse de noi arată diferite aspecte ale eficienței computaționale. Complexitatea SFE corespunde timpului de calcul secvenţial. Adâncimea SPE corespunde timpului de calcul paralel. Numărul maxim de vârfuri cu aceeași adâncime în CFE corespunde numărului de procesoare din calculul paralel.

19 Exemplu: suma a doi biți Exemplul 6. Construiți un SFE pe o bază standard care implementează (calculează) suma a doi biți x și y. Soluţie. Să scriem un tabel cu suma a doi biți x și y. Această sumă poate fi un număr cu două cifre binare, așa că introducem două variabile booleene z 0, z 1 astfel încât x + y = 2z 1 + z 0: x y z 1 z

20 Exemplu: suma a doi biți Soluție (continuare). Atunci z 0 = x y, z 1 = xy. Ținând cont de faptul că x y = (x y) (x y), obținem CFE: Este clar că L(S 1) = 3 și D(S 1) = 3.

21 CFE în bază arbitrară În mod similar, este introdus conceptul de CFE în bază arbitrară B P 2.

22 Exemplu: suma a trei biți Exemplul 7. Construiți un SFE în baza P2 2 (adică din toate funcțiile booleene în funcție de două variabile) realizând (calculând) suma a trei biți x, y și z.

23 Exemplu: suma a trei biți Soluție. Similar exemplului 6, scriem un tabel cu suma a trei biți x, y și z. Această sumă poate fi și un număr cu două cifre binare, așa că introducem două variabile booleene u 0, u 1, astfel încât x + y + z = 2u 1 + u 0: x y z u 1 u

24 Exemplu: suma a trei biți Soluție (continuare). Atunci u 0 = x y z, u 1 = xy xz yz. Ținând cont de faptul că xy xz yz = xy z(x y), obținem CFE: Vedem că L(S) = 5 și D(S) = 3.

25 Implementarea funcției booleene a CFE Este posibil să se implementeze o funcție booleană arbitrară (sau un sistem de funcții booleene) a CFE în baza B 0 = (x&y, x y, x)? Poate sa. Cum poate fi justificat acest lucru? De exemplu, da. pentru că (x&y, x y, x) este un sistem complet în P 2, o funcție booleană arbitrară f poate fi reprezentată printr-o formulă numai prin conjuncție, disjuncție și negație. De exemplu, sub forma unui DNF perfect, dacă f 0, și sub forma x & x, dacă f = 0. Și apoi, folosind această DNF (formulă), construiți CFE-ul corespunzător. Această metodă de construire a SFE pentru funcții booleene se numește metoda de sinteză a DNF.

26 Sinteza CFE prin DNF Și ce complexitate va avea CFE S prin DNF pentru o funcție booleană f (x 1,..., x n) în funcție de n variabile? Un DNF perfect pentru o funcție f va conține cel mult 2 n conjuncții elementare. Fiecare conjuncție elementară este o conjuncție de n variabile sau negațiile acestora.

27 Sinteza SFE prin DNF Prin urmare, circuitul va avea: n invertoare pentru a implementa toate negaţiile variabilelor x 1,..., x n ; prin (n 1) conjunctor pentru a implementa fiecare dintre cel mult 2 n conjuncții elementare într-un DNF perfect; cel mult (2 n 1) disjunctor pentru implementarea disjuncției conjuncțiilor elementare ale DNF. Obținem că L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n.

28 Complexitatea unei funcții booleene Complexitatea L(f) a unei funcții booleene f (x 1,..., x n) din clasa CFE este complexitatea minimă dintre toate CFE-urile care implementează funcția f. Astfel, am demonstrat teorema: Teorema 1. Pentru o funcție arbitrară f (x 1,..., x n) P 2, L(f) n 2 n + n este adevărată.

29 Probleme pentru soluția independentă 1. Pentru o funcție booleană f (x 1, x 2, x 3) = (), construiți un CFE în baza standard de complexitate Pentru o funcție booleană f (x 1, x 2, x 3) = (), construiți un CFE in în baza de complexitate standard Pentru o funcție booleană f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, construiți un SFE în baza standard de adâncime Demonstrați că în baza standard L(x y) = 4.

30 Literatură pentru prelegere 4 1. Yablonsky S.V. Introducere în matematica discretă. M .: Liceu, Partea a V-a, cap. 2, cu Gavrilov G.P., Sapozhenko A.A. Sarcini și exerciții de matematică discretă. Moscova: Fizmatlit, Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.

31 Sfârșitul cursului 4

Curs: Scheme de elemente funcționale cu întârzieri (SFES), automatizarea mapărilor acestora. Reprezentarea KAV FEZ. Simplificari ale CAV. Distinctitudinea și indistingerea stărilor CAV. teorema lui Moore

Prelegere: Teorema lui Ansel privind împărțirea unui cub n-dimensional în lanțuri. Teorema privind numărul de funcții monotone ale algebrei logicii. Teoremă privind descifrarea funcțiilor monotone ale algebrei logicii. Lector - Conf. univ. Selezneva Svetlana

Prelegere: Automate finite cu ieșire (KAV). Funcții automate, metode de atribuire a acestora. Teorema de transformare a secventelor periodice prin functii automate. Lector - conferențiar Svetlana Nikolaevna Selezneva

Curs: Seturi parțial comandate (POS). Diagrama CHUM. Elemente maxime, minime, cele mai mari și cele mai mici. Lanțuri și anti-lanțuri, lungimea și lățimea sfârșitului ciumei. Teorema despre împărțirea PL în antilanțuri.

Cursul 2. Proprietățile coeficienților binomi. Însumarea și metoda de generare a funcțiilor (cazul final). Coeficienți polinomi. Estimări pentru coeficienți binomi și polinomi. Estimări de sumă

Prelegere: Algoritm pentru recunoașterea completității în P k. clase închise. Clase de funcții care păstrează seturile și păstrează partițiile, închiderea lor. Teorema lui Kuznețov asupra completității funcționale. Cursuri precompletate.

Curs 2. Combinatorică. Proprietățile coeficienților binomi. Numărarea sumelor și metoda de generare a funcțiilor. Coeficienți polinomi. Estimări pentru coeficienți binomi și polinomi. Asimptotic

Curs: Funcții cu valori finite. Funcții elementare cu valori k. Modalități de specificare a funcțiilor cu valori k: tabele, formule, formele I și II, polinoame. Completitudine. Teorema privind completitudinea sistemului Post. Funcția Webb.

Curs 3. Secvenţe determinate de relaţii recurente. Ecuații liniare recurente omogene și neomogene (LORU și LNRU). Deciziile comune ale LORU și LNRU. Lector - Conf. univ. Selezneva Svetlana

Curs 15. Funcţiile logicii cu valori finite. Funcții elementare ale logicii cu valori k. Metode de specificare a funcțiilor logice cu valori k: tabele, formule, forme I și II, polinoame. Completitudine. Lector - Conf. univ. Selezneva

Curs: Funcţiile logicii cu valori finite. Funcții elementare ale logicii cu valori k. Metode de specificare a funcțiilor logice cu valori k: tabele, formule, forme I și II, polinoame. Completitudine. Lector - Conf. univ. Selezneva Svetlana

Prelegere: Funcția Möbius pe CCM. Funcția Möbius pe cubul n-dimensional. Formula de inversare a lui Möbius. Principiul incluziunii-excluderii. Problema numărării numărului de permutări-tulburări. Lector - Conf. univ. Selezneva Svetlana

Cursul 2. Proprietățile coeficienților binomi. Metoda de generare a funcțiilor, calculul sumelor și dovada identităților. Coeficienți polinomi. Principiul incluziunii-excluderii. Lector - Conf. univ. Selezneva Svetlana

Prelegere: Funcții esențiale. Trei leme privind funcțiile esențiale. Criteriul de completitudine al lui Yablonsky. Criteriul de completitudine Slupetsky. Funcții Schaeffer. Lector conf. univ. Svetlana Nikolaevna Selezneva [email protected]

Curs: Numerele combinatorii de bază. Estimări și asimptotice pentru numere combinatorii. Lector - profesor asociat Svetlana Nikolaevna Selezneva, facultatea CMC a Universității de Stat din Moscova numită după M.V. Lomonosov Prelegeri pe site-ul http://mk.cs.msu.su

Curs: Proprietăţile coeficienţilor binomi. Însumarea și metoda de generare a funcțiilor (cazul final). Coeficienți polinomi. Estimări pentru coeficienți binomi și polinomi. Estimări pentru sumele binomului

Prelegere: Automate finite cu ieșire. Transformarea secvențelor periodice de către automate finite cu ieșire. Distincitatea stărilor în automate finite cu ieșire. Simplificarea mașinilor. Lector Selezneva

Prelegere: Set coperta și coperta matricei. Acoperire cu gradient. Lema de acoperire cu gradient. Estimări pentru cardinalitatea setului de umbrire a unui cub n-dimensional. Estimări pentru lungimea formelor normale ale funcțiilor polinomiale

Cursul 5. Set coperta și capacul matricei. Acoperire cu gradient. Lema de acoperire cu gradient. Estimări pentru cardinalitatea setului de umbrire al cubului boolean. Estimări pentru lungimea formelor normale booleene polinomiale

Curs 3. Secvenţe determinate de relaţii recurente. Ecuații liniare recurente omogene și neomogene (LORU și LNRU). Deciziile comune ale LORU și LNRU. Exemple Lector - Conf. univ. Selezneva

Curs 3. Relații pe platouri. Proprietăți. Formula de includere-excludere. Relația de echivalență. Relație de ordine parțială. Lector - Conf. univ. Svetlana N. Selezneva Prelegeri despre modele discrete.

Curs 4. Caracteristici ale logicii multivalorice. Clasă închisă, baza unei clase închise. Teoremele lui Yanov și Muchnik privind existența în logica cu mai multe valori a claselor închise fără bază și a claselor închise cu număr numărabil.

Lectura. Funcțiile argumentului natural (secvența). Ecuații liniare recurente omogene și neomogene (LORU și LNRU). Deciziile comune ale LORU și LNRU. Exemple Lector - Conf. univ. Svetlana Selezneva

Prelegere: Numărul cromatic al unui grafic. Criteriu pentru graficul în două culori. Teoreme asupra limitelor superioare și inferioare pentru numărul cromatic al unui grafic. Lector - Conf. univ. Svetlana N. Selezneva Prelegeri despre modele discrete.

Prelegere: Grafice și rețele. O estimare a numărului de pseudografe cu q muchii. O estimare a numărului de arbori cu q muchii. Grafice plane. Formula lui Euler pentru graficele plane. Cel mai mare număr de muchii în graficele plane. nonplanaritate

Curs 1. Combinatorică. Plasări, permutări, plasamente cu repetări, combinații, combinații cu repetări. Numărul lor. Lector - Conf. univ. Svetlana N. Selezneva Departamentul de Cibernetică Matematică

Prelegere: Secvențe. Ecuații liniare recurente omogene și neomogene. Soluții generale ale ecuațiilor liniare recurente omogene și neomogene. Lector - conferențiar Svetlana Nikolaevna Selezneva

Cursul 8. Planse de colorat. Echivalența coloranților în raport cu grupul. Funcții de generare. O serie de enumerare pentru cifre și o serie de enumerare pentru funcții. teorema lui Poya. Lector Selezneva Svetlana Nikolaevna

Prelegerea: Colorat. Echivalența coloranților în raport cu grupul de permutare. Teorema lui Polya (caz special). Funcții de generare. O serie de enumerare pentru cifre și o serie de enumerare pentru funcții. Teorema

Curs 2. Forme normale conjunctive. Implicit, implicatul simplu al unei funcții. Funcții CNF prescurtate ale algebrei logicii. Metode pentru construirea unui CNF abreviat. Lector Selezneva Svetlana Nikolaevna [email protected]

Modele matematice și metode de sinteză logică a VLSI Toamna 2015 Cursul 4 Planul de curs Optimizarea logică a circuitelor logice combinaționale Diferite moduri de reprezentare a funcțiilor algebrei logicii (FAL)

Prelegere: Automate finite nedeterministe (NFA) fără ieșire. O teoremă privind coincidența claselor de mulțimi de cuvinte permise de automate deterministe finite și nedeterministe finite. Procedură

Curs 1. Selectii. Plasări, permutări, plasamente cu repetări, combinații, combinații cu repetări, numărul acestora. Exemple. Lector - conferențiar Svetlana Nikolaevna Selezneva Prelegeri la curs Discret

Curs 1. Obiecte combinatorii: selecții, așezări, permutări, plasamente cu repetări, combinații, combinații cu repetări, numărul acestora. Numerele combinatorii: factorial, factorial descrescător, binom

CURTEA 4 SCHEME DIN ELEMENTE FUNCȚIONALE 1. Definiții de bază În primul rând, este necesar să avem în vedere compoziția. O funcție poate fi reprezentată ca o „cutie neagră” care are o intrare și o ieșire. Lăsa

Cursul 2. Algoritm pentru recunoașterea completității în P k. teorema lui Kuznetsov. clase închise. Clase de funcții care păstrează un set. Clase de funcții care păstrează partiția. Cursuri precompletate. Lector Selezneva

Curs 3. Polinomul Zhegalkin. Metode de construire a polinomului funcției Zhegalkin. Funcția implicită liniară. Forma normală conjunctivă liniară (LCNF). Găsirea tuturor funcțiilor implicate liniare. Examinare

Cursul 2. Generarea de funcții: numărarea sumelor combinatorii și demonstrarea identităților, enumerarea obiectelor combinatorii. Principiul incluziunii-excluderii. Numărarea numărului de permutări-tulburări. Lector -

Curs 5. Grafice. Planse de colorat grafic. Numărul cromatic al graficului. Criteriul de bicromaticitate pentru un grafic. Limitele superioare pentru numărul cromatic al unui grafic. Lector Selezneva Svetlana Nikolaevna [email protected] Prelegeri

Prelegere: Automate finite (KA) fără ieșire (recunoaștere de automate finite). Diagrame de tranziție. Seturi de automate (limbi). Lema privind proprietățile mulțimilor de automate. Un exemplu de set neautomat. Lector

Curs 1. Funcții cu valori finite. Funcții elementare cu valori k. Modalități de specificare a funcțiilor cu valori k: tabele, formule, formele I și II, polinoame. Completitudine. Teorema privind completitudinea sistemului Post. Funcția Webb.

Cursul 7 Model grafic pentru sarcina de distribuție a zborurilor. Numărul cromatic al graficului. Un criteriu pentru ca un grafic să fie bicolor.

Curs „Fundamentele Ciberneticii” pentru studenții specializării 01.02.09.01 (software matematic și informatic) 1. Informații generale (volum de muncă, forme de control etc.). Cursul este

Curs 6. Grafice. Proprietățile ereditare ale graficelor. Estimarea numărului de muchii din graficele cu proprietate ereditară. Grafice extreme. Cel mai mare număr de muchii în graficele plane și fără triunghiuri cu un dat

Math-Net.Ru Portal matematic integral rusesc DS Romanov, O metodă de proiectare a circuitelor ușor de testat care admit teste de verificare unitară de lungime constantă, Diskr. Mat., 2014, volumul 26, numărul 2,

Prelegere: Automate finite fără ieșire, deterministe și nedeterministe. O teoremă privind coincidența claselor de mulțimi de cuvinte permise de automate finite deterministe și nedeterministe. Procedură

Lucrare practică 2 Construirea formelor normale ale unei funcții logice Scopul lucrării: Să învețe cum să construiești forme normale conjunctive, disjunctive, perfecte ale unei funcții logice Conținutul lucrării: De bază

Seminar privind complexitatea funcțiilor booleene Cursul 1: Introducere Clubul de informatică A. Kulikov la POMI http://compsciclub.ru 25/09/2011 25/09/2011 1 / 26 Plan de curs 1 Funcții booleene 2 Circuite booleene 3 Aproape

Lucrări practice 1 Analiza și sinteza sistemelor de control logic și releu

Prelegere: Expresii regulate și seturi regulate. Teorema lui Kleene privind coincidența claselor de mulțimi de automate și mulțimi obișnuite. Lector - Profesor asociat Svetlana Nikolaevna Selezneva Prelegeri despre matematică discretă

Cursul 3 Algebre booleene și funcții booleene Algebre booleene Conceptul de sisteme algebrice Un sistem algebric sau o structură algebrică este un set de simboluri ale unui alfabet (purtător) cu un anumit

Curs 5. Grafice. Exemple de aplicații ale graficelor. sarcina de transport. Debitul în rețea, teorema lui Ford și Fulkerson asupra valorii debitului maxim în rețea. Algoritm pentru construirea debitului maxim în rețea. Lector

Prelegere: Grafice. Exemple de aplicații ale graficelor. sarcina de transport. Debitul în rețea, teorema lui Ford și Fulkerson asupra valorii debitului maxim în rețea. Algoritm pentru construirea debitului maxim în rețea. Lector -

Lecția 8 Reamintim că pentru mulțimile arbitrare A și B există mulțimi A B = (x x A și x B); (intersecția lui A și B) A B = (x x A sau x B); (uniunea lui A și B) A \ B = (x x A și x / B) (diferența dintre A și B).

Cursul 7. Numerele Ramsey. Limită superioară pentru numărul Ramsey. Limita inferioară pentru numărul Ramsey. Lector Selezneva Svetlana Nikolaevna [email protected] facultatea CMC a Universității de Stat din Moscova numită după M.V. Prelegeri Lomonosov pe site-ul http://mk.cs.msu.ru

Prelegere: Grafice. Noțiuni de bază. Grafice conectate. Copaci. Arborele de bază. Numărul de vârfuri agățate din arborele de întindere. Lector - Conf. univ. Svetlana N. Selezneva Prelegeri despre modele discrete. magistratură,

Curs 11. Circuite booleene. Matematică discretă, HSE, Facultatea de Informatică (toamna 2014 primăvara 2015) Un circuit boolean în variabile x 1,..., x n este o succesiune de funcții booleene g

APROBAT Prorector pentru Afaceri Academice Yu. A. Samarsky 10 iunie 2008 PROGRAM SI SARCINI pentru cursul STRUCTURI DISCRETE in directia 010600 facultatea CIVT Departamentul de analiza datelor curs II semestrul 4 Doi

Universitatea de Stat Lomonosov din Moscova Facultatea de Matematică Computațională și Cibernetică S. A. Lozhkin ELEMENTE ALE TEORIEI SINTEZEI SISTEMELOR DE CONTROL DISCRETE Moscova 2016 Cuprins

Curs: Proprietățile ereditare ale graficelor. Grafice extreme. numere Ramsey. Lector - profesor asociat Svetlana Nikolaevna Selezneva, facultatea CMC a Universității de Stat din Moscova numită după M.V. Lomonosov Prelegeri pe site-ul http://mk.cs.msu.su Ereditar

Curs: Operații pe seturi finite de automate. Complementarea, unirea, intersecția, produsul și iterația seturi de automate, automatismul acestora. Lector - Conf. univ. Svetlana Nikolaevna Selezneva Prelegeri

Ministerul Federației Ruse pentru Comunicații și Informatizare Regiunea Volga Academia de Stat de Telecomunicații și Informatică Departamentul de Matematică Superioară Aprobat de Consiliul Metodologic PGATI 29 martie 2002

Curs 5. Colorarea muchiilor graficelor. Indicele cromatic al graficului. Indicele cromatic al graficelor bipartite. Limitele superioare și inferioare pentru indicele cromatic al unui grafic. Lector Selezneva Svetlana Nikolaevna [email protected]

Math-Net.Ru Portal matematic integral rusesc NP Red'kin, Pe circuite care admit teste de diagnosticare scurte, Diskr. Mat., 1989, volumul 1, numărul 3, 71 76 Utilizarea întregului rus

LOGICA MATEMATICĂ(1) Teme pentru exerciții practice 1. Algebra enunțurilor Un enunț este o valoare care poate lua două valori: adevărat și fals. Declarațiile sunt notate cu majuscule

Cursul 2

(SFE) într-o anumită bază. Complexitate și profunzime

sistem. Exemple. Metodă pentru sinteza SFE prin DNF.

Lector - conferențiar Svetlana Nikolaevna Selezneva

Prelegeri despre „Matematica discretă 2”.

cursul 1, grupa 141,

facultatea CMC a Universității de Stat din Moscova numită după M.V. Lomonosov

Prelegeri pe site-ul http://mk.cs.msu.su

Exemple SPE Sinteza SPE din DNF

Circuite din elemente funcționale

Să definim circuite de elemente funcționale în anumite baze.

Să ne dăm un set de funcții booleene B = (g1 (x1,..., xn1),..., gs (x1,..., xns)) P2, unde n1,..., ns 0.

Să numim acest set baza.

Rețineți că acest concept de bază nu este în nici un fel legat de conceptul de bază P2, care a fost considerat în algebra logicii.

De regulă, vom lua în considerare baza standard B0 = (x&y, x y, x ).

Exemple SFE Sinteza SFE din DNF Definirea unui circuit din elemente funcționale

1) un grafic aciclic direcționat G = (V, E), al cărui vârf v V are un grad în d (v) care nu depășește doi (d (v) 2);

2) fiecare vârf v cu un grad în egal cu 0 (d (v) = 0) se numește intrare (sau intrare în circuit) și îi este atribuită o variabilă booleană xi;

3) toate celelalte vârfuri (cu excepția intrărilor) sunt numite vârfuri interne ale circuitului;

4) fiecărui vârf v cu un grad în egal cu 1 (d (v) = 1) i se atribuie un element de negație (funcțional); toate astfel de vârfuri se numesc invertoare;

5) fiecărui vârf v cu un grad în egală cu 2 (d (v) = 2) i se atribuie fie un element de conjuncție (funcțional) & fie un element de disjuncție (funcțional); toate vârfurile cărora le sunt alocate elemente ale unei conjuncții se numesc conjunctori, toate vârfurile cărora le sunt alocate elemente ale unei conjuncții se numesc disjunctori;

Exemple CFE Sinteza CFE din DNF Definiția unui circuit din elemente funcționale (continuare)

6) în plus, unora dintre vârfuri sunt atribuite diferite variabile de ieșire y1,..., ym în perechi.

Dacă este dat un CFE S, ale cărui intrări sunt alocate doar variabilelor x1,..., xn și cu variabilele de ieșire y1,..., ym, atunci vom nota acest CFE cu S(x1,..., xn; y1,..., ym).

Exemple SPE Sinteza SPE din DNF

–  –  –

Determinarea adâncimii unui vârf CFE Prin inducție, determinăm adâncimea d(v) a unui vârf v în CFE S.

1. Baza inducției. Fiecare intrare v a SPE S are o adâncime egală cu 0: d(v) = 0.

–  –  –

SFE și caracteristicile lor Schemele elementelor funcționale sunt un model de calcul.

Caracteristicile SPE introduse de noi arată diferite aspecte ale eficienței computaționale.

Complexitatea SFE corespunde timpului de calcul secvenţial.

Adâncimea SPE corespunde timpului de calcul paralel.

Numărul maxim de vârfuri cu aceeași adâncime în CFE corespunde numărului de procesoare din calculul paralel.

Exemple CFE Sinteza CFE din DNF Exemplu: suma a trei biți Soluție. Similar exemplului 6, scriem un tabel cu suma a trei biți x, y și z. Această sumă poate fi și un număr cu două cifre binare, așa că introducem două variabile booleene

u0, u1 astfel încât x + y + z = 2u1 + u0:

–  –  –

Literatura pentru prelegere 4

1. Yablonsky S.V. Introducere în matematica discretă. M.:

Liceu, 2001. Partea a V-a, Cap. 2, p. 336-355.

2. Gavrilov G.P., Sapozhenko A.A. Sarcini și exerciții de matematică discretă. M.: Fizmatlit, 2004. Ch. X 1,1, 1,5, 1,7, 1,17, 1,18.

Exemple SPE Sinteza SPE din DNF

31. Scheme de elemente funcționale, reguli de construcție și funcționare, metoda de sinteză a sfe pe baza sdnf și sknf.

Definiție. Un element funcțional este un model matematic al unui convertor elementar discret, care, conform unei anumite legi, transformă semnalele pe care le primește la intrare într-un semnal la ieșirea convertorului. Din elemente funcționale, cu ajutorul unor reguli, se pot construi modele mai complexe ca structură și funcționare - diagrame ale elementelor funcționale. În aceste modele, semnalele de intrare și de ieșire sunt codificate cu simbolurile 0 și 1.

Reguli de construcție. Pentru a obține SPE-uri complexe de la altele mai simple, li se aplică secvențial operațiunile de împărțire a intrării sau ieșirii circuitului, atașarea unui element funcțional la circuit și conectarea elementului funcțional la intrarea sau ieșirea circuitului. Aceste operații seamănă cu regulile pentru obținerea unei formule complexe din cele mai simple folosind suprapunerea.

Sinteza SFE.Întrucât disjuncția, conjuncția și negația formează un sistem complet în clasă R 2, apoi orice funcție booleană de la n argumentele pot fi implementate printr-un circuit de elemente functionale - disjunctori, conjunctori si invertoare - cu n intrări și o ieșire. Pentru a face acest lucru, puteți, de exemplu, să exprimați o funcție booleană dată în termeni de SDNF sau SKNF și apoi să „sintetizați” formula rezultată sub forma unui circuit de elemente funcționale, aplicând secvențial operațiunile de împărțire, unire și conectare enumerate. de mai sus.

32. Metoda de sinteză SPE bazată pe implementarea compactă a tuturor conjuncțiilor folosind un multipol universal, complexitatea circuitelor rezultate.

Definiție. O funcție de n argumente se numește funcție booleană (sau o funcție a algebrei logicii) dacă asociază un număr cu fiecare mulțime.

Pentru a seta funcții booleene, vom folosi tabele, vectori, formule și grafice. Să luăm următoarea notație: este mulțimea tuturor mulțimilor, unde.

Definiție. Un element funcțional este un model matematic al unui convertor elementar discret, care, conform unei anumite legi, transformă semnalele pe care le primește la intrare într-un semnal la ieșirea convertorului. Din elemente funcționale, cu ajutorul unor reguli, se pot construi modele mai complexe ca structură și funcționare - diagrame ale elementelor funcționale. În aceste modele, semnalele de intrare și de ieșire sunt codificate cu simbolurile 0 și 1.

Metoda de sinteză SPE bazată pe implementarea compactă a tuturor conjuncțiilor folosind un multipol universal. Această metodă se bazează și pe reprezentarea unei funcții sub formă de SDNF, dar vă permite să construiți circuite mai puțin complexe datorită unei implementări mai compacte a conjuncțiilor. Descompunerea unei funcții în SDNF poate conține conjuncții care au factori comuni. Dacă două astfel de conjuncții sunt implementate de un subcircuit într-un bloc, atunci acest lucru va necesita conjunctori cu cel puțin unul mai puțin decât erau necesari înainte, cu implementare independentă a tuturor conjuncțiilor prin prima metodă de sinteză. O implementare compactă a tuturor conjuncțiilor posibile de lungime n poate fi realizat folosind un multipol universal construit inductiv având n intrări și 2 n ieșiri, unde n = 1,2,3,… Avantajele metodei sunt vizibile mai ales atunci când este necesară implementarea unui sistem de mai multe funcții booleene folosind un singur circuit. În acest caz, ar fi posibilă împărțirea și apoi trecerea prin disjunctori a acelor ieșiri ale multipolului universal care corespund conjuncțiilor incluse în SDNF a funcțiilor sistemului dat. Acest lucru ar face posibil să se descurce cu mai puțini conjunctori decât dacă fiecare funcție a unui sistem dat ar fi implementată independent de propriul său subcircuit.

Complexitatea unui astfel de multipol este egală cu L() =.

Dacă circuitul elementelor funcţionale Σ conţine exact r elemente funcţionale, atunci spunem că are complexitate rși scrieți-o ca o ecuație L(Σ) = r.

În tehnologia modernă a dispozitivelor de control și de calcul, un loc important îl ocupă convertoarele discrete, adică dispozitivele care au un anumit număr de intrări și ieșiri. Seturile de semnale care ajung la intrări și apar la ieșiri aparțin unor mulțimi finite cunoscute.

Dacă această lucrare nu vă convine, există o listă de lucrări similare în partea de jos a paginii. De asemenea, puteți utiliza butonul de căutare

Aranov Viktor Pavlovici Matematică discretă. Secțiunea 5. DNF și scheme din FE.

Cursul 28 Probleme de analiză și sinteză

Cursul 28 SCHEME DIN ELEMENTE FUNCȚIONALE.

PROBLEME DE ANALIZĂ ȘI SINTEZĂ

Planul cursului:

1. Conceptul de circuit de elemente funcţionale(FE).

2. Probleme de analiză și sinteză a circuitelor din FE.

1. Conceptul de circuit din FE

În tehnologia modernă de control și dispozitive de calcul, un loc important este ocupat deconvertoare discrete, adică dispozitive care au un anumit număr de intrări și ieșiri. Seturile de semnale care ajung la intrări și apar la ieșiri aparțin unor mulțimi finite cunoscute. Dispozitivele convertesc seturile de semnal de intrare în seturi de ieșire. Modelul matematic al unor astfel de dispozitive sunt așa-numitelecircuite din elemente funcţionale(SFE).

Ca exemplu, luați în considerare circuitul electric a trei diode și rezistența prezentate în Fig. unu.

Orez. 1. Circuitul electric și simbolul acestuia

În punctele circuitului reprezentate de un cerc, în momente diferite, poate apărea fie un nivel ridicat, aproximativ egal cu 5 V, fie un nivel scăzut, aproximativ egal cu zero. În punctul circuitului marcat cu liniuță, se menține un nivel de tensiune constant scăzut.

Punctele marcate vor fi interpretate ca intrări, iar punctul ca ieșire. Funcționarea circuitului poate fi descrisă după cum urmează: dacă nivelul de tensiune este scăzut la toate intrările, atunci și ieșirea este scăzută, dacă cel puțin una dintre intrări are un nivel de tensiune ridicat, atunci ieșirea este ridicată. Dacă desemnăm o stare cu un nivel de tensiune ridicat drept unu și cu un nivel de tensiune scăzut ca zero, atunci dependența ieșirii de intrări poate fi specificată folosind o funcție booleană.

Pe baza acestui fapt, circuitul de mai sus se numește elementul logic „SAU”.

Circuite similare pot fi construite din tuburi de vid, întrerupătoare electromecanice, elemente pneumatice etc. Dependența ieșirii de intrări poate fi descrisă nu numai ca o disjuncție, ci și cu ajutorul conjuncției, negației și funcțiilor booleene mai complexe.

Vom lua în considerare elemente logice cu dependență diferită a ieșirii de intrări. Aceste elemente pot fi conectate între ele prin alimentarea ieșirilor unor elemente la intrările altora. Ca rezultat, obținem SFE.

Definirea conceptului de SFE poate fi împărțită în două etape. În prima etapă este dezvăluită partea structurală a acestui concept, în a doua - cea funcțională.

eu etapă. Să împărțim acest pas în mai mulți pași.

1 . Există un set finit de obiecte () numitelemente logice.Fiecare element are intrări și o ieșire. Elementul este reprezentat grafic așa cum se arată în Fig. 2.

2 . Prin inducție definim conceptul rețea logică ca obiect care are un anumit număr de intrări și un anumit număr de ieșiri (fig. 3).

a) Baza inducției. Un vârf izolat se numește o rețea logică trivială. Prin definiție, este atât o intrare, cât și o ieșire (Figura 4).

… …

…

Orez. 2 Fig. 3 Fig. patru

b) Tranziție inductivă. Această parte se bazează pe utilizarea a trei operații.

I . Operația de combinare a rețelelor disjunse. Fie și două rețele care nu se intersectează (fără elemente comune, intrări și ieșiri) având atât intrări, cât și, respectiv, ieșiri. Uniunea teoretică a rețelelor este o rețea logică care are intrări și ieșiri.

II . Operația de atașare a unui element. Fie rețeaua și elementul să fie astfel încât și în diferite ieșiri cu numere sunt alese. Apoi figura se numește o rețea logică, care este rezultatul conectării unui element la o rețea. Intrările sunt toate intrările, ieșirile sunt toate ieșirile rețelei, cu excepția ieșirilor cu numere, precum și ieșirile elementului. Rețeaua are intrări și ieșiri (Fig. 5).

… …

Orez. 6.

Orez. 5

III . Operația de împărțire a ieșirii. Lasă o ieșire cu un număr să fie selectată în rețea. Apoi figura se numește o rețea logică obținută prin împărțirea ieșirii. Intrările sunt toate intrările, ieșirile sunt toate ieșirile rețelei cu numerele 1, ..., ... și încă două ieșiri care decurg din ieșire cu numărul rețelei (Fig. 6). Prin urmare, are intrări și ieșiri.

3 . Lasă alfabetele și să fie date.

O diagramă a elementelor funcționalese numește o rețea logică cu intrări din alfabet și ieșiri din alfabet, care se notează

. (1)

Dăm exemple de scheme.

1. Fie mulțimea formată din trei elemente AND (conjunctor), OR (disjunctor) și NOT (invertor).

Apoi figura (Fig. 6) va fi o diagramă, deoarece poate fi construită folosind operațiunile I  III  .

 

Orez. 6 Fig. 7

2. Figura prezentată în fig. 7, este și o diagramă.

II etapă. Determinarea funcționării circuitului.

4 . Să comparăm SFE (1) cu sistemul de funcții al algebrei logicii

(2)

numit siconductivitatea acestui circuit.

Exemplu. a) Pentru circuit, avem un sistem format dintr-o ecuație

Sau.

b) Pentru schemă, obținem în mod similar

1. Implementarea funcţiilor booleene prin circuite FE. Probleme de analiză și sinteză

scheme din PV

Sarcină de analiză: pentru un SFE dat (1) pentru a obține un sistem de ecuații booleene (2).

Algoritm de rezolvare a problemei: urmărirea operațiunilor de construire a unei rețele I III , calculăm secvenţial funcţiile la ieşirile elementelor de reţea.

Sarcina de sinteză: pentru o bază dată de elemente funcționale și un sistem arbitrar de ecuații booleene (2), construiți un circuit (1) din FE date care implementează acest sistem de ecuații.

Existența unei soluții la problema de sinteză este determinată de teorema Post, conform căreia sistemul de funcții care implementează FE de bază trebuie să fie complet. Funcțiile pot fi reprezentate ca o suprapunere de funcții, iar fiecărui pas al suprapunerii îi corespunde o anumită combinație de elemente.

Exemplu. Pentru funcție

(3)

Schema corespunzătoare suprapunerii din partea dreaptă a formulei (3) este prezentată în fig. opt.

  

Orez. opt

Problema de sinteză constă în faptul că pentru un sistem dat de ecuații booleene este posibil să se construiască multe circuite din FE care implementează acest sistem. În acest sens, se pune problema sintezei optime: dintre toate schemele posibile care implementează o anumită funcție, alegeți-o pe cea mai bună în ceea ce privește o caracteristică sau alta, de exemplu, cu cel mai mic număr de elemente. Astfel de scheme vor fi numite minim .

Următoarea afirmație este adevărată.

Teorema. Există un algoritm care pentru fiecare sistem de funcții booleene construiește un circuit minim.

Acest algoritm pentru construirea de circuite minime aparține clasei de algoritmi de tip „forță brută”, deoarece se bazează pe vizualizarea tuturor circuitelor până la o anumită complexitate. Algoritmii de forță brută, de regulă, sunt foarte laborioși și nepotriviți pentru scopuri practice. Prin urmare, luăm în considerare în continuare o problemă mai simplă pentru care sistemul original de ecuații conține o ecuație

și, prin urmare, circuitul dorit are o singură ieșire.

Notați complexitatea circuitului minim cu . Vom lua în considerare problema de sinteză nu pentru o singură funcție, ci pentru întreaga clasă de funcții de variabile. Calitatea algoritmilor de sinteză este comparată prin compararea așa-numitelor funcții Shannon. Lăsa

complexitatea minimă a circuitelor pe care le implementează, care sunt obținute cu ajutorul algoritmului.

Funcțiile se numesc funcții Shannon și este evident că

Sarcina sintezei este de a găsi un algoritm de care ar fi posibil să fim mai aproape și astfel încât complexitatea algoritmului să fie semnificativ mai mică decât complexitatea algoritmului de căutare exhaustivă. Cu o astfel de formulare a problemei, nu este necesar ca algoritmul pentru fiecare funcție să găsească circuitul minim, este necesar doar ca cel mai simplu circuit obținut cu ajutorul lui să aibă o complexitate care nu depășește cu mult.