logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 085903 - LOGICA E ALGEBRA
Docente Nuccio Claudia
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - MI (358) INGEGNERIA INFORMATICAI1AEP085903 - LOGICA E ALGEBRA

Programma dettagliato e risultati di apprendimento attesi
Programma Dettagliato

Obiettivi

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.

 

Programma dettagliato

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, reticoli ed algebre di Boole (definizioni ed esempi).

 

4.2 Sottostrutture, criteri relativi.

 

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

 

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

 

Prerequisiti

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


Note Sulla Modalità di valutazione

La valutazione dello studente avviene attraverso esame o due prove in itinere. Per superare l'esame tramite le prove in itinere lo studente deve raggiungere la sufficienza complessiva e superare la soglia minima di punteggio fissata per ciascuna delle due prove. In occasione della seconda prova in itinere e del primo appello d'esame verrà proposto un esercizio sull'uso del theorem prover la cui valutazione sarà sommata al voto (se prossimo alla sufficienza) conseguito nelle prove in itinere o nell'esame.

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 specialistica è offerto nel primo semestre un corso in inglese con gli stessi contenuti.


Bibliografia
Risorsa bibliografica obbligatoriaNote ed esercizi Beep Polimi
Note:

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

Risorsa bibliografica facoltativaE. Mendelson, Introduzione alla logica matematica, Editore: Bollati Boringhieri, Anno edizione: 1972, ISBN: 9788833952840
Note:

Per la parte di logica. Capitoli 1 e 2

Risorsa bibliografica facoltativaA.Asperti, A.Ciabattoni, Logica a informatica, Editore: McGraw-Hill, Anno edizione: 1997, ISBN: 9788838607578
Note:

Per la parte di logica. Capitolo 6

Risorsa bibliografica facoltativaD. Mandrioli, P. Spoletini, Mathematical logic for computer science - an introduction, Editore: Esculapio. Progetto Leonardo, Anno edizione: 2010, ISBN: 9788874883738
Note:

Per la parte di logica

Risorsa bibliografica facoltativaA. Facchini, Algebra e matematica discreta, Editore: Zanichelli, Anno edizione: 2000, ISBN: 9788808097392
Risorsa bibliografica facoltativaM. Curzio, P. Longobardi, M. Maj, Lezioni di algebra, Editore: Liguori, Anno edizione: 1994, ISBN: 978-88-207-2228-9
Note:

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


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
32.0
esercitazione
20.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
27/09/2020