460-2051/02 – Introduction to Logical Thinking (ULM)

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.

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