B006803 - MATEMATICA DISCRETA E LOGICA

Italiano

Elementi di teoria degli insiemi. Funzioni, relazioni e principio di induzione. Elementi di calcolo combinatorio. Relazioni di ordine, reticoli ed algebre di Boole. Elementi di teoria dei numeri. Aritmetica modulare ed applicazioni alla crittografia. Elementi di teoria dei grafi. Formule-semantica. Il “teorema di forma normale”. Metodo di risoluzione. Logica dei predicati.

Dispense sul sito del corso. (Piattaforma UniFi e-Learning)

Conoscenze: Questo corso è inteso a sviluppare nello studente la comprensione delle idee matematiche e a maturare l’attitudine al pensiero astratto. Si vuole inoltre enfatizzare l’importanza di una corretta notazione matematica nel ragionamento scientifico. Lo studente aumenterà la sua conoscenza matematica, sviluppando la sua capacità nel linguaggio matematico.Competenze acquisite: Alla fine del corso lo studente acquisirà competenze di base nell’ambito della Matematica Discreta e della Logica, come specificato nel programma del corso. Acquisirà esperienza ed abilità nell’affrontare problemi di carattere combinatorio, aritmetico e logico.Capacità acquisite (al termine del corso): Alla fine del corso lo studente sarà in grado di: esporre correttamente e con linguaggio adeguato le nozioni studiate; risolvere problemi numerici direttamente o impostando algoritmi da implementare su macchine; sviluppare semplici dimostrazioni per via diretta, per assurdo e/o per induzione; manipolare espressioni logiche.

Insegnamenti contenenti i prerequisiti (vincolanti e/o consigliati)Corsi vincolanti: NessunoCorsi raccomandati: Nessuno

CFU: 9Numero di ore totali del corso: 234Numero di ore per studio personale e altre attività formative di tipo individuale: 150Numero di ore relative alle attività in aula: 80Numero di ore relative ad attività di laboratorio (lezioni in laboratorio): 0Numero di ore relative ad attività di esercitazioni (in laboratorio e in campo): 0Numero di ore relative ad attività seminariali: 0Numero di ore relative ad attività di stage: 0Numero di ore per prove in itinere: 4

Frequenza delle lezioni ed esercitazioni: RaccomandataStrumenti a supporto della didattica: UniFi e-Learning: http://e-l.unifi.itOrario di ricevimento: Prof. Marco BarlottiMartedì, 16:00-18:30;Giovedì, 15:30-17:30Via delle Pandette, 9 – 50127 FirenzeTel. 0554374669 – Fax 0554374913E-mail: marco.barlotti@dmd.unifi.it

Scritta e Orale

Teoria degli insiemi. Applicazioni. Cardinalità di insiemi. Combinatoria elementare: combinazioni e disposizioni, con e senza ripetizioni.Permutazioni: decomposizione in prodotto di cicli disgiunti e in prodotto di trasposizioni. Elementi di Teoria dei Numeri:induzione matematica, funzioni ricorsive, massimo comun divisore, algoritmo di Euclide. Rappresentazioni b-adiche. Equazioni diofantee ed aritmetica modulare. Applicazioni alla crittografia. Relazioni di equivalenza e relazioni d’ordine. Reticoli. Algebre di Boole. Elementi di teoria dei grafi.Logica proposizionale: formule, valutazioni, tautologie. Metodo di risoluzione: teorema di decomposizione, regole di Davis-Putnam, teorema di correttezza e completezza. Logica dei predicati. Teorema di forma prenessa, teorema di Skolem, universo di Herbrand, teorema di Herbrand.