COMPITO DI MATEMATICA DISCRETA Parte I 2 Luglio 2009

COMPITO DI MATEMATICA DISCRETA Parte I 2 Luglio 2009

1. Formalizzare la seguente frase: “x `e un numero primo”.

Soluzione: x `e un numero primo sse

(x 6= 0) ∧ (x 6= 1) ∧ (∀y)(∀z)(x = y × z → (y = x ∨ z = x)).

2. Dimostrare per induzione, utilizzando la formula di Stifel ⁿk
= ^{n − 1}k − 1
+ ^{n − 1}k
, che per ogni intero n ≥ 1

n

X

k=0

n

k
= 2ⁿ.

Soluzione: Base dell’induzione n = 1: ¹0
+ ¹1
= 1 + 1 = 2 = 2¹. Supponiamo che l’identita’ sia vera per n e dimostriamola per n + 1.

2ⁿ⁺¹ = 2ⁿ+ 2ⁿ

= Pn k=0

n

k
+ Pⁿ_k=0 ⁿk

per ipotesi d’induzione

= Pn+1 k=1

n

k − 1
+ Pⁿ_k=0 ⁿk

= ⁿ_n
+ Pⁿ_k=1 k − 1ⁿ
+ Pⁿ_k=1 ⁿk
+ ⁿ0

= 1 +Pn

k=1( k − 1ⁿ
+ ⁿk
) + 1

= 1 +Pn k=1

n + 1

k
+ 1 per la formula di Stifel

= ^{n + 1}n + 1
+ Pⁿ_k=1 ^{n + 1}k
+ ^{n + 1}0

= Pn+1 k=0

n + 1 k

3. Si dimostri che esistono infinite funzioni surgettive dall’insieme dei numeri naturali nell’insieme {0, 1, 2, 3}.

Soluzione: Un insieme X `e infinito se esiste una funzione iniettiva da N0in X. Per ogni numero naturale n si consideri la seguente funzione fn: N0 → {0, 1, 2, 3}:

f_n(x) =  3 se x = n x mod 3 altrimenti

dove x mod 3 `e uguale al resto della divisione di x per 3. Quindi, x mod 3 pu`o essere uguale a 0 oppure 1 oppure 2. Se n 6= k allora f_n 6= f_k perch´e f_n(n) = 3 mentre fk(n) = n mod 3 < 3.

1