logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 085903 - LOGICA E ALGEBRA
Docente Möseneder Frajria Pierluigi
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) - CO (360) INGEGNERIA INFORMATICA*AZZZZ085903 - LOGICA E ALGEBRA

Obiettivi dell'insegnamento

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.


Risultati di apprendimento attesi

Descrittori di Dublino

Risultati di apprendimento attesi

 

Conoscenza e comprensione

 

  • Comprendere concetti chiave in matematica: nozioni di funzioni, relazioni e loro proprietà.

  • Conoscere le principali tecniche dimostrative.

  • Conoscere i principali formalismi logici.

  • Comprendere la nozione di sistema formale e di dimostrazione.

  • Conoscere le principali strutture algebriche e il concetto di omomorfismo e quoziente.

Capacità di applicare conoscenza e comprensione

  • Sapere applicare il linguaggio logico alla costruzione di specifiche di progetto per un sistema.

  • Capacità di traduzione da linguaggio naturale a linguaggi logici opportuni.

  • Capacità di modellare un problema in un opportuno linguaggio logico o algebrico.

  • Capacità di comprendere le nozioni algebriche di base (come l’aritmetica modulare) al fine di comprendere la matematica considerata in corsi più avanzati.

  • Capacità di comprendere tecniche dimostrative specifiche in ambito informatico, come la diagonalizzazione.

  • Saper comprendere il funzionamento di un theorem prover e aver le basi per saperlo progettare e utilizzare.

 

Autonomia di giudizio

  • Saper distinguere tra nozione di sintassi e semantica.

  • Saper valutare l’adeguatezza della descrizione e delle specifiche di un problema al fine di analizzare il processo di programmazione e progettazione di un sistema formale in modo rigoroso e non ambiguo.

  • Sviluppare maggior senso critico nel processo di formalizzazione di un problema.

 

Capacità di apprendimento

  • Avere le basi per comprendere concetti chiave e nozioni più avanzati di informatica.

  • Essere in grado di applicare le conoscenze acquisite in maniera sistematica e rigorosa a problemi complessi.

  • Sviluppare una forma mentis orientata al rigore di pensiero.

  • Capacità di astrazione.

 


Argomenti trattati

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.


Prerequisiti

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


Modalità di valutazione

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.

 

Modalità di verifica

Descrizione

 

Risultato di apprendimento perseguito

Prova scritta

  • risoluzione di problemi numerici

  • domande di carattere teorico a risposta aperta sugli argomenti del corso

1,2

1,2,3,5

 

Valutazione elaborato di laboratorio

  • valutazione di un elaborato relativo all’utilizzo di un theorem prover illustrato nel corso attraverso un’attività pratica.

2, 3, 5


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


Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
30:00
45:00
Esercitazione
16:00
24:00
Laboratorio Informatico
4:00
6:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
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
19/01/2021