Corespondența G între mulțimi AȘi ÎN numit submult. Dacă, atunci ei spun asta b

corespunde A. Ansamblul tuturor elementelor corespondente

Chemat cale elementul a. Se numește mulțimea tuturor cărora le corespunde elementul

prototip element b.

Multe cupluri (b, a) astfel că se numește inversă

către G si este desemnat . Conceptele de imagine și prototip pentru

„G și sunt reciproc inverse.

Exemple. 1) Să-l potrivim cu un număr natural P

set de numere reale . Imaginea cu numărul 5

va fi o jumătate de interval

(aceasta înseamnă cel mai mare număr întreg, mai mic sau egal cu X). Prototipul numărului 5 din această corespondență este o mulțime infinită: jumătate de interval.

În ceea ce privește închiderea, putem da și alte definiții ale închiderii și completității (echivalente cu cele originale):

K este o clasă închisă dacă K = [K];

K este un sistem complet dacă [K] = P 2 .

Exemple.

* (0), (1) - clase închise.

* Un set de funcții ale unei variabile este o clasă închisă.

* - clasă închisă.

* Clasa (1, x+y) nu este o clasă închisă.

Să ne uităm la unele dintre cele mai importante clase închise.

1. T 0- clasa de funcții care păstrează 0.

Să notăm cu T 0 clasa tuturor funcțiilor algebrei logicii f(x 1 , x 2 , ... , x n) păstrând constanta 0, adică funcții pentru care f(0, ... , 0 ) = 0.

Este ușor de observat că există funcții care aparțin lui T 0 și funcții care nu aparțin acestei clase:

0, x, xy, xÚy, x+y О T 0 ;

Din faptul că Ï T 0 rezultă, de exemplu, că nu se poate exprima prin disjuncţie şi conjuncţie.

Deoarece tabelul pentru funcția f din clasa T 0 conține valoarea 0 în prima linie, atunci pentru funcțiile din T 0 puteți seta valori arbitrare numai pe 2 n - 1 set de valori variabile, adică

unde este mulțimea de funcții care păstrează 0 și depind de n variabile.

Să arătăm că T 0 este o clasă închisă. Deoarece xÎT 0 , atunci pentru a justifica închiderea este suficient să se arate închiderea față de operația de suprapunere, întrucât operația de modificare a variabilelor este un caz special de suprapunere cu funcția x.

Lăsa . Atunci este suficient să arătăm că . Acesta din urmă decurge din lanțul egalităților

2. T 1- clasa de funcții care păstrează 1.

Să notăm cu T 1 clasa tuturor funcțiilor algebrei logicii f(x 1, x 2, ... , x n) păstrând constanta 1, adică funcții pentru care f(1, ... , 1 ) = 1.

Este ușor de observat că există funcții care aparțin lui T 1 și funcții care nu aparțin acestei clase:

1, x, xy, xÚy, xºy О T 1 ;

0, , x+y Ï T 1 .

Din faptul că x + y Ï T 0 rezultă, de exemplu, că x + y nu poate fi exprimat în termeni de disjuncție și conjuncție.

Rezultatele despre clasa T 0 sunt transferate trivial în clasa T 1 . Astfel avem:

T 1 - clasa inchisa;

3. L- clasa de funcţii liniare.

Să notăm cu L clasa tuturor funcțiilor algebrei logice f(x 1 , x 2 , ... , x n) care sunt liniare:

Este ușor de observat că există funcții care aparțin lui L și funcții care nu aparțin acestei clase:

0, 1, x, x+y, x 1 º x 2 = x 1 + x 2 + 1, = x+1 О L;

Să demonstrăm, de exemplu, că xÚy Ï L .

Să presupunem contrariul. Vom căuta o expresie pentru xÚy sub forma unei funcții liniare cu coeficienți nedeterminați:

Pentru x = y = 0 avem a=0,

pentru x = 1, y = 0 avem b = 1,

pentru x = 0, y = 1 avem g = 1,

dar atunci pentru x = 1, y = 1 avem 1v 1 ¹ 1 + 1, ceea ce demonstrează neliniaritatea funcției xy.

Dovada închiderii clasei de funcții liniare este destul de evidentă.

Deoarece o funcție liniară este determinată în mod unic prin specificarea valorilor n+1 ale coeficientului a 0 , ... , a n , numărul de funcții liniare din clasa L (n) de funcții în funcție de n variabile este egal cu 2 n+1.

4. S- clasa de funcții auto-duale.

Definirea clasei de funcții auto-duale se bazează pe utilizarea așa-numitului principiu al dualității și al funcțiilor duale.

Funcția definită de egalitate este numită dual cu funcția .

Evident, tabelul pentru funcția duală (cu ordonarea standard a seturilor de valori variabile) se obține din tabelul pentru funcția originală prin inversarea (adică înlocuirea 0 cu 1 și 1 cu 0) coloanei de valori ale funcției și răsturnând-o.

Este ușor să vezi asta

(x 1 Ú x 2)* = x 1 Ù x 2 ,

(x 1 Ù x 2)* = x 1 Ú x 2 .

Din definiție rezultă că (f*)* = f, adică funcția f este duală cu f*.

Fie ca o funcție să fie exprimată folosind suprapunerea prin alte funcții. Întrebarea este cum să construim o formulă care să implementeze? Să notăm cu = (x 1, ..., x n) toate simbolurile variabile diferite găsite în mulțimi.

Teorema 2.6. Dacă funcția j se obține ca o suprapunere a funcțiilor f, f 1, f 2, ..., f m, adică

o funcție duală la o suprapunere este o suprapunere de funcții duale.

Dovada.

j*(x 1 ,...,x n) = ` f(`x 1 ,...,`x n) =

Teorema a fost demonstrată. ð

Principiul dualității rezultă din teoremă: dacă o formulă A realizează funcția f(x 1 , ... , x n), atunci formula obținută din A prin înlocuirea funcțiilor incluse în ea cu cele duale ale acestora realizează funcția duală f *(x 1 , ... , x n).

Să notăm cu S clasa tuturor funcțiilor autoduale din P 2:

S = (f | f* = f )

Este ușor de observat că există funcții care aparțin lui S și funcții care nu aparțin acestei clase:

0, 1, xy, xÚy Ï S .

Un exemplu mai puțin trivial de funcție auto-duală este funcția

h(x, y, z) = xy Ú xz Ú yz;

Folosind teorema funcției duale la suprapunere, avem

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h* ; h О S.

Pentru o funcție auto-duală, identitatea este valabilă

deci pe seturi și , pe care o vom numi opus, funcția auto-duală ia valori opuse. Rezultă că funcția auto-duală este complet determinată de valorile sale din prima jumătate a rândurilor tabelului standard. Prin urmare, numărul de funcții auto-duale din clasa S (n) de funcții în funcție de n variabile este egal cu:

Să demonstrăm acum că clasa S este închisă. Deoarece xÎS , atunci pentru a justifica închiderea este suficient să arătăm închiderea față de operația de suprapunere, întrucât operația de modificare a variabilelor este un caz special de suprapunere cu funcția x. Lăsa . Atunci este suficient să arătăm că . Acesta din urmă este instalat direct:

5. M- clasa funcţiilor monotone.

Înainte de a defini conceptul de funcție monotonă în algebra logicii, este necesar să se introducă o relație de ordonare asupra mulțimii de mulțimi ale variabilelor sale.

Ei spun că setul vine înaintea setului (sau „nu mai mult decât”, sau „mai mic decât sau egal cu”) și utilizați notația dacă a i £ b i pentru tot i = 1, ... , n. Dacă și , atunci vom spune că mulțimea precede cu strictețe mulțimea (sau „strict mai puțin”, sau „mai puțin decât” mulțimea) și vom folosi notația . Seturile și sunt numite comparabile dacă fie , fie . În cazul în care nici una dintre aceste relații nu este valabilă, mulțimile și sunt numite incomparabile. De exemplu, (0, 1, 0, 1) £ (1, 1, 0, 1), dar mulțimile (0, 1, 1, 0) și (1, 0, 1, 0) sunt incomparabile. Astfel, relația £ (numită adesea relație de precedență) este o ordine parțială pe mulțimea B n. Mai jos sunt diagrame ale mulțimilor parțial ordonate B 2, B 3 și B 4.

Relația de ordine parțială introdusă este un concept extrem de important care depășește cu mult domeniul de aplicare al cursului nostru.

Acum avem ocazia să definim conceptul de funcție monotonă.

Funcția algebră logică este numită monoton, dacă pentru oricare două mulțimi și , astfel încât , inegalitatea este valabilă . Mulțimea tuturor funcțiilor monotone ale algebrei logicii este notată cu M, iar mulțimea tuturor funcțiilor monotone care depind de n variabile este notă cu M(n).

Este ușor de observat că există funcții care aparțin lui M și funcții care nu aparțin acestei clase:

0, 1, x, xy, xÚy О M;

x+y, x®y, xºy Ï M .

Să arătăm că clasa funcțiilor monotone M este o clasă închisă. Deoarece xОМ, atunci pentru a justifica închiderea este suficient să se arate închiderea în raport cu operația de suprapunere, deoarece operația de modificare a variabilelor este un caz special de suprapunere cu funcția x.

Lăsa . Atunci este suficient să arătăm că .

Fie mulțimi de variabile, respectiv, funcții j, f 1 , ... , f m , iar mulțimea de variabile a funcției j este formată din acele și numai acele variabile care apar în funcțiile f 1 , ... , f m . Fie și două seturi de valori ale variabilei și . Aceste seturi definesc seturile valori variabile , astfel încât . Datorită monotonității funcțiilor f 1 , ... , f m

iar datorită monotonității funcției f

De aici ajungem

Numărul de funcții monotone în funcție de n variabile nu este cunoscut cu exactitate. Limita inferioară poate fi obținută cu ușurință:

unde este întreaga parte de la n/2.

De asemenea, se dovedește a fi o estimare prea mare de mai sus:

Rafinarea acestor estimări este o sarcină importantă și interesantă a cercetării moderne.

Criteriul de completitudine

Acum suntem capabili să formulăm și să dovedim un criteriu de completitudine (teorema lui Post), care determină condițiile necesare și suficiente pentru completitudinea unui sistem de funcții. Să prefațăm formularea și demonstrarea criteriului de completitudine cu câteva leme necesare care au interes independent.

Lema 2.7. Lema despre funcția non-duală.

Dacă f(x 1 , ... , x n)Ï S , atunci se poate obține o constantă din acesta prin înlocuirea funcțiilor x și `x.

Dovada. Din moment ce fÏS, atunci există un set de valori ale variabilelor
=(a 1 ,...,a n) astfel încât

f(`a 1 ,...,`a n) = f(a 1 ,...,a n)

Să înlocuim argumentele din funcția f:

x i este înlocuit cu ,

adică să punem și să luăm în considerare funcția

Astfel, am obținut o constantă (deși nu se știe ce constantă este: 0 sau 1). ð

Lema 2.8. Lema despre funcția nemonotonă.

Dacă funcția f(x 1 ,...,x n) este nemonotonă, f(x 1 ,...,x n) Ï M, atunci se poate obține o negație din ea prin schimbarea variabilelor și înlocuirea constantelor 0 și 1.

Dovada. Deoarece f(x 1 ,...,x n) Ï M, atunci există seturi de valori ale variabilelor sale, , , astfel încât , și pentru cel puțin o valoare i, a i< b i . Выполним следующую замену переменных функции f:

x i va fi înlocuit cu

După o astfel de înlocuire obținem o funcție a unei variabile j(x), pentru care avem:

Aceasta înseamnă că j(x)=`x. Lema este dovedită. ð

Lema 2.9. Lema despre funcția neliniară.

Dacă f(x 1 ,...,x n) Ï L , atunci din acesta prin substituirea constantelor 0, 1 și folosind funcția `x putem obține funcția x 1 &x 2 .

Dovada. Să reprezentăm f ca un DNF (de exemplu, un DNF perfect) și să folosim relațiile:

Exemplu. Să dăm două exemple de aplicare a acestor transformări.

Astfel, o funcție scrisă în formă normală disjunctivă, după aplicarea relațiilor indicate, deschiderea parantezelor și transformărilor algebrice simple, devine un polinom mod 2 (polinomul Zhegalkin):

unde A 0 este o constantă, iar A i este o conjuncție a unor variabile din numărul x 1,..., x n, i = 1, 2, ..., r.

Dacă fiecare conjuncție A i constă dintr-o singură variabilă, atunci f este o funcție liniară, care contrazice condiția lemei.

În consecință, în polinomul Zhegalkin pentru funcția f există un termen care conține cel puțin doi factori. Fără pierderea generalității, putem presupune că printre acești factori există variabile x 1 și x 2. Atunci polinomul poate fi transformat după cum urmează:

f = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (x 3 ,..., x n),

unde f 1 (x 3 ,..., x n) ¹ 0 (altfel polinomul nu include o conjuncție care conține conjuncția x 1 x 2).

Fie (a 3 ,...,a n) astfel încât f 1 (a 3 ,...,a n) = 1. Atunci

j(x 1 ,x 2) = f(x 1 ,x 2 , a 3 ,...,a n) = x 1 x 2 +ax 1 +bx 2 +g ,

unde a, b, g sunt constante egale cu 0 sau 1.

Să folosim operația de negație pe care o avem și să considerăm funcția y(x 1 ,x 2) obținută din j(x 1 ,x 2) după cum urmează:

y(x 1 ,x 2) = j(x 1 +b, x 2 +a)+ab+g.

Este evident că

y(x 1 ,x 2) =(x 1 +b)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2.

Prin urmare,

y(x 1 ,x 2) = x 1 x 2 .

Lema este complet dovedită. ð

Lema 2.10. Lema principală a criteriului de completitudine.

Dacă clasa F=( f ) a funcțiilor de algebră logică conține funcții care nu păstrează unitatea, nu păstrează 0, sunt non-auto-duale și nemonotone:

apoi din functiile acestui sistem, prin operatii de suprapunere si inlocuire de variabile, se pot obtine constantele 0, 1 si functia.

Dovada. Să luăm în considerare funcția. Apoi

Există două cazuri posibile de considerații ulterioare, desemnate în prezentarea următoare ca 1) și 2).

1). Funcția de pe setul de unități ia valoarea 0:

Vom înlocui totul funcții variabile variabila x. Apoi funcția

există, pentru că

Și .

Să luăm o funcție non-duală. Deoarece am obținut deja funcția, atunci prin lema pe o funcție non-duală (lema 2.7. ) puteți obține o constantă de la. A doua constantă poate fi obținută de la prima folosind funcția. Deci, în primul caz considerat, se obțin constante și negație. . Al doilea caz, și odată cu el lema principală a criteriului de completitudine, sunt complet dovedite. ð

Teorema 2.11. Un criteriu pentru completitudinea sistemelor de funcții în algebra logicii (teorema lui Post).

Pentru ca sistemul de funcții F = (f i) să fie complet, este necesar și suficient ca acesta să nu fie cuprins în întregime în nici una dintre cele cinci clase închise T 0, T 1, L, S, M, adică pt. fiecare dintre clasele T 0 , T 1 , L , S, M în F există cel puţin o funcţie care nu aparţine acestei clase.

Necesitate. Fie F un sistem complet. Să presupunem că F este conținut într-una din clasele indicate, să o notăm cu K, adică. F Í K. Ultima includere este imposibilă, deoarece K este o clasă închisă care nu este un sistem complet.

Adecvarea. Fie ca întregul sistem de funcții F = (f i ) să nu fie cuprins în nici una din cele cinci clase închise T 0 , T 1 , L , S , M . Să luăm următoarele funcții în F:

Apoi, pe baza lemei principale (lema 2.10 ) dintr-o funcție care nu păstrează 0, o funcție care nu păstrează 1, funcții non-duale și nemonotone, se pot obține constantele 0, 1 și funcția de negație:

Pe baza lemei funcțiilor neliniare (lema 2.9 ) din constante, negație și o funcție neliniară putem obține conjuncția:

Sistem de funcții - un sistem complet conform teoremei despre posibilitatea de a reprezenta orice funcție a algebrei logicii sub forma unei forme normale disjunctive perfecte (de remarcat că disjuncția poate fi exprimată prin conjuncție și negație sub forma ).

Teorema este complet demonstrată. ð

Exemple.

1. Să arătăm că funcția f(x,y) = x|y formează un sistem complet. Să construim un tabel de valori ale funcției x½y:

X	y	x\|y

f(0,0) = 1, deci x | yÏT 0 .

f(1,1) = 0, deci x | yÏT 1 .

f(0,0) = 1, f(1,1) = 0, deci x | mie.

f(0,1) = f(1,0) = 1, - pe multimi opuse x | y ia aceleasi valori, prin urmare x | da.

În sfârșit, ce înseamnă neliniaritatea funcției?
x | y.

Pe baza criteriului de completitudine, putem afirma că f(x,y) = x | y formează un sistem complet. ð

2. Să arătăm că sistemul de funcții formează un sistem complet.

Într-adevăr, .

Astfel, printre funcțiile sistemului nostru am găsit: o funcție care nu păstrează 0, o funcție care nu păstrează 1, funcții non-auto-duale, nemonotone și neliniare. Pe baza criteriului de completitudine, se poate susține că sistemul de funcții formează un sistem complet. ð

Astfel, suntem convinși că criteriul de completitudine dă un aspect constructiv și metoda eficienta clarificarea completității sistemelor de funcții ale algebrei logicii.

Să formulăm acum trei corolare din criteriul de completitudine.

Corolarul 1. Orice clasă închisă K de funcții ale algebrei logicii care nu coincide cu întregul set de funcții al algebrei logicii (K¹P 2) este conținută în cel puțin una dintre clasele închise construite.

Definiție. Se numește clasa închisă K pre-plin, dacă K este incomplet și pentru orice funcție fÏ K clasa K È (f) este completă.

Din definiție rezultă că clasa precompletă este închisă.

Corolarul 2.În algebra logicii există doar cinci clase precomplete și anume: T 0, T 1, L, M, S.

Pentru a demonstra corolarul, trebuie doar să verificați că niciuna dintre aceste clase nu este conținută în cealaltă, ceea ce este confirmat, de exemplu, de următorul tabel de funcții aparținând unor clase diferite:

T0	T 1	L	S	M
+	-	+	-	+
-	+	+	-	+
-	-	+	+	-

Corolarul 3. Din fiecare sistem complet funcții, se poate distinge un subsistem complet care nu conține mai mult de patru funcții.

Din demonstrarea criteriului de completitudine rezultă că nu se pot distinge mai mult de cinci funcții. Din demonstrarea lemei principale (Lema 2.10 ) urmează că fie nu este auto-dual, fie nu păstrează unitatea și nu este monoton. Prin urmare, nu sunt necesare mai mult de patru funcții.

- (Lat. târzie superpositio, - suprapunere, din Lat. superpositus - aşezat deasupra) (compoziţie) - operaţie logico-matematică. calcul, care constă în obţinerea din k.l. funcțiile date f și g ale unui calcul dat optiune noua g (f) (expresia g... ... Enciclopedie filosofică

Termenul de suprapunere (suprapunere) se poate referi la următoarele concepte: Compoziția de suprapunere a funcțiilor (funcție complexă) Principiul suprapunerii este un principiu din fizică și matematică care descrie suprapunerea proceselor (de exemplu, undele) și, ca urmare, ... ... Wikipedia

Compunerea de funcții, alcătuirea unei funcții complexe din două funcții... Enciclopedie matematică

Acest termen are alte semnificații, vezi Suprapunerea. Mecanica cuantică... Wikipedia

Acest articol sau secțiune conține o listă de surse sau referințe externe, dar sursele declarațiilor individuale rămân neclare din cauza lipsei de note de subsol... Wikipedia

În teoria sistemelor funcţionale discrete Funcția booleană numiți o funcție de tip, unde este o mulțime booleană și n este un întreg nenegativ, care se numește aritatea sau localitatea funcției. Elementele 1 (unu) și 0 (zero) sunt interpretate standard ...... Wikipedia

Una dintre cele mai importante pentru bazele matematicii și matematicii. clase logice de concepte care servesc drept clarificări conţin. conceptele unei funcții aritmetice efectiv calculabile și un predicat aritmetic efectiv decidabil și, în cele din urmă, și... ... Enciclopedie filosofică

Funcția, calculul valorilor unui roi poate fi efectuat folosind o procedură eficientă predeterminată sau un algoritm. O trăsătură caracteristică a proceselor de calcul este calculul cantităților necesare de probleme care apare secvenţial din datele iniţiale... ... Enciclopedie matematică

Este necesar să transferați conținutul acestui articol la articolul „Diferențierea unei funcții complexe”. Puteți ajuta proiectul combinând articole. Dacă este necesar să discutăm despre fezabilitatea fuziunii, înlocuiți acest șablon cu șablonul ((la fuzionare)) ... Wikipedia

- (lat. compositio compoziție, legare, adăugare, conexiune): Wikționarul are un articol „compoziție” Art Composition (artă plastică) este o componentă organizatorică a unei forme artistice care dă pro... Wikipedia

Cărți

Matematică discretă. Construcții teoretice de bază. Partea a VI-a, A.I. Shirokov. Manualul este partea a VI-a a secțiunii „Construcții teoretice de bază ale matematicii discrete”. În cap. XI are în vedere următoarele concepte: alcătuirea funcţiilor (§1); functii,...

Suprapunerea functiilor

O suprapunere a funcțiilor f1, ..., fm este o funcție f obținută prin înlocuirea acestor funcții între ele și redenumirea variabilelor.

Să fie două mapări și, în plus, un set nevid. Atunci o suprapunere sau o compoziție de funcții este o funcție definită prin egalitate pentru fiecare.

Domeniul de definire al unei suprapuneri este o mulțime.

Funcția se numește funcția exterioară și interioară pentru suprapunere.

Funcțiile prezentate ca o compoziție a celor „mai simple” se numesc funcții complexe.

Exemple de utilizare a suprapunerii sunt: rezolvarea unui sistem de ecuații prin substituție; găsirea derivatei unei funcții; găsirea valorii unei expresii algebrice prin înlocuirea valorilor variabilelor specificate în ea.

Funcții recursive

Recursiunea este o metodă de definire a unei funcții în care valorile funcției definite pentru valori arbitrare ale argumentelor sunt exprimate într-un mod cunoscut prin valorile funcției definite pentru valori mai mici ale argumentului.

Funcție primitiv recursivă

Definiția conceptului de funcție recursivă primitivă este inductivă. Constă în specificarea unei clase de funcții recursive primitive de bază și a doi operatori (suprapunere și recursivitate primitivă) care vă permit să construiți noi funcții recursive primitive pe baza celor existente.

Funcțiile recursive primitive de bază includ următoarele trei tipuri de funcții:

Zero function-- function fără argumente, revenind mereu 0 .

O funcție de succesiune a unei variabile care asociază orice număr natural cu numărul natural imediat următor.

Funcții, în care, de la n variabile, maparea oricărui set ordonat de numere naturale la un număr din această mulțime.

Operatorii de substituție și recursivitate primitivă sunt definiți după cum urmează:

Operator de suprapunere (uneori operator de substituție). Fie o funcție de m variabile și fie un set ordonat de funcții, fiecare cu variabile. Apoi rezultatul suprapunerii funcțiilor într-o funcție este o funcție de variabile care asociază un număr cu orice set ordonat de numere naturale.

Operator recursiv primitiv. Fie o funcție a n variabile și fie o funcție a variabilelor. Apoi rezultatul aplicării operatorului recursiv primitiv la o pereche de funcții se numește funcție a unei variabile de formă;

ÎN această definiție o variabilă poate fi înțeleasă ca un numărător de iterații, -- ca functia originala la începutul unui proces iterativ care produce o anumită secvență de funcții de variabile, începând cu și -- ca un operator care ia ca variabile de intrare, numărul pasului de iterație, o funcție la un pas de iterație dat și returnează un funcția la următorul pas de iterație.

Setul de funcții recursive primitive este mulțimea minimă care conține toate funcții de bazăși închis sub operatorii de substituție și recursivitate primitive specificați.

În termeni de programare imperativă, funcțiile recursive primitive corespund blocurilor de program care utilizează numai operații aritmetice, precum și operator condiționalși un operator de buclă aritmetică (un operator de buclă în care numărul de iterații este cunoscut la începutul buclei). Dacă programatorul începe să folosească operatorul buclă while, în care numărul de iterații este necunoscut în prealabil și, în principiu, poate fi infinit, apoi intră în clasa funcțiilor parțial recursive.

Să subliniem o serie de funcții aritmetice binecunoscute care sunt primitiv recursive.

Funcția de adunare a două numere naturale () poate fi considerată ca o funcție recursivă primitivă a două variabile, obținută prin aplicarea operatorului recursiv primitiv la funcții și, al doilea dintre care se obține prin substituirea funcției principale în funcția principală:

Înmulțirea a două numere naturale poate fi considerată ca o funcție recursivă primitivă a două variabile, obținută prin aplicarea operatorului recursiv primitiv la funcții și, al doilea dintre care se obține prin înlocuirea funcțiilor de bază și în funcția de adunare:

Diferența simetrică (valoarea absolută a diferenței) a două numere naturale () poate fi considerată ca o funcție recursivă primitivă a două variabile, obținută prin aplicarea următoarelor substituții și recursiuni primitive:

Să ne familiarizăm cu conceptul de suprapunere (sau impunere) de funcții, care constă în substituirea unei funcții dintr-un alt argument în locul argumentului unei funcții date. De exemplu, o suprapunere de funcții dă o funcție, iar funcțiile sunt obținute în mod similar

În general, să presupunem că o funcție este definită într-un anumit domeniu și funcția este definită într-un domeniu și valorile sale sunt toate conținute în domeniu. Atunci variabila z, așa cum se spune, prin y, este ea însăși o funcție a

Având în vedere o valoare dată, ei găsesc mai întâi valoarea y corespunzătoare acesteia (după regula caracterizată printr-un semn), apoi stabilesc valoarea y corespunzătoare (conform regulii

caracterizat printr-un semn, valoarea acestuia este considerată corespunzătoare x-ului selectat. Funcția rezultată dintr-o funcție sau dintr-o funcție complexă este rezultatul unei suprapuneri de funcții

Presupunerea că valorile funcției nu depășesc limitele regiunii Y în care este definită funcția este foarte semnificativă: dacă este omisă, atunci poate rezulta absurditate. De exemplu, presupunând că putem lua în considerare doar acele valori ale lui x pentru care altfel expresia nu ar avea sens.

Considerăm util să subliniem aici că caracterizarea unei funcții ca complexă nu este legată de natura dependenței funcționale a lui z de x, ci doar de modul în care este specificată această dependență. De exemplu, lăsați pentru y pentru Then

Aici funcția s-a dovedit a fi specificată ca o funcție complexă.

Acum că conceptul de suprapunere a funcțiilor este pe deplin clarificat, putem caracteriza cu exactitate cea mai simplă dintre acele clase de funcții care sunt studiate în analiză: acestea sunt, în primul rând, funcțiile elementare enumerate mai sus și apoi toate cele care se obțin din ele. folosind patru operatii aritmeticeși suprapuneri, aplicate succesiv de un număr finit de ori. Se spune că ele sunt exprimate prin elementar în forma lor finală; uneori sunt numite şi elementare.

Ulterior, stăpânind un aparat analitic mai complex (serie infinită, integrale), ne vom familiariza cu alte funcții care joacă, de asemenea, un rol important în analiză, dar depășesc deja clasa funcțiilor elementare.