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

Front Cover
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

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

Other editions - View all

Common terms and phrases

Bibliographic information