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. 

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. 

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.

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

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

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

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

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. 

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