Vai al contenuto principale
Se prosegui nella navigazione del sito, ne accetti le politiche:
  • Condizioni di utilizzo e trattamento dei dati
Prosegui
x
e-Learning - UNIMIB
  • Home
  • My Media
  • Altro
Ascolta questa pagina con ReadSpeaker
Italiano ‎(it)‎
English ‎(en)‎ Italiano ‎(it)‎
 Login
e-Learning - UNIMIB
Home My Media
Percorso della pagina
  1. Area di Scienze
  2. Corso di Laurea Magistrale
  3. Informatica [F1802Q - F1801Q]
  4. Insegnamenti
  5. A.A. 2025-2026
  6. 1° anno
  1. Fondamenti Logico Matematici dell'Informatica
  2. Introduzione
Insegnamento Titolo del corso
Fondamenti Logico Matematici dell'Informatica
Codice identificativo del corso
2526-1-F1802Q122
Descrizione del corso SYLLABUS

Syllabus del corso

  • Italiano ‎(it)‎
  • English ‎(en)‎
Esporta

Obiettivi

L'obiettivo dell'insegnamento è quello di introdurre i concetti fondamentali che legano la logica alla scienza dei calcolatori così che lo studente possa comprendere gli sviluppi moderni della logica computazionale.

Conoscenza e comprensione: lo studente conoscerà il concetto di Isomorfismo Curry-Howard e come esso si lega alla programmazione funzionale e alla logica intuzionista nell'ambito della correttezza dei programmi. Si introdurranno le logiche modali e si mostrerà come essere si legano alla rappresentazione della conoscenza.

Conoscenza e capacità di comprensione applicate: lo studente sarà in grado di scrivere funzioni in lambda calcolo, svolgere esercizi di tipizzazione di funzioni nell'ambito della correttezza dei programmi, stabilire la validità intuizionista di una formula che rappresenta una specifica ed estrarre dalla dimostrazione un programma in lambda calcolo. Lo studente sarà in grado di stabilire la soddisfacibilità di formule modali e modellare problemi scrivendo formule modali.

Capacità critiche di giudizio: saper scegliere tra diverse rappresentazioni della stessa funzione o della stessa tipizzazione; saper valutare divese formule che rappresentano la stessa conoscenza;

capacità di comunicare: saper definire correttamente i termini introdotti e distinguere cosa catturano le diverse definizioni date; enunciare anche con parole proprie ma in modo matematicamente corretto i teoremi principali mettondone in evidenza il significato;

capacità di proseguire lo studio in modo autonomo: essere in grado di cogliere che i meccanismi introdotti sono istanziabili anche ai linguaggi non funzionali; generalizzare la capacità di usare gli strumenti logici anche su logiche modali non viste la lezione e selezionare il framework logico più adatto per affrontare un problema nuovo.

Contenuti sintetici

  1. Inquadramento storico e connessione con i contenuti degli insegnamenti Linguaggi di Programmazione e Linguaggi e Computabilità;
  2. Introduzione all'Isomorfismo Curry-Howard;
  3. Fondamenti di Logica Classica e Logica Intuizionista;
  4. Logiche Modali e Logiche Descrittive.

Programma esteso

  1. Illustremo come logica e computazione sono connessi partendo dai concetti di programmazione funzionale e teoria della ricorsività illustrati al secondo anno della Laurea Triennale. Questo ci permetterà di introdurre il linguaggio funzionale noto come Lambda Calcolo ed il concetto di Tipo i quali hanno un ruolo chiave nella correttezza dei programmi;
  2. dal punto precedente arriveremo ad introdurre il concetto di Isomorfismo Curry-Howard noto anche come paradigma Propositions as Types che ha grande importanza nei linguaggi funzionali tipati;
  3. i precedenti punti oltre ad introdurre aspetti tecnici chiariscono le motivazioni per cui in informatica i concetti logici hanno grande importanza e rendono logica e computazione due concetti strettamente legati. In particolare al termine del punto 2 avremo motivato l'importanza della logica Intuizionista in informatica. Saremo quindi pronti a presentare sintassi, semantica e sistemi di dimostrazione per la logica Classica e successivamente per la logica Intuizionista;
  4. le logiche modali sono un'ampia famiglia di logiche oggi ampiamente usate in informatica per applicazioni che vanno dalla verifica di sistemi formali, all'analisi di giochi, alla rappresentazione di sistemi di agenti. Studieremo le proprietà base di queste logiche per poi concentrarci sulle logiche descrittive;
  5. dal punto di vista formale, le logiche descrittive sono varianti delle logiche modali. Cambiano, invece, dal punto di vista applicativo: le logiche descrittive sono utilizzate per rappresentare la conoscenza e ragionare in sistemi intelligenti. In questo punto studieremo le tecniche di ragionamento di questi linguaggi e il loro uso in Intelligenza Artificiale.

Prerequisiti

Nozioni base dagli insegnamenti dei primi due anni della laurea Triennale in Informatica;

Modalità didattica

TIPOLOGIA DI INSEGNAMENTO: 24 lezioni da 2 ore svolte in modalità erogativa in presenza.

Materiale didattico

Il sito di elearning verrà utilizzato per distribuire materiale ad-hoc.

Open Logic Project è un progetto collaborativo che riunisce in modo organico materiali relativi alla logica matematica insegnata nei corsi di filosofia. Contiene tutti gli argomenti trattati nell'insegnamento e può essere un buon riferimento .

Circa il materiale standard, purtroppo non esiste un unico libro che copra gli argomenti dell'insegnamento.
I seguenti libri ed articoli vengono suggeriti perchè in possesso della nostra biblioteca e/o scaricabili gratuitamente:

  1. Dirk van Dalen. Logic and structure (3. ed.). Universitext. Springer, 1994. Di interesse i capitoli su logica classica e intuizionista;
  2. Philip Wadler.Propositions as types. Commun. ACM, 58(12):75–84, 2015. Articolo divulgativo;
  3. Morten Heine Sörensen and Pawel Urzyczyn. Lectures on the Curry-Howard isomorphism. Elsevier, 2006. Testo avanzato che copre i punti da 1 a 3 del programma.
  4. Markus Krötzsch, Frantisek Simancik, Ian Horrocks. A Description Logic Primer. https://arxiv.org/abs/1201.4089 Breve introduzione alle logiche descrittive.

Periodo di erogazione dell'insegnamento

Secondo semestre;

Modalità di verifica del profitto e valutazione

  • Solo prova finale (non ci sono prove in itinere);
  • solo prova orale, che può svolgersi in una delle due seguenti modalità:
    1. COLLOQUIO SUGLI ARGOMENTI SVOLTI A LEZIONE;
    2. COLLOQUIO SU ARGOMENTI DI APPROFONDIMENTO NON TRATTATI A LEZIONE;
  • per entrambe le tipologie di prova la valutazione riguarda la conoscenza degli argomenti, compresa la capacità di rispondere a domande e svolgere esercizi, chiarezza espositiva e rigore matematico nell'esposizione.

Orario di ricevimento

Per appuntamento via email.

Esporta

Aims

In this course we introduce the foundations of logic in order to explain the notion of computation. Our aim is to allow the student to manage the recent achievements of logic in computer science.

Knowledge and understanding: The student will understand the concept of the Curry-Howard isomorphism and how it relates to functional programming and intuitionistic logic in the context of program correctness. Modal logics will be introduced, and it will be shown how they relate to the representation of knowledge.

Applying knowledge and understanding: The student will be able to write functions in lambda calculus, carry out type-checking exercises for functions in the context of program correctness, determine the intuitionistic validity of a formula representing a specification, and extract a lambda calculus program from the proof. The student will also be able to determine the satisfiability of modal formulas and model problems by writing modal formulas.

Making judgements: Ability to choose between different representations of the same function or of the same typing; ability to evaluate different formulas that represent the same knowledge.

communication skills: Ability to correctly define the introduced terms and to distinguish what each given definition captures; ability to state the main theorems, even in one’s own words, while maintaining mathematical accuracy and highlighting their meaning.

learning skills: Ability to recognize that the introduced mechanisms can also be instantiated in non-functional programming languages; ability to generalize the use of logical tools to modal logics not covered in the course, and to select the most appropriate logical framework for addressing a new problem.

Contents

  1. Historical overview and connections with the courses Programming Languages and
    Languages and Computability

  2. The Curry-Howard Isomorphism or propositions as types paradigm;

  3. Foundations of Classical and Intuitionistic logics;

  4. Modal and Description Logics.

Detailed program

  1. Starting from functional programming and recursive theory, we present the intimate relationships between logic and computation. This motivates a brief introduction of the functional language known as Lambda Calculus and the notion of Type: both have an important role in the framework of program correctness;
  2. previous point motivates the introduction of the Curry-Howard Isomorphism, also known as Propositions as types paradigm that is theoretically important both in typed functional languages and in program correctness;
  3. previous points are the main motivations to study logic in computer science. It will be clear the importance of Intuitionistic logic in computer science. Thus we start to study Classical and Intuitionistic logic by introducing the key points: syntax, semantics and proof systems;
  4. Modal logics are widely used in computer science for applications ranging from formal verification, to game analysis, to multi-agent system representation. We will study the basic properties of these logics to focus later on description logics;
  5. from a formal point of view, description logics are variants of modal logics. They differ from the application point of view: description logics are used to represent knowledge and reason in intelligent systems. We will study the reasoning techniques associated to these languages, and their use in Artificial Intelligence.

Prerequisites

Basic notions from first and second year of Bachelor Degree in Informatica;

Teaching form

Teaching format: 24 lessons of 2 hours each in-person.

Textbook and teaching resource

Open Logic Project is a collection of teaching materials on mathematical logic used in logic courses as taught in many philosophy departments.
Open Logic contains the topics of the course and it can be a good reference.

As regards standard books, there is no a single book covering all points of the course.
The following books and papers are owned by our library and/or are freely downloadable:

  1. Dirk van Dalen. Logic and structure (3. ed.). Universitext. Springer, 1994. It contains material related to Classical and Intuitionistic logics (point 3 of the program);
  2. Philip Wadler.Propositions as types. Commun. ACM, 58(12):75–84, 2015. non-technical paper;
  3. Morten Heine Sörensen and Pawel Urzyczyn. Lectures on the Curry-Howard isomorphism. Elsevier, 2006. Advanced book, technical, contains points 1-3 of the program;
  4. Markus Krötzsch, Frantisek Simancik, Ian Horrocks. A Description Logic Primer. https://arxiv.org/abs/1201.4089 Brief introduction to description logics.

Semester

Second semester.

Assessment method

  • Final exam (no intermediate exam);

  • oral exam. Two possible choices:

    1. oral exam on the contents of the course;
    2. oral exam on deeper topics not considered in the program of the course.
  • In both cases we evaluate the knowledge of the topics, included the ability to answer to questions and solve exercises, clarity of presentation and mathematical precision.

Office hours

On request, scheduled via email.

Entra

Scheda del corso

Settore disciplinare
INF/01
CFU
6
Periodo
Secondo Semestre
Tipo di attività
Obbligatorio a scelta
Ore
48
Tipologia CdS
Laurea Magistrale
Lingua
Italiano

Staff

    Docente

  • GF
    Guido Giuseppe Fiorino
  • RP
    Rafael Penaloza Nyssen

Opinione studenti

Vedi valutazione del precedente anno accademico

Bibliografia

Trova i libri per questo corso nella Biblioteca di Ateneo

Metodi di iscrizione

Iscrizione manuale

Non sei collegato. (Login)
Politiche
Ottieni l'app mobile
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy
  • Accessibilità
  • Statistiche