MATHEMATICAL LOGIC

Course objectives

Given for granted some basic and indispensable goals (knowledge and understanding in the field of studies; ability to apply knowledge and understanding; capability of critical analysis; ability to communicate about what has been learned; skills to undertake further studies with some autonomy), the course intends to attain the following specific objectives: knolwedge of the fundamental results and methods of Mathematical Logic with a special attention to their applications in Artificial Intelligence.

Channel 1
NICOLA GALESI Lecturers' profile

Program - Frequency - Exams

Course program
1.Propositional Logic 1.1 Meaning and denotation 1.2 Connectives 1.3 Syntax 1.4 Semantic 2. Deductive systems for propositional logic 2.1 Sequent Calculus 2.1.1 Cut Elimination 2.2 Axiomatic systems 2.3 Resolution (Davis-Putnam) 2.4 Soundnsess and Completeness for propositional calculi 3. First order Logic 3.1 Syntax (Quantifiers, free and closed variable, subformulas, substitutions) 3.2 Semantic (satisfiabilty, models) 3.3 Normal forms (prenex and skolem) 3.4 Examples of first order languages 4. First order calculi 4.2 Sequent calculus 4.3 Axiomatic systems 4.4 Soundness and Completeness 4.5 Applications of di Completeness (Entscheidungsproblem, Infinte models, Compactness) 5. Gödel Incompleteness Theorems (intro) 5.3 I Incompleteness Theorem 5.4 II Incompleteness Theorem 6 Propositional Satisfiability and P vs NP problem (intro)
Prerequisites
No prerequisites
Books
1. Introduction to Mathematical Logic, Elliot Mendelson (https://www.karlin.mff.cuni.cz/~krajicek/mendelson.pdf)
Frequency
Presence is not registered.
Exam mode
The following aspects will be considered towards the final evaluation of the written exam: (1) the logic followed by the student for the solution of the problems; (2) the correctness and the soundness of the solutions of the problems; (3) how compatible are the solutions to the problems of the exams in accordance to the knowledge and the ability the student has received along all the lectures. (4) the ability to write correctly in Italian (or English if the exam is in English) A further oral exam is not mandatory and it is at teacher discretion or in some specific cases. The evaluation of the oral exam will consider the following aspects: (1) the ability to elaborate a correct and clear answer to the questions raised and (2) the readiness of the student in answering the questions (3) How the student is able to infer genuine new knowledge from the topics covered during the lectures.
Bibliography
2. A concise introduction to Mathematical Logic, W. Rautenberg (Springer 2006) 3. Logic and Structure, D. van Dalen (Springer 1994)
Lesson mode
Theory and practice classroom
  • Lesson code1022365
  • Academic year2025/2026
  • CoursePhilosophy and Artificial Intelligence
  • CurriculumSingle curriculum
  • Year2nd year
  • Semester1st semester
  • SSDMAT/01
  • CFU6