Disegna un diagramma di Venn e decidi regione per regione che cosa appartiene all’espressione insiemistica.
Nei problemi di conteggio, riempi le regioni dal centro verso l’esterno: prima tutti gli insiemi, poi le coppie, poi i singoli insiemi, infine l’esterno.
Usa il principio di inclusione-esclusione come verifica: |A ∪ B| = |A| + |B| − |A ∩ B|.
Per una relazione, verifica ogni proprietà su ogni coppia e fornisci un controesempio quando non vale.
Per una funzione, conta le frecce che arrivano a ciascun elemento di B: al più una significa iniettiva, almeno una suriettiva.
Teoria dei grafi
Lemma delle strette di mano
Σ deg(v) = 2|E|
Grafi completi
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regolare
|E| = n·k/2
Albero e foresta
|E| = n − 1, |E| = n − c
Foglie di un albero
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Eulero
circuito: tutti i gradi pari; cammino: esattamente 2 gradi dispari
Cicli hamiltoniani in Kn
(n − 1)!/2
Aggiornamento di Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Cammini di lunghezza L
(Mᴸ)ij
Metodo
Scrivi il grado di ogni vertice; la somma dei gradi è il doppio del numero di lati.
Nelle domande su Eulero, verifica che il grafo sia connesso e conta i vertici di grado dispari.
Per gli alberi, usa n − 1 lati e il lemma delle strette di mano.
Per Dijkstra, tieni una tabella delle distanze provvisorie e a ogni passo fissa il vertice non ancora fissato con la distanza minima.
Per un albero di copertura minimo, ordina i lati per peso e salta ogni lato che chiude un ciclo (Kruskal), oppure fai crescere un solo albero a partire da un vertice iniziale (Prim).
Teoria dei numeri e aritmetica modulare
Divisione con resto
a = q·n + r, 0 ≤ r < n
Euclide
gcd(a, b) = gcd(b, a mod b)
Minimo comune multiplo
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruenza lineare
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Funzione φ di Eulero
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Metodo
Riduci prima ogni numero modulo n; i resti sono compresi tra 0 e n − 1.
Per un MCD, dividi ripetutamente con l’algoritmo di Euclide; l’ultimo resto diverso da zero è il MCD.
Per un inverso, esegui l’algoritmo esteso e tieni il coefficiente di a; aggiungi n se è negativo.
Risolvi a·x ≡ b moltiplicando per a⁻¹; combina due congruenze scrivendo x = r₁ + m₁k.
Per le potenze, scrivi l’esponente in binario ed eleva al quadrato ripetutamente; in RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
2Esercizi
1.Logica proposizionale e dimostrazioniMedia
Quale formula è logicamente equivalente a ¬(p ∧ r)? Clicca su di essa.
¬(p ∧ r)
1¬p ∧ ¬r
2¬p ∧ r
3¬p ∨ r
4¬p ∨ ¬r
2.Logica proposizionale e dimostrazioniDifficile
Quante delle 16 righe della tabella di verità rendono vera ((¬b → ¬a) ↔ ¬(c ∨ a)) ∧ ¬((¬d → c) ∧ b)? Chiama questo numero N.
((¬b → ¬a) ↔ ¬(c ∨ a)) ∧ ¬((¬d → c) ∧ b)
N =
3.Insiemi, relazioni e funzioniMedia
R = {(1, 1), (1, 2), (1, 4), (2, 2), (2, 3), (2, 4), (3, 1), (3, 3)} è una relazione su {1, 2, 3, 4}. Qual è il numero minimo k di coppie ordinate da aggiungere a R per renderla transitiva (la dimensione della chiusura transitiva meno |R|)?
Il diagramma a frecce mostra una funzione f: A → B con A = {1, 2, 3} e B = {a, b, c}. Clicca la descrizione che si adatta a f.
f = {(1, a), (2, b), (3, a)}
1iniettiva, non suriettiva
2suriettiva, non iniettiva
3biiettiva
4nessuna delle due
5.Teoria dei grafiMedia
Quanti cicli hamiltoniani diversi H ha il grafo completo K5? I cicli che differiscono solo per il vertice iniziale o per il verso contano come lo stesso.
K5
H =
6.Teoria dei grafiDifficile
Quanti cammini chiusi di lunghezza 3 partono e terminano in B? Un cammino può ripetere vertici e lati. Chiama il numero N.
M = matrice di adiacenzaL = 3
N =
7.Teoria dei numeri e aritmetica modulareMedia
Risolvi 34x ≡ 21 (mod 43). Dai la soluzione x con 0 < x < 43.
34x ≡ 21 (mod 43)
x =
8.Teoria dei numeri e aritmetica modulareDifficile
Risolvi 15x ≡ 33 (mod 39). Dai la più piccola soluzione positiva x.
15x ≡ 33 (mod 39)
x =
3Soluzioni
1.Logica proposizionale e dimostrazioni
Risposta: ¬p ∨ ¬r
Equivalenza logica: due formule sono equivalenti (≡) quando hanno lo stesso valore in ogni riga della tabella di verità. Una tautologia vale 1 in ogni riga, una contraddizione vale 0 in ogni riga, e una contingenza non è né l’una né l’altra. Leggi utili: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b e ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contronominale); ¬(a → b) ≡ a ∧ ¬b; e le leggi distributive, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
La legge
De Morgan: ¬(a ∧ b) ≡ ¬a ∨ ¬b. L’∧ diventa ∨ e le due parti vengono negate.
¬(p ∧ r) ≡ ¬p ∨ ¬r
Verifica con la tabella di verità
p = 1, r = 1: 0 | 0 0 1 0
p = 1, r = 0: 1 | 0 0 0 1
p = 0, r = 1: 1 | 0 1 1 1
p = 0, r = 0: 1 | 1 0 1 1
Risposta
¬p ∨ ¬r
Le colonne dopo la barra sono le opzioni nell’ordine mostrato.
2.Logica proposizionale e dimostrazioni
Risposta: N = 7
Tabelle di verità: una formula con n variabili distinte ha 2ⁿ righe, una per ogni combinazione di valori di verità (1 = vero, 0 = falso). Procedi dall’interno verso l’esterno e dai a ogni sottoformula una colonna propria. ¬a inverte il valore; a ∧ b vale 1 solo quando entrambi valgono 1; a ∨ b vale 0 solo quando entrambi valgono 0; a → b vale 0 solo quando a = 1 e b = 0; a ↔ b vale 1 quando i due lati sono uguali.
Colonne
¬b; ¬a; ¬b → ¬a; c ∨ a; ¬(c ∨ a); (¬b → ¬a) ↔ ¬(c ∨ a); ¬d; ¬d → c; (¬d → c) ∧ b; ¬((¬d → c) ∧ b); ((¬b → ¬a) ↔ ¬(c ∨ a)) ∧ ¬((¬d → c) ∧ b)
Dividi secondo a
a = 1: 4
a = 0: 3
N = 4 + 3 = 7
Risposta
N = 7
3.Insiemi, relazioni e funzioni
Risposta: k = 4
Relazioni: una relazione R su un insieme X è un insieme di coppie ordinate (x, y). R è riflessiva quando (x, x) ∈ R per ogni x in X; simmetrica quando (x, y) ∈ R comporta sempre (y, x) ∈ R; antisimmetrica quando (x, y) e (y, x) sono entrambe in R solo se x = y; e transitiva quando (x, y) e (y, z) in R implicano (x, z) ∈ R. Una relazione di equivalenza è riflessiva, simmetrica e transitiva, e divide X in classi disgiunte.
Coppie da aggiungere
{(1, 3), (2, 1), (3, 2), (3, 4)}
Conta
k = 4
Risposta
k = 4
4.Insiemi, relazioni e funzioni
Risposta: nessuna delle due
Funzioni e conteggio: una funzione f: A → B assegna a ogni elemento di A esattamente un’immagine in B. f è iniettiva (uno a uno) quando elementi diversi hanno immagini diverse, suriettiva (su) quando ogni elemento di B è un’immagine, e biiettiva quando valgono entrambe. Con |A| = m e |B| = n ci sono nᵐ funzioni, n!/(n − m)! iniettive (m ≤ n), e per inclusione-esclusione Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ suriettive. |𝒫(A)| = 2ᵐ e |A × B| = m·n.
Iniettiva?
f(1) = f(3) = a → non iniettiva
Suriettiva?
c non riceve alcuna freccia → non suriettiva
Risposta
nessuna delle due
Risposta
nessuna delle due
5.Teoria dei grafi
Risposta: H = 12
Eulero, Hamilton e alberi: un grafo connesso ha un circuito euleriano (ogni lato una volta, di nuovo al punto di partenza) quando ogni vertice ha grado pari, e un cammino euleriano che non è un circuito quando esattamente due vertici hanno grado dispari; il cammino va allora da un vertice dispari all’altro. Un ciclo hamiltoniano visita ogni vertice una volta; Kn ne ha (n − 1)!/2. Un albero con n vertici ha n − 1 lati, e un grafo connesso con m lati mantiene un albero di copertura dopo aver tolto m − n + 1 lati.
Conta
H = (5 − 1)!/2 = 24/2 = 12
Risposta
H = 12
6.Teoria dei grafi
Risposta: N = 2
Gradi: il grado di un vertice è il numero di lati che vi arrivano. Ogni lato ha due estremi, quindi i gradi sommano al doppio del numero di lati: Σ deg(v) = 2|E| (il lemma delle strette di mano). Il numero di vertici di grado dispari è quindi pari. Kn ha n(n − 1)/2 lati, un grafo k-regolare con n vertici ne ha nk/2, e un albero con n vertici ha n − 1 lati.
Matrice di adiacenza
A: 0 1 1 0 0
B: 1 0 0 1 1
C: 1 0 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
Un altro passo
(M³)BB = 0·1 + 3·0 + 2·0 + 1·1 + 1·1 = 2
Risposta
N = 2
7.Teoria dei numeri e aritmetica modulare
Risposta: x = 12
Inversi e congruenze: a ha un inverso modulo n esattamente quando MCD(a, n) = 1. L’algoritmo di Euclide esteso scrive 1 = s·n + t·a, e allora a⁻¹ ≡ t (mod n). Una congruenza a·x ≡ b (mod n) con MCD(a, n) = 1 ha la soluzione x ≡ a⁻¹·b. Due congruenze x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂) con moduli coprimi hanno una soluzione modulo m₁·m₂ (teorema cinese del resto). La φ di Eulero φ(n) conta i numeri da 1 a n coprimi con n: φ(n) = n·∏(1 − 1/p).
Inverso di 34
r = 43, t = 0
r = 34, q = 1, t = 1
r = 9, q = 3, t = −1
r = 7, q = 1, t = 4
r = 2, q = 3, t = −5
r = 1, q = 2, t = 19
34−1 ≡ 19 (mod 43)
Risolvi
x ≡ 19·21 = 399 ≡ 12 (mod 43)
verifica: 34·12 = 408 ≡ 21 (mod 43)
Risposta
x = 12
8.Teoria dei numeri e aritmetica modulare
Risposta: x = 10
Inversi e congruenze: a ha un inverso modulo n esattamente quando MCD(a, n) = 1. L’algoritmo di Euclide esteso scrive 1 = s·n + t·a, e allora a⁻¹ ≡ t (mod n). Una congruenza a·x ≡ b (mod n) con MCD(a, n) = 1 ha la soluzione x ≡ a⁻¹·b. Due congruenze x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂) con moduli coprimi hanno una soluzione modulo m₁·m₂ (teorema cinese del resto). La φ di Eulero φ(n) conta i numeri da 1 a n coprimi con n: φ(n) = n·∏(1 − 1/p).