Matematica Discreta
Recupero Compitino Modulo I 4 Giugno 2013
Nome e Cognome:
Numero Matricola:
Giustificare ogni risposta.
Esercizio 1
Sia X un insieme. Per ogni A ⊆ X, si definisca A = {x : x ∈ X and x /∈ A}. Si dimostri che per tutti i sottoinsiemi A, B di X vale la seguente relazione:
A ∪ (A ∩ B) = A ∪ B.
Soluzione: (1) Prima proviamo che A ∪ (A ∩ B) ⊆ A ∪ B. Sia x ∈ A ∪ (A ∩ B). Allora abbiamo due casi: x ∈ A oppure x ∈ A ∩ B.
Primo caso: Se x ∈ A allora x appartiene ad ogni sovrainsieme di A, in particolare A ∪ B.
Secondo caso: Se x ∈ A ∩ B allora x ∈ A e x ∈ B; quindi x appartiene ad ogni sovrainsieme di B, in particolare A ∪ B.
(2) Proviamo che A ∪ B ⊆ A ∪ (A ∩ B). Sia x ∈ A ∪ B. Allora abbiamo due casi.
Primo caso: Se x ∈ A allora x appartiene ad ogni sovrainsieme di A, in particolare A ∪ (A ∩ B).
Secondo caso: x ∈ B. Da A ∪ A = X, si ha che x appartiene ad A oppure x ∈ A. Si hanno due sottocasi:
• x ∈ A: allora x appartiene ad ogni sovrainsieme di A, in particolare x ∈ A ∪ (A ∩ B).
• x ∈ A: allora dall’ipotesi principale che x ∈ B segue che x ∈ A ∩ B. Quindi x appartiene ad ogni sovrainsieme di A ∩ B, in particolare x ∈ A ∪ (A ∩ B).
Esercizio 2
Sia A = {a, b, c} un alfabeto di caratteri e sia A∗ l’insieme delle stringhe di alfabeto A. Si consideri la seguente relazione binaria R su A∗:
αRβ se, e solamente se, β e’ una sottostringa di α.
ESEMPIO: la stringa “cane” e’ una sottostringa della stringa “doppiocanestro”. Si verifichi se la relazione R e’
riflessiva, simmetrica, transitiva, antisimmetrica.
Soluzione:
• Riflessivit`a: Si, perch´e ogni stringa `e una sottostringa di se stessa.
• Simmetria: No. Controesempio: “cane” e’ una sottostringa della stringa “doppiocanestro”, ma “doppiocanestro”
non e’ una sottostringa della stringa “cane”.
• Transitivit`a: Si. Sia αRβ e βRγ. Da αRβ esistono due stringhe α1 e α2 tali che α = α1βα2. (Per esempio, nel caso di “cane” e “doppiocanestro” abbiamo che α1= doppio e α2= stro). Allo stesso modo, da βRγ esistono due stringhe β1 e β2 tali che β = β1γβ2. Mettendo insieme le due uguaglianze α = α1βα2 e β = β1γβ2, otteniamo α = α1β1γβ2α2. Ne segue che γ e’ una sottostringa di α.
• Antisimmetria: Sia αRβ e βRα. Allora esistono quattro stringhe α1, α2, β1e β2tali che α = α1βα2e β = β1αβ2. Mettendo insieme le due uguaglianze si ottiene α = α1β1αβ2α2. Ne segue che le stringhe α1, α2, β1 e β2 sono la stringa vuota. Allora α = β.
Esercizio 3
Sia A = {a, b, c} un alfabeto di caratteri. Quante sono le stringhe di alfabeto A di lunghezza 10? Quante sono le stringhe di alfabeto A di lunghezza 10 che non hanno ripetizione di caratteri?
Soluzione: Abbiamo 3 possibilit`a per ciascuna delle 10 posizioni nella stringa. In totale quindi 310.
Non abbiamo stringhe di lunghezza dieci senza ripetizioni di caratteri costruite con un alfabeto di tre soli caratteri.
Esercizio 4
Si determini qual e’ il resto della divisione di (64)342per 13.
Soluzione: Dividiamo 64 per 13. Otteniamo 64 = (13 × 4) + 12. Ma 12 `e uguale a −1 modulo 13. Allora abbiamo:
(64)342= (−1)342= ((−1)2)171≡ 1171= 1 modulo 13.
Esercizio 5
Si provi per induzione che
2n= X
0≤k≤n
n k
.
Soluzione: Base dell’induzione n = 0: 1 = 20 =P
0≤k≤0
0 k
=
0 0
= 1. Supponiamo per ipotesi d’induzione che l’uguaglianza sia vera per n e dimostriamola per n + 1. Applichiamo la formula di Stiefel:
P
0≤k≤n+1
n + 1 k
= (P
1≤k≤n
n + 1 k
) +
n + 1 n + 1
+
n + 1 0
= (P
1≤k≤n
n + 1 k
) + 2
= P
1≤k≤n(
n k
+
n k − 1
) + 2 formula di Stiefel
= (P
1≤k≤n
n k
) + (P
1≤k≤n
n k − 1
) + 2
= (1 +P
1≤k≤n
n k
) + (1 +P
1≤k≤n
n k − 1
)
= (
n 0
+P
1≤k≤n
n k
) + (
n n
+P
0≤r≤n−1
n r
) ponendo r = k − 1
= (P
0≤k≤n
n k
) + (P
0≤r≤n
n r
)
= 2n+ 2n Ipotesi d’induzione
= 2n+1.
