Gurantor department | Department of Computer Science | Credits | 5 |

Subject guarantor | Mgr. Marek Menšík, Ph.D. | Subject version guarantor | Mgr. Marek Menšík, Ph.D. |

Study level | undergraduate or graduate | Requirement | Compulsory |

Year | 1 | Semester | winter |

Study language | English | ||

Year of introduction | 2019/2020 | Year of cancellation | |

Intended for the faculties | FEI | Intended for study types | Bachelor |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

KOT06 | Ing. Martin Kot, Ph.D. | ||

MEN059 | Mgr. Marek Menšík, Ph.D. | ||

SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Credit and Examination | 2+2 |

Part-time | Credit and Examination | 18+0 |

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.

Lectures

Tutorials

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.

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

During the semester, students write a credit test in which students demonstrate practical skills from the taught topicks. Students then pass the exam containing not only practical but also theoretical foundations.

Other requirements are not placed on students.

Subject has no prerequisities.

Subject has no co-requisities.

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.

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Credit and Examination | Credit and Examination | 100 (100) | 51 |

Credit | Credit | 40 (40) | 21 |

Credit test | Written test | 30 | 11 |

Online test | Other task type | 10 | 2 |

Examination | Examination | 60 | 30 |

Show history

Academic year | Programme | Field of study | Spec. | Zaměření | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|---|

2020/2021 | (B0613A140010) Computer Science | TZI | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2019/2020 | (B0613A140010) Computer Science | TZI | P | English | Ostrava | 1 | Compulsory | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|