This volume presents the proceedings from the Eleventh Brazilian Logic Conference on MathematicalLogic held by the Brazilian Logic Society (co-sponsored by the Centre for Logic, Epistemology and the History of Science, State University of Campinas, Sao Paulo) in Salvador, Bahia, Brazil. The conference and the volume are dedicated to the memory of professor Mario Tourasse Teixeira, an educator and researcher who contributed to the formation of several generations of Brazilian logicians. Contributions were made from (...) leading Brazilian logicians and their Latin-American and European colleagues. All papers were selected by a careful refereeing processs and were revised and updated by their authors for publication in this volume. There are three sections: Advances in Logic, Advances in Theoretical Computer Science, and Advances in Philosophical Logic. Well-known specialists present original research on several aspects of model theory, proof theory, algebraic logic, category theory, connections between logic and computer science, and topics of philosophical logic of current interest. Topics interweave proof-theoretical, semantical, foundational, and philosophical aspects with algorithmic and algebraic views, offering lively high-level research results. (shrink)
This revised and considerably expanded 2nd edition brings together a wide range of topics, including modal, tense, conditional, intuitionist, many-valued, paraconsistent, relevant, and fuzzy logics. Part 1, on propositional logic, is the old Introduction, but contains much new material. Part 2 is entirely new, and covers quantification and identity for all the logics in Part 1. The material is unified by the underlying theme of world semantics. All of the topics are explained clearly using devices such as tableau proofs, (...) and their relation to current philosophical issues and debates are discussed. Students with a basic understanding of classical logic will find this book an invaluable introduction to an area that has become of central importance in both logic and philosophy. It will also interest people working in mathematics and computer science who wish to know about the area. (shrink)
K. Marx’s 200th jubilee coincides with the celebration of the 85 years from the first publication of his “Mathematical Manuscripts” in 1933. Its editor, Sofia Alexandrovna Yanovskaya (1896–1966), was a renowned Soviet mathematician, whose significant studies on the foundations of mathematics and mathematicallogic, as well as on the history and philosophy of mathematics are unduly neglected nowadays. Yanovskaya, as a militant Marxist, was actively engaged in the ideological confrontation with idealism and its influence on modern mathematics (...) and their interpretation. Concomitantly, she was one of the pioneers of mathematicallogic in the Soviet Union, in an era of fierce disputes on its compatibility with Marxist philosophy. Yanovskaya managed to embrace in an originally Marxist spirit the contemporary level of logico-philosophical research of her time. Due to her highly esteemed status within Soviet academia, she became one of the most significant pillars for the culmination of modern mathematics in the Soviet Union. In this paper, I attempt to trace the influence of the complex socio-cultural context of the first decades of the Soviet Union on Yanovskaya’s work. Among the several issues I discuss, her encounter with L. Wittgenstein is striking. (shrink)
This introduction to mathematicallogic 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)
A comprehensive one-year graduate (or advanced undergraduate) course in mathematicallogic and foundations of mathematics. No previous knowledge of logic is required; the book is suitable for self-study. Many exercises (with hints) are included.
Undergraduate students with no prior classroom instruction in mathematicallogic 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 mathematicallogic 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)
Assuming no previous study in logic, this informal yet rigorous text covers the material of a standard undergraduate first course in mathematicallogic, 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)
This introduction to rigorous mathematicallogic 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 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)
Suitable for advanced undergraduates and graduate students from diverse fields and varying backgrounds, this self-contained course in mathematicallogic features numerous exercises that vary in difficulty. The author is a Professor of Mathematics at the University of Wisconsin.
Traditional logic as a part of philosophy is one of the oldest scientific disciplines. Mathematicallogic, 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 mathematicallogic, 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 mathematicallogic. These initial chapters cover just the material for an introductory course on mathematicallogic 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 mathematicallogic. 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 mathematicallogic 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)
Noted logician and philosopher addresses various forms of mathematicallogic, 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.
An excellent introduction to mathematicallogic, 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)
This lively introduction to mathematicallogic, 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.
MathematicalLogic 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 presents a comprehensive treatment of basic mathematicallogic. 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)
A history of logic -- Patterns of reasoning -- A language and its meaning -- A symbolic language -- 1850-1950 mathematicallogic -- 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)
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)
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)
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.