Matematica Discreta (6 crediti) BBBB
9 Gennaio 2017
Cognome e nome:
Matricola:
1. Dimostrare per induzione che, per ogni n ≥ 1, il numero n3+ 5n `e divisibile per 6.
Soluzione: Base dell’induzione n = 1:
13+ 5 × 1) = 1 + 5 = 6,
che `e divisibile per 6. Supponiamo per ipotesi di induzione che n3+ 5n sia divisibile per 6.
Verifichiamo che anche (n + 1)3 + 5(n + 1) `e divisibile per 6.
(n + 1)3+ 5(n + 1) = n3+ 3n2 + 3n + 1 + 5n + 5 = (n3+ 5n) + 3n2+ 3n + 6.
Sia n3+ 5n che 6 sono divisibili per 6. Proviamo che 3n2+ 3n `e divisibile per 6. Si ha:
3n2 + 3n = 3n(n + 1),
che `e divisibile per 3. Inoltre, n(n + 1) sono due numeri consecutivi, uno dei quali `e sicura- mente pari. In conclusione, 6 divide 3n2+ 3n e quindi (n + 1)3 + 5(n + 1) `e divisibile per 6. Il principio d’induzione ci permette di concludere che n3 + 5n `e divisibile per 6 per ogni n ≥ 1.
2. Formalizzare nel linguaggio matematico i seguenti enunciati, specificando l’universo del discorso, i simboli di relazione e le eventuali costanti
• “Tutti i calciatori amano un figlio di Giovanni”.
• “Tutti gli studenti in corso amano qualche libro”.
Soluzione: L’universo del discorso relativo al primo enunciato `e l’insieme di tutte le persone.
Utilizzeremo le seguenti relazioni:
(a) C(x) sse x `e un calciatore;
(b) xF y sse x `e figlio di y;
(c) xAy sse x ama y;
(d) G `e una costante che denota Giovanni.
1
∀x(C(x) → ∃y(yF G ∧ xAy)).
L’universo del discorso relativo al secondo enunciato `e l’unione dei seguenti due insiemi:
l’insieme di tutte le persone e l’insieme di tutti i libri. Utilizzeremo le seguenti relazioni:
(a) S(x) sse x `e uno studente;
(b) C(x) sse x `e in corso;
(c) xAy sse x ama y;
(d) L(x) sse x `e un libro.
∀x(S(x) ∧ C(x) → ∃y(L(y) ∧ xAy)).
3. Si trovi il resto della divisione di 576 per 17.
Soluzione: 17 `e un numero primo; quindi possiamo applicare il piccolo teorema di Fermat al numero 5 che `e relativamente primo con 17: 516≡171. Dividiamo 76 per 16: 76 = 16 × 4 + 12 e procediamo come segue:
576= 516×4+12 = 516×4512= (516)4512 ≡1714512= 512. Proseguiamo come segue:
512 = (52)6 ≡1786 = (82)3 = (−4)3 = (−4)2× (−4) = 16 × (−4) ≡17 −(−4) = 4.
4. Sia Z insieme dei numeri interi e sia E la relazione sull’insieme R dei numeri reali definita da
xEy ⇔ x2 − y2 ∈ Z.
Dimostrare che E `e una relazione di equivalenza. Determinare la classe di equivalenza del numero 1.
Soluzione: Dobbiamo provare che E verifica le propriet`a riflessiva, simmetrica e transitiva.
(a) (Propriet`a Riflessiva) Dalla definizione di E abbiamo: xEx sse x2−x2 ∈ Z. Da x2−x2 = 0 si ricava che xEx per ogni numero reale x.
(b) (Propriet`a Simmetrica) Dall’ipotesi xEy si ricava x2 − y2 ∈ Z. Ricordiamo che ogni numero intero z ammette un opposto −z che `e sempre un intero. Quindi, da x2− y2 ∈ Z si ricava che −(x2 − y2) ∈ Z, cio´e y2− x2 ∈ Z. In conclusione, yEx.
(c) (Propriet`a Transitiva) Per ipotesi si ha xEy e yEz, che implicano x2−y2 ∈ Z e y2−z2 ∈ Z. Allora (x2− y2) + (y2− z2) ∈ Z, perch´e la somma di due interi `e un numero intero.
Infine, (x2− y2) + (y2− z2) = x2+ (y2− y2) − z2 = x2− z2 ∈ Z, che implica xEz.
Per definizione, la classe di equivalenza di 1 `e l’insieme [1]E = {z ∈ R : z2 − 1 ∈ Z}. Dal fatto che z2− 1 ∈ Z sse z2 ∈ Z si ricava che [1]E = Z.
5. Sia A un insieme di cardinalit`a n. Dimostrare che i sottoinsiemi di A di cardinalit`a k sono
n k.
