Computer Science

LORENZO CARLUCCI
GIUSEPPE PERELLI

General Objectives:
The objective of the course is to introduce students to the fundamental results and methods of Mathematical Logic with a special attention to their applications in Computer Science.

Specific Objectives:
The specific objective of the course is twofold.
In the first place the course is meant to offer a rigorous knoweldge and an ability to apply those methods and results of Mathematical Logic that have numerous applications in many areas of Computer Science. In the second place the aim is to endow the student with a set of fundamental tools in the perspective of doing active research in theoretical Computer Science.

Knowledge and Understanding:
The course aims at endowing the student with a rigorous in-depth knowledge of the course topics through the study of poofs and the production of rigorous arguments in homework assignments. Particular attention is devoted to conceptual motivation, rigorous proofs and applicability of results and methods.

Applying knowledge and understanding:
The methods of Mathematical Logic play a fundamental role in many areas of Computer Science such as Complexity Theory, Database Theory, Artifical Intelligence. The aim of the course is to stimulate in the student the ability to apply the methods and the results in various contexts of Computer Science.

Autonomy of judgement:
Active participation to the course is encouraged. Autonomous judgement is exercised through homework assignments and problem-solving tasks.

Communication skills:
The student has the option to give a class presentation of a result as final exam in the form of an academic scientific talk.

Future learning abilities:
The methods of analysis and formalization acquired during the course can be fruitfully applied in many different contexts. The formalization and problem-solving exercise offered during the course strengthens the learning abilities and the capacity of acquiring new skills.

Knowledge and comprehension of some of the fundamental concepts, methods and results of Logic in Computer Science.
Ability in formalizing problems from various areas as logical problems. Ability to write rigorous proofs in the area of
Logic in Computer Science. Ability to navigate through current research in the area.

Basic notions about boolean connectives, familiarity with the informal concept of algorithm.

Fundamentals: predicate logic, models and structures. Theories. Definability, completeness, decidability, examples
of complete and decidable theories, quantifier elimination, isomorphism and elementary equivalence of structures.

Finite Model Theory: expressibility of queries in various logic. Methods for proving the non-expressibility of
queries, Ehrenfeucht-Fraissé games, Back-and-forth conditions, Gaifman locality, logical characterization of
complexity classes (Fagin's Theorem on NP).

Undecidability: undecidability of validity (Church's Theorem, Trakhtenbrot's Theorem), undecidability of arithmetical
truth, undefinability of arithmetical truth, Gödel's Incompleteness Theorems, Arithmetical Hierarchy, oracle computation,
Post's Theorem, theorems with computable instances and no computable solution (König, Ramsey, Hindman).

Miscellaneous: choice of more advanced research topics.

Handouts by the teacher.

1. Introduction to Mathematical Logic, Elliot Mendelson
2. A concise introduction to Mathematical Logic, W. Rautenberg
3. Elements of Finite Model Theory, L. Libkin

Lecture. Student participation is strongly encouraged through a dialogical approach that favours interaction.
Significant space is given to the in-depth comprehension of the new concepts through the use of examples and exercises.

Attendance is strongly encouraged. The student who wishes to give the exam without attending the course should contact the instructor before the beginning of the lectures in order to agree on an adequate study program.

Homework: 4/5 sets of homework assignments.

Final: either a written exam with problems or a class presentation of a research topic/paper.

Grading policy: Final grade is 40% homework and 60% final.

Presentation of a research paper or project.