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

 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
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 studyWay of compl.Extent
Full-time Credit and Examination 2+2
Part-time Credit and Examination 18+0

### Subject aims expressed by acquired skills and competences

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

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

### Compulsory literature:

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

### Recommended literature:

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

### Way of continuous check of knowledge in the course of semester

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

Other requirements are not placed on students.

### Prerequisities

Subject has no prerequisities.

### Co-requisities

Subject has no co-requisities.

### Subject syllabus:

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.

### Conditions for subject completion

Full-time form (validity from: 2019/2020 Winter semester)
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
Mandatory attendence parzicipation: It is necessary to obtain at least 21 points from the credit and 30 points from the exam.

Show history

### Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType 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

### Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner