Logic and Graph Theory

Přednášející:

Marie Demlová, Pavel Pták, Jiří Velebil

Cvičící:

Marie Demlová, Pavel Pták, Jiří Velebil

Předmět zajišťuje:

katedra matematiky

Anotace:

The course covers basics of logic and theory of graphs. Propositional logic contains: truth validation, semantical consequence and tautological equivalence of formulas, CNF and DNF, complete systems of logical connectives, and resolution method in propositional logic. In predicate logic the stress is put on formalization of sentences as formulas of predicate logic, and resolution method in predicate logic. Next topic is an introduction to the theory of graphs and its applications. It covers connectivity, strong connectivity, trees and spanning trees, Euler?s graphs, Hamilton?s graphs, independent sets, and colourings.

Požadavky:

Discrete Mathematics, Linear Algebra

Osnova přednášek:

1.Formulas of propositional logic, truth validation, tautology, contradiction, satisfiable formulas.

2.Semantical consequence and tautological equivalence in propositional logic.

3.CNF and DNF, Boolean calculus.

4.Resolution method in propositional logic.

5.Predicate logic, syntactically correct formulas

6.Interpretation, sematical consequence and tautological equivalence.

7.Resilution method in predicate logic.

8.Directed and undirected graphs.

9.Connectivity, trees, spanning trees.

10.Strong connectivity, acyclic graphs.

11.Euler?s graphs and their application.

12.Hamilton?s graphs and their application.

13.Independent sets, cliques in graphs.

14.Colourings.

Osnova cvičení:

1.Formulas of propositional logic, truth validation, tautology, contradiction, satisfiable formulas.

2.Semantical consequence and tautological equivalence in propositional logic.

3.CNF and DNF, Boolean calculus.

4.Resolution method in propositional logic.

5.Predicate logic, syntactically correct formulas

6.Interpretation, sematical consequence and tautological equivalence.

7.Resilution method in predicate logic.

8.Directed and undirected graphs.

9.Connectivity, trees, spanning trees.

10.Strong connectivity, acyclic graphs.

11.Euler?s graphs and their application.

12.Hamilton?s graphs and their application.

13.Independent sets, cliques in graphs.

14.Colourings.

Cíle studia:

Studijní materiály:

[1] M. Demlová: Mathematical Logic. ČVUT Praha, 1999.

[2] R. Diestel: Graph Theory, Springer-Verlag, 1997

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+6s

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	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
Po	místnost Z4:B2-326 Pták P. 13:30–16:00 (přednášková par. 1) Zikova ulice Konzultační místnostmístnost Z4:B2-326 Pták P. 16:15–17:45 (přednášková par. 1 paralelka 101) Zikova ulice Konzultační místnost
Út
St
Čt
Pá

Předmět je součástí následujících studijních plánů:

• Cybernetics and Robotics - Robotics (povinný předmět programu)
• Cybernetics and Robotics - Senzors and Instrumention (povinný předmět programu)
• Cybernetics and Robotics - Systems and Control (povinný předmět programu)
• Open Informatics - Computer Systems (povinný předmět programu)
• Open Informatics - Computer and Information Science (povinný předmět programu)
• Open Informatics - Software Systems (povinný předmět programu)
• Cybernetics and Robotics (povinný předmět programu)
• Open Informatics (povinný předmět programu)