Skip to main content
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
e-Learning - UNIMIB
  • Home
  • My Media
  • More
Listen to this page using ReadSpeaker
English ‎(en)‎
English ‎(en)‎ Italiano ‎(it)‎
 Log in
e-Learning - UNIMIB
Home My Media
Percorso della pagina
  1. Science
  2. Master Degree
  3. Informatica [F1802Q - F1801Q]
  4. Courses
  5. A.A. 2025-2026
  6. 1st year
  1. Logical Foundations of Computer Science
  2. Summary
Insegnamento Course full name
Logical Foundations of Computer Science
Course ID number
2526-1-F1802Q122
Course summary SYLLABUS

Course Syllabus

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

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.

Export

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.

Enter

Key information

Field of research
INF/01
ECTS
6
Term
Second semester
Activity type
Mandatory to be chosen
Course Length (Hours)
48
Degree Course Type
2-year Master Degreee
Language
Italian

Staff

    Teacher

  • GF
    Guido Giuseppe Fiorino
  • RP
    Rafael Penaloza Nyssen

Students' opinion

View previous A.Y. opinion

Bibliography

Find the books for this course in the Library

Enrolment methods

Manual enrolments

You are not logged in. (Log in)
Policies
Get the mobile app
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy policy
  • Accessibility
  • Statistics