 CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2022/2023
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

# Discrete Mathematics and Logic

Code Completion Credits Range Language
BIE-DML.21 Z,ZK 5 2P+1R+1C English
The course cannot be taken simultaneously with:
Mathematical Logic (BIE-MLO)
Elements of Discrete Mathematics (BIE-ZDM)
Garant předmětu:
Daniel Dombek, Eva Pernecká, Jitka Rybníčková
Lecturer:
Eva Pernecká, Jitka Rybníčková, Jiřina Scholtzová
Tutor:
Eva Pernecká, Jitka Rybníčková, Jiřina Scholtzová
Supervisor:
Department of Applied Mathematics
Synopsis:

Students will get acquainted with the basic concepts of propositional logic and predicate logic and learn to work with their laws. Necessary concepts from set theory will be explained. Special attention is paid to relations, their general properties, and their types, especially functional relations, equivalences, and partial orders. The course also lays down the basics of combinatorics and number theory, with emphasis on modular arithmetics.

Requirements:

None.

Syllabus of lectures:

1. Propositional logic. Formulas. Truth tables. Logical equivalence. Basic laws.

2. Disjunctive and conjunctive normal forms. Full forms. Logical consequence.

3. Predicate logic. Formalization of language.

4. Sets and functions. Basic number sets. Cardinalities of sets.

5. Types of mathematical proofs. Mathematical induction.

6. Binary relations (properties, representations). Composition of relations.

7. Equivalence and ordering.

8. Combinatorics and its basic principles.

9. Classical definition of probability. k-combinations with repetition, permutations with repetition, Stirling numbers, properties of binomial coefficients.

10. Fundamentals of number theory, modular arithmetic.

11. Properties of prime numbers, Fundamental theorem of arithmetic.

12. Diophantine equations, linear congruences, Chinese remainder theorem.

Syllabus of tutorials:

1. Introduction to mathematical logics.

2. Formulas, truth tables. Tautology, contradiction, satisfiability; consequence and equivalence.

3. Universal systems of connectives. Disjunctive and conjunctive normal forms, minimalization.

4. Syntax of predicate logic. Language, terms, formulas. Formalization of language.

5. Sets and maps

6. Types of mathematical proofs. Mathematical induction.

7. Binary relation (properties, representation), composition of relations.

8. Equivalence and order.

9. Application of combinatorial principles.

11. Divisibility. Diophantine equations solution.

12. Solution of linear congruences and their systems.

Study Objective:
Study materials:

1. Mendelson E.: Introduction to Mathematical Logic (6th Edition); Chapman and Hall 2015; ISBN 978-1482237726

2. Chartrand G., Zhang P.: Discrete Mathematics; Waveland;2011; ISBN 978-1577667308

3. Graham R. L., Knuth D. E., Patashnik O.: Concrete Mathematics: A Foundation for Computer Science (2nd Edition); Addison-Wesley Professional; 1994; ISBN 978-0201558029

4. Trlifajová K., Vašata D.: Matematická logika; ČVUT2017; ISBN 978-80-01-05342-3

5. Nešetřil J., Matoušek J.: Kapitoly z diskrétní matematiky; Karolinum2007; ISBN 978-80-246-1411-3

Note:
Further information:
https://courses.fit.cvut.cz/BIE-DML
Time-table for winter semester 2022/2023:
 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 roomTH:A-s135Pernecká E.Rybníčková J.11:00–12:30(lecture parallel1)Thákurova 7 (FSv-budova A)As135roomT9:346Pernecká E.Rybníčková J.12:45–14:15(lecture parallel1parallel nr.101)DejviceNBFIT učebna roomT9:343Pernecká E.Rybníčková J.09:15–10:45(lecture parallel1parallel nr.102)DejviceNBFIT učebnaroomT9:343Pernecká E.Rybníčková J.11:00–12:30(lecture parallel1parallel nr.103)DejviceNBFIT učebna
Time-table for summer semester 2022/2023:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2023-03-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6540106.html