Strutture discrete/Matematica discreta

STRUTTURE DISCRETE

APPUNTI COMPLETI

- TUTTE LE DIMOSTRAZIONI

- TUTTTI GLI ESERCIZI RISOLTI CON PASSAGGI

- TUTTI I TRUCCHI PER SEMPLIFICARE I CALCOLI DIANA INGRID PUTELLI

INDICE:

PARTE 0

- INTRODDUZIONE AL CORSO

0.1 IL MONDO DISCRETO DELL’INFORMATICA

0.2 IL MONDO BINARIO DELL’INFORMATICA

PARTE 1

1.1 Introduzione alla Logica Proposizionale e agli Operatori di Base

1.2 Il Concetto di Insieme e le Proprietà di Base

1.3 Insiemi ed Operazioni tra di Essi

1.4 Dimostrazione Diretta

1.5 Famiglie di Insiemi

1.6 Insieme Prodotto

1.7 Paradossi

1.8 Relazioni Binarie e Funzioni

1.9 Relazioni di Equivalenza

1.10 Relazioni d'Ordine

1.11 Rappresentazione di Insiemi Finiti

1.12 Il Problema dell'Hitting Set

1.13 Caso Studio: Famiglie di Insiemi Chiuse e la Congettura Union-Closed

PARTE 2

2.1 Numeri Naturali, Interi Relativi, Razionali

2.2 Divisione tra Interi

2.3 Divisibilità e Criteri di Divisibilità

2.4 MCD ed Algoritmo di Euclide

2.5 Numeri Primi e Coprimi

2.6 Aritmetica Modulare

2.7 Congruenze

2.8 Proprietà delle Congruenze

2.9 Invarianza rispetto a Somma e Prodotto

2.10 Funzione φ di Eulero - Definizione e Formula Generale

2.11 Il Teorema di Eulero

2.12 Applicazioni dell'Aritmetica Modulare

2.13 La Prova del 9

2.14 Codici ISBN e Carte di Credito

2.15 Cifrari Monoalfabetici a Trasposizione

2.16 Teoria dei Numeri e Problemi Aperti

2.17 Numeri Primi di Mersenne e Numeri Perfetti

2.18 Numeri Primi Gemelli

2.19 La Congettura di Goldbach

2.20 Caso Studio: Il Problema 3x+1 (Congettura di Collatz)

PARTE 3

3.1 Disposizioni e Combinazioni

3.2 Permutazioni e Combinazioni

3.3 Teorema Binomiale

3.4 Il Triangolo di Pascal

3.5 Combinazioni con Ripetizione

3.6 Il Principio dei Cassetti (Pigeonhole Principle)

3.7 Formalizzazione Matematica - Assiomi e Proprietà

3.8 La Regola di Bayes

3.9 Problemi d'Urna

3.10 Variabili Casuali

3.11 Caso Studio: Giochi e Paradossi Probabilistici (Il Paradosso di Monty Hall)

PARTE 4

4.1 Introduzione: Strette di Mano e Passeggiate su Ponti

4.2 Definizioni di Base

4.3 Gradi di un Nodo

4.4 Classi Particolari di Grafi: Grafi Regolari, Grafi Completi, Grafi Bipartiti

4.5 Sottografi, Isomorfismi e Omeomorfismi

4.6 Percorsi, Cammini e Cicli

4.7 Grafi Connessi

4.8 Rappresentazione di un Grafo

4.9 Numero di Percorsi tra Nodi

4.10 Grafi Euleriani e Grafi Hamiltoniani

4.11 Grafi Pesati e il Problema del Commesso Viaggiatore

4.12 Colorazione di Grafi e Numero Cromatico

4.13 Grafi Planari, Formula di Eulero e Caratterizzazione della Planarità

4.14 Definizione di Albero e Caratterizzazione. Alberi Binari e loro Proprietà.

4.15 Casi Studio: Esempi di Problemi Combinatori Computazionalmente Complessi

PARTE 0

- IL MONDO DISCRETO DELL’INFORMATICA

Discreto ≠ Indiscreto! In matematica/informatica, l'opposto di discreto è continuo.

Il computer è DISCRETO: lavora con 0 e 1 (bit), non con valori continui.

La digitalizzazione = campionamento + quantizzazione (trasformare il mondo continuo

in discreto).

Cos'è l'Informatica?

Informatica = Information + Automatique (elaborazione automatica dell'informazione)

Come funziona? Per mezzo di ALGORITMI.

Algoritmo = una sequenza finita e ordinata di operazioni, ognuna delle quali si completa

in un tempo finito.

Cosa fa un Computer?

Un computer deve fare 3 cose fondamentali:

N. Cosa fa Come lo fa

Input/Output

1 Usa i dispositivi di input/output (tastiera, monitor, etc.)

Memorizzare

2 Usa la memoria principale (RAM) e secondaria (HD)

Elaborare

3 Usa il processore (CPU)

- IL MONDO BINARIO DELL’INFORMATICA

Il computer parla solo 0 e 1 (sistema binario).

Bit = Binary Digit (0 o 1).

Byte = 8 bit (l'unità di misura base della memoria).

Con n bit si possono rappresentare 2ⁿ sequenze.

Le unità di misura sono: KB, MB, GB, TB (per la memoria) e Kb, Mb, Gb (per la

trasmissione).

Il Linguaggio del Computer

Per comunicare con il computer, serve un linguaggio formale. Come tutti i linguaggi, ha

bisogno di:

1. Un Alfabeto: Un insieme finito di simboli.

L'alfabeto minimale dell'informatica è quello binario: {0, 1}.

o Ogni simbolo (0 o 1) si chiama bit (binary digit).

o

2. Una Grammatica: Regole per combinare i simboli.

Esempio: 1011 è una parola binaria valida.

o

Importante: La stessa informazione può essere rappresentata con codifiche

⚠️

diverse!

Il numero 2021 in decimale = 2021

 Il numero 2021 in romano = MMXXI

 Il numero 2021 in binario = 11111100101



 Numero di Bit Combinazioni Possibili Esempi

2 2² = 4 00, 01, 10, 11

3 2³ = 8 000, 001, 010, 011, 100, 101, 110, 111

2⁸ = 256

8 (1 byte) 00000000, 00000001, ..., 11111111

Regola d'oro: Con n bit si possono rappresentare 2ⁿ sequenze diverse.

Le Unità di Misura della Memoria

La capacità di memoria (RAM e HD) si misura in byte. Valore

Unità Simbolo Dimensione Approssimato

Kilobyte KB 2¹⁰ byte = 1.024 byte ~ 1.000 byte

Valore

Unità Simbolo Dimensione Approssimato

Megabyte MB 2²⁰ byte = 1.048.576 byte ~ 1 milione di byte

Gigabyte GB 2³⁰ byte = 1.073.741.824 byte ~ 1 miliardo di byte

2⁴⁰ byte = 1.099.511.627.776

Terabyte TB ~ 1 trilione di byte

byte

La Velocità di Trasmissione

La capacità di trasmissione dati si misura in bit.

Unità Simbolo Dimensione

Kilobit Kb 2¹⁰ bit = 1.024 bit

Megabit Mb 2²⁰ bit = 1.048.576 bit

Gigabit Gb 2³⁰ bit = 1.073.741.824 bit

Rappresentazione dei numeri

1. Sistemi Additivi: I simboli hanno un valore fisso e si sommano (es. numeri

romani).

2. Sistemi Posizionali: Il valore di una cifra dipende dalla sua posizione (es.

decimale, binario).

3. Il sistema binario è posizionale in base 2.

PARTE 1

1.1 INTRODUZIONE ALLA LOGICA PROPOSIZIONALE E AGLI OPERATORI DI BASE

INTRODUZIONE STORICA

La logica proposizionale viene sviluppata nel III secolo A.C. dalla scuola degli Stoici ed in

particolare Crisippo.

Gran parte del lavoro e degli scritti originali furono perduti. Solo tanti secoli dopo il lavoro

prima di Leibnitz e poi di Boole e De Morgan formalizzò in maniera definitiva il campo.

La Logica Proposizionale è, anche per questo, conosciuta come Logica Booleana.

LA LOGICA COME LINGUAGGIO FORMALE

Le logiche sono linguaggi formali per rappresentare informazioni da cui trarre

conclusioni.

Ogni linguaggio è la composizione di due parti fondamentali:

Concetto Definizione

Definisce le frasi (formule) del linguaggio

Sintassi Definisce il significato delle frasi (vero/falso)

Semantica

TIPI DI LOGICHE

Linguaggio Assunzioni ontologiche Valori di verità

Fatti Vero/Falso

Logica Proposizionale Fatti e relazioni su oggetti Vero/Falso

Logica del primo ordine Fatti, tempo e relazioni su oggetti Vero/Falso

Logica Temporale Fatti, tempo e relazioni su oggetti Grado di credenza

Logica Probabilistica

La logica proposizionale è la logica più semplice, inerentemente connessa al mondo

binario 0/1 dei calcolatori. Si occupa di fatti, proposizioni o affermazioni e della loro

veridicità.

PROPOSIZIONI

Definizione: Una proposizione è un'affermazione che è vera oppure falsa, ma non

entrambe.

SINTASSI DELLA LOGICA PROPOSIZIONALE

Variabili Proposizionali

Il vocabolario consiste di un insieme di variabili proposizionali P, denotate con p, q, r, . .

. o con numerazione sottoscritta (p₁, p₂, etc.).

Le variabili proposizionali possono assumere solo 2 valori:

1 o Vero (True, T)

 0 o Falso (False, F)



Ogni variabile proposizionale è, già da sé, una formula proposizionale.

I Connettivi Logici

Simbolo Nome Leggi

Negazione "non"

¬

∨ Disgiunzione "o"

∧ Congiunzione "e"

⇒ Implicazione "se...allora" o "implica"

⇔ Coimplicazione "se e solo se" o "implica e co-implica"

Formule Proposizionali

Se P e Q sono formule, allora sono formule anche:

Operazione Formula

Negazione ¬P (oppure ¬Q)

∨

Disgiunzione P Q

∧

Congiunzione P Q

⇒

Implicazione P Q

⇔

Doppia implicazione P Q

Precedenza degli Operatori

1. ( ) Parentesi

2. ¬ Negazione (ha la precedenza maggiore!)

3. e (stessa precedenza, si applicano da sinistra verso destra)

∧ ∨

4. e

⇒ ⇔

ATTENZIONE!

⚠️ = (leggi: "non p o q")

 ¬p ∨ q (¬p) ∨ q

= la negazione si applica a tutta la disgiunzione (leggi: "non (p o q)")

 ¬(p ∨ q)

SEMANTICA: INTERPRETAZIONE

Una interpretazione I su P è una funzione:

{0, {,

o

1} }

: → : →

Data una interpretazione I:

Formula È vera se e solo se

I(P₁) è falsa

I(¬P₁) almeno una tra I(P₁) e I(P₂) è vera

I(P₁ P₂)

∨ I(P₁) e I(P₂) sono entrambe vere

I(P₁ P₂)

∧ I(P₁) è falsa oppure I(P₂) è vera

I(P₁ P₂)

⇒ I(P₁ P₂) è vera e I(P₂ P₁) è vera

I(P₁ P₂) ⇒ ⇒

⇔

TAVOLE DI VERITÀ

Negazione (¬)

P ¬p

V F

F V

La negazione inverte il valore di verità.

Esempi:

Proposizioni Vere Proposizioni False

Roma è la capitale d'Italia Catania è la capitale d'Italia

3 > 2 2 > 3

Non è vero che Catania è la capitale d'Italia Non è vero che Roma è la capitale d'Italia

Congiunzione (∧) - "e" ∧

p q p q

V V V

V F F

F V F

F F F

Vera SOLO quando entrambe sono vere.

Esempi:

P₁ P₂ P₁ P₂

∧

Roma è la capitale Catania è capoluogo Sicilia F

Roma è la capitale Palermo è capoluogo Sicilia V

Milano è la capitale Non è vero che Catania è capoluogo F

Disgiunzione (∨) - "o" ∨

p q p q

V V V

V F V

F V V

F F F

Falsa SOLO quando entrambe sono false.

Implicazione (⇒) - "se...allora" ⇒

p q p q

V V V

V F F

F V V

F F V

Falsa SOLO quando p=V e q=F!

Doppia Implicazione (⇔) ⇔

p q p q

V V V

V F F

F V F

F F V

Vera SOLO quando p e q hanno lo stesso valore.

SODDISFACIBILITÀ

Tipo Definizione Esempio

Esiste ALMENO una interpretazione I tale che I(P) = p ∧ (q ∨ ¬p)

Soddisfacibile V

Tipo Definizione Esempio

p ∧ (q ∨ ¬p) ∧ (¬q ∨

NON esiste alcuna interpretazione I tale che I(P) = V

Insoddisfacibile ¬p)

p ⇒ (¬p ⇒ q)

Tautologia (Valida) Per OGNI interpretazione I, I(P) = V

Una formula è valida se e solo se la sua negazione è insoddisfacibile.

I Due Principi Fondamentali

Principio Formula Tipo

∨ Tautologia (sempre vera)

Terzo escluso p ¬p

∧ Insoddisfacibile (sempre falsa)

Non contraddizione p ¬p

EQUIVALENZA LOGICA

Due formule P e Q si dicono equivalenti (P ≡ Q) se hanno lo stesso valore di verità per

ogni interpretazione.

Proprietà dei Connettivi

Proprietà Formula

q ≡ q

∨ ∨ ∨

Commutatività p p

q ≡ q

∧ ∧ ∧

Commutatività p p

r ≡ p

∨ ∨ ∨ ∨ ∨

Associatività (p q) (q r)

r ≡ p

∧ ∧ ∧ ∧ ∧

Associatività (p q) (q r)

Altre Equivalenze

Nome Formula

¬(¬p) ≡ p

Doppia negazione

Nome Formula

q ≡ ¬q

⇒ ⇒

Contrapposizione p ¬p

q ≡ ¬p

⇒ ∨

Eliminazione implicazione p q

q ≡ (p

⇔ ⇒ ∧ ⇒

Eliminazione doppia implicazione p q) (q p)

Leggi di De Morgan

Formula

q) ≡ ¬p

∨ ∧

¬(p ¬q

q) ≡ ¬p

∧ ∨

¬(p ¬q

Distributività

Formula

r) ≡ (p

∧ ∨ ∧ ∨ ∧

p (q q) (p r)

r) ≡ (p

∨ ∧ ∨ ∧ ∨

p (q q) (p r)

Equivalenze con Valori Numerici

Operazione Equivalenza Numerica

∨ max(p, q)

p q

∧ min(p, q)

p q

⇒ max(1 - p, q)

p q

⇔ min(max(1 - p, q), max(p, 1 - q))

p q

CONSEGUENZA LOGICA (⊨)

Sia Γ un insieme di formule e P una proposizione.

Γ⊨

se ogni interpretazione I che soddisfa tutte le formule di Γ soddisfa anche P.

Esempio 1: Γ = {p, p q} q

⇒ ⊨

⇒

P q q

p q

V V V V

V F F F

F V V V

F F V F

Esempio 2: Γ = {p r, q ¬r} p q

∨ ∨ ⊨ ∨

FORME NORMALI

Forma Normale Congiuntiva (CNF)

Congiunzione di disgiunzioni.

Esempio: (p ∨ q) ∧ (¬p ∨ ¬r ∨ s)

Forma Normale Disgiuntiva (DNF)

Disgiunzione di congiunzioni.

Esempio: (p ∧ q) ∨ (¬p ∧ ¬r ∧ s)

Algoritmo di Trasformazione

Fase Operazione q → (p

⇔: ⇔ ⇒ ∧ ⇒

1 Elimina p q) (q p)

q → ¬p

⇒: ⇒ ∨

2 Elimina p q

Sposta ¬ (De Morgan e doppia negazione)

3 ∧ ∨

4-a Per CNF: distribuisci su

∨ ∧

4-b Per DNF: distribuisci su

Esempio: Trasforma in CNF e DNF

p (q (r s))

⇒ ∧ ∨

CNF:

Passo Risultato

⇒ ∨ ∧ ∨

Elimina ¬p (q (r s))

∧ ∨ ∨ ∧ ∨ ∨

Distribuisci su (¬p q) (¬p r s)

DNF:

Passo Risultato

⇒ ∨ ∧ ∨

Elimina ¬p (q (r s))

∨ ∧ ∨ ∧ ∨ ∧

Distribuisci su ¬p (q r) (q s)

ESERCIZI

Trasforma in CNF e DNF:

1. ¬(p ⇒ (q ∧ (r ∨ s)))

2. (q ∧ (r ∨ s)) ⇒ p

3. p ∧ (q ∨ (s ∧ (¬p ∨ ¬q)))

4. ((p ∨ ¬q ∨ r) ∧ s) ∨ t

1.2 IL CONCETTO DI INSIEME E LE PROPRIETA’ DI BASE

IL CONCETTO DI INSIEME E LE PROPRIETÀ DI BASE

COSA DEVI SAPERE ASSOLUTAMENTE

1. Un insieme è una collezione ben definita di oggetti

2. L'appartenenza (∈) è la relazione fondamentale

3. Due insiemi sono uguali se hanno gli stessi elementi (Assioma di Estensionalità)

4. La cardinalità |A| è il numero di elementi di A

5. Un insieme si dice discreto se i suoi elementi sono "isolati"

SPIEGAZIONE

Cos'è un insieme?

Definizione (intuitiva): Un insieme è una collezione ben definita di oggetti.

I sinonimi possibili sono: aggregato, classe, famiglia.

Attenzione: Seguiamo la "Teoria ingenua degli insiemi" (quella di Cantor), non la teoria

assiomatica di Zermelo-Fraenkel che esula dai nostri scopi.

Appartenenza (∈)

Se T è un insieme, l'espressione x T si legge: "x appartiene all'insieme T" oppure "x è

∈

un elemento di T".

Scriveremo x T per negare l'appartenenza.

∉

Assioma di Estensionalità (Uguaglianza)

Definizione: Due insiemi A e B sono uguali se hanno gli stessi elementi.

(∀ )( )

= ⇔ ∈ ⇔ ∈

Come descrivere un insieme

1. Per elencazione: Si elencano gli elementi tra parentesi graffe.

Esempi: = insieme con elementi 1, 2, 3

 {1, 2, 3}

= singoletto (insieme con un solo elemento)

 {a}

= insieme vuoto (non contiene elementi)

 ∅

2. Per proprietà: Si specifica una proprietà che caratterizza gli elementi.

{: ( )}

dove P(x) è una proprietà ben definita (per ogni x, P(x) è vera o falsa).

Esempi: è un insieme (anche se non conosciamo i divisori!)

 {x : x è un divisore di 10¹⁰⁰⁰ + 1}

NON è un insieme (non è una proprietà ben definita)

 {x : x è alto}

Importante: L'ordine e le ripetizioni non contano!

= =

 {1, 2, 3} {3, 2, 1} {1, 2, 3, 2, 1}

Cardinalità

Definizione: La cardinalità di un insieme A, denotata con |A|, è il numero di elementi che

lo costituisce.

Se |A| è un numero intero → insieme finito

 Se |A| non è un numero intero → insieme infinito



Esempi:

 |∅| = 0

 |{1, 2, 3}| = 3

 |{a}| = 1

 |{x : x è pari}| = +

Relazione di Inclusione (⊆)

Definizione: A è un sottoinsieme di B, denotato con A B, se:

⊆

(∀ )( )

⊆ ⇔ ∈ ⇒ ∈

Se A B, B è un sovrainsieme di A (B A)

 ⊆ ⊇

Se A B e A ≠ B, allora A è un sottoinsieme proprio di B (A B)

 ⊆ ⊂

Esempio:

T = {1, 2, 3, ..., 100}

{x T : x è multiplo di 10} = {10, 20, 30, ..., 100}

∈

Insiemi Discreti

Definizione: Un insieme A si dice discreto se è possibile ordinare i suoi elementi in

maniera tale che tra un elemento e il successivo non vi siano altri elementi dell'insieme.

Ogni insieme finito è discreto.

Insiemi Numerici

Insieme Nome Tipo

Numeri naturali Discreto

N Numeri interi relativi Discreto

Z Numeri razionali Né discreto né continuo

Q Numeri reali Continuo

R Numeri complessi Continuo

C ℕ⊂ℤ⊂ℚ⊂ℝ⊂ℂ

1.3 INSIEMI E OPERAZIONI TRA DI ESSI

COSA DEVI SAPERE ASSOLUTAMENTE

1. Unione (∪): elementi che appartengono ad almeno uno dei due insiemi

2. Intersezi