# Mathematical Logic: Part 1: Propositional Calculus, Boolean Algebras, Predicate Calculus, Completeness Theorems

OUP Oxford, Sep 7, 2000 - Mathematics - 360 pages
Logic forms the basis of mathematics, and is hence a fundamental part of any mathematics course. In particular, it is a major element in theoretical computer science and has undergone a huge revival with the explosion of interest in computers and computer science. This book provides students with a clear and accessible introduction to this important subject. The concept of model underlies the whole book, giving the text a theoretical coherence whilst still covering a wide area of logic.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 Propositional calculus 7 11 Syntax 8 112 Proofs by induction on the set of formulas 11 113 The decomposition tree of a formula 13 114 The unique decomposition theorem 15 115 Definitions by induction on the set of formulas 18 116 Substitutions in a propositional formula 19 12 Semantics 21
 314 Formulas of the language 122 315 Free variables bound variables and closed formulas 125 316 Substitutions in formulas 127 32 Structures 130 321 Models of a language 131 322 Substructures and restrictions 133 323 Homomorphisms and isomorphisms 135 33 Satisfaction of formulas in structures 137

 122 Tautologies and logically equivalent formulas 27 123 Some tautologies 31 13 Normal forms and complete sets of connectives 34 132 Normal forms 38 133 Complete sets of connectives 40 14 The interpolation lemma 42 142 The definability theorem 44 15 The compactness theorem 45 152 The compactness theorem for propositional calculus 48 EXERCISES FOR CHAPTER 1 53 Boolean algebras 63 21 Algebra and topology review 64 212 Topology 67 213 An application to propositional calculus 71 221 Properties of Boolean algebras order relations 72 222 Boolean algebras as ordered sets 75 23 Atoms in a Boolean algebra 79 24 Homomorphisms isomorphisms subalgebras 81 242 Boolean subalgebras 86 25 Ideals and filters 88 252 Maximal ideals 91 253 Filters 93 254 Ultrafilters 94 255 Filterbases 96 26 Stones theorem 97 261 The Stone space of a Boolean algebra 98 262 Stones theorem 102 EXERCISES FOR CHAPTER 2 106 Predicate calculus 112 31 Syntax 113 312 Terms of the language 115 313 Substitutions in terms 121
 332 Satisfaction of the formulas in a structure 140 34 Universal equivalence and semantic consequence 147 35 Prenex forms and Skolem forms 157 352 Skolem forms 160 36 First steps in model theory 165 362 Elementary equivalence 170 363 The language associated with a structure and formulas with parameters 174 364 Functions and relations definable in a structure 176 37 Models that may not respect equality 179 EXERCISES FOR CHAPTER 3 182 The completeness theorems 193 41 Formal proofs or derivations 194 412 Formal proofs 196 413 The finiteness theorem and the deduction theorem 200 42 Henkin models 202 421 Henkin witnesses 203 422 The completeness theorem 205 43 Herbrands method 209 432 The avatars of a formula 212 44 Proofs using cuts 217 442 Completeness of the method 221 45 The method of resolution 224 452 Proofs by resolution 230 EXERCISES FOR CHAPTER 4 241 Solutions 245 Solutions to the exercises for Chapter 2 270 Solutions to the exercises for Chapter 3 293 Solutions to the exercises for Chapter 4 320 Bibliography 330 Index 332 Copyright