Future Data and Knowledge Base Systems will require new functionalities: richer data modelling capabilities, more powerful query languages, and new concepts of query answers. Future query languages will include functionalities such as hypothetical reasoning, abductive reasoning, modal reasoning, and metareasoning, involving knowledge and belief. Intentional answers will lead to cooperative query answering in which the answer to a query takes into consideration user's expectations. Non-classical logic plays an important role in this book for the formalization of new queries and new answers. It is shown how logic permits precise definitions for concepts like cooperative answers, subjective queries, or reliable sources of information, and gives a precise framework for reasoning about these complex concepts. It is worth noting that advances in knowledge management are not just an application domain for existing results in logic, but also require new developments in logic. The book is organized into 10 chapters which cover the areas of cooperative query answering (in the first three chapters), metareasoning and abductive reasoning (chapters 5 to 7), and, finally, hypothetical and subjunctive reasoning (last three chapters).

This textbook explains the basic principles of categorical type theory and the techniques used to derive categorical semantics for specific type theories. It introduces the reader to ordered set theory, lattices and domains, and this material provides plenty of examples for an introduction to category theory, which covers categories, functors, natural transformations, the Yoneda lemma, cartesian closed categories, limits, adjunctions and indexed categories. Four kinds of formal system are considered in detail, namely algebraic, functional, polymorphic functional, and higher order polymorphic functional type theory. For each of these the categorical semantics are derived and results about the type systems are proved categorically. Issues of soundness and completeness are also considered. Aimed at advanced undergraduates and beginning graduates, this book will be of interest to theoretical computer scientists, logicians and mathematicians specializing in category theory.

This textbook explains the basic principles of categorical type theory and the techniques used to derive categorical semantics for specific type theories. It introduces the reader to ordered set theory, lattices and domains, and this material provides plenty of examples for an introduction to category theory, which covers categories, functors, natural transformations, the Yoneda lemma, cartesian closed categories, limits, adjunctions and indexed categories. Four kinds of formal system are considered in detail, namely algebraic, functional, polymorphic functional, and higher order polymorphic functional type theory. For each of these the categorical semantics are derived and results about the type systems are proved categorically. Issues of soundness and completeness are also considered. Aimed at advanced undergraduates and beginning graduates, this book will be of interest to theoretical computer scientists, logicians and mathematicians specializing in category theory.

The International Workshop on Combinatorial Algorithms was established in 1989 as the Australasian Workshop on Combinatorial Algorithms. As a consequence of the workshop's success in attracting mathematicians and computer scientists from around the world, it was decided at the 2006 meeting to go global, to change the workshop's name, and to hold it in appropriate venues around the world. The workshop supports basic research on the interface between mathematics and computing, specifically * Algorithms & Data Structures * Complexity Theory * Algorithms on Graphs & Strings * Combinatorial Optimization * Cryptography & Information Security * Computational Biology * Communications Networks and many other related areas. This is Volume 2 in the series of IWOCA proceedings. See http://www.iwoca.org/

Readers of this volume are invited on a journey through a logician's life, as witnessed by his colleagues and friends. They will have the opportunity to immerse themselves in the regions of set theory, arithmetic, data analysis, algebra, fuzzy logic and other topics that Petr Hajek has shared with the contributors. Each of the contributions is unique in its approach as well as its personal envoi, helping to create a full-blooded, vivid and genuine picture of the man who has been so emphatically influential to so many of us. Mature and fresh ideas blend in the texts which will, hopefully, make an interesting and enjoyable reading for Petr Hajek as well as for any keen logician.

This book principally concerns the rapidly growing area of what might be termed "Logical Complexity Theory": the study of bounded arithmetic, propositional proof systems, length of proof, and similar themes, and the relations of these topics to computational complexity theory. Issuing from a two-year international collaboration, the book contains articles concerning the existence of the most general unifier, a special case of Kreisel's conjecture on length-of-proof, propositional logic proof size, a new alternating logtime algorithm for boolean formula evaluation and relation to branching programs, interpretability between fragments of arithmetic, feasible interpretability, provability logic, open induction, Herbrand-type theorems, isomorphism between first and second order bounded arithmetics, forcing techniques in bounded arithmetic, and ordinal arithmetic in *L *D o. Also included is an extended abstract of J.P. Ressayre's new approach concerning the model completeness of the theory of real closed exponential fields. Additional features of the book include the transcription and translation of a recently discovered 1956 letter from Kurt Godel to J. von Neumann, asking about a polynomial time algorithm for the proof in k-symbols of predicate calculus formulas (equivalent to the P-NP question); and an open problem list consisting of seven fundamental and 39 technical questions contributed by many researchers, together with a bibliography of relevant references. This scholarly work will interest mathematical logicians, proof and recursion theorists, and researchers in computational complexity.

The Many Sides of Logic'' is a volume containing a selection of the papers delivered at three simultaneous events held between 11-17 May 2008 in Paraty, RJ, Brazil, continuing a tradition of three decades of Brazilian and Latin-American meetings and celebrating the 30th anniversary of an institution congenital with the mature interest for logic, epistemology and history of sciences in Brazil: CLE 30 - 30th Anniversary of the Centre for Logic, Epistemology and the History of Science at the State University of Campinas (UNICAMP) XV EBL -15th Brazilian Logic Conference XIV SLALM - 14th Latin-American Symposium on Mathematical Logic Several renowned logicians, philosophers and mathematicians gathered in colonial Paraty, a historic village on the Brazilian coast founded in the 17th Century and surrounded by the luscious Atlantic rain forest to deliver lectures and talks celebrating the many sides of logic: the philosophical, the mathematical, the computational, the historical, and the multiple facets therein. The topics of the joint conferences, well represented here, included philosophical and mathematical Logic and applications with emphasis on model theory and proof theory, set theory, non-classical logics and applications, history and philosophy of logic, philosophy of the formal sciences and issues on the foundations of mathematics. The events have been preceded by a Logic School planned for students and young researchers held at the UNICAMP campus in Campinas, SP.

This is an up-to-date and integrated introduction to model theory, designed to be used for graduate courses (for students who are familiar with first-order logic), and as a reference for more experienced logicians and mathematicians. Model theory is concerned with the notions of definition, interpretation and structure in a very general setting, and is applied to a wide variety of other areas such as set theory, geometry, algebra (in particular group theory), and computer science (e.g. logic programming and specification). Professor Hodges emphasises definability and methods of construction, and introduces the reader to advanced topics such as stability. He also provides the reader with much historical information and a full bibliography, enhancing the book's use as a reference.

By considering the size of the logical network needed to perform a given computational task, the intrinsic difficulty of that task can be examined. Boolean function complexity, the combinatorial study of such networks, is a subject that started back in the 1950s and has today become one of the most challenging and vigorous areas of theoretical computer science. The papers in this book stem from the London Mathematical Society Symposium on Boolean Function Complexity held at Durham University in July 1990. The range of topics covered will be of interest to the newcomer to the field as well as the expert, and overall the papers are representative of the research presented at the Symposium. Anyone with an interest in Boolean Function complexity will find that this book is a necessary purchase.

Non-classical views about important issues in logic and its philosophy are a distinctive trait of Shahid Rahman's work. This volume has been designed, on the occasion of his 50th birthday, as a gathering place for unconventional approaches, original ideas and attempts to question well-established standards. Some of the world top philosophers and logicians contributed to a brilliant collection of papers, some of which doubtlessly leave their mark on the work to come in logic and in philosophy of formal sciences. Contributors are: Philippe Balbiani, Diderik Batens, Johan van Benthem, Giacomo Bonanno, Walter A. Carnielli, Newton C. A. Da Costa, Michel Crubellier, Francisco A. Doria, Dov M. Gabbay, Olivier Gasquet, Gerhard Heinzmann, Andreas Herzig, Jaakko Hintikka, Justine Jacot, Reinhard Kahle, Erik C. W. Krabbe, D cio Krause, Franck Lihoreau, Kuno Lorenz, Ilkka Niiniluoto, Graham Priest, Stephen Read, Manuel Rebuschi, Greg Restall, Gabriel Sandu, Gerhard Schurz, Fran ois Schwarzentruber, Yaroslav Shramko, G ran Sundholm, John Symons, Christian Thiel, Nicolas Troquard, Tero Tulenheimo, Jean Paul Van Bendegem, Daniel Vanderveken, Yde Venema, Heinrich Wansing, Jan Wolenski and John Woods.

This book is concerned with techniques for formal theorem-proving, with particular reference to Cambridge LCF (Logic for Computable Functions). Cambridge LCF is a computer program for reasoning about computation. It combines the methods of mathematical logic with domain theory, the basis of the denotational approach to specifying the meaning of program statements. Cambridge LCF is based on an earlier theorem-proving system, Edinburgh LCF, which introduced a design that gives the user flexibility to use and extend the system. A goal of this book is to explain the design, which has been adopted in several other systems. The book consists of two parts. Part I outlines the mathematical preliminaries, elementary logic and domain theory, and explains them at an intuitive level, giving reference to more advanced reading; Part II provides sufficient detail to serve as a reference manual for Cambridge LCF. It will also be a useful guide for implementors of other programs based on the LCF approach.

The study of permutation groups has always been closely associated with that of highly symmetric structures. The objects considered here are countably infinite, but have only finitely many different substructures of any given finite size. They are precisely those structures which are determined by first-order logical axioms together with the assumption of countability. This book concerns such structures, their substructures and their automorphism groups. A wide range of techniques are used: group theory, combinatorics, Baire category and measure among them. The book arose from lectures given at a research symposium and retains their informal style, whilst including as well many recent results from a variety of sources. It concludes with exercises and unsolved research problems.

Advances in Modal Logic is a unique international forum for presenting the latest results and new directions of research in Modal Logic broadly conceived. The topics dealt with are of interdisciplinary interest and range from mathematical, computational, and philosophical problems to applications in knowledge representation and formal linguistics. This volume contains invited and contributed papers from the seventh conference in the AiML series, held in Nancy, France, in September 2008. It reports on substantial advances, both in the foundations of modal logic and in a number of application areas. It includes papers on the metatheory of a variety of modal logics; on systems for spatial and temporal reasoning and interpreting natural language; on the emerging coalgebraic perspective; and on historical views of the nature of modality.

Included in this volume are two essays on the theory of numbers: "Continuity and Irrational Numbers" and "The Nature and Meaning of Numbers." The text is an authorized translation by Wooster Woodruff Beman, Professor of Mathematics in the University of Michigan.

Here is an introductory textbook which is designed to be useful not only to intending logicians but also to mathematicians in general. Based on Dr Hamilton's lectures to third and fourth year undergraduate mathematicians at the University of Stirling it has been written to introduce student or professional mathematicians, whose background need cover no more than a typical first year undergraduate mathematics course, to the techniques and principal results of mathematical logic. In presenting the subject matter without bias towards particular aspects, applications or developments, an attempt has been made to place it in the context of mathematics and to emphasise the relevance of logic to the mathematician. Starting at an elementart level, the text progresses from informal discussion to the precise description and use of formal mathematical and logical systems. The early chapters cover propositional and predicate calculus. The later chapters deal with Goedel's theorem on the incompleteness of arithmetic and with various undecidability and unsolvability results, including a discussion of Turing machines and abstract computability. Each section ends with exercises designed to clarify and consolidate the material in that section. Hints or solutions to many of these are provided at the end of the book. The revision of this very successful textbook includes new sections on Skolemisation and applying well-formed formulas to logic programming. Some corrections have been made and extra exercises added.

In recent years the interplay between model theory and other branches of mathematics has led to many deep and intriguing results. In this, the first book on the topic, the theme is the interplay between model theory and the theory of modules. The book is intended to be a self-contained introduction to the subject and introduces the requisite model theory and module theory as it is needed. Dr Prest develops the basic ideas concerning what can be said about modules using the information which may be expressed in a first-order language. Later chapters discuss stability-theoretic aspects of modules, and structure and classification theorems over various types of rings and for certain classes of modules. Both algebraists and logicians will enjoy this account of an area in which algebra and model theory interact in a significant way. The book includes numerous examples and exercises and consequently will make an ideal introduction for graduate students coming to this subject for the first time.

In this 1987 text Professor Jech gives a unified treatment of the various forcing methods used in set theory, and presents their important applications. Product forcing, iterated forcing and proper forcing have proved powerful tools when studying the foundations of mathematics, for instance in consistency proofs. The book is based on graduate courses though some results are also included, making the book attractive to set theorists and logicians.

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability problems are algorithmically solvable for restricted subsets--or, as we say, fragments--of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees.

This book develops arithmetic without the induction principle, working in theories that are interpretable in Raphael Robinson's theory Q. Certain inductive formulas, the bounded ones, are interpretable in Q. A mathematically strong, but logically very weak, predicative arithmetic is constructed. Originally published in 1986. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These editions preserve the original texts of these important books while presenting them in durable paperback and hardcover editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905.

Using set theory in the first part of his book, and proof theory in the second, Gaisi Takeuti gives us two examples of how mathematical logic can be used to obtain results previously derived in less elegant fashion by other mathematical techniques, especially analysis. In Part One, he applies Scott- Solovay's Boolean-valued models of set theory to analysis by means of complete Boolean algebras of projections. In Part Two, he develops classical analysis including complex analysis in Peano's arithmetic, showing that any arithmetical theorem proved in analytic number theory is a theorem in Peano's arithmetic. In doing so, the author applies Gentzen's cut elimination theorem. Although the results of Part One may be regarded as straightforward consequences of the spectral theorem in function analysis, the use of Boolean- valued models makes explicit and precise analogies used by analysts to lift results from ordinary analysis to operators on a Hilbert space. Essentially expository in nature, Part Two yields a general method for showing that analytic proofs of theorems in number theory can be replaced by elementary proofs. Originally published in 1978. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These editions preserve the original texts of these important books while presenting them in durable paperback and hardcover editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905.

Advances in Modal Logic is a unique international forum for presenting the latest results and new directions of research in modal logic broadly conceived. The topics dealt with are of interdisciplinary interest and range from mathematical, computational, and philosophical problems to applications in knowledge representation and formal linguistics. This volume contains invited and contributed papers from the sixth conference in the series, held for the first time outside Europe, in Noosa, Queensland, Australia, in September 2006. It reports on considerable progress, both in the foundations of modal logic and in a number of application areas. It includes papers on the theory of modal logic itself, on process theory, multi-agent systems and spatial reasoning, and work on quantified modal logic, modal reasoning methods, and philosophical issues.

This book provides an invaluable overview of the reach of logic. It provides reference to some of the most important, well-established results in logic, while at the same time offering insight into the latest research issues in the area. It also has a balance of theory and practice, containing essays in the areas of Modal Logic, Intuitionistic Logic, Logic and Language, Non-monotonic Logic and Logic Programming, Temporal Logic, Logic and Learning, Combination of Logics, Practical Reasoning, Logic and Artificial Intelligence, Abduction, Theorem Proving, and Goal-Directed Reasoning. It will be invaluable reading for researchers and graduate students in Logic and Computer Science, and a fabulous source of inspiration for research students in search of a topic for a PhD in logic and theoretical computer science.

This book provides an invaluable overview of the reach of logic. It provides reference to some of the most important, well-established results in logic, while at the same time offering insight into the lattest research issues in the area. It also has a balance of theory and practice, containing essays in the areas of Modal Logic, Intuitionistic Logic, Logic and Language, Non-monotonic Logic and Logic Programming, Temporal Logic, Logic and Learning, Combination of Logics, Practical Reasoning, Logic and Artificial Intelligence, Abduction, Theorem Proving, and Goal-Directed Reasoning. It will be invaluable reading for researchers and graduate students in Logic and Computer Science, and a fabulous source of inspiration for research students in search of a topic for a PhD in logic or theoretical computer science.

· Are you more likely to become a professional footballer if your surname is Ball? · How can you be one hundred per cent sure you will win a bet? · Why did so many Pompeiians stay put while Mount Vesuvius was erupting? · How do you prevent a nuclear war? Ever since the dawn of human civilisation, we have been trying to make predictions about what's in store for us. We do this on a personal level, so that we can get on with our lives efficiently (should I hang my laundry out to dry, or will it rain?). But we also have to predict on a much larger scale, often for the good of our broader society (how can we spot economic downturns or prevent terrorist attacks?). For just as long, we have been getting it wrong. From religious oracles to weather forecasters, and from politicians to economists, we are subjected to poor predictions all the time. Our job is to separate the good from the bad. Unfortunately, the foibles of our own biology - the biases that ultimately make us human - can let us down when it comes to making rational inferences about the world around us. And that can have disastrous consequences. How to Expect the Unexpected will teach you how and why predictions go wrong, help you to spot phony forecasts and give you a better chance of getting your own predictions correct.