Matematica Discreta (6 crediti) AAAAA

Matematica Discreta (6 crediti) AAAAA

23 Gennaio 2017

Cognome e nome:

Matricola:

1. Si applichi il teorema di Eulero per calcolare il resto della divisione di 4²⁴³ per 225.

Soluzione: La funzione φ `e moltiplicativa. Quindi,

φ(225) = φ(3²5²) = φ(3²)φ(5²) = 3²(1−(1/3))5²(1−(1/5)) = 9×(2/3)×25×(4/5) = 6×20 = 120.

In conclusione, si ha: 4²⁴³ = 4^2×120+3 = (4¹²⁰)² × 4³ ≡225 1²× 4³ = 64.

2. Spiegare le quattro figure combinatorie (disposizioni/combinazioni con o senza ripetizione) utilizzando n contenitori distinti (numerati da 1 ad n) e k palline.

Soluzione: Dobbiamo sistemare k palline in n contenitori distinguibili tra di loro.

(1) Le palline sono distinguibili tra loro (per esempio, sono numerate da 1 a k) e si pu`o mettere al pi`u una pallina in ogni contenitore. Questo modello corrisponde alle disposizioni semplici di un insieme di n elementi di ordine k ≤ n.

(2) Le palline sono distinguibili tra loro (per esempio, sono numerate da 1 a k) e si pu`o mettere pi`u di una pallina in ogni contenitore. Questo modello corrisponde alle disposizioni con ripetizione di un insieme di n elementi di ordine k. Non vi `e alcun vincolo tra n e k.

(3) Le palline sono indistinguibili tra loro e si pu`o mettere al pi`u una pallina in ogni conte- nitore. Questo modello corrisponde alle combinazioni semplici di un insieme di n elementi di ordine k ≤ n.

(4) Le palline sono indistinguibili tra loro e si pu`o mettere pi`u di una pallina in ogni con- tenitore. Questo modello corrisponde alle combinazioni con ripetizione di un insieme di n elementi di ordine k. Non vi `e alcun vincolo tra n e k.

3. Definiamo la seguente relazione binaria E sull’insieme N⁺ dei numeri naturali positivi:

xEy sse x divide y oppure x < y + 2.

Determinare se la relazione E definisce un ordinamento parziale su N⁺.

Soluzione: La relazione E definisce un ordinamento parziale su N⁺ se verifica la propriet`a riflessiva, transitiva e antisimmetrica.

1

P. Riflessiva: Dato un arbitrario numero naturale positivo x, si ha xEx perch´e x divide x.

P. Antisimmetrica: Non vale: 1 divide 2 e 2 < 1 + 2 = 3, ma 1 6= 2. Quindi 1E2 e 2E1 con 1 6= 2.

P. transitiva: Non vale. Ecco un controesempio: 4E3 e 3E2 ma 4E2 `e falso. Infatti, 4 < 3+2 e 3 < 2 + 2, ma n´e 4 divide 2 n´e 4 < 2 + 2.

In conclusione, E non `e un ordinamento parziale.

4. Provare per induzione che, per ogni n ≥ 1, vale la seguente uguaglianza

n

X

k=1

2^k= 2(2ⁿ− 1).

Soluzione: n = 1: P1

k=12^k = 2¹ = 2 e 2(2¹ − 1) = 2(2 − 1) = 2.

Supponiamo per ipotesi d’induzione che Pn

k=12^k = 2(2ⁿ− 1). Proviamo l’uguaglianza per n + 1.

n+1

X

k=1

2^k = (

n

X

k=1

2^k) + 2ⁿ⁺¹=_Ip.Ind.2(2ⁿ− 1) + 2ⁿ⁺¹ = 2(2ⁿ− 1 + 2ⁿ) = 2(2ⁿ⁺¹− 1).

Il principio d’induzione permette di concludere chePn

k=12^k = 2(2ⁿ− 1) per ogni n ≥ 1.

5. Formalizzare nel linguaggio matematico i seguenti enunciati, specificando l’universo del discorso, i simboli di relazione e le eventuali costanti:

• Nessuno studente ama ogni corso

• Marco ama tutti gli amici che non sono alti.

Soluzione: Per il primo enunciato consideriamo come universo l’insieme delle persone e dei corsi. Utilizzeremo due relazioni unarie S e C ed una relazione binaria A. Associamo alle relazioni il seguente significato:

S(x) sse x `e uno studente.

xAy sse x ama y.

C(x) sse x `e un corso.

Il primo enunciato si formalizza nel modo seguente (non `e l’unico!):

¬∃x(S(x) ∧ ∀y(C(y) → xAy)).

Per il secondo enunciato consideriamo come universo l’insieme delle persone. Utilizzeremo una costante m, una relazioni unaria T e due relazioni binarie A, F . Associamo alle relazioni il seguente significato:

m denota Marco.

xAy sse x ama y.

xF y sse x `e un amico di y.

T (x) sse x `e alto.

Il secondo enunciato si formalizza nel modo seguente (non `e l’unico!):

∀y((yF m ∧ ¬T (y)) → mAy).