University of Warsaw - Central Authentication System
Strona główna

Logics for computer scientists

General data

Course ID: 1000-217bLOG
Erasmus code / ISCED: 11.304 The subject classification code consists of three to five digits, where the first three represent the classification of the discipline according to the Discipline code list applicable to the Socrates/Erasmus program, the fourth (usually 0) - possible further specification of discipline information, the fifth - the degree of subject determined based on the year of study for which the subject is intended. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title: Logics for computer scientists
Name in Polish: Logika dla informatyków
Organizational unit: Faculty of Mathematics, Informatics, and Mechanics
Course groups: (in Polish) Grupa fundamentalnych przedmiotów teoretycznych dla informatyki magisterskiej
(in Polish) Grupa przedmiotów obowiązkowych dla informatyki magisterskiej-specj. Automaty, logika, złożoność
Elective courses (facultative) for Computer Science
Elective courses for Computer Science and Machine Learning
Obligatory courses for 1st grade 2nd stage Computer Science
ECTS credit allocation (and other scores): 6.00 Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.
Language: English
Type of course:

obligatory courses

Short description:

Introduction to propositional logic and first-order logic: element of model theory, elements of proof theory, role in computer science. Other logics important in computer science.

Full description:

1. Propositional logic.

2. First-order logic: definitions, logic in use, limitations of expressive power.

3. Proof theory: proof systems for propositional logic, proof systems for first-order logic, completeness theorem for first-order logic.

4. Model theory: compactness theorem, Skolem-Loewenheim theorem about cardinalities of models.

5. Arithmetic and G?del's incompleteness theorem.

6. Logics in computer science: three-valued logics, Codd's theorem about equivalence of first-order logic and relational algebra, decidability of logical theories

7. At least one of the following topics:

a. Logic of programs: PDL,

b. Propositional temporal logic LTL,

c. Intuitionistic logic,

d. Second order logic.

Bibliography:

http://www.mimuw.edu.pl/~urzy/calosc.pdf

Learning outcomes: (in Polish)

Wiedza: absolwent zna i rozumie

* w pogłębionym stopniu - wiedzę z działów matematyki niezbędnych do studiowania informatyki (logika i jej związki

z informatyką, teoria złożoności) [K_W01],

* w pogłębionym stopniu - rolę i znaczenie konstrukcji rozumowań matematycznych [K_W02].

Umiejętności: absolwent potrafi

* konstruować rozumowania matematyczne [K_U01],

* wyrażać problemy obliczeniowe w języku matematyki [K_U02],

* analizować pojęcia sformalizowane w wybranych systemach logicznych o znaczeniu informatycznym, tworzyć w

nich formalizacje zadanych pojęć bądź też dowodzić niemożności takiej formalizacji [K_U07].

Classes in period "Summer semester 2024/25" (past)

Time span: 2025-02-17 - 2025-06-08
Selected timetable range:
Go to timetable
Type of class:
Classes, 30 hours more information
Lab, 15 hours more information
Lecture, 30 hours more information
Coordinators: Filip Mazowiecki
Group instructors: Jacek Chrząszcz, Tomasz Gogacz, Tomáš Masařík, Filip Mazowiecki, Daria Walukiewicz-Chrząszcz
Students list: (inaccessible to you)
Credit: Examination

Classes in period "Summer semester 2025/26" (future)

Time span: 2026-02-16 - 2026-06-07
Selected timetable range:
Go to timetable
Type of class:
Classes, 30 hours more information
Lab, 15 hours more information
Lecture, 30 hours more information
Coordinators: Filip Mazowiecki
Group instructors: Jacek Chrząszcz, Tomasz Gogacz, Tomáš Masařík, Filip Mazowiecki, Daria Walukiewicz-Chrząszcz
Students list: (inaccessible to you)
Credit: Course - Examination
Lecture - Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
contact accessibility statement site map USOSweb 7.1.2.0-7 (2025-06-25)