Primo Compitino Matematica Discreta AAAAAA 6 Dicembre 2011

Primo Compitino Matematica Discreta AAAAAA 6 Dicembre 2011

Cognome e Nome:

Numero di Matricola:

1. Dimostrare per induzione che

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

Soluzione: Base induzione n = 2: 2³ = 8 ≥ 2²+ 4 = 8. OK

Supponiamo, per ipotesi d’induzione, che n³ ≥ n² + 4 e dimostriamo che (n + 1)³ ≥ (n + 1)²+ 4. Abbiamo che (n + 1)²+ 4 = n²+ 2n + 5 e (n + 1)³ = n³+ 3n²+ 3n + 1.

Quindi dobbiamo provare che:

n³+ 3n²+ 3n + 1 ≥ n²+ 2n + 5 = n²+ 4 + (2n + 1) Dal momento che n³ ≥ n²+ 4 (Ip. Ind.), e’ sufficiente provare che

3n²+ 3n + 1 ≥ 2n + 1 ossia

3n²+ n ≥ 0 che e’ vera.

2. Dimostrare la seguente uguaglianza insiemistica: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Soluzione: Prima dimostriamo che A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C).

Sia x ∈ A ∪ (B ∩ C). Allora x ∈ A oppure x ∈ B ∩ C. Distinguiamo i due casi:

(a) x ∈ A: allora x appartiene ad ogni sovrainsieme di A, in particolare x ∈ A ∪ B e x ∈ A ∪ B. Quindi x ∈ (A ∪ B) ∩ (A ∪ C).

(b) x ∈ B ∩ C: allora x ∈ B e x ∈ C. Da x ∈ B segue che x ∈ A ∪ B e da x ∈ C segue che A ∪ C. In conclusione, x ∈ (A ∪ B) ∩ (A ∪ C).

Questo conclude la prova della disuguaglianza A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C).

Ora proviamo che (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C). Sia x ∈ (A ∪ B) ∩ (A ∪ C). Allora x ∈ A ∪ B e x ∈ A ∪ C. Distinguiamo due casi esaustivi.

(a) x ∈ A: allora x ∈ A ∪ B e x ∈ (A ∪ C), da cui x ∈ (A ∪ B) ∩ (A ∪ C).

1

(b) x /∈ A: da x ∈ A ∪ B segue quindi che x ∈ B e da x ∈ A ∪ C segue che x ∈ C.

Cosi’ x ∈ B ∩ C. Quindi x appartiene ad ogni sovrainsieme di B ∩ C, in particolare x ∈ A ∪ (B ∩ C).

3. Determinare, giustificando la risposta, se l’enunciato

∀a∀b[a + b dispari ⇒ a pari oppure b non primo]

e’ vero o falso.

Soluzione: L’enunciato e’ falso. Controesempio: Si scelga a = 5 e b = 2. Allora 5 + 2 e’

dispari con a dispari e b primo.

4. Formalizzare l’enunciato ”Giovanni ama ogni animale non feroce”.

Soluzione: ∀x[An(x) ∧ ¬F er(x) → Ama(G, x)].

5. Determinare quali propriet`a verifica la seguente binaria relazione R tra numeri interi:

xRy sse x + y = 0.

Soluzione: Riflessiva: NO. Controesempio 1 + 1 6= 0)

Simmetrica: SI. Se x+y = 0 allora y +x = 0 per la proprieta’ commutativa della somma.

Transitiva: NO. Controesempio 1 + (−1) = 0 e (−1) + 1 = 0 ma 1 + 1 6= 0.

Antisimmetrica: NO. Controesempio: 1 + (−1) = 0 e (−1) + 1 = 0 ma 1 6= −1.

2