Corso di Laurea in Informatica Prova scritta del 14 Gennaio 2004

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Nell’universo dei numeri naturali, sia P (x) il predicato: “x è un numero pari”, e sia D(x) il predicato: “x è un numero dispari”.

• Quale delle seguenti formule esprime l’enunciato: “Per ogni numero pari x, f(x) ≥ 0” ?

• Quali delle seguenti formule sono una la negazione dell’altra ?

\begin{matrix}1. ∀x ( P (x) → f(x) < 0 ); & 2. ∃x ( D(x) ∧ f(x) < 0 ); & 3. ∃x ( D(x) → f(x) < 0 ); \\ 4. ∀x ( f(x) ≥ 0 → P (x) ); & 5. ∀x ( P (x) → f(x) ≥ 0 ); & 6. ∃x ( P (x) ∧ f(x) ≥ 0 ). \end{matrix}

Esercizio 2. Siano

A = ℚ \ {1} = {x ∈ ℚ | x ≠ 1},
B = ℚ \ {−1} = {x ∈ ℚ | x ≠ −1},
C = ℚ \ {1, −1, 0} = {x ∈ ℚ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0},
D = C ∩ ℤ = {x ∈ ℤ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0}.

Si consideri la formula f(x) = \frac{x+1}{−x+1}.

1. Stabilire in quali dei seguenti casi la formula f(x) definisce una funzione con il dominio e codominio specificati:

a) f : A → A; b) f : B → B; c) f : C → C; d) f : D → D.

2. Dopo aver verificato che f: C → C è ben definita, determinare una espressione algebrica che definisce (f ∘ f)(x).

3. Determinare inoltre se la funzione f: C → C è iniettiva, surgettiva, biunivoca.

4. Stabilire se f : C → C è una funzione invertibile e in tal caso trovare una espressione algebrica che definisce la funzione inversa f^{−1} : C → C.

Esercizio 3. Indichiamo con X_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare quanti elementi di X_{180} sono multipli sia di 5 che di 11;

2. Determinare quanti elementi di X_{180} non sono nè multipli di 5 nè multipli di 11;

3. Determinare quanti sottoinsiemi di X_{180} contengono almeno un multiplo di 5;

Esercizio 4. Sia u_{0} = 4; u_{1} = 9; u_{2} = 16; u_{n+3} = 3u_{n+2} − 3u_{n+1} + u_{n}. Dimostrare per induzione che u_{n} = (n + 2)^{2} per ogni n ∈ ℕ.

Esercizio 5. Determinare tutte le soluzioni intere x della congruenza:

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Nell’universo dei numeri naturali, sia P (x) il predicato: “x è un numero pari”, e sia D(x) il predicato: “x è un numero dispari”.

• Quale delle seguenti formule esprime l’enunciato: “Per ogni numero dispari x, f(x) > 0” ?

• Quali delle seguenti formule sono una la negazione dell’altra ?

\begin{matrix}1. ∃x ( P (x) → f(x) ≤ 0 ); & 2. ∀x ( D(x) → f(x) > 0 ); & 3. ∀x ( f(x) > 0 → D(x) ); \\ 4. ∃x ( P (x) ∧ f(x) > 0 ); & 5. ∀x ( D(x) → f(x) ≤ 0 ); & 6. ∃x ( P (x) ∧ f(x) ≤ 0 ). \end{matrix}

Esercizio 2.Siano

A = ℚ \ {1} = {x ∈ ℚ | x ≠ 1},
B = ℚ \ {−1} = {x ∈ ℚ | x ≠ −1},
C = ℚ \ {1, −1, 0} = {x ∈ ℚ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0},
D = C ∩ ℤ = {x ∈ ℤ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0}.

Si consideri la formula f(x) = \frac{x−1}{x+1}.

1. Stabilire in quali dei seguenti casi la formula f(x) definisce una funzione con il dominio e codominio specificati:

a) f : A → A; b) f : B → B; c) f : C → C; d) f : D → D.

2. Dopo aver verificato che f: C → C è ben definita, determinare una espressione algebrica che definisce (f ∘ f)(x).

3. Determinare inoltre se la funzione f: C → C è iniettiva, surgettiva, biunivoca.

4. Stabilire se f : C → C è una funzione invertibile e in tal caso trovare una espressione algebrica che definisce la funzione inversa f^{−1} : C → C.

Esercizio 3. Indichiamo con X_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare quanti elementi di X_{140} sono multipli sia di 3 che di 11;

2. Determinare quanti elementi di X_{140} non sono nè multipli di 3 nè multipli di 11;

3. Determinare quanti sottoinsiemi di X_{140} contengono almeno un multiplo di 11;

4. Determinare quanti sottoinsiemi di X_{140} non contengono multipli di 3 ma contengono almeno un multiplo di 11.

Esercizio 4. Sia u_{0} = 1; u_{1} = 0; u_{2} = 1; u_{n+3} = 3u_{n+2} − 3u_{n+1} + u_{n}. Dimostrare per induzione che u_{n} = (n − 1)^{2} per ogni n ∈ ℕ.

Esercizio 5. Determinare tutte le soluzioni intere x della congruenza:

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Nell’universo dei numeri naturali, sia P (x) il predicato: “x è un numero pari”, e sia D(x) il predicato: “x è un numero dispari”.

• Quale delle seguenti formule esprime l’enunciato: “Per ogni numero pari x, f(x) ≤ 0”?

• Quali delle seguenti formule sono una la negazione dell’altra ?

\begin{matrix}1. ∃x ( D(x) ∧ f(x) > 0 ); & 2. ∃x ( D(x) → f(x) > 0 ); & 3. ∃x ( P (x) ∧ f(x) ≤ 0 ) \\ 4. ∀x ( P (x) → f(x) ≤ 0 ); & 5. ∀x ( f(x) ≤ 0 → P (x) ); & 6. ∀x ( P (x) → f(x) > 0 ). \end{matrix}

Esercizio 2.Siano

A = ℚ \ {1} = {x ∈ ℚ | x ≠ 1},
B = ℚ \ {−1} = {x ∈ ℚ | x ≠ −1},
C = ℚ \ {1, −1, 0} = {x ∈ ℚ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0},
D = C ∩ ℤ = {x ∈ ℤ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0}.

Si consideri la formula f(x) = \frac{−x−1}{x−1}.

1. Stabilire in quali dei seguenti casi la formula f(x) definisce una funzione con il dominio e codominio specificati:

a) f : A → A; b) f : B → B; c) f : C → C; d) f : D → D.

2. Dopo aver verificato che f: C → C è ben definita, determinare una espressione algebrica che definisce (f ∘ f)(x).

3. Determinare inoltre se la funzione f: C → C è iniettiva, surgettiva, biunivoca.

4. Stabilire se f : C → C è una funzione invertibile e in tal caso trovare una espressione algebrica che definisce la funzione inversa f^{−1} : C → C.

Esercizio 3. Indichiamo con X_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare quanti elementi di X_{160} sono multipli sia di 7 che di 11;

2. Determinare quanti elementi di X_{160} non sono nè multipli di 7 nè multipli di 11;

3. Determinare quanti sottoinsiemi di X_{160} contengono almeno un multiplo di 7;

4. Determinare quanti sottoinsiemi di X_{160} non contengono multipli di 7 ma contengono almeno un multiplo di 11.

Esercizio 4. Sia u_{0} = 1; u_{1} = 4; u_{2} = 9; u_{n+3} = 3u_{n+2} − 3u_{n+1} + u_{n}. Dimostrare per induzione che u_{n} = (n + 1)^{2} per ogni n ∈ ℕ.

Esercizio 5. Determinare tutte le soluzioni intere x della congruenza:

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Nell’universo dei numeri naturali, sia P (x) il predicato: “x è un numero pari”, e sia D(x) il predicato: “x è un numero dispari”.

• Quale delle seguenti formule esprime l’enunciato: “Per ogni numero dispari x, f(x) ≤ 0” ?

• Quali delle seguenti formule sono una la negazione dell’altra ?

\begin{matrix}1. ∀x ( f(x) ≤ 0 → D(x) ); & 2. ∃x ( D(x) ∧ f(x) ≤ 0 ); & 3. ∀x ( D(x) → f(x) > 0 ); \\ 4. ∃x ( P (x) → f(x) > 0 ); & 5. ∃x ( P (x) ∧ f(x) > 0 ); & 6. ∀x ( D(x) → f(x) ≤ 0 ). \end{matrix}

Esercizio 2.Siano

A = ℚ \ {1} = {x ∈ ℚ | x ≠ 1},
B = ℚ \ {−1} = {x ∈ ℚ | x ≠ −1},
C = ℚ \ {1, −1, 0} = {x ∈ ℚ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0},
D = C ∩ ℤ = {x ∈ ℤ | x ≠ 1 ∧ x ≠ −1 ∧ x ≠ 0}.

Si consideri la formula f(x) = \frac{−x+1}{−x−1}.

1. Stabilire in quali dei seguenti casi la formula f(x) definisce una funzione con il dominio e codominio specificati:

a) f : A → A; b) f : B → B; c) f : C → C; d) f : D → D.

2. Dopo aver verificato che f: C → C è ben definita, determinare una espressione algebrica che definisce (f ∘ f)(x).

3. Determinare inoltre se la funzione f: C → C è iniettiva, surgettiva, biunivoca.

4. Stabilire se f : C → C è una funzione invertibile e in tal caso trovare una espressione algebrica che definisce la funzione inversa f^{−1} : C → C.

Esercizio 3. Indichiamo con X_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare quanti elementi di X_{120} sono multipli sia di 5 che di 7;

2. Determinare quanti elementi di X_{120} non sono nè multipli di 5 nè multipli di 7;

3. Determinare quanti sottoinsiemi di X_{120} contengono almeno un multiplo di 5;

4. Determinare quanti sottoinsiemi di X_{120} non contengono multipli di 5 ma contengono almeno un multiplo di 7.

Esercizio 4. Sia u_{1} = 1; u_{2} = 0; u_{3} = 1; u_{n+3} = 3u_{n+2} − 3u_{n+1} + u_{n}. Dimostrare per induzione che u_{n} = (n − 2)^{2} per ogni n ≥ 1 in ℕ.

Esercizio 5. Determinare tutte le soluzioni intere x della congruenza: