ALGEBRA E LOGICA (Pareschi e Schoof) 2^{o} appello Roma 9 maggio 2002, 14:00–15:45.

COGNOME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOME . . . . . . . . . . . . . . . . . . . . . . . .

Inserire le risposte negli spazi predisposti, accompagnandole con spiegazioni chiare ed essenziali. NON SI ACCETTANO RISPOSTE SCRITTE SU ALTRI FOGLI. Ogni esercizio vale 5 punti.

1. Sia h > −1 un numero reale. Dimostrare per induzione che 1 + nh ≤ (1 + h)^{n} per ogni n ∈ N.

Per n = 1 l’affermazione è vera perché 1 + h ≥ 1 + h. Supponiamo che sia vera per n. Allora (1 + h)^{n+1} = (1 + h)(1 + h)^{n} ≥ (1 + h)(1 + nh) = 1 + (n + 1)h + nh^{2}, il quale è maggiore o uguale a 1 + (n + 1)h, perché nh^{2} ≥ 0. L’affermazione è quindi anche vera per n + 1.

2. Determinare il resto delle divisioni per 5, per 7 e per 11 di 2^{677}; determinare il resto della divisione per 385 di 2^{677}

Sia x = 2^{677}. Siccome 5 è primo e l’esponente 677 è congruo a 1 modulo 4 = 5 − 1, per il Teorema di Fermat abbiamo che x ≡ 2^{1} = 2 (mod 5). Similmente, 677 è congruo a 5 (mod 6) e a 7 (mod 10) e quindi x ≡ 2^{5} ≡ 4 (mod 7) e x ≡ 2^{7} ≡ 7 (mod 11). I resti richiesti sono quindi rispettivamente 2, 4 e 7.

Siccome 385 = 5 · 7 · 11, un’applicazione del Teorema Cinese del Rresto ci dà il resto della divisione per 385. Con un calcolo standard si trova che x ≡ 172 (mod 385). Il resto richiesto è quindi uguale a 172.

3. Siano x, y due variabili booleane. Definiamo x NOR y tramite 0 NOR 0 = 1, 0 NOR 1 = 0, 1 NOR 0 = 0, 1 NOR 1 = 0. Esprimere x + y, xy in termini del operatore NOR.

Osserviamo che x NOR x = \overline{x}. Siccome x + y = \overline{(x NOR y)} abbiamo che x + y = (x NOR y) NOR (x NOR y). Similmente, siccome xy = \overline{x} NOR \overline{y}, abbiamo che xy = (x NOR x) NOR (y NOR y).

4. Sia P = N × N. Per (a, b) ∈ P e (c, d) ∈ P definiamo (a, b) ≤ (c, d) quando ab ≤ cd. Stabilire se la relazione “≤” ‘e: (a) riflessiva, (b) transitiva, (c) simmetrica (d) anti-simmetrica.

Siccome ab ≤ ab per ogni a, b ∈ N, la relazione è riflessiva. Se ab ≤ cd e cd ≤ ef, allora ab ≤ ef. Questo implica che la relazione è transitiva. La relazione non è simmetrica perché (1, 1) ≤ (1, 2) mentre non vale (1, 2)≤(1, 1). La relazione non è nemmeno anti-simmetrica, perché (2, 2) ≤ (1, 4) e (1, 4) ≤ (2, 2), ma (1, 4) ≠ (2, 2).

5. Determinare quante sono le soluzioni (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) con x_{i} ≥ 0 dell’equazione x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 16 con x_{2} ≥ 2 e x_{3} ≤ 4.

Ponendo y_{2} = x_{2} − 2, il problema è di determinare il numero delle soluzione intere non negative dell’equazione x_{1} +y_{2} +x_{3} +x_{4} +x_{5} = 14, con x_{3} ≤ 4. Trascurando per adesso questa ultima condizione, ci sono \binom{14+5−1}{5−1} soluzioni. Le soluzioni da scartare sono quelle con x_{3} ≥ 5. Ponendo y_{5} = x_{3} − 5, le soluzioni da scartare sono le soluzioni intere non negative dell’equazione x_{1} + y_{2} + y_{3} + x_{4} + x_{5} = 9. Ci sono quindi \binom{9+5−1}{5−1} soluzioni da scartare. Il numero delle soluzioni che soddisfano la condizione x_{3} ≤ 4 è quindi uguale a \binom{18}{4} − \binom{13}{4} = 2345.

6. Sull’insieme N × N definiamo la relazione “∼” tramite (a, b) ∼ (c, d) quando a + d = b + c. (a) Dimostrare che si tratta di una relazione di equivalenza. Per ogni (a, b) ∈ N × N sia [(a, b] la sua classe di equivalenza.

(b) Dimostrare che la funzione [(a, b)] ↦ a − b è una biezione fra l’insieme delle classi di equivalenza e Z.

(a) Siccome a + b = a + b per ogni a, b ∈ N, la relazione è riflessiva. La relazione è simmetrica perché da (a, b) ∼ (c, d) segue b + c = a + d e quindi (c, d) ∼ (a, b). Se (a, b) ∼ (c, d) e (c, d) ∼ (e, f), allora a + d = b + c e c + f = d + e. Facendo la somma, troviamo che a + f = e + b e quindi (a, b) ∼ (e, f). La relazione è quindi transitiva.

(b) Se [(a, b)] e [(c, d)] hanno la stessa immagine, allora a − b = c − d e quindi a + d = b + c. In altre parole (a, b) ∼ (c, d) e quindi [(a, b)] = [(c, d)]. Questo dimostra che la funzione è iniettiva. La suriettività segue dal fatto che ogni n ∈ Z si può scrivere come differenza di due interi positivi a, b.