tailieunhanh - A Problem Course in Mathematical Logic Version 1.6 Stefan Bilaniuk Department of Mathematics Trent

Engineering is the goal-oriented process of designing and making tools and systems to exploit natural phenomena for practical human means, often (but not always) using results and techniques from science. The development of technology may draw upon many fields of knowledge, including scientific, engineering, mathematical, linguistic, and historical knowledge, to achieve some practical result. | A Problem Course in Mathematical Logic Version Stefan Bilaniuk Department of Mathematics Trent UNivERSiTy Peterborough Ontario Canada K9J 7B8 E-mail address sbilaniuk@ 1991 Mathematics Subject Classification. 03 Key words and phrases. logic computability incompleteness Abstract. This is a text for a problem-oriented course on mathematical logic and computability. Copyright 1994-2003 Stefan Bilaniuk. Permission is granted to copy distribute and or modify this document under the terms of the GNU Free Documentation License Version or any later version published by the Free Software Foundation with no Invariant Sections no Front-Cover Texts and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License . This work was typeset with lATpX using the Ạ S-IATpX and Ạ. óToiits packages of the American Mathematical Society. Contents Preface v Introduction ix Part I. Propositional Logic 1 Chapter 1. Language 3 Chapter 2. Truth Assignments 7 Chapter 3. Deductions 11 Chapter 4. Soundness and Completeness 15 Hints for Chapters 1-4 17 Part II. First-Order Logic 21 Chapter 5. Languages 23 Chapter 6. Structures and Models 33 Chapter 7. Deductions 41 Chapter 8. Soundness and Completeness 47 Chapter 9. Applications of Compactness 53 Hints for Chapters 5-9 59 Part III. Computability 65 Chapter 10. Turing Machines 67 Chapter 11. Variations and Simulations 75 Chapter 12. Computable and Non-Computable Functions 81 Chapter 13. Recursive Functions 87 Chapter 14. Characterizing Computability 95 .