Subject description - B0B01LGR

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
B0B01LGR Logic anad Graphs
Roles:P, PV Extent of teaching:3P+2S
Department:13101 Language of teaching:CS
Guarantors:Demlová M. Completion:Z,ZK
Lecturers:Gollová A. Credits:5
Tutors:Dostál M., Gollová A. Semester:Z,L

Web page:


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

Study targets:

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


This subject is dedicated to the study of mathematical logic and graph theory. In the logic part of the course we will discuss the basics of propositional logic and first-order logic (predicate logic). We study formal syntax, and the languages of logic are compared to programming languages. The practical problem of deriving a conclusion from given premises is discussed. We introduce syntactic inference rules and discuss their meaningfulness. We introduce the meaning (semantics) of propositional logic in a standard way. We will study semantic entailment and its relation to syntactic entailment. In predicate logic, we introduce its semantics and study the truth of a proposition of predicate logic in a given interpretation. We introduce and explain the rules of natural deduction for working with quantifiers. In the graph theory part we present practical problems that are describable and solvable by graph theoretical methods. We introduce the basic concepts of graph theory as a means of expression to describe theoretical and practical problems. We will derive the theoretical properties of the concepts as a means to develop graph algorithms.

Course outlines:

Topics in propositional logic (approx. 4 weeks):
1. Formal language.
2. Deduction.
3. Semantics and semantic entailment.
4. Reserve lecture.
Topics in predicate logic (approx. 4 weeks):
1. The language of predicate logic.
2. Deduction.
3. The model of a set of sentences, semantic entailment.
4. Reserve lecture.
Topics in graph theory (approx. 5 weeks):
1. Basic concepts of graph theory.
2. Trees and minimum spanning trees.
3. Acyclic graphs. Strong connectivity.
4. Euler graphs.
5. Colouring. (Planar graphs.)

Exercises outline:

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.




Propositional logic, predicate logic, syntactic and semantic consequence, basic notions of graph theory, graph algorithms.

Subject is included into these academic programs:

Program Branch Role Recommended semester
BPKYR_2021 Common courses P 1
BPBIO_2018 Common courses PV 5
BPOI_BO_2018 Common courses P 2
BPOI4_2018 Computer Games and Graphics P 2
BPOI3_2018 Software P 2
BPOI2_2018 Internet of Things P 2
BPOI1_2018 Artificial Intelligence and Computer Science P 2
BPKYR_2016 Common courses P 1
BPOI1_2016 Computer and Information Science P 2
BPOI_BO_2016 Common courses P 2
BPOI4_2016 Computer Games and Graphics P 2
BPOI3_2016 Software P 2
BPOI2_2016 Internet of Things P 2

Page updated 7.6.2023 12:50:36, semester: L/2022-3, Z/2023-4, Z/2024-5, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)