Discrete Mathematics and Logic
Code  Completion  Credits  Range  Language 

BIDML.21  Z,ZK  5  2P+1R+1C  Czech 
 Garant předmětu:
 Jan Spěvák
 Lecturer:
 Daniel Dombek, Jiřina Scholtzová, Jan Spěvák
 Tutor:
 Jakub Čermák, Daniel Dombek, Jan Legerský, Jitka Rybníčková, Jiřina Scholtzová, Jan Spěvák, Irena Šindelářová
 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. Mathematical induction. Types of mathematical proofs.
6. Binary relations (properties, representations). Composition of relations.
7. Equivalence and ordering.
8. Enumerative combinatorics and its basic principles.
9. kcombinations with repetition, permutations with repetition, Stirling numbers, properties of binomial coefficients. Classical definition of probability.
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. Formulas, truth tables. Tautology, contradiction.
2. Consequence and equivalence. Universal systems of connectives.
3. Disjunctive and conjunctive normal forms.
4. Syntax of predicate logic. Language, terms, formulas. Formalization of language.
5. Mathematical induction.
6. Sets and maps.
7. Binary relation (properties, representation), composition of relations.
8. Equivalence and order.
9. Application of combinatorial principles, probability,
10. Advanced 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 9781482237726
2. Chartrand G., Zhang P.: Discrete Mathematics; Waveland;2011; ISBN 9781577667308
3. Graham R. L., Knuth D. E., Patashnik O.: Concrete Mathematics: A Foundation for Computer Science (2nd Edition); AddisonWesley Professional; 1994; ISBN 9780201558029
4. Trlifajová K., Vašata D.: Matematická logika; ČVUT2017; ISBN 9788001053423
5. Nešetřil J., Matoušek J.: Kapitoly z diskrétní matematiky; Karolinum 2007; ISBN 9788024614113
 Note:
 Further information:
 https://courses.fit.cvut.cz/BIDML
 Timetable for winter semester 2024/2025:
 Timetable is not available yet
 Timetable for summer semester 2024/2025:
 Timetable is not available yet
 The course is a part of the following study plans:

 Bachelor specialization Information Security, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Management Informatics, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Computer Graphics, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Computer Engineering, in Czech, 2021 (compulsory course in the program)
 Bachelor program, unspecified specialization, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Web Engineering, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Artificial Intelligence, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Computer Science, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Software Engineering, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Computer Systems and Virtualization, in Czech, 2021 (compulsory course in the program)
 Bachelor specialization Computer Networks and Internet, in Czech, 2021 (compulsory course in the program)