| Course Unit Code | 460-2051/01 |
|---|
| Number of ECTS Credits Allocated | 5 ECTS credits |
|---|
| Type of Course Unit * | Compulsory |
|---|
| Level of Course Unit * | First Cycle |
|---|
| Year of Study * | First Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | There are no prerequisites or co-requisites for this course unit |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |
| MEN059 | Mgr. Marek Menšík, Ph.D. |
| Summary |
|---|
| Many areas of computer science require the ability to work with the notions from the area of discrete mathematical structures. The goal of the course is to introduce such fundamental material for computer science. The students will obtain knowledge on discrete mathematical structures and techniques which are applied in computing practice. Three kinds of topics are covered, namely basic logic, naïve set theory and proof techniques. The course not only introduces theoretical concepts, but is also oriented to practical applications. For instance, the ability to create and understand a proof, either a formal one or a less formal but still rigorous argument, is important in almost every area of computer science. |
| Learning Outcomes of the Course Unit |
|---|
Learning outcomes cover these abilities.
Student will be able to explain by examples basic notions of the naïve set theory, functions, and relations. To perform operations on sets, functions and relations like union, intersection, power set, composition of functions and relations, to relate practical examples to the appropriate set-theoretical model, and to interpret operations and terminology.
Concerning the part on basic logic, the students will learn how to formalize natural language sentences in the language of propositional and/or first-order predicate logic. They will be able to recognize those sentences where formalization in the propositional logic suffices from those where formalization in the 1st-order predicate logic is required, and describe strengths and limitations of propositional and predicate logic. They will apply these formal methods so that to determine whether a given formula is logically valid, satisfiable or contradiction, and transfer formulas into normal forms. Last but not least, the students will be able to prove both formally and informally valid arguments and logically valid formulas. Finally, they will be able to apply these methods of logical reasoning to real problems, such as predicting the behavior of software or solving problematic puzzles.
The students will become acquainted with particular basic rules of inference such as modus ponens and modus tollens. They will learn particular proof methods such as direct proofs, indirect proofs, disproving by a counterexample, and they will be able to vote for a particular proof method apt for a given problem and propose a solution by proving that. They will also learn how to apply the inductive methods whenever a classical proof of validity is not possible. Finally, they will be familiar with the properties of relations and functions and obtain the skills of using structural induction and application of recursive mathematical definitions. |
| Course Contents |
|---|
1. Propositional Logic; syntax, semantics, formalization of sentences in the language of propositional logic
2. Propositional Logic; equivalent transformations, normal forms of formulae (conjunctive and disjunctive)
3. Propositional Logic; satisfiability, logical validity, contradiction, inference rules (modus ponens, modus tollens, ...)
4. Naïve theory of sets; operations on sets such as union, intersection, complement, power set, Cartesian product, and relations between sets such as being a subset; definition of functions and relations, demonstration by examples.
5. 1st-order predicate logic; syntax, semantics, formalization of sentences in the language of 1st-order predicate logic
6. 1st-order predicate logic; interpretation of non-logical symbols, models, Venn diagrams, demonstration of logical validity, satisfiability, and contradiction by models
7. 1st-order predicate logic; quantified formulae, equivalent transformations of formulae, de Morgan laws and normal forms
8. Cardinality of sets, countable and uncountable sets
9. Relational structures; relations of equivalence and partial order, factor set induced by equivalence
10. Types and properties of functions; surjection (mapping on), injection (one-to-one mapping into), bijection (one-to-one mapping on), inverse functions, composition of functions
11. The notion of proof, proof techniques, structure of proofs, direct and indirect proof
12. Inductive proofs and recursion; proof by mathematical induction on natural numbers, structural induction
13. Recursive mathematical functions, recursive definitions
Topics dealt with in Seminars:
Topics dealt with in seminars follow the topics of particular lectures. At seminars the students will receive an individual home-work within the scope of one lesson.
1. Propositional Logic, syntax, semantics.
2. Formalization of sentences in the language of propositional logic.
3. Propositional Logic; equivalent transformations, using the deduction rulles.
4. Naïve theory of set.
5. 1st-order predicate logic; syntax, semantics.
6. Formalization of sentences in the language of 1st-order predicate logic.
7. Venn diagrams, equivalent transformations of formulae.
8. Cardinality of sets, countable and uncountable sets.
9. Relations of equivalence and partial order, factor set induced by equivalence
10. Types and properties of functions.
11. Proof techniques, structure of proofs, direct and indirect proof.
12. Inductive proofs and recursion
13. Recursive mathematical functions.
|
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[1] DEVLIN, Keith. Introduction to mathematical thinking. Plzeň: Vydavatelství Západočeské univerzity v Plzni, 2012. ISBN 978-061-5653-631.
[2]MAKINSON, David. Sets, logic and maths for computing: modelling and reasoning about systems. 2nd ed. New York: Springer, 2012. ISBN 978-1447124993.
|
[1] DEVLIN, Keith. Introduction to mathematical thinking. Plzeň: Vydavatelství Západočeské univerzity v Plzni, 2012. ISBN 978-061-5653-631.
[2] VOPĚNKA, Petr. Úvod do klasické teorie množin. Plzeň: Vydavatelství Západočeské univerzity v Plzni, 2011. ISBN 978-80-253-1251-3.
|
| Recommended Reading: |
|---|
[1] HUTH, Michael a Mark RYAN. Logic in computer science: modelling and reasoning about systems. 2nd ed. New York: Cambridge University Press, 2004. ISBN 978-0521543101.
|
[1] SOCHOR, Antonín. Logika pro všechny ochotné myslet: modelling and reasoning about systems. V Praze: Univerzita Karlova, 2011. ISBN 978-80-246-1959-0.
[2] ŠVEJDAR, Vítězslav. Logika, neúplnost, složitost a nutnost. Praha: Academia, 2002. ISBN 978-80-200-1005-6.
[3] HUTH, Michael a Mark RYAN. Logic in computer science: modelling and reasoning about systems. 2nd ed. New York: Cambridge University Press, 2004. ISBN 978-0521543101.
|
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Credit and Examination | Credit and Examination | 100 (100) | 51 |
| Credit | Credit | 40 (40) | 21 |
| Zápočtová písemka | Written test | 30 | 11 |
| Online test | Other task type | 10 | 2 |
| Examination | Examination | 60 | 30 |