An Introduction to Mathematical Logic and Type Theory

To Truth Through Proof

Author: Peter B. Andrews

Publisher: Springer Science & Business Media


Category: Mathematics

Page: 390

View: 238

In case you are considering to adopt this book for courses with over 50 students, please contact [email protected] for more information. 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.

Types for Proofs and Programs

International Conference, TYPES 2007, Cividale Del Friuli, Italy, May 2-5, 2007, Revised Selected Papers

Author: Marino Miculan

Publisher: Springer Science & Business Media


Category: Computers

Page: 203

View: 317

These proceedings contain a selection of refereed papers presented at or related totheAnnualWorkshopoftheTYPESproject(EUcoordinationaction510996), which was held during May 2–5, 2007 in Cividale del Friuli (Udine), Italy. The topic of this workshop was formal reasoning and computer progr- ming basedon type theory:languagesand computerized toolsfor reasoning,and applications in several domains such as analysis of programming languages, c- ti?ed software, formalization of mathematics and mathematics education. The workshopwasattended by morethan 100researchersandincluded morethan 40 presentations. We also had the pleasure of three invited lectures, from Fr´ ed´ eric Blanqui (INRIA, Protheo team), Peter Sewell (University of Cambridge) and Amy Felty (University of Ottawa). From 22 submitted papers, 13 were selected after a reviewing process. Each submitted paper was reviewed by three referees; the ?nal decisions were made by the editors. This workshop is the last of a series of meetings of the TYPES working group funded by the European Union (IST project 29001, ESPRIT Working Group 21900, ESPRIT BRA 6435).

Mathematics, Computer Science and Logic - A Never Ending Story

The Bruno Buchberger Festschrift

Author: Peter Paule

Publisher: Springer Science & Business Media


Category: Computers

Page: 113

View: 326

This book presents four mathematical essays which explore the foundations of mathematics and related topics ranging from philosophy and logic to modern computer mathematics. While connected to the historical evolution of these concepts, the essays place strong emphasis on developments still to come. The book originated in a 2002 symposium celebrating the work of Bruno Buchberger, Professor of Computer Mathematics at Johannes Kepler University, Linz, Austria, on the occasion of his 60th birthday. Among many other accomplishments, Professor Buchberger in 1985 was the founding editor of the Journal of Symbolic Computation; the founder of the Research Institute for Symbolic Computation (RISC) and its chairman from 1987-2000; the founder in 1990 of the Softwarepark Hagenberg, Austria, and since then its director. More than a decade in the making, Mathematics, Computer Science and Logic - A Never Ending Story includes essays by leading authorities, on such topics as mathematical foundations from the perspective of computer verification; a symbolic-computational philosophy and methodology for mathematics; the role of logic and algebra in software engineering; and new directions in the foundations of mathematics. These inspiring essays invite general, mathematically interested readers to share state-of-the-art ideas which advance the never ending story of mathematics, computer science and logic. Mathematics, Computer Science and Logic - A Never Ending Story is edited by Professor Peter Paule, Bruno Buchberger’s successor as director of the Research Institute for Symbolic Computation.

Hybrid Logic and its Proof-Theory

Author: Torben Braüner

Publisher: Springer Science & Business Media


Category: Philosophy

Page: 231

View: 124

This is the first book-length treatment of hybrid logic and its proof-theory. Hybrid logic is an extension of ordinary modal logic which allows explicit reference to individual points in a model (where the points represent times, possible worlds, states in a computer, or something else). This is useful for many applications, for example when reasoning about time one often wants to formulate a series of statements about what happens at specific times. There is little consensus about proof-theory for ordinary modal logic. Many modal-logical proof systems lack important properties and the relationships between proof systems for different modal logics are often unclear. In the present book we demonstrate that hybrid-logical proof-theory remedies these deficiencies by giving a spectrum of well-behaved proof systems (natural deduction, Gentzen, tableau, and axiom systems) for a spectrum of different hybrid logics (propositional, first-order, intensional first-order, and intuitionistic).

Treatise on Intuitionistic Type Theory

Author: Johan Georg Granström

Publisher: Springer Science & Business Media


Category: Philosophy

Page: 198

View: 807

Intuitionistic type theory can be described, somewhat boldly, as a partial fulfillment of the dream of a universal language for science. This book expounds several aspects of intuitionistic type theory, such as the notion of set, reference vs. computation, assumption, and substitution. Moreover, the book includes philosophically relevant sections on the principle of compositionality, lingua characteristica, epistemology, propositional logic, intuitionism, and the law of excluded middle. Ample historical references are given throughout the book.

A HOL Intepretation of Noden

Author: Brian T. Graham



Category: Automatic theorem proving

Page: 78

View: 195

Abstract: "We describe the use of the HOL system to corroborate the logical consistency of Noden, an integrated HDL and proof system. The Noden logic is interpreted by representing terms of its logic (which are terms of the Noden HDL) as logical statements in the HOL logic. We describe the abstract datatypes representing types and values, and sample the representation of built-in operations, functions and macros as HOL function specifications. An interpretation of Noden truth-valued statements is presented as a translation of these to HOL sequents, and the representation of Noden proof functions as HOL conversions. Results of the work are summarised, including exposed errors and ambiguities of the Noden logic and implementation. We conclude that this approach to providing assurance of soundness and consistency of a less secure proof system is not only useful, but is a practical method of prototyping and an aid to specifying such a system."