# Subject description - AE0B01LGR

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
AE0B01LGR Logic and Graph Theory
Roles:P, V Extent of teaching:3+2
Department:13101 Language of teaching:EN
Guarantors:  Completion:Z,ZK
Lecturers:  Credits:6
Tutors:  Semester:L

Anotation:

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.

Výsledek studentské ankety předmětu je zde: AE0B01LGR

Course outlines:

 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.

Exercises outline:

 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.

Literature:

 [1] M. Demlová: Mathematical Logic. ČVUT Praha, 1999. [2] R. Diestel: Graph Theory, Springer-Verlag, 1997

Requirements:

Discrete Mathematics, Linear Algebra

Subject is included into these academic programs:

 Program Branch Role Recommended semester BEKME1 Communication Technology V 2 BEKME5 Komunikace a elektronika V 2 BEKME_BO Common courses V 2 BEKME4 Network and Information Technology V 2 BEKME3 Applied Electronics V 2 BEKME2 Multimedia Technology V 2 BEKYR1 Robotics P 2 BEKYR_BO Common courses P 2 BEKYR3 Systems and Control P 2 BEKYR2 Sensors and Instrumentation P 2 BEEEM1 Applied Electrical Engineering V 2 BEEEM_BO Common courses V 2 BEEEM2 Electrical Engineering and Management V 2 BEOI1 Computer Systems P 2 BEOI_BO Common courses P 2 BEOI3 Software Systems P 2 BEOI2 Computer and Information Science P 2

 Page updated 22.6.2021 05:52:39, semester: L/2021-2, L/2020-1, Z,L/2022-3, Z/2021-2, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)