73149 - LOGICA PER L'INFORMATICA (1)

Anno Accademico 2020/2021

Conoscenze e abilità da conseguire

Al termine del corso, lo studente conosce il linguaggio del calcolo proposizionale e della logica del prim'ordine. È in grado di scrivere e comprendere proposizioni logiche e di verificarne la validità.

Contenuti

PRIMO MODULO: LOGICA

  1. Paradossi e loro risoluzione. Applicazione dei paradossi per dimostrare risultati negativi in informatica.
  2. Cenni alla teoria assiomatica degli insiemi: ZF, relazioni, funzioni, quozienti, cardinalità. Teorema di Cantor.
  3. Linguaggi proposizionali: sintassi e semantica. Soddisfacibilità; equivalenze semantiche. Metodi sintattici: Risoluzione proposizionale e Deduzione Naturale. Correttezza e completezza.
  4. Linguaggi del prim'ordine. Predicati, termini, quantificatori. Sintassi. Variabili libere e vincolate. Interpretazioni. Semantica per un linguaggio predicativo. Soddisfacibilità e equivalenze semantiche.
  5. BNF per la definizione di grammatiche. Induzione strutturale e ricorsione strutturale.
  6. Metodi sintattici del prim'ordine: Deduzione naturale. Teorema di correttezza. Teorema di completezza. Teorema di compattezza.

 

SECONDO MODULO: ALGEBRA

  1. Generalizzazione, astrazione, instanziazione in matematica e informatica. Funzioni di ordine superiore.
  2. Cenni di algebra: semigruppi, monoidi, gruppi e loro applicazioni nella programmazione generica.

Testi/Bibliografia

  1. A. Asperti - A. Ciabattoni, Logica a informatica, McGraw Hill, 1997.
  2. Lucidi forniti dal docente.

Metodi didattici

Il corso si svolge nel primo semestre ed è articolato in lezioni frontali in aula ed esercitazioni settimanali svolte tramite didattica a distanza. Durante le lezioni frontali vengono trattati esaustivamente tutti gli argomenti del corso, fornendo dimostrazioni dettagliate della quasi totalità dei teoremi. Durante le esercitazioni di laboratorio viene chiesto allo studente di applicare quanto appreso a lezione alla dimostrazione di nuovi teoremi.

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento si baserà sull'analisi degli elaborati prodotti dagli studenti durante le esercitazioni in laboratorio e su un esame scritto. Lo studente che raggiunga la sufficienza nell'esame scritto potrà effettuare un orale integrativo opzionale sugli stessi argomenti per migliorare la valutazione. L'orale diventa obbligatorio per quegli studenti impossibilitati a frequentare l'attività di laboratorio.


L'attività di laboratorio è mirata all'apprendimento di strumenti di auto-verifica della capacità di produrre dimostrazioni matematiche rigorose. Viene utilizzato il software Matita.


L'esame scritto, della durata di tre ore, si articola in domande di teoria (definizioni, enunciati, dimostrazioni viste a lezione) e esercizi di ragionamento (produzione di nuove dimostrazioni e risoluzione di problemi).

Strumenti a supporto della didattica

I lucidi delle lezioni vengono resi disponibili tramite Web. Inoltre viene fornito il software Matita utilizzato nelle esercitazioni in laboratorio.

Orario di ricevimento

Consulta il sito web di Claudio Sacerdoti Coen