De ce un articol de fundamente?
Articolele avansate din această bibliotecă presupun cunoașterea notațiilor matematice standard. Acest articol le definește explicit, pentru a servi drept referință comună. Dacă întâlnești într-un articol simboluri ca $\forall$, $\exists$, $\in$, $\mathbb{N}$, $\sum$ sau $\prod$ și nu ești sigur de semnificația lor exactă, ai ajuns unde trebuie.
1. Mulțimi (Seturi)
Definiție
O mulțime este o colecție bine definită de obiecte distincte, numite elemente. Notația standard:
$$A = {1, 2, 3, 4}$$
Apartenență
- $x \in A$ — $x$ aparține mulțimii $A$
- $x \notin A$ — $x$ nu aparține mulțimii $A$
Mulțimi uzuale în informatică
| Simbol | Mulțimea | Exemple | |---|---|---| | $\mathbb{N}$ | Numere naturale | ${0, 1, 2, 3, \dots}$ | | $\mathbb{Z}$ | Numere întregi | ${\dots, -2, -1, 0, 1, 2, \dots}$ | | $\mathbb{Q}$ | Numere raționale | $\frac{1}{2}, -\frac{3}{4}, 7$ | | $\mathbb{R}$ | Numere reale | $\pi, e, \sqrt{2}$ | | $\mathbb{C}$ | Numere complexe | $a + bi$ | | ${0,1}^*$ | Toate șirurile binare | $"0", "01", "110"$ | | $\mathbb{B}$ | Boolean | ${\text{adevărat}, \text{fals}}$ | | $\emptyset$ | Mulțimea vidă | ${}$ |
Operații cu mulțimi
| Operație | Notație | Definiție | |---|---|---| | Reuniune | $A \cup B$ | ${x \mid x \in A \lor x \in B}$ | | Intersecție | $A \cap B$ | ${x \mid x \in A \land x \in B}$ | | Diferență | $A \setminus B$ | ${x \mid x \in A \land x \notin B}$ | | Produs cartezian | $A \times B$ | ${(a,b) \mid a \in A, b \in B}$ | | Complement | $\overline{A}$ | $U \setminus A$ (față de universul $U$) | | Mulțimea părților | $\mathcal{P}(A)$ | ${X \mid X \subseteq A}$ (toate submulțimile) |
Cardinal
Cardinalul unei mulțimi $|A|$ este numărul de elemente.
- $|A \cup B| = |A| + |B| - |A \cap B|$ (principiul includerii-excluderii, cazul binar)
- $|A \times B| = |A| \cdot |B|$
- $|\mathcal{P}(A)| = 2^{|A|}$
2. Cuantificatori și logică predicativă
Cuantificatorii de bază
| Simbol | Citire | Sens | |---|---|---| | $\forall x \in A$ | Pentru orice $x$ din $A$ | Proprietatea trebuie să fie adevărată pentru toate elementele | | $\exists x \in A$ | Există un $x$ din $A$ | Proprietatea e adevărată pentru cel puțin un element | | $\exists! x \in A$ | Există un unic $x$ din $A$ | Proprietatea e adevărată pentru exact un element | | $\nexists x \in A$ | Nu există niciun $x$ din $A$ | Proprietatea e falsă pentru toate elementele |
Exemple uzuale
- "Toate numerele naturale sunt mai mari sau egale cu 0": $\forall n \in \mathbb{N}, n \ge 0$
- "Există un număr întreg care adunat cu 2 dă 7": $\exists x \in \mathbb{Z}, x + 2 = 7$
- "Orice șir mărginit de numere reale are o subșir convergent" (Bolzano–Weierstrass): $\forall (a_n) \subset \mathbb{R}, (a_n) \text{ mărginit} \implies \exists (a_{n_k}) \text{ convergent}$
Negarea cuantificatorilor
- $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$
- $\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$
Regulă: negația unui $\forall$ devine $\exists$, și invers.
3. Funcții
Definiție formală
O funcție $f: A \to B$ este o regulă care asociază fiecărui element $x \in A$ exact un element $f(x) \in B$.
- $A$ = domeniul (mulțimea de plecare)
- $B$ = codomeniul (mulțimea de sosire)
- $f(x)$ = imaginea lui $x$ prin $f$
Tipuri de funcții
| Tip | Definiție | Exemple | |---|---|---| | Injectivă (unu-la-unu) | $f(x_1)=f(x_2) \implies x_1=x_2$ | $f(x)=2x$, $f(x)=x^3$ | | Surjectivă (pe) | $\forall y \in B, \exists x \in A: f(x)=y$ | $f(x)=x$, $f(x)=x^3$ | | Bijectivă | injectivă și surjectivă | $f(x)=x+1$, permutările | | Constantă | $f(x)=c$, $\forall x$ | $f(x)=5$ | | Identitate | $f(x)=x$ | $\text{id}_A$ |
Compunerea funcțiilor
$$(g \circ f)(x) = g(f(x))$$
Compunerea e asociativă: $h \circ (g \circ f) = (h \circ g) \circ f$, dar nu comutativă: $f \circ g \ne g \circ f$ în general.
Funcții inverse
Dacă $f: A \to B$ e bijectivă, atunci există $f^{-1}: B \to A$ astfel încât:
$$f^{-1}(f(x)) = x \quad\text{și}\quad f(f^{-1}(y)) = y$$
4. Relații
Definiție
O relație binară $R$ între $A$ și $B$ este o submulțime a produsului cartezian: $R \subseteq A \times B$. Scriem $aRb$ pentru $(a,b) \in R$.
Proprietăți (relații pe aceeași mulțime $R \subseteq A \times A$)
| Proprietate | Definiție | Exemplu | |---|---|---| | Reflexivă | $\forall a \in A: aRa$ | $"="$ (egalitatea) | | Simetrică | $aRb \implies bRa$ | $"="$ (egalitatea), relația de prietenie | | Antisimetrică | $(aRb \land bRa) \implies a=b$ | $\le$ (mai mic sau egal) | | Tranzitivă | $(aRb \land bRc) \implies aRc$ | $<$, $\le$, $"="$ | | Totală | $\forall a,b \in A: aRb \lor bRa$ | $\le$ pe $\mathbb{R}$ |
Tipuri fundamentale de relații
-
Relație de echivalență — reflexivă, simetrică, tranzitivă. Partitionează mulțimea în clase de echivalență.
- Exemplu: $a \equiv b \pmod{n}$ (congruența modulo $n$)
-
Relație de ordine parțială — reflexivă, antisimetrică, tranzitivă.
- Exemplu: $A \subseteq B$ (incluziunea mulțimilor)
- Dacă e și totală, e ordine totală (ex: $\le$ pe $\mathbb{R}$)
-
Relație de ordine strictă — ireflexivă, tranzitivă.
- Exemplu: $a < b$
Notații pentru relații de ordine
- $a \preceq b$ — ordine parțială (generic)
- $a \prec b$ — ordine strictă asociată
- $a \sqsubseteq b$ — ordine în latice (domain theory)
- $a \le b$ — ordine totală uzuală
5. Demonstrații matematice
Demonstrația directă
Pornești de la premise și aplici pași logici până la concluzie.
Exemplu: Dacă $n$ e par, atunci $n^2$ e par. $n = 2k \implies n^2 = 4k^2 = 2(2k^2)$, deci e par. $\square$
Demonstrația prin contradicție (reductio ad absurdum)
Presupui că concluzia e falsă și derivezi o contradicție logică.
Exemplu: $\sqrt{2}$ e irațional. Presupunem $\sqrt{2} = p/q$ cu fracție ireductibilă. Atunci $2q^2 = p^2$, deci $p^2$ e par $\implies p$ e par $\implies p=2k \implies 2q^2=4k^2 \implies q^2=2k^2 \implies q$ par. Contradicție: $p$ și $q$ au factor comun 2. $\square$
Demonstrația prin inducție matematică
Se aplică pentru propoziții $P(n)$ cu $n \in \mathbb{N}$.
Pași:
- Baza: Arăți $P(0)$ (sau $P(1)$) e adevărată.
- Pasul inductiv: Presupui $P(k)$ adevărată și arăți $P(k+1)$ adevărată.
Exemplu: Suma primelor $n$ numere: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
- Baza $n=1$: $1 = \frac{1 \cdot 2}{2}$. Adevărat.
- Pas: $\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$. $\square$
Demonstrația constructivă
Construiești explicit un exemplu care satisface proprietatea.
Exemplu: Există numere prime mai mari decât 10. $\implies$ 11 e prim. $\square$
Demonstrația prin contraexemplu
Pentru a infirma o afirmație universală, găsești un singur caz care o contrazice.
Exemplu: "Toate numerele prime sunt impare" e fals, pentru că 2 e prim și e par.
6. Notații matematice frecvente
Suma și produsul
$$\sum_{i=1}^{n} a_i = a_1 + a_2 + \dots + a_n$$ $$\prod_{i=1}^{n} a_i = a_1 \cdot a_2 \cdot \dots \cdot a_n$$
Factorial
$$n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n$$ Prin convenție: $0! = 1$.
Operatorul de atribuire
În algoritmi, $x \leftarrow x + 1$ înseamnă "incrementează $x$". Nu e o ecuație, e o comandă.
Inegalități uzuale
| Inegalitate | Formula | |---|---| | Triunghiului | $|a + b| \le |a| + |b|$ | | Cauchy–Schwarz | $(\sum a_i b_i)^2 \le (\sum a_i^2)(\sum b_i^2)$ | | Bernoulli | $(1 + x)^n \ge 1 + nx$ pentru $x > -1$, $n \in \mathbb{N}$ | | Medii | $\min \le \text{armonică} \le \text{geometrică} \le \text{aritmetică} \le \max$ |
7. Structuri algebrice de bază
O operație binară $\circ$ pe o mulțime $A$ e o funcție $\circ: A \times A \to A$.
Proprietăți ale operațiilor
| Proprietate | Definiție | |---|---| | Asociativitate | $(a \circ b) \circ c = a \circ (b \circ c)$ | | Comutativitate | $a \circ b = b \circ a$ | | Element neutru | $\exists e: a \circ e = e \circ a = a$ | | Element invers | $\forall a, \exists a^{-1}: a \circ a^{-1} = e$ | | Distributivitate | $a \circ (b \star c) = (a \circ b) \star (a \circ c)$ |
Ierarhia structurilor
| Structură | Operații | Proprietăți | |---|---|---| | Monoid | $\circ$ | Asociativ + element neutru | | Grup | $\circ$ | Asociativ + neutru + inverse (ex: $(\mathbb{Z}, +)$) | | Grup abelian | $\circ$ | Grup + comutativ (ex: $(\mathbb{R}, +)$) | | Inel | $+, \times$ | $(+, \text{abelian})$, $\times$ asociativ, $\times$ distributiv peste $+$ (ex: $\mathbb{Z}$) | | Corp | $+, \times$ | Inel + $\times$ are inverse (ex: $\mathbb{R}, \mathbb{Q}, \mathbb{C}$) | | Spațiu vectorial | $+, \cdot$ | Adunare de vectori + înmulțire cu scalari dintr-un corp |
8. Asimptotice: pe scurt
Notațiile asimptotice sunt definite formal astfel:
| Notație | Definiție | |---|---| | $f(n) \in O(g(n))$ | $\exists c, n_0: 0 \le f(n) \le c \cdot g(n), \forall n \ge n_0$ | | $f(n) \in \Omega(g(n))$ | $\exists c, n_0: 0 \le c \cdot g(n) \le f(n), \forall n \ge n_0$ | | $f(n) \in \Theta(g(n))$ | $f(n) \in O(g(n)) \land f(n) \in \Omega(g(n))$ | | $f(n) \in o(g(n))$ | $\lim_{n\to\infty} f(n)/g(n) = 0$ |
Pentru o analiză detaliată, vezi articolul dedicat Notația Big O.
Referințe și lecturi suplimentare
- Matematica pentru informatică: De la bază la mod expert — continuarea naturală, cu aplicații avansate
- Lambda Calculus — fundamente matematice ale calculabilității
- Limbaje formale și automate — mulțimi, funcții și relații aplicate în teoria limbajelor
- Knuth, D. Concrete Mathematics — referința clasică
- Rosen, K. Discrete Mathematics and Its Applications — manual universitar standard