Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2020/2021

Computability and Mathematical Logic

The course is not on the list Without time-table
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, s-m-n 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.Graw-Hill,Inc. 1974.

H.R. Lewis, C.H.Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey, 1981.

Note:
Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2020-09-18
For updated information see http://bilakniha.cvut.cz/en/predmet13405.html