Corso di laurea in Informatica

Conoscenza delle basi della matematica della scuola superiore: in particolare le operazioni aritmetiche di base, le proprietà delle potenze, le equazioni di primo e secondo grado. Conoscenza della terminologia di base relativa alle parti del discorso: nomi, verbi, proposizioni, aggettivi. Conoscenza della logica proposizionale.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): sono utili le competenze acquisite in Fondamenti dell'Informatica (INF0348) su logica proposizionale e insiemistica di base.

Insegnamenti che utilizzano argomenti sviluppati nel corso in forma più o meno approfondita sono: Algoritmi e strutture dati (MFN0597), Basi di Dati (MFN 0602), Calcolabilità e complessità (INF0090), Linguaggi formali e traduttori (MFN0603), Linguaggi e paradigmi di programmazione (MFN1354), Logica per l'informatica (INF0003), Metodi formali dell'informatica (MFN0633), Sistemi intelligenti (MFN0607).

L’insegnamento si propone di fornire allo studente le basi della logica matematica, con particolare riguardo per i suoi aspetti più rilevanti per la formazione di base di un informatico, tra cui una adeguata familiarità con le strutture algebriche e la semantica di Tarski per la logica del primo ordine. Questi contenuti fanno parte degli Obiettivi formativi specifici del CdS in Informatica (L31), in particolare sono tra quelli relativi all'area di Matematica di base.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE. Conoscenza delle nozioni fondamentali di insiemistica e loro utilizzo in contesti logici o informatici. Conoscenza delle formulazioni classiche del principio di induzione e suo utilizzo in ambito informatico. Conoscenza della struttura delle formule del primo ordine. Conoscenza delle definizioni delle principali nozioni semantiche relative alla logica del primo ordine (validità, conseguenza logica)

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE. Capacità di riconoscere le principali tecniche di dimostrazione (diretta, per assurdo, per contrapposizione, per casi) in semplici dimostrazioni di proposizioni relative a strutture algebriche e relazionali. Dovrà essere in grado di utilizzare le principali forme del principio di induzione (ordinaria, forte, principio del minimo) in semplici dimostrazioni aritmetiche o relative alla sintassi formale dei linguaggi proposizionali e del prim’ordine. Dovrà essere in grado di analizzare sia sintatticamente che semanticamente le formule proposizionali, anche mediante l'uso di tavole di verità. Dovrà dimostrare di essere in grado di formalizzare mediante formule logiche semplici asserzioni formulate in italiano. Dovrà essere in grado di valutare la validità o meno di semplici formule del prim'ordine in strutture algebriche in accordo con le regole della semantica di Tarski e dovrà essere in grado di stabilire quando una formula non è conseguenza logica di altre formule provvedendo semplici controesempi. Dovrà inoltre sapere determinare l'insieme di verità di una data formula del prim'ordine in una struttura assegnata.

AUTONOMIA DI GIUDIZIO. Acquisizione dei criteri di base per riconoscere la corretta impostazione di una semplice dimostrazione.

ABILITÀ COMUNICATIVE. Acquisizione degli elementi della terminologia logica di base.

CAPACITÀ DI APPRENDIMENTO. Acquisizione di capacità autonome di apprendimento e di autovalutazione della propria preparazione, teorica e pratica.

Ripasso sulle tecniche di dimostrazione:

• Dimostrazione diretta, per assurdo, per contrapposizione;

• Connettivi logici e loro significato in termini di condizioni di verità;

• Tavole di verità e conseguenza logica tra proposizioni.

 

Ripasso su insiemistica di base:

• Insiemi, Relazioni, Funzioni

• Operazioni infinitarie: unioni e intersezioni, prodotti e somme, con le principali proprietà. 

 

Il principio di induzione:

• Forma ordinaria e forte del principio di induzione;

• Principio del minimo;

• Equivalenza tra forme del principio di induzione;

• Induzione strutturale;

• Ricorsione.

 

Formalizzazione:

• Linguaggi proposizionali e del prim’ordine: termini, quantificatori, alfabeto non logico, formule;

• Schemi di traduzione da linguaggio naturale in linguaggi del prim’ordine (condizione sufficiente, necessaria, per tutti gli n abbastanza grandi, ci sono n arbitrariamente grandi,…).

 

Semantica della Logica del primo ordine:

• Regole della semantica di Tarski per formule del primo ordine: esempi, e definizioni;

• Conseguenza logica tra formule del primo ordine: definizioni e costruzione di contro-esempi.

 

Strutture algebriche:

 • ordini parziali, alberi finiti, reticoli, algebre di Boole: proprietà di base e formalizzazione al primo ordine. 

 

Il corso sarà svolto esclusivamente in presenza, con lezioni frontali nelle aule e orari indicati sul sito del Dipartimento di Informatica. 

Le prove di esame sono scritte, a meno di richiesta da parte dei docenti di esame orale come integrazione della prova scritta. Le domande dello scritto e dell'eventuale orale possono riguardare sia la teoria che lo svolgimento di esercizi. L’esito dell’esame è espresso in trentesimi. L'eventuale orale potrà contare fino ad un totale di 15 punti.

Tutto il materiale utilizzato durante le lezioni frontali è disponibile sulla pagina Moodle del corso, e resa disponibile di volta in volta seguendo l’evolversi dell’insegnamento.