Corso di Laurea in Informatica Prova scritta del 24 Maggio 2004

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {1, 2, …, 80} l’insieme dei numeri interi positivi minori o uguali a 80. Determinare le cardinalità degli insiemi seguenti:

1. A × A ;

2. {(x, y) ∈ A × A | x ≠ y} ;

3. {(x, y) ∈ A × A | x < y} ;

4. {X ⊂ A | |X| = 3} ;

5. {(x, y, z) ∈ A × A × A | x < y < z}.

Esercizio 2. Siano A e B sottoinsiemi non vuoti di ℕ.

• Quali delle seguenti formule formalizza la proprietà: “ min A ≤ max B ” ? 1. ∃x ∈ A ∀y ∈ B (x ≤ y) ;

2. ∀y ∈ B ∃x ∈ A (x ≤ y) ;

3. ∀x ∈ A ∃y ∈ B (x ≤ y) ;

4. ∃x ∈ A ∃y ∈ B (x ≤ y) ;

5. ∀x ∈ A ∀y ∈ B (x ≤ y) ;

6. ∃y ∈ B ∀x ∈ A (x ≤ y) .

• Scrivi una formula che formalizza la proprietà: “ min A ≤ min B ”.

Esercizio 3. Siano A = {a, b, c, d, e, f}, B = {a, b, c, d}, e sia F : P(A) → P(B) definita da F (X) = X ∩ B. Stabilire (giustificando) se ciascuna delle seguenti affermazioni è vera o falsa.

1. ∀X, Y ∈ P(A) ( X ⊆ Y → F (X) ⊆ F (Y) )

2. ∀x ∈ B ∀X ⊆ A ( x ∈ X → x ∈ F (X) )

3. ∀x ∈ A ∀X ⊆ A ( x ∈ X → x ∈ F (X) ) Esercizio 4. Sia b ∈ ℝ, b > 2. Definiamo per induzione la successione {g_{n} | n ∈ ℕ} ponendo g_{0} = b, g_{n+1} = g_{n}^{2} − 2. Dimostrare che:

1. ∀n g_{n} > 2;

2. la successione g_{n} è crescente.

Esercizio 5. Determinare i valori di n per cui l’equazione

9x ≡ n (mod n^{2})

ammette soluzioni. Determinare inoltre le soluzioni per n = 11.

Corso di Laurea in Informatica Prova scritta del 24 Maggio 2004

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia B = {1, 2, …, 90} l’insieme dei numeri interi positivi minori o uguali a 90. Determinare le cardinalità degli insiemi seguenti:

1. B × B ;

2. {(x, y) ∈ B × B | x ≠ y} ;

3. {(x, y) ∈ B × B | x < y} ;

4. {Y ⊂ B | |Y | = 4} ;

5. {(x, y, z) ∈ B × B × B | x < y < z}.

Esercizio 2. Siano A e B sottoinsiemi non vuoti di ℕ.

• Quali delle seguenti formule formalizza la proprietà: “ max A ≤ min B ” ? 1. ∃x ∈ A ∀y ∈ B (x ≤ y) ;

2. ∀y ∈ B ∃x ∈ A (x ≤ y) ;

3. ∀x ∈ A ∃y ∈ B (x ≤ y) ;

4. ∃x ∈ A ∃y ∈ B (x ≤ y) ;

5. ∀x ∈ A ∀y ∈ B (x ≤ y) ;

6. ∃y ∈ B ∀x ∈ A (x ≤ y) .

• Scrivi una formula che formalizza la proprietà: “ max A ≥ min B ”.

Esercizio 3. Determinare i valori di k per cui l’equazione

9x ≡ k (mod k^{2})

ammette soluzioni. Determinare inoltre le soluzioni per k = 11. Esercizio 4. Siano A = {1, 2, 3, 4, 5, 6}, B = {1, 2, 3, 4}, e sia F : P(A) → P(B) definita da F (X) = X ∩ B. Stabilire (giustificando) se ciascuna delle seguenti affermazioni è vera o falsa.

1. ∀X, Y ∈ P(A) ( X ⊆ Y → F (X) ⊆ F (Y) )

2. ∀x ∈ A ∀X ⊆ A ( x ∈ X → x ∈ F (X) )

3. ∀x ∈ B ∀X ⊆ A ( x ∈ X → x ∈ F (X) ) Esercizio 5. Sia a ∈ ℝ, a > 2. Definiamo per induzione la successione {f_{n} | n ∈ ℕ} ponendo f_{0} = a, f_{n+1} = f_{n}^{2} − 2. Dimostrare che

1. ∀n f_{n} > 2;

2. la successione f_{n} è crescente.