A history of logic -- Patterns of reasoning -- A language and its meaning -- A symbolic language -- 1850-1950 mathematical logic -- Modern symbolic logic -- Elements of set theory -- Sets, functions, relations -- Induction -- Turning machines -- Computability and decidability -- Propositional logic -- Syntax and proof systems -- Semantics of PL -- Soundness and completeness -- First order logic -- Syntax and proof systems of FOL -- Semantics of FOL -- More semantics (...) -- Soundness and completeness -- Why is first order logic "First Order"? (shrink)
Together, Models and Computability and its sister volume Sets and Proofs will provide readers with a comprehensive guide to the current state of mathematical logic. All the authors are leaders in their fields and are drawn from the invited speakers at 'Logic Colloquium '97' (the major international meeting of the Association of Symbolic Logic). It is expected that the breadth and timeliness of these two volumes will prove an invaluable and unique resource for specialists, post-graduate researchers, and the (...) informed and interested nonspecialist. (shrink)
This book presents a comprehensive treatment of basic mathematical logic. The author's aim is to make exact the vague, intuitive notions of natural number, preciseness, and correctness, and to invent a method whereby these notions can be communicated to others and stored in the memory. He adopts a symbolic language in which ideas about natural numbers can be stated precisely and meaningfully, and then investigates the properties and limitations of this language. The treatment of mathematical concepts in (...) the main body of the text is rigorous, but, a section of 'historical remarks' traces the evolution of the ideas presented in each chapter. Sources of the original accounts of these developments are listed in the bibliography. (shrink)
This publication refers to the proceedings of the Seventh Latin American on Mathematical Logic held in Campinas, SP, Brazil, from July 29 to August 2, 1985. The event, dedicated to the memory of Ayda I. Arruda, was sponsored as an official Meeting of the Association for Symbolic Logic. Walter Carnielli. -/- The Journal of Symbolic Logic Vol. 51, No. 4 (Dec., 1986), pp. 1093-1103.
Assuming no previous study in logic, this informal yet rigorous text covers the material of a standard undergraduate first course in mathematical logic, using natural deduction and leading up to the completeness theorem for first-order logic. At each stage of the text, the reader is given an intuition based on standard mathematical practice, which is subsequently developed with clean formal mathematics. Alongside the practical examples, readers learn what can and can't be calculated; for example the correctness of a (...) derivation proving a given sequent can be tested mechanically, but there is no general mechanical test for the existence of a derivation proving the given sequent. The undecidability results are proved rigorously in an optional final chapter, assuming Matiyasevich's theorem characterising the computably enumerable relations. Rigorous proofs of the adequacy and completeness proofs of the relevant logics are provided, with careful attention to the languages involved. Optinal sections discuss the classification of mathematical structures by first-order theories; the required theory of cardinality is developed from scratch. Throughout the book there are notes on historical aspects of the material, and connections with linguistics and computer science, and the discussion of syntax and semantics is influenced by modern linguistic approaches. Two basic themes in recent cognitive science studies of actual human reasoning are also introduced. Including extensive exercises and selected solutions, this text is ideal for students in logic, mathematics, philosophy, and computer science. (shrink)
A Mathematical Introduction to Logic, Second Edition, offers increased flexibility with topic coverage, allowing for choice in how to utilize the textbook in a course. The author has made this edition more accessible to better meet the needs of today's undergraduate mathematics and philosophy students. It is intended for the reader who has not studied logic previously, but who has some experience in mathematical reasoning. Material is presented on computer science issues such as computational complexity and database queries, (...) with additional coverage of introductory material such as sets. Increased flexibility of the text, allowing instructors more choice in how they use the textbook in courses. Reduced mathematical rigour to fit the needs of undergraduate students. (shrink)
Proofs and Refutations is essential reading for all those interested in the methodology, the philosophy and the history of mathematics. Much of the book takes the form of a discussion between a teacher and his students. They propose various solutions to some mathematical problems and investigate the strengths and weaknesses of these solutions. Their discussion (which mirrors certain real developments in the history of mathematics) raises some philosophical problems and some problems about the nature of mathematical discovery or (...) creativity. Imre Lakatos is concerned throughout to combat the classical picture of mathematical development as a steady accumulation of established truths. He shows that mathematics grows instead through a richer, more dramatic process of the successive improvement of creative hypotheses by attempts to 'prove' them and by criticism of these attempts: the logic of proofs and refutations. (shrink)
Graduate-level historical study is ideal for students intending to specialize in the topic, as well as those who only need a general treatment. Part I discusses traditional and symbolic logic. Part II explores the foundations of mathematics, emphasizing Hilbert’s metamathematics. Part III focuses on the philosophy of mathematics. Each chapter has extensive supplementary notes; a detailed appendix charts modern developments.
Undergraduate students with no prior classroom instruction in mathematical logic will benefit from this evenhanded multipart text by one of the centuries greatest authorities on the subject. Part I offers an elementary but thorough overview of mathematical logic of first order. The treatment does not stop with a single method of formulating logic; students receive instruction in a variety of techniques, first learning model theory (truth tables), then Hilbert-type proof theory, and proof theory handled through derived rules. Part (...) II supplements the material covered in Part I and introduces some of the newer ideas and the more profound results of logical research in the twentieth century. Subsequent chapters introduce the study of formal number theory, with surveys of the famous incompleteness and undecidability results of Godel, Church, Turing, and others. The emphasis in the final chapter reverts to logic, with examinations of Godel's completeness theorem, Gentzen's theorem, Skolem's paradox and nonstandard models of arithmetic, and other theorems. Unabridged republication of the edition published by John Wiley & Sons, Inc. New York, 1967. Preface. Bibliography. Theorem and Lemma Numbers: Pages. List of Postulates. Symbols and Notations. Index. (shrink)
The history of modern logic is usually written as the history of mathematical or, more general, symbolic logic. As such it was created by mathematicians. Not regarding its anticipations in Scholastic logic and in the rationalistic era, its continuous development began with George Boole's The Mathematical Analysis of Logic of 1847, and it became a mathematical subdiscipline in the early 20th century. This style of presentation cuts off one eminent line of development, the philosophical development of (...) logic, although logic is evidently one of the basic disciplines of philosophy. One needs only to recall some of the standard 19th century definitions of logic as, e.g., the art and science of reasoning (Whateley) or as giving the normative rules of correct reasoning (Herbart). In the paper the relationship between the philosophical and the mathematical development of logic will be discussed. Answers to the following questions will be provided: 1. What were the reasons for the philosophers' lack of interest in formal logic? 2. What were the reasons for the mathematicians' interest in logic? 3. What did "logic reform" mean in the 19th century? Were the systems of mathematical logic initially regarded as contributions to a reform of logic? 4. Was mathematical logic regarded as art, as science or as both? (shrink)
The Annual European Meeting of the Association for Symbolic Logic, generally known as the Logic Colloquium, is the most prestigious annual meeting in the field. Many of the papers presented there are invited surveys of recent developments. Highlights of this volume from the 2005 meeting include three papers on different aspects of connections between model theory and algebra; a survey of recent major advances in combinatorial set theory; a tutorial on proof theory and modal logic; and a description of (...) Bernay's philosophy of mathematics. (shrink)
Filling the need for an accessible, carefully structured introductory text in symbolic logic, Modern Logic has many features designed to improve students' comprehension of the subject, including a proof system that is the same as the award-winning computer program MacLogic, and a special appendix that shows how to use MacLogic as a teaching aid. There are graded exercises at the end of each chapter--more than 900 in all--with selected answers at the end of the book. Unlike competing texts, Modern (...) Logic gives equal weight to semantics and proof theory and explains their relationship, and develops in detail techniques for symbolizing natural language in first-order logic. After a general introduction featuring the notion of logical form, the book offers sections on classical sentential logic, monadic predicate logic, and full first-order logic with identity. A concluding section deals with extensions of and alternatives to classical logic, including modal logic, intuitionistic logic, and fuzzy logic. For students of philosophy, mathematics, computer science, or linguistics, Modern Logic provides a thorough understanding of basic concepts and a sound basis for more advanced work. (shrink)
This introduction to rigorous mathematical logic is simple enough in both presentation and context for students of a wide range of ages and abilities. Starting with symbolizing sentences and sentential connectives, it proceeds to the rules of logical inference and sentential derivation, examines the concepts of truth and validity, and presents a series of truth tables. Subsequent topics include terms, predicates, and universal quantifiers; universal specification and laws of identity; axioms for addition; and universal generalization. Throughout the book, the (...) authors emphasize the pervasive and important problem of translating English sentences into logical or mathematical symbolism. 1964 edition. Index. (shrink)
This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This expressive notation (...) facilitates proofs of the classical incompleteness and undecidability theorems which are very elegant and easy to understand. The discussion of semantics makes clear the important distinction between standard and nonstandard models which is so important in understanding puzzling phenomena such as the incompleteness theorems and Skolem's Paradox about countable models of set theory. Some of the numerous exercises require giving formal proofs. A computer program called ETPS which is available from the web facilitates doing and checking such exercises. Audience: This volume will be of interest to mathematicians, computer scientists, and philosophers in universities, as well as to computer scientists in industry who wish to use higher-order logic for hardware and software specification and verification. (shrink)
Noted logician and philosopher addresses various forms of mathematical logic, discussing both theoretical underpinnings and practical applications. After historical survey, lucid treatment of set theory, model theory, recursion theory and constructivism and proof theory. Place of problems in development of theories of logic, logic’s relationship to computer science, more. Suitable for readers at many levels of mathematical sophistication. 3 appendixes. Bibliography. 1981 edition.
This lively introduction to mathematical logic, easily accessible to non-mathematicians, offers an historical survey, coverage of predicate calculus, model theory, Godel’s theorems, computability and recursivefunctions, consistency and independence in axiomatic set theory, and much more. Suggestions for Further Reading. Diagrams.
Traditional logic as a part of philosophy is one of the oldest scientific disciplines. Mathematical logic, however, is a relatively young discipline and arose from the endeavors of Peano, Frege, Russell and others to create a logistic foundation for mathematics. It steadily developed during the 20th century into a broad discipline with several sub-areas and numerous applications in mathematics, informatics, linguistics and philosophy. While there are already several well-known textbooks on mathematical logic, this book is unique in that (...) it is much more concise than most others, and the material is treated in a streamlined fashion which allows the professor to cover many important topics in a one semester course. Although the book is intended for use as a graduate text, the first three chapters could be understood by undergraduates interested in mathematical logic. These initial chapters cover just the material for an introductory course on mathematical logic combined with the necessary material from set theory. This material is of a descriptive nature, providing a view towards decision problems, automated theorem proving, non-standard models and other subjects. The remaining chapters contain material on logic programming for computer scientists, model theory, recursion theory, Godel’s Incompleteness Theorems, and applications of mathematical logic. Philosophical and foundational problems of mathematics are discussed throughout the text. The author has provided exercises for each chapter, as well as hints to selected exercises. About the German edition: …The book can be useful to the student and lecturer who prepares a mathematical logic course at the university. What a pity that the book is not written in a universal scientific language which mankind has not yet created. - A.Nabebin, Zentralblatt. (shrink)
This junior/senior level text is devoted to a study of first-order logic and its role in the foundations of mathematics: What is a proof? How can a proof be justified? To what extent can a proof be made a purely mechanical procedure? How much faith can we have in a proof that is so complex that no one can follow it through in a lifetime? The first substantial answers to these questions have only been obtained in this century. The most (...) striking results are contained in Goedel's work: First, it is possible to give a simple set of rules that suffice to carry out all mathematical proofs; but, second, these rules are necessarily incomplete - it is impossible, for example, to prove all true statements of arithmetic. The book begins with an introduction to first-order logic, Goedel's theorem, and model theory. A second part covers extensions of first-order logic and limitations of the formal methods. The book covers several advanced topics, not commonly treated in introductory texts, such as Trachtenbrot's undecidability theorem. Fraissé's elementary equivalence, and Lindstroem's theorem on the maximality of first-order logic. (shrink)
Highlights of this volume from the 2004 Annual European Meeting of the Association for Symbolic Logic (ASL) include a tutorial survey of the recent highpoints of universal algebra, written by a leading expert; explorations of foundational questions; a quartet of model theory papers giving an excellent reflection of current work in model theory, from the most abstract aspect "abstract elementary classes" to issues around p-adic integration.
Mathematical Logic for Computer Science is a mathematics textbook with theorems and proofs, but the choice of topics has been guided by the needs of computer science students. The method of semantic tableaux provides an elegant way to teach logic that is both theoretically sound and yet sufficiently elementary for undergraduates. To provide a balanced treatment of logic, tableaux are related to deductive proof systems.The logical systems presented are:- Propositional calculus (including binary decision diagrams);- Predicate calculus;- Resolution;- Hoare logic;- (...) Z;- Temporal logic.Answers to exercises (for instructors only) as well as Prolog source code for algorithms may be found via the Springer London web site: http://www.springer.com/978-1-85233-319-5 Mordechai Ben-Ari is an associate professor in the Department of Science Teaching of the Weizmann Institute of Science. He is the author of numerous textbooks on concurrency, programming languages and logic, and has developed software tools for teaching concurrency. In 2004, Ben-Ari received the ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education. (shrink)
This book contains an introduction to symbolic logic and a thorough discussion of mechanical theorem proving and its applications. The book consists of three major parts. Chapters 2 and 3 constitute an introduction to symbolic logic. Chapters 4–9 introduce several techniques in mechanical theorem proving, and Chapters 10 an 11 show how theorem proving can be applied to various areas such as question answering, problem solving, program analysis, and program synthesis.
A comprehensive one-year graduate (or advanced undergraduate) course in mathematical logic and foundations of mathematics. No previous knowledge of logic is required; the book is suitable for self-study. Many exercises (with hints) are included.
Suitable for advanced undergraduates and graduate students from diverse fields and varying backgrounds, this self-contained course in mathematical logic features numerous exercises that vary in difficulty. The author is a Professor of Mathematics at the University of Wisconsin.
An excellent introduction to mathematical logic, this book provides readers with a sound knowledge of the most important approaches to the subject, stressing the use of logical methods in attacking nontrivial problems. It covers the logic of classes, of propositions, of propositional functions, and the general syntax of language, with a brief introduction that also illustrates applications to so-called undecidability and incompleteness theorems. Other topics include the simple proof of the completeness of the theory of combinations, Church's theorem on (...) the recursive unsolvability of the decision problem for the restricted function calculus, and the demonstrable properties of a formal system as a criterion for its acceptability. 1950 ed. (shrink)
Logic forms the basis of mathematics and is a fundamental part of any mathematics course. This book provides students with a clear and accessible introduction to this important subject, using the concept of model as the main focus and covering a wide area of logic. The chapters of the book cover propositional calculus, boolean algebras, predicate calculus and completelness theorems with answeres to all of the excercises and the end of the volume. This is an ideal introduction to mathematics and (...) logic for the advanced undergraduate student. (shrink)
Logic With Trees is a new and original introduction to modern formal logic. It contains discussions on philosophical issues such as truth, conditionals and modal logic, presenting the formal material with clarity, and preferring informal explanations and arguments to intimidatingly rigorous development. Worked examples and exercises guide beginners through the book, with answers to selected exercises enabling readers to check their progress. Logic With Trees equips students with: a complete and clear account of the truth-tree system for first order logic; (...) the importance of logic and its relevance to many different disciplines; the skills to grasp sophisticated formal reasoning techniques necessary to explore complex metalogic; the ability to contest claims that "ordinary" reasoning is well represented by formal first order logic. (shrink)
Comprehensive account of constructive theory of first-order predicate calculus. Covers formal methods including algorithms and epi-theory, brief treatment of Markov’s approach to algorithms, elementary facts about lattices and similar algebraic systems, more. Philosophical and reflective as well as mathematical. Graduate-level course. 1963 ed. Exercises.
Lucid, non-intimidating presentation of propositional logic, propositional calculus and predicate logic by Russian scholar. Topics of concern in a variety of fields, including computer science, systems analysis, linguistics, etc. Accessible to high school students; valuable review of fundamentals for professionals. Exercises (no solutions). Preface. Three appendices. Indices. Bibliogaphy. 14 figures.