Course on mathematical logic and computability theory. Textbook

The present tutorial is intended to study the mathematical logic and theory of algorithms. It describes the language of the logic of statements and the language of the logic of first-order predicates, the semantics of these languages. Based on the general concept of calculation, the calculus of Hilbert type, sequential terms and method of resolutions as methods of formal mathematical evidence are presented.
The main formal axiomatic theories are considered: elementary arithmetic and the theory of sets of Chermelo-Frenkel. The theory of algorithms is represented by the theory of computability, within the framework of which several accurate definitions of the concept of the algorithm (Turing machines, normal Markov algorithms, lambda-calculus, partially recursive functions) and proven intractability of a number of problems, among which the problem of stopping Turing machines, the problem of equality for semigroups, problems The general accuracy and predictions for the calculation of predicates. The theorems of the Gödel about incompleteness are considered. The calculus of Hoara is outlined to formally proof the correctness of programs of a certain imperative programming language. The book has more than 200 exercises.
The training manual is addressed primarily to students learning in the areas of preparation of the enlarged groups Computer and Information Sciences, Informatics and Computing Technique, but will be useful and students of a group of mathematics and mechanics, as well as all those who want to start Systematic study of mathematical logic