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 study the extension of dependence logic \ by a majority quantifier \ over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, \\) captures the complexity class counting hierarchy. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of \\).

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence (...) class='Hi'>logic is complete for nondeterministic exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster. (shrink)

We study the expressive power of open formulas of dependence logic introduced in Väänänen [Dependence logic (Vol. 70 of London Mathematical Society Student Texts), 2007]. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic.

We introduce generalized quantifiers, as defined in Tarskian semantics by Mostowski and Lindström, in logics whose semantics is based on teams instead of assignments, e.g., IF-logic and Dependence logic. Both the monotone and the non-monotone case is considered. It is argued that to handle quantifier scope dependencies of generalized quantifiers in a satisfying way the dependence atom in Dependence logic is not well suited and that the multivalued dependence atom is a better choice. (...) This atom is in fact definably equivalent to the independence atom recently introduced by Väänänen and Grädel. (shrink)

Dependence logic and its many variants are new logics that aim at establishing a unified logical theory of dependence and independence underlying seemingly unrelated subjects. The area of dependence logic has developed rapidly in the past few years. We will give a short introduction to dependence logic and review some of the recent developments in the area.

The properties of the ${\forall^{1}}$ quantifier defined by Kontinen and Väänänen in [13] are studied, and its definition is generalized to that of a family of quantifiers ${\forall^{n}}$ . Furthermore, some epistemic operators δ n for Dependence Logic are also introduced, and the relationship between these ${\forall^{n}}$ quantifiers and the δ n operators are investigated.The Game Theoretic Semantics for Dependence Logic and the corresponding Ehrenfeucht- Fraissé game are then adapted to these new connectives.Finally, it is proved (...) that the ${\forall^{1}}$ quantifier is not uniformly definable in Dependence Logic, thus answering a question posed by Kontinen and Väänänen in the above mentioned paper. (shrink)

RESUMO Um problema de longa data na erudição aristotélica diz respeito à questão de como reconciliar a dupla descrição de Aristóteles da metafísica como ontologia (a ciência universal do ser enquanto ser) e teologia (a ciência da substância imutável e separada). Uma tentativa importante de responder a esta questão (iniciada primeiro por G. Patzig) consiste em dizer que a substância imutável e separada é focalmente anterior (ou o significado focal da) substância e, portanto, de ser em geral (uma vez que (...) a substância é focalmente anterior a ser no geral). Este artigo visa refutar esse tipo de abordagem para o problema da unidade da metafísica de Aristóteles, argumentando que (i) as relações de significado focal implicam a prioridade lógica (definição) dos itens anteriores sobre os itens dependentes situados em tais relações; (ii) a substância imutável e separada não é logicamente anterior aos outros tipos de substâncias distinguidas por Aristóteles; e, portanto, (iii) a substância imutável e separada não é focalmente anterior à (o significado focal de) substância. (shrink)

We examine the transitions between sets of possible worlds described by the compositional semantics of Modal Dependence Logic, and we use them as the basis for a dynamic version of this logic. We give a game theoretic semantics, a (compositional) transition semantics and a power game semantics for this new variant of modal Dependence Logic, and we prove their equivalence; and furthermore, we examine a few of the properties of this formalism and show that Modal (...) Dependence Logic can be recovered from it by reasoning in terms of reachability. Then we show how we can generalize this approach to a very general formalism for reasoning about transformations between pointed Kripke models. (shrink)

Intuitionistic dependence logic was introduced by Abramsky and Väänänen [1] as a variant of dependence logic under a general construction of Hodges’ (trump) team semantics. It was proven that there is a translation from intuitionistic dependence logic sentences into second order logic sentences. In this paper, we prove that the other direction is also true, therefore intuitionistic dependence logic is equivalent to second order logic on the level of sentences.

We characterize the expressive power of extensions of Dependence Logic and Independence Logic by monotone generalized quanti ers in terms of quanti er extensions of existential second-order logic.

We show that for any pair $\phi$ and $\psi$ of contradictory formulas of dependence logic there is a formula $\theta$ of the same logic such that $\phi\equiv\theta$ and $\psi\equiv\neg\theta$. This generalizes a result of Burgess.

Dependence logic, introduced in Väänänen [11], cannot be axiomatized. However, first-order consequences of dependence logic sentences can be axiomatized, and this is what we shall do in this paper. We give an explicit axiomatization and prove the respective Completeness Theorem.

We study the computational complexity of the model checking problem for quantifier-free dependence logic ${(\mathcal{D})}$ formulas. We characterize three thresholds in the complexity: logarithmic space (LOGSPACE), non-deterministic logarithmic space (NL) and non-deterministic polynomial time (NP).

We examine the relationship between dependence logic and game logics. A variant of dynamic game logic, called Transition Logic, is developed, and we show that its relationship with dependence logic is comparable to the one between first-order logic and dynamic game logic discussed by van Benthem. This suggests a new perspective on the interpretation of dependence logic formulas, in terms of assertions about reachability in games of imperfect information against Nature. (...) We then capitalize on this intuition by developing expressively equivalent variants of dependence logic in which this interpretation is taken to the foreground. (shrink)

Independence Friendly Logic, introduced by Hintikka, is a logic in which a quantifier can be marked for being independent of other quantifiers. Dependence logic, introduced by Väänänen, is a logic with the complementary approach: for a quantifier it can be indicated on which quantifiers it depends. These logics are claimed to be useful for many phenomena, for instance natural language semantics. In this contribution we will compare these two logics by investigating their application in a (...) compositional analysis of the de dicto - de re ambiguity in natural language. It will be argued that Independence Friendly logic is suitable, whereas Dependence Logic is not. (shrink)

In recent years, the logic of questions and dependencies has been investigated in the closely related frameworks of inquisitive logic and dependence logic. These investigations have assumed classical logic as the background logic of statements, and added formulas expressing questions and dependencies to this classical core. In this paper, we broaden the scope of these investigations by studying questions and dependency in the context of intuitionistic logic. We propose an intuitionistic team semantics, where (...) teams are embedded within intuitionistic Kripke models. The associated logic is a conservative extension of intuitionistic logic with questions and dependence formulas. We establish a number of results about this logic, including a normal form result, a completeness result, and translations to classical inquisitive logic and modal dependence logic. (shrink)

Compound propositions which can successfully be defended in a quantumdialogue independent of the elementary propositions contained in it, must have this property also independent of the mutual elementary commensur-abilities. On the other hand, formal commensurabilities must be taken into account. Therefore, for propositions which can be proved by P, irrespective of both the elementary propositions and of the elementary commensur-abilities, there exists a formal strategy of success. The totality of propositions with a formal strategy of success in a quantum dialogue (...) form the effective quantum logic. The propositions of the effective quantum logic can be derived from a calculus Q eff which is — on the other hand — equivalent to a lattice L qi.Propositions about measuring results are above all time dependent propositions A(S;t). In a dialogue, different partial propositions will have in general different time values. If one can (accidentally) win a material dialogue, this dialogue can be related to a single time value. For the propositions of the effective quantum logic there exist formal strategies of success, independent of the elementary propositions contained in it. All partial propositions appearing in the dialogue are formally commensurable. Therefore the propositions of effective quantum logic which can be proved by formal dialogues can always be related to a single time. They present a description of the system S considered in which all partial propositions can be related jointly to the state of S.Therefore in the effective quantum logic we have — in the limit of equal time values — a situation which corresponds conceptually to the description of the system (S; ψ) in Hilbert space. Consequently, one would expect that also the lattice L qi — except from the tertium non datur 8 — agrees with the lattice L q of subspaces of Hilbert space. It has been shown that these lattices are in fact isomorphic. (shrink)

In the core chapters 4–6, Iacona (2018) argues against the “Uniqueness Thesis” (UT), stating that “there is a unique notion of logical form that fulfils both the logical role and the semantic role” (39), where the former “concerns the formal explanation of logical properties and logical relations, such as validity or contradiction” (37), and the latter “concerns the formulation of a compositional theory of meaning” (ibid.). He argues for this on the basis of relations of coreference among referential expressions, names (...) and indexicals. From what I take to be a fundamental agreement on most relevant issues, here I will nonetheless press him to clarify the notions of intrinsicness and the logical and semantic role of logical form on which he relies. (shrink)

The purpose of this paper is to analyse the possible implications of Peirce's categories for a project of a community. In order to do so, I will start by analysing the first formulation of these categories in Peirce's early writings, and then I will compare them with their later formulations. Thus, we will see some their most important characteristics, namely, their universality and their dynamism, which will allow for a particular understanding of the role that logic can play in (...) his system, in a theory of scientific inquiry and, finally, in a community in general. (shrink)

This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more (...) concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games. (shrink)

Independence‐Friendly logic introduced by Hintikka and Sandu studies patterns of dependence and independence of quantifiers which exceed those found in ordinary first‐order logic. The present survey focuses on the game‐theoretical interpretation of IF‐logic, including connections to solution concepts in classical game theory, but we shall also present its compositional interpretation together with its connections to notions of dependence and dependence between terms.

Humans, unlike other animals, are equipped with a powerful brain that permits conscious awareness and reflection. A growing trend in psychological science has questioned the benefits of consciousness, however. Testing a hypothesis advanced by [Lieberman, M. D., Gaunt, R., Gilbert, D. T., & Trope, Y. . Reflection and reflexion: A social cognitive neuroscience approach to attributional inference. Advances in Experimental Social Psychology, 34, 199–249], four studies suggested that the conscious, reflective processing system is vital for logical reasoning. Substantial decrements in (...) logical reasoning were found when a cognitive load manipulation preoccupied conscious processing, while hampering the nonconscious system with consciously suppressed thoughts failed to impair reasoning . Nonconscious activation of the idea of logical reasoning increased the activation of logic-relevant concepts, but failed to improve logical reasoning performance unless the logical conclusions were largely intuitive and thus not reliant on logical reasoning . Meanwhile, stimulating the conscious goal of reasoning well led to improvements in reasoning performance . These findings offer evidence that logical reasoning is aided by the conscious, reflective processing system. (shrink)

In this paper we prove that three of the main propositional logics of dependence, none of which is structural, are structurally complete with respect to a class of substitutions under which the logics are closed. We obtain an analogous result with respect to stable substitutions, for the negative variants of some well-known intermediate logics, which are intermediate theories that are closely related to inquisitive logic.

Quantum-mechanical event descriptions are context-dependent descriptions. The role of quantum (nondistributive) logic is in the partial ordering of contexts rather than in the ordering of quantum-mechanical events. Moreover, the kind of quantum logic displayed by quantum mechanics can be easily inferred from the general notion of contextuality used in ordinary language. The formalizable core of Bohr's notion of complementarity is the type of context dependence discussed in this paper.

Although the case for the judgment-dependence of many other domains has been pored over, surprisingly little attention has been paid to mathematics and logic. This paper presents two dilemmas for a judgment-dependent account of these areas. First, the extensionality-substantiality dilemma: in each case, either the judgment-dependent account is extensionally inadequate or it cannot meet the substantiality condition (roughly: non-vacuous specification). Second, the extensionality-extremality dilemma: in each case, either the judgment-dependent account is extensionally inadequate or it cannot meet the (...) extremality condition (roughly: absence of independent explanation). The paper concludes with a moral concerning the judgment-dependence of a posteriori areas of discourse that emerges from consideration of these two a priori cases. (shrink)

In this paper, we axiomatize the negatable consequences in dependence and independence logic by extending the systems of natural deduction of the logics given in [22] and [11]. We prove a characterization theorem for negatable formulas in independence logic and negatable sentences in dependence logic, and identify an interesting class of formulas that are negatable in independence logic. Dependence and independence atoms, first-order formulas belong to this class. We also demonstrate our extended system (...) of independence logic by giving explicit derivations for Armstrong's Axioms and the Geiger-Paz-Pearl axioms of dependence and independence atoms. (shrink)

We introduce an atomic formula ${\vec{y} \bot_{\vec{x}}\vec{z}}$ intuitively saying that the variables ${\vec{y}}$ are independent from the variables ${\vec{z}}$ if the variables ${\vec{x}}$ are kept constant. We contrast this with dependence logic ${\mathcal{D}}$ based on the atomic formula = ${(\vec{x}, \vec{y})}$ , actually equivalent to ${\vec{y} \bot_{\vec{x}}\vec{y}}$ , saying that the variables ${\vec{y}}$ are totally determined by the variables ${\vec{x}}$ . We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ gives rise to a natural logic capable of formalizing basic intuitions about (...) independence and dependence. We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ can be used to give partially ordered quantifiers and IF-logic an alternative interpretation without some of the shortcomings related to so called signaling that interpretations using = ${(\vec{x}, \vec{y})}$ have. (shrink)

We extend the earlier results on the equivalence between the Boolean and the multivalued dependencies in relational databases and fragments of the Boolean propositional logic. It is shown that these equivalences are still valid for the databases that store complex data elements obtained from the recursive nesting of record, list, set and multiset constructors. The major proof argument utilises properties of Brouwerian algebras.The equivalences have several consequences. Firstly, they provide new insights into databases that are not in first normal (...) form. Secondly, they characterise the implication of data dependencies in nested databases in purely logical terms. The database designer can take advantage of these equivalences to reduce database design problems to well-studied problems in Boolean propositional logic. Furthermore, relational database design solutions can be reused to solve problems for nested databases. (shrink)

Public or stakeholder participation in environmental governance has been strongly advocated within the United Nations (UN) since the early 1990s. A relatively new mechanism for global climate finance that emphasises stakeholder engagement is the Green Climate Fund (GCF), a UN strategy for channelling funds from the Global North to the Global South. Drawing on previous critical approaches to multi-stakeholder involvement in global governance, this article explores stakeholder involvement within the GCF. The study combines ideas from institutional logics and resource dependency (...) to provide a better understanding of how stakeholder arrangements are shaped in climate organisations. Results show that the GCF stakeholder arrangement favours private sector stakeholders – stakeholders that take a technical and apolitical approach to climate finance – and disfavours smaller, less resourceful stakeholders as well as those who perform a politicised watchdog function. (shrink)