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
Vuoi dimostrare ¬q → ¬r per contrapposizione. Quale implicazione dimostri al suo posto? Clicca su di essa.
¬q → ¬r
1¬q ∧ ¬¬r
2¬r → ¬q
3¬¬r → ¬¬q
4¬¬q → ¬¬r
2.Logica proposizionale e dimostrazioniDifficile
L’argomento con premesse r → q; q e conclusione r non è valido. Clicca la riga della tabella di verità che è un controesempio.
r → qq∴ r
1q = 1, r = 1
2q = 1, r = 0
3q = 0, r = 1
4q = 0, r = 0
3.Insiemi, relazioni e funzioniMedia
Su 74 studenti del primo anno, 33 hanno superato Matematica (M), 38 hanno superato Fisica (P) e 31 hanno superato Chimica (C). 17 hanno superato M e P, 15 hanno superato M e C, 10 hanno superato P e C, e 3 le hanno superate tutte e tre. Quanti stanno in esattamente due dei tre insiemi? Chiama il numero n.
|U| = 74
n =
4.Insiemi, relazioni e funzioniDifficile
Su X = {1, 2, …, 8} la relazione x ~ y vale quando x ≡ y (mod 3). Quanti elementi ci sono nella classe di equivalenza [1]?
X = {1, …, 8}x ~ y ⟺ 3 | (x − y)
|[1]| =
5.Teoria dei grafiMedia
Il grafo connesso ha un circuito euleriano, un cammino euleriano che non è un circuito, oppure nessuno dei due? Clicca la tua risposta.
|V| = 7|E| = 9
1Circuito euleriano
2Cammino euleriano, nessun circuito
3nessuna delle due
6.Teoria dei grafiDifficile
Usa l’algoritmo di Dijkstra per trovare la lunghezza d(F) del cammino minimo da A a F nel grafo pesato.
partenza: Aarrivo: F
d(F) =
7.Teoria dei numeri e aritmetica modulareMedia
Risolvi 53x ≡ 65 (mod 90). Dai la soluzione x con 0 < x < 90.
53x ≡ 65 (mod 90)
x =
8.Teoria dei numeri e aritmetica modulareDifficile
Risolvi 72x ≡ 18 (mod 87). Dai la più piccola soluzione positiva x.
72x ≡ 18 (mod 87)
x =
3Soluzioni
1.Logica proposizionale e dimostrazioni
Risposta: ¬¬r → ¬¬q
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).
Parti dell’implicazione
a = ¬q, b = ¬r
Contronominale
¬b → ¬a = ¬¬r → ¬¬q
Risposta
¬¬r → ¬¬q
La contronominale è equivalente all’enunciato originale, quindi dimostrarla dimostra l’enunciato.
2.Logica proposizionale e dimostrazioni
Risposta: q = 1, r = 0
Quantificatori e argomenti: ¬∀x P(x) ≡ ∃x ¬P(x) e ¬∃x P(x) ≡ ∀x ¬P(x). Sposta una negazione verso l’interno, scambia ogni quantificatore che attraversa e nega la formula interna con le leggi proposizionali, come ¬(a → b) ≡ a ∧ ¬b. Un argomento è valido quando la conclusione vale 1 in ogni riga in cui tutte le premesse valgono 1. Una sola riga con premesse vere e conclusione falsa è un controesempio e mostra che l’argomento non è valido.
Premesse e conclusione riga per riga
q = 1, r = 1: 1 1 | 1
q = 1, r = 0: 1 1 | 0
q = 0, r = 1: 0 0 | 1
q = 0, r = 0: 1 0 | 0
Controesempio
q = 1, r = 0
Risposta
q = 1, r = 0
Un argomento di questa forma sembra una regola valida, ma una sola riga basta a mostrare che non lo è.
3.Insiemi, relazioni e funzioni
Risposta: n = 33
Insiemi e diagrammi di Venn: A ∪ B contiene gli elementi in A o in B (o in entrambi), A ∩ B gli elementi in entrambi, A − B gli elementi di A che non sono in B, e il complementare A′ tutto ciò che è in U e non in A. In un diagramma di Venn ogni espressione insiemistica è un’unione di regioni, quindi contala regione per regione. Inclusione-esclusione: |A ∪ B| = |A| + |B| − |A ∩ B|, e |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Centro e coppie
M ∩ P ∩ C: 3
M ∩ P solo: 17 − 3 = 14
M ∩ C solo: 15 − 3 = 12
P ∩ C solo: 10 − 3 = 7
Insiemi singoli
M solo: 33 − 14 − 12 − 3 = 4
P solo: 38 − 14 − 7 − 3 = 14
C solo: 31 − 12 − 7 − 3 = 9
Risposta
14 + 12 + 7 = 33
Risposta
n = 33
4.Insiemi, relazioni e funzioni
Risposta: |[1]| = 3
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.
La classe
[1] = {1, 4, 7}
|[1]| = 3
Risposta
|[1]| = 3
5.Teoria dei grafi
Risposta: nessuna delle due
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.
Cammini minimi e alberi di copertura: l’algoritmo di Dijkstra fissa un vertice per passo: il vertice non fissato con la distanza provvisoria minima. La sua distanza è allora definitiva, e ogni vertice adiacente v riceve d(v) = min(d(v), d(u) + w(u, v)). L’algoritmo di Kruskal costruisce un albero di copertura minimo prendendo i lati dal più leggero al più pesante e saltando ogni lato che chiuderebbe un ciclo; l’algoritmo di Prim fa crescere un solo albero da un vertice iniziale aggiungendo sempre il lato più leggero che ne esce. Un albero di copertura di n vertici ha n − 1 lati.
Dijkstra passo per passo
Ogni riga: il vertice fissato, la sua distanza definitiva e i vertici adiacenti la cui distanza migliora.
A (0): B: 3
B (3): C: 9, D: 8
D (8): E: 15, G: 16
C (9)
E (15): F: 17
G (16)
F (17)
Cammino minimo
A → B → D → E → F
d(F) = 17
Risposta
d(F) = 17
7.Teoria dei numeri e aritmetica modulare
Risposta: x = 25
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 53
r = 90, t = 0
r = 53, q = 1, t = 1
r = 37, q = 1, t = −1
r = 16, q = 2, t = 2
r = 5, q = 3, t = −5
r = 1, q = 5, t = 17
53−1 ≡ 17 (mod 90)
Risolvi
x ≡ 17·65 = 1105 ≡ 25 (mod 90)
verifica: 53·25 = 1325 ≡ 65 (mod 90)
Risposta
x = 25
8.Teoria dei numeri e aritmetica modulare
Risposta: x = 22
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).