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:	Dostál M.	Credits:	5
Tutors:	Dostál M., Gollová A., Žukovec N.	Semester:	Z,L

Web page:

https://cw.fel.cvut.cz/wiki/courses/b0b01lgr/

Anotation:

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.

Content:

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. 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): Formal language. The language of propositional logic. Semantics and semantic entailment. Deriving conclusions (natural deduction). Topics in predicate logic (approx. 4 weeks): The language of predicate logic. Semantics and semantic entailment in predicate logic. Deriving conclusions (natural deduction). Topics in graph theory (approx. 6 weeks): Basic concepts of graph theory. Trees and minimum spanning trees. Acyclic graphs. Strong connectivity. Euler graphs. 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.

Literature:

[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.

Requirements:

None.

Keywords:

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
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
BPBIO_2018	Common courses	PV	5
BPKYR_2021	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 20.4.2024 15:51:33, semester: Z,L/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)