93283 - LOGICA PER L'INFORMATICA (9 CFU)

Scheda insegnamento

Anno Accademico 2022/2023

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à. È in grado di applicare processi di generalizzazione e istanziazione sia in matematica che in programmazione.

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.

 

In considerazione della tipologia di attività e dei metodi didattici adottati, la frequenza di questa attività formativa richiede la preventiva partecipazione di tutti gli studenti ai Moduli 1 e 2 di formazione sulla sicurezza nei luoghi di studio, [https://elearning-sicurezza.unibo.it/] in modalità e-learning.

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