Computability and Mathematical Logic
Code  Completion  Credits  Range  Language 

01VYML  ZK  4  4+0  Czech 
 Lecturer:
 Tutor:
 Supervisor:
 Department of Mathematics
 Synopsis:

Algorithms and algorithmically computable functions, algorithmically definable sets and their mathematical definitions. Recursion theory. Classical propositional and predicate logic. Application of the recursion theory to the logic.
 Requirements:
 Syllabus of lectures:

Algorithms and algorithmically computable functions, Markov?s normal algorithms, Turing machines, recursive functions, recursive and recursively enumerable sets and predicates, smn theorem, productive and creative sets, algorithmically unsolvable problems. Propositions, tautologies, axioms, theorems, correctness, completeness and decidability of propositional calculus. Relational structures, language of predicate calculus, terms, formulae, axioms, theorems, satisfactions, truth, tautologies, correctness, model, Gödel completeness theorem, undecidability of predicate calculus, resolution method.
 Syllabus of tutorials:
 Study Objective:

To acquaint the students with classical results of the recursion theory as a mathematical definition of intuitive notion of the algorithm and with used finite and constructive methods. Principal results of the classical logic.
 Study materials:

Povinná
N. Cutland: Computability. An Introduction to Recursive Functions Theory. Cambridge
University Press, Cambridge, 1980. (Selected chapters.)
A. Grzegorczyk: An Outline of Mathematical Logic. Polish Scientific Publishers,
Varšava 1974. (Selected chapters.)
Doporučená
Z. Manna: Mathematical Theory of Computation. Mc.GrawHill,Inc. 1974.
H.R. Lewis, C.H.Papadimitriou: Elements of the Theory of Computation. PrenticeHall, Englewood Cliffs, New Jersey, 1981.
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Matematická informatika (compulsory course of the specialization)