Preogettazione logica - Appunti

INSIEMI

N, R, Q, Z

• A ⊆ B ∀a se a ∈ A, a ∈ B (inclusione)
• A = B A ⊆ B e B ⊆ A (uguaglianza)
• A ⊂ B A ⊆ B e A ≠ B (inclusione stretta)
• ∅ insieme vuoto

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. {{∅, ∅}} 1 elemento
5. {∅, {∅}} 2 elementi
6. {R, N} 2 elementi

^p(E) = 2ⁿ

numero elementi

^p({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3},

                 {1, 2, 3}} ∅ = 2³ = 8

∅ ∈ A <=> per ogni a      se a ∈ ∅ allora a ∈ A

B ⊆ C <=> per ogni a      se a ∈ B allora a ∈ C

negare significa trovare un a t.c. a ∈ B e a ∉ C

IMMAGINE

a ∈ A , f(a) e' detta immagine di A secondo f

CONTROIMMAGINE

f : A → B   B'₁ ⊆ B

f^-1(B'₁) = { a | a ∈ A e f(a) ∈ B' }

e' controimmagine di B'₁ secondo f

A _φ → B _γ → C

γφ è iniettiva → φ è iniettiva

γφ è suriettiva → γ è suriettiva

γφ è iniettiva → γ è iniettiva

γφ è suriettiva → φ è suriettiva

A _F → B _g → C _h → D

hχg(χf) = (h•g)•f

non è vero che h•f = F•h

NUMERI DI PEANO

1) 0 ∈ ℕ2) S: ℕ → ℕ è iniettiva3) 0 ∉ Im(S) , 0 ∉ S(ℕ)4) principio di induzione    sia P ⊆ ℕ se a) 0 ∈ P        b) ∀m ∈ ℕ se m ∈ P allora S(m) ∈ P    allora P = ℕ    sia P una proprietà su ℕ.P(0) & ∀m ∈ ℕ · P(m) → P(S(m)) ⇒ ∀x ∈ ℕ · P(x)

_{∑ⁿi=0 qⁱ = ^{1 - qn+1}/1-q}

per q ∈ ℝ \ {n ≠ 1}

dimostriamo per induzione

• P(0)

_{∑⁰i=0 qⁱ = ^{1 - q0+1}/1-q = 1 ✔}

• P(n)

_{∑ⁿi=0 qⁱ = ^{1 - qn+1}/1-q}

⟹_{∑ⁿ⁺¹i=0 qⁱ = ^{1 - qn+2}/1-q}

=_{∑ⁿi=0 qⁱ + qⁿ⁺¹}

=^{1 - qn+1}/_1-q + qⁿ⁺¹

=^{(1-q)qn+1 + 1 - qn+2}/_1-q

= ^{1 - qn+2}/_1-q ✔

ϑ: ℕ → ℕ

0 ∈ ϑ (ℕ)

ϑ è iniettiva

ϑ (ℕ) = ℕ - 0

P(h): ∃x n = x + n ∀n > 0

P(0): 0 = x + n x = -n √

P(h): ∃x n = x + n ⇒ ∃y n + n = y + n

A ⇒ B

esercizi:

1. ∀n ≥ 5 2⁵ > n²
2. n! > 2ⁿ⁻¹

DEFINIZIONE DI DIVISIONE

teorema

a, b

b ≠ 0

esiste un'unica coppia (q, r) di numeri tali che:

1. 0 ≤ r < |b|
2. a = b q + r

se r = 0 a è divisibile per b

b | a (b|a b|c) => b|a-c

∃q a = bq

N.B.

a | b significa a divide b(b è multiplo di a)

∃n t.c. a⋅n = b