Il corso ha lo scopo di avvicinare lo studente ai concetti base della logica e dell'algebra. Alla fine del corso lo sudente dovrebbe essere in grado di scrivere una formula corretta in logica proposizionale ed in logica del  I ordine, di tradurre concetti in formule, di manipolare le formule trasformandole in particolari forme normali, di interpretare le formule, di produrre semplici dimostrazioni formali e dovrebbe essere  familiare con le principali strutture algebriche.

Vengono presentati il “linguaggio” dell’algebra e della logica focalizzando l'attenzione sui concetti di relazioni ed applicazioni, gli aspetti semantico e sintattico delle logiche proposizionale e del I ordine e, facendo uso della logica del I ordine,  vengono introdotte le principali strutture algebriche e le nozioni di sottostruttura, relazione di congruenza, struttura quoziente, omo/isomorfismi fra strutture simili. Proprietà caratteristiche delle varie strutture sono messe in evidenza su esempi che intervengono in molte applicazioni.

La parte di logica sarà anche supportata da una breve attività di esercitazioni in aula informatizzata per illustrare l’uso di un semplice theorem prover.

1. LOGICA DELLE PROPOSIZIONI

1.1 Il linguaggio della logica delle proposizioni, formule sintatticamente corrette. Valutazione di una formula, tautologie e contraddizioni. Deduzione ed equivalenza semantica. Forme normali disgiuntive e congiuntive.

1.2 Sistemi formali. Teoria L, teoremi di deduzione, correttezza e completezza, decidibilità. Risoluzione e raffinamenti.

2. RELAZIONI ED APPLICAZIONI

2.1 Relazioni, con particolare riguardo alle relazioni binarie su un insieme. Prodotto di relazioni. Proprietà delle relazioni binarie: serialità, riflessività, simmetria, transitività, antisimmetria.  Chiusure di una relazione rispetto ad un insieme dato di proprietà.

2.2 Relazioni di equivalenza ed applicazioni. Concetti di insieme quoziente, di kernel di una applicazione, teoremi di fattorizzazione di una applicazione. Cardinalità di un insieme e teorema di Cantor.

2.3 Relazioni d’ordine, i reticoli come insiemi ordinati.

2.4 Operazioni interne ed esterne, proprietà delle operazioni. Unità ed inverso di un elemento rispetto ad una operazione binaria.

3. LOGICA DEL I ORDINE

3.1 Il linguaggio del calcolo  predicativo del I ordine, termini e formule sintatticamente corrette. Variabili libere e vincolate. Formule chiuse. Valutazione di una formula: il concetto di interpretazione. Formule soddisfacibili, vere e logicamente valide. Forme normali prenesse, forme di Skolem.

3.2 Sistemi formali: cenni sulla teoria K e risoluzione.

3.3 Teorie del primo ordine e teorie del primo ordine con identità.

3.4 Modelli di una teoria.

3.5 Teoremi di deduzione, di correttezza e completezza. Questioni di decidibilità.

4. STRUTTURE ALGEBRICHE

4.1 Le principali strutture algebriche: semigruppi, monoidi, gruppi, anelli, corpi, cenni di teoria dei gruppi.

4.2 Sottostrutture, criteri relativi.

4.3 Relazioni di congruenza, strutture quozienti. La relazione di congruenza modulo n, aritmetica modulare e applicazioni

4.4 Strutture simili, omomorfismi ed isomorfismi fra strutture simili, il kernel di un omomorfismo ed il teorema di fattorizzazione degli omomorfismi.

Le nozioni contenute in un primo corso di algebra lineare e analisi matematica.

A) Valutazione in itinere:   Sono previste due prove in itinere e una valutazione di laboratorio. Il voto finale si ottiene aggiungendo al voto delle prove in itinere la valutazione di laboratorio. La prima prova vale il 40% del voto delle prove in itinere mentre la seconda prova vale il 60% del voto delle prove in itinere.
La prima prova conterrà solo esercizi mentre la seconda prova conterrà anche domande di teoria. La valutazione di laboratorio è un punteggio minore o uguale a 3 punti che valuta sia la partecipazione al laboratorio che il risultato di una prova di laboratorio che si tiene subito dopo la seconda prova in itinere. E' promosso chi ha un voto finale maggiore o uguale a 18 purchè in entrambe le prove si abbia un voto maggiore o uguale a 12. Si può rifare la prova in itinere peggiore ma solo al primo appello d'esame.

B) Esame: compito scritto su tutto il programma seguito da una discussione orale del compito.

Il giorno dell'esame eventuali studenti stranieri potranno avere il testo del compito tradotto in inglese, dietro richiesta preventiva di almeno 3 giorni. Agli studenti stranieri sarà possibile svolgere il compito in inglese e verrà indicata una adeguata bibliografia inglese. Gli studenti stranieri possono comunque prendere in considerazione il fatto che per la laurea magistrale è offerto a Milano nel primo semestre un corso in inglese con gli stessi contenuti.

Note sui contenuti del corso, esercizi e temi d'esame svolti sono a disposizionesu Beep

Per la parte di logica. Capitoli 1 e 2

Per la parte di logica. Capitolo 6

Per la parte di logica

Per la parte di algebra. Capitolo 1, fino a paragrafo 12; Capitolo 2, paragrafo 8; Capitolo 3; Capitolo 4, paragrafi1,2,5; Capitolo 5, paragrafi 1,2,3,4,5,6; Capitolo 11, paragrafi 1,2,3,8,9