John N. Crossley - Böcker

Mathematical logic has grown from an exotic branch of mathematics into an indispensable tool in computer science as well as other parts of mathematics. This concise book presents the subject of mathematical logic in a lively and approachable fashion although logic can be a formidably abstruse topic, even for mathematicians. This second edition of What is Mathematical Logic?, originally published 50 years ago, deals with important ideas in modern mathematical logic, without the detailed mathematical work required of those with a professional interest in logic. The ideas are set forth simply and clearly in a pleasant style and, despite the book's relative brevity, all the basic material is covered in these pages. Three new chapters have been added, covering automatic theorem proving, logic beyond traditional first order logic, and other logics including intuitionistic, free, and modal logics.Students of computer science and mathematical logic will find it a stimulating introduction and valuable supplement for courses, including current further reading suggestions in this lively area at the intersection of mathematics, philosophy, and computer science.

This book ?nds new things to do with an old idea. The proofs-as-programs paradigm constitutes a set of approaches to developing programs from proofs in constructive logic. It has been over thirty years since the paradigm was ?rst conceived. At that time, there was a belief that proofs-as-programs had the - tential for practical application to semi-automated software development. I- tial applications were mostly concerned with ?ne-grain, mathematical program synthesis. For various reasons, research interest in the area eventually tended toward more theoretic issues of constructive logic and type theory. However, in recent years, the situation has become more balanced, and there is increasingly active research in applying constructive techniques to industrial-scale, complex software engineering problems. Thismonographdetailsseveralimportantadvancesinthisdirectionofpr- tical proofs-as-programs. One of the central themes of the book is a general, abstract framework for developing new systems of program synthesis by adapting proofs-as-programs to new contexts. Framework-oriented approaches that facilitate analogous - proaches to building systems for solving particular problems have been popular and successful. Thesemethodsarehelpful asthey providea formal toolbox that enablesa“roll-your-own”approachtodevelopingsolutions.Itishopedthatour framework will have a similar impact. The framework is demonstrated by example. We will give two novel - plications of proofs-as-programs to large-scale, coarse-grain software engine- ing problems: contractual imperative program synthesis and structured p- gram synthesis. These applications constitute an exemplary justi?cation of the framework. Also, in and of themselves, these approaches to synthesis should be interesting forresearchers working in the target problem domains.

Anil Nerode, Director of the Mathematics Institute at Cornell, USA, is one of the most influential logicians in the world. This volume, published in his honour, contains much new and significant work. The papers in this book are principally concerned with mathematical logic and some of its applications in computing. The book contains papers on recursion theory, intuitionism, computability in group theory, recursive model theory, reverse mathematics and the extraction of programs from proofs. A survey of Nerode's technical achievements over the last 30 years is also included. In particular, the book features papers on new developments in the understanding of the properties of intuitionistic set theory and intuitionistic analysis, the extension of computability in ordinary mathematics pioneered by Marian Boykan Pour-El and Ian Richards, the proof-theoretic strength of a long-standing conjecture of Fraisse and an extension of, and further account of, the Curry-Howard method of extracting programs from logical proofs. The papers in general arose from the conference, "Logical Methods in Mathematics and Computer Science.A Symposium in Honor of Anil Nerode on the Occasion of his Sixtieth Birthday", held at the Mathematical Sciences Institute at Cornell University, from June 1-3, 1992.

This book ?nds new things to do with an old idea. The proofs-as-programs paradigm constitutes a set of approaches to developing programs from proofs in constructive logic. It has been over thirty years since the paradigm was ?rst conceived. At that time, there was a belief that proofs-as-programs had the - tential for practical application to semi-automated software development. I- tial applications were mostly concerned with ?ne-grain, mathematical program synthesis. For various reasons, research interest in the area eventually tended toward more theoretic issues of constructive logic and type theory. However, in recent years, the situation has become more balanced, and there is increasingly active research in applying constructive techniques to industrial-scale, complex software engineering problems. Thismonographdetailsseveralimportantadvancesinthisdirectionofpr- tical proofs-as-programs. One of the central themes of the book is a general, abstract framework for developing new systems of program synthesis by adapting proofs-as-programs to new contexts. Framework-oriented approaches that facilitate analogous - proaches to building systems for solving particular problems have been popular and successful. Thesemethodsarehelpful asthey providea formal toolbox that enablesa“roll-your-own”approachtodevelopingsolutions.Itishopedthatour framework will have a similar impact. The framework is demonstrated by example. We will give two novel - plications of proofs-as-programs to large-scale, coarse-grain software engine- ing problems: contractual imperative program synthesis and structured p- gram synthesis. These applications constitute an exemplary justi?cation of the framework. Also, in and of themselves, these approaches to synthesis should be interesting forresearchers working in the target problem domains.

The twenty-six papers in this volume reflect the wide and still expanding range of Anil Nerode's work. A conference on Logical Methods was held in honor of Nerode's sixtieth birthday (4 June 1992) at the Mathematical Sciences Institute, Cornell University, 1-3 June 1992. Some of the conference papers are here, but others are from students, co-workers and other colleagues. The intention of the conference was to look forward, and to see the directions currently being pursued, in the development of work by, or with, Nerode. Here is a brief summary of the contents of this book. We give a retrospective view of Nerode's work. A number of specific areas are readily discerned: recursive equivalence types, recursive algebra and model theory, the theory of Turing degrees and r.e. sets, polynomial-time computability and computer science. Nerode began with automata theory and has also taken a keen interest in the history of mathematics. All these areas are represented. The one area missing is Nerode's applied mathematical work relating to the environment. Kozen's paper builds on Nerode's early work on automata. Recursive equivalence types are covered by Dekker and Barback, the latter using directly a fundamental metatheorem of Nerode. Recursive algebra is treated by Ge & Richards (group representations). Recursive model theory is the subject of papers by Hird, Moses, and Khoussainov & Dadajanov, while a combinatorial problem in recursive model theory is discussed in Cherlin & Martin's paper. Cenzer presents a paper on recursive dynamics.

Ars musice, composed in Paris during the late thirteenth century, reflects Johannes de Grocheio's awareness of the complexity of the task of describing music. As the editors note in their introduction, "Grocheio is aware of the enormous range of types of music performed in different ways in different places. How can he impose order on this enormous subject matter? He decided to resolve this question by structuring his discussion around the practice of music that he observed in the city of Paris, organized into three main 'branches': music of the people (musica vulgalis), composite or regular, 'which they call measured music' (musica mensurata), and ecclesiastical music (musica ecclesiastica), which he claims derives from the other two (AM 6.2). The originality of Grocheio's treatise has attracted considerable scholarly interest. It has long been recognized as a unique source of information about musical life in medieval Paris. Through his treatise, Grocheio enables a modern reader to become aware of the complex auditory environment of that city in the late thirteenth century as well as of its intellectual vitality at a particularly vibrant moment in its history."

The Tractatus de tonis of Guy of Saint-Denis (written ca. 1300-10)differs from other treatises on plainchant in the depth of its analysis of thevarious tones into which chant was traditionally classified. The treatise ofGuy of Saint-Denis is preserved as the concluding item in an anthology of textsabout plainchant that Guy compiled (now London, British Library, MS Harley281), beginning with some writings of Guido of Arezzo and a Cistercian tonary,but also including the Ars musice ofJohannes de Grocheio and the Tractatus detonis of Petrus de Cruce. Guy's treatise presents itself as a syntheticoverview of both the theory and practice of plainchant in a way that combinesthe very practical reflection of Guido of Arezzo with ideas of more Aristoteleianinspired theorists such as Johannes de Grocheio and Peter of Auvergne.