| Bibliografia |
- Kenneth H. Rosen, Discrete mathematics and its
applications, Mc Graw-Hill
- Peter J. Eccles, An Introduction to mathematical
reasoning, Cambridge University Press
- Note del corso (formato pdf) (aggiornate settimanalmente)
- Note 1 (presentazione del corso)
- Note 2 (insiemi, prima parte)
- Note 3 (insiemi, seconda parte)
- Note 4 (funzioni)
- Note 5 (introduzione alla logica)
- Note 6 (logica proposizionale, prima parte)
- Note 7 (logica proposizionale, seconda parte)
- Soluzione Es.1.24 (logica proposizionale, seconda parte)
- Note 8 (logica predicativa, introduzione)
- Note 9 (logica predicativa, prima parte)
- Note 10 (logica predicativa, seconda parte)
- Esercizi di preparazione al primo compitino
- Note 11 (tecniche di dimostrazione, prima parte)
- Note 12 (tecniche di dimostrazione, seconda parte)
- Soluzione Es.1.10 (tecniche di dimostrazione, seconda parte)
- Note 13 (tecniche di dimostrazione, terza parte)
- Soluzione Es.1.12 e 1.13 (tecniche di dimostrazione, terza parte)
- Note 14 (dimostrazioni su insiemi)
- Soluzione Es.1.19 (dimostrazioni su insiemi)
- Note 15 (dimostrazioni sull'aritmetica, prima parte)
- Note 16 (dimostrazioni sull'aritmetica, seconda parte)
- Note 17 (dimostrazioni sull'aritmetica, terza parte)
- Note 18 (dimostrazioni sull'aritmetica, quarta parte)
- Note 19 (relazioni, prima parte)
- Note 20 (relazioni, seconda parte)
- Note 21 (calcolo combinatorio)
- Esercizi di preparazione al secondo compitino
- Tabelle riassuntive (formato pdf) (aggiornate settimanalmente)
- Materiale integrativo: Note di Francesca Levi (formato pdf)
|
|
| Lezioni |
- Martedì 26 Settembre 2006:
Presentazione del corso.
Puntatori a testi di consultazione.
Rompicapo logico-matematici.
Dimostrazioni visuali.
Ultimo teorema di Fermat.
Congettura di Eulero.
Congettura di Goldbach.
Esercizi.
- Venerdì 29 Settembre 2006:
Definizione di: insieme, uguaglianza tra insiemi, inclusione, sottoinsieme e sottoinsieme proprio.
Diagrammi di Eulero-Venn.
Cardinalità di insiemi finiti.
Insieme delle parti.
Esercizi.
- Martedì 3 Ottobre 2006:
Prodotto cartesiano.
Unione, intersezione, differenza, complemento.
Insiemi disgiunti.
Leggi booleane (idempotenze, commutatività, associatività, identità, dominanza, distributività).
Dimostrazioni con diagrammi di Eulero-Venn.
Esercizi.
- Venerdì 6 Ottobre 2006:
Prove basate su diagammi, prove discorsive, prove basate su equivalenze note.
Famiglie di insiemi.
Definizione di funzione, dominio, codominio, immagine.
Rappresentazione grafica.
Esercizi.
- Martedì 10 Ottobre 2006:
Restrizione.
Funzione caratteristica di un insieme.
Funzioni iniettive, surgettive e bigettive.
Funzioni biunivoche e inverse.
Controimmagine.
Composizione di funzioni.
Teoremi su composizione di funzioni.
Introduzione alla logica matematica: sintassi, semantica e deduzione.
Proposizioni elementari.
Negazione.
Tabelle di verità.
Congiunzione.
Esercizi.
- Venerdì 13 Ottobre 2006:
ANNULLATA.
- Martedì 17 Ottobre 2006:
Disgiunzione (inclusiva e esclusiva).
Implicazione.
Doppia implicazione.
Formule proposizionali.
Disambiguazione delle formule.
Esercizi.
- Venerdì 20 Ottobre 2006:
Semantica delle formule: interpretazione.
Tautologia, contraddizione e soddisfacibilità.
Equivalenza logica.
Principio di rimpiazzamento.
Leggi di identità, dominanza, idempotenza, commutatività, associatività, doppia negazione, terzo escluso, non contradditorietà, De Morgan, distributività.
Esercizi.
- Martedì 24 Ottobre 2006:
Leggi di assorbimento e semplificazione.
Eliminazione dell'implicazione.
Riduzione a formule con sole negazione e congiunzione.
Consistenza di insiemi di formule.
Riassunto su logica proposizionale.
Esempi di logica predicativa.
Esercizi.
- Venerdì 27 Ottobre 2006:
Quantificatore universale.
Quantificatore esistenziale.
Costanti, variabili, simboli di funzione, simboli di predicato.
Termini, formule atomiche, formule predicative.
Campo d'azione dei quantificatori.
Variabili libere e legate. Formule aperte e chiuse.
Termini chiusi.
Interpretazione.
Valutazione di termini chiusi.
Sostituzioni.
Validità di formule predicative rispetto a una interpretazione fissata.
Esercizi.
- Martedì 31 Ottobre 2006:
Validità di formule predicative rispetto a una interpretazione fissata.
Truth Set.
Formule predicative valide, soddisfacibili, insoddisfacibili.
Equivalenza di formule predicative.
Leggi di equivalenza sui quantificatori.
Rappresentazione di frasi in logica predicativa.
Esercizi.
- Venerdì 3 Novembre 2006:
Esercizi di preparazione al compitino
- Venerdì 10 Novembre 2006:
PRIMA PROVA INTERMEDIA
- Martedì 14 Novembre 2006:
Correzione primo compitino.
Quantificazione esistenziale con unicità.
Definizione di teorema, lemma, corollario, congettura, teoria, conseguenza logica.
Regole di inferenza valide: esempi.
Sistemi di dimostrazione formale.
Esercizi.
- Venerdì 17 Novembre 2006:
Sistemi corretti.
Regole di inferenza della logica proposizionale: OR-INTRO, AND-INTRO, MODUS PONENS, MODUS TOLLENS, DISJUNCTIVE SYLLOGISM, HYPOTHETICAL SYLLOGISM, AND-ELIM, EQUIV, CONTRADICTION.
Dimostrazioni formali.
Regole di Generalizzazione e di Istanziazione dei quantificatori Universale e Esistenziale.
Esercizi.
- Martedì 21 Novembre 2006:
Esercizi su regole di Generalizzazione e di Istanziazione dei quantificatori Universale e Esistenziale.
Tecniche di prova con regole estese.
Prove dirette.
Prove indirette.
- Venerdì 24 Novembre 2006:
Prove per assurdo.
Prove per casi.
Doppia implicazione.
Modularità nelle prove.
Dimostrazioni su domini specifici: gli insiemi.
Interpretazione su dominio degli insiemi.
Lemmi elementari.
Dimostrazioni formali su insiemi.
Relazione tra dimostrazioni discorsive e dimostrazioni formali.
Esercizi.
- Martedì 28 Novembre 2006:
Dimostrazioni formali, dimostrazioni discorsive e controesempi su proprietà degli insiemi.
Dimostrazioni su domini specifici: l'aritmetica.
Definizione di numero primo, numero composto, divisibilità, fattore e multiplo.
Lemma primo o composto.
Lemma divisibilità #1, #2 e #3.
Esercizi.
- Venerdì 1 Dicembre 2006:
Test di primalità.
Teorema del test di divisibilità.
Prove costruttive e non costruttive.
Massimo comun divisore.
Co-primi (o primi relativi).
Proprietà dei divisori di primi #1, #2 e #3.
Co-primalità dei fattori.
Esercizi.
- Martedì 5 Dicembre 2006:
Principio del buon ordinamento.
Algoritmo di divisione.
Algoritmo di Euclide per il calcolo del massimo comun divisore.
Teorema di Bezout e suoi corollari (senza dimostrazioni).
Definizioni ricorsive, algoritmi ricorsivi e prove per induzione.
Numeri triangolari.
La torre di Hanoi.
Numeri di Fibonacci.
Il problema della scacchiera senza una casella.
Induzione matematica debole.
Inganni dell'induzione: Tutti i gatti hanno lo stesso colore.
Esercizi.
- Venerdì 8 Dicembre 2006:
FESTIVITÀ.
- Martedì 12 Dicembre 2006:
Teorema di validità dell'induzione debole.
Induzione matematica forte.
Teorema fondamentale dell'aritmetica (dimostrata
l'esistenza della fattorizzazione, non l'unicità).
Numeri di Mersenne.
Relazioni binarie.
Operazioni su relazioni.
Rappresentazione con matrici e con grafi.
Relazioni su uno stesso insieme.
Proprietà riflessiva, simmetrica, transitiva.
Esercizi.
- Venerdì 15 Dicembre 2006:
Proprietà irriflessiva, antisimmetrica, asimmetrica.
Equivalenze.
Classi di equivalenza.
Partizioni.
Congruenze modulo m.
Ordinamenti parziali.
Diagrammi di Hasse.
Ordinamenti totali.
Esercizi.
- (RECUPERO) Mercoledì 20 Dicembre 2006:
Chiusura riflessiva di una relazione.
Chiusura simmetrica di una relazione.
Chiusura transitiva di una relazione.
Inclusione-esclusione.
Regola della somma.
Regola del prodotto.
Stringhe binarie.
Permutazioni.
Combinazioni.
Esercizi.
Esercizi di preparazione al compitino
- Venerdì 22 Dicembre 2006:
SECONDA PROVA INTERMEDIA
|
|