Elementi di teoria degli insiemi. Il principio di induzione. Funzioni. Operazioni. Permutazioni. Relazioni di ordine. L'algoritmo di Euclide. Numeri primi. Reticoli. Relazioni di equivalenza. Alcune equazioni diofantine. Cardinalità. Elementi di combinatorica.
Grafi: grafi bipartiti, grafi piani, grafi euleriani, grafi hamiltoniani. Colorazioni.
Logica proposizionale: formule, la notazione in clausole, confutazioni.
Logica dei predicati: formule, forma normale prenessa, skolemizzazione.
Marco Barlotti - Appunti di Algebra.
Marco Barlotti - Appunti di Teoria dei Grafi.
Marco Barlotti - Appunti di Logica.
Questi testi, assieme a specifiche raccolte che comprendono esercizi con le loro soluzioni, sono resi via via disponibili sulla piattaforma e-learning dell'Università di Firenze nella pagina dedicata all'insegnamento:
https://e-l.unifi.it/course/view.php?id=7266
Obiettivi Formativi
Questo insegnamento vuole sviluppare nello studente la comprensione delle idee matematiche e maturarne l’attitudine al pensiero astratto, sottolineando anche l’importanza di una corretta notazione matematica nel ragionamento scientifico.
Alla fine del corso lo studente dovrà avere acquisito le seguenti competenze di base:
(1) familiarità con il linguaggio degli insiemi;
(2) conoscenza delle proprietà aritmetiche dei numeri naturali, specificatamente con riferimento alle operazioni di somma e prodotto, alla divisione euclidea e alle relazioni di "minore o uguale" e di "divisibilità";
(3) conoscenza dell'aritmetica modulare, e familiarità con alcune classi di equazioni diofantine;
(4) conoscenza dei problemi fondamentale della combinatorica e delle tecniche risolutive (principio di addizione, principio di moltiplicazione, principio dei buchi di piccionaia, teorema dei matrimoni);
(5) conoscenza delle nozioni più elementari di teoria dei grafi finiti (planarità, connessione) e di alcune classificazioni (in particolare, definizione dei grafi euleriani e dei grafi hamiltoniani);
(6) conoscenza dei principi fondamentali della logica proposizionale e della logica dei predicati;
(7) familiarità con le tecniche di confutazione e in particolare con l'algoritmo di Davis e Putnam.
Alla fine del corso, inoltre, lo studente dovrà avere acquisito le seguenti capacità:
(1) esporre correttamente e con linguaggio adeguato le nozioni studiate;
(2) sviluppare autonomamente semplici dimostrazioni (per induzione, per assurdo o applicando principi matematici);
(3) calcolare il massimo comun divisore fra due numeri naturali utilizzando l'algoritmo di Euclide;
(4) calcolare il minimo comune multiplo fra due numeri naturali;
(5) risolvere equazioni diofantine lineari in due incognite;
(6) applicare il teorema di Euler-Fermat alla risoluzione di alcune equazioni esponenziali;
(7) esprimere un numero naturale nelle notazioni posizionali riferite a diverse basi, e trasformare l'espressione di un numero naturale da una base all'altra;
(8) applicare alcuni criteri di divisibilità nelle diverse basi;
(9) calcolare la cardinalità di insiemi finiti applicando il principio di addizione e/o il principio di moltiplicazione;
(10) verificare la non planarità di un grafo applicando opportune condizioni necessarie;
(11) verificare se un grafo è euleriano;
(12) verificare, in alcuni casi particolari, se un grafo è hamiltoniano;
(13) descrivere il grafo duale di un grafo finito disegnato nel piano senza sovrapposizione di lati;
(14) trasformare una formula della logica proposizionale in altra, ad essa logicamente equivalente, che sia in forma normale congiuntiva;
(15) decidere se una formula della logica proposizionale è soddisfacibile;
(16) trasformare una formula della logica dei predicati in altra, ad essa logicamente equivalente, che sia in forma normale prenessa;
(17) trasformare una formula della logica dei predicati in altra, soddisfacibile se e soltanto se la precedente è soddisfacibile, che sia in forma di Skolem;
(18) decidere, in alcuni casi particolari, se una formula della logica dei predicati è soddisfacibile;
(19) risolvere semplici problemi logici traducendoli opportunamente in formule logiche e decidendone la soddisfacibilità.
Prerequisiti
Nessuno.
Metodi Didattici
L'insegnamento consiste in lezioni frontali, accompagnate da esercitazioni tenute anch'esse dal docente.
Nelle lezioni viene esposta la materia oggetto del corso cercando di sottolinearne gli aspetti essenziali; in questa ottica si evita in generale di soffermarsi su sottigliezze dimostrative per le quali gli studenti interessati possono comunque consultare i testi di riferimento gratuitamente disponibili nella pagina e-learning dell'insegnamento.
Nelle esercitazioni si applicano a casi specifici le tecniche precedentemente esposte in generale per via teorica. Una adeguata quantità di altri esercizi, corredati delle soluzioni complete, è altresì disponibile nella già citata pagina e-learning dell'insegnamento.
Sia durante le lezioni che durante le esercitazioni è incoraggiato l'intervento degli studenti con osservazioni, domande e richieste di chiarimento.
Altre Informazioni
L'insegnamento assegna 9 crediti formativi universitari.
Sono previste circa 70 ore di lezione e 20 ore di esercitazioni.
Nei mesi di febbraio e maggio si svolgeranno due prove scritte (cosiddette "in itinere") che consentono di presentarsi direttamente all'orale (evitando la prova scritta preliminare) in qualsiasi appello dello stesso anno accademico.
Non è prevista attività di laboratorio. Il numero di ore di studio individuali da dedicare alla materia da parte di ciascuno studente può essere stimato, molto grossolanamente, in 150; ovviamente il numero effettivo di ore che ciascuno studente impiegherà per acquisire le nozioni relative al corso dipenderà in modo essenziale dalla qualità dello studio e quindi potrà essere molto diverso, in più oppure in meno, rispetto a questa stima.
La frequenza delle lezioni è consigliata, ma il materiale che viene via via reso disponibile nella pagina e-learning dell'insegnamento dovrebbe risultare sufficiente per una adeguata preparazione.
Il prof. Marco Barlotti riceve gli studenti presso la stanza 2.13 al secondo piano di via delle Pandette 9 a Firenze, generalmente il mercoledì dalle 15:00 alle 17:00; è comunque gradita una email di preavviso all'indirizzo <marco.barlotti@unifi.it>, ed è comunque sempre possibile concordare per email un diverso luogo e/o un diverso orario per l'incontro.
Modalità di verifica apprendimento
Lo studente conseguirà i crediti relativi all'insegnamento superando un esame che consiste in:
(1) una prova scritta preliminare nella quale sono proposti da 5 a 7 esercizi per accertare la capacità del candidato di applicare semplici algoritmi risolutivi appresi a lezione;
e
(2) una prova orale nella quale vengono poste domande alle quali il candidato deve rispondere; nella dinamica domanda-risposta viene valutata la conoscenza da parte del candidato
(2.1) delle nozioni fondamentali apprese durante l'insegnamento (definizioni)
(2.2) dei collegamenti che intercorrono fra tali nozioni (teoremi)
e
(2.3) di alcune tecniche dimostrative di tali collegamenti.
Superare la prova scritta preliminare è condizione necessaria e sufficiente per sostenere (nello stesso appello) la prova orale.
Il candidato che abbia svolto con esito positivo le due prove "in itinere" che si tengono nel mese di febbraio e nel mese di maggio può accedere (una sola volta!) direttamente alla prova orale in qualunque appello dell'anno accademico in cui ha svolto tali prove.
Programma del corso
L'impostazione assiomatica in matematica: la teoria degli insiemi nei classici assiomi di Zermelo e Frenkel. Come si definisce un insieme: mediante elenco degli elementi, mediante una proprietà caratteristica, come unione di insiemi già definiti, come insieme delle parti. Coppie ordinate, n-ple ordinate, sequenze ordinate, matrici. Prodotto cartesiano.
Il principio di induzione. Dimostrazioni per induzione.
Relazioni in un insieme. Relazione inversa. Restrizione ad un sottoinsieme. Funzioni. Dominio. Immagine, immagine inversa. Iniettività e suriettività. La funzione inversa. Composizione di funzioni. Successioni definite per recursione. Le successioni "tipo Fibonacci".
Operazioni in un insieme. Chiusura rispetto a un'operazione. Associatività e commutatività. Elemento neutro. Il simmetrico di un elemento. La proprietà distributiva. Gruppi. Anelli. Anelli di matrici.
Permutazioni. Il gruppo simmetrico; Il gruppo Sym(n). Cicli.
Relazioni di ordine. Intervalli. Minimo e massimo. Elementi minimali ed elementi massimali. Limitazioni inferiori e limitazioni superiori. Estremo superiore. Estremo inferiore.
La divisione euclidea. Massimo comun divisore nei numeri naturali. L'algoritmo di Euclide. Una classe di equazioni diofantine. Minimo comune multiplo nei numeri naturali.
Numeri irriducibili e numeri primi. Il "teorema fondamentale dell'aritmetica". Numeri primi "di Fermat". Numeri primi "di Mersenne". Numeri perfetti.
Reticoli. Reticoli complementati. Distributività.
Relazioni di equivalenza. Classi di equivalenza. Insieme quoziente. Le classi di resto. La notazione posizionale in base "dieci" e in altre basi. I criteri di divisibilità per i numeri interi.
Equazioni di primo grado nell'anello delle classi di resto modulo n. Divisori dello zero ed elementi invertibili nell'anello delle classi di resto modulo n. La funzione "phi" di Euler. Il teorema di Fermat-Euler. Cenni sul criptosistema RSA.
Equipotenza. Cardinalità. Confronto tra cardinalità.
Il principio dei buchi di piccionaia. Il teorema dei matrimoni.
Elementi di calcolo combinatorio. Il principio di addizione e il principio di moltiplicazione. Disposizioni con ripetizione; disposizioni semplici. Combinazioni semplici; combinazioni con ripetizione.
Generalità sui grafi: grafi con orientamento, grafi senza orientamento. Isomorfismo fra grafi. Grafi bipartiti. Grafi disegnati su una superficie. Sottografi. Calibro.
Cammini, circuiti, cicli. Connessione. Una caratterizzazione dei grafi connessi bipartiti. Matrice di adiacenza. Alberi e foreste. Caratterizzazione degli alberi non orientati come grafi connessi minimali.
Calibro e planarità. Il teorema di Kuratowski.
Grafi euleriani: loro caratterizzazione. Grafi hamiltoniani: il teorema di Ore, il teorema di Grinberg.
Colorazione di carte geografiche. Il grafo duale di un grafo disegnato nel piano senza sovrapposizione di lati. Colorazione dei vertici di un grafo.
Enunciati. Il principio aristotelico del "terzo escluso". Alfabeto e formule della logica proposizionale. Valutazioni di verità. Le tabelle dei valori di verità. La forma normale congiuntiva. Notazione in clausole. Confutazioni. L'algoritmo di Martin Davis e Hilary Putnam. Confutazioni rapide. Il teorema di compattezza.
Formule ben formate nella logica dei predicati. Formule aperte e formule chiuse. Comparse libere e vincolate delle variabili. Valutazioni di verità nella logica dei predicati. Forma normale prenessa. Skolemizzazione. L'universo di Herbrand.