This book is an introduction to finite model theory which stresses the computer science origins of the area. In addition to presenting the main techniques for analyzing logics over finite models, the book deals extensively with applications in databases, complexity theory, and formal languages, as well as other branches of computer science. It covers Ehrenfeucht-Fraïssé games, locality-based techniques, complexity analysis of logics, including the basics of descriptive complexity, second-order logic and its fragments, connections with finite automata, fixed point logics, finite (...) variable logics, zero-one laws, and embedded finite models, and gives a brief tour of recently discovered applications of finite model theory. This book can be used both as an introduction to the subject, suitable for a one- or two-semester graduate course, or as reference for researchers who apply techniques from logic in computer science. (shrink)

I LOGIC IN PHILOSOPHY— PHILOSOPHY OF LOGIC i. On the relation of logic to philosophy I n this book, the consequences of certain logical insights for ...

Proof, Computation and Agency: Logic at the Crossroads provides an overview of modern logic and its relationship with other disciplines. As a highlight, several articles pursue an inspiring paradigm called 'social software', which studies patterns of social interaction using techniques from logic and computer science. The book also demonstrates how logic can join forces with game theory and social choice theory. A second main line is the logic-language-cognition connection, where the articles collected here bring several fresh perspectives. Finally, the book (...) takes up Indian logic and its connections with epistemology and the philosophy of science, showing how these topics run naturally into each other. (shrink)

This book develops a view of logic as a theory of information-driven agency and intelligent interaction between many agents - with conversation, argumentation and games as guiding examples. It provides one uniform account of dynamic logics for acts of inference, observation, questions and communication, that can handle both update of knowledge and revision of beliefs. It then extends the dynamic style of analysis to include changing preferences and goals, temporal processes, group action and strategic interaction in games. Throughout, the book (...) develops a mathematical theory unifying all these systems, and positioning them at the interface of logic, philosophy, computer science and game theory. A series of further chapters explores repercussions of the 'dynamic stance' for these areas, as well as cognitive science. (shrink)

This work is an attempt to lay foundations for a theory of interactive computation and bring logic and theory of computing closer together. It semantically introduces a logic of computability and sets a program for studying various aspects of that logic. The intuitive notion of computational problems is formalized as a certain new, procedural-rule-free sort of games between the machine and the environment, and computability is understood as existence of an interactive Turing machine that wins the game against any possible (...) environment. The formalism used as a specification language for computational problems, called the universal language, is a non-disjoint union of the formalisms of classical, intuitionistic and linear logics, with logical operators interpreted as certain—most basic and natural—operations on problems. Validity of a formula is understood as being “always computable”, and the set of all valid formulas is called the universal logic. The name “universal” is related to the potential of this logic to integrate, on the basis of one semantics, classical, intuitionistic and linear logics, with their seemingly unrelated or even antagonistic philosophies. In particular, the classical notion of truth turns out to be nothing but computability restricted to the formulas of the classical fragment of the universal language, which makes classical logic a natural syntactic fragment of the universal logic. The same appears to be the case for intuitionistic and linear logics . Unlike classical logic, these two do not have a good concept of truth, and the notion of computability restricted to the corresponding two fragments of the universal language, based on the intuitions that it formalizes, can well qualify as “intuitionistic truth” and “linear-logic truth”. The paper also provides illustrations of potential applications of the universal logic in knowledgebase, resourcebase and planning systems, as well as constructive applied theories. The author has tried to make this article easy to read. It is fully self-contained and can be understood without any specialized knowledge of any particular subfield of logic or computer science. (shrink)

Quantification is a topic which brings together linguistics, logic, and philosophy. Quantifiers are the essential tools with which, in language or logic, we refer to quantity of things or amount of stuff. In English they include such expressions as no, some, all, both, many. Peters and Westerstahl present the definitive interdisciplinary exploration of how they work - their syntax, semantics, and inferential role.

Thinking should be taught in every class, but only children’s philosophy workshops allow learning and the practice of correct thinking without linking them to the acquisition of some other mandatory learning. The reading of stories with veiled philosophical content is one way to conduct philosophical workshops for children. We may give children stories that contain some laws of correct logical reasoning. However, in order to achieve this aim, we must extract the content from the symbolic logic and translate it into (...) everyday language. We must choose areas where the thought process is of interest for children, such as that found in logical games. This method was used by Lewis Carroll in his book The Game of Logic. We attempt to develop further his idea by suggesting games which are used by children in their everyday life. (shrink)

This book presents novel formalizations of three of the most important medieval logical theories: supposition, consequence and obligations. In an additional fourth part, an in-depth analysis of the concept of formalization is presented - a crucial concept in the current logical panorama, which as such receives surprisingly little attention.Although formalizations of medieval logical theories have been proposed earlier in the literature, the formalizations presented here are all based on innovative vantage points: supposition theories as algorithmic hermeneutics, theories of consequence analyzed (...) with tools borrowed from model-theory and two-dimensional semantics, and obligations as logical games. For this reason, this is perhaps the first time that these medieval logical theories are made fully accessible to the modern philosopher and logician who wishes to obtain a better grasp of them, but who has always been held back by the lack of appropriate ‘translations' into modern terms.Moreover, the book offers a reflection on the very nature of logic, a reflection that is prompted by the comparisons between medieval and modern logic, their similarities and dissimilarities. It is thus a contribution not only to the history of logic, but also to the philosophy of logic, the philosophy of language and semantics.The analysis of medieval logic is also relevant for the modern philosopher and logician in that, being the unifying methodology used across all disciplines at that time, logic really provided unity to science. It thus presents a unified model of scientific investigation, where logic plays the aggregating role. (shrink)

Develops a logical analysis of dialogue in which two or more parties attempt to advance their own interests. It includes a classification of the major types of dialogues and a discussion of several important informal fallacies.

A comprehensive examination of the interfaces of logic, computer science, and game theory, drawing on twenty years of research on logic and games.

Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence logic is given an alternative game theoretic (...) semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)

We describe a logic which is the same as first-order logic except that it allows control over the information that passes down from formulas to subformulas. For example the logic is adequate to express branching quantifiers. We describe a compositional semantics for this logic; in particular this gives a compositional meaning to formulas of the 'information-friendly' language of Hintikka and Sandu. For first-order formulas the semantics reduces to Tarski's semantics for first-order logic. We prove that two formulas have the same (...) interpretation in all structures if and only if replacing an occurrence of one by an occurrence of the other in a sentence never alters the truth-value of the sentence in any structure. (shrink)

[Wilfrid Hodges] During the last forty or so years it has become popular to offer explanations of logical notions in terms of games. There is no doubt that many people find games helpful for understanding various logical phenomena. But we ask whether anything is really 'explained' by these accounts, and we analyse Paul Lorenzen's dialogue foundations for constructive logic as an example. The conclusion is that the value of games lies in their ability to provide helpful metaphors and representations, rather (...) than in any true conceptual analysis. In fact some of the standard explanations of logical notions in terms of competitive games simply don't work. /// [ Erik C. W. Krabbe] In an attempt to redeem the Lorenzen-type dialogues from their detractors, it is perhaps best first to provide a survey of the various benefits these dialogues have been supposed to yield. This will be done in Section I. It will not be possible, within the confines of this paper, to scrutinize them all, but in Section II we shall delve deeper into the capacity of this type of dialogue to yield a model for the immanent criticism of philosophical positions. Section III will extend the concept of a dialogue in such a way as to conform better with our intuitive conceptions of what a rational discussion of a position should contain. This will be followed up by a concept of 'winning a dialogue' that takes position midway between the old conception of 'winning one play' and that of the full-fledged presentation of a winning strategy. Concepts of 'rational discussion' are thus shown to be, plausibly, more fundamental than those of proof. In Section IV, I shall discuss the specific problems about dialogical foundations put forward by Wilfrid Hodges. (shrink)

We present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of history-free strategy; strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a (...) natural notion of polarity, leading to a refined treatment of the additives. We make comparisons with related work by Joyal, Blass, et al. (shrink)

A systematic introduction suitable for readers who have little familiarity with logic. Provides numerous examples and complete proofs.

In recent years, model checking has become an essential technique for the formal verification of systems. With a clarity of presentation and its many illuminating examples, this book makes this technical material easy to grasp. It is perfectly suited for an advanced undergraduate or graduate class in formal verification and will serve as a valuable resource to practitioners of formal methods.