Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024

Logic anad Graphs

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
B0B01LGR Z,ZK 5 3P+2S Czech
Garant předmětu:
Marie Demlová
Lecturer:
Matěj Dostál, Alena Gollová
Tutor:
Matěj Dostál, Alena Gollová, Natalie Žukovec
Supervisor:
Department of Mathematics
Synopsis:

This course covers basics of mathematical logic and graph theory. Syntax and semantics of propositional and predicate logic are introduced. The importance of the notion of consequence and of the relationship between a formula and its model is stressed. Further, basic notions from graph theory are introduced.

Requirements:

None.

Syllabus of lectures:

Topics in propositional logic (approx. 4 weeks):

1. Formal language. The language of propositional logic.

2. Semantics and semantic entailment.

3. The resolution method in propositional logic.

4. Deriving conclusions (natural deduction).

Topics in predicate logic (approx. 4 weeks):

1. The language of predicate logic.

2. Semantics and semantic entailment in predicate logic.

3. The resolution method in predicate logic.

4. Reserve lecture.

Topics in graph theory (approx. 6 weeks):

1. Basic concepts of graph theory.

2. Trees and minimum spanning trees.

3. Acyclic graphs. Strong connectivity.

4. Euler graphs.

5. Colouring. Planar graphs.

6. Reserve lecture.

Syllabus of tutorials:

In the exercise classes students solve theoretical and algorithmic problems from logic and graph theory.

Students strenghten and extend their knowledge and skills obtained from the lectures.

Study Objective:

The aim of the course is to introduce students to the basics of mathematical logic and graph theory.

Study materials:

[1] M. Huth, M. Ryan: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004.

[2] J. A. Bondy, U. S. R. Murty: Graph theory with applications. Elsevier Science Ltd/North-Holland, 1976.

Note:
Further information:
https://math.fel.cvut.cz/en/people/gollova/lgr.html
Time-table for winter semester 2023/2024:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
roomT2:C4-365
Gollová A.
09:15–10:45
(lecture parallel1
parallel nr.101)

Dejvice
Cvičebna
roomT2:C4-365
Gollová A.
11:00–12:30
(lecture parallel1
parallel nr.102)

Dejvice
Cvičebna
roomT2:C4-363
Dostál M.
12:45–14:15
(lecture parallel1
parallel nr.107)

Dejvice
Cvicebna
Wed
roomT2:C4-365
Gollová A.
09:15–10:45
(lecture parallel1
parallel nr.106)

Dejvice
Cvičebna
roomT2:C4-365
Gollová A.
11:00–12:30
(lecture parallel1
parallel nr.104)

Dejvice
Cvičebna
Thu
roomT2:C4-78
Dostál M.
09:15–10:45
(lecture parallel1
parallel nr.103)

Dejvice
T2:C4-78
roomT2:C4-364
Dostál M.
11:00–12:30
(lecture parallel1
parallel nr.105)

Dejvice
Cvicebna
roomT2:C4-365
Gollová A.
16:15–17:45
(lecture parallel1
parallel nr.108)

Dejvice
Cvičebna
roomT2:C3-135
Gollová A.
14:30–16:00
(lecture parallel1)
Dejvice
T2:C3-135
Fri
roomT2:C3-135
Gollová A.
11:00–12:30
(lecture parallel1)
Dejvice
T2:C3-135
Time-table for summer semester 2023/2024:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
roomT2:D3-209
Dostál M.
11:00–12:30
(lecture parallel1)
Dejvice
T2:D3-209
roomT2:C3-51
Dostál M.
14:30–16:00
(lecture parallel1
parallel nr.101)

Dejvice
T2:C3-51
roomT2:C3-51
Dostál M.
12:45–14:15
(lecture parallel1
parallel nr.102)

Dejvice
T2:C3-51
Tue
roomT2:D3-209
Dostál M.
12:45–14:15
EVEN WEEK

(lecture parallel1)
Dejvice
T2:D3-209
roomT2:C4-459
Dostál M.
14:30–16:00
(lecture parallel1
parallel nr.111)

Dejvice
Laborator počítače
Wed
roomT2:A4-202b

14:30–16:00
(lecture parallel1
parallel nr.103)

Dejvice
Učebna
roomT2:A4-202b

16:15–17:45
(lecture parallel1
parallel nr.104)

Dejvice
Učebna
roomT2:A4-202b

18:00–19:30
(lecture parallel1
parallel nr.105)

Dejvice
Učebna
Thu
roomT2:C2-84
Žukovec N.
09:15–10:45
(lecture parallel1
parallel nr.112)

Dejvice
Ucebna
roomT2:C2-84
Žukovec N.
12:45–14:15
(lecture parallel1
parallel nr.106)

Dejvice
Ucebna
roomT2:C2-84
Žukovec N.
14:30–16:00
(lecture parallel1
parallel nr.107)

Dejvice
Ucebna
roomT2:A4-202a

16:15–17:45
(lecture parallel1
parallel nr.108)

Dejvice
Ucebna
Fri
roomT2:A4-202a

11:00–12:30
(lecture parallel1
parallel nr.110)

Dejvice
Ucebna
roomT2:A4-202a

12:45–14:15
(lecture parallel1
parallel nr.109)

Dejvice
Ucebna
The course is a part of the following study plans:
Data valid to 2023-11-30
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet4680706.html