logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 085903 - LOGICA E ALGEBRA
Docente Adami Stefania
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
I1TEP085903 - LOGICA E ALGEBRA
I3IEP085903 - LOGICA E ALGEBRA
II3EP085903 - LOGICA E ALGEBRA
IT1EP085903 - LOGICA E ALGEBRA
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*EP085903 - LOGICA E ALGEBRA

Obiettivi dell'insegnamento

Il corso ha lo scopo di avvicinare lo studente ai concetti di base della logica e dell'algebra. Alla fine del corso lo studente dovrebbe essere in grado di scrivere correttamente una formula 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 avere familiarità con le principali strutture algebriche. Vengono presentati i “linguaggi” dell’algebra e della logica focalizzando l'attenzione sui concetti di relazioni ed applicazioni e sugli aspetti semantico e sintattico delle logiche proposizionale e del I ordine. Inoltre, facendo uso della logica del I ordine, vengono introdotte le principali strutture algebriche e le nozioni di sottostruttura, relazione di congruenza, struttura quoziente, omomorfismi e isomorfismi fra strutture simili. Proprietà caratteristiche delle varie strutture sono messe in evidenza con esempi che intervengono in molte applicazioni.

La parte di logica sarà anche supportata da una breve attività di esercitazioni al computer con l’utilizzo del programma Spass per illustrare l’uso di un semplice theorem prover. 


Risultati di apprendimento attesi

Le lezioni e le esercitazioni consentiranno allo studente di 

conoscere e comprendere (DdD1):

  • i concetti chiave in matematica: nozioni di funzioni, relazioni e loro proprietà.
  • le principali tecniche dimostrative.
  • i principali formalismi logici.
  • la nozione di sistema formale e di dimostrazione.
  • le principali strutture algebriche e il concetto di omomorfismo e quoziente.

saper applicare le conoscenza acquisite al fine di (DdD2):

  • sapere applicare il linguaggio logico alla formalizzazione di alcuni problemi.
  • avere la capacità di tradurre da linguaggio naturale a linguaggi logici opportuni.
  • avere la capacità di modellare un problema in un opportuno linguaggio logico o algebrico.
  • avere la capacità di comprendere alcune nozioni algebriche di base (come l’aritmetica modulare) al fine di comprendere la matematica considerata in corsi più avanzati.
  • avere la capacità di comprendere alcune tecniche dimostrative specifiche in ambito informatico, come la diagonalizzazione.
  • avere la capacità di comprendere il funzionamento di un theorem prover e aver le basi per saperlo progettare e utilizzare.

ottenere un autonomia di giudizio (DdD3):

  • nel saper distinguere tra nozione di sintassi e semantica.
  • nel 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.
  • che permetta di sviluppare maggior senso critico nel processo di formalizzazione di un problema.

ed avere una capacità di apprendimento (DdD5):

  • che permetta di comprendere concetti chiave e nozioni più avanzati di informatica.
  • che permetta allo studente di sviluppare una forma mentis orientata al rigore di pensiero e migliorare il processo di astrazione di un problema. 

Il docente si attende una comprensione non limitata all'enunciazione di definizioni e risultati e alla risoluzione di esercizi standard, ma critica ed in grado di distinguere le diverse situazioni, e di compiere scelte consapevoli, giustificando i procedimenti seguiti. Si attende inoltre un'adeguata correttezza nei calcoli e un'esposizione ben argomentata nella risoluzione dei problemi proposti. 


Argomenti trattati
  1. RELAZIONI ED APPLICAZIONI

1.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à.

1.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.

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

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

  1. LOGICA PROPOSIZIONALE

2.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.

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

  1. 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, false in un'interpretazione. Formule logicamente valide. Forma normale prenessa, forma 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à.

  1. STRUTTURE ALGEBRICHE

4.1 Le principali strutture algebriche: semigruppi, monoidi, gruppi, anelli, corpi, campi (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.


Modalità di valutazione

La valutazione dello studente avviene attraverso un esame scritto. In occasione dei primi due appelli di gennaio e febbraio verrà proposto un esercizio sulla formalizzazione di un problema nella sintassi del theorem prover usato durante l’esercitazione al computer il cui punteggio sarà aggiunto al voto conseguito nella prova d’esame se quest’ultimo risulta sufficiente o prossimo alla sufficienza.

Il giorno dell'esame eventuali studenti stranieri potranno avere il testo del compito tradotto in inglese, dietro richiesta preventiva di almeno sei 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. 

   Modalità di verifica

   

   Descrizione

 

Risultato di apprendimento perseguito (DdD)

Prova scritta

risoluzione di problemi numerici

 

esercizi di tipo progettuale

 

 domande di carattere teorico a risposta aperta sugli argomenti del corso

 

1,2

 

1,2,3,5 

 

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 (solo per i primi due appelli).

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 obbligatoriaA. Frigeri, S. Adami, A. Cherubini , C. Nuccio, L.Mauri, E. Rodaro, Logica e algebra, esercizi svolti e richiami di teoria, Editore: Maggioli Editore, Anno edizione: 2018, ISBN: 978-88-916-2986-9
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 facoltativaLuigia Carlucci Aiello, Fiora Pirri, Strutture, logica, linguaggi, Editore: Pearson, ISBN: 9788891907844
Risorsa bibliografica facoltativaA. Facchini, Algebra e matematica discreta, Editore: Zanichelli, Anno edizione: 2000, ISBN: 9788808097392
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 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
48:45
Esercitazione
16:00
26:15
Laboratorio Informatico
4:00
0: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
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
27/09/2020