Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2019/2020

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:
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, ISBN-13 978-0-486-49785-3

[5] Diestel, R.: Graph Theory, Springer-Verlag, 4th edition, 2010, ISBN 978-3-642-14278-9

Note:
Further information:
http://math.feld.cvut.cz/dostamat/teaching/lgr1819.htm http://math.feld.cvut.cz/gollova/lgr.html
Time-table 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
roomT2:A4-202b
Kalousová A.
09:15–10:45
(lecture parallel1
parallel nr.101)

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

Dejvice
Učebna
roomT2:C4-363

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

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

Dejvice
Učebna
roomT2:A4-202b
Kalousová 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
Posluchárna
roomT2:C4-78
Dostál M.
11:00–12:30
(lecture parallel1
parallel nr.105)

Dejvice
Posluchárna
roomKN:E-128

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

Karlovo nám.
Cvičebna K3
roomKN:E-107
Dostál M.
14:30–16:00
(lecture parallel1)
Karlovo nám.
Zengerova posluchárna K1
Fri
roomT2:D3-309
Dostál M.
11:00–12:30
ODD WEEK

(lecture parallel1)
Dejvice
Posluchárna
Time-table for summer semester 2019/2020:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2019-09-17
For updated information see http://bilakniha.cvut.cz/en/predmet4680706.html