Appunti di Matematica discreta

Matematica discreta

Ilaria Chiesura

A.A. 2022-2023

Contents

• 1 Introduzione 5
• 1.1 Cos’è la matematica discreta? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
• 2 Principio di induzione 7
• 2.1 Principio di induzione (con gli insiemi) . . . . . . . . . . . . . . . . . . . . . . . . 7
• 2.2 Principio di induzione (con i predicati) . . . . . . . . . . . . . . . . . . . . . . . . . 7
• 2.3 Altre forme del principio di induzione . . . . . . . . . . . . . . . . . . . . . . . . . 7
• 2.3.1 Principio del buon ordinamento (P.B.O.) . . . . . . . . . . . . . . . . . . . . 7
• 2.3.2 Forma forte del principio di induzione (P.I.F.) . . . . . . . . . . . . . . . . . 8
• 3 Numeri naturali 9
• 3.1 Assiomi di N (o assiomi di Peano) . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
• 4 Cardinalità 11
• 4.1 Equivalenza al concetto di insieme finito . . . . . . . . . . . . . . . . . . . . . . . . 12
• 4.2 Classe dell’insieme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
• 5 Contare con insiemi finiti e infiniti 15
• 5.1 Contare con insiemi finiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
• 5.1.1 Permutazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
• 5.1.2 Disposizione senza ripetizione . . . . . . . . . . . . . . . . . . . . . . . . . 16
• 5.1.3 Combinazione senza ripetizione . . . . . . . . . . . . . . . . . . . . . . . . 16
• 5.1.4 Cenni di probabilità discreta . . . . . . . . . . . . . . . . . . . . . . . . . . 18
• 5.2 Principio di inclusione-esclusione . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
• 5.3 Principio dei cassetti (o principio della piccionaia) . . . . . . . . . . . . . . . . . . . 19
• 5.3.1 Funzioni “floor” e “ceiling” . . . . . . . . . . . . . . . . . . . . . . . . . . 19
• 5.4 Numero di Ramsay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
• 6 Successioni ricorsive 23
• 6.1 Caso del primo ordine lineare omogeneo . . . . . . . . . . . . . . . . . . . . . . . . 24
• 6.2 Caso del primo ordine lineare non omogeneo . . . . . . . . . . . . . . . . . . . . . 24
• 6.2.1 Caso costante f(n) = β . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
• 6.3 Caso del secondo ordine lineare omogeneo . . . . . . . . . . . . . . . . . . . . . . 25
• 6.4 Caso del secondo ordine lineare non omogeneo . . . . . . . . . . . . . . . . . . . 25
• 6.4.1 Caso ∆ ≠ 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
• 6.4.2 Caso ∆ = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
• 6.5 Ordini maggiori del secondo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
• 6.5.1 Cenno ai sistemi di equazioni ricorsive . . . . . . . . . . . . . . . . . . . . 28
• 6.6 Equazioni ricorsive non lineari del primo ordine . . . . . . . . . . . . . . . . . . . . 29
• 6.7 Condizioni per l’esistenza dei punti fissi . . . . . . . . . . . . . . . . . . . . . . . . 31
• 6.8 Funzioni lipschitziane (o di Lipschitz) . . . . . . . . . . . . . . . . . . . . . . . . . 31
• 34 Contents
• 7 Grafi 35
• 7.1 Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
• 7.1.1 Albero generatore (”spanning tree”) . . . . . . . . . . . . . . . . . . . . . . 39
• 7.2 Grafi completi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
• 7.3 Grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
• 7.4 Grafi completi-bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
• 7.5 Grafi planari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
• 7.5.1 Planarità di k_n (grafo completo) . . . . . . . . . . . . . . . . . . . . . . . . 42
• 7.5.2 Percorsi/cicli euleriani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
• 7.5.3 Percorsi/cicli hamiltoniani . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
• 7.5.4 Ipercubo (H_n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
• 7.5.5 Grafo ciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
• 7.5.6 Grafo cammino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
• 7.6 Matrice di adiacenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
• 7.7 Matrice di permutazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
• 7.8 Spettro del grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
• 7.8.1 Lo spettro di k_n (grafo completo) . . . . . . . . . . . . . . . . . . . . . . 48
• 7.8.2 Lo spettro di k_m,n (grafo completo-bipartito) . . . . . . . . . . . . . . . 48
• 7.8.3 Spettro di C_n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
• 7.9 Grafo cammino (P_n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Chapter 1 Introduzione

1.1 Cos’è la matematica discreta?

La matematica discreta è la branca della matematica che studia le strutture matematiche discrete, nel senso che non supportano o richiedono né il concetto di continuità né quello di densità.

Definizione: un sottoinsieme Y di uno spazio metrico X si dice denso in X se, per ogni elemento x di X e per ogni numero reale positivo ε esiste un elemento y di Y che dista da x meno di ε. La maggior parte degli oggetti studiati nella matematica discreta (se non tutti) sono insiemi numerabili come gli interi.

La matematica discreta è diventata famosa per le sue applicazioni in informatica. I concetti e le notazioni della matematica discreta sono utili per lo studio o la modellazione di oggetti o problemi negli algoritmi informatici e nei linguaggi di programmazione.

La matematica discreta include normalmente:

• Logica: studio del ragionamento corretto;
• Teoria degli insiemi: uno studio delle collezioni di elementi;
• Teoria dei numeri;
• Combinatoria: la parte della matematica che studia insiemi finiti di oggetti semplici e le loro proprietà ben definite;
• Teoria dei grafi;
• La teoria della probabilità e le catene di Markov.

Definizione: la proposizione è una frase (affermazione) di cui possiamo dire con certezza se è vera o falsa.

Definizione: il predicato è una frase che contiene variabili e che si trasforma in proposizione quando le variabili vengono sostituite con costanti.

Si può trasformare un predicato in una proposizione? Sì, quantificando le variabili, cioè utilizzando ∀ (per ogni) e ∃ (esiste).

56 Chapter 1. Introduzione

Chapter 2 Principio di induzione

Il principio di induzione (P.I.) o principio di induzione debole (P.I.D) è un principio che serve per dimostrare affermazioni del tipo: ∀n vale . . . = . . .).

Questo principio vale nell’insieme dei numeri naturali (N = 0, 1, 2, 3...). In tale insieme ogni numero ha un successivo, sono ben definite somma, prodotto e ordine ed esiste un primo numero (lo zero).

2.1 Principio di induzione (con gli insiemi)

Sia S ⊆ N tale che

• n₀ ∈ S (cioè S non vuoto) −→ passo base
• Se n ≥ n₀ e n ∈ S allora (n + 1) ∈ S −→ passo induttivo

Allora n ∈ S : n ≥ n₀.

2.2 Principio di induzione (con i predicati)

Sia P(n) predicato di variabile n (n ∈ N); supponiamo n₀ ∈ N.

a. P(n₀) è vera.

b. Se n ≥ n₀ e P(n) è vera allora P(n + 1) è vera.

Allora P(n) è vera.

2.3 Altre forme del principio di induzione

I principi indicati sotto sono equivalenti al principio di induzione.

2.3.1 Principio del buon ordinamento (P.B.O.)

Ogni sottoinsieme non vuoto di N ha minimo.

Ricordiamo cosa vuol dire minimo: m è minimo di S se e solo se S ⊆ N, m ∈ S e m ≤ n ∀n ∈ S.

Il principio del buon ordinamento non vale in Z.

Per dimostrarlo basta trovare un controesempio cioè un esempio di insieme S ⊆ Z che non soddisfi il principio del buon ordinamento.

78 Chapter 2. Principio di induzione

Osservazione: si può dimostrare che il principio del buon ordinamento equivale al principio di induzione ⇐⇒ teorema P.B.O. P.I.

Dimostrazione: supponiamo che P.B.O. vera in N. Dimostriamo P.I. è vero. Quindi preso un predicato qualsiasi P(n), supposto che soddisfi (a) e (b) (per un certo n₀), devo dimostrare che vale la conclusione (c) cioè P(n) vera ∀n ≥ n₀.

Considero l’insieme A = {n ∈ N e n ≥ n₀ : P(n) falsa}. Equivalentemente devo dimostrare che A = 0.

Ragiono “per assurdo” suppongo che A ≠ 0 per P.B.O. cioè ∃ n₁ = min A ⇒ n₁ ∈ A ⇒ n₁ ≥ n₀ e P(n₁) è falsa.

Stiamo supponendo (a) e (b); se so a), so che P(n₀) è vera. Inoltre, se n₁ = n₀ ⇒ P(n₁) è vera. Abbiamo n₁ > n₀; n₁ − 1 ∈ N, n₁ − 1 ≥ n₀ ⇒ n₁ − 1 /∈ A ⇒ P(n₁ − 1) è vera.

Posso usare (b) per (n₁ − 1) ⇒ P(n₁) = P((n₁ − 1) + 1) è vera, cioè P(n₁) è vera. Abbiamo trovato una contraddizione ⇒ è vero che A = 0/ ⇒ P(n) è vera ∀n ≥ n₀.

P(n) è un predicato qualsiasi, quindi abbiamo dimostrato che dal P.B.O. segue P.I.

2.3.2 Forma forte del principio di induzione (P.I.F.)

Dato un predicato P(n) e n₀ ∈ N.

∀n ≥ n₀, se P(j) è vera ∀j tale che n₀ ≤ j ≤ n allora P(n + 1) è vera.

Allora vale P(n) ∀n ≥ n₀.

Teorema di equivalenza P.B.O. ⇒ P.I. ⇒ P.I.F. ⇒ P.B.O.

Ragionamento deduttivo: se tutte le premesse sono vere allora anche la conclusione sarà vera.

Ragionamento induttivo: nonostante le premesse siano tutte vere, la conclusione non è detto che sia vera.

Chapter 3 Numeri naturali

3.1 Assiomi di N (o assiomi di Peano)

Esiste una terna (N, 0, σ) tale che

N è un insieme.

0 ∈ N (quindi non è vuoto).

σ : N → N è una funzione iniettiva cioè se σn = σm ⇒ n = m.

0 ∉ σ(N) (σ non è suriettiva).

Se S ⊆ N tale che 0 ∈ S e σ(S) ⊆ S allora S = N.

Osservazioni:

• 1. Si “postula” l’esistenza di (N, 0, σ).
• 2. Se scelgo N = 0,1,2, . . . , σ(n) = n + 1 è iniettiva.
• 3. Corrisponde al principio di induzione.
• 4. Dai soli assiomi (in maniera ricorsiva) si può costruire la struttura di somma, prodotto con proprietà e introduce la relazione n ≤ m ⇐⇒ ∃k ∈ N, n + k = m.
• 5. Peano mostra che gli assiomi caratterizzano la terna (N, 0, σ) in modo unico a meno di isomorfi.

Teorema: se (N, 0, σ) e (N′, 0′, σ′) soddisfano tutti gli assiomi di Peano ⇒ ∃! ϕ : N → N′ biunivoca, ϕ0 = 0′ e ∀n ∈ N ϕσn = σ′ϕn, cioè mette in corrispondenza 0 e 0′, ed il successivo di n con il successivo di ϕ(n).

910 Chapter 3. Numeri naturali

Chapter 4 Cardinalità

L’equipotenza è una relazione di equivalenza cioè ha la proprietà riflessiva, simmetrica e transitiva.

Definizione: f : A → B è biunivoca ⇐⇒ f è iniettiva e suriettiva (∃ f⁻¹ : B → A tale che f⁻¹ ◦ f = Id_A e f ◦ f⁻¹ = Id_B).

Definizione: due insiemi A e B si dicono equipotenti se esiste una funzione f : A → B biunivoca (A ∼ B).

Definizione: se ∃n ∈ N tale che A e {1, 2, 3, . . . , n} sono equipotenti allora si dice che |A| = n è la cardinalità di A. La definizione di cardinalità si estende all’insieme 0/ ponendo |0/| = 0.

Definizione: un insieme A si dice finito se ∃n ∈ N tale che |A| = n.

Osservazione: se A è un insieme finito, la cardinalità indica il numero di elementi di A.

Osservazione: se f : {1, 2, 3, . . . , n} → A è biunivoca, f opera in questo modo:

1 ↦ f(1) = a₁ ∈ A

2 ↦ f(2) = a₂ ∈ A

...

n ↦ f(n) = a_n ∈ A

Cioè f definisce un modo per contare gli elementi di A.

Relazioni di equivalenza in un insieme: dato X insieme qualsiasi; una relazione R è un sottoinsieme del prodotto cartesiano X × X.

a ∼ b ⇐⇒ (a,b) ∈ R.

R ⊆ X × X ∀a, b ∈ X.

Definizione: se equipotenza è di equivalenza, dato a ∈ X si chiamano classi di equivalenza [a] di a l’insieme formato da tutti gli elementi che sono equivalenti ad A.

A ∼ B ⇐⇒ A, B sono equipollenti.

Proprietà: la relazione tra insiemi ”A sono equipollenti” è una relazione di equivalenza.

Dimostrazione: ∼ è un’equivalenza:

• 1) ∼ è riflessivo cioè A ∼ A ∀A.
• 2) ∼ è simmetrico cioè A ∼ B ⇐⇒ B ∼ A.
• 3) ∼ è transitivo cioè A ∼ B e B ∼ C ⇒ A ∼ C.

1. Id_A : A → A è l’identità in A ⇐⇒ ∃ f : A → B biunivoca, f(a) = a ∀a ∈ A.

2. Se f : A → B biunivoca ⇒ f⁻¹ : B → A, la funzione inversa è biunivoca.

3. Se f : A → B biunivoca e g : B → C biunivoca ⇒ ∃ h : A → C: prendo h = g ◦ f ⇒ è ancora biunivoca.

1112 Chapter 4. Cardinalità

Corollario: tutti gli insiemi equipollenti con uno stesso insieme finito hanno la stessa cardinalità.

Osservazione: la relazione di equipollenza vale anche tra insiemi non finiti.

Definizione:

• A si dice numerabile ⇐⇒ A ∼ N.
• A si dice non numerabile ⇐⇒ A né finito né numerabile.
• A si dice “al più” numerabile ⇐⇒ A è finito o numerabile.

Lo studio del “contare” con insiemi non finiti è stato effettuato da Georg Cantor.

4.1 Equivalenza al concetto di insieme finito

Teorema: le seguenti condizioni sono equivalenti:

• 1. A è infinito.
• 2. A contiene un sottoinsieme numerabile.
• 3. A è equipotente ad un sottoinsieme improprio.

Dimostrazione: si può dimostrare che 1) ⇒ 2) ⇒ 3) ⇒ 1).

Definizione di confronto tra cardinalità di insiemi infiniti:

|A| ≤ |B| ⇐⇒ ∃ f : A → B iniettiva.

Osservazione 1: se A ⊆ B, |A| ≤ |B| vero perché posso scegliere f = Id_A : A → B, a ↦ a.

Osservazione 2: la relazione |A| ≤ |B| è transitiva?

|A| ≤ |B| e |B| ≤ |C| ⇒ |A| ≤ |C|?

Cioè se ∃ f : A → B iniettiva, ∃ g : B → C iniettiva ⇒ ∃ h : A → C: se scelgo h = g ◦ f è ancora iniettiva ⇒ |A| ≤ |C|.

Osservazione 3: se A ∼ B (cioè sono equipotenti) ⇒ |A| ≤ |B| e |B| ≤ |A|?

Se A ∼ B vuol dire che ∃ϕ : A → B biunivoca ⇒ è anche iniettiva ⇒ ok |A| ≤ |B|.

Inoltre, f : B → A è biunivoca ⇒ iniettiva ⇒ |B| ≤ |A|.

Vale il viceversa? Quindi se |A| ≤ |B| e |B| ≤ |A| ⇒ A ∼ B? Se ∃ f : A → B iniettiva, ∃ g : B → A iniettiva ⇒ ∃ h : A → B biunivoca?

La risposta è sì ed è il contenuto del teorema di Cantor-Bernstein.

Osservazione 4: se vale il teorema vale allora la relazione di confronto tra cardinalità |A| ≤ |B| avrebbe tre proprietà:

• 1. Riflessiva: |A| ≤ |A|.
• 2. Transitiva: se |A| ≤ |B| e |B| ≤ |C| ⇒ |A| ≤ |C|.
• 3. Antisimmetrica: se |A| ≤ |B| e |B| ≤ |A| ⇐⇒ |A| = |B|.

Una relazione con le proprietà 1, 2, 3 si dice che è una relazione d’ordine.

4.2 Classe dell’insieme

4.2. Classe dell’insieme 13

Teorema: se in X c’è una relazione di equivalenza allora le classi di equivalenza formano una classe dell’insieme.

i. [a] ≠ 0/ ∀a ∈ X (proprietà riflessiva).

ii. [a] = [b] oppure [a] ∩ [b] = 0/ ∀a, b ∈ X (usando proprietà transitiva e simmetrica).

iii. ∪_a∈X [a] = X.

Definizione: si chiama quoziente e si indica con X/∼ l’insieme di tutte le classi di equivalenza (cioè la partizione).

Osservazione: la cardinalità di un insieme A, in modo informale, è come un’etichetta che caratterizza la classe di equivalenza a cui A appartiene, cioè è le caratteristiche che accomunano gli insiemi equipotenti ad A.

Definizione confronto tra cardinalità eventualmente diverse:

1. |A| ≤ |B| ∀A (proprietà riflessiva).

2. |A| ≤ |B| e |B| ≤ |C| ⇒ |A| ≤ |C| (proprietà transitiva).

Teorema di Cantor-Bernstein: se |A| ≤ |B| e |B| ≤ |A| ⇐⇒ |A| = |B|, cioè A e B sono equipotenti.

Osservazione: il teorema di Cantor-Bernstein afferma che vale la proprietà antisimmetrica; si può concludere che il minore-uguale (≤) è una relazione d’ordine.

Esempio: f : P → N è iniettiva ma non suriettiva, n ↦ n ⇒ |P| ≤ |N|.

Proprietà: se A, B ≠ 0/, ∃ f : A → B iniettiva ⇐⇒ ∃ g : B → A suriettiva.

Esempio: |N| < |R|.

1) Ci sono cardinalità intermedie?

Non possiamo rispondere.