Počet kreditů 5
Vyučováno v Winter and summer
Rozsah výuky 3P+2S
Garant předmětu

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 andof the relationship between a formula and its model is stressed, Further, basic notions from graph theory are introduced.


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

1. Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfyable formula.
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 rezolution 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. Plannar graphs.

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.

[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.

Rozvrh předmětu