Logica e matematica discreta (2011/2012)

Codice insegnamento
4S000018
Docente
Andrea Masini
Coordinatore
Andrea Masini
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
II semestre dal 1-mar-2012 al 15-giu-2012.

Orario lezioni

II semestre
Giorno Ora Tipo Luogo Note
martedì 10.30 - 13.30 lezione Aula Gino Tessari  
mercoledì 11.30 - 13.30 lezione Aula Gino Tessari  

Obiettivi formativi

Lo scopo principale di questo insegnamento è introdurre le nozioni fondamentali della logica simbolica (sintassi, semantica, sistemi deduttivi) e della matematica discreta (insiemi, funzioni, grafi, alberi, strutture)

Programma

Parte 1 (3CFU) Matematica Discreta

Insiemi: corrispondenze e applicazioni, relazioni, equivalenze, partizioni, relazioni d'ordine, cardinalità, insieme finiti, numerabili e più che numerabili (teorema di Cantor), ordinamento dei cardinali;
Reticoli: concetti di inf e sup, reticoli completi e reticoli booleani, reticoli visti come esempio di struttura algebrica.
Grafi e alberi: cammini, circuiti euleriani, grafi planari e alberi.

Strutture Algebriche: insiemi dotati di un'operazione (esempi: semigruppi, monoidi, monoidi di parole, gruppi, permutazioni), insiemi dotati di più operazioni (esempi: anelli, algebre di Boole). Morfismi e isomorfismi di strutture.

Parte 2 (3CFU) Logica

Linguaggio proposizionale: connettivi e proposizioni, tavole di verità, valutazioni;
Strutture: esempi notevoli, monoidi, semigruppi, numeri naturali, grafi;
Linguaggio del I ordine: semantica di Tarski, conseguenza logica;
Deduzione naturale.
Teoremi fondamentali della deduzione naturale: correttezza (dimostrazione) e completezza (solo enunciato);
Formalizzazioni al primo ordine.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Alberto Facchini Algebra e Matematica Discreta (Edizione 1) Edizioni Decibel/Zanichelli 2000 978-8808-09739-2 Studiare: cap 1 (saltando paragrafo 5 e 6) cap 2 (saltando paragrafo 11 ed appendice 14.1)
Andrea Asperti, Agata Ciabattoni Logica a Informatica McGraw-Hill 2007 Srtudiare: Cap 1 (saltando 1.3.6 e 1.3.7) Cap 4 (saltando 4.3.4, 4.3.5 e 4.3.6)
Dirk van Dalen Logic and Structure (Edizione 4) Springer-Verlag 2004 3540208798

Modalità d'esame

Esame scritto

Materiale didattico

Documenti

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2011/2012 non sono ancora disponibili