Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
Web page:
https://math.fel.cvut.cz/en/people/gollova/lgr.html
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. We will introduce the resolution method in both propositional and predicate logics.
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. The language of propositional logic. |
| 2. | | Semantics and semantic entailment. |
| 3. | | The resolution method in propositional logic. |
| 4. | | Deriving conclusions (natural deduction). |
Topics in predicate logic (approx. 4 weeks):
| 1. | | The language of predicate logic. |
| 2. | | Semantics and semantic entailment in predicate logic. |
| 3. | | The resolution method in predicate logic. |
| 4. | | Reserve lecture. |
Topics in graph theory (approx. 6 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. |
| 6. | | Reserve lecture. |
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:
| Page updated 21.12.2024 12:51:19, semester: Z,L/2024-5, Z/2025-6, Send comments about the content to the Administrators of the Academic Programs |
Proposal and Realization: I. Halaška (K336), J. Novák (K336) |