Logic anad Graphs
Code  Completion  Credits  Range  Language 

B0B01LGR  Z,ZK  5  3P+2S  Czech 
 Lecturer:
 Matěj Dostál
 Tutor:
 Matěj Dostál, Anna Kalousová
 Supervisor:
 Department of Mathematics
 Synopsis:

This course covers basics of mathematical logic and graph theory. Syntax and sematics of propositional and predicate logic is introduced. Stress is put on understanding of the notion of semantic consequent of sets of formulas. The relationship between a formula and its model and rezolution methods (both in propositional and predicate logic) are dealt with. Further, basic notions from graph theory are introduced.
 Requirements:

None.
 Syllabus of lectures:

1. Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula.
2. Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus.
3. Semantic consequence. The rezolution method in propositionl 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.
 Syllabus of tutorials:

1. Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula.
2. Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus.
3. Semantic consequence. The rezolution method in propositionl 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.
 Study Objective:

The aim of the course is to introduce students with basis of mathematical logic and graph theory.
 Study materials:

[4] Hodel, R. E.: An Introduction to Mathematical Logic, 2013, ISBN13 9780486497853
[5] Diestel, R.: Graph Theory, SpringerVerlag, 4th edition, 2010, ISBN 9783642142789
 Note:
 Further information:
 http://math.feld.cvut.cz/dostamat/teaching/lgr1819.htm http://math.feld.cvut.cz/gollova/lgr.html
 Timetable for winter semester 2019/2020:

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 Fri Thu Fri  Timetable for summer semester 2019/2020:
 Timetable is not available yet
 The course is a part of the following study plans:

 Cybernetics and Robotics 2016 (compulsory course in the program)
 Open Informatics  Computer Science 2016 (compulsory course in the program)
 Open Informatics  Internet of Things 2016 (compulsory course in the program)
 Open Informatics  Software 2016 (compulsory course in the program)
 Open Informatics  Computer Games and Graphics 2016 (compulsory course in the program)
 Open Informatics (compulsory course in the program)
 Medical electronics and bioinformatics (compulsory elective course)
 Open Informatics (compulsory course in the program)
 Open Informatics  Artificial Intelligence and Computer Science 2018 (compulsory course in the program)
 Open Informatics  Internet of Things 2018 (compulsory course in the program)
 Open Informatics  Software 2018 (compulsory course in the program)
 Open Informatics  Computer Games and Graphics 2018 (compulsory course in the program)