Logic anad Graphs

B232 - Summer 23/24
You don't have access to the course
B161 - Winter 16/17 B171 - Winter 17/18 B181 - Winter 18/19 B191 - Winter 19/20 B192 - Summer 19/20 B201 - Winter 20/21 B202 - Summer 20/21 B211 - Winter 21/22 B212 - Summer 21/22 B221 - Winter 22/23 B222 - Summer 22/23 B231 - Winter 23/24 B232 - Summer 23/24

Logic anad Graphs - B0B01LGR

Student survey results
Credits 5
Semesters Both
Completion Assessment + Examination
Language of teaching Czech
Extent of teaching 3P+2S
Annotation
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.
Study targets
The aim of the course is to introduce students to the basics of mathematical logic and graph theory.
Course outlines
Topics in propositional logic (approx. 4 weeks):
Formal language. The language of propositional logic.
Semantics and semantic entailment.
Deriving conclusions (natural deduction).

Topics in predicate logic (approx. 4 weeks):
The language of predicate logic.
Semantics and semantic entailment in predicate logic.
Deriving conclusions (natural deduction).

Topics in graph theory (approx. 6 weeks):
Basic concepts of graph theory.
Trees and minimum spanning trees.
Acyclic graphs. Strong connectivity.
Euler graphs.
Colouring. Planar graphs.
Exercises outlines
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.
Literature
[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.
Requirements
None.