INSIEMI
N, R, Q, Z
- A ⊆ B ∀ x se ∈ A, x ∈ B (inclusione)
- A = B ⟺ A ⊆ B e B ⊆ A (uguaglianza)
- A ⊂ B ⟺ A ⊆ B e A ≠ B (inclusione stretta)
- ∅ insieme vuoto
α P(x) A = {x | P(x)} (assioma di comprensione)
es.
A = {x | x ∈ R e x > 0} reali maggiori di 0
P = {x | x ∈ N e ∃r ∈ N t.c. x = 2r} numeri pari
- ∅
- {∅} 1 elemento
- { {∅} } 1 elemento
- { 0 } 1 elemento
- { ∅, {∅} } 2 elementi
- { R, N } 2 elementi
Paradosso di Russel
R = {x | x ∉ x}
ho definito R grazie alla struttura
A = {x | P(x)}, ma R non è un insieme!
infatti,
R ∈ R ⇒ R ∉ R
R ∉ R ⇒ R ∈ R
contraddizione!
UNIONE
A ∪ B = {x | x ∈ A o x ∈ B}
INTERSEZIONE
A ∩ B = {x | x ∈ A e x ∈ B}
SOTTRAZIONE
A \ B = {x | x ∈ A e x ∉ B}
TEOREMA
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
1a dim:
A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C)
x ∈ A ∪ (B ∩ C)
- x ∈ A
- x ∈ B ∩ C
- x ∈ B
- x ∈ C
caso 1
x ∈ A → x ∈ A ∪ B e x ∈ A ∪ C → x ∈ (A ∪ B) ∩ (A ∪ C)
caso 2
x ∈ B e x ∈ C → x ∈ A ∪ B e x ∈ A ∪ C → x ∈ (A ∪ B) ∩ (A ∪ C)
OK
2a dim:
A ∪ (B ∩ C) ⊇ (A ∪ B) ∩ (A ∪ C)
- x ∈ A
- x ∈ A ∪ B
- x ∈ B
- x ∈ A
- x ∈ A ∪ C
- x ∈ C
- x ∈ (A ∪ B) ∩ (A ∪ C)
caso 1
x ∈ A → x ∈ A ∪ (B ∩ C)
caso 2
x ∉ A → x ∈ B e x ∈ C → x ∈ B ∩ C → x ∈ A ∪ (B ∩ C)
OK
FUNZIONE INVERSA
ψ2 φ0ψ2 A φ B φ0ψ ψ0φ ψ0φ2 φ2
ψ2 ψ0φ≡idA & φ φ2≡idB ⇒ ψ1=ψ2
dim.
ψ1=ψ0 idB= ψ1 o (φ φ) = (ψ0 φ) φ2 = idA o φ2= ψ1
A φ B
- ∃!φ: B t.c. ψ0φ≡idA ψ0≡idB
- φ è bietttiva
dim.
- (1) ⇒ (2)
ψ0 φ≡idA iniettiva ⇒ φ
iniettivaφ φ≡idB suriettiva ⇒ φ suriettiva
φ è biettiva
Σn qi = (1 - qn+1) / (1 - q) per q ∈ R {1}
dimostriamo per induzione
- P(0) Σi=0 qi = (1 - q0+1) / (1 - q) = 1 ✔
- P(n) Σi=0 qi = (1 - qn+1) / (1 - q) -> Σi=0 qi = (1 - qn+2) / (1 - q) n+1Σi=0 qi = Σi=0 qi + qn+1 =(1 - qn+1) / (1 - q) + qn+1 = (1 - qn+1 + qn+1 - qn+2 ) / (1 - q) = (1 - qn+2) / (1 - q) ✔
σ: N → N
0 ∈ Θ(N)
σ è iniettiva
Θ (N) = N - O
P(h): ∃ x n = x + n ∀ n > 0
P(O): O = x + n x = -n √
P(h): ∃ x n = x + n => ∃ y n + n B
esercizi:
- ∀ n ≥ 5 25 > n2
- n! ≥ 2n - 1
Algoritmo di Euclide (per il MCD)
a,b b≠0 MCD(a,b):
r1=a r0=b
rn=r0.q1+r1 r0=r1.q2+r2 r1=r2.q3+r3 ... rn-1=rn.qn+1+rn+1 ...=0
rn è MCD(a,b)
Come funziona?
Se rn+1=0 allora rn=MCD(a,b) 1) L'algoritmo termina 2) rn∣a rn∣b 3) c|a d|b → c|rn
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
-
Logica: teoria, Filosofia della mente, logica e lingue naturali
-
Automazione dei processi industriali - Il controllore a logica programmabile (M1_05)
-
Logica - problema degli esistenziali negativi nella logica contemporanea
-
Appunti di Logica e metodologia giuridica