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

Logics for computer scientists

General data

Course ID: 1000-217bLOG
Erasmus code / ISCED: 11.304 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (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: 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 2023/24" (in progress)

Time span: 2024-02-19 - 2024-06-16
Selected timetable range:
Navigate to timetable
Type of class:
Classes, 30 hours more information
Lab, 15 hours more information
Lecture, 30 hours more information
Coordinators: Jacek Chrząszcz, Jerzy Tyszkiewicz
Group instructors: Jacek Chrząszcz, Lorenzo Clemente, Michał Godziszewski, Tomáš Masařík, Filip Mazowiecki, Jerzy Tyszkiewicz, Daria Walukiewicz-Chrząszcz
Students list: (inaccessible to you)
Examination: Examination

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

Time span: 2025-02-17 - 2025-06-08
Selected timetable range:
Navigate 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)
Examination: 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 USOSweb 7.0.3.0 (2024-03-22)