Corso di Laurea in Informatica Prova scritta del 16 Giugno 2004

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

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

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

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

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

Esercizio 1.

1. Scrivere formalmente, utilizzando esclusivamente i simboli logici e le operazioni aritmetiche, il seguente enunciato P: “Il massimo comun divisore di a e b divide c”.

2. Per ciascuno dei seguenti enunciati Q_{1}, Q_{2}, Q_{3}, determinare se l’implicazione Q_{i} → P è vera o falsa nell’universo dei numeri naturali (dando una dimostrazione o trovando un controesempio).

Q_{1} : “∃x ax = c ” ;  Q_{2} : “∃x abx = c^{2} ” ;  Q_{3} : “ac = b^{2} ” .

Esercizio 2. Sia A un insieme, B ⊆ A un suo sottoinsieme, e P(A) = {X | X ⊆ A} l’insieme delle parti di A. Si consideri la funzione F : P(A) → P(A) definita da F (X) = (A \ X) ∩ B. (Si ricordi che A \ X denota la differenza insiemistica A \ X = {a ∈ A | a ∉ X}). Dimostrare che:

1. F (X) = B \ X;

2. (F ∘ F ∘ F)(X) = F (X).

Esercizio 3. Sia A un insieme di 15 elementi. Determinare quante sono:

1. le coppie di sottoinsiemi (X, Y) di A tali che X abbia 4 elementi, Y ne abbia 3, e X ∩ Y = ∅;

2. le coppie di sottoinsiemi (X, Y) di A tali che X abbia 5 elementi, Y ne abbia 9, e X ⊆ Y.

Esercizio 4. Sia a un numero reale diverso da 0 e 1. Definiamo per ricorrenza la successione f, ponendo f_{0} = a e f_{n+1} = f_{n}^{2} − f_{n} + 1. Dimostrare che:

1. ∀n f_{n} ≠ 0;

2. ∀n f_{n} ≠ 1;

3. ∀n f_{n+1} > f_{n}.

Esercizio 5. Si consideri la congruenza 69x ≡ 57 (mod 75).

1. Determinarne le soluzioni;

2. Determinare il numero delle soluzioni x tali che 100 ≤ x ≤ 999.