This book presents in a systematic way a number of topics in modern mathematical logic and the theory of algorithms. It can be used as both a text book on mathematical logic for university students and a text for specialist courses. The sections corresponding to the obligatory syllabus (Sections 1 to 9 of Chapter 1,without the small type, Sections 10 and 11 of Chapter 2, Sections 15 and 16 of Chapter 3,Sections 18 to 20, 22 and 23 of Chapter 4 and Section 35of Chapter 7) are written more thoroughly and in more detail than the sectionsrelating to more special questions. The exposition of the propositional calculus and the calculus of predicates is not a conventional one, beginning as it does with a study of sequential variants of the calculi of natural deduction( although the traditional calculi, referred to as Hilbertian ,also appears here). The reasons for this are: A) the possibility of providing a good explanation of the meaning of all the rules of inference; B) the possibility of acquiring more rapidly the knack of making formal proofs; C) a practical opportunity of making all the formal proofs necessary in the course for these calculi.This book was translated from the Russian by Vladimir Shokurov. The book was published by first Mir Publishers in 1984.All credits to the original uploader.Table of ContentsPreface 7INTRODUCTION 9Chapter 1. THE PROPOSITIONAL CALCULUS 15 1. Sets and words 15 2. The language of the propositional calculus 21 3. Axiom system and rules of inference 25 4. The equivalence of formulas 32 5. Normal forms35 6. Semantics of the propositional calculus 43 7. Characterization of provable formula 48 8. Hilbertian propositional calculus 52 9. Conservative extension of calculi 56Chapter 2. SET THEORY 6510. Predicates and mappings 65 11. Partially ordered sets 70 12. Filters of Boolean algebra 78 13.The power of a set 82 14.The axiom of choice 90Chapter 3. TRUTH ON ALGEBRAIC SYSTEMS 9615. Algebraic systems96 16. Formulas of the signature $\Sigma$ 102 17. Compactness theorem110Chapter 4. THE CALCULUS OF PREDICATES 117 18. Axioms and rules of inference 117 19. The equivalence of formulas 126 20. Normal forms 130 21. Theorem on the existence of a model 132 22. Hilbertian calculus of predicates 139 23. Pure calculus of predicates 144Chapter 5. MODEL THEORY 14924. Elementary equivalence 149 25. Axiomatizable classes 157 26. Skolem functions 165 27. Mechanism of compatibility 168 28. Countable homogeneity and universality 181 29. Categoricity 188Chapter6. PROOF THEORY 19830. The Gentzen system G 198 31. The invertibility of rules 204 32. Comparison of the calculi $CP^\Sigma$ and G 210 33. Herbrand theorem 217 34. The calculi of resolvents 228Chapter7. ALGORITHMS AND RECURSIVE FUNCTIONS23635. Normal algorithms and Turing machines 236 36. Recursive functions 247 37. Recursively enumerable predicates 264 38. Undecidability of the calculus of predicates and Godel's incompleteness theorem 276 List of symbols 292 Subject Index  295