【英文原版书】A problem book in Mathematical Logic I.pdf

A Problem Course in
Mathematical Logic
Version
Volume I
Propositional and
First-Order Logic
Stefan Bilaniuk
Department of Mathematics
Trent University
Peterborough, Ontario
Canada K9J 7B8
E-mail address: ******@
1991 Mathematics Subject Classification. 03
Key words and phrases. propositional logic, first-order logic
A Problem Course In Mathematical Logic
Volume I: Propositional and First-Order Logic
Version
Copyright °c 1994–1999 by Stefan Bilaniuk.
Abstract. This is a text for a problem-oriented undergraduate
course in mathematical logic. It covers the basics of propositional
and first-order logic through the Soundness, Completeness, and
Compactness Theorems. Volume II, Computation, covers the ba-
sics putability using Turing machines and recursive func-
tions, the pleteness Theorems, plexity theory through
the P and NP.
Information on availabality and the conditions under which
this book may be used and reproduced are given in the preface.
This book was typeset using LATEX, using the AMS-LATEX and
AMSFonts packages of the American Mathematical Society.
Contents
iii
Preface
This book is intended to be the basis for a problem-oriented full-year
course in mathematical logic for students with a modicum of mathe-
matical sophistication. Volume I covers the basics of propositional and
first-order logic through the Soundness, Completeness, pact-
ness Theorems, plus some material on applications of pactness
Theorem. It could easily be used for a one-semester course on these
topics. Volume II covers the basics putability using Turing ma-
chines and recursive functions, the pleteness Theorem, and basic
complexity theory; it could also be used as for a one-semester course
on these topics.
In keeping with the modified Moore-method, this book supplies
definitions, problems, and statements of results, along with some ex-
planations, examples, and hints. The intent is for the students, indi-
vidua