Logic for computer science (2009/2010)

Course code
Name of lecturer
Luca Vigano'
Luca Vigano'
Number of ECTS credits allocated
Other available courses
Academic sector
Language of instruction
1st Semester dal Oct 1, 2009 al Jan 31, 2010.

Lesson timetable

1st Semester
Day Time Type Place Note
Monday 11:30 AM - 1:30 PM lesson Lecture Hall A  
Wednesday 8:30 AM - 10:30 AM lesson Lecture Hall D  

Learning outcomes

The mere existence of computer science depends on the capability of representing notions adequately and processing them through appropriate transformations of their representations. In other words, the elaboration of knowledge is based on the distinctions and relationship between semantics and syntax.

The main objective of this course is thus the introduction of the fundamental notions of symbolic logic: syntax, semantics, language and metalanguage, deductive systems, structure and representability.


Propositional logic: Syntax and semantics; deductive systems (introduce at least one of the following systems: natural deduction, sequent calculus, tableaux); soundness and completeness; functional completeness.

Predicate logic: Quantifiers; structures and semantics of first-order logic; equality; extensions of the deductive systems for quantifiers and equality; first-order mathematical theories; theorems of soundness and completeness; compactness theorem and Loewenheim-Skolem theorem; formalization of mathematical structures and representability; Peano arithmetics; statement of the incompleteness theorem.

Assessment methods and criteria

The examination consists of a written test that must be taken without the help of notes, books, or other documentation. The teacher may decide to replace the written test with an oral examination.