'Numbers and Proofs' presents a gentle introduction to the notion of proof to give the reader an understanding of how to decipher others' proofs as well as construct their own. Useful methods of proof are illustrated in the context of studying problems concerning mainly numbers (real, rational, complex and integers). An indispensable guide to all students of mathematics. Each proof is preceded by a discussion which is intended to show the reader the kind of thoughts they might have before any attempt proof is made. Established proofs which the student is in a better position to follow then follow.
Presented in the author's entertaining and informal style, and written to reflect the changing profile of students entering universities, this book will prove essential reading for all seeking an introduction to the notion of proof as well as giving a definitive guide to the more common forms. Stressing the importance of backing up "truths" found through experimentation, with logically sound and watertight arguments, it provides an ideal bridge to more complex undergraduate maths.

Synthesis of Finite State Machines: Logic Optimization is the second in a set of two monographs devoted to the synthesis of Finite State Machines (FSMs). The first volume, Synthesis of Finite State Machines: Functional Optimization, addresses functional optimization, whereas this one addresses logic optimization. The result of functional optimization is a symbolic description of an FSM which represents a sequential function chosen from a collection of permissible candidates. Logic optimization is the body of techniques for converting a symbolic description of an FSM into a hardware implementation. The mapping of a given symbolic representation into a two-valued logic implementation is called state encoding (or state assignment) and it impacts heavily area, speed, testability and power consumption of the realized circuit. The first part of the book introduces the relevant background, presents results previously scattered in the literature on the computational complexity of encoding problems, and surveys in depth old and new approaches to encoding in logic synthesis. The second part of the book presents two main results about symbolic minimization; a new procedure to find minimal two-level symbolic covers, under face, dominance and disjunctive constraints, and a unified frame to check encodability of encoding constraints and find codes of minimum length that satisfy them. The third part of the book introduces generalized prime implicants (GPIs), which are the counterpart, in symbolic minimization of two-level logic, to prime implicants in two-valued two-level minimization. GPIs enable the design of an exact procedure for two-level symbolic minimization, based on a covering step which is complicated by the need to guarantee encodability of the final cover. A new efficient algorithm to verify encodability of a selected cover is presented. If a cover is not encodable, it is shown how to augment it minimally until an encodable superset of GPIs is determined. To handle encodability the authors have extended the frame to satisfy encoding constraints presented in the second part. The covering problems generated in the minimization of GPIs tend to be very large. Recently large covering problems have been attacked successfully by representing the covering table with binary decision diagrams (BDD). In the fourth part of the book the authors introduce such techniques and extend them to the case of the implicit minimization of GPIs, where the encodability and augmentation steps are also performed implicitly. Synthesis of Finite State Machines: Logic Optimization will be of interest to researchers and professional engineers who work in the area of computer-aided design of integrated circuits.

The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.

This book collects, for the first time in one volume, contributions honoring Professor Raymond Smullyan's work on self-reference. It serves not only as a tribute to one of the great thinkers in logic, but also as a celebration of self-reference in general, to be enjoyed by all lovers of this field. Raymond Smullyan, mathematician, philosopher, musician and inventor of logic puzzles, made a lasting impact on the study of mathematical logic; accordingly, this book spans the many personalities through which Professor Smullyan operated, offering extensions and re-evaluations of his academic work on self-reference, applying self-referential logic to art and nature, and lastly, offering new puzzles designed to communicate otherwise esoteric concepts in mathematical logic, in the manner for which Professor Smullyan was so well known. This book is suitable for students, scholars and logicians who are interested in learning more about Raymond Smullyan's work and life.

Lattice-valued Logic aims at establishing the logical foundation for uncertain information processing routinely performed by humans and artificial intelligence systems. In this textbook for the first time a general introduction on lattice-valued logic is given. It systematically summarizes research from the basic notions up to recent results on lattice implication algebras, lattice-valued logic systems based on lattice implication algebras, as well as the corresponding reasoning theories and methods. The book provides the suitable theoretical logical background of lattice-valued logic systems and supports newly designed intelligent uncertain-information-processing systems and a wide spectrum of intelligent learning tasks.

This volume contains English translations of Frege's early writings in logic and philosophy and of relevant reviews by other leading logicians. Professor Bynum has contributed a biographical essay, introduction, and extensive bibliography.

This volume is dedicated to Prof. Dag Prawitz and his outstanding contributions to philosophical and mathematical logic. Prawitz's eminent contributions to structural proof theory, or general proof theory, as he calls it, and inference-based meaning theories have been extremely influential in the development of modern proof theory and anti-realistic semantics. In particular, Prawitz is the main author on natural deduction in addition to Gerhard Gentzen, who defined natural deduction in his PhD thesis published in 1934. The book opens with an introductory paper that surveys Prawitz's numerous contributions to proof theory and proof-theoretic semantics and puts his work into a somewhat broader perspective, both historically and systematically. Chapters include either in-depth studies of certain aspects of Dag Prawitz's work or address open research problems that are concerned with core issues in structural proof theory and range from philosophical essays to papers of a mathematical nature. Investigations into the necessity of thought and the theory of grounds and computational justifications as well as an examination of Prawitz's conception of the validity of inferences in the light of three "dogmas of proof-theoretic semantics" are included. More formal papers deal with the constructive behaviour of fragments of classical logic and fragments of the modal logic S4 among other topics. In addition, there are chapters about inversion principles, normalization of p roofs, and the notion of proof-theoretic harmony and other areas of a more mathematical persuasion. Dag Prawitz also writes a chapter in which he explains his current views on the epistemic dimension of proofs and addresses the question why some inferences succeed in conferring evidence on their conclusions when applied to premises for which one already possesses evidence.

Modern mathematical logic would not exist without the analytical tools first developed by George Boole in The Mathematical Analysis of Logic and The Laws of Thought. The influence of the Boolean school on the development of logic, always recognised but long underestimated, has recently become a major research topic. This collection is the first anthology of works on Boole. It contains two works published in 1865, the year of Boole's death, but never reprinted, as well as several classic studies of recent decades and ten original contributions appearing here for the first time. From the programme of the English Algebraic School to Boole's use of operator methods, from the problem of interpretability to that of psychologism, a full range of issues is covered. The Boole Anthology is indispensable to Boole studies and will remain so for years to come.

Natural duality theory is one of the major growth areas within general algebra. This text provides a short path to the forefront of research in duality theory. It presents a coherent approach to new results in the area, as well as exposing open problems.

Unary algebras play a special role throughout the text. Individual unary algebras are relatively simple and easy to work with. But as a class they have a rich and complex entanglement with dualisability. This combination of local simplicity and global complexity ensures that, for the study of natural duality theory, unary algebras are an excellent source of examples and counterexamples.

A number of results appear here for the first time. In particular, the text ends with an appendix that provides a new and definitive approach to the concept of the rank of a finite algebra and its relationship with strong dualisability.

This superb exposition of a complex subject examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

Goguen categories extend the relational calculus and its categorical formalization to the fuzzy world. Starting from the fundamental concepts of sets, binary relations and lattices this book introduces several categorical formulations of an abstract theory of relations such as allegories, Dedekind categories and related structures. It is shown that neither theory is sufficiently rich to describe basic operations on fuzzy relations. The book then introduces Goguen categories and provides a comprehensive study of these structures including their representation theory, and the definability of norm-based operations. The power of the theory is demonstrated by a comprehensive example. A certain Goguen category is used to specify and to develop a fuzzy controller. Based on its abstract description as well as certain desirable properties and their formal proofs, a verified controller is derived without compromising the - sometimes - intuitive choice of norm-based operations by fuzzy engineers.

New discoveries about algorithms are leading scientists beyond the Church-Turing Thesis, which governs the "algorithmic universe" and asserts the conventionality of recursive algorithms. A new paradigm for computation, the super-recursive algorithm, offers promising prospects for algorithms of much greater computing power and efficiency.
Super-Recursive Algorithms provides an accessible, focused examination of the theory of super-recursive algorithms and its ramifications for the computer industry, networks, artificial intelligence, embedded systems, and the Internet. The book demonstrates how these algorithms are more appropriate as mathematical models for modern computers, and how these algorithms present a better framework for computing methods in such areas as numerical analysis, array searching, and controlling and monitoring systems. In addition, a new practically-oriented perspective on the theory of algorithms, computation, and automata, as a whole, is developed. Problems of efficiency, software development, parallel and distributed processing, pervasive and emerging computation, computer architecture, machine learning, brain modeling, knowledge discovery, and intelligent systems are addressed.
Topics and Features:
* Encompasses and systematizes all main classes of super-recursive algorithms and the theory behind them

* Describes the strengthening link between the theory of super-recursive algorithms and actual algorithms close to practical realization

* Examines the theory's basis as a foundation for advancements in computing, information science, and related technologies

* Encompasses and systematizes all main types of mathematical models of algorithms

* Highlights how super-recursive algorithms pave the way for more advanced design, utilization, and maintenance of computers

* Examines and restructures the existing variety of mathematical models of complexity of algorithms and computation, introducing new models

* Possesses a comprehensive bibliography and index
This clear exposition, motivated by numerous examples and illustrations, serves to develop a new paradigm for complex, high-performance computing based on both partial recursive functions and more inclusive recursive algorithms. Researchers and advanced students interested in theory of computation and algorithms will find the book an essential resource for an important new class of algorithms.

Mathematics and logic have been central topics of concern since the dawn of philosophy. Since logic is the study of correct reasoning, it is a fundamental branch of epistemology and a priority in any philosophical system. Philosophers have focused on mathematics as a case study for general philosophical issues and for its role in overall knowledge- gathering. Today, philosophy of mathematics and logic remain central disciplines in contemporary philosophy, as evidenced by the regular appearance of articles on these topics in the best mainstream philosophical journals; in fact, the last decade has seen an explosion of scholarly work in these areas.
This volume covers these disciplines in a comprehensive and accessible manner, giving the reader an overview of the major problems, positions, and battle lines. The 26 contributed chapters are by established experts in the field, and their articles contain both exposition and criticism as well as substantial development of their own positions. The essays, which are substantially self-contained, serve both to introduce the reader to the subject and to engage in it at its frontiers. Certain major positions are represented by two chapters--one supportive and one critical.
The Oxford Handbook of Philosophy of Math and Logic is a ground-breaking reference like no other in its field. It is a central resource to those wishing to learn about the philosophy of mathematics and the philosophy of logic, or some aspect thereof, and to those who actively engage in the discipline, from advanced undergraduates to professional philosophers, mathematicians, and historians.

An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language, thus introducing readers to new classes of algorithms which may be analysed more precisely than was the case until now. The book is as self-contained as possible and includes a great deal of background material. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest.

This book is for researchers in computer science, mathematical logic, and philosophical logic. It shows the state of the art in current investigations of process calculi with mainly two major paradigms at work: linear logic and modal logic. The combination of approaches and pointers for further integration also suggests a grander vision for the field.

Poland has played an enormous role in the development of mathematical logic. Leading Polish logicians, like Lesniewski, Lukasiewicz and Tarski, produced several works related to philosophical logic, a field covering different topics relevant to philosophical foundations of logic itself, as well as various individual sciences. This collection presents contemporary Polish work in philosophical logic which in many respects continue the Polish way of doing philosophical logic. This book will be of interest to logicians, mathematicians, philosophers, and linguists.

The classical theory of computation has its origins in the work of Goedel, Turing, Church, and Kleene and has been an extraordinarily successful framework for theoretical computer science. The thesis of this book, however, is that it provides an inadequate foundation for modern scientific computation where most of the algorithms are real number algorithms. The goal of this book is to develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing. Along the way, the authors consider such fundamental problems as: * Is the Mandelbrot set decidable? * For simple quadratic maps, is the Julia set a halting set? * What is the real complexity of Newton's method? * Is there an algorithm for deciding the knapsack problem in a ploynomial number of steps? * Is the Hilbert Nullstellensatz intractable? * Is the problem of locating a real zero of a degree four polynomial intractable? * Is linear programming tractable over the reals? The book is divided into three parts: The first part provides an extensive introduction and then proves the fundamental NP-completeness theorems of Cook-Karp and their extensions to more general number fields as the real and complex numbers. The later parts of the book develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing.

The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.

Since their appearance in the late 19th century, the Cantor--Dedekind theory of real numbers and philosophy of the continuum have emerged as pillars of standard mathematical philosophy. On the other hand, this period also witnessed the emergence of a variety of alternative theories of real numbers and corresponding theories of continua, as well as non-Archimedean geometry, non-standard analysis, and a number of important generalizations of the system of real numbers, some of which have been described as arithmetic continua of one type or another. With the exception of E.W. Hobson's essay, which is concerned with the ideas of Cantor and Dedekind and their reception at the turn of the century, the papers in the present collection are either concerned with or are contributions to, the latter groups of studies. All the contributors are outstanding authorities in their respective fields, and the essays, which are directed to historians and philosophers of mathematics as well as to mathematicians who are concerned with the foundations of their subject, are preceded by a lengthy historical introduction.

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.

without a properly developed inconsistent calculus based on infinitesimals, then in consistent claims from the history of the calculus might well simply be symptoms of confusion. This is addressed in Chapter 5. It is further argued that mathematics has a certain primacy over logic, in that paraconsistent or relevant logics have to be based on inconsistent mathematics. If the latter turns out to be reasonably rich then paraconsistentism is vindicated; while if inconsistent mathematics has seri ous restriytions then the case for being interested in inconsistency-tolerant logics is weakened. (On such restrictions, see this chapter, section 3. ) It must be conceded that fault-tolerant computer programming (e. g. Chapter 8) finds a substantial and important use for paraconsistent logics, albeit with an epistemological motivation (see this chapter, section 3). But even here it should be noted that if inconsistent mathematics turned out to be functionally impoverished then so would inconsistent databases. 2. Summary In Chapter 2, Meyer's results on relevant arithmetic are set out, and his view that they have a bearing on G8del's incompleteness theorems is discussed. Model theory for nonclassical logics is also set out so as to be able to show that the inconsistency of inconsistent theories can be controlled or limited, but in this book model theory is kept in the background as much as possible. This is then used to study the functional properties of various equational number theories."

This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.

Reasoning under uncertainty is always based on a specified language or for malism, including its particular syntax and semantics, but also on its associated inference mechanism. In the present volume of the handbook the last aspect, the algorithmic aspects of uncertainty calculi are presented. Theory has suffi ciently advanced to unfold some generally applicable fundamental structures and methods. On the other hand, particular features of specific formalisms and ap proaches to uncertainty of course still influence strongly the computational meth ods to be used. Both general as well as specific methods are included in this volume. Broadly speaking, symbolic or logical approaches to uncertainty and nu merical approaches are often distinguished. Although this distinction is somewhat misleading, it is used as a means to structure the present volume. This is even to some degree reflected in the two first chapters, which treat fundamental, general methods of computation in systems designed to represent uncertainty. It has been noted early by Shenoy and Shafer, that computations in different domains have an underlying common structure. Essentially pieces of knowledge or information are to be combined together and then focused on some particular question or domain. This can be captured in an algebraic structure called valuation algebra which is described in the first chapter. Here the basic operations of combination and focus ing (marginalization) of knowledge and information is modeled abstractly subject to simple axioms."

This book is the final version of a course on algorithmic information theory and the epistemology of mathematics and physics. It discusses Einstein and Goedel's views on the nature of mathematics in the light of information theory, and sustains the thesis that mathematics is quasi-empirical. There is a foreword by Cris Calude of the University of Auckland, and supplementary material is available at the author's web site. The special feature of this book is that it presents a new "hands on" didatic approach using LISP and Mathematica software. The reader will be able to derive an understanding of the close relationship between mathematics and physics. "The Limits of Mathematics is a very personal and idiosyncratic account of Greg Chaitin's entire career in developing algorithmic information theory. The combination of the edited transcripts of his three introductory lectures maintains all the energy and content of the oral presentations, while the material on AIT itself gives a full explanation of how to implement Greg's ideas on real computers for those who want to try their hand at furthering the theory." (John Casti, Santa Fe Institute)

Alfred Tarski was one of the two giants of the twentieth-century development of logic, along with Kurt Goedel. The four volumes of this collection contain all of Tarski's published papers and abstracts, as well as a comprehensive bibliography. Here will be found many of the works, spanning the period 1921 through 1979, which are the bedrock of contemporary areas of logic, whether in mathematics or philosophy. These areas include the theory of truth in formalized languages, decision methods and undecidable theories, foundations of geometry, set theory, and model theory, algebraic logic, and universal algebra.