Algebra - Matematica Discreta

Parte di Algebra

LOGICA: scritto e orale facoltative - orale alza come abbassa

ALG e GEST: scritto e orale facoltativo

Numeri naturali → numeri interi positivi

N = { 0, 1, 2, 3, ... }

Proprietà dei numeri naturali

1. proprietà commutativa somma a + b = b + a   ∀ a, b ∈ N
2. proprietà associativa somma (a + b) + c = a + (b + c)   ∀ a, b, c ∈ N
3. esiste elemento neutro somma a + 0 = 0   ∀ a ∈ N
4. prop associativa commutativa prodotto a · b = b · a   ∀ a, b ∈ N
5. prop associativa prodotto a · (b · c) = (a · b) · c   ∀ a, b, c ∈ N
6. elemento neutro prodotto a · 1 = 1 · a = a   ∀ a ∈ N
7. prop distributiva prodotto rispetto a somma a · (b + c) = a · b + a · c   ∀ a, b, c ∈ N

Regola dell'insieme dei n. naturali c'è il processo di dimostrazione perinduzione → con una serie di passaggi logici, è alla \[\dots\] una dimostrazioneServe per dimostrare le proprietà legate ai numeri naturali→ serve per dimostrare che una proprietà P(m) è vera per ogninumero naturale.

OSS: La base induttiva è detto δ ∞† il numero m

In questo caso di dimostra una proprietà P(m) ∀ n > m †

Parte di Algebra

LOGICA: scritto e orale facoltative → orale obbl. come abbonas

ALG e GEST: scritto e orale facoltative

Numeri naturali ⇒ numeri interi positivi

N = {0, 1, 2, 3, ...}

Proprietà dei numeri naturali

1. Proprietà commutativa somma a + b = b + a ∀ a, b ∈ ℕ
2. Proprietà associativa somma (a + b) + c = a + (b + c) ∀ a, b, c ∈ ℕ
3. Esiste elemento neutro somma a + 0 = a ∀ a ∈ ℕ
4. Prop. commutativa prodotto a · b = b · a ∀ a, b ∈ ℕ
5. Prop. associativa prodotto a · (b · c) = (a · b) · c ∀ a, b, c ∈ ℕ
6. Elemento neutro prodotto a · 1 = 1 · a = a ∀ a ∈ ℕ
7. Prop. distributiva prodotto rispetto a somma a · (b + c) = a · b + a · c ∀ a, b, c ∈ ℕ

Legato all'insieme dei n. naturali c'è il processo di dimostrazione per induzione → con una serie di passaggi logici, si arriva ad una dimostrazione.

Serve per dimostrare le proprietà legate ai numeri naturali → serve per dimostrare che una proprietà P(m) è vera per ogni numero naturale.

OSS.: La base induttiva è di solito 0 ed 1 ma può essere anche un altro numero m^*

In questo caso si dimostra una proprietà P(m) ∀ n > m^*

Principio di induzione

Se P(n) è una formula tale che

• P(0) è vera _{Base induttiva}
• ∀m ∈ ℕ se P(m) è vera allora P(m+1) è vera

si ha che P(m) è vera ∀m ∈ ℕ

Es. 1

Dimostrare che la somma dei primi n numeri naturali è uguale a m:

\[ m: \frac{m(m+1)}{2} \]

Ove si assuma che:

• \[1+2+3+...+m = \frac{m(m+1)}{2}\]

Dimostrazione per ind: Base induttiva m=1

Dimostriamo che P(0) è vera

• se m=1
• \[1= \frac{1 \cdot 2}{2} \]

Supponiamo che P(m) sia vera

P(m+1) è vera, cioè che:

• \[1+2+...+m+(m+1) = \frac{m(m+1)}{2} + (m+1)\]

Fine della dimostrazione.

ES. 2

Dimostrare che la somma dei primi n numeri dispari è uguale a m².

1 + 3 + 5 + 7 + ... + (2m-1) = m²

Σ_k=1^m 2k - 1 = m²   P(m)

Base Inizitiva P(1)

1 = 1² SI ⇒ P(1) è vera

2) Supponiamo P(m) vera e dimostriamo che P(m+1) sia vera,ovvero che

Σ_k=1^m+1 2K - 1 = m² = (m+1)² P(m+1)

Σ_k=1^M 2K + 2(m+1) - 1

= m² + 2(m+1) - 1 = m² + 2m+2 - 1 = m² + 2m + 2 = (m+1)²

DIMOSTRAZIONE TERMINATA

ES. 3

Dimostrare la disuguaglianza (t+x)^m >= t + mx   ∀ m >= 2   ∀ x > -1

x ≠ 0   (x ε R)

Dimostrazione

P(2) Base Iniz.

(t+x)² >= t + 2x ?

(t+x)² = t² + x² >= t+2x   VERA

2) Supponiamo P(m) vera e dimostriamo che P(m+1) è verache vale (t+x)^m+1 >= t + (m+1)x (deve corrispondere)

(t+x)^m+1 = (t+x)^m(t+x)

= (t+x)^m t + x >= (t+mx)(t+x)

= t + (t+m)x = mx²

= t + (t+m)x = mx² >= 0

DIMOSTRAZIONE TERMINATA

ES. 4

Di