Preogettazione logica - Appunti

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. ∅
2. {∅} 1 elemento
3. { {∅} } 1 elemento
4. { 0 } 1 elemento
5. { ∅, {∅} } 2 elementi
6. { 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)

1^a 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

2^a 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

ψ₂ φ₀ψ₂ A φ B φ₀ψ ψ₀φ ψ₀φ₂ φ₂

ψ₂ ψ₀φ≡id_A & φ φ₂≡id_B ⇒ ψ₁=ψ₂

dim.

ψ₁=ψ₀ id_B= ψ₁ o (φ φ) = (ψ₀ φ) φ₂ = id_A o φ₂= ψ₁

A φ B

1. ∃!φ: B t.c. ψ₀φ≡id_A ψ₀≡id_B
2. φ è bietttiva

dim.

1. (1) ⇒ (2)

ψ₀ φ≡id_A iniettiva ⇒ φ

φ φ≡id_B suriettiva ⇒ φ suriettiva

φ è biettiva

_Σⁿ qⁱ = (1 - qⁿ⁺¹) / (1 - q) per q ∈ R {1}

dimostriamo per induzione

• P(0) _Σⁱ⁼⁰ qⁱ = (1 - q⁰⁺¹) / (1 - q) = 1 ✔
• P(n) _Σⁱ⁼⁰ qⁱ = (1 - qⁿ⁺¹) / (1 - q) -> _Σⁱ⁼⁰ qⁱ = (1 - qⁿ⁺²) / (1 - q) n+1_Σⁱ⁼⁰ qⁱ = _Σⁱ⁼⁰ qⁱ + qⁿ⁺¹ =(1 - qⁿ⁺¹) / (1 - q) + qⁿ⁺¹ = (1 - qⁿ⁺¹ + qⁿ⁺¹ - qⁿ⁺² ) / (1 - q) = (1 - qⁿ⁺²) / (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:

1. ∀ n ≥ 5 2⁵ > n²
2. n! ≥ 2^{n - 1}

Algoritmo di Euclide (per il MCD)

a,b b≠0 MCD(a,b):

r₁=a r₀=b

r_n=r₀.q₁+r₁ r₀=r₁.q₂+r₂ r₁=r₂.q₃+r₃ ... r_n-1=r_n.q_n+1+r_n+1 ...=0

r_n è MCD(a,b)

Come funziona?

Se r_n+1=0 allora r_n=MCD(a,b) 1) L'algoritmo termina 2) r_n∣a r_n∣b 3) c|a d|b → c|r_n