Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2021/2022

Logic anad Graphs

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
B0B01LGR Z,ZK 5 3P+2S Czech
Lecturer:
Alena Gollová, Matěj Dostál
Tutor:
Alena Gollová, Matěj Dostál, Vojtěch Štěpančík
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 semantic 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:

1. Syntax and semantics of propositional logic, formulas, truth valuations, tautologies, contradictions, satisfiable formulas.

2. Tautological equivalence of two formulas. CNF and DNF, Boolean calculus.

3. Semantic consequence. The resolution method in propositional logic.

4. Syntax of predicate logic, a sentence, an open formula.

5. Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence.

6. The resolution method in predicate logic.

7. Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness.

8. Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees.

9.Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges.

10. Euler graphs and their applications.

11. Hamiltonian graphs and their applications.

12. Independent sets, cliques, vertex and edge cover, Graph coloring.

13. Planar graphs.

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://cw.fel.cvut.cz/b212/courses/b0b01lgr/
Time-table for winter semester 2021/2022:
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:A4-202b
Gollová A.
09:15–10:45
(lecture parallel1
parallel nr.101)

Dejvice
Učebna
roomT2:A4-202b
Gollová A.
11:00–12:30
(lecture parallel1
parallel nr.102)

Dejvice
Učebna
roomT2:C4-363
Gollová A.
12:45–14:15
(lecture parallel1
parallel nr.107)

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

Dejvice
Učebna
roomT2:A4-202b
Gollová A.
11:00–12:30
(lecture parallel1
parallel nr.104)

Dejvice
Uč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
roomKN:E-128

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

Karlovo nám.
Cvičebna K3
roomT2:C3-135
Gollová A.
14:30–16:00
(lecture parallel1)
Dejvice
T2:C3-135
roomKN:E-107
Gollová A.
14:30–16:00
(lecture parallel1)
Karlovo nám.
Zengerova posluchárna K1
Fri
roomT2:D3-309
Gollová A.
11:00–12:30
ODD WEEK

(lecture parallel1)
Dejvice
T2:D3-309
Time-table for summer semester 2021/2022:
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

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

Dejvice
T2:C3-51
roomT2:C3-51

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
Wed
roomT2:A4-202b
Gollová A.
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:A4-202a
Dostál M.
12:45–14:15
(lecture parallel1
parallel nr.106)

Dejvice
Ucebna
roomT2:A4-202a
Štěpančík V.
14:30–16:00
(lecture parallel1
parallel nr.107)

Dejvice
Ucebna
roomT2:A4-202a
Štěpančík V.
16:15–17:45
(lecture parallel1
parallel nr.108)

Dejvice
Ucebna
Fri
roomT2:A4-202a
Gollová A.
11:00–12:30
(lecture parallel1
parallel nr.110)

Dejvice
Ucebna
roomT2:A4-202a
Gollová A.
12:45–14:15
(lecture parallel1
parallel nr.109)

Dejvice
Ucebna
The course is a part of the following study plans:
Data valid to 2022-08-15
For updated information see http://bilakniha.cvut.cz/en/predmet4680706.html