Matematica Discreta (6 crediti) AAAAA

Matematica Discreta (6 crediti) AAAAA

7 Gennaio 2016

Cognome e nome:

Matricola:

1. Dimostrare per induzione che

n² ≥ 2n + 5 per ogni n ≥ 4.

Soluzione: Base dell’induzione n = 4: 16 = 4² ≥ 2 × 4 + 5 = 13.

Supponiamo che la disuguaglianza n² ≥ 2n + 5 sia vera per n e dimostriamola per n + 1.

Dobbiamo cio´e dimostrare che (n + 1)² ≥ 2(n + 1) + 5.

(n+1)² = n²+2n+1 ≥_Ip.Ind. 2n+5+2n+1 = (2n+7)+(2n−1) = 2(n+1)+5+(2n−1) ≥ 2(n+1)+5.

perch´e 2n − 1 ≥ 0 se n ≥ 4.

Infatti, da n ≥ 4 si ha 2n ≥ 8, da cui 2n − 1 ≥ 7, che `e maggiore o uguale a 0.

2. Formalizzare nel linguaggio matematico i seguenti enunciati.

• “Ad ogni studente piace qualche materia”.

• “Esiste uno studente che ama tutte le materie”.

Soluzione: Siano: S(x) sse x `e uno studente; M (x) sse x `e una materia; xLy sse ad x piace y. Allora si ha:

∀x(S(x) → ∃y(M (y) ∧ xLy).

∃x(S(x) ∧ ∀y(M (y) → xLy)) 3. Si trovi il resto della divisione di 4⁷⁶ per 13.

Soluzione: essendo 13 primo, possiamo applicare il piccolo teorema di Fermat, che in questo caso particolare afferma 4¹² ≡ 1 mod 13. Abbiamo inoltre che 76 = 12 · 6 + 4, e quindi 4⁷⁶= (4¹²)⁶· 4⁴ ≡ 4⁴ = 16 × 16 ≡ 3 × 3 = 9 mod 13.

1

4. Sia X l’insieme delle funzioni aventi dominio l’insieme {a, b} e codominio l’insieme {0, 1, 2}.

Determinare quali propriet`a soddisfa la relazione binaria R su X cos`ı definita:

f Rg se e solo se f (b) = g(b)

Nel caso R sia una relazione di equivalenza, fornire esplicitamente un rappresentante per le classi di equivalenza.

Soluzione: P. riflessiva: f Rf per ogni f perch´e f (b) = f (b).

P. Simmetrica: f Rg → gRf : deriva dalla propriet`a simmetrica dell’uguaglianza. Supponen- do che f Rg, cio´e f (b) = g(b), si deriva g(b) = f (b), che implica gRf .

P. Transitiva: f Rg ∧ gRh → f Rh: deriva dalla propriet`a transitiva dell’uguaglianza. Sup- ponendo che f Rg e gRh, cio´e f (b) = g(b) e g(b) = h(b), allora si ha f (b) = h(b), che implica f Rh.

Una classe di equivalenza `e caratterizzata dal valore che la funzione assume sull’input b.

Abbiamo tre possibilit`a: 0, 1, 2. Quindi abbiamo tre classi di equivalenza.

Primo rappresentante: f (b) = 0 = f (a).

Secondo rappresentante: f (b) = 1 = f (a).

Terzo rappresentante: f (b) = 2 = f (a).