Epistemic Operators in Dependence Logic

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 δ ⁿ for Dependence Logic are also introduced, and the relationship between these ${\forall^{n}}$ quantifiers and the δ ⁿ 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.     

On the Logic of Nonmonotonic Conditionals and Conditional Probabilities: Predicate Logic

In a previous paper I described a range of nonmonotonic conditionals that behave like conditional probability functions at various levels of probabilistic support. These conditionals were defined as semantic relations on an object language for sentential logic. In this paper I extend the most prominent family of these conditionals to a language for predicate logic. My approach to quantifiers is closely related to Hartry Field's probabilistic semantics. Along the way I will show how Field's semantics differs from a substitutional interpretation of quantifiers in crucial ways, and show that Field's approach is closely related to the usual objectual semantics. One of Field's quantifier rules, however, must be significantly modified to be adapted to nonmonotonic conditional semantics. And this modification suggests, in turn, an alternative quantifier rule for probabilistic semantics.     

IF多值逻辑及博弈语义

本文基于经典一阶逻辑句法的逻辑优先性分析,把Hintikka的独立联结词和独立量词扩展到多值逻辑中。我们给出IF多值逻辑的句法,并使用不完全信息的语义赋值博弈解释了IF多值逻辑。     

Quantifiers and Congruence Closure

We prove some results about the limitations of the expressive power of quantifiers on finite structures. We define the concept of a bounded quantifier and prove that every relativizing quantifier which is bounded is already first-order definable (Theorem 3.8). We weaken the concept of congruence closed (see [6]) to weakly congruence closed by restricting to congruence relations where all classes have the same size. Adapting the concept of a thin quantifier (Caicedo [1]) to the framework of finite structures, we define the concept of a meager quantifier. We show that no proper extension of first-order logic by means of meager quantifiers is weakly congruence closed (Theorem 4.9). We prove the failure of the full congruence closure property for logics which extend first-order logic by means of meager quantifiers, arbitrary monadic quantifiers, and the Härtig quantifier (Theorem 6.1).     

On The Computational Consequences of Independence in Propositional Logic

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline.     

Toward model-theoretic modal logics

Adding certain cardinality quantifiers into first-order language will give substantially more expressive languages. Thus, many mathematical concepts beyond first-order logic can be handled. Since basic modal logic can be seen as the bisimular invariant fragment of first-order logic on the level of models, it has no ability to handle modally these mathematical concepts beyond first-order logic. By adding modalities regarding the cardinalities of successor states, we can, in principle, investigate modal logics of all cardinalities. Thus ways of exploring model-theoretic logics can be transferred to modal logics.     

Fresh Logic: proof-theory and semantics for FM and nominal techniques

In this paper we introduce Fresh Logic, a natural deduction style first-order logic extended with term-formers and quantifiers derived from the FM-sets model of names and binding in abstract syntax. Fresh Logic can be classical or intuitionistic depending on whether we include a law of excluded middle; we present a proof-normalisation procedure for the intuitionistic case and a semantics based on Kripke models in FM-sets for which it is sound and complete.     

Three-valued Logics in Modal Logic

Every truth-functional three-valued propositional logic can be conservatively translated into the modal logic S5. We prove this claim constructively in two steps. First, we define a Translation Manual that converts any propositional formula of any three-valued logic into a modal formula. Second, we show that for every S5-model there is an equivalent three-valued valuation and vice versa. In general, our Translation Manual gives rise to translations that are exponentially longer than their originals. This fact raises the question whether there are three-valued logics for which there is a shorter translation into S5. The answer is affirmative: we present an elegant linear translation of the Logic of Paradox and of Strong Three-valued Logic into S5.     

The Skolem-Löwenheim theorem in toposes

The topos theory gives tools for unified proofs of theorems for model theory for various semantics and logics. We introduce the notion of power and the notion of generalized quantifier in topos and we formulate sufficient condition for such quantifiers in order that they fulfil downward Skolem-Löwenheim theorem when added to the language. In the next paper, in print, we will show that this sufficient condition is fulfilled in a vast class of Grothendieck toposes for the general and the existential quantifiers.     

Complexity Results for Modal Dependence Logic

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p ₁, . . . , p _n , = (p ₁, . . . , p _n-1, p _n ) intuitively states that the value of p _n is determined by those of p ₁, . . . , p _n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence 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.     

Δ-core Fuzzy Logics with Propositional Quantifiers, Quantifier Elimination and Uniform Craig Interpolation

In this paper we investigate the connections between quantifier elimination, decidability and Uniform Craig Interpolation in Δ-core fuzzy logics added with propositional quantifiers. As a consequence, we are able to prove that several propositional fuzzy logics have a conservative extension which is a Δ-core fuzzy logic and has Uniform Craig Interpolation.     

走向模型论的模态逻辑

增加特定的基数量词,扩张一阶语言,就可以导致实质性地增强语言的表达能力,这样许多超出一阶逻辑范围的数学概念就能得到处理。由于在模型的层次上基本模态逻辑可以看作一阶逻辑的互模拟不变片断,显然它不能处理这些数学概念。因此,增加说明后继状态类上基数概念的模态词,原则上我们就能以模态的方式处理所有基数。我们把讨论各种模型论逻辑的方式转移到模态方面。     

The Logic of Opacity

We explore the view that Frege's puzzle is a source of straightforward counterexamples to Leibniz's law. Taking this seriously requires us to revise the classical logic of quantifiers and identity; we work out the options, in the context of higher‐order logic. The logics we arrive at provide the resources for a straightforward semantics of attitude reports that is consistent with the Millian thesis that the meaning of a name is just the thing it stands for. We provide models to show that some of these logics are non‐degenerate.     

Prior expectation and the interpretation of natural language quantifiers

Abstract

The interpretation of natural language quantifiers depends, in part, on one's prior expectations about what the proportion being described might be. This hypothesis is tested empirically, by comparing the interpretation of 10 different quantifier expressions in three contexts which contained proportions about which subjects' expectations were reliably different (Experiment 1). It is further argued that quantifiers perform many functions which cannot be observed by considering only the proportion(s) denoted by a quantifier. The experimental evidence presented shows that quantifiers can provide information about what the user of the quantifier had expected before “knowing the facts” (Experiment 2). It is also clear that when writers produce a quantifier, they can reveal their assumptions about the prior expectations held by their readers (Experiment 2).     

Nice Embedding in Classical Logic

It is shown that a set of semi-recursive logics, including many fragments of CL (Classical Logic), can be embedded within CL in an interesting way. A logic belongs to the set iff it has a certain type of semantics, called nice semantics. The set includes many logics presented in the literature. The embedding reveals structural properties of the embedded logic. The embedding turns finite premise sets into finite premise sets. The partial decision methods for CL that are goal directed with respect to CL are turned into partial decision methods that are goal directed with respect to the embedded logics.     

From IF to BI

We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried by the semantics is the logic of Bunched Implications due to Pym and O’Hearn, which combines intuitionistic and multiplicative connectives. This introduces several new connectives not previously considered in logics of informational dependence, but which we show play a very natural rôle, most notably intuitionistic implication. As regards the quantifiers, we show that their interpretation in the Hodges semantics is forced, in that they are the image under the general construction of the usual Tarski semantics; this implies that they are adjoints to substitution, and hence uniquely determined. As for the dependence predicate, we show that this is definable from a simpler predicate, of constancy or dependence on nothing. This makes essential use of the intuitionistic implication. The Armstrong axioms for functional dependence are then recovered as a standard set of axioms for intuitionistic implication. We also prove a full abstraction result in the style of Hodges, in which the intuitionistic implication plays a very natural rôle.     

关于不可化归的多态式量词句的CCG探析

广义量词理论对英语中一些特定的量词句进行分析,把其中两个单态式量词合并成一个多态式量词。Keenan证明了这个多态式量词的意义不能化归为两个单态式量词的意义,即多态式量词的意义不能从两个单态式量词的标准意义推演出来。Keenan的研究是很有价值的,但本文尝试从另外的角度思考,对汉语类似的多态式量化句进行个案处理,采纳组合范畴语法针对自然语言表层结构的词汇主义方法,遵循部分表达式的意义决定整体表达式意义的组合原则,从两个单态式量词的非标准意义推演出整个多态式量词句的量化意义。     

Categorical Abstract Algebraic Logic: Behavioral π-Institutions

Recently, Caleiro, Gon¸calves and Martins introduced the notion of behaviorally algebraizable logic. The main idea behind their work is to replace, in the traditional theory of algebraizability of Blok and Pigozzi, unsorted equational logic with multi-sorted behavioral logic. The new notion accommodates logics over many-sorted languages and with non-truth-functional connectives. Moreover, it treats logics that are not algebraizable in the traditional sense while, at the same time, shedding new light to the equivalent algebraic semantics of logics that are algebraizable according to the original theory. In this paper, the notion of an abstract multi-sorted π-institution is introduced so as to transfer elements of the theory of behavioral algebraizability to the categorical setting. Institutions formalize a wider variety of logics than deductive systems, including logics involving multiple signatures and quantifiers. The framework developed has the same relation to behavioral algebraizability as the classical categorical abstract algebraic logic framework has to the original theory of algebraizability of Blok and Pigozzi.     

Game Logic - An Overview

Game Logic is a modal logic which extends Propositional Dynamic Logic by generalising its semantics and adding a new operator to the language. The logic can be used to reason about determined 2-player games. We present an overview of meta-theoretic results regarding this logic, also covering the algebraic version of the logic known as Game Algebra.