Matematica Discreta (6 crediti) BBBBBB 30 Gennaio 2015
Cognome e Nome:
Numero di Matricola:
Giustificare ogni risposta scrivendo in modo chiaro e conciso.
1. Dimostrare per induzione che
n
X
i=1
(2i − 1) = n2 per ogni n ≥ 1.
Soluzione: Base dell’induzione (n = 1): 1 =P1
i=1(2i − 1) = 12.
Supponiamo per ipotesi d’induzione che l’uguaglianza sia vera per n. Dimostriamola per n + 1.
n+1
X
i=1
(2i−1) =
n
X
i=1
(2i−1)+(2(n+1)−1) =Ip.Ind n2+2(n+1)−1 = n2+2n+1 = (n+1)2.
2. Formalizzare nel linguaggio matematico i seguenti due enunciati:
(i) Il padre di Maria ama qualche studente.
(ii) Ogni professore legge qualche libro.
Soluzione: (i) Sia M una costante (Maria), Padre(x) una funzione unaria (essere padre di x), A(x, y) una relazione binaria (x ama y), S(x) una relazione unaria (x `e uno studente).
∃x(S(x) ∧ A(Padre(M ), x)) (ii)
∀x(Prof(x) → ∃y(Libro(y) ∧ legge(x, y)))
3. Sia X l’insieme delle biciclette di Mestre. Determinare quali propriet`a verifica la seguente relazione binaria R su X: xRy sse la ruota anteriore della bicicletta x `e della stessa marca della ruota posteriore della bicicletta y.
Soluzione: R non `e riflessiva in generale. Controesempio: La bicicletta di Pinco ha ruote di marca diversa.
1
R non `e simmetrica in generale. Se la ruota anteriore della bicicletta di Pinco `e della stessa marca della ruota posteriore della bicicletta di Marco, non `e detto che la ruota anteriore della bicicletta di Marco sia della stessa marca della ruota posteriore della bicicletta di Pinco.
R non `e transitiva in generale.
R non `e antisimmetrica in generale.
4. Si risolva la seguente congruenza: 3x ≡ 24 (mod 17).
5. Una targa automobilistica `e una sequenza di sei caratteri x1x2x3x4x5x6: i primi quattro caratteri x1, x2, x3, x4 appartengono all’alfabeto delle cifre {1, 2, 3}, mentre i rimanenti due caratteri x5, x6 appartengono all’alfabeto delle lettere maiuscole {C, D, E}. Quante sono le targhe automobilistiche x1x2x3x4x5x6 tali che il numero x1x2 `e congruo a 0 modulo 3, e x5 = C oppure x5 = E ?
Soluzione: In totale abbiamo 36 targhe.
x1x2 = 11|12|13|21|22|23|31|32|33, dove il simbolo | significa “oppure”. I multipli di 3 sono 12, 21 e 33. In totale 3. Quindi abbiamo 3 possibilit`a per x1x2, 3 possibilit`a per x3, 3 possibilit`a per x4, 2 possibilit`a per x5 e 3 possibilit`a per x6. In totale 34× 2.
2
