In the Lambek calculus of order 2 we allow only sequents in which the depth of nesting of implications is limited to 2. We prove that the decision problem of provability in the calculus can be solved in time polynomial in the length of the sequent. A normal form for proofs of second order sequents is defined. It is shown that for every proof there is a normal form proof with the same axioms. With this normal form we can give (...) an algorithm that decides provability of sequents in polynomial time. (shrink)

In this paper, we give a step by step introduction to the theory of well quasi-ordered transition systems. The framework combines two concepts, namely (i) transition systems which are monotonic wrt. a well-quasi ordering ; and (ii) a scheme for symbolic backward reachability analysis. We describe several models with infinite-state spaces, which can be analyzed within the framework, e.g., Petri nets, lossy channel systems, timed automata, timed Petri nets, and multiset rewriting systems. We will also present better quasi-ordered transition systems (...) which allow the design of efficient symbolic representations of infinite sets of states. (shrink)

We study increasing F-sequences, where F is a dilator: an increasing F-sequence is a sequence (indexed by ordinal numbers) of ordinal numbers, starting with 0 and terminating at the first step x where F(x) is reached (at every step x + 1 we use the same process as in decreasing F-sequences, cf. [2], but with "+ 1" instead of "- 1"). By induction on dilators, we shall prove that every increasing F-sequence terminates and moreover we can determine for every dilator (...) F the point where the increasing F-sequence terminates. We apply these results to inverse Goodstein sequences, i.e. increasing (1 + Id) (ω) -sequences. We show that the theorem every inverse Goodstein sequence terminates (a combinatorial theorem about ordinal numbers) is not provable in ID 1 . For a general presentation of the results stated in this paper, see [1]. We use notions and results concerning the category ON (ordinal numbers), dilators and bilators, summarized in [2, pp. 25-31]. (shrink)

The purpose of this essay is to both discuss commands as a species of speech act and to discuss commands within the broader framework of how they are used and ...

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as “every coalition satisfying property P can achieve φ” and “there exists a coalition C satisfying property P such that C can achieve φ”. We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

We axiomatize the notion of state over finitely generated free NM-algebras, the Lindenbaum algebras of pure Nilpotent Minimum logic. We show that states over the free n -generated NM-algebra exactly correspond to integrals of elements of with respect to Borel probability measures.

This is a survey article on algebraic logic. It gives a historical background leading up to a modern perspective. Central problems in algebraic logic (like the representation problem) are discussed in connection to other branches of logic, like modal logic, proof theory, model-theoretic forcing, finite combinatorics, and Gödel's incompleteness results. We focus on cylindric algebras. Relation algebras and polyadic algebras are mostly covered only insofar as they relate to cylindric algebras, and even there we have not told the whole story. (...) We relate the algebraic notion of neat embeddings (a notion special to cylindric algebras) to the metalogical ones of provability, interpolation and omitting types in variants of first logic. Another novelty that occurs here is relating the algebraic notion of atom-canonicity for a class of boolean algebras with operators to the metalogical one of omitting types for the corresponding logic. A hitherto unpublished application of algebraic logic to omitting types of first order logic is given. Proofs are included when they serve to illustrate certain concepts. Several open problems are posed. We have tried as much as possible to avoid exploring territory already explored in the survey articles of Monk [93] and Németi [97] in the subject. (shrink)

SC , CA , QA and QEA stand for the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasipolyadic algebras, and quasipolyadic equality algebras of dimension , respectively. Generalizing a result of Németi on cylindric algebras, we show that for K {SC, CA, QA, QEA} and ordinals , the class Nr K of -dimensional neat reducts of -dimensional K algebras, though closed under taking homomorphic images and products, is not closed under forming subalgebras (i.e. is not a variety) if (...) and only if > 1.From this it easily follows that for 1 , the operation of forming -neat reducts of algebras in K does not commute with forming subalgebras, a notion to be made precise. (shrink)

We present a semantics for strong negation systems on the basis of the subformula property of the sequent calculus. The new models, called subformula models, are constructed as a special class of canonical Kripke models for providing the way from the cut-elimination theorem to model-theoretic results. This semantics is more intuitive than the standard Kripke semantics for strong negation systems.

In some recent papers, the authors and Peter Gärdenfors have defined and studied two different kinds of formal operation, conceived as possible representations of the intuitive process of contracting a theory to eliminate a proposition. These are partial meet contraction (including as limiting cases full meet contraction and maxichoice contraction) and safe contraction. It is known, via the representation theorem for the former, that every safe contraction operation over a theory is a partial meet contraction over that theory. The purpose (...) of the present paper is to study the relationship more finely, by seeking an explicit map between the component orderings involved in each of the two kinds of contraction. It is shown that at least in the finite case a suitable map exists, with the consequence that the relational, transitively relational, and antisymmetrically relational partial meet contraction functions form identifiable subclasses of the safe contraction functions, over any theory finite modulo logical equivalence. In the process of constructing the map, as the composition of four simple transformations, mediating notions of bottom and top contraction are introduced. The study of the infinite case remains open. (shrink)

There exists a considerable body of work on epistemic logics for resource-bounded reasoners. In this paper, we concentrate on a less studied aspect of resource-bounded reasoning, namely, on the ascription of beliefs and inference rules by the agents to each other. We present a formal model of a system of bounded reasoners which reason about each other’s beliefs, and investigate the problem of belief ascription in a resource-bounded setting. We show that for agents whose computational resources and memory are bounded, (...) correct ascription of beliefs cannot be guaranteed, even in the limit. We propose a solution to the problem of correct belief ascription for feasible agents which involves ascribing reasoning strategies , or preferences on formulas, to other agents, and show that if a resource-bounded agent knows the reasoning strategy of another agent, then its ascription of beliefs to the other agent is correct in the limit. (shrink)

We show how sequent calculi for some generalized quantifiers can be obtained by generalizing the Herbrand approach to ordinary first order proof theory. Typical of the Herbrand approach, as compared to plain sequent calculus, is increased control over relations of dependence between variables. In the case of generalized quantifiers, explicit attention to relations of dependence becomes indispensible for setting up proof systems. It is shown that this can be done by turning variables into structured objects, governed by various types of (...) structural rules. These structured variables are interpreted semantically by means of a dependence relation. This relation is an analogue of the accessibility relation in modal logic. We then isolate a class of axioms for generalized quantifiers which correspond to first-order conditions on the dependence relation. (shrink)

This paper presents a bivalent extensional semantics for positive free logic without resorting to the philosophically questionable device of using models endowed with a separate domain of non-existing objects. The models here introduced have only one (possibly empty) domain, and a partial reference function for the singular terms (that might be undefined at some arguments). Such an approach provides a solution to an open problem put forward by Lambert, and can be viewed as supplying a version of parametrized truth non (...) unlike the notion of truth at world found in modal logic. A model theory is developed, establishing compactness, interpolation (implying a strong form of Beth definability), and completeness (with respect to a particular axiomatization). (shrink)

Hybrid languages are expansions of propositional modal languages which can refer to (or even quantify over) worlds. The use of strong hybrid languages dates back to at least [Pri67], but recent work (for example [BS98, BT98a, BT99]) has focussed on a more constrained system called $\mathscr{H}(\downarrow, @)$ . We show in detail that $\mathscr{H}(\downarrow, @)$ is modally natural. We begin by studying its expressivity, and provide model theoretic characterizations (via a restricted notion of Ehrenfeucht-Fraisse game, and an enriched notion of (...) bisimulation) and a syntactic characterization (in terms of bounded formulas). The key result to emerge is that $\mathscr{H}(\downarrow, @)$ corresponds to the fragment of first-order logic which is invariant for generated submodels. We then show that $\mathscr{H}(\downarrow, @)$ enjoys (strong) interpolation, provide counterexamples for its finite variable fragments, and show that weak interpolation holds for the sublanguage H(@). Finally, we provide complexity results for H(@) and other fragments and variants, and sharpen known undecidability results for $\mathscr{H}(\downarrow, @)$. (shrink)

Following the pioneer work of Bruno De Finetti [12], conditional probability spaces (allowing for conditioning with events of measure zero) have been studied since (at least) the 1950's. Perhaps the most salient axiomatizations are Karl Popper's in [31], and Alfred Renyi's in [33]. Nonstandard probability spaces [34] are a well know alternative to this approach. Vann McGee proposed in [30] a result relating both approaches by showing that the standard values of infinitesimal probability functions are representable as Popper functions, and (...) that every Popper function is representable in terms of the standard real values of some infinitesimal measure.Our main goal in this article is to study the constraints on (qualitative and probabilistic) change imposed by an extended version of McGee's result. We focus on an extension capable of allowing for iterated changes of view. Such extension, we argue, seems to be needed in almost all considered applications. Since most of the available axiomatizations stipulate (definitionally) important constraints on iterated change, we propose a non-question-begging framework, Iterative Probability Systems (IPS) and we show that every Popper function can be regarded as a Bayesian IPS. A generalized version of McGee's result is then proved and several of its consequences considered. In particular we note that our proof requires the imposition of Cumulativity, i.e. the principle that a proposition that is accepted at any stage of an iterative process of acceptance will continue to be accepted at any later stage. The plausibility and range of applicability of Cumulativity is then studied. In particular we appeal to a method for defining belief from conditional probability (first proposed in [42] and then slightly modified in [6] and [3]) in order to characterize the notion of qualitative change induced by Cumulative models of probability kinematics. The resulting cumulative notion is then compared with existing axiomatizations of belief change and probabilistic supposition. We also consider applications in the probabilistic accounts of conditionals [1] and [30]. (shrink)

Neutrosophic Logic was created by Florentin Smarandache (1995) and is an extension / combination of the fuzzy logic, intuitionistic logic, paraconsistent logic, ...

We extend to the predicate frame a previous characterization of the maximal intermediate propositional constructive logics. This provides a technique to get maximal intermediate predicate constructive logics starting from suitable sets of classically valid predicate formulae we call maximal nonstandard predicate constructive logics. As an example of this technique, we exhibit two maximal intermediate predicate constructive logics, yet leaving open the problem of stating whether the two logics are distinct. Further properties of these logics will be also investigated.

We provide a constructive, direct, and simple proof of the completeness of the cut-free part of the hypersequential calculus for G¨odel logic (thereby proving both completeness of the calculus for its standard semantics, and the admissibility of the cut rule in the full calculus). We then extend the results and proofs to derivations from assumptions, showing that such derivations can be confined to those in which cuts are made only on formulas which occur in the assumptions.

We construct a faithful interpretation of ukasiewicz's logic in product logic (both propositional and predicate). Using known facts it follows that the product predicate logic is not recursively axiomatizable.We prove a completeness theorem for product logic extended by a unary connective of Baaz [1]. We show that Gödel's logic is a sublogic of this extended product logic.

We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators (...) is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT. (shrink)

One of the most important contributions of A. Church to logic is his invention of the lambda calculus. We present the genesis of this theory and its two major areas of application: the representation of computations and the resulting functional programming languages on the one hand and the representation of reasoning and the resulting systems of computer mathematics on the other hand.

A λ-theory T is a consistent set of equations between λ-terms closed under derivability. The degree of T is the degree of the set of Godel numbers of its elements. H is the $\lamda$ -theory axiomatized by the set {M = N ∣ M, N unsolvable. A $\lamda$ -theory is sensible $\operatorname{iff} T \supset \mathscr{H}$ , for a motivation see [6] and [4]. In § it is proved that the theory H is ∑ 0 2 -complete. We present Wadsworth's proof (...) that its unique maximal consistent extention $\mathscr{H}^\ast (= \mathrm{T}(D_\infty))$ is Π 0 2 -complete. In $\S2$ it is proved that $\mathscr{H}_\eta(= \lambda_\eta-\text{Calculus} + \mathscr{H})$ is not closed under the ω-rule (see [1]). In $\S3$ arguments are given to conjecture that $\mathscr{H}\omega (= \lambda + \mathscr{H} + omega-rule)$ is Π 1 1 -complete. This is done by representing recursive sets of sequence numbers as λ-terms and by connecting wellfoundedness of trees with provability in Hω. In $\S4$ an infinite set of equations independent over H η will be constructed. From this it follows that there are 2^{ℵ_0 sensible theories T such that $\mathscr{H} \subset T \subset \mathscr{H}^\ast$ and 2 ℵ 0 sensible hard models of arbitrarily high degrees. In $\S5$ some nonprovability results needed in $\S\S1$ and 2 are established. For this purpose one uses the theory H η extended with a reduction relation for which the Church-Rosser theorem holds. The concept of Gross reduction is used in order to show that certain terms have no common reduct. (shrink)

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators or, in a more direct way, in which derivations are not translated. Both translations are (...) closely related in a canonical way. The two direct translations turn out to be complete. The paper fulfills the program of Church [1932], [1933] and Curry [1930] to base logic on a consistent system of λ-terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). (shrink)

This article answers two questions (posed in the literature), each concerning the guaranteed existence of proofs free of double negation. A proof is free of double negation if none of its deduced steps contains a term of the formn(n(t)) for some term t, where n denotes negation. The first question asks for conditions on the hypotheses that, if satisfied, guarantee the existence of a double-negation-free proof when the conclusion is free of double negation. The second question asks about the existence (...) of an axiom system for classical propositional calculus whose use, for theorems with a conclusion free of double negation, guarantees the existence of a double-negation-free proof. After giving conditions that answer the first question, we answer the second question by focusing on the Lukasiewicz three-axiom system. We then extend our studies to infinite-valued sentential calculus and to intuitionistic logic and generalize the notion of being double-negation free. The double-negation proofs of interest rely exclusively on the inference rule condensed detachment, a rule that combines modus ponens with an appropriately general rule of substitution. The automated reasoning program Otter played an indispensable role in this study. (shrink)

Proceedings of the Tenth Brazilian Conference on Mathematical Logic. Coleção CLE, volume 14, 1995. Centro De Lógica, Epistemologia e História da Ciência, Unicamp, Campinas, SP, Brazil.

. In this paper we address the question of recovering a logic system by combining two or more fragments of it. We show that, in general, by fibring two or more fragments of a given logic the resulting logic is weaker than the original one, because some meta-properties of the connectives are lost after the combination process. In order to overcome this problem, the categories Mcon and Seq of multiple-conclusion consequence relations and sequent calculi, respectively, are introduced. The main feature (...) of these categories is the preservation, by morphisms, of meta-properties of the consequence relations, which allows, in several cases, to recover a logic by fibring of its fragments. The fibring in this categories is called meta−fibring. Several examples of well-known logics which can be recovered by meta-fibring its fragments (in opposition to fibring in the usual categories) are given. Finally, a general semantics for objects in Seq (and, in particular, for objects in Mcon) is proposed, obtaining a category of logic systems called Log. A general theorem of preservation of completeness by fibring in Log is also obtained. (shrink)

Prior Analytics by the Greek philosopher Aristotle (384 – 322 BCE) and Laws of Thought by the English mathematician George Boole (1815 – 1864) are the two most important surviving original logical works from before the advent of modern logic. This article has a single goal: to compare Aristotle’s system with the system that Boole constructed over twenty-two centuries later intending to extend and perfect what Aristotle had started. This comparison merits an article itself. Accordingly, this article does not discuss (...) many other historically and philosophically important aspects of Boole’s book, e.g. his confused attempt to apply differential calculus to logic, his misguided effort to make his system of ‘class logic’ serve as a kind of ‘truth-functional logic’, his now almost forgotten foray into probability theory, or his blindness to the fact that a truth-functional combination of equations that follows from a given truth-functional combination of equations need not follow truth-functionally. One of the main conclusions is that Boole’s contribution widened logic and changed its nature to such an extent that he fully deserves to share with Aristotle the status of being a founding figure in logic. By setting forth in clear and systematic fashion the basic methods for establishing validity and for establishing invalidity, Aristotle became the founder of logic as formal epistemology. By making the first unmistakable steps toward opening logic to the study of ‘laws of thought’—tautologies and laws such as excluded middle and non-contradiction—Boole became the founder of logic as formal ontology. (shrink)

In this paper we show the embedding of Hybrid Probabilistic Logic Programs into the rather general framework of Residuated Logic Programs, where the main results of (definite) logic programming are validly extrapolated, namely the extension of the immediate consequences operator of van Emden and Kowalski. The importance of this result is that for the first time a framework encompassing several quite distinct logic programming semantics is described, namely Generalized Annotated Logic Programs, Fuzzy Logic Programming, Hybrid Probabilistic Logic Programs, and Possibilistic (...) Logic Programming. Moreover, the embedding provides a more general semantical structure paving the way for defining paraconsistent probabilistic reasoning with a logic programming semantics. (shrink)

Logic and psychology overlap in judgment, inference and proof. The problems raised by this commonality are notoriously difficult, both from a historical and from a philosophical point of view. Sundholm has for a long time addressed these issues. His beautiful piece of work [A Century of Inference: 1837-1936] begins by summarizing the main difficulty in the usual provocative manner of the author: one can start, he says, by the act of knowledge to go to the object, as the Idealist does; (...) one can also start by the object to go to the act, in the Realist mood; never the two shall meet. He is himself inclined to accept the first perspective as the right one and he has eventually developed an original version of antirealism which starts, not from considerations about the publicity of meaning, in the manner of Dummett, but from an epistemic standpoint, trying to search in a non-Fregean tradition of analysis of judgement and cognate notions a way of founding constructivist semantics. The present paper ploughes the same field. We concentrate on the significance, for Sundholm’s program, of the perspective that has been opened by Twardowski in his important essay on acts and products (1912. (shrink)

Courtroom dialogue involves questions and answers, which may be modeled by erotetic logic. In this short communication, we model the courtroom objection "Asked and Answered!" using such a logic. The model is applied to the case of the traffic light.

Readers choosing to download the article--one must use the "other links" tab--should please be so kind as to respect the author's wishes and also see the Erratum et Corrigendum which is locally available by simply clicking on the article title. -/- Cross-examination of witnesses is not an opportunity to explore the beliefs of those on the stand on even relevant matters. Rather, it is an opportunity to impeach evidence given by the witness during direct examination. That is possible in two (...) ways: questioning the credibility of the witness directly, for example by bringing up a perjury conviction or by asking what favors he received in expectation of his future testimony, or questioning the witness’ credibility indirectly, by trying to disassemble the story he has woven on examination-in-chief. We are concerned with formalizing this last process. Like the question of the whole truth, the questioner is allowed considerable latitude, but that latitude is bounded by the examination in-chief. Also like that question, any formalization will have to use a logic which models questions and answers, not just propositions. Such a logic is called an erotetic logic, and we review the basics of the erotetic logic we will be using and then present our formalization using that logic. (shrink)

Exactly what is meant by the requirement that witnesses swear in a court of law to tell "the whole truth"? It cannot mean simply the "truth," because that's a separate and prior requirement. It cannot mean "nothing but the truth," because that's also a separate requirement. It cannot mean "the whole story," because the adversary system not only does not require that, it does not even permit that. All it permits the witness to do is answer the questions put to (...) him. Using erotetic logic, the author suggests an answer to what is meant by the requirement. (shrink)

Resolution is an effective deduction procedure for classical logic. There is no similar "resolution" system for non-classical logics (though there are various automated deduction systems). The paper presents resolution systems for intuistionistic predicate logic as well as for modal and temporal logics within the framework of labelled deductive systems. Whereas in classical predicate logic resolution is applied to literals, in our system resolution is applied to L(abelled) R(epresentation) S(tructures). Proofs are discovered by a refutation procedure defined on LRSs, that imposes (...) a hierarchy on clause sets of such structures together with an inheritance discipline. This is a form of Theory Resolution. For intuitionistic logic these structures are called I(ntuitionistic) R(epresentation) S(tructures). Their hierarchical structure allows the restriction of unification of individual variables and/or constants without using Skolem functions. This structures must therefore be preserved when we consider other (non-modal) logics. Variations between different logics are captured by fine tuning of the inheritance properties of the hierarchy. For modal and temporal logics IRS's are extended to structures that represent worlds and/or times. This enables us to consider all kinds of combined logics. (shrink)

Modeling a complex phenomena such as the mind presents tremendous computational complexity challenges. Modeling field theory (MFT) addresses these challenges in a non-traditional way. The main idea behind MFT is to match levels of uncertainty of the model (also, a problem or some theory) with levels of uncertainty of the evaluation criterion used to identify that model. When a model becomes more certain, then the evaluation criterion is adjusted dynamically to match that change to the model. This process is called (...) the Dynamic Logic of Phenomena (DLP) for model construction and it mimics processes of the mind and natural evolution. This paper provides a formal description of DLP by specifying its syntax, semantics, and reasoning system. We also outline links between DLP and other logical approaches. Computational complexity issues that motivate this work are presented using an example of polynomial models. (shrink)

Classical logic has proved inadequate in various areas of computer science, artificial intelligence, mathematics, philosopy and linguistics. This is an introduction to extensions of first-order logic, based on the principle that many-sorted logic (MSL) provides a unifying framework in which to place, for example, second-order logic, type theory, modal and dynamic logics and MSL itself. The aim is two fold: only one theorem-prover is needed; proofs of the metaproperties of the different existing calculi can be avoided by borrowing them from (...) MSL. To make the book accessible to readers from different disciplines, whilst maintaining precision, the author has supplied detailed step-by-step proofs, avoiding difficult arguments, and continually motivating the material with examples. Consequently this can be used as a reference, for self-teaching or for first-year graduate courses. (shrink)

In this paper, I argue that ad hominem arguments are not always fallacious. More explicitly, in certain cases of practical reasoning, the circumstances of a person are relevant to whether or not the conclusion should be accepted. This occurs, I suggest, when a person gives advice to others or prescribes certain courses of action but fails to follow her own advice or act in accordance with her own prescriptions. This is not an instance of a fallacious tu quoque provided that (...) such circumstantial ad hominem arguments are construed as rebuttals to appeals (administrative) authority (of expertise), or so I argue. (shrink)

Of the various accounts of negation that have been offered by logicians in the history of Western logic, that of negation as cancellation is a very distinctive one, quite different from the explosive accounts of modern "classical" and intuitionist logics, and from the accounts offered in standard relevant and paraconsistent logics. Despite its ancient origin, however, a precise understanding of the notion is still wanting. The first half of this paper offers one. Both conceptually and historically, the account of negation (...) as cancellation is intimately connected with connexivist principles such as ¬( ¬). Despite this, standard connexivist logics incorporate quite different accounts of negation. The second half of the paper shows how the cancellation account of negation of the first part gives rise to a semantics for a simple connexivist logic. (shrink)

This paper develops a new framework for combining propositional logics, called "juxtaposition". Several general metalogical theorems are proved concerning the combination of logics by juxtaposition. In particular, it is shown that under reasonable conditions, juxtaposition preserves strong soundness. Under reasonable conditions, the juxtaposition of two consequence relations is a conservative extension of each of them. A general strong completeness result is proved. The paper then examines the philosophically important case of the combination of classical and intuitionist logics. Particular attention is (...) paid to the phenomenon of collapse. It is shown that there are logics with two stocks of classical or intuitionist connectives that do not collapse. Finally, the paper briefy investigates the question of which rules, when added to these logics, lead to collapse. (shrink)

We continue our work [5] on the logic of multisets (or on the multiset semantics of linear logic), by interpreting further the additive disjunction . To this purpose we employ a more general class of processes, called free, the axiomatization of which requires a new rule (not compatible with the full LL), the cancellation rule. Disjunctive multisets are modeled as finite sets of multisets. The -Horn fragment of linear logic, with the cut rule slightly restricted, is sound with respect to (...) this semantics. Another rule, which is a slight modification of cancellation, added to HF makes the system sound and complete. (shrink)

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)

The core language can be extended by defining additional logical constants. E.g., we can add ‘→’ (implication), ‘∨’ (disjunction), and ‘∀x’ (universal quantifiers). The choice of logical primitives is not as optional in DPL as it is in standard predicate logic.

Imperatives cannot be true or false, so they are shunned by logicians. And yet imperatives can be combined by logical connectives: "kiss me and hug me" is the conjunction of "kiss me" with "hug me". This example may suggest that declarative and imperative logic are isomorphic: just as the conjunction of two declaratives is true exactly if both conjuncts are true, the conjunction of two imperatives is satisfied exactly if both conjuncts are satisfied—what more is there to say? Much more, (...) I argue. "If you love me, kiss me", a conditional imperative, mixes a declarative antecedent ("you love me") with an imperative consequent ("kiss me"); it is satisfied if you love and kiss me, violated if you love but don't kiss me, and avoided if you don't love me. So we need a logic of three -valued imperatives which mixes declaratives with imperatives. I develop such a logic. (shrink)

Suppose that a sign at the entrance of a hotel reads: “Don’t enter these premises unless you are accompanied by a registered guest”. You see someone who is about to enter, and you tell her: “Don’t enter these premises if you are an unaccompanied registered guest”. She asks why, and you reply: “It follows from what the sign says”. It seems that you made a valid inference from an imperative premise to an imperative conclusion. But it also seems that imperatives (...) cannot be true or false, so what does it mean to say that your inference is valid? It cannot mean that the truth of its premise guarantees the truth of its conclusion. One is thus faced with what is known as “Jørgensen’s dilemma” (Ross 1941: 55-6): it seems that imperative logic cannot exist because logic deals only with entities that, unlike imperatives, can be true or false, but it also seems that imperative logic must exist. It must exist not only because inferences with imperatives can be valid, but also because imperatives (like “Enter” and “Don’t enter”) can be inconsistent with each other, and also because one can apply logical operations to imperatives: “Don’t enter” is the negation of “Enter”, and “Sing or dance” is the disjunction of “Sing” and “Dance”. A standard reaction to this dilemma consists in basing imperative logic on analogues of truth and falsity. For example, the imperative “Don’t enter” is satisfied if you don’t enter and is violated if you enter, and one might say that an inference from an imperative premise to an imperative conclusion is valid exactly if the satisfaction (rather than the truth) of the premise guarantees the satisfaction of the conclusion. But before getting into the details, more needs to be said on what exactly imperatives are. (shrink)

We investigate a variant of the variable convention proposed at Tractatus 5.53ff for the purpose of eliminating the identity sign from logical notation. The variant in question is what Hintikka has called the strongly exclusive interpretation of the variables, and turns out to be what Ramsey initially (and erroneously) took to be Wittgenstein's intended method. We provide a tableau calculus for this identity-free logic, together with soundness and completeness proofs, as well as a proof of mutual interpretability with first-order logic (...) with identity. (shrink)