This volume presents the proceedings from the Eleventh Brazilian Logic Conference on Mathematical Logic held by the Brazilian Logic Society 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)

Logic has pride of place in mathematics and its 20th century offshoot, computer science. Modern symbolic logic was developed, in part, as a way to provide a formal framework for mathematics: Frege, Peano, Whitehead and Russell, as well as Hilbert developed systems of logic to formalize mathematics. These systems were meant to serve either as themselves foundational, or at least as formal analogs of mathematical reasoning amenable to mathematical study, e.g., in Hilbert’s consistency program. Similar (...) efforts continue, but have been expanded by the development of sophisticated methods to study the properties of such systems using proof and model theory. In parallel with this evolution of logical formalisms as tools for articulating mathematical theories (broadly speaking), much progress has been made in the quest for a mechanization of logical inference and the investigation of its theoretical limits, culminating recently in the development of new foundational frameworks for mathematics with sophisticated computer-assisted proof systems. In addition, logical formalisms developed by logicians in mathematical and philosophical contexts have proved immensely useful in describing theories and systems of interest to computer scientists, and to some degree, vice versa. Three examples of the influence of logic in computer science are automated reasoning, computer verification, and type systems for programming languages. (shrink)

Mathematical Logic 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 Handbook is a combination of authoritative exposition, comprehensive survey, and fundamental research exploring the underlying unifying themes in the various areas. The intended audience is graduate students and researchers in the areas of computing and logic, as well as other people interested in the subject. We assume as background some mathematical sophistication. Much of the material will also be of interest to logicians and mathematicians.

Preface -- 1. Propositional logic : proofs from axioms and inference rules -- 2. First order logic : proofs with quantifiers -- 3. Set theory : proofs by detachment, contraposition, and contradiction -- 4. Mathematical induction : definitions and proofs by induction -- 5. Well-formed sets : proofs by transfinite induction with already well-ordered sets -- 6. The axiom of choice : proofs by transfinite induction -- 7. applications : Nobel-Prize winning applications of sets, functions, and relations -- 8. Solutions (...) to some odd-numbered exercises. (shrink)

Many books explain what is known about the universe. This book investigates what cannot be known. Rather than exploring the amazing facts that science, mathematics, and reason have revealed to us, this work studies what science, mathematics, and reason tell us cannot be revealed. In The Outer Limits of Reason, Noson Yanofsky considers what cannot be predicted, described, or known, and what will never be understood. He discusses the limitations of computers, physics, logic, and our own (...) thought processes. Yanofsky describes simple tasks that would take computers trillions of centuries to complete and other problems that computers can never solve; perfectly formed English sentences that make no sense; different levels of infinity; the bizarre world of the quantum; the relevance of relativity theory; the causes of chaos theory; math problems that cannot be solved by normal means; and statements that are true but cannot be proven. He explains the limitations of our intuitions about the world -- our ideas about space, time, and motion, and the complex relationship between the knower and the known. Moving from the concrete to the abstract, from problems of everyday language to straightforward philosophical questions to the formalities of physics and mathematics, Yanofsky demonstrates a myriad of unsolvable problems and paradoxes. Exploring the various limitations of our knowledge, he shows that many of these limitations have a similar pattern and that by investigating these patterns, we can better understand the structure and limitations of reason itself. Yanofsky even attempts to look beyond the borders of reason to see what, if anything, is out there. (shrink)

Depending on what one means by the main connective of logic, the -if..., then... -, several systems of logic result: classic and modal logics, intuitionistic logic or relevance logic. This book presents the underlying ideas, the syntax and the semantics of these logics. Soundness and completeness are shown constructively and in a uniform way. Attention is paid to the interdisciplinary role of logic: its embedding in the foundations of mathematics and its intimate connection with philosophy, in particular the philosophy (...) of language. Set theory is presented both as a conditio sine qua non for logic and as a interesting exact ontology. The study of infinite sets yields perplexing results. Formalization of informal number theory results in formal number theory; Godel's incompleteness is treated. At appropriate places attention is paid to paradoxes, intuitionism, conditionals, the historical development of logic, to logic programming and automated theorem proving for classical logic.". (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its (...) applications and thus presents the state of the art in the area. (shrink)

This volume presents the proceedings of the workshop CSL '91 (Computer Science Logic) held at the University of Berne, Switzerland, October 7-11, 1991. This was the fifth in a series of annual workshops on computer sciencelogic (the first four are recorded in LNCS volumes 329, 385, 440, and 533). The volume contains 33 invited and selected papers on a variety of logical topics in computer science, including abstract datatypes, bounded theories, complexity results, cut elimination, denotational (...) semantics, infinitary queries, Kleene algebra with recursion, minimal proofs, normal forms in infinite-valued logic, ordinal processes, persistent Petri nets, plausibility logic, program synthesis systems, quantifier hierarchies, semantics of modularization, stable logic, term rewriting systems, termination of logic programs, transitive closure logic, variants of resolution, and many others. (shrink)

This workshop on stochastic theory and adaptive control assembled many of the leading researchers on stochastic control and stochastic adaptive control to increase scientific exchange and cooperative research between these two subfields of stochastic analysis. The papers included in the proceedings include survey and research. They describe both theoretical results and applications of adaptive control. There are theoretical results in identification, filtering, control, adaptive control and various other related topics. Some applications to manufacturing systems, queues, networks, medicine and other topics (...) are gien. (shrink)

Computational methods such as computer simulations, Monte Carlo methods, and agent-based modeling have become the dominant techniques in many areas of science. Extending Ourselves contains the first systematic philosophical account of these new methods, and how they require a different approach to scientific method. Paul Humphreys draws a parallel between the ways in which such computational methods have enhanced our abilities to mathematically model the world, and the more familiar ways in which scientific instruments have expanded our access (...) to the empirical world. This expansion forms the basis for a new kind of empiricism, better suited to the needs of science than the older anthropocentric forms of empiricism. Human abilities are no longer the ultimate standard of epistemological correctness.Humphreys also includes arguments for the primacy of properties rather than objects, the need to consider technological constraints when appraising scientific methods, and a detailed account of how the path from computational template to scientific application is constructed. This last feature allows us to hold a form of selective realism in which anti-realist arguments based on formal reconstructions of theories can be avoided. One important consequence of the rise of computational methods is that the traditional organization of the sciences is being replaced by an organization founded on computational templates.Extending Ourselves will be of interest to philosophers of science, epistemologists, and to anyone interested in the role played by computers in modern science. (shrink)

We characterize abstraction in computer science by first comparing the fundamental nature of computer science with that of its cousin mathematics. We consider their primary products, use of formalism, and abstraction objectives, and find that the two disciplines are sharply distinguished. Mathematics, being primarily concerned with developing inference structures, has information neglect as its abstraction objective. Computer science, being primarily concerned with developing interaction patterns, has information hiding as its abstraction objective. We (...) show that abstraction through information hiding is a primary factor in computer science progress and success through an examination of the ubiquitous role of information hiding in programming languages, operating systems, network architecture, and design patterns. (shrink)

Demonstrating the different roles that logic plays in the disciplines of computer science, mathematics, and philosophy, this concise undergraduate textbook covers select topics from three different areas of logic: proof theory, computability theory, and nonclassical logic. The book balances accessibility, breadth, and rigor, and is designed so that its materials will fit into a single semester. Its distinctive presentation of traditional logic material will enhance readers' capabilities and mathematical maturity. The proof theory portion presents classical propositional logic (...) and first-order logic using a computer-oriented (resolution) formal system. Linear resolution and its connection to the programming language Prolog are also treated. The computability component offers a machine model and mathematical model for computation, proves the equivalence of the two approaches, and includes famous decision problems unsolvable by an algorithm. The section on nonclassical logic discusses the shortcomings of classical logic in its treatment of implication and an alternate approach that improves upon it: Anderson and Belnap's relevance logic. Applications are included in each section. The material on a four-valued semantics for relevance logic is presented in textbook form for the first time. Aimed at upper-level undergraduates of moderate analytical background, Three Views of Logic will be useful in a variety of classroom settings. Gives an exceptionally broad view of logic. Treats traditional logic in a modern format. Presents relevance logic with applications. Provides an ideal text for a variety of one-semester upper-level undergraduate courses. (shrink)

The prelims comprise: Introduction Computer Science and Mathematics The Formal Verification Debate Abstraction in Computer Science Conclusion.

This is a concise book that introduces students to the basics of logical thinking and important mathematical structures that are critical for a solid understanding of logical formalisms themselves as well as for building the necessary background to tackle other fields that are based on these logical principles. Despite its compact and small size, it includes many solved problems and quite a few end-of-section exercises that will help readers consolidate their understanding of the material. This textbook is essential reading for (...) anyone interested in the logical foundations of Informatics, Computer Science, Data Science, Artificial Intelligence, and other related areas. Written with undergraduate students in these disciplines in mind, this book can very well serve the needs of interested and curious readers who wish to get a grasp of the logical principles upon which these fields are built. This book does not require readers to possess math skills beyond those learned in high school. (shrink)

This is a review of Yves Nievergelt, Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Birkäuser Verlag, Boston, 2002, €90, pp. 480, ISBN 0-8176-4249-8, hardcover.

The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second (...) recursion theorem, I prove that it is mathematically possible for us to be in a simulation that is being run on a computer \textit{by us}. In such a case, there would be two identical instances of us; the question of which of those is ``really us'' is meaningless. I also show how Rice's theorem provides some interesting impossibility results concerning simulation and self-simulation; briefly describe the philosophical implications of fully homomorphic encryption for (self-)simulation; briefly investigate the graphical structure of universes simulating universes simulating universes, among other issues. I end by describing some of the possible avenues for future research that this preliminary investigation reveals. (shrink)

The process of constructing mathematical models is examined and a case made that the construction process is an integral part of the justification for the model. The role of heuristics in testing and modifying models is described and some consequences for scientific methodology are drawn out. Three different ways of constructing the same model are detailed to demonstrate the claims made here.

This festschrift volume is dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday. For over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central areas of theoretical computer science. He is universally admired as a founding father and long-standing pillar of the discipline of computer science. On Friday, 28 April 2006, the School of Computer Science at Tel Aviv University held a “Computation Day Celebrating Boaz (...) (Boris) Trakhtenbrot's Eighty-Fifth Birthday”. As a follow-up to that event, his students and colleagues were asked to contribute to a volume in his honor and in recognition of his grand contributions to the field. The book opens with two historical overviews and a bibliography. These are followed by 33 thoroughly reviewed technical contributions. The broad range of topics covered include mathematical logic, logics for computer science, mathematics for computer science, automata and formal languages, asynchronous computation, semantics of programming languages, verification, and software engineering. This tapestry of subjects stands as testimony to the vast scope of Trakhtenbrot's achievements and the profound influence he has had on the field. (shrink)

This textbook is a logic manual which includes an elementary course and an advanced course. It covers more than most introductory logic textbooks, while maintaining a comfortable pace that students can follow. The technical exposition is clear, precise and follows a paced increase in complexity, allowing the reader to get comfortable with previous definitions and procedures before facing more difficult material. The book also presents an interesting overall balance between formal and philosophical discussion, making it suitable for both philosophy and (...) more formal/science oriented students. This textbook is of great use to undergraduate philosophy students, graduate philosophy students, logic teachers, undergraduates and graduates in mathematics, computer science or related fields in which logic is required. (shrink)

We examine the philosophical disputes among computer scientists concerning methodological, ontological, and epistemological questions: Is computer science a branch of mathematics, an engineering discipline, or a natural science? Should knowledge about the behaviour of programs proceed deductively or empirically? Are computer programs on a par with mathematical objects, with mere data, or with mental processes? We conclude that distinct positions taken in regard to these questions emanate from distinct sets of received beliefs or paradigms (...) within the discipline: – The rationalist paradigm, which was common among theoretical computer scientists, defines computer science as a branch of mathematics, treats programs on a par with mathematical objects, and seeks certain, a priori knowledge about their ‘correctness’ by means of deductive reasoning. – The technocratic paradigm, promulgated mainly by software engineers and has come to dominate much of the discipline, defines computer science as an engineering discipline, treats programs as mere data, and seeks probable, a posteriori knowledge about their reliability empirically using testing suites. – The scientific paradigm, prevalent in the branches of artificial intelligence, defines computer science as a natural (empirical) science, takes programs to be entities on a par with mental processes, and seeks a priori and a posteriori knowledge about them by combining formal deduction and scientific experimentation. We demonstrate evidence corroborating the tenets of the scientific paradigm, in particular the claim that program-processes are on a par with mental processes. We conclude with a discussion in the influence that the technocratic paradigm has been having over computer science. (shrink)

Epistemic logic has grown from its philosophical beginnings to find diverse applications in computer science, and as a means of reasoning about the knowledge and belief of agents. This book provides a broad introduction to the subject, along with many exercises and their solutions. The authors begin by presenting the necessary apparatus from mathematics and logic, including Kripke semantics and the well-known modal logics K, T, S4 and S5. Then they turn to applications in the context of (...) distributed systems and artificial intelligence. These include the notions of common knowledge, distributed knowledge, explicit and implicit belief, the interplays between knowledge and time, and knowledge and action, as well as a graded (or numerical) variant of the epistemic operators. The authors also discuss extensively the problem of logical omniscience. They cover Halpern & Moses' theory of honest formulas, and they make a digression into the realm of nonmonotonic reasoning and preferential entailment. They discuss Moore's autoepistemic logic, together with Levesque's related logic of "all I know". Furthermore, they show how one can base default and counterfactual reasoning on epistemic logic. Graduate students in philosophy or in computer science, especially those with an interest in AI, will find this book useful. (shrink)

This volume contains the proceedings of three special sessions: Algebra and Computer Science, held during the Joint AMS-EMS-SPM meeting in Porto, Portugal, June 10–13, 2015; Groups, Algorithms, and Cryptography, held during the Joint Mathematics Meeting in San Antonio, TX, January 10–13, 2015; and Applications of Algebra to Cryptography, held during the Joint AMS-Israel Mathematical Union meeting in Tel-Aviv, Israel, June 16–19, 2014. Papers contained in this volume address a wide range of topics, from theoretical aspects of algebra, (...) namely group theory, universal algebra and related areas, to applications in several different areas of computer science. From the computational side, the book aims to reflect the rapidly emerging area of algorithmic problems in algebra, their computational complexity and applications, including information security, constraint satisfaction problems, and decision theory. The book gives special attention to recent advances in quantum computing that highlight the need for a variety of new intractability assumptions and have resulted in a new area called group-based cryptography. (shrink)

Linear Logic is a branch of proof theory which provides refined tools for the study of the computational aspects of proofs. These tools include a duality-based categorical semantics, an intrinsic graphical representation of proofs, the introduction of well-behaved non-commutative logical connectives, and the concepts of polarity and focalisation. These various aspects are illustrated here through introductory tutorials as well as more specialised contributions, with a particular emphasis on applications to computer science: denotational semantics, lambda-calculus, logic programming and concurrency (...) theory. The volume is rounded-off by two invited contributions on new topics rooted in recent developments of linear logic. The book derives from a summer school that was the climax of the EU Training and Mobility of Researchers project 'Linear Logic in Computer Science'. It is an excellent introduction to some of the most active research topics in the area. (shrink)

This paper discusses how facet-like structures occur as a commonplace feature in a variety of computer science disciplines as a means for structuring class hierarchies. The paper then focuses on a mathematical model for facets (and class hierarchies in general), called formal concept analysis, and discusses graphical representations of faceted systems based on this model.

An understanding of logic is essential to computer science. This book provides a highly accessible account of the logical basis required for reasoning about computer programs and applying logic in fields like artificial intelligence. The text contains extended examples, algorithms, and programs written in Standard ML and Prolog. No prior knowledge of either language is required. The book contains a clear account of classical first-order logic, one of the basic tools for program verification, as well as an (...) introductory survey of modal and temporal logics and possible world semantics. An introduction to intuitionistic logic as a basis for an important style of program specification is also featured in the book. (shrink)

Book review r A. (2004). "Book review: Yves nievergelt, foundations of ...