Algebra e Logica (Pareschi-Schoof)

Soluzioni degli esercizi dell’esame del 9-9-2202.

1. INDUZIONE Dimostriamo, per esempio. che ∑_{k=1}^{n} k^{3} = (n(n + 1)/2)^{2} per ogni intero positivo n. Dato un intero positivo n denotiamo con P (n) l’uguaglianza ∑_{k=1}^{n} k^{3} = (n(n + 1)/2)^{2}.

- P(1) è vera. Infatti il primo membro di P (1) è uguale a 1 e il secondo membro di P (1) è (1 · 2/2)^{2} = 1 - Dimostriamo che P (n) → P (n + 1) è vera. Infatti ∑_{k=1}^{n+1} k^{3} = ∑_{k=1}^{n} k^{3} + (n + 1)^{3}. Supponendo P (n) vera, abbiamo che il secondo membro dell’ultima uguaglianza è uguale a (n(n + 1)/2)^{2} + (n + 1)^{3}. Raccogliendo (n + 1)^{2} ciò è uguale a (n + 1)^{2}((n^{2} + 4n + 4)/4) = ((n + 1)(n + 2)/2)^{2}.

2. NUMERI INTERI. Risolviamo, ad esempio, il seguente esercizio: determinare il resto delle divisioni per 5, per 11 e per 55 del numero 2238^{2142}.

- Resto per 5. 2238 ≡ 3 (mod 5) e 2142 ≡ 2 (mod 4). Quindi 2238^{2142} ≡ 3^{2142} (mod 5) e, per il Teorema di Fermat, 3^{2142} ≡ 3^{2} = 9 ≡ 4 (mod 5). Quindi il resto è 4.

- Resto per 11. 2238 ≡ −2 + 2 − 3 + 8 = 5 (mod 11). 2242 ≡ 2 (mod 10). Ragionando come prima 2238^{2142} ≡ 5^{2} = 25 ≡ 3 (mod 11). Quindi il resto è 3.

- Resto per 55. Usando il Teorema cinese dei resti,ci si riduce a risolvere il sistema di congruenze

\{ \begin{matrix}x ≡ 4 (mod5) \\ x ≡ 3 (mod11) \end{matrix}

la cui soluzione, come si vede facilmente, è 14 (mod 55). Quindi il resto è 14.

3. COMBINATORIA. Determiniamo, ad esempio, il numero di terne di interi non negativi (x_{1}, x_{2}, x_{3}) tali che x_{1} + x_{2} + x_{3} ≤ 13 e x_{1} ≤ 5. Il numero delle terne tali che x_{1} + x_{2} + x_{3} ≤ 13 è uguale al numero delle quaterne (x_{1}, x_{2}, x_{3}, x_{4}) tale che x_{1} + x_{2} + x_{3} + x_{4} = 13, cioè C(16, 3). Allo stesso modo, il numero delle terne tali che x_{1} + x_{2} + x_{3} ≤ 13 e x_{1} ≥ 6 è C(7 + 3, 3) = C(10, 3). Quindi il numero cercato è C(16, 3) − C(10, 3) = 440.

4. RELAZIONI. Consideriamo, ad esempio, la relazione R su A = {1, 2, 3, 4, 5} consistente nelle coppie ordinate (a, b) tali che |a − b| = 1. Si vede subito che

R = {(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)}

Sia usando i prodotti booleni delle matrici associate, sia considerando le coppie unite da cammini nel grafo associato, si perviene al risultato che la chiusura transitiva di R consiste in tutto A × A. E’ chiaro che tale relazione non è una relazione d’ordine, perche’ non è antisimmetrica .(In altre versioni si perviene invece a relazioni non riflessive).

5. GRAFI. In questo caso omettiamo le soluzioni a causa di difficoltà grafiche. In ogni caso si ricordi che per dimostrare che due grafi NON SONO isomorfi bisogna trovare una proprietà invariante per isomorfismo posseduta dall’uno ma non dall’altro. Invece per dimostrare che SONO isomorfi, bisogna, di norma, esibire un esplicito isomorfismo di grafi.

6. LOGICA. Esprimiamo, ad esempio, xȳ mediante NAND. Poichè xNANDy = x̄y e yNANDy = ȳ si ha che xȳ = (xNAND(yNANDy))NAND(xNAND(yNANDy)).

Analogamente con NOR. Poichè xNORy = x̄ȳ e xNORx = x̄ si ha che xȳ = ¯ x̄ȳ = (xNORx)NORy. (Naturalmente, in entrambi i casi, si possono trovare anche altre espressioni altrettanto valide).